1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006 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 2 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; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
43 #include "tree-gimple.h"
47 #include "tree-pass.h"
49 #include "alloc-pool.h"
50 #include "splay-tree.h"
52 #include "tree-ssa-structalias.h"
55 #include "pointer-set.h"
57 /* The idea behind this analyzer is to generate set constraints from the
58 program, then solve the resulting constraints in order to generate the
61 Set constraints are a way of modeling program analysis problems that
62 involve sets. They consist of an inclusion constraint language,
63 describing the variables (each variable is a set) and operations that
64 are involved on the variables, and a set of rules that derive facts
65 from these operations. To solve a system of set constraints, you derive
66 all possible facts under the rules, which gives you the correct sets
69 See "Efficient Field-sensitive pointer analysis for C" by "David
70 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
71 http://citeseer.ist.psu.edu/pearce04efficient.html
73 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
74 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
75 http://citeseer.ist.psu.edu/heintze01ultrafast.html
77 There are three types of real constraint expressions, DEREF,
78 ADDRESSOF, and SCALAR. Each constraint expression consists
79 of a constraint type, a variable, and an offset.
81 SCALAR is a constraint expression type used to represent x, whether
82 it appears on the LHS or the RHS of a statement.
83 DEREF is a constraint expression type used to represent *x, whether
84 it appears on the LHS or the RHS of a statement.
85 ADDRESSOF is a constraint expression used to represent &x, whether
86 it appears on the LHS or the RHS of a statement.
88 Each pointer variable in the program is assigned an integer id, and
89 each field of a structure variable is assigned an integer id as well.
91 Structure variables are linked to their list of fields through a "next
92 field" in each variable that points to the next field in offset
94 Each variable for a structure field has
96 1. "size", that tells the size in bits of that field.
97 2. "fullsize, that tells the size in bits of the entire structure.
98 3. "offset", that tells the offset in bits from the beginning of the
99 structure to this field.
111 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
112 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
113 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
116 In order to solve the system of set constraints, the following is
119 1. Each constraint variable x has a solution set associated with it,
122 2. Constraints are separated into direct, copy, and complex.
123 Direct constraints are ADDRESSOF constraints that require no extra
124 processing, such as P = &Q
125 Copy constraints are those of the form P = Q.
126 Complex constraints are all the constraints involving dereferences
127 and offsets (including offsetted copies).
129 3. All direct constraints of the form P = &Q are processed, such
130 that Q is added to Sol(P)
132 4. All complex constraints for a given constraint variable are stored in a
133 linked list attached to that variable's node.
135 5. A directed graph is built out of the copy constraints. Each
136 constraint variable is a node in the graph, and an edge from
137 Q to P is added for each copy constraint of the form P = Q
139 6. The graph is then walked, and solution sets are
140 propagated along the copy edges, such that an edge from Q to P
141 causes Sol(P) <- Sol(P) union Sol(Q).
143 7. As we visit each node, all complex constraints associated with
144 that node are processed by adding appropriate copy edges to the graph, or the
145 appropriate variables to the solution set.
147 8. The process of walking the graph is iterated until no solution
150 Prior to walking the graph in steps 6 and 7, We perform static
151 cycle elimination on the constraint graph, as well
152 as off-line variable substitution.
154 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
155 on and turned into anything), but isn't. You can just see what offset
156 inside the pointed-to struct it's going to access.
158 TODO: Constant bounded arrays can be handled as if they were structs of the
159 same number of elements.
161 TODO: Modeling heap and incoming pointers becomes much better if we
162 add fields to them as we discover them, which we could do.
164 TODO: We could handle unions, but to be honest, it's probably not
165 worth the pain or slowdown. */
167 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map
)))
168 htab_t heapvar_for_stmt
;
170 static bool use_field_sensitive
= true;
171 static int in_ipa_mode
= 0;
173 /* Used for predecessor bitmaps. */
174 static bitmap_obstack predbitmap_obstack
;
176 /* Used for points-to sets. */
177 static bitmap_obstack pta_obstack
;
179 /* Used for oldsolution members of variables. */
180 static bitmap_obstack oldpta_obstack
;
182 /* Used for per-solver-iteration bitmaps. */
183 static bitmap_obstack iteration_obstack
;
185 static unsigned int create_variable_info_for (tree
, const char *);
186 typedef struct constraint_graph
*constraint_graph_t
;
187 static void unify_nodes (constraint_graph_t
, unsigned int, unsigned int, bool);
189 DEF_VEC_P(constraint_t
);
190 DEF_VEC_ALLOC_P(constraint_t
,heap
);
192 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
194 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
196 static struct constraint_stats
198 unsigned int total_vars
;
199 unsigned int nonpointer_vars
;
200 unsigned int unified_vars_static
;
201 unsigned int unified_vars_dynamic
;
202 unsigned int iterations
;
203 unsigned int num_edges
;
204 unsigned int num_implicit_edges
;
205 unsigned int points_to_sets_created
;
210 /* ID of this variable */
213 /* Name of this variable */
216 /* Tree that this variable is associated with. */
219 /* Offset of this variable, in bits, from the base variable */
220 unsigned HOST_WIDE_INT offset
;
222 /* Size of the variable, in bits. */
223 unsigned HOST_WIDE_INT size
;
225 /* Full size of the base variable, in bits. */
226 unsigned HOST_WIDE_INT fullsize
;
228 /* A link to the variable for the next field in this structure. */
229 struct variable_info
*next
;
231 /* True if the variable is directly the target of a dereference.
232 This is used to track which variables are *actually* dereferenced
233 so we can prune their points to listed. */
234 unsigned int directly_dereferenced
:1;
236 /* True if this is a variable created by the constraint analysis, such as
237 heap variables and constraints we had to break up. */
238 unsigned int is_artificial_var
:1;
240 /* True if this is a special variable whose solution set should not be
242 unsigned int is_special_var
:1;
244 /* True for variables whose size is not known or variable. */
245 unsigned int is_unknown_size_var
:1;
247 /* True for variables that have unions somewhere in them. */
248 unsigned int has_union
:1;
250 /* True if this is a heap variable. */
251 unsigned int is_heap_var
:1;
253 /* Points-to set for this variable. */
256 /* Old points-to set for this variable. */
259 /* Finished points-to set for this variable (IE what is returned
260 from find_what_p_points_to. */
261 bitmap finished_solution
;
263 /* Variable ids represented by this node. */
266 /* Variable id this was collapsed to due to type unsafety. This
267 should be unused completely after build_succ_graph, or something
269 struct variable_info
*collapsed_to
;
271 typedef struct variable_info
*varinfo_t
;
273 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
275 /* Pool of variable info structures. */
276 static alloc_pool variable_info_pool
;
278 DEF_VEC_P(varinfo_t
);
280 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
282 /* Table of variable info structures for constraint variables.
283 Indexed directly by variable info id. */
284 static VEC(varinfo_t
,heap
) *varmap
;
286 /* Return the varmap element N */
288 static inline varinfo_t
289 get_varinfo (unsigned int n
)
291 return VEC_index(varinfo_t
, varmap
, n
);
294 /* Return the varmap element N, following the collapsed_to link. */
296 static inline varinfo_t
297 get_varinfo_fc (unsigned int n
)
299 varinfo_t v
= VEC_index(varinfo_t
, varmap
, n
);
302 return v
->collapsed_to
;
306 /* Variable that represents the unknown pointer. */
307 static varinfo_t var_anything
;
308 static tree anything_tree
;
309 static unsigned int anything_id
;
311 /* Variable that represents the NULL pointer. */
312 static varinfo_t var_nothing
;
313 static tree nothing_tree
;
314 static unsigned int nothing_id
;
316 /* Variable that represents read only memory. */
317 static varinfo_t var_readonly
;
318 static tree readonly_tree
;
319 static unsigned int readonly_id
;
321 /* Variable that represents integers. This is used for when people do things
323 static varinfo_t var_integer
;
324 static tree integer_tree
;
325 static unsigned int integer_id
;
327 /* Lookup a heap var for FROM, and return it if we find one. */
330 heapvar_lookup (tree from
)
332 struct tree_map
*h
, in
;
335 h
= htab_find_with_hash (heapvar_for_stmt
, &in
, htab_hash_pointer (from
));
341 /* Insert a mapping FROM->TO in the heap var for statement
345 heapvar_insert (tree from
, tree to
)
350 h
= ggc_alloc (sizeof (struct tree_map
));
351 h
->hash
= htab_hash_pointer (from
);
354 loc
= htab_find_slot_with_hash (heapvar_for_stmt
, h
, h
->hash
, INSERT
);
355 *(struct tree_map
**) loc
= h
;
358 /* Return a new variable info structure consisting for a variable
359 named NAME, and using constraint graph node NODE. */
362 new_var_info (tree t
, unsigned int id
, const char *name
)
364 varinfo_t ret
= pool_alloc (variable_info_pool
);
369 ret
->directly_dereferenced
= false;
370 ret
->is_artificial_var
= false;
371 ret
->is_heap_var
= false;
372 ret
->is_special_var
= false;
373 ret
->is_unknown_size_var
= false;
374 ret
->has_union
= false;
375 ret
->solution
= BITMAP_ALLOC (&pta_obstack
);
376 ret
->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
377 ret
->finished_solution
= NULL
;
379 ret
->collapsed_to
= NULL
;
383 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
385 /* An expression that appears in a constraint. */
387 struct constraint_expr
389 /* Constraint type. */
390 constraint_expr_type type
;
392 /* Variable we are referring to in the constraint. */
395 /* Offset, in bits, of this constraint from the beginning of
396 variables it ends up referring to.
398 IOW, in a deref constraint, we would deref, get the result set,
399 then add OFFSET to each member. */
400 unsigned HOST_WIDE_INT offset
;
403 typedef struct constraint_expr ce_s
;
405 DEF_VEC_ALLOC_O(ce_s
, heap
);
406 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
407 static void do_deref (VEC (ce_s
, heap
) **);
409 /* Our set constraints are made up of two constraint expressions, one
412 As described in the introduction, our set constraints each represent an
413 operation between set valued variables.
417 struct constraint_expr lhs
;
418 struct constraint_expr rhs
;
421 /* List of constraints that we use to build the constraint graph from. */
423 static VEC(constraint_t
,heap
) *constraints
;
424 static alloc_pool constraint_pool
;
428 DEF_VEC_ALLOC_I(int, heap
);
430 /* The constraint graph is represented as an array of bitmaps
431 containing successor nodes. */
433 struct constraint_graph
435 /* Size of this graph, which may be different than the number of
436 nodes in the variable map. */
439 /* Explicit successors of each node. */
442 /* Implicit predecessors of each node (Used for variable
444 bitmap
*implicit_preds
;
446 /* Explicit predecessors of each node (Used for variable substitution). */
449 /* Indirect cycle representatives, or -1 if the node has no indirect
451 int *indirect_cycles
;
453 /* Representative node for a node. rep[a] == a unless the node has
457 /* Equivalence class representative for a node. This is used for
458 variable substitution. */
461 /* Label for each node, used during variable substitution. */
464 /* Bitmap of nodes where the bit is set if the node is a direct
465 node. Used for variable substitution. */
466 sbitmap direct_nodes
;
468 /* Vector of complex constraints for each graph node. Complex
469 constraints are those involving dereferences or offsets that are
471 VEC(constraint_t
,heap
) **complex;
474 static constraint_graph_t graph
;
476 /* During variable substitution and the offline version of indirect
477 cycle finding, we create nodes to represent dereferences and
478 address taken constraints. These represent where these start and
480 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
481 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
482 #define FIRST_ADDR_NODE (LAST_REF_NODE + 1)
484 /* Return the representative node for NODE, if NODE has been unioned
486 This function performs path compression along the way to finding
487 the representative. */
490 find (unsigned int node
)
492 gcc_assert (node
< graph
->size
);
493 if (graph
->rep
[node
] != node
)
494 return graph
->rep
[node
] = find (graph
->rep
[node
]);
498 /* Union the TO and FROM nodes to the TO nodes.
499 Note that at some point in the future, we may want to do
500 union-by-rank, in which case we are going to have to return the
501 node we unified to. */
504 unite (unsigned int to
, unsigned int from
)
506 gcc_assert (to
< graph
->size
&& from
< graph
->size
);
507 if (to
!= from
&& graph
->rep
[from
] != to
)
509 graph
->rep
[from
] = to
;
515 /* Create a new constraint consisting of LHS and RHS expressions. */
518 new_constraint (const struct constraint_expr lhs
,
519 const struct constraint_expr rhs
)
521 constraint_t ret
= pool_alloc (constraint_pool
);
527 /* Print out constraint C to FILE. */
530 dump_constraint (FILE *file
, constraint_t c
)
532 if (c
->lhs
.type
== ADDRESSOF
)
534 else if (c
->lhs
.type
== DEREF
)
536 fprintf (file
, "%s", get_varinfo_fc (c
->lhs
.var
)->name
);
537 if (c
->lhs
.offset
!= 0)
538 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
539 fprintf (file
, " = ");
540 if (c
->rhs
.type
== ADDRESSOF
)
542 else if (c
->rhs
.type
== DEREF
)
544 fprintf (file
, "%s", get_varinfo_fc (c
->rhs
.var
)->name
);
545 if (c
->rhs
.offset
!= 0)
546 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
547 fprintf (file
, "\n");
550 /* Print out constraint C to stderr. */
553 debug_constraint (constraint_t c
)
555 dump_constraint (stderr
, c
);
558 /* Print out all constraints to FILE */
561 dump_constraints (FILE *file
)
565 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
566 dump_constraint (file
, c
);
569 /* Print out all constraints to stderr. */
572 debug_constraints (void)
574 dump_constraints (stderr
);
579 The solver is a simple worklist solver, that works on the following
582 sbitmap changed_nodes = all zeroes;
584 For each node that is not already collapsed:
586 set bit in changed nodes
588 while (changed_count > 0)
590 compute topological ordering for constraint graph
592 find and collapse cycles in the constraint graph (updating
593 changed if necessary)
595 for each node (n) in the graph in topological order:
598 Process each complex constraint associated with the node,
599 updating changed if necessary.
601 For each outgoing edge from n, propagate the solution from n to
602 the destination of the edge, updating changed as necessary.
606 /* Return true if two constraint expressions A and B are equal. */
609 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
611 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
614 /* Return true if constraint expression A is less than constraint expression
615 B. This is just arbitrary, but consistent, in order to give them an
619 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
621 if (a
.type
== b
.type
)
624 return a
.offset
< b
.offset
;
626 return a
.var
< b
.var
;
629 return a
.type
< b
.type
;
632 /* Return true if constraint A is less than constraint B. This is just
633 arbitrary, but consistent, in order to give them an ordering. */
636 constraint_less (const constraint_t a
, const constraint_t b
)
638 if (constraint_expr_less (a
->lhs
, b
->lhs
))
640 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
643 return constraint_expr_less (a
->rhs
, b
->rhs
);
646 /* Return true if two constraints A and B are equal. */
649 constraint_equal (struct constraint a
, struct constraint b
)
651 return constraint_expr_equal (a
.lhs
, b
.lhs
)
652 && constraint_expr_equal (a
.rhs
, b
.rhs
);
656 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
659 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
660 struct constraint lookfor
)
668 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
669 if (place
>= VEC_length (constraint_t
, vec
))
671 found
= VEC_index (constraint_t
, vec
, place
);
672 if (!constraint_equal (*found
, lookfor
))
677 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
680 constraint_set_union (VEC(constraint_t
,heap
) **to
,
681 VEC(constraint_t
,heap
) **from
)
686 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
688 if (constraint_vec_find (*to
, *c
) == NULL
)
690 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
692 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
697 /* Take a solution set SET, add OFFSET to each member of the set, and
698 overwrite SET with the result when done. */
701 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
703 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
707 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
709 /* If this is a properly sized variable, only add offset if it's
710 less than end. Otherwise, it is globbed to a single
713 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
715 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
716 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
719 bitmap_set_bit (result
, v
->id
);
721 else if (get_varinfo (i
)->is_artificial_var
722 || get_varinfo (i
)->has_union
723 || get_varinfo (i
)->is_unknown_size_var
)
725 bitmap_set_bit (result
, i
);
729 bitmap_copy (set
, result
);
730 BITMAP_FREE (result
);
733 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
737 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
740 return bitmap_ior_into (to
, from
);
746 tmp
= BITMAP_ALLOC (&iteration_obstack
);
747 bitmap_copy (tmp
, from
);
748 solution_set_add (tmp
, inc
);
749 res
= bitmap_ior_into (to
, tmp
);
755 /* Insert constraint C into the list of complex constraints for graph
759 insert_into_complex (constraint_graph_t graph
,
760 unsigned int var
, constraint_t c
)
762 VEC (constraint_t
, heap
) *complex = graph
->complex[var
];
763 unsigned int place
= VEC_lower_bound (constraint_t
, complex, c
,
766 /* Only insert constraints that do not already exist. */
767 if (place
>= VEC_length (constraint_t
, complex)
768 || !constraint_equal (*c
, *VEC_index (constraint_t
, complex, place
)))
769 VEC_safe_insert (constraint_t
, heap
, graph
->complex[var
], place
, c
);
773 /* Condense two variable nodes into a single variable node, by moving
774 all associated info from SRC to TO. */
777 merge_node_constraints (constraint_graph_t graph
, unsigned int to
,
783 gcc_assert (find (from
) == to
);
785 /* Move all complex constraints from src node into to node */
786 for (i
= 0; VEC_iterate (constraint_t
, graph
->complex[from
], i
, c
); i
++)
788 /* In complex constraints for node src, we may have either
789 a = *src, and *src = a, or an offseted constraint which are
790 always added to the rhs node's constraints. */
792 if (c
->rhs
.type
== DEREF
)
794 else if (c
->lhs
.type
== DEREF
)
799 constraint_set_union (&graph
->complex[to
], &graph
->complex[from
]);
800 VEC_free (constraint_t
, heap
, graph
->complex[from
]);
801 graph
->complex[from
] = NULL
;
805 /* Remove edges involving NODE from GRAPH. */
808 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
810 if (graph
->succs
[node
])
811 BITMAP_FREE (graph
->succs
[node
]);
814 /* Merge GRAPH nodes FROM and TO into node TO. */
817 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
820 if (graph
->indirect_cycles
[from
] != -1)
822 /* If we have indirect cycles with the from node, and we have
823 none on the to node, the to node has indirect cycles from the
824 from node now that they are unified.
825 If indirect cycles exist on both, unify the nodes that they
826 are in a cycle with, since we know they are in a cycle with
828 if (graph
->indirect_cycles
[to
] == -1)
830 graph
->indirect_cycles
[to
] = graph
->indirect_cycles
[from
];
834 unsigned int tonode
= find (graph
->indirect_cycles
[to
]);
835 unsigned int fromnode
= find (graph
->indirect_cycles
[from
]);
837 if (unite (tonode
, fromnode
))
838 unify_nodes (graph
, tonode
, fromnode
, true);
842 /* Merge all the successor edges. */
843 if (graph
->succs
[from
])
845 if (!graph
->succs
[to
])
846 graph
->succs
[to
] = BITMAP_ALLOC (&pta_obstack
);
847 bitmap_ior_into (graph
->succs
[to
],
851 clear_edges_for_node (graph
, from
);
855 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
856 it doesn't exist in the graph already. */
859 add_implicit_graph_edge (constraint_graph_t graph
, unsigned int to
,
865 if (!graph
->implicit_preds
[to
])
866 graph
->implicit_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
868 if (!bitmap_bit_p (graph
->implicit_preds
[to
], from
))
870 stats
.num_implicit_edges
++;
871 bitmap_set_bit (graph
->implicit_preds
[to
], from
);
875 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
876 it doesn't exist in the graph already.
877 Return false if the edge already existed, true otherwise. */
880 add_pred_graph_edge (constraint_graph_t graph
, unsigned int to
,
883 if (!graph
->preds
[to
])
884 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
885 if (!bitmap_bit_p (graph
->preds
[to
], from
))
886 bitmap_set_bit (graph
->preds
[to
], from
);
889 /* Add a graph edge to GRAPH, going from FROM to TO if
890 it doesn't exist in the graph already.
891 Return false if the edge already existed, true otherwise. */
894 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
905 if (!graph
->succs
[from
])
906 graph
->succs
[from
] = BITMAP_ALLOC (&pta_obstack
);
907 if (!bitmap_bit_p (graph
->succs
[from
], to
))
910 if (to
< FIRST_REF_NODE
&& from
< FIRST_REF_NODE
)
912 bitmap_set_bit (graph
->succs
[from
], to
);
919 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
922 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
925 return (graph
->succs
[dest
]
926 && bitmap_bit_p (graph
->succs
[dest
], src
));
929 /* Build the constraint graph, adding only predecessor edges right now. */
932 build_pred_graph (void)
938 graph
= XNEW (struct constraint_graph
);
939 graph
->size
= (VEC_length (varinfo_t
, varmap
)) * 3;
940 graph
->succs
= XCNEWVEC (bitmap
, graph
->size
);
941 graph
->implicit_preds
= XCNEWVEC (bitmap
, graph
->size
);
942 graph
->preds
= XCNEWVEC (bitmap
, graph
->size
);
943 graph
->indirect_cycles
= XNEWVEC (int, VEC_length (varinfo_t
, varmap
));
944 graph
->label
= XCNEWVEC (unsigned int, graph
->size
);
945 graph
->rep
= XNEWVEC (unsigned int, graph
->size
);
946 graph
->eq_rep
= XNEWVEC (int, graph
->size
);
947 graph
->complex = XCNEWVEC (VEC(constraint_t
, heap
) *,
948 VEC_length (varinfo_t
, varmap
));
949 graph
->direct_nodes
= sbitmap_alloc (graph
->size
);
950 sbitmap_zero (graph
->direct_nodes
);
952 for (j
= 0; j
< FIRST_REF_NODE
; j
++)
954 if (!get_varinfo (j
)->is_special_var
)
955 SET_BIT (graph
->direct_nodes
, j
);
958 for (j
= 0; j
< graph
->size
; j
++)
961 graph
->eq_rep
[j
] = -1;
964 for (j
= 0; j
< VEC_length (varinfo_t
, varmap
); j
++)
965 graph
->indirect_cycles
[j
] = -1;
967 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
969 struct constraint_expr lhs
= c
->lhs
;
970 struct constraint_expr rhs
= c
->rhs
;
971 unsigned int lhsvar
= get_varinfo_fc (lhs
.var
)->id
;
972 unsigned int rhsvar
= get_varinfo_fc (rhs
.var
)->id
;
974 if (lhs
.type
== DEREF
)
977 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
978 add_pred_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
979 if (rhs
.type
== ADDRESSOF
)
980 RESET_BIT (graph
->direct_nodes
, rhsvar
);
982 else if (rhs
.type
== DEREF
)
985 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
986 add_pred_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
988 RESET_BIT (graph
->direct_nodes
, lhsvar
);
990 else if (rhs
.type
== ADDRESSOF
)
993 add_pred_graph_edge (graph
, lhsvar
, FIRST_ADDR_NODE
+ rhsvar
);
994 /* Implicitly, *x = y */
995 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
997 RESET_BIT (graph
->direct_nodes
, rhsvar
);
999 else if (lhsvar
> anything_id
1000 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1003 add_pred_graph_edge (graph
, lhsvar
, rhsvar
);
1004 /* Implicitly, *x = *y */
1005 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
,
1006 FIRST_REF_NODE
+ rhsvar
);
1008 else if (lhs
.offset
!= 0 || rhs
.offset
!= 0)
1010 if (rhs
.offset
!= 0)
1011 RESET_BIT (graph
->direct_nodes
, lhs
.var
);
1012 if (lhs
.offset
!= 0)
1013 RESET_BIT (graph
->direct_nodes
, rhs
.var
);
1018 /* Build the constraint graph, adding successor edges. */
1021 build_succ_graph (void)
1026 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1028 struct constraint_expr lhs
;
1029 struct constraint_expr rhs
;
1030 unsigned int lhsvar
;
1031 unsigned int rhsvar
;
1038 lhsvar
= find (get_varinfo_fc (lhs
.var
)->id
);
1039 rhsvar
= find (get_varinfo_fc (rhs
.var
)->id
);
1041 if (lhs
.type
== DEREF
)
1043 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1044 add_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1046 else if (rhs
.type
== DEREF
)
1048 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1049 add_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1051 else if (rhs
.type
== ADDRESSOF
)
1054 gcc_assert (find (get_varinfo_fc (rhs
.var
)->id
)
1055 == get_varinfo_fc (rhs
.var
)->id
);
1056 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1058 else if (lhsvar
> anything_id
1059 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1061 add_graph_edge (graph
, lhsvar
, rhsvar
);
1067 /* Changed variables on the last iteration. */
1068 static unsigned int changed_count
;
1069 static sbitmap changed
;
1071 DEF_VEC_I(unsigned);
1072 DEF_VEC_ALLOC_I(unsigned,heap
);
1075 /* Strongly Connected Component visitation info. */
1082 unsigned int *node_mapping
;
1084 VEC(unsigned,heap
) *scc_stack
;
1088 /* Recursive routine to find strongly connected components in GRAPH.
1089 SI is the SCC info to store the information in, and N is the id of current
1090 graph node we are processing.
1092 This is Tarjan's strongly connected component finding algorithm, as
1093 modified by Nuutila to keep only non-root nodes on the stack.
1094 The algorithm can be found in "On finding the strongly connected
1095 connected components in a directed graph" by Esko Nuutila and Eljas
1096 Soisalon-Soininen, in Information Processing Letters volume 49,
1097 number 1, pages 9-14. */
1100 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1104 unsigned int my_dfs
;
1106 SET_BIT (si
->visited
, n
);
1107 si
->dfs
[n
] = si
->current_index
++;
1108 my_dfs
= si
->dfs
[n
];
1110 /* Visit all the successors. */
1111 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
1115 if (i
> LAST_REF_NODE
)
1119 if (TEST_BIT (si
->roots
, w
))
1122 if (!TEST_BIT (si
->visited
, w
))
1123 scc_visit (graph
, si
, w
);
1125 unsigned int t
= find (w
);
1126 unsigned int nnode
= find (n
);
1127 gcc_assert(nnode
== n
);
1129 if (si
->dfs
[t
] < si
->dfs
[nnode
])
1130 si
->dfs
[n
] = si
->dfs
[t
];
1134 /* See if any components have been identified. */
1135 if (si
->dfs
[n
] == my_dfs
)
1137 if (VEC_length (unsigned, si
->scc_stack
) > 0
1138 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1140 bitmap scc
= BITMAP_ALLOC (NULL
);
1141 bool have_ref_node
= n
>= FIRST_REF_NODE
;
1142 unsigned int lowest_node
;
1145 bitmap_set_bit (scc
, n
);
1147 while (VEC_length (unsigned, si
->scc_stack
) != 0
1148 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1150 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1152 bitmap_set_bit (scc
, w
);
1153 if (w
>= FIRST_REF_NODE
)
1154 have_ref_node
= true;
1157 lowest_node
= bitmap_first_set_bit (scc
);
1158 gcc_assert (lowest_node
< FIRST_REF_NODE
);
1159 EXECUTE_IF_SET_IN_BITMAP (scc
, 0, i
, bi
)
1161 if (i
< FIRST_REF_NODE
)
1163 /* Mark this node for collapsing. */
1164 if (unite (lowest_node
, i
))
1165 unify_nodes (graph
, lowest_node
, i
, false);
1169 unite (lowest_node
, i
);
1170 graph
->indirect_cycles
[i
- FIRST_REF_NODE
] = lowest_node
;
1174 SET_BIT (si
->roots
, n
);
1177 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1180 /* Unify node FROM into node TO, updating the changed count if
1181 necessary when UPDATE_CHANGED is true. */
1184 unify_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1185 bool update_changed
)
1188 gcc_assert (to
!= from
&& find (to
) == to
);
1189 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1190 fprintf (dump_file
, "Unifying %s to %s\n",
1191 get_varinfo (from
)->name
,
1192 get_varinfo (to
)->name
);
1195 stats
.unified_vars_dynamic
++;
1197 stats
.unified_vars_static
++;
1199 merge_graph_nodes (graph
, to
, from
);
1200 merge_node_constraints (graph
, to
, from
);
1202 if (update_changed
&& TEST_BIT (changed
, from
))
1204 RESET_BIT (changed
, from
);
1205 if (!TEST_BIT (changed
, to
))
1206 SET_BIT (changed
, to
);
1209 gcc_assert (changed_count
> 0);
1214 /* If the solution changes because of the merging, we need to mark
1215 the variable as changed. */
1216 if (bitmap_ior_into (get_varinfo (to
)->solution
,
1217 get_varinfo (from
)->solution
))
1219 if (update_changed
&& !TEST_BIT (changed
, to
))
1221 SET_BIT (changed
, to
);
1226 BITMAP_FREE (get_varinfo (from
)->solution
);
1227 BITMAP_FREE (get_varinfo (from
)->oldsolution
);
1229 if (stats
.iterations
> 0)
1231 BITMAP_FREE (get_varinfo (to
)->oldsolution
);
1232 get_varinfo (to
)->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
1235 if (valid_graph_edge (graph
, to
, to
))
1237 if (graph
->succs
[to
])
1238 bitmap_clear_bit (graph
->succs
[to
], to
);
1242 /* Information needed to compute the topological ordering of a graph. */
1246 /* sbitmap of visited nodes. */
1248 /* Array that stores the topological order of the graph, *in
1250 VEC(unsigned,heap
) *topo_order
;
1254 /* Initialize and return a topological info structure. */
1256 static struct topo_info
*
1257 init_topo_info (void)
1259 size_t size
= VEC_length (varinfo_t
, varmap
);
1260 struct topo_info
*ti
= XNEW (struct topo_info
);
1261 ti
->visited
= sbitmap_alloc (size
);
1262 sbitmap_zero (ti
->visited
);
1263 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1268 /* Free the topological sort info pointed to by TI. */
1271 free_topo_info (struct topo_info
*ti
)
1273 sbitmap_free (ti
->visited
);
1274 VEC_free (unsigned, heap
, ti
->topo_order
);
1278 /* Visit the graph in topological order, and store the order in the
1279 topo_info structure. */
1282 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1288 SET_BIT (ti
->visited
, n
);
1290 if (graph
->succs
[n
])
1291 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[n
], 0, j
, bi
)
1293 if (!TEST_BIT (ti
->visited
, j
))
1294 topo_visit (graph
, ti
, j
);
1297 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1300 /* Return true if variable N + OFFSET is a legal field of N. */
1303 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1305 varinfo_t ninfo
= get_varinfo (n
);
1307 /* For things we've globbed to single variables, any offset into the
1308 variable acts like the entire variable, so that it becomes offset
1310 if (ninfo
->is_special_var
1311 || ninfo
->is_artificial_var
1312 || ninfo
->is_unknown_size_var
)
1317 return (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1320 /* Process a constraint C that represents *x = &y. */
1323 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1324 constraint_t c
, bitmap delta
)
1326 unsigned int rhs
= c
->rhs
.var
;
1330 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1331 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1333 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1334 if (type_safe (j
, &offset
) && !(get_varinfo (j
)->is_special_var
))
1336 /* *x != NULL && *x != ANYTHING*/
1340 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1342 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1346 sol
= get_varinfo (t
)->solution
;
1347 if (!bitmap_bit_p (sol
, rhs
))
1349 bitmap_set_bit (sol
, rhs
);
1350 if (!TEST_BIT (changed
, t
))
1352 SET_BIT (changed
, t
);
1357 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1358 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1363 /* Process a constraint C that represents x = *y, using DELTA as the
1364 starting solution. */
1367 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1370 unsigned int lhs
= find (c
->lhs
.var
);
1372 bitmap sol
= get_varinfo (lhs
)->solution
;
1376 if (bitmap_bit_p (delta
, anything_id
))
1378 flag
= !bitmap_bit_p (sol
, anything_id
);
1380 bitmap_set_bit (sol
, anything_id
);
1383 /* For each variable j in delta (Sol(y)), add
1384 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1385 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1387 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1388 if (type_safe (j
, &roffset
))
1391 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1394 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1399 /* Adding edges from the special vars is pointless.
1400 They don't have sets that can change. */
1401 if (get_varinfo (t
) ->is_special_var
)
1402 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1403 else if (add_graph_edge (graph
, lhs
, t
))
1404 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1406 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1407 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1412 /* If the LHS solution changed, mark the var as changed. */
1415 get_varinfo (lhs
)->solution
= sol
;
1416 if (!TEST_BIT (changed
, lhs
))
1418 SET_BIT (changed
, lhs
);
1424 /* Process a constraint C that represents *x = y. */
1427 do_ds_constraint (constraint_t c
, bitmap delta
)
1429 unsigned int rhs
= find (c
->rhs
.var
);
1430 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1431 bitmap sol
= get_varinfo (rhs
)->solution
;
1435 if (bitmap_bit_p (sol
, anything_id
))
1437 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1439 varinfo_t jvi
= get_varinfo (j
);
1441 unsigned int loff
= c
->lhs
.offset
;
1442 unsigned HOST_WIDE_INT fieldoffset
= jvi
->offset
+ loff
;
1445 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1450 if (!bitmap_bit_p (get_varinfo (t
)->solution
, anything_id
))
1452 bitmap_set_bit (get_varinfo (t
)->solution
, anything_id
);
1453 if (!TEST_BIT (changed
, t
))
1455 SET_BIT (changed
, t
);
1463 /* For each member j of delta (Sol(x)), add an edge from y to j and
1464 union Sol(y) into Sol(j) */
1465 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1467 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1468 if (type_safe (j
, &loff
) && !(get_varinfo(j
)->is_special_var
))
1472 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1475 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1479 tmp
= get_varinfo (t
)->solution
;
1481 if (set_union_with_increment (tmp
, sol
, roff
))
1483 get_varinfo (t
)->solution
= tmp
;
1485 sol
= get_varinfo (rhs
)->solution
;
1486 if (!TEST_BIT (changed
, t
))
1488 SET_BIT (changed
, t
);
1493 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1494 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1498 /* Handle a non-simple (simple meaning requires no iteration),
1499 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1502 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1504 if (c
->lhs
.type
== DEREF
)
1506 if (c
->rhs
.type
== ADDRESSOF
)
1509 do_da_constraint (graph
, c
, delta
);
1514 do_ds_constraint (c
, delta
);
1517 else if (c
->rhs
.type
== DEREF
)
1520 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1521 do_sd_constraint (graph
, c
, delta
);
1530 gcc_assert(c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
);
1531 t
= find (c
->rhs
.var
);
1532 solution
= get_varinfo (t
)->solution
;
1533 t
= find (c
->lhs
.var
);
1534 tmp
= get_varinfo (t
)->solution
;
1536 flag
= set_union_with_increment (tmp
, solution
, c
->rhs
.offset
);
1540 get_varinfo (t
)->solution
= tmp
;
1541 if (!TEST_BIT (changed
, c
->lhs
.var
))
1543 SET_BIT (changed
, c
->lhs
.var
);
1550 /* Initialize and return a new SCC info structure. */
1552 static struct scc_info
*
1553 init_scc_info (size_t size
)
1555 struct scc_info
*si
= XNEW (struct scc_info
);
1558 si
->current_index
= 0;
1559 si
->visited
= sbitmap_alloc (size
);
1560 sbitmap_zero (si
->visited
);
1561 si
->roots
= sbitmap_alloc (size
);
1562 sbitmap_zero (si
->roots
);
1563 si
->node_mapping
= XNEWVEC (unsigned int, size
);
1564 si
->dfs
= XCNEWVEC (unsigned int, size
);
1566 for (i
= 0; i
< size
; i
++)
1567 si
->node_mapping
[i
] = i
;
1569 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1573 /* Free an SCC info structure pointed to by SI */
1576 free_scc_info (struct scc_info
*si
)
1578 sbitmap_free (si
->visited
);
1579 sbitmap_free (si
->roots
);
1580 free (si
->node_mapping
);
1582 VEC_free (unsigned, heap
, si
->scc_stack
);
1587 /* Find indirect cycles in GRAPH that occur, using strongly connected
1588 components, and note them in the indirect cycles map.
1590 This technique comes from Ben Hardekopf and Calvin Lin,
1591 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1592 Lines of Code", submitted to PLDI 2007. */
1595 find_indirect_cycles (constraint_graph_t graph
)
1598 unsigned int size
= graph
->size
;
1599 struct scc_info
*si
= init_scc_info (size
);
1601 for (i
= 0; i
< MIN (LAST_REF_NODE
, size
); i
++ )
1602 if (!TEST_BIT (si
->visited
, i
) && find (i
) == i
)
1603 scc_visit (graph
, si
, i
);
1608 /* Compute a topological ordering for GRAPH, and store the result in the
1609 topo_info structure TI. */
1612 compute_topo_order (constraint_graph_t graph
,
1613 struct topo_info
*ti
)
1616 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1618 for (i
= 0; i
!= size
; ++i
)
1619 if (!TEST_BIT (ti
->visited
, i
) && find (i
) == i
)
1620 topo_visit (graph
, ti
, i
);
1623 /* Perform offline variable substitution.
1625 This is a linear time way of identifying variables that must have
1626 equivalent points-to sets, including those caused by static cycles,
1627 and single entry subgraphs, in the constraint graph.
1629 The technique is described in "Off-line variable substitution for
1630 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1631 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56.
1633 There is an optimal way to do this involving hash based value
1634 numbering, once the technique is published i will implement it
1637 The general method of finding equivalence classes is as follows:
1638 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1639 Add fake nodes (ADDRESS nodes) and edges for a = &b constraints.
1640 Initialize all non-REF/ADDRESS nodes to be direct nodes
1641 For each SCC in the predecessor graph:
1642 for each member (x) of the SCC
1643 if x is not a direct node:
1644 set rootnode(SCC) to be not a direct node
1645 collapse node x into rootnode(SCC).
1646 if rootnode(SCC) is not a direct node:
1647 label rootnode(SCC) with a new equivalence class
1649 if all labeled predecessors of rootnode(SCC) have the same
1651 label rootnode(SCC) with this label
1653 label rootnode(SCC) with a new equivalence class
1655 All direct nodes with the same equivalence class can be replaced
1656 with a single representative node.
1657 All unlabeled nodes (label == 0) are not pointers and all edges
1658 involving them can be eliminated.
1659 We perform these optimizations during move_complex_constraints.
1662 static int equivalence_class
;
1664 /* Recursive routine to find strongly connected components in GRAPH,
1665 and label it's nodes with equivalence classes.
1666 This is used during variable substitution to find cycles involving
1667 the regular or implicit predecessors, and label them as equivalent.
1668 The SCC finding algorithm used is the same as that for scc_visit. */
1671 label_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1675 unsigned int my_dfs
;
1677 gcc_assert (si
->node_mapping
[n
] == n
);
1678 SET_BIT (si
->visited
, n
);
1679 si
->dfs
[n
] = si
->current_index
++;
1680 my_dfs
= si
->dfs
[n
];
1682 /* Visit all the successors. */
1683 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
1685 unsigned int w
= si
->node_mapping
[i
];
1687 if (TEST_BIT (si
->roots
, w
))
1690 if (!TEST_BIT (si
->visited
, w
))
1691 label_visit (graph
, si
, w
);
1693 unsigned int t
= si
->node_mapping
[w
];
1694 unsigned int nnode
= si
->node_mapping
[n
];
1695 gcc_assert(nnode
== n
);
1697 if (si
->dfs
[t
] < si
->dfs
[nnode
])
1698 si
->dfs
[n
] = si
->dfs
[t
];
1702 /* Visit all the implicit predecessors. */
1703 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->implicit_preds
[n
], 0, i
, bi
)
1705 unsigned int w
= si
->node_mapping
[i
];
1707 if (TEST_BIT (si
->roots
, w
))
1710 if (!TEST_BIT (si
->visited
, w
))
1711 label_visit (graph
, si
, w
);
1713 unsigned int t
= si
->node_mapping
[w
];
1714 unsigned int nnode
= si
->node_mapping
[n
];
1715 gcc_assert (nnode
== n
);
1717 if (si
->dfs
[t
] < si
->dfs
[nnode
])
1718 si
->dfs
[n
] = si
->dfs
[t
];
1722 /* See if any components have been identified. */
1723 if (si
->dfs
[n
] == my_dfs
)
1725 while (VEC_length (unsigned, si
->scc_stack
) != 0
1726 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1728 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1729 si
->node_mapping
[w
] = n
;
1731 if (!TEST_BIT (graph
->direct_nodes
, w
))
1732 RESET_BIT (graph
->direct_nodes
, n
);
1734 SET_BIT (si
->roots
, n
);
1736 if (!TEST_BIT (graph
->direct_nodes
, n
))
1738 graph
->label
[n
] = equivalence_class
++;
1742 unsigned int size
= 0;
1743 unsigned int firstlabel
= ~0;
1745 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
1747 unsigned int j
= si
->node_mapping
[i
];
1749 if (j
== n
|| graph
->label
[j
] == 0)
1752 if (firstlabel
== (unsigned int)~0)
1754 firstlabel
= graph
->label
[j
];
1757 else if (graph
->label
[j
] != firstlabel
)
1762 graph
->label
[n
] = 0;
1764 graph
->label
[n
] = firstlabel
;
1766 graph
->label
[n
] = equivalence_class
++;
1770 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1773 /* Perform offline variable substitution, discovering equivalence
1774 classes, and eliminating non-pointer variables. */
1776 static struct scc_info
*
1777 perform_var_substitution (constraint_graph_t graph
)
1780 unsigned int size
= graph
->size
;
1781 struct scc_info
*si
= init_scc_info (size
);
1783 bitmap_obstack_initialize (&iteration_obstack
);
1784 equivalence_class
= 0;
1786 /* We only need to visit the non-address nodes for labeling
1787 purposes, as the address nodes will never have any predecessors,
1788 because &x never appears on the LHS of a constraint. */
1789 for (i
= 0; i
< LAST_REF_NODE
; i
++)
1790 if (!TEST_BIT (si
->visited
, si
->node_mapping
[i
]))
1791 label_visit (graph
, si
, si
->node_mapping
[i
]);
1793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1794 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
1796 bool direct_node
= TEST_BIT (graph
->direct_nodes
, i
);
1798 "Equivalence class for %s node id %d:%s is %d\n",
1799 direct_node
? "Direct node" : "Indirect node", i
,
1800 get_varinfo(i
)->name
,
1801 graph
->label
[si
->node_mapping
[i
]]);
1804 /* Quickly eliminate our non-pointer variables. */
1806 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
1808 unsigned int node
= si
->node_mapping
[i
];
1810 if (graph
->label
[node
] == 0 && TEST_BIT (graph
->direct_nodes
, node
))
1812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1814 "%s is a non-pointer variable, eliminating edges.\n",
1815 get_varinfo (node
)->name
);
1816 stats
.nonpointer_vars
++;
1817 clear_edges_for_node (graph
, node
);
1823 /* Free information that was only necessary for variable
1827 free_var_substitution_info (struct scc_info
*si
)
1830 free (graph
->label
);
1831 free (graph
->eq_rep
);
1832 sbitmap_free (graph
->direct_nodes
);
1833 bitmap_obstack_release (&iteration_obstack
);
1836 /* Return an existing node that is equivalent to NODE, which has
1837 equivalence class LABEL, if one exists. Return NODE otherwise. */
1840 find_equivalent_node (constraint_graph_t graph
,
1841 unsigned int node
, unsigned int label
)
1843 /* If the address version of this variable is unused, we can
1844 substitute it for anything else with the same label.
1845 Otherwise, we know the pointers are equivalent, but not the
1848 if (graph
->label
[FIRST_ADDR_NODE
+ node
] == 0)
1850 gcc_assert (label
< graph
->size
);
1852 if (graph
->eq_rep
[label
] != -1)
1854 /* Unify the two variables since we know they are equivalent. */
1855 if (unite (graph
->eq_rep
[label
], node
))
1856 unify_nodes (graph
, graph
->eq_rep
[label
], node
, false);
1857 return graph
->eq_rep
[label
];
1861 graph
->eq_rep
[label
] = node
;
1867 /* Move complex constraints to the appropriate nodes, and collapse
1868 variables we've discovered are equivalent during variable
1869 substitution. SI is the SCC_INFO that is the result of
1870 perform_variable_substitution. */
1873 move_complex_constraints (constraint_graph_t graph
,
1874 struct scc_info
*si
)
1880 for (j
= 0; j
< graph
->size
; j
++)
1881 gcc_assert (find (j
) == j
);
1883 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1885 struct constraint_expr lhs
= c
->lhs
;
1886 struct constraint_expr rhs
= c
->rhs
;
1887 unsigned int lhsvar
= find (get_varinfo_fc (lhs
.var
)->id
);
1888 unsigned int rhsvar
= find (get_varinfo_fc (rhs
.var
)->id
);
1889 unsigned int lhsnode
, rhsnode
;
1890 unsigned int lhslabel
, rhslabel
;
1892 lhsnode
= si
->node_mapping
[lhsvar
];
1893 rhsnode
= si
->node_mapping
[rhsvar
];
1894 lhslabel
= graph
->label
[lhsnode
];
1895 rhslabel
= graph
->label
[rhsnode
];
1897 /* See if it is really a non-pointer variable, and if so, ignore
1901 if (!TEST_BIT (graph
->direct_nodes
, lhsnode
))
1902 lhslabel
= graph
->label
[lhsnode
] = equivalence_class
++;
1905 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1908 fprintf (dump_file
, "%s is a non-pointer variable,"
1909 "ignoring constraint:",
1910 get_varinfo (lhs
.var
)->name
);
1911 dump_constraint (dump_file
, c
);
1913 VEC_replace (constraint_t
, constraints
, i
, NULL
);
1920 if (!TEST_BIT (graph
->direct_nodes
, rhsnode
))
1921 rhslabel
= graph
->label
[rhsnode
] = equivalence_class
++;
1924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1927 fprintf (dump_file
, "%s is a non-pointer variable,"
1928 "ignoring constraint:",
1929 get_varinfo (rhs
.var
)->name
);
1930 dump_constraint (dump_file
, c
);
1932 VEC_replace (constraint_t
, constraints
, i
, NULL
);
1937 lhsvar
= find_equivalent_node (graph
, lhsvar
, lhslabel
);
1938 rhsvar
= find_equivalent_node (graph
, rhsvar
, rhslabel
);
1939 c
->lhs
.var
= lhsvar
;
1940 c
->rhs
.var
= rhsvar
;
1942 if (lhs
.type
== DEREF
)
1944 if (rhs
.type
== ADDRESSOF
|| rhsvar
> anything_id
)
1945 insert_into_complex (graph
, lhsvar
, c
);
1947 else if (rhs
.type
== DEREF
)
1949 if (!(get_varinfo (lhsvar
)->is_special_var
))
1950 insert_into_complex (graph
, rhsvar
, c
);
1952 else if (rhs
.type
!= ADDRESSOF
&& lhsvar
> anything_id
1953 && (lhs
.offset
!= 0 || rhs
.offset
!= 0))
1955 insert_into_complex (graph
, rhsvar
, c
);
1961 /* Eliminate indirect cycles involving NODE. Return true if NODE was
1962 part of an SCC, false otherwise. */
1965 eliminate_indirect_cycles (unsigned int node
)
1967 if (graph
->indirect_cycles
[node
] != -1
1968 && !bitmap_empty_p (get_varinfo (node
)->solution
))
1971 VEC(unsigned,heap
) *queue
= NULL
;
1973 unsigned int to
= find (graph
->indirect_cycles
[node
]);
1976 /* We can't touch the solution set and call unify_nodes
1977 at the same time, because unify_nodes is going to do
1978 bitmap unions into it. */
1980 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node
)->solution
, 0, i
, bi
)
1982 if (find (i
) == i
&& i
!= to
)
1985 VEC_safe_push (unsigned, heap
, queue
, i
);
1990 VEC_iterate (unsigned, queue
, queuepos
, i
);
1993 unify_nodes (graph
, to
, i
, true);
1995 VEC_free (unsigned, heap
, queue
);
2001 /* Solve the constraint graph GRAPH using our worklist solver.
2002 This is based on the PW* family of solvers from the "Efficient Field
2003 Sensitive Pointer Analysis for C" paper.
2004 It works by iterating over all the graph nodes, processing the complex
2005 constraints and propagating the copy constraints, until everything stops
2006 changed. This corresponds to steps 6-8 in the solving list given above. */
2009 solve_graph (constraint_graph_t graph
)
2011 unsigned int size
= VEC_length (varinfo_t
, varmap
);
2016 changed
= sbitmap_alloc (size
);
2017 sbitmap_zero (changed
);
2019 /* Mark all initial non-collapsed nodes as changed. */
2020 for (i
= 0; i
< size
; i
++)
2022 varinfo_t ivi
= get_varinfo (i
);
2023 if (find (i
) == i
&& !bitmap_empty_p (ivi
->solution
)
2024 && ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
2025 || VEC_length (constraint_t
, graph
->complex[i
]) > 0))
2027 SET_BIT (changed
, i
);
2032 /* Allocate a bitmap to be used to store the changed bits. */
2033 pts
= BITMAP_ALLOC (&pta_obstack
);
2035 while (changed_count
> 0)
2038 struct topo_info
*ti
= init_topo_info ();
2041 bitmap_obstack_initialize (&iteration_obstack
);
2043 compute_topo_order (graph
, ti
);
2045 while (VEC_length (unsigned, ti
->topo_order
) != 0)
2048 i
= VEC_pop (unsigned, ti
->topo_order
);
2050 /* If this variable is not a representative, skip it. */
2054 /* In certain indirect cycle cases, we may merge this
2055 variable to another. */
2056 if (eliminate_indirect_cycles (i
) && find(i
) != i
)
2059 /* If the node has changed, we need to process the
2060 complex constraints and outgoing edges again. */
2061 if (TEST_BIT (changed
, i
))
2066 VEC(constraint_t
,heap
) *complex = graph
->complex[i
];
2067 bool solution_empty
;
2068 RESET_BIT (changed
, i
);
2071 /* Compute the changed set of solution bits. */
2072 bitmap_and_compl (pts
, get_varinfo (i
)->solution
,
2073 get_varinfo (i
)->oldsolution
);
2075 if (bitmap_empty_p (pts
))
2078 bitmap_ior_into (get_varinfo (i
)->oldsolution
, pts
);
2080 solution
= get_varinfo (i
)->solution
;
2081 solution_empty
= bitmap_empty_p (solution
);
2083 /* Process the complex constraints */
2084 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
2086 /* The only complex constraint that can change our
2087 solution to non-empty, given an empty solution,
2088 is a constraint where the lhs side is receiving
2089 some set from elsewhere. */
2090 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2091 do_complex_constraint (graph
, c
, pts
);
2094 solution_empty
= bitmap_empty_p (solution
);
2096 if (!solution_empty
)
2100 /* Propagate solution to all successors. */
2101 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
2107 unsigned int to
= find (j
);
2108 tmp
= get_varinfo (to
)->solution
;
2111 /* Don't try to propagate to ourselves. */
2115 flag
= set_union_with_increment (tmp
, pts
, 0);
2119 get_varinfo (to
)->solution
= tmp
;
2120 if (!TEST_BIT (changed
, to
))
2122 SET_BIT (changed
, to
);
2130 free_topo_info (ti
);
2131 bitmap_obstack_release (&iteration_obstack
);
2135 sbitmap_free (changed
);
2136 bitmap_obstack_release (&oldpta_obstack
);
2139 /* Map from trees to variable infos. */
2140 static htab_t vi_for_tree
;
2142 typedef struct tree_vi
2148 /* Hash a tree id structure. */
2151 tree_vi_hash (const void *p
)
2153 const tree_vi_t ta
= (tree_vi_t
) p
;
2154 return htab_hash_pointer (ta
->t
);
2157 /* Return true if the tree in P1 and the tree in P2 are the same. */
2160 tree_vi_eq (const void *p1
, const void *p2
)
2162 const tree_vi_t ta1
= (tree_vi_t
) p1
;
2163 const tree_vi_t ta2
= (tree_vi_t
) p2
;
2164 return ta1
->t
== ta2
->t
;
2167 /* Insert ID as the variable id for tree T in the hashtable. */
2170 insert_vi_for_tree (tree t
, varinfo_t vi
)
2173 struct tree_vi finder
;
2177 slot
= htab_find_slot (vi_for_tree
, &finder
, INSERT
);
2178 gcc_assert (*slot
== NULL
);
2179 new_pair
= XNEW (struct tree_vi
);
2182 *slot
= (void *)new_pair
;
2185 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2186 exist in the hash table, return false, otherwise, return true and
2187 set *VI to the varinfo we found. */
2190 lookup_vi_for_tree (tree t
, varinfo_t
*vi
)
2193 struct tree_vi finder
;
2196 pair
= htab_find (vi_for_tree
, &finder
);
2203 /* Return a printable name for DECL */
2206 alias_get_name (tree decl
)
2208 const char *res
= get_name (decl
);
2210 int num_printed
= 0;
2219 if (TREE_CODE (decl
) == SSA_NAME
)
2221 num_printed
= asprintf (&temp
, "%s_%u",
2222 alias_get_name (SSA_NAME_VAR (decl
)),
2223 SSA_NAME_VERSION (decl
));
2225 else if (DECL_P (decl
))
2227 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2229 if (num_printed
> 0)
2231 res
= ggc_strdup (temp
);
2237 /* Find the variable id for tree T in the hashtable.
2238 If T doesn't exist in the hash table, create an entry for it. */
2241 get_vi_for_tree (tree t
)
2244 struct tree_vi finder
;
2247 pair
= htab_find (vi_for_tree
, &finder
);
2249 return get_varinfo (create_variable_info_for (t
, alias_get_name (t
)));
2254 /* Get a constraint expression from an SSA_VAR_P node. */
2256 static struct constraint_expr
2257 get_constraint_exp_from_ssa_var (tree t
)
2259 struct constraint_expr cexpr
;
2261 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
2263 /* For parameters, get at the points-to set for the actual parm
2265 if (TREE_CODE (t
) == SSA_NAME
2266 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2267 && SSA_NAME_IS_DEFAULT_DEF (t
))
2268 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
2270 cexpr
.type
= SCALAR
;
2272 cexpr
.var
= get_vi_for_tree (t
)->id
;
2273 /* If we determine the result is "anything", and we know this is readonly,
2274 say it points to readonly memory instead. */
2275 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
2277 cexpr
.type
= ADDRESSOF
;
2278 cexpr
.var
= readonly_id
;
2285 /* Process a completed constraint T, and add it to the constraint
2289 process_constraint (constraint_t t
)
2291 struct constraint_expr rhs
= t
->rhs
;
2292 struct constraint_expr lhs
= t
->lhs
;
2294 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
2295 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
2297 if (lhs
.type
== DEREF
)
2298 get_varinfo (lhs
.var
)->directly_dereferenced
= true;
2299 if (rhs
.type
== DEREF
)
2300 get_varinfo (rhs
.var
)->directly_dereferenced
= true;
2302 if (!use_field_sensitive
)
2308 /* ANYTHING == ANYTHING is pointless. */
2309 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
2312 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2313 else if (lhs
.var
== anything_id
&& lhs
.type
== ADDRESSOF
)
2318 process_constraint (t
);
2320 /* This can happen in our IR with things like n->a = *p */
2321 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
2323 /* Split into tmp = *rhs, *lhs = tmp */
2324 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
2325 tree pointertype
= TREE_TYPE (rhsdecl
);
2326 tree pointedtotype
= TREE_TYPE (pointertype
);
2327 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
2328 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2330 /* If this is an aggregate of known size, we should have passed
2331 this off to do_structure_copy, and it should have broken it
2333 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
2334 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
2336 process_constraint (new_constraint (tmplhs
, rhs
));
2337 process_constraint (new_constraint (lhs
, tmplhs
));
2341 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
2342 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2346 /* Return true if T is a variable of a type that could contain
2350 could_have_pointers (tree t
)
2352 tree type
= TREE_TYPE (t
);
2354 if (POINTER_TYPE_P (type
) || AGGREGATE_TYPE_P (type
)
2355 || TREE_CODE (type
) == COMPLEX_TYPE
)
2360 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2363 static unsigned HOST_WIDE_INT
2364 bitpos_of_field (const tree fdecl
)
2367 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
2368 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
2371 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
2372 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
2376 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2377 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2380 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
2381 const unsigned HOST_WIDE_INT fieldsize
,
2382 const unsigned HOST_WIDE_INT accesspos
,
2383 const unsigned HOST_WIDE_INT accesssize
)
2385 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
2387 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
2389 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
2395 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2398 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
)
2401 HOST_WIDE_INT bitsize
= -1;
2402 HOST_WIDE_INT bitmaxsize
= -1;
2403 HOST_WIDE_INT bitpos
;
2405 struct constraint_expr
*result
;
2406 unsigned int beforelength
= VEC_length (ce_s
, *results
);
2408 /* Some people like to do cute things like take the address of
2411 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
2412 forzero
= TREE_OPERAND (forzero
, 0);
2414 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
2416 struct constraint_expr temp
;
2419 temp
.var
= integer_id
;
2421 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2425 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
2427 /* String constants are readonly, so there is nothing to really do
2429 if (TREE_CODE (t
) == STRING_CST
)
2432 get_constraint_for (t
, results
);
2433 result
= VEC_last (ce_s
, *results
);
2434 result
->offset
= bitpos
;
2436 gcc_assert (beforelength
+ 1 == VEC_length (ce_s
, *results
));
2438 /* This can also happen due to weird offsetof type macros. */
2439 if (TREE_CODE (t
) != ADDR_EXPR
&& result
->type
== ADDRESSOF
)
2440 result
->type
= SCALAR
;
2442 if (result
->type
== SCALAR
)
2444 /* In languages like C, you can access one past the end of an
2445 array. You aren't allowed to dereference it, so we can
2446 ignore this constraint. When we handle pointer subtraction,
2447 we may have to do something cute here. */
2449 if (result
->offset
< get_varinfo (result
->var
)->fullsize
2452 /* It's also not true that the constraint will actually start at the
2453 right offset, it may start in some padding. We only care about
2454 setting the constraint to the first actual field it touches, so
2457 for (curr
= get_varinfo (result
->var
); curr
; curr
= curr
->next
)
2459 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2460 result
->offset
, bitmaxsize
))
2462 result
->var
= curr
->id
;
2466 /* assert that we found *some* field there. The user couldn't be
2467 accessing *only* padding. */
2468 /* Still the user could access one past the end of an array
2469 embedded in a struct resulting in accessing *only* padding. */
2470 gcc_assert (curr
|| ref_contains_array_ref (orig_t
));
2472 else if (bitmaxsize
== 0)
2474 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2475 fprintf (dump_file
, "Access to zero-sized part of variable,"
2479 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2480 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2487 /* Dereference the constraint expression CONS, and return the result.
2488 DEREF (ADDRESSOF) = SCALAR
2489 DEREF (SCALAR) = DEREF
2490 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2491 This is needed so that we can handle dereferencing DEREF constraints. */
2494 do_deref (VEC (ce_s
, heap
) **constraints
)
2496 struct constraint_expr
*c
;
2499 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
2501 if (c
->type
== SCALAR
)
2503 else if (c
->type
== ADDRESSOF
)
2505 else if (c
->type
== DEREF
)
2507 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "dereftmp");
2508 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2509 process_constraint (new_constraint (tmplhs
, *c
));
2510 c
->var
= tmplhs
.var
;
2517 /* Given a tree T, return the constraint expression for it. */
2520 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
2522 struct constraint_expr temp
;
2524 /* x = integer is all glommed to a single variable, which doesn't
2525 point to anything by itself. That is, of course, unless it is an
2526 integer constant being treated as a pointer, in which case, we
2527 will return that this is really the addressof anything. This
2528 happens below, since it will fall into the default case. The only
2529 case we know something about an integer treated like a pointer is
2530 when it is the NULL pointer, and then we just say it points to
2532 if (TREE_CODE (t
) == INTEGER_CST
2533 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2535 temp
.var
= integer_id
;
2538 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2541 else if (TREE_CODE (t
) == INTEGER_CST
2542 && integer_zerop (t
))
2544 temp
.var
= nothing_id
;
2545 temp
.type
= ADDRESSOF
;
2547 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2551 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2553 case tcc_expression
:
2555 switch (TREE_CODE (t
))
2559 struct constraint_expr
*c
;
2561 tree exp
= TREE_OPERAND (t
, 0);
2562 tree pttype
= TREE_TYPE (TREE_TYPE (t
));
2564 get_constraint_for (exp
, results
);
2565 /* Make sure we capture constraints to all elements
2567 if ((handled_component_p (exp
)
2568 && ref_contains_array_ref (exp
))
2569 || TREE_CODE (TREE_TYPE (exp
)) == ARRAY_TYPE
)
2571 struct constraint_expr
*origrhs
;
2573 struct constraint_expr tmp
;
2575 if (VEC_length (ce_s
, *results
) == 0)
2578 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2579 origrhs
= VEC_last (ce_s
, *results
);
2581 VEC_pop (ce_s
, *results
);
2582 origvar
= get_varinfo (origrhs
->var
);
2583 for (; origvar
; origvar
= origvar
->next
)
2585 tmp
.var
= origvar
->id
;
2586 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2589 else if (VEC_length (ce_s
, *results
) == 1
2590 && (AGGREGATE_TYPE_P (pttype
)
2591 || TREE_CODE (pttype
) == COMPLEX_TYPE
))
2593 struct constraint_expr
*origrhs
;
2595 struct constraint_expr tmp
;
2597 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2598 origrhs
= VEC_last (ce_s
, *results
);
2600 VEC_pop (ce_s
, *results
);
2601 origvar
= get_varinfo (origrhs
->var
);
2602 for (; origvar
; origvar
= origvar
->next
)
2604 tmp
.var
= origvar
->id
;
2605 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2609 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
2611 if (c
->type
== DEREF
)
2614 c
->type
= ADDRESSOF
;
2620 /* XXX: In interprocedural mode, if we didn't have the
2621 body, we would need to do *each pointer argument =
2623 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2626 tree heapvar
= heapvar_lookup (t
);
2628 if (heapvar
== NULL
)
2630 heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2631 DECL_EXTERNAL (heapvar
) = 1;
2632 get_var_ann (heapvar
)->is_heapvar
= 1;
2633 if (gimple_referenced_vars (cfun
))
2634 add_referenced_var (heapvar
);
2635 heapvar_insert (t
, heapvar
);
2638 temp
.var
= create_variable_info_for (heapvar
,
2639 alias_get_name (heapvar
));
2641 vi
= get_varinfo (temp
.var
);
2642 vi
->is_artificial_var
= 1;
2643 vi
->is_heap_var
= 1;
2644 temp
.type
= ADDRESSOF
;
2646 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2651 temp
.var
= anything_id
;
2654 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2660 temp
.type
= ADDRESSOF
;
2661 temp
.var
= anything_id
;
2663 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2670 switch (TREE_CODE (t
))
2674 get_constraint_for (TREE_OPERAND (t
, 0), results
);
2679 case ARRAY_RANGE_REF
:
2681 get_constraint_for_component_ref (t
, results
);
2685 temp
.type
= ADDRESSOF
;
2686 temp
.var
= anything_id
;
2688 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2695 switch (TREE_CODE (t
))
2699 case NON_LVALUE_EXPR
:
2701 tree op
= TREE_OPERAND (t
, 0);
2703 /* Cast from non-pointer to pointers are bad news for us.
2704 Anything else, we see through */
2705 if (!(POINTER_TYPE_P (TREE_TYPE (t
))
2706 && ! POINTER_TYPE_P (TREE_TYPE (op
))))
2708 get_constraint_for (op
, results
);
2716 temp
.type
= ADDRESSOF
;
2717 temp
.var
= anything_id
;
2719 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2724 case tcc_exceptional
:
2726 switch (TREE_CODE (t
))
2730 get_constraint_for (PHI_RESULT (t
), results
);
2736 struct constraint_expr temp
;
2737 temp
= get_constraint_exp_from_ssa_var (t
);
2738 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2744 temp
.type
= ADDRESSOF
;
2745 temp
.var
= anything_id
;
2747 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2752 case tcc_declaration
:
2754 struct constraint_expr temp
;
2755 temp
= get_constraint_exp_from_ssa_var (t
);
2756 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2761 temp
.type
= ADDRESSOF
;
2762 temp
.var
= anything_id
;
2764 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2771 /* Handle the structure copy case where we have a simple structure copy
2772 between LHS and RHS that is of SIZE (in bits)
2774 For each field of the lhs variable (lhsfield)
2775 For each field of the rhs variable at lhsfield.offset (rhsfield)
2776 add the constraint lhsfield = rhsfield
2778 If we fail due to some kind of type unsafety or other thing we
2779 can't handle, return false. We expect the caller to collapse the
2780 variable in that case. */
2783 do_simple_structure_copy (const struct constraint_expr lhs
,
2784 const struct constraint_expr rhs
,
2785 const unsigned HOST_WIDE_INT size
)
2787 varinfo_t p
= get_varinfo (lhs
.var
);
2788 unsigned HOST_WIDE_INT pstart
, last
;
2790 last
= p
->offset
+ size
;
2791 for (; p
&& p
->offset
< last
; p
= p
->next
)
2794 struct constraint_expr templhs
= lhs
;
2795 struct constraint_expr temprhs
= rhs
;
2796 unsigned HOST_WIDE_INT fieldoffset
;
2798 templhs
.var
= p
->id
;
2799 q
= get_varinfo (temprhs
.var
);
2800 fieldoffset
= p
->offset
- pstart
;
2801 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2804 temprhs
.var
= q
->id
;
2805 process_constraint (new_constraint (templhs
, temprhs
));
2811 /* Handle the structure copy case where we have a structure copy between a
2812 aggregate on the LHS and a dereference of a pointer on the RHS
2813 that is of SIZE (in bits)
2815 For each field of the lhs variable (lhsfield)
2816 rhs.offset = lhsfield->offset
2817 add the constraint lhsfield = rhs
2821 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2822 const struct constraint_expr rhs
,
2823 const unsigned HOST_WIDE_INT size
)
2825 varinfo_t p
= get_varinfo (lhs
.var
);
2826 unsigned HOST_WIDE_INT pstart
,last
;
2828 last
= p
->offset
+ size
;
2830 for (; p
&& p
->offset
< last
; p
= p
->next
)
2833 struct constraint_expr templhs
= lhs
;
2834 struct constraint_expr temprhs
= rhs
;
2835 unsigned HOST_WIDE_INT fieldoffset
;
2838 if (templhs
.type
== SCALAR
)
2839 templhs
.var
= p
->id
;
2841 templhs
.offset
= p
->offset
;
2843 q
= get_varinfo (temprhs
.var
);
2844 fieldoffset
= p
->offset
- pstart
;
2845 temprhs
.offset
+= fieldoffset
;
2846 process_constraint (new_constraint (templhs
, temprhs
));
2850 /* Handle the structure copy case where we have a structure copy
2851 between a aggregate on the RHS and a dereference of a pointer on
2852 the LHS that is of SIZE (in bits)
2854 For each field of the rhs variable (rhsfield)
2855 lhs.offset = rhsfield->offset
2856 add the constraint lhs = rhsfield
2860 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2861 const struct constraint_expr rhs
,
2862 const unsigned HOST_WIDE_INT size
)
2864 varinfo_t p
= get_varinfo (rhs
.var
);
2865 unsigned HOST_WIDE_INT pstart
,last
;
2867 last
= p
->offset
+ size
;
2869 for (; p
&& p
->offset
< last
; p
= p
->next
)
2872 struct constraint_expr templhs
= lhs
;
2873 struct constraint_expr temprhs
= rhs
;
2874 unsigned HOST_WIDE_INT fieldoffset
;
2877 if (temprhs
.type
== SCALAR
)
2878 temprhs
.var
= p
->id
;
2880 temprhs
.offset
= p
->offset
;
2882 q
= get_varinfo (templhs
.var
);
2883 fieldoffset
= p
->offset
- pstart
;
2884 templhs
.offset
+= fieldoffset
;
2885 process_constraint (new_constraint (templhs
, temprhs
));
2889 /* Sometimes, frontends like to give us bad type information. This
2890 function will collapse all the fields from VAR to the end of VAR,
2891 into VAR, so that we treat those fields as a single variable.
2892 We return the variable they were collapsed into. */
2895 collapse_rest_of_var (unsigned int var
)
2897 varinfo_t currvar
= get_varinfo (var
);
2900 for (field
= currvar
->next
; field
; field
= field
->next
)
2903 fprintf (dump_file
, "Type safety: Collapsing var %s into %s\n",
2904 field
->name
, currvar
->name
);
2906 gcc_assert (!field
->collapsed_to
);
2907 field
->collapsed_to
= currvar
;
2910 currvar
->next
= NULL
;
2911 currvar
->size
= currvar
->fullsize
- currvar
->offset
;
2916 /* Handle aggregate copies by expanding into copies of the respective
2917 fields of the structures. */
2920 do_structure_copy (tree lhsop
, tree rhsop
)
2922 struct constraint_expr lhs
, rhs
, tmp
;
2923 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
2925 unsigned HOST_WIDE_INT lhssize
;
2926 unsigned HOST_WIDE_INT rhssize
;
2928 get_constraint_for (lhsop
, &lhsc
);
2929 get_constraint_for (rhsop
, &rhsc
);
2930 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
2931 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
2932 lhs
= *(VEC_last (ce_s
, lhsc
));
2933 rhs
= *(VEC_last (ce_s
, rhsc
));
2935 VEC_free (ce_s
, heap
, lhsc
);
2936 VEC_free (ce_s
, heap
, rhsc
);
2938 /* If we have special var = x, swap it around. */
2939 if (lhs
.var
<= integer_id
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2946 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2947 possible it's something we could handle. However, most cases falling
2948 into this are dealing with transparent unions, which are slightly
2950 if (rhs
.type
== ADDRESSOF
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2952 rhs
.type
= ADDRESSOF
;
2953 rhs
.var
= anything_id
;
2956 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2957 that special var. */
2958 if (rhs
.var
<= integer_id
)
2960 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2962 struct constraint_expr templhs
= lhs
;
2963 struct constraint_expr temprhs
= rhs
;
2965 if (templhs
.type
== SCALAR
)
2966 templhs
.var
= p
->id
;
2968 templhs
.offset
+= p
->offset
;
2969 process_constraint (new_constraint (templhs
, temprhs
));
2974 tree rhstype
= TREE_TYPE (rhsop
);
2975 tree lhstype
= TREE_TYPE (lhsop
);
2979 lhstypesize
= DECL_P (lhsop
) ? DECL_SIZE (lhsop
) : TYPE_SIZE (lhstype
);
2980 rhstypesize
= DECL_P (rhsop
) ? DECL_SIZE (rhsop
) : TYPE_SIZE (rhstype
);
2982 /* If we have a variably sized types on the rhs or lhs, and a deref
2983 constraint, add the constraint, lhsconstraint = &ANYTHING.
2984 This is conservatively correct because either the lhs is an unknown
2985 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2986 constraint, and every variable it can point to must be unknown sized
2987 anyway, so we don't need to worry about fields at all. */
2988 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
2989 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
2991 rhs
.var
= anything_id
;
2992 rhs
.type
= ADDRESSOF
;
2994 process_constraint (new_constraint (lhs
, rhs
));
2998 /* The size only really matters insofar as we don't set more or less of
2999 the variable. If we hit an unknown size var, the size should be the
3000 whole darn thing. */
3001 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
3004 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
3006 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
3009 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
3012 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
3014 if (!do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
)))
3016 lhs
.var
= collapse_rest_of_var (lhs
.var
);
3017 rhs
.var
= collapse_rest_of_var (rhs
.var
);
3022 process_constraint (new_constraint (lhs
, rhs
));
3025 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
3026 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
3027 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
3028 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
3031 tree pointedtotype
= lhstype
;
3034 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
3035 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
3036 do_structure_copy (tmpvar
, rhsop
);
3037 do_structure_copy (lhsop
, tmpvar
);
3042 /* Update related alias information kept in AI. This is used when
3043 building name tags, alias sets and deciding grouping heuristics.
3044 STMT is the statement to process. This function also updates
3045 ADDRESSABLE_VARS. */
3048 update_alias_info (tree stmt
, struct alias_info
*ai
)
3051 use_operand_p use_p
;
3053 enum escape_type stmt_escape_type
= is_escape_site (stmt
);
3055 if (stmt_escape_type
== ESCAPE_TO_CALL
3056 || stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
3058 ai
->num_calls_found
++;
3059 if (stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
3060 ai
->num_pure_const_calls_found
++;
3063 /* Mark all the variables whose address are taken by the statement. */
3064 addr_taken
= addresses_taken (stmt
);
3067 bitmap_ior_into (gimple_addressable_vars (cfun
), addr_taken
);
3069 /* If STMT is an escape point, all the addresses taken by it are
3071 if (stmt_escape_type
!= NO_ESCAPE
)
3076 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
3078 tree rvar
= referenced_var (i
);
3079 if (!unmodifiable_var_p (rvar
))
3080 mark_call_clobbered (rvar
, stmt_escape_type
);
3085 /* Process each operand use. If an operand may be aliased, keep
3086 track of how many times it's being used. For pointers, determine
3087 whether they are dereferenced by the statement, or whether their
3088 value escapes, etc. */
3089 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
3093 struct ptr_info_def
*pi
;
3094 bool is_store
, is_potential_deref
;
3095 unsigned num_uses
, num_derefs
;
3097 op
= USE_FROM_PTR (use_p
);
3099 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3100 to the set of addressable variables. */
3101 if (TREE_CODE (op
) == ADDR_EXPR
)
3103 bitmap addressable_vars
= gimple_addressable_vars (cfun
);
3105 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
);
3106 gcc_assert (addressable_vars
);
3108 /* PHI nodes don't have annotations for pinning the set
3109 of addresses taken, so we collect them here.
3111 FIXME, should we allow PHI nodes to have annotations
3112 so that they can be treated like regular statements?
3113 Currently, they are treated as second-class
3115 add_to_addressable_set (TREE_OPERAND (op
, 0),
3120 /* Ignore constants. */
3121 if (TREE_CODE (op
) != SSA_NAME
)
3124 var
= SSA_NAME_VAR (op
);
3125 v_ann
= var_ann (var
);
3127 /* The base variable of an SSA name must be a GIMPLE register, and thus
3128 it cannot be aliased. */
3129 gcc_assert (!may_be_aliased (var
));
3131 /* We are only interested in pointers. */
3132 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
3135 pi
= get_ptr_info (op
);
3137 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3138 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
)))
3140 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
));
3141 VEC_safe_push (tree
, heap
, ai
->processed_ptrs
, op
);
3144 /* If STMT is a PHI node, then it will not have pointer
3145 dereferences and it will not be an escape point. */
3146 if (TREE_CODE (stmt
) == PHI_NODE
)
3149 /* Determine whether OP is a dereferenced pointer, and if STMT
3150 is an escape point, whether OP escapes. */
3151 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
3153 /* Handle a corner case involving address expressions of the
3154 form '&PTR->FLD'. The problem with these expressions is that
3155 they do not represent a dereference of PTR. However, if some
3156 other transformation propagates them into an INDIRECT_REF
3157 expression, we end up with '*(&PTR->FLD)' which is folded
3160 So, if the original code had no other dereferences of PTR,
3161 the aliaser will not create memory tags for it, and when
3162 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3163 memory operations will receive no VDEF/VUSE operands.
3165 One solution would be to have count_uses_and_derefs consider
3166 &PTR->FLD a dereference of PTR. But that is wrong, since it
3167 is not really a dereference but an offset calculation.
3169 What we do here is to recognize these special ADDR_EXPR
3170 nodes. Since these expressions are never GIMPLE values (they
3171 are not GIMPLE invariants), they can only appear on the RHS
3172 of an assignment and their base address is always an
3173 INDIRECT_REF expression. */
3174 is_potential_deref
= false;
3175 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3176 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == ADDR_EXPR
3177 && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt
, 1)))
3179 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3180 this represents a potential dereference of PTR. */
3181 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3182 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
3183 if (TREE_CODE (base
) == INDIRECT_REF
3184 && TREE_OPERAND (base
, 0) == op
)
3185 is_potential_deref
= true;
3188 if (num_derefs
> 0 || is_potential_deref
)
3190 /* Mark OP as dereferenced. In a subsequent pass,
3191 dereferenced pointers that point to a set of
3192 variables will be assigned a name tag to alias
3193 all the variables OP points to. */
3194 pi
->is_dereferenced
= 1;
3196 /* If this is a store operation, mark OP as being
3197 dereferenced to store, otherwise mark it as being
3198 dereferenced to load. */
3200 pointer_set_insert (ai
->dereferenced_ptrs_store
, var
);
3202 pointer_set_insert (ai
->dereferenced_ptrs_load
, var
);
3205 if (stmt_escape_type
!= NO_ESCAPE
&& num_derefs
< num_uses
)
3207 /* If STMT is an escape point and STMT contains at
3208 least one direct use of OP, then the value of OP
3209 escapes and so the pointed-to variables need to
3210 be marked call-clobbered. */
3211 pi
->value_escapes_p
= 1;
3212 pi
->escape_mask
|= stmt_escape_type
;
3214 /* If the statement makes a function call, assume
3215 that pointer OP will be dereferenced in a store
3216 operation inside the called function. */
3217 if (get_call_expr_in (stmt
)
3218 || stmt_escape_type
== ESCAPE_STORED_IN_GLOBAL
)
3220 pointer_set_insert (ai
->dereferenced_ptrs_store
, var
);
3221 pi
->is_dereferenced
= 1;
3226 if (TREE_CODE (stmt
) == PHI_NODE
)
3229 /* Mark stored variables in STMT as being written to and update the
3230 reference counter for potentially aliased symbols in STMT. */
3231 if (stmt_references_memory_p (stmt
) && STORED_SYMS (stmt
))
3235 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt
), 0, i
, bi
)
3236 pointer_set_insert (ai
->written_vars
, referenced_var (i
));
3241 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3242 Expressions of the type PTR + CST can be handled in two ways:
3244 1- If the constraint for PTR is ADDRESSOF for a non-structure
3245 variable, then we can use it directly because adding or
3246 subtracting a constant may not alter the original ADDRESSOF
3247 constraint (i.e., pointer arithmetic may not legally go outside
3248 an object's boundaries).
3250 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3251 then if CST is a compile-time constant that can be used as an
3252 offset, we can determine which sub-variable will be pointed-to
3255 Return true if the expression is handled. For any other kind of
3256 expression, return false so that each operand can be added as a
3257 separate constraint by the caller. */
3260 handle_ptr_arith (VEC (ce_s
, heap
) *lhsc
, tree expr
)
3263 struct constraint_expr
*c
, *c2
;
3266 VEC (ce_s
, heap
) *temp
= NULL
;
3267 unsigned int rhsoffset
= 0;
3269 if (TREE_CODE (expr
) != PLUS_EXPR
3270 && TREE_CODE (expr
) != MINUS_EXPR
)
3273 op0
= TREE_OPERAND (expr
, 0);
3274 op1
= TREE_OPERAND (expr
, 1);
3276 get_constraint_for (op0
, &temp
);
3277 if (POINTER_TYPE_P (TREE_TYPE (op0
))
3278 && TREE_CODE (op1
) == INTEGER_CST
3279 && TREE_CODE (expr
) == PLUS_EXPR
)
3281 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
3287 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
3288 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
3290 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
3292 varinfo_t temp
= get_varinfo (c2
->var
);
3294 /* An access one after the end of an array is valid,
3295 so simply punt on accesses we cannot resolve. */
3296 temp
= first_vi_for_offset (temp
, rhsoffset
);
3303 c2
->offset
= rhsoffset
;
3304 process_constraint (new_constraint (*c
, *c2
));
3307 VEC_free (ce_s
, heap
, temp
);
3313 /* Walk statement T setting up aliasing constraints according to the
3314 references found in T. This function is the main part of the
3315 constraint builder. AI points to auxiliary alias information used
3316 when building alias sets and computing alias grouping heuristics. */
3319 find_func_aliases (tree origt
)
3322 VEC(ce_s
, heap
) *lhsc
= NULL
;
3323 VEC(ce_s
, heap
) *rhsc
= NULL
;
3324 struct constraint_expr
*c
;
3326 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
3327 t
= TREE_OPERAND (t
, 0);
3329 /* Now build constraints expressions. */
3330 if (TREE_CODE (t
) == PHI_NODE
)
3332 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))));
3334 /* Only care about pointers and structures containing
3336 if (could_have_pointers (PHI_RESULT (t
)))
3341 /* For a phi node, assign all the arguments to
3343 get_constraint_for (PHI_RESULT (t
), &lhsc
);
3344 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
3347 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
3349 STRIP_NOPS (strippedrhs
);
3350 rhstype
= TREE_TYPE (strippedrhs
);
3351 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
3353 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3355 struct constraint_expr
*c2
;
3356 while (VEC_length (ce_s
, rhsc
) > 0)
3358 c2
= VEC_last (ce_s
, rhsc
);
3359 process_constraint (new_constraint (*c
, *c2
));
3360 VEC_pop (ce_s
, rhsc
);
3366 /* In IPA mode, we need to generate constraints to pass call
3367 arguments through their calls. There are two case, either a
3368 modify_expr when we are returning a value, or just a plain
3369 call_expr when we are not. */
3370 else if (in_ipa_mode
3371 && ((TREE_CODE (t
) == GIMPLE_MODIFY_STMT
3372 && TREE_CODE (GIMPLE_STMT_OPERAND (t
, 1)) == CALL_EXPR
3373 && !(call_expr_flags (GIMPLE_STMT_OPERAND (t
, 1))
3374 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
3375 || (TREE_CODE (t
) == CALL_EXPR
3376 && !(call_expr_flags (t
)
3377 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
3385 if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
3387 lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
3388 rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
3395 decl
= get_callee_fndecl (rhsop
);
3397 /* If we can directly resolve the function being called, do so.
3398 Otherwise, it must be some sort of indirect expression that
3399 we should still be able to handle. */
3402 fi
= get_vi_for_tree (decl
);
3406 decl
= TREE_OPERAND (rhsop
, 0);
3407 fi
= get_vi_for_tree (decl
);
3410 /* Assign all the passed arguments to the appropriate incoming
3411 parameters of the function. */
3412 arglist
= TREE_OPERAND (rhsop
, 1);
3414 for (;arglist
; arglist
= TREE_CHAIN (arglist
))
3416 tree arg
= TREE_VALUE (arglist
);
3417 struct constraint_expr lhs
;
3418 struct constraint_expr
*rhsp
;
3420 get_constraint_for (arg
, &rhsc
);
3421 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3430 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3433 while (VEC_length (ce_s
, rhsc
) != 0)
3435 rhsp
= VEC_last (ce_s
, rhsc
);
3436 process_constraint (new_constraint (lhs
, *rhsp
));
3437 VEC_pop (ce_s
, rhsc
);
3441 /* If we are returning a value, assign it to the result. */
3444 struct constraint_expr rhs
;
3445 struct constraint_expr
*lhsp
;
3448 get_constraint_for (lhsop
, &lhsc
);
3449 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3458 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3461 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3462 process_constraint (new_constraint (*lhsp
, rhs
));
3465 /* Otherwise, just a regular assignment statement. */
3466 else if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
3468 tree lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
3469 tree rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
3472 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3473 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
)
3474 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop
))
3475 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
))
3477 do_structure_copy (lhsop
, rhsop
);
3481 /* Only care about operations with pointers, structures
3482 containing pointers, dereferences, and call expressions. */
3483 if (could_have_pointers (lhsop
)
3484 || TREE_CODE (rhsop
) == CALL_EXPR
)
3486 get_constraint_for (lhsop
, &lhsc
);
3487 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3489 /* RHS that consist of unary operations,
3490 exceptional types, or bare decls/constants, get
3491 handled directly by get_constraint_for. */
3493 case tcc_declaration
:
3495 case tcc_exceptional
:
3496 case tcc_expression
:
3501 get_constraint_for (rhsop
, &rhsc
);
3502 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3504 struct constraint_expr
*c2
;
3507 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3508 process_constraint (new_constraint (*c
, *c2
));
3516 /* For pointer arithmetic of the form
3517 PTR + CST, we can simply use PTR's
3518 constraint because pointer arithmetic is
3519 not allowed to go out of bounds. */
3520 if (handle_ptr_arith (lhsc
, rhsop
))
3525 /* Otherwise, walk each operand. Notice that we
3526 can't use the operand interface because we need
3527 to process expressions other than simple operands
3528 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3530 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
3532 tree op
= TREE_OPERAND (rhsop
, i
);
3535 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3536 get_constraint_for (op
, &rhsc
);
3537 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3539 struct constraint_expr
*c2
;
3540 while (VEC_length (ce_s
, rhsc
) > 0)
3542 c2
= VEC_last (ce_s
, rhsc
);
3543 process_constraint (new_constraint (*c
, *c2
));
3544 VEC_pop (ce_s
, rhsc
);
3553 /* After promoting variables and computing aliasing we will
3554 need to re-scan most statements. FIXME: Try to minimize the
3555 number of statements re-scanned. It's not really necessary to
3556 re-scan *all* statements. */
3557 mark_stmt_modified (origt
);
3558 VEC_free (ce_s
, heap
, rhsc
);
3559 VEC_free (ce_s
, heap
, lhsc
);
3563 /* Find the first varinfo in the same variable as START that overlaps with
3565 Effectively, walk the chain of fields for the variable START to find the
3566 first field that overlaps with OFFSET.
3567 Return NULL if we can't find one. */
3570 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3572 varinfo_t curr
= start
;
3575 /* We may not find a variable in the field list with the actual
3576 offset when when we have glommed a structure to a variable.
3577 In that case, however, offset should still be within the size
3579 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3587 /* Insert the varinfo FIELD into the field list for BASE, at the front
3591 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3593 varinfo_t prev
= base
;
3594 varinfo_t curr
= base
->next
;
3600 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3604 insert_into_field_list_sorted (varinfo_t base
, varinfo_t field
)
3606 varinfo_t prev
= base
;
3607 varinfo_t curr
= base
->next
;
3618 if (field
->offset
<= curr
->offset
)
3623 field
->next
= prev
->next
;
3628 /* qsort comparison function for two fieldoff's PA and PB */
3631 fieldoff_compare (const void *pa
, const void *pb
)
3633 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3634 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3635 HOST_WIDE_INT foasize
, fobsize
;
3637 if (foa
->offset
!= fob
->offset
)
3638 return foa
->offset
- fob
->offset
;
3640 foasize
= TREE_INT_CST_LOW (foa
->size
);
3641 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3642 return foasize
- fobsize
;
3645 /* Sort a fieldstack according to the field offset and sizes. */
3647 sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3649 qsort (VEC_address (fieldoff_s
, fieldstack
),
3650 VEC_length (fieldoff_s
, fieldstack
),
3651 sizeof (fieldoff_s
),
3655 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3656 of TYPE onto fieldstack, recording their offsets along the way.
3657 OFFSET is used to keep track of the offset in this entire structure, rather
3658 than just the immediately containing structure. Returns the number
3660 HAS_UNION is set to true if we find a union type as a field of
3664 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3665 HOST_WIDE_INT offset
, bool *has_union
)
3670 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3672 fieldoff_s
*real_part
, *img_part
;
3673 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3674 real_part
->type
= TREE_TYPE (type
);
3675 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3676 real_part
->offset
= offset
;
3677 real_part
->decl
= NULL_TREE
;
3679 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3680 img_part
->type
= TREE_TYPE (type
);
3681 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3682 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3683 img_part
->decl
= NULL_TREE
;
3688 if (TREE_CODE (type
) == ARRAY_TYPE
)
3690 tree sz
= TYPE_SIZE (type
);
3691 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3696 || ! host_integerp (sz
, 1)
3697 || TREE_INT_CST_LOW (sz
) == 0
3699 || ! host_integerp (elsz
, 1)
3700 || TREE_INT_CST_LOW (elsz
) == 0)
3703 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3704 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3707 for (i
= 0; i
< nr
; ++i
)
3713 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3714 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3717 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3719 else if (!(pushed
= push_fields_onto_fieldstack
3720 (TREE_TYPE (type
), fieldstack
,
3721 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
)))
3722 /* Empty structures may have actual size, like in C++. So
3723 see if we didn't push any subfields and the size is
3724 nonzero, push the field onto the stack */
3731 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3732 pair
->type
= TREE_TYPE (type
);
3734 pair
->decl
= NULL_TREE
;
3735 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3745 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3746 if (TREE_CODE (field
) == FIELD_DECL
)
3752 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3753 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3756 if (!var_can_have_subvars (field
))
3758 else if (!(pushed
= push_fields_onto_fieldstack
3759 (TREE_TYPE (field
), fieldstack
,
3760 offset
+ bitpos_of_field (field
), has_union
))
3761 && DECL_SIZE (field
)
3762 && !integer_zerop (DECL_SIZE (field
)))
3763 /* Empty structures may have actual size, like in C++. So
3764 see if we didn't push any subfields and the size is
3765 nonzero, push the field onto the stack */
3772 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3773 pair
->type
= TREE_TYPE (field
);
3774 pair
->size
= DECL_SIZE (field
);
3776 pair
->offset
= offset
+ bitpos_of_field (field
);
3786 /* Create a constraint from ANYTHING variable to VI. */
3788 make_constraint_from_anything (varinfo_t vi
)
3790 struct constraint_expr lhs
, rhs
;
3796 rhs
.var
= anything_id
;
3798 rhs
.type
= ADDRESSOF
;
3799 process_constraint (new_constraint (lhs
, rhs
));
3802 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3803 if it is a varargs function. */
3806 count_num_arguments (tree decl
, bool *is_varargs
)
3811 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3815 if (TREE_VALUE (t
) == void_type_node
)
3825 /* Creation function node for DECL, using NAME, and return the index
3826 of the variable we've created for the function. */
3829 create_function_info_for (tree decl
, const char *name
)
3831 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3835 bool is_varargs
= false;
3837 /* Create the variable info. */
3839 vi
= new_var_info (decl
, index
, name
);
3844 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3845 insert_vi_for_tree (vi
->decl
, vi
);
3846 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3850 /* If it's varargs, we don't know how many arguments it has, so we
3857 vi
->is_unknown_size_var
= true;
3862 arg
= DECL_ARGUMENTS (decl
);
3864 /* Set up variables for each argument. */
3865 for (i
= 1; i
< vi
->fullsize
; i
++)
3868 const char *newname
;
3870 unsigned int newindex
;
3871 tree argdecl
= decl
;
3876 newindex
= VEC_length (varinfo_t
, varmap
);
3877 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3878 newname
= ggc_strdup (tempname
);
3881 argvi
= new_var_info (argdecl
, newindex
, newname
);
3882 argvi
->decl
= argdecl
;
3883 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3886 argvi
->fullsize
= vi
->fullsize
;
3887 argvi
->has_union
= false;
3888 insert_into_field_list_sorted (vi
, argvi
);
3889 stats
.total_vars
++;
3892 insert_vi_for_tree (arg
, argvi
);
3893 arg
= TREE_CHAIN (arg
);
3897 /* Create a variable for the return var. */
3898 if (DECL_RESULT (decl
) != NULL
3899 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3902 const char *newname
;
3904 unsigned int newindex
;
3905 tree resultdecl
= decl
;
3909 if (DECL_RESULT (decl
))
3910 resultdecl
= DECL_RESULT (decl
);
3912 newindex
= VEC_length (varinfo_t
, varmap
);
3913 asprintf (&tempname
, "%s.result", name
);
3914 newname
= ggc_strdup (tempname
);
3917 resultvi
= new_var_info (resultdecl
, newindex
, newname
);
3918 resultvi
->decl
= resultdecl
;
3919 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3920 resultvi
->offset
= i
;
3922 resultvi
->fullsize
= vi
->fullsize
;
3923 resultvi
->has_union
= false;
3924 insert_into_field_list_sorted (vi
, resultvi
);
3925 stats
.total_vars
++;
3926 if (DECL_RESULT (decl
))
3927 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
3933 /* Return true if FIELDSTACK contains fields that overlap.
3934 FIELDSTACK is assumed to be sorted by offset. */
3937 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3939 fieldoff_s
*fo
= NULL
;
3941 HOST_WIDE_INT lastoffset
= -1;
3943 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3945 if (fo
->offset
== lastoffset
)
3947 lastoffset
= fo
->offset
;
3952 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3953 This will also create any varinfo structures necessary for fields
3957 create_variable_info_for (tree decl
, const char *name
)
3959 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3961 tree
decltype = TREE_TYPE (decl
);
3962 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
3963 bool notokay
= false;
3965 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
3966 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
3968 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
3969 return create_function_info_for (decl
, name
);
3971 hasunion
= TREE_CODE (decltype) == UNION_TYPE
3972 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
3973 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
3975 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
3978 VEC_free (fieldoff_s
, heap
, fieldstack
);
3984 /* If the variable doesn't have subvars, we may end up needing to
3985 sort the field list and create fake variables for all the
3987 vi
= new_var_info (decl
, index
, name
);
3990 vi
->has_union
= hasunion
;
3992 || TREE_CODE (declsize
) != INTEGER_CST
3993 || TREE_CODE (decltype) == UNION_TYPE
3994 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
3996 vi
->is_unknown_size_var
= true;
4002 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
4003 vi
->size
= vi
->fullsize
;
4006 insert_vi_for_tree (vi
->decl
, vi
);
4007 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
4008 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
4009 make_constraint_from_anything (vi
);
4012 if (use_field_sensitive
4014 && !vi
->is_unknown_size_var
4015 && var_can_have_subvars (decl
)
4016 && VEC_length (fieldoff_s
, fieldstack
) <= MAX_FIELDS_FOR_FIELD_SENSITIVE
)
4018 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
4019 fieldoff_s
*fo
= NULL
;
4022 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
4025 || TREE_CODE (fo
->size
) != INTEGER_CST
4033 /* We can't sort them if we have a field with a variable sized type,
4034 which will make notokay = true. In that case, we are going to return
4035 without creating varinfos for the fields anyway, so sorting them is a
4039 sort_fieldstack (fieldstack
);
4040 /* Due to some C++ FE issues, like PR 22488, we might end up
4041 what appear to be overlapping fields even though they,
4042 in reality, do not overlap. Until the C++ FE is fixed,
4043 we will simply disable field-sensitivity for these cases. */
4044 notokay
= check_for_overlaps (fieldstack
);
4048 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
4049 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
4051 if (fo
== NULL
|| notokay
)
4053 vi
->is_unknown_size_var
= 1;
4056 VEC_free (fieldoff_s
, heap
, fieldstack
);
4060 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
4061 vi
->offset
= fo
->offset
;
4062 for (i
= VEC_length (fieldoff_s
, fieldstack
) - 1;
4063 i
>= 1 && VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
4067 const char *newname
= "NULL";
4070 newindex
= VEC_length (varinfo_t
, varmap
);
4074 asprintf (&tempname
, "%s.%s",
4075 vi
->name
, alias_get_name (fo
->decl
));
4077 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
,
4078 vi
->name
, fo
->offset
);
4079 newname
= ggc_strdup (tempname
);
4082 newvi
= new_var_info (decl
, newindex
, newname
);
4083 newvi
->offset
= fo
->offset
;
4084 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
4085 newvi
->fullsize
= vi
->fullsize
;
4086 insert_into_field_list (vi
, newvi
);
4087 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
4088 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
4089 make_constraint_from_anything (newvi
);
4093 VEC_free (fieldoff_s
, heap
, fieldstack
);
4098 /* Print out the points-to solution for VAR to FILE. */
4101 dump_solution_for_var (FILE *file
, unsigned int var
)
4103 varinfo_t vi
= get_varinfo (var
);
4107 if (find (var
) != var
)
4109 varinfo_t vipt
= get_varinfo (find (var
));
4110 fprintf (file
, "%s = same as %s\n", vi
->name
, vipt
->name
);
4114 fprintf (file
, "%s = { ", vi
->name
);
4115 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4117 fprintf (file
, "%s ", get_varinfo (i
)->name
);
4119 fprintf (file
, "}\n");
4123 /* Print the points-to solution for VAR to stdout. */
4126 debug_solution_for_var (unsigned int var
)
4128 dump_solution_for_var (stdout
, var
);
4131 /* Create varinfo structures for all of the variables in the
4132 function for intraprocedural mode. */
4135 intra_create_variable_infos (void)
4138 struct constraint_expr lhs
, rhs
;
4140 /* For each incoming pointer argument arg, ARG = ANYTHING or a
4141 dummy variable if flag_argument_noalias > 2. */
4142 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
4146 if (!could_have_pointers (t
))
4149 /* With flag_argument_noalias greater than two means that the incoming
4150 argument cannot alias anything except for itself so create a HEAP
4152 if (POINTER_TYPE_P (TREE_TYPE (t
))
4153 && flag_argument_noalias
> 2)
4156 tree heapvar
= heapvar_lookup (t
);
4160 lhs
.var
= get_vi_for_tree (t
)->id
;
4162 if (heapvar
== NULL_TREE
)
4164 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)),
4166 get_var_ann (heapvar
)->is_heapvar
= 1;
4167 DECL_EXTERNAL (heapvar
) = 1;
4168 if (gimple_referenced_vars (cfun
))
4169 add_referenced_var (heapvar
);
4170 heapvar_insert (t
, heapvar
);
4172 vi
= get_vi_for_tree (heapvar
);
4173 vi
->is_artificial_var
= 1;
4174 vi
->is_heap_var
= 1;
4176 rhs
.type
= ADDRESSOF
;
4178 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4180 struct constraint_expr temp
= lhs
;
4182 process_constraint (new_constraint (temp
, rhs
));
4187 varinfo_t arg_vi
= get_vi_for_tree (t
);
4189 for (p
= arg_vi
; p
; p
= p
->next
)
4190 make_constraint_from_anything (p
);
4195 /* Set bits in INTO corresponding to the variable uids in solution set
4196 FROM, which came from variable PTR.
4197 For variables that are actually dereferenced, we also use type
4198 based alias analysis to prune the points-to sets. */
4201 set_uids_in_ptset (tree ptr
, bitmap into
, bitmap from
)
4206 HOST_WIDE_INT ptr_alias_set
= get_alias_set (TREE_TYPE (ptr
));
4208 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
4210 varinfo_t vi
= get_varinfo (i
);
4211 unsigned HOST_WIDE_INT var_alias_set
;
4213 /* The only artificial variables that are allowed in a may-alias
4214 set are heap variables. */
4215 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
4218 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
4220 /* Variables containing unions may need to be converted to
4221 their SFT's, because SFT's can have unions and we cannot. */
4222 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
4223 bitmap_set_bit (into
, DECL_UID (sv
->var
));
4225 else if (TREE_CODE (vi
->decl
) == VAR_DECL
4226 || TREE_CODE (vi
->decl
) == PARM_DECL
)
4228 if (var_can_have_subvars (vi
->decl
)
4229 && get_subvars_for_var (vi
->decl
))
4231 /* If VI->DECL is an aggregate for which we created
4232 SFTs, add the SFT corresponding to VI->OFFSET. */
4233 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
4236 var_alias_set
= get_alias_set (sft
);
4237 if (!vi
->directly_dereferenced
4238 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
4239 bitmap_set_bit (into
, DECL_UID (sft
));
4244 /* Otherwise, just add VI->DECL to the alias set.
4245 Don't type prune artificial vars. */
4246 if (vi
->is_artificial_var
)
4247 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4250 var_alias_set
= get_alias_set (vi
->decl
);
4251 if (!vi
->directly_dereferenced
4252 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
4253 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4261 static bool have_alias_info
= false;
4263 /* The list of SMT's that are in use by our pointer variables. This
4264 is the set of SMT's for all pointers that can point to anything. */
4265 static bitmap used_smts
;
4267 /* Due to the ordering of points-to set calculation and SMT
4268 calculation being a bit co-dependent, we can't just calculate SMT
4269 used info whenever we want, we have to calculate it around the time
4270 that find_what_p_points_to is called. */
4272 /* Mark which SMT's are in use by points-to anything variables. */
4275 set_used_smts (void)
4279 used_smts
= BITMAP_ALLOC (&pta_obstack
);
4281 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, vi
); i
++)
4283 tree var
= vi
->decl
;
4286 struct ptr_info_def
*pi
= NULL
;
4288 /* For parm decls, the pointer info may be under the default
4290 if (TREE_CODE (vi
->decl
) == PARM_DECL
4291 && gimple_default_def (cfun
, var
))
4292 pi
= SSA_NAME_PTR_INFO (gimple_default_def (cfun
, var
));
4293 else if (TREE_CODE (var
) == SSA_NAME
)
4294 pi
= SSA_NAME_PTR_INFO (var
);
4296 /* Skip the special variables and those without their own
4298 if (vi
->is_special_var
|| find (vi
->id
) != vi
->id
4300 || (pi
&& !pi
->is_dereferenced
)
4301 || (TREE_CODE (var
) == VAR_DECL
&& !may_be_aliased (var
))
4302 || !POINTER_TYPE_P (TREE_TYPE (var
)))
4305 if (TREE_CODE (var
) == SSA_NAME
)
4306 var
= SSA_NAME_VAR (var
);
4312 smt
= va
->symbol_mem_tag
;
4313 if (smt
&& bitmap_bit_p (vi
->solution
, anything_id
))
4314 bitmap_set_bit (used_smts
, DECL_UID (smt
));
4318 /* Merge the necessary SMT's into the solution set for VI, which is
4319 P's varinfo. This involves merging all SMT's that are a subset of
4320 the SMT necessary for P. */
4323 merge_smts_into (tree p
, varinfo_t vi
)
4328 VEC(tree
, gc
) *aliases
;
4331 if (TREE_CODE (p
) == SSA_NAME
)
4332 var
= SSA_NAME_VAR (p
);
4334 smt
= var_ann (var
)->symbol_mem_tag
;
4337 HOST_WIDE_INT smtset
= get_alias_set (TREE_TYPE (smt
));
4339 /* Need to set the SMT subsets first before this
4340 will work properly. */
4341 bitmap_set_bit (vi
->finished_solution
, DECL_UID (smt
));
4342 EXECUTE_IF_SET_IN_BITMAP (used_smts
, 0, i
, bi
)
4344 tree newsmt
= referenced_var (i
);
4345 tree newsmttype
= TREE_TYPE (newsmt
);
4347 if (alias_set_subset_of (get_alias_set (newsmttype
),
4349 bitmap_set_bit (vi
->finished_solution
, i
);
4352 aliases
= var_ann (smt
)->may_aliases
;
4357 for (k
= 0; VEC_iterate (tree
, aliases
, k
, al
); k
++)
4358 bitmap_set_bit (vi
->finished_solution
,
4364 /* Given a pointer variable P, fill in its points-to set, or return
4366 Rather than return false for variables that point-to anything, we
4367 instead find the corresponding SMT, and merge in it's aliases. In
4368 addition to these aliases, we also set the bits for the SMT's
4369 themselves and their subsets, as SMT's are still in use by
4370 non-SSA_NAME's, and pruning may eliminate every one of their
4371 aliases. In such a case, if we did not include the right set of
4372 SMT's in the points-to set of the variable, we'd end up with
4373 statements that do not conflict but should. */
4376 find_what_p_points_to (tree p
)
4381 if (!have_alias_info
)
4384 /* For parameters, get at the points-to set for the actual parm
4386 if (TREE_CODE (p
) == SSA_NAME
4387 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
4388 && SSA_NAME_IS_DEFAULT_DEF (p
))
4389 lookup_p
= SSA_NAME_VAR (p
);
4391 if (lookup_vi_for_tree (lookup_p
, &vi
))
4394 if (vi
->is_artificial_var
)
4397 /* See if this is a field or a structure. */
4398 if (vi
->size
!= vi
->fullsize
)
4400 /* Nothing currently asks about structure fields directly,
4401 but when they do, we need code here to hand back the
4403 if (!var_can_have_subvars (vi
->decl
)
4404 || get_subvars_for_var (vi
->decl
) == NULL
)
4409 struct ptr_info_def
*pi
= get_ptr_info (p
);
4412 bool was_pt_anything
= false;
4414 if (!pi
->is_dereferenced
)
4417 /* This variable may have been collapsed, let's get the real
4419 vi
= get_varinfo (find (vi
->id
));
4421 /* Translate artificial variables into SSA_NAME_PTR_INFO
4423 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4425 varinfo_t vi
= get_varinfo (i
);
4427 if (vi
->is_artificial_var
)
4429 /* FIXME. READONLY should be handled better so that
4430 flow insensitive aliasing can disregard writable
4432 if (vi
->id
== nothing_id
)
4434 else if (vi
->id
== anything_id
)
4435 was_pt_anything
= 1;
4436 else if (vi
->id
== readonly_id
)
4437 was_pt_anything
= 1;
4438 else if (vi
->id
== integer_id
)
4439 was_pt_anything
= 1;
4440 else if (vi
->is_heap_var
)
4441 pi
->pt_global_mem
= 1;
4445 /* Share the final set of variables between the SSA_NAME
4446 pointer infos for collapsed nodes that are collapsed to
4447 non-special variables. This is because special vars have
4448 no real types associated with them, so while we know the
4449 pointers are equivalent to them, we need to generate the
4450 solution separately since it will include SMT's from the
4451 original non-collapsed variable. */
4452 if (!vi
->is_special_var
&& vi
->finished_solution
)
4454 pi
->pt_vars
= vi
->finished_solution
;
4458 vi
->finished_solution
= BITMAP_GGC_ALLOC ();
4459 stats
.points_to_sets_created
++;
4461 /* Instead of using pt_anything, we instead merge in the SMT
4462 aliases for the underlying SMT. */
4463 if (was_pt_anything
)
4465 merge_smts_into (p
, vi
);
4466 pi
->pt_global_mem
= 1;
4469 set_uids_in_ptset (vi
->decl
, vi
->finished_solution
, vi
->solution
);
4470 pi
->pt_vars
= vi
->finished_solution
;
4473 if (bitmap_empty_p (pi
->pt_vars
))
4485 /* Dump points-to information to OUTFILE. */
4488 dump_sa_points_to_info (FILE *outfile
)
4492 fprintf (outfile
, "\nPoints-to sets\n\n");
4494 if (dump_flags
& TDF_STATS
)
4496 fprintf (outfile
, "Stats:\n");
4497 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4498 fprintf (outfile
, "Non-pointer vars: %d\n",
4499 stats
.nonpointer_vars
);
4500 fprintf (outfile
, "Statically unified vars: %d\n",
4501 stats
.unified_vars_static
);
4502 fprintf (outfile
, "Dynamically unified vars: %d\n",
4503 stats
.unified_vars_dynamic
);
4504 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4505 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4506 fprintf (outfile
, "Number of implicit edges: %d\n",
4507 stats
.num_implicit_edges
);
4510 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4511 dump_solution_for_var (outfile
, i
);
4515 /* Debug points-to information to stderr. */
4518 debug_sa_points_to_info (void)
4520 dump_sa_points_to_info (stderr
);
4524 /* Initialize the always-existing constraint variables for NULL
4525 ANYTHING, READONLY, and INTEGER */
4528 init_base_vars (void)
4530 struct constraint_expr lhs
, rhs
;
4532 /* Create the NULL variable, used to represent that a variable points
4534 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4535 var_nothing
= new_var_info (nothing_tree
, 0, "NULL");
4536 insert_vi_for_tree (nothing_tree
, var_nothing
);
4537 var_nothing
->is_artificial_var
= 1;
4538 var_nothing
->offset
= 0;
4539 var_nothing
->size
= ~0;
4540 var_nothing
->fullsize
= ~0;
4541 var_nothing
->is_special_var
= 1;
4543 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4545 /* Create the ANYTHING variable, used to represent that a variable
4546 points to some unknown piece of memory. */
4547 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4548 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING");
4549 insert_vi_for_tree (anything_tree
, var_anything
);
4550 var_anything
->is_artificial_var
= 1;
4551 var_anything
->size
= ~0;
4552 var_anything
->offset
= 0;
4553 var_anything
->next
= NULL
;
4554 var_anything
->fullsize
= ~0;
4555 var_anything
->is_special_var
= 1;
4558 /* Anything points to anything. This makes deref constraints just
4559 work in the presence of linked list and other p = *p type loops,
4560 by saying that *ANYTHING = ANYTHING. */
4561 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4563 lhs
.var
= anything_id
;
4565 rhs
.type
= ADDRESSOF
;
4566 rhs
.var
= anything_id
;
4569 /* This specifically does not use process_constraint because
4570 process_constraint ignores all anything = anything constraints, since all
4571 but this one are redundant. */
4572 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4574 /* Create the READONLY variable, used to represent that a variable
4575 points to readonly memory. */
4576 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4577 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY");
4578 var_readonly
->is_artificial_var
= 1;
4579 var_readonly
->offset
= 0;
4580 var_readonly
->size
= ~0;
4581 var_readonly
->fullsize
= ~0;
4582 var_readonly
->next
= NULL
;
4583 var_readonly
->is_special_var
= 1;
4584 insert_vi_for_tree (readonly_tree
, var_readonly
);
4586 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4588 /* readonly memory points to anything, in order to make deref
4589 easier. In reality, it points to anything the particular
4590 readonly variable can point to, but we don't track this
4593 lhs
.var
= readonly_id
;
4595 rhs
.type
= ADDRESSOF
;
4596 rhs
.var
= anything_id
;
4599 process_constraint (new_constraint (lhs
, rhs
));
4601 /* Create the INTEGER variable, used to represent that a variable points
4603 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4604 var_integer
= new_var_info (integer_tree
, 3, "INTEGER");
4605 insert_vi_for_tree (integer_tree
, var_integer
);
4606 var_integer
->is_artificial_var
= 1;
4607 var_integer
->size
= ~0;
4608 var_integer
->fullsize
= ~0;
4609 var_integer
->offset
= 0;
4610 var_integer
->next
= NULL
;
4611 var_integer
->is_special_var
= 1;
4613 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4615 /* INTEGER = ANYTHING, because we don't know where a dereference of
4616 a random integer will point to. */
4618 lhs
.var
= integer_id
;
4620 rhs
.type
= ADDRESSOF
;
4621 rhs
.var
= anything_id
;
4623 process_constraint (new_constraint (lhs
, rhs
));
4626 /* Initialize things necessary to perform PTA */
4629 init_alias_vars (void)
4631 bitmap_obstack_initialize (&pta_obstack
);
4632 bitmap_obstack_initialize (&oldpta_obstack
);
4633 bitmap_obstack_initialize (&predbitmap_obstack
);
4635 constraint_pool
= create_alloc_pool ("Constraint pool",
4636 sizeof (struct constraint
), 30);
4637 variable_info_pool
= create_alloc_pool ("Variable info pool",
4638 sizeof (struct variable_info
), 30);
4639 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4640 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4641 vi_for_tree
= htab_create (10, tree_vi_hash
, tree_vi_eq
, free
);
4643 memset (&stats
, 0, sizeof (stats
));
4648 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
4649 predecessor edges. */
4652 remove_preds_and_fake_succs (constraint_graph_t graph
)
4656 /* Clear the implicit ref and address nodes from the successor
4658 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
4660 if (graph
->succs
[i
])
4661 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
4662 FIRST_REF_NODE
* 2);
4665 /* Free the successor list for the non-ref nodes. */
4666 for (i
= FIRST_REF_NODE
; i
< graph
->size
; i
++)
4668 if (graph
->succs
[i
])
4669 BITMAP_FREE (graph
->succs
[i
]);
4672 /* Now reallocate the size of the successor list as, and blow away
4673 the predecessor bitmaps. */
4674 graph
->size
= VEC_length (varinfo_t
, varmap
);
4675 graph
->succs
= xrealloc (graph
->succs
, graph
->size
* sizeof (bitmap
));
4677 free (graph
->implicit_preds
);
4678 graph
->implicit_preds
= NULL
;
4679 free (graph
->preds
);
4680 graph
->preds
= NULL
;
4681 bitmap_obstack_release (&predbitmap_obstack
);
4684 /* Create points-to sets for the current function. See the comments
4685 at the start of the file for an algorithmic overview. */
4688 compute_points_to_sets (struct alias_info
*ai
)
4690 struct scc_info
*si
;
4693 timevar_push (TV_TREE_PTA
);
4696 init_alias_heapvars ();
4698 intra_create_variable_infos ();
4700 /* Now walk all statements and derive aliases. */
4703 block_stmt_iterator bsi
;
4706 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4708 if (is_gimple_reg (PHI_RESULT (phi
)))
4710 find_func_aliases (phi
);
4711 /* Update various related attributes like escaped
4712 addresses, pointer dereferences for loads and stores.
4713 This is used when creating name tags and alias
4715 update_alias_info (phi
, ai
);
4719 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4721 tree stmt
= bsi_stmt (bsi
);
4723 find_func_aliases (stmt
);
4725 /* Update various related attributes like escaped
4726 addresses, pointer dereferences for loads and stores.
4727 This is used when creating name tags and alias
4729 update_alias_info (stmt
, ai
);
4736 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4737 dump_constraints (dump_file
);
4742 "\nCollapsing static cycles and doing variable "
4744 build_pred_graph ();
4745 si
= perform_var_substitution (graph
);
4746 move_complex_constraints (graph
, si
);
4747 free_var_substitution_info (si
);
4749 build_succ_graph ();
4750 find_indirect_cycles (graph
);
4752 /* Implicit nodes and predecessors are no longer necessary at this
4754 remove_preds_and_fake_succs (graph
);
4757 fprintf (dump_file
, "\nSolving graph:\n");
4759 solve_graph (graph
);
4762 dump_sa_points_to_info (dump_file
);
4764 have_alias_info
= true;
4766 timevar_pop (TV_TREE_PTA
);
4770 /* Delete created points-to sets. */
4773 delete_points_to_sets (void)
4778 if (dump_file
&& (dump_flags
& TDF_STATS
))
4779 fprintf (dump_file
, "Points to sets created:%d\n",
4780 stats
.points_to_sets_created
);
4782 htab_delete (vi_for_tree
);
4783 bitmap_obstack_release (&pta_obstack
);
4784 VEC_free (constraint_t
, heap
, constraints
);
4786 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4787 VEC_free (constraint_t
, heap
, graph
->complex[i
]);
4790 free (graph
->succs
);
4791 free (graph
->indirect_cycles
);
4794 VEC_free (varinfo_t
, heap
, varmap
);
4795 free_alloc_pool (variable_info_pool
);
4796 free_alloc_pool (constraint_pool
);
4797 have_alias_info
= false;
4800 /* Return true if we should execute IPA PTA. */
4804 return (flag_unit_at_a_time
!= 0
4806 /* Don't bother doing anything if the program has errors. */
4807 && !(errorcount
|| sorrycount
));
4810 /* Execute the driver for IPA PTA. */
4812 ipa_pta_execute (void)
4814 struct cgraph_node
*node
;
4815 struct scc_info
*si
;
4818 init_alias_heapvars ();
4821 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4823 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
4827 varid
= create_function_info_for (node
->decl
,
4828 cgraph_node_name (node
));
4829 if (node
->local
.externally_visible
)
4831 varinfo_t fi
= get_varinfo (varid
);
4832 for (; fi
; fi
= fi
->next
)
4833 make_constraint_from_anything (fi
);
4837 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4839 if (node
->analyzed
&& cgraph_is_master_clone (node
))
4841 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
4843 tree old_func_decl
= current_function_decl
;
4846 "Generating constraints for %s\n",
4847 cgraph_node_name (node
));
4849 current_function_decl
= node
->decl
;
4851 FOR_EACH_BB_FN (bb
, cfun
)
4853 block_stmt_iterator bsi
;
4856 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4858 if (is_gimple_reg (PHI_RESULT (phi
)))
4860 find_func_aliases (phi
);
4864 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4866 tree stmt
= bsi_stmt (bsi
);
4867 find_func_aliases (stmt
);
4870 current_function_decl
= old_func_decl
;
4875 /* Make point to anything. */
4883 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4884 dump_constraints (dump_file
);
4889 "\nCollapsing static cycles and doing variable "
4892 build_pred_graph ();
4893 si
= perform_var_substitution (graph
);
4894 move_complex_constraints (graph
, si
);
4895 free_var_substitution_info (si
);
4897 build_succ_graph ();
4898 find_indirect_cycles (graph
);
4900 /* Implicit nodes and predecessors are no longer necessary at this
4902 remove_preds_and_fake_succs (graph
);
4905 fprintf (dump_file
, "\nSolving graph:\n");
4907 solve_graph (graph
);
4910 dump_sa_points_to_info (dump_file
);
4913 delete_alias_heapvars ();
4914 delete_points_to_sets ();
4918 struct tree_opt_pass pass_ipa_pta
=
4921 gate_ipa_pta
, /* gate */
4922 ipa_pta_execute
, /* execute */
4925 0, /* static_pass_number */
4926 TV_IPA_PTA
, /* tv_id */
4927 0, /* properties_required */
4928 0, /* properties_provided */
4929 0, /* properties_destroyed */
4930 0, /* todo_flags_start */
4931 0, /* todo_flags_finish */
4935 /* Initialize the heapvar for statement mapping. */
4937 init_alias_heapvars (void)
4939 if (!heapvar_for_stmt
)
4940 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
,
4945 delete_alias_heapvars (void)
4947 htab_delete (heapvar_for_stmt
);
4948 heapvar_for_stmt
= NULL
;
4952 #include "gt-tree-ssa-structalias.h"