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"
56 /* The idea behind this analyzer is to generate set constraints from the
57 program, then solve the resulting constraints in order to generate the
60 Set constraints are a way of modeling program analysis problems that
61 involve sets. They consist of an inclusion constraint language,
62 describing the variables (each variable is a set) and operations that
63 are involved on the variables, and a set of rules that derive facts
64 from these operations. To solve a system of set constraints, you derive
65 all possible facts under the rules, which gives you the correct sets
68 See "Efficient Field-sensitive pointer analysis for C" by "David
69 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
70 http://citeseer.ist.psu.edu/pearce04efficient.html
72 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
73 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
74 http://citeseer.ist.psu.edu/heintze01ultrafast.html
76 There are three types of real constraint expressions, DEREF,
77 ADDRESSOF, and SCALAR. There is one type of fake constraint
78 expression, called INCLUDES. 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.
87 INCLUDES is a constraint expression type used to represent just a
88 setting of a bit in the points-to set without having the address
89 taken. It exists mainly for abstraction sake, and is used for
90 initializing fake variables like the ESCAPED_VARS set.
92 Each pointer variable in the program is assigned an integer id, and
93 each field of a structure variable is assigned an integer id as well.
95 Structure variables are linked to their list of fields through a "next
96 field" in each variable that points to the next field in offset
98 Each variable for a structure field has
100 1. "size", that tells the size in bits of that field.
101 2. "fullsize, that tells the size in bits of the entire structure.
102 3. "offset", that tells the offset in bits from the beginning of the
103 structure to this field.
115 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
116 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
117 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
120 In order to solve the system of set constraints, the following is
123 1. Each constraint variable x has a solution set associated with it,
126 2. Constraints are separated into direct, copy, and complex.
127 Direct constraints are ADDRESSOF constraints that require no extra
128 processing, such as P = &Q
129 Copy constraints are those of the form P = Q.
130 Complex constraints are all the constraints involving dereferences
131 and offsets (including offsetted copies).
133 3. All direct constraints of the form P = &Q are processed, such
134 that Q is added to Sol(P)
136 4. All complex constraints for a given constraint variable are stored in a
137 linked list attached to that variable's node.
139 5. A directed graph is built out of the copy constraints. Each
140 constraint variable is a node in the graph, and an edge from
141 Q to P is added for each copy constraint of the form P = Q
143 6. The graph is then walked, and solution sets are
144 propagated along the copy edges, such that an edge from Q to P
145 causes Sol(P) <- Sol(P) union Sol(Q).
147 7. As we visit each node, all complex constraints associated with
148 that node are processed by adding appropriate copy edges to the graph, or the
149 appropriate variables to the solution set.
151 8. The process of walking the graph is iterated until no solution
154 Prior to walking the graph in steps 6 and 7, We perform static
155 cycle elimination on the constraint graph, as well
156 as off-line variable substitution.
158 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
159 on and turned into anything), but isn't. You can just see what offset
160 inside the pointed-to struct it's going to access.
162 TODO: Constant bounded arrays can be handled as if they were structs of the
163 same number of elements.
165 TODO: Modeling heap and incoming pointers becomes much better if we
166 add fields to them as we discover them, which we could do.
168 TODO: We could handle unions, but to be honest, it's probably not
169 worth the pain or slowdown. */
171 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map
)))
172 htab_t heapvar_for_stmt
;
174 static bool use_field_sensitive
= true;
175 static int in_ipa_mode
= 0;
176 static bitmap_obstack predbitmap_obstack
;
177 static bitmap_obstack ptabitmap_obstack
;
178 static bitmap_obstack iteration_obstack
;
180 static unsigned int create_variable_info_for (tree
, const char *);
181 static void build_constraint_graph (void);
183 DEF_VEC_P(constraint_t
);
184 DEF_VEC_ALLOC_P(constraint_t
,heap
);
186 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
188 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
190 static struct constraint_stats
192 unsigned int total_vars
;
193 unsigned int collapsed_vars
;
194 unsigned int unified_vars_static
;
195 unsigned int unified_vars_dynamic
;
196 unsigned int iterations
;
197 unsigned int num_edges
;
202 /* ID of this variable */
205 /* Name of this variable */
208 /* Tree that this variable is associated with. */
211 /* Offset of this variable, in bits, from the base variable */
212 unsigned HOST_WIDE_INT offset
;
214 /* Size of the variable, in bits. */
215 unsigned HOST_WIDE_INT size
;
217 /* Full size of the base variable, in bits. */
218 unsigned HOST_WIDE_INT fullsize
;
220 /* A link to the variable for the next field in this structure. */
221 struct variable_info
*next
;
223 /* Node in the graph that represents the constraints and points-to
224 solution for the variable. */
227 /* True if the address of this variable is taken. Needed for
228 variable substitution. */
229 unsigned int address_taken
:1;
231 /* True if this variable is the target of a dereference. Needed for
232 variable substitution. */
233 unsigned int indirect_target
:1;
235 /* True if the variable is directly the target of a dereference.
236 This is used to track which variables are *actually* dereferenced
237 so we can prune their points to listed. This is equivalent to the
238 indirect_target flag when no merging of variables happens. */
239 unsigned int directly_dereferenced
:1;
241 /* True if this is a variable created by the constraint analysis, such as
242 heap variables and constraints we had to break up. */
243 unsigned int is_artificial_var
:1;
245 /* True if this is a special variable whose solution set should not be
247 unsigned int is_special_var
:1;
249 /* True for variables whose size is not known or variable. */
250 unsigned int is_unknown_size_var
:1;
252 /* True for variables that have unions somewhere in them. */
253 unsigned int has_union
:1;
255 /* True if this is a heap variable. */
256 unsigned int is_heap_var
:1;
258 /* Points-to set for this variable. */
261 /* Finished points-to set for this variable (IE what is returned
262 from find_what_p_points_to. */
263 bitmap finished_solution
;
265 /* Variable ids represented by this node. */
268 /* Vector of complex constraints for this node. Complex
269 constraints are those involving dereferences. */
270 VEC(constraint_t
,heap
) *complex;
272 /* Variable id this was collapsed to due to type unsafety.
273 This should be unused completely after build_constraint_graph, or
274 something is broken. */
275 struct variable_info
*collapsed_to
;
277 typedef struct variable_info
*varinfo_t
;
279 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
281 /* Pool of variable info structures. */
282 static alloc_pool variable_info_pool
;
284 DEF_VEC_P(varinfo_t
);
286 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
288 /* Table of variable info structures for constraint variables. Indexed directly
289 by variable info id. */
290 static VEC(varinfo_t
,heap
) *varmap
;
292 /* Return the varmap element N */
294 static inline varinfo_t
295 get_varinfo (unsigned int n
)
297 return VEC_index(varinfo_t
, varmap
, n
);
300 /* Return the varmap element N, following the collapsed_to link. */
302 static inline varinfo_t
303 get_varinfo_fc (unsigned int n
)
305 varinfo_t v
= VEC_index(varinfo_t
, varmap
, n
);
308 return v
->collapsed_to
;
312 /* Variable that represents the unknown pointer. */
313 static varinfo_t var_anything
;
314 static tree anything_tree
;
315 static unsigned int anything_id
;
317 /* Variable that represents the NULL pointer. */
318 static varinfo_t var_nothing
;
319 static tree nothing_tree
;
320 static unsigned int nothing_id
;
322 /* Variable that represents read only memory. */
323 static varinfo_t var_readonly
;
324 static tree readonly_tree
;
325 static unsigned int readonly_id
;
327 /* Variable that represents integers. This is used for when people do things
329 static varinfo_t var_integer
;
330 static tree integer_tree
;
331 static unsigned int integer_id
;
333 /* Lookup a heap var for FROM, and return it if we find one. */
336 heapvar_lookup (tree from
)
338 struct tree_map
*h
, in
;
341 h
= htab_find_with_hash (heapvar_for_stmt
, &in
, htab_hash_pointer (from
));
347 /* Insert a mapping FROM->TO in the heap var for statement
351 heapvar_insert (tree from
, tree to
)
356 h
= ggc_alloc (sizeof (struct tree_map
));
357 h
->hash
= htab_hash_pointer (from
);
360 loc
= htab_find_slot_with_hash (heapvar_for_stmt
, h
, h
->hash
, INSERT
);
361 *(struct tree_map
**) loc
= h
;
364 /* Return a new variable info structure consisting for a variable
365 named NAME, and using constraint graph node NODE. */
368 new_var_info (tree t
, unsigned int id
, const char *name
, unsigned int node
)
370 varinfo_t ret
= pool_alloc (variable_info_pool
);
376 ret
->address_taken
= false;
377 ret
->indirect_target
= false;
378 ret
->directly_dereferenced
= false;
379 ret
->is_artificial_var
= false;
380 ret
->is_heap_var
= false;
381 ret
->is_special_var
= false;
382 ret
->is_unknown_size_var
= false;
383 ret
->has_union
= false;
384 ret
->solution
= BITMAP_ALLOC (&ptabitmap_obstack
);
385 ret
->variables
= BITMAP_ALLOC (&ptabitmap_obstack
);
386 ret
->finished_solution
= NULL
;
389 ret
->collapsed_to
= NULL
;
393 typedef enum {SCALAR
, DEREF
, ADDRESSOF
, INCLUDES
} constraint_expr_type
;
395 /* An expression that appears in a constraint. */
397 struct constraint_expr
399 /* Constraint type. */
400 constraint_expr_type type
;
402 /* Variable we are referring to in the constraint. */
405 /* Offset, in bits, of this constraint from the beginning of
406 variables it ends up referring to.
408 IOW, in a deref constraint, we would deref, get the result set,
409 then add OFFSET to each member. */
410 unsigned HOST_WIDE_INT offset
;
413 typedef struct constraint_expr ce_s
;
415 DEF_VEC_ALLOC_O(ce_s
, heap
);
416 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
417 static void do_deref (VEC (ce_s
, heap
) **);
419 /* Our set constraints are made up of two constraint expressions, one
422 As described in the introduction, our set constraints each represent an
423 operation between set valued variables.
427 struct constraint_expr lhs
;
428 struct constraint_expr rhs
;
431 /* List of constraints that we use to build the constraint graph from. */
433 static VEC(constraint_t
,heap
) *constraints
;
434 static alloc_pool constraint_pool
;
437 /* The constraint graph is represented as an array of bitmaps
438 containing successor nodes. */
440 struct constraint_graph
446 typedef struct constraint_graph
*constraint_graph_t
;
448 static constraint_graph_t graph
;
450 /* Create a new constraint consisting of LHS and RHS expressions. */
453 new_constraint (const struct constraint_expr lhs
,
454 const struct constraint_expr rhs
)
456 constraint_t ret
= pool_alloc (constraint_pool
);
462 /* Print out constraint C to FILE. */
465 dump_constraint (FILE *file
, constraint_t c
)
467 if (c
->lhs
.type
== ADDRESSOF
)
469 else if (c
->lhs
.type
== DEREF
)
471 fprintf (file
, "%s", get_varinfo_fc (c
->lhs
.var
)->name
);
472 if (c
->lhs
.offset
!= 0)
473 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
474 fprintf (file
, " = ");
475 if (c
->rhs
.type
== ADDRESSOF
)
477 else if (c
->rhs
.type
== DEREF
)
479 else if (c
->rhs
.type
== INCLUDES
)
481 fprintf (file
, "%s", get_varinfo_fc (c
->rhs
.var
)->name
);
482 if (c
->rhs
.offset
!= 0)
483 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
484 if (c
->rhs
.type
== INCLUDES
)
486 fprintf (file
, "\n");
489 /* Print out constraint C to stderr. */
492 debug_constraint (constraint_t c
)
494 dump_constraint (stderr
, c
);
497 /* Print out all constraints to FILE */
500 dump_constraints (FILE *file
)
504 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
505 dump_constraint (file
, c
);
508 /* Print out all constraints to stderr. */
511 debug_constraints (void)
513 dump_constraints (stderr
);
518 The solver is a simple worklist solver, that works on the following
521 sbitmap changed_nodes = all ones;
522 changed_count = number of nodes;
523 For each node that was already collapsed:
526 while (changed_count > 0)
528 compute topological ordering for constraint graph
530 find and collapse cycles in the constraint graph (updating
531 changed if necessary)
533 for each node (n) in the graph in topological order:
536 Process each complex constraint associated with the node,
537 updating changed if necessary.
539 For each outgoing edge from n, propagate the solution from n to
540 the destination of the edge, updating changed as necessary.
544 /* Return true if two constraint expressions A and B are equal. */
547 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
549 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
552 /* Return true if constraint expression A is less than constraint expression
553 B. This is just arbitrary, but consistent, in order to give them an
557 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
559 if (a
.type
== b
.type
)
562 return a
.offset
< b
.offset
;
564 return a
.var
< b
.var
;
567 return a
.type
< b
.type
;
570 /* Return true if constraint A is less than constraint B. This is just
571 arbitrary, but consistent, in order to give them an ordering. */
574 constraint_less (const constraint_t a
, const constraint_t b
)
576 if (constraint_expr_less (a
->lhs
, b
->lhs
))
578 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
581 return constraint_expr_less (a
->rhs
, b
->rhs
);
584 /* Return true if two constraints A and B are equal. */
587 constraint_equal (struct constraint a
, struct constraint b
)
589 return constraint_expr_equal (a
.lhs
, b
.lhs
)
590 && constraint_expr_equal (a
.rhs
, b
.rhs
);
594 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
597 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
598 struct constraint lookfor
)
606 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
607 if (place
>= VEC_length (constraint_t
, vec
))
609 found
= VEC_index (constraint_t
, vec
, place
);
610 if (!constraint_equal (*found
, lookfor
))
615 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
618 constraint_set_union (VEC(constraint_t
,heap
) **to
,
619 VEC(constraint_t
,heap
) **from
)
624 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
626 if (constraint_vec_find (*to
, *c
) == NULL
)
628 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
630 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
635 /* Take a solution set SET, add OFFSET to each member of the set, and
636 overwrite SET with the result when done. */
639 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
641 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
645 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
647 /* If this is a properly sized variable, only add offset if it's
648 less than end. Otherwise, it is globbed to a single
651 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
653 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
654 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
657 bitmap_set_bit (result
, v
->id
);
659 else if (get_varinfo (i
)->is_artificial_var
660 || get_varinfo (i
)->has_union
661 || get_varinfo (i
)->is_unknown_size_var
)
663 bitmap_set_bit (result
, i
);
667 bitmap_copy (set
, result
);
668 BITMAP_FREE (result
);
671 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
675 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
678 return bitmap_ior_into (to
, from
);
684 tmp
= BITMAP_ALLOC (&iteration_obstack
);
685 bitmap_copy (tmp
, from
);
686 solution_set_add (tmp
, inc
);
687 res
= bitmap_ior_into (to
, tmp
);
693 /* Insert constraint C into the list of complex constraints for VAR. */
696 insert_into_complex (unsigned int var
, constraint_t c
)
698 varinfo_t vi
= get_varinfo (var
);
699 unsigned int place
= VEC_lower_bound (constraint_t
, vi
->complex, c
,
701 VEC_safe_insert (constraint_t
, heap
, vi
->complex, place
, c
);
705 /* Condense two variable nodes into a single variable node, by moving
706 all associated info from SRC to TO. */
709 condense_varmap_nodes (unsigned int to
, unsigned int src
)
711 varinfo_t tovi
= get_varinfo (to
);
712 varinfo_t srcvi
= get_varinfo (src
);
717 /* the src node, and all its variables, are now the to node. */
719 EXECUTE_IF_SET_IN_BITMAP (srcvi
->variables
, 0, i
, bi
)
720 get_varinfo (i
)->node
= to
;
722 /* Merge the src node variables and the to node variables. */
723 bitmap_set_bit (tovi
->variables
, src
);
724 bitmap_ior_into (tovi
->variables
, srcvi
->variables
);
725 bitmap_clear (srcvi
->variables
);
727 /* Move all complex constraints from src node into to node */
728 for (i
= 0; VEC_iterate (constraint_t
, srcvi
->complex, i
, c
); i
++)
730 /* In complex constraints for node src, we may have either
731 a = *src, and *src = a. */
733 if (c
->rhs
.type
== DEREF
)
738 constraint_set_union (&tovi
->complex, &srcvi
->complex);
739 VEC_free (constraint_t
, heap
, srcvi
->complex);
740 srcvi
->complex = NULL
;
744 /* Remove edges involving NODE from GRAPH. */
747 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
752 /* Walk the successors, erase the associated preds. */
754 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[node
], 0, j
, bi
)
756 bitmap_clear_bit (graph
->preds
[j
], node
);
759 /* Walk the preds, erase the associated succs. */
761 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[node
], 0, j
, bi
)
763 bitmap_clear_bit (graph
->succs
[j
], node
);
766 if (graph
->preds
[node
])
768 BITMAP_FREE (graph
->preds
[node
]);
769 graph
->preds
[node
] = NULL
;
772 if (graph
->succs
[node
])
774 BITMAP_FREE (graph
->succs
[node
]);
775 graph
->succs
[node
] = NULL
;
779 static bool edge_added
= false;
781 /* Merge GRAPH nodes FROM and TO into node TO. */
784 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
790 /* Merge all the predecessor edges. */
791 if (graph
->preds
[from
])
793 if (!graph
->preds
[to
])
794 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
796 EXECUTE_IF_SET_IN_BITMAP (graph
->preds
[from
], 0, j
, bi
)
800 bitmap_clear_bit (graph
->succs
[j
], from
);
801 bitmap_set_bit (graph
->succs
[j
], to
);
804 bitmap_ior_into (graph
->preds
[to
],
808 /* Merge all the successor edges. */
809 if (graph
->succs
[from
])
811 if (!graph
->succs
[to
])
812 graph
->succs
[to
] = BITMAP_ALLOC (&ptabitmap_obstack
);
813 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[from
], 0, j
, bi
)
815 bitmap_clear_bit (graph
->preds
[j
], from
);
816 bitmap_set_bit (graph
->preds
[j
], to
);
818 bitmap_ior_into (graph
->succs
[to
],
822 clear_edges_for_node (graph
, from
);
825 /* Add a graph edge to GRAPH, going from TO to FROM if
826 it doesn't exist in the graph already.
827 Return false if the edge already existed, true otherwise. */
830 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
841 if (!graph
->preds
[to
])
842 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
843 if (!graph
->succs
[from
])
844 graph
->succs
[from
] = BITMAP_ALLOC (&ptabitmap_obstack
);
845 if (!bitmap_bit_p (graph
->succs
[from
], to
))
850 bitmap_set_bit (graph
->preds
[to
], from
);
851 bitmap_set_bit (graph
->succs
[from
], to
);
858 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
861 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
864 return (graph
->succs
[dest
]
865 && bitmap_bit_p (graph
->succs
[dest
], src
));
868 /* Build the constraint graph. */
871 build_constraint_graph (void)
877 graph
= XNEW (struct constraint_graph
);
878 graph_size
= VEC_length (varinfo_t
, varmap
) + 1;
879 graph
->succs
= XCNEWVEC (bitmap
, graph_size
);
880 graph
->preds
= XCNEWVEC (bitmap
, graph_size
);
882 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
884 struct constraint_expr lhs
= c
->lhs
;
885 struct constraint_expr rhs
= c
->rhs
;
886 unsigned int lhsvar
= get_varinfo_fc (lhs
.var
)->id
;
887 unsigned int rhsvar
= get_varinfo_fc (rhs
.var
)->id
;
889 if (lhs
.type
== DEREF
)
891 /* *x = y or *x = &y (complex) */
892 if (rhs
.type
== ADDRESSOF
|| rhsvar
> anything_id
)
893 insert_into_complex (lhsvar
, c
);
895 else if (rhs
.type
== DEREF
)
897 /* !special var= *y */
898 if (!(get_varinfo (lhsvar
)->is_special_var
))
899 insert_into_complex (rhsvar
, c
);
901 else if (rhs
.type
== ADDRESSOF
|| rhs
.type
== INCLUDES
)
904 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
906 else if (lhsvar
> anything_id
)
908 /* Ignore self edges, as they can't possibly contribute
910 if (lhsvar
!= rhsvar
|| rhs
.offset
!= 0 || lhs
.offset
!= 0)
912 if (rhs
.offset
!= 0 || lhs
.offset
!= 0)
913 insert_into_complex (lhsvar
, c
);
915 add_graph_edge (graph
, lhs
.var
, rhs
.var
);
923 /* Changed variables on the last iteration. */
924 static unsigned int changed_count
;
925 static sbitmap changed
;
928 DEF_VEC_ALLOC_I(unsigned,heap
);
931 /* Strongly Connected Component visitation info. */
936 sbitmap in_component
;
938 unsigned int *visited_index
;
939 VEC(unsigned,heap
) *scc_stack
;
940 VEC(unsigned,heap
) *unification_queue
;
944 /* Recursive routine to find strongly connected components in GRAPH.
945 SI is the SCC info to store the information in, and N is the id of current
946 graph node we are processing.
948 This is Tarjan's strongly connected component finding algorithm, as
949 modified by Nuutila to keep only non-root nodes on the stack.
950 The algorithm can be found in "On finding the strongly connected
951 connected components in a directed graph" by Esko Nuutila and Eljas
952 Soisalon-Soininen, in Information Processing Letters volume 49,
953 number 1, pages 9-14. */
956 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
961 gcc_assert (get_varinfo (n
)->node
== n
);
962 SET_BIT (si
->visited
, n
);
963 RESET_BIT (si
->in_component
, n
);
964 si
->visited_index
[n
] = si
->current_index
++;
966 /* Visit all the successors. */
967 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
970 if (!TEST_BIT (si
->visited
, w
))
971 scc_visit (graph
, si
, w
);
972 if (!TEST_BIT (si
->in_component
, w
))
974 unsigned int t
= get_varinfo (w
)->node
;
975 unsigned int nnode
= get_varinfo (n
)->node
;
976 if (si
->visited_index
[t
] < si
->visited_index
[nnode
])
977 get_varinfo (n
)->node
= t
;
981 /* See if any components have been identified. */
982 if (get_varinfo (n
)->node
== n
)
984 unsigned int t
= si
->visited_index
[n
];
985 SET_BIT (si
->in_component
, n
);
986 while (VEC_length (unsigned, si
->scc_stack
) != 0
987 && t
< si
->visited_index
[VEC_last (unsigned, si
->scc_stack
)])
989 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
990 get_varinfo (w
)->node
= n
;
991 SET_BIT (si
->in_component
, w
);
992 /* Mark this node for collapsing. */
993 VEC_safe_push (unsigned, heap
, si
->unification_queue
, w
);
997 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1001 /* Collapse two variables into one variable, merging solutions if
1005 collapse_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1006 bool merge_solutions
)
1008 bitmap tosol
, fromsol
;
1010 merge_graph_nodes (graph
, to
, from
);
1011 condense_varmap_nodes (to
, from
);
1012 if (merge_solutions
)
1014 tosol
= get_varinfo (to
)->solution
;
1015 fromsol
= get_varinfo (from
)->solution
;
1016 bitmap_ior_into (tosol
, fromsol
);
1017 BITMAP_FREE (fromsol
);
1020 if (valid_graph_edge (graph
, to
, to
))
1022 if (graph
->preds
[to
])
1024 bitmap_clear_bit (graph
->preds
[to
], to
);
1025 bitmap_clear_bit (graph
->succs
[to
], to
);
1031 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1032 SI is the Strongly Connected Components information structure that tells us
1033 what components to unify.
1034 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1035 count should be updated to reflect the unification. */
1038 process_unification_queue (constraint_graph_t graph
, struct scc_info
*si
,
1039 bool update_changed
)
1042 bitmap tmp
= BITMAP_ALLOC (update_changed
? &iteration_obstack
: NULL
);
1045 /* We proceed as follows:
1047 For each component in the queue (components are delineated by
1048 when current_queue_element->node != next_queue_element->node):
1050 rep = representative node for component
1052 For each node (tounify) to be unified in the component,
1053 merge the solution for tounify into tmp bitmap
1055 clear solution for tounify
1057 merge edges from tounify into rep
1059 merge complex constraints from tounify into rep
1061 update changed count to note that tounify will never change
1064 Merge tmp into solution for rep, marking rep changed if this
1065 changed rep's solution.
1067 Delete any self-edges we now have for rep. */
1068 while (i
!= VEC_length (unsigned, si
->unification_queue
))
1070 unsigned int tounify
= VEC_index (unsigned, si
->unification_queue
, i
);
1071 unsigned int n
= get_varinfo (tounify
)->node
;
1073 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1074 fprintf (dump_file
, "Unifying %s to %s\n",
1075 get_varinfo (tounify
)->name
,
1076 get_varinfo (n
)->name
);
1078 stats
.unified_vars_dynamic
++;
1080 stats
.unified_vars_static
++;
1081 bitmap_ior_into (tmp
, get_varinfo (tounify
)->solution
);
1082 collapse_nodes (graph
, n
, tounify
, false);
1084 if (update_changed
&& TEST_BIT (changed
, tounify
))
1086 RESET_BIT (changed
, tounify
);
1087 if (!TEST_BIT (changed
, n
))
1088 SET_BIT (changed
, n
);
1091 gcc_assert (changed_count
> 0);
1096 bitmap_clear (get_varinfo (tounify
)->solution
);
1099 /* If we've either finished processing the entire queue, or
1100 finished processing all nodes for component n, update the solution for
1102 if (i
== VEC_length (unsigned, si
->unification_queue
)
1103 || get_varinfo (VEC_index (unsigned, si
->unification_queue
, i
))->node
!= n
)
1105 /* If the solution changes because of the merging, we need to mark
1106 the variable as changed. */
1107 if (bitmap_ior_into (get_varinfo (n
)->solution
, tmp
))
1109 if (update_changed
&& !TEST_BIT (changed
, n
))
1111 SET_BIT (changed
, n
);
1117 if (valid_graph_edge (graph
, n
, n
))
1119 if (graph
->succs
[n
])
1121 if (graph
->preds
[n
])
1122 bitmap_clear_bit (graph
->preds
[n
], n
);
1123 bitmap_clear_bit (graph
->succs
[n
], n
);
1132 /* Information needed to compute the topological ordering of a graph. */
1136 /* sbitmap of visited nodes. */
1138 /* Array that stores the topological order of the graph, *in
1140 VEC(unsigned,heap
) *topo_order
;
1144 /* Initialize and return a topological info structure. */
1146 static struct topo_info
*
1147 init_topo_info (void)
1149 size_t size
= VEC_length (varinfo_t
, varmap
);
1150 struct topo_info
*ti
= XNEW (struct topo_info
);
1151 ti
->visited
= sbitmap_alloc (size
);
1152 sbitmap_zero (ti
->visited
);
1153 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1158 /* Free the topological sort info pointed to by TI. */
1161 free_topo_info (struct topo_info
*ti
)
1163 sbitmap_free (ti
->visited
);
1164 VEC_free (unsigned, heap
, ti
->topo_order
);
1168 /* Visit the graph in topological order, and store the order in the
1169 topo_info structure. */
1172 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1179 SET_BIT (ti
->visited
, n
);
1180 temp
= graph
->succs
[n
];
1183 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, j
, bi
)
1185 if (!TEST_BIT (ti
->visited
, j
))
1186 topo_visit (graph
, ti
, j
);
1188 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1191 /* Return true if variable N + OFFSET is a legal field of N. */
1194 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1196 varinfo_t ninfo
= get_varinfo (n
);
1198 /* For things we've globbed to single variables, any offset into the
1199 variable acts like the entire variable, so that it becomes offset
1201 if (ninfo
->is_special_var
1202 || ninfo
->is_artificial_var
1203 || ninfo
->is_unknown_size_var
)
1208 return (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1211 /* Process a constraint C that represents *x = &y. */
1214 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1215 constraint_t c
, bitmap delta
)
1217 unsigned int rhs
= c
->rhs
.var
;
1221 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1222 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1224 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1225 if (type_safe (j
, &offset
) && !(get_varinfo (j
)->is_special_var
))
1227 /* *x != NULL && *x != ANYTHING*/
1231 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1233 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1237 sol
= get_varinfo (t
)->solution
;
1238 if (!bitmap_bit_p (sol
, rhs
))
1240 bitmap_set_bit (sol
, rhs
);
1241 if (!TEST_BIT (changed
, t
))
1243 SET_BIT (changed
, t
);
1248 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1249 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1254 /* Process a constraint C that represents x = *y, using DELTA as the
1255 starting solution. */
1258 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1261 unsigned int lhs
= get_varinfo (c
->lhs
.var
)->node
;
1263 bitmap sol
= get_varinfo (lhs
)->solution
;
1267 if (bitmap_bit_p (delta
, anything_id
))
1269 flag
= !bitmap_bit_p (sol
, anything_id
);
1271 bitmap_set_bit (sol
, anything_id
);
1274 /* For each variable j in delta (Sol(y)), add
1275 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1276 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1278 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1279 if (type_safe (j
, &roffset
))
1282 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1285 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1290 /* Adding edges from the special vars is pointless.
1291 They don't have sets that can change. */
1292 if (get_varinfo (t
) ->is_special_var
)
1293 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1294 else if (add_graph_edge (graph
, lhs
, t
))
1295 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1297 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1298 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1303 /* If the LHS solution changed, mark the var as changed. */
1306 get_varinfo (lhs
)->solution
= sol
;
1307 if (!TEST_BIT (changed
, lhs
))
1309 SET_BIT (changed
, lhs
);
1315 /* Process a constraint C that represents *x = y. */
1318 do_ds_constraint (constraint_t c
, bitmap delta
)
1320 unsigned int rhs
= get_varinfo (c
->rhs
.var
)->node
;
1321 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1322 bitmap sol
= get_varinfo (rhs
)->solution
;
1326 if (bitmap_bit_p (sol
, anything_id
))
1328 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1330 varinfo_t jvi
= get_varinfo (j
);
1332 unsigned int loff
= c
->lhs
.offset
;
1333 unsigned HOST_WIDE_INT fieldoffset
= jvi
->offset
+ loff
;
1336 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1341 if (!bitmap_bit_p (get_varinfo (t
)->solution
, anything_id
))
1343 bitmap_set_bit (get_varinfo (t
)->solution
, anything_id
);
1344 if (!TEST_BIT (changed
, t
))
1346 SET_BIT (changed
, t
);
1354 /* For each member j of delta (Sol(x)), add an edge from y to j and
1355 union Sol(y) into Sol(j) */
1356 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1358 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1359 if (type_safe (j
, &loff
) && !(get_varinfo(j
)->is_special_var
))
1363 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1366 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1370 tmp
= get_varinfo (t
)->solution
;
1372 if (set_union_with_increment (tmp
, sol
, roff
))
1374 get_varinfo (t
)->solution
= tmp
;
1376 sol
= get_varinfo (rhs
)->solution
;
1377 if (!TEST_BIT (changed
, t
))
1379 SET_BIT (changed
, t
);
1384 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1385 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1389 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1390 constraint (IE *x = &y, x = *y, and *x = y). */
1393 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1395 if (c
->lhs
.type
== DEREF
)
1397 if (c
->rhs
.type
== ADDRESSOF
)
1400 do_da_constraint (graph
, c
, delta
);
1405 do_ds_constraint (c
, delta
);
1408 else if (c
->rhs
.type
== DEREF
)
1411 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1412 do_sd_constraint (graph
, c
, delta
);
1421 gcc_assert(c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
);
1422 t
= get_varinfo (c
->rhs
.var
)->node
;
1423 solution
= get_varinfo (t
)->solution
;
1424 t
= get_varinfo (c
->lhs
.var
)->node
;
1425 tmp
= get_varinfo (t
)->solution
;
1427 flag
= set_union_with_increment (tmp
, solution
, c
->rhs
.offset
);
1431 get_varinfo (t
)->solution
= tmp
;
1432 if (!TEST_BIT (changed
, c
->lhs
.var
))
1434 SET_BIT (changed
, c
->lhs
.var
);
1441 /* Initialize and return a new SCC info structure. */
1443 static struct scc_info
*
1444 init_scc_info (void)
1446 struct scc_info
*si
= XNEW (struct scc_info
);
1447 size_t size
= VEC_length (varinfo_t
, varmap
);
1449 si
->current_index
= 0;
1450 si
->visited
= sbitmap_alloc (size
);
1451 sbitmap_zero (si
->visited
);
1452 si
->in_component
= sbitmap_alloc (size
);
1453 sbitmap_ones (si
->in_component
);
1454 si
->visited_index
= XCNEWVEC (unsigned int, size
+ 1);
1455 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1456 si
->unification_queue
= VEC_alloc (unsigned, heap
, 1);
1460 /* Free an SCC info structure pointed to by SI */
1463 free_scc_info (struct scc_info
*si
)
1465 sbitmap_free (si
->visited
);
1466 sbitmap_free (si
->in_component
);
1467 free (si
->visited_index
);
1468 VEC_free (unsigned, heap
, si
->scc_stack
);
1469 VEC_free (unsigned, heap
, si
->unification_queue
);
1474 /* Find cycles in GRAPH that occur, using strongly connected components, and
1475 collapse the cycles into a single representative node. if UPDATE_CHANGED
1476 is true, then update the changed sbitmap to note those nodes whose
1477 solutions have changed as a result of collapsing. */
1480 find_and_collapse_graph_cycles (constraint_graph_t graph
, bool update_changed
)
1483 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1484 struct scc_info
*si
= init_scc_info ();
1486 for (i
= 0; i
!= size
; ++i
)
1487 if (!TEST_BIT (si
->visited
, i
) && get_varinfo (i
)->node
== i
)
1488 scc_visit (graph
, si
, i
);
1490 process_unification_queue (graph
, si
, update_changed
);
1494 /* Compute a topological ordering for GRAPH, and store the result in the
1495 topo_info structure TI. */
1498 compute_topo_order (constraint_graph_t graph
,
1499 struct topo_info
*ti
)
1502 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1504 for (i
= 0; i
!= size
; ++i
)
1505 if (!TEST_BIT (ti
->visited
, i
) && get_varinfo (i
)->node
== i
)
1506 topo_visit (graph
, ti
, i
);
1509 /* Perform offline variable substitution.
1511 This is a linear time way of identifying variables that must have
1512 equivalent points-to sets, including those caused by static cycles,
1513 and single entry subgraphs, in the constraint graph.
1515 The technique is described in "Off-line variable substitution for
1516 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1517 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1520 perform_var_substitution (constraint_graph_t graph
)
1522 struct topo_info
*ti
= init_topo_info ();
1524 bitmap_obstack_initialize (&iteration_obstack
);
1525 /* Compute the topological ordering of the graph, then visit each
1526 node in topological order. */
1527 compute_topo_order (graph
, ti
);
1529 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1531 unsigned int i
= VEC_pop (unsigned, ti
->topo_order
);
1532 varinfo_t vi
= get_varinfo (i
);
1533 bool okay_to_elim
= false;
1534 unsigned int root
= VEC_length (varinfo_t
, varmap
);
1539 /* We can't eliminate things whose address is taken, or which is
1540 the target of a dereference. */
1541 if (vi
->address_taken
|| vi
->indirect_target
)
1544 /* See if all predecessors of I are ripe for elimination */
1545 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[i
], 0, k
, bi
)
1548 w
= get_varinfo (k
)->node
;
1550 /* We can't eliminate the node if one of the predecessors is
1551 part of a different strongly connected component. */
1555 okay_to_elim
= true;
1559 okay_to_elim
= false;
1563 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1564 then Solution(i) is a subset of Solution (w), where w is a
1565 predecessor in the graph.
1566 Corollary: If all predecessors of i have the same
1567 points-to set, then i has that same points-to set as
1568 those predecessors. */
1569 tmp
= BITMAP_ALLOC (NULL
);
1570 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1571 get_varinfo (w
)->solution
);
1572 if (!bitmap_empty_p (tmp
))
1574 okay_to_elim
= false;
1581 /* See if the root is different than the original node.
1582 If so, we've found an equivalence. */
1583 if (root
!= get_varinfo (i
)->node
&& okay_to_elim
)
1585 /* Found an equivalence */
1586 get_varinfo (i
)->node
= root
;
1587 collapse_nodes (graph
, root
, i
, true);
1588 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1589 fprintf (dump_file
, "Collapsing %s into %s\n",
1590 get_varinfo (i
)->name
,
1591 get_varinfo (root
)->name
);
1592 stats
.collapsed_vars
++;
1596 bitmap_obstack_release (&iteration_obstack
);
1597 free_topo_info (ti
);
1600 /* Solve the constraint graph GRAPH using our worklist solver.
1601 This is based on the PW* family of solvers from the "Efficient Field
1602 Sensitive Pointer Analysis for C" paper.
1603 It works by iterating over all the graph nodes, processing the complex
1604 constraints and propagating the copy constraints, until everything stops
1605 changed. This corresponds to steps 6-8 in the solving list given above. */
1608 solve_graph (constraint_graph_t graph
)
1610 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1613 changed_count
= size
;
1614 changed
= sbitmap_alloc (size
);
1615 sbitmap_ones (changed
);
1617 /* The already collapsed/unreachable nodes will never change, so we
1618 need to account for them in changed_count. */
1619 for (i
= 0; i
< size
; i
++)
1620 if (get_varinfo (i
)->node
!= i
)
1623 while (changed_count
> 0)
1626 struct topo_info
*ti
= init_topo_info ();
1629 bitmap_obstack_initialize (&iteration_obstack
);
1633 /* We already did cycle elimination once, when we did
1634 variable substitution, so we don't need it again for the
1636 if (stats
.iterations
> 1)
1637 find_and_collapse_graph_cycles (graph
, true);
1642 compute_topo_order (graph
, ti
);
1644 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1646 i
= VEC_pop (unsigned, ti
->topo_order
);
1647 gcc_assert (get_varinfo (i
)->node
== i
);
1649 /* If the node has changed, we need to process the
1650 complex constraints and outgoing edges again. */
1651 if (TEST_BIT (changed
, i
))
1657 VEC(constraint_t
,heap
) *complex = get_varinfo (i
)->complex;
1658 bool solution_empty
;
1660 RESET_BIT (changed
, i
);
1663 solution
= get_varinfo (i
)->solution
;
1664 solution_empty
= bitmap_empty_p (solution
);
1666 /* Process the complex constraints */
1667 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
1669 /* The only complex constraint that can change our
1670 solution to non-empty, given an empty solution,
1671 is a constraint where the lhs side is receiving
1672 some set from elsewhere. */
1673 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
1674 do_complex_constraint (graph
, c
, solution
);
1677 solution_empty
= bitmap_empty_p (solution
);
1679 if (!solution_empty
)
1681 /* Propagate solution to all successors. */
1682 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
1685 bitmap tmp
= get_varinfo (j
)->solution
;
1688 gcc_assert (get_varinfo (j
)->node
== j
);
1690 flag
= set_union_with_increment (tmp
, solution
, 0);
1694 get_varinfo (j
)->solution
= tmp
;
1695 if (!TEST_BIT (changed
, j
))
1697 SET_BIT (changed
, j
);
1705 free_topo_info (ti
);
1706 bitmap_obstack_release (&iteration_obstack
);
1709 sbitmap_free (changed
);
1713 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1715 /* Map from trees to variable ids. */
1716 static htab_t id_for_tree
;
1718 typedef struct tree_id
1724 /* Hash a tree id structure. */
1727 tree_id_hash (const void *p
)
1729 const tree_id_t ta
= (tree_id_t
) p
;
1730 return htab_hash_pointer (ta
->t
);
1733 /* Return true if the tree in P1 and the tree in P2 are the same. */
1736 tree_id_eq (const void *p1
, const void *p2
)
1738 const tree_id_t ta1
= (tree_id_t
) p1
;
1739 const tree_id_t ta2
= (tree_id_t
) p2
;
1740 return ta1
->t
== ta2
->t
;
1743 /* Insert ID as the variable id for tree T in the hashtable. */
1746 insert_id_for_tree (tree t
, int id
)
1749 struct tree_id finder
;
1753 slot
= htab_find_slot (id_for_tree
, &finder
, INSERT
);
1754 gcc_assert (*slot
== NULL
);
1755 new_pair
= XNEW (struct tree_id
);
1758 *slot
= (void *)new_pair
;
1761 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1762 exist in the hash table, return false, otherwise, return true and
1763 set *ID to the id we found. */
1766 lookup_id_for_tree (tree t
, unsigned int *id
)
1769 struct tree_id finder
;
1772 pair
= htab_find (id_for_tree
, &finder
);
1779 /* Return a printable name for DECL */
1782 alias_get_name (tree decl
)
1784 const char *res
= get_name (decl
);
1786 int num_printed
= 0;
1795 if (TREE_CODE (decl
) == SSA_NAME
)
1797 num_printed
= asprintf (&temp
, "%s_%u",
1798 alias_get_name (SSA_NAME_VAR (decl
)),
1799 SSA_NAME_VERSION (decl
));
1801 else if (DECL_P (decl
))
1803 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
1805 if (num_printed
> 0)
1807 res
= ggc_strdup (temp
);
1813 /* Find the variable id for tree T in the hashtable.
1814 If T doesn't exist in the hash table, create an entry for it. */
1817 get_id_for_tree (tree t
)
1820 struct tree_id finder
;
1823 pair
= htab_find (id_for_tree
, &finder
);
1825 return create_variable_info_for (t
, alias_get_name (t
));
1830 /* Get a constraint expression from an SSA_VAR_P node. */
1832 static struct constraint_expr
1833 get_constraint_exp_from_ssa_var (tree t
)
1835 struct constraint_expr cexpr
;
1837 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
1839 /* For parameters, get at the points-to set for the actual parm
1841 if (TREE_CODE (t
) == SSA_NAME
1842 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
1843 && gimple_default_def (cfun
, SSA_NAME_VAR (t
)) == t
)
1844 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
1846 cexpr
.type
= SCALAR
;
1848 cexpr
.var
= get_id_for_tree (t
);
1849 /* If we determine the result is "anything", and we know this is readonly,
1850 say it points to readonly memory instead. */
1851 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
1853 cexpr
.type
= INCLUDES
;
1854 cexpr
.var
= readonly_id
;
1861 /* Process a completed constraint T, and add it to the constraint
1865 process_constraint (constraint_t t
)
1867 struct constraint_expr rhs
= t
->rhs
;
1868 struct constraint_expr lhs
= t
->lhs
;
1870 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
1871 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
1873 gcc_assert (lhs
.type
!= INCLUDES
);
1875 if (lhs
.type
== DEREF
)
1876 get_varinfo (lhs
.var
)->directly_dereferenced
= true;
1877 if (rhs
.type
== DEREF
)
1878 get_varinfo (rhs
.var
)->directly_dereferenced
= true;
1880 if (!use_field_sensitive
)
1886 /* ANYTHING == ANYTHING is pointless. */
1887 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
1890 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1891 else if (lhs
.var
== anything_id
1892 && (lhs
.type
== INCLUDES
|| lhs
.type
== ADDRESSOF
))
1897 process_constraint (t
);
1899 /* This can happen in our IR with things like n->a = *p */
1900 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
1902 /* Split into tmp = *rhs, *lhs = tmp */
1903 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
1904 tree pointertype
= TREE_TYPE (rhsdecl
);
1905 tree pointedtotype
= TREE_TYPE (pointertype
);
1906 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
1907 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
1909 /* If this is an aggregate of known size, we should have passed
1910 this off to do_structure_copy, and it should have broken it
1912 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
1913 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
1915 process_constraint (new_constraint (tmplhs
, rhs
));
1916 process_constraint (new_constraint (lhs
, tmplhs
));
1918 else if (rhs
.type
== ADDRESSOF
)
1921 gcc_assert (rhs
.offset
== 0);
1923 for (vi
= get_varinfo (rhs
.var
); vi
!= NULL
; vi
= vi
->next
)
1924 vi
->address_taken
= true;
1926 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
1930 if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
1931 get_varinfo (lhs
.var
)->indirect_target
= true;
1932 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
1936 /* Return true if T is a variable of a type that could contain
1940 could_have_pointers (tree t
)
1942 tree type
= TREE_TYPE (t
);
1944 if (POINTER_TYPE_P (type
) || AGGREGATE_TYPE_P (type
)
1945 || TREE_CODE (type
) == COMPLEX_TYPE
)
1950 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1953 static unsigned HOST_WIDE_INT
1954 bitpos_of_field (const tree fdecl
)
1957 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
1958 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
1961 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
1962 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
1966 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1967 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1970 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
1971 const unsigned HOST_WIDE_INT fieldsize
,
1972 const unsigned HOST_WIDE_INT accesspos
,
1973 const unsigned HOST_WIDE_INT accesssize
)
1975 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
1977 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
1979 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
1985 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1988 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
)
1991 HOST_WIDE_INT bitsize
= -1;
1992 HOST_WIDE_INT bitmaxsize
= -1;
1993 HOST_WIDE_INT bitpos
;
1995 struct constraint_expr
*result
;
1996 unsigned int beforelength
= VEC_length (ce_s
, *results
);
1998 /* Some people like to do cute things like take the address of
2001 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
2002 forzero
= TREE_OPERAND (forzero
, 0);
2004 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
2006 struct constraint_expr temp
;
2009 temp
.var
= integer_id
;
2011 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2015 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
2017 /* String constants are readonly, so there is nothing to really do
2019 if (TREE_CODE (t
) == STRING_CST
)
2022 get_constraint_for (t
, results
);
2023 result
= VEC_last (ce_s
, *results
);
2024 result
->offset
= bitpos
;
2026 gcc_assert (beforelength
+ 1 == VEC_length (ce_s
, *results
));
2028 /* This can also happen due to weird offsetof type macros. */
2029 if (TREE_CODE (t
) != ADDR_EXPR
&& result
->type
== ADDRESSOF
)
2030 result
->type
= SCALAR
;
2032 if (result
->type
== SCALAR
)
2034 /* In languages like C, you can access one past the end of an
2035 array. You aren't allowed to dereference it, so we can
2036 ignore this constraint. When we handle pointer subtraction,
2037 we may have to do something cute here. */
2039 if (result
->offset
< get_varinfo (result
->var
)->fullsize
2042 /* It's also not true that the constraint will actually start at the
2043 right offset, it may start in some padding. We only care about
2044 setting the constraint to the first actual field it touches, so
2047 for (curr
= get_varinfo (result
->var
); curr
; curr
= curr
->next
)
2049 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2050 result
->offset
, bitmaxsize
))
2052 result
->var
= curr
->id
;
2056 /* assert that we found *some* field there. The user couldn't be
2057 accessing *only* padding. */
2058 /* Still the user could access one past the end of an array
2059 embedded in a struct resulting in accessing *only* padding. */
2060 gcc_assert (curr
|| ref_contains_array_ref (orig_t
));
2062 else if (bitmaxsize
== 0)
2064 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2065 fprintf (dump_file
, "Access to zero-sized part of variable,"
2069 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2070 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2077 /* Dereference the constraint expression CONS, and return the result.
2078 DEREF (ADDRESSOF) = SCALAR
2079 DEREF (SCALAR) = DEREF
2080 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2081 This is needed so that we can handle dereferencing DEREF constraints. */
2084 do_deref (VEC (ce_s
, heap
) **constraints
)
2086 struct constraint_expr
*c
;
2089 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
2091 if (c
->type
== SCALAR
)
2093 else if (c
->type
== ADDRESSOF
)
2095 else if (c
->type
== DEREF
)
2097 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "dereftmp");
2098 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2099 process_constraint (new_constraint (tmplhs
, *c
));
2100 c
->var
= tmplhs
.var
;
2107 /* Given a tree T, return the constraint expression for it. */
2110 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
2112 struct constraint_expr temp
;
2114 /* x = integer is all glommed to a single variable, which doesn't
2115 point to anything by itself. That is, of course, unless it is an
2116 integer constant being treated as a pointer, in which case, we
2117 will return that this is really the addressof anything. This
2118 happens below, since it will fall into the default case. The only
2119 case we know something about an integer treated like a pointer is
2120 when it is the NULL pointer, and then we just say it points to
2122 if (TREE_CODE (t
) == INTEGER_CST
2123 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2125 temp
.var
= integer_id
;
2128 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2131 else if (TREE_CODE (t
) == INTEGER_CST
2132 && integer_zerop (t
))
2134 temp
.var
= nothing_id
;
2135 temp
.type
= ADDRESSOF
;
2137 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2141 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2143 case tcc_expression
:
2145 switch (TREE_CODE (t
))
2149 struct constraint_expr
*c
;
2151 tree exp
= TREE_OPERAND (t
, 0);
2152 tree pttype
= TREE_TYPE (TREE_TYPE (t
));
2154 get_constraint_for (exp
, results
);
2155 /* Make sure we capture constraints to all elements
2157 if ((handled_component_p (exp
)
2158 && ref_contains_array_ref (exp
))
2159 || TREE_CODE (TREE_TYPE (exp
)) == ARRAY_TYPE
)
2161 struct constraint_expr
*origrhs
;
2163 struct constraint_expr tmp
;
2165 if (VEC_length (ce_s
, *results
) == 0)
2168 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2169 origrhs
= VEC_last (ce_s
, *results
);
2171 VEC_pop (ce_s
, *results
);
2172 origvar
= get_varinfo (origrhs
->var
);
2173 for (; origvar
; origvar
= origvar
->next
)
2175 tmp
.var
= origvar
->id
;
2176 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2179 else if (VEC_length (ce_s
, *results
) == 1
2180 && (AGGREGATE_TYPE_P (pttype
)
2181 || TREE_CODE (pttype
) == COMPLEX_TYPE
))
2183 struct constraint_expr
*origrhs
;
2185 struct constraint_expr tmp
;
2187 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2188 origrhs
= VEC_last (ce_s
, *results
);
2190 VEC_pop (ce_s
, *results
);
2191 origvar
= get_varinfo (origrhs
->var
);
2192 for (; origvar
; origvar
= origvar
->next
)
2194 tmp
.var
= origvar
->id
;
2195 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2199 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
2201 if (c
->type
== DEREF
)
2204 c
->type
= ADDRESSOF
;
2210 /* XXX: In interprocedural mode, if we didn't have the
2211 body, we would need to do *each pointer argument =
2213 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2216 tree heapvar
= heapvar_lookup (t
);
2218 if (heapvar
== NULL
)
2220 heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2221 DECL_EXTERNAL (heapvar
) = 1;
2222 get_var_ann (heapvar
)->is_heapvar
= 1;
2223 if (gimple_referenced_vars (cfun
))
2224 add_referenced_var (heapvar
);
2225 heapvar_insert (t
, heapvar
);
2228 temp
.var
= create_variable_info_for (heapvar
,
2229 alias_get_name (heapvar
));
2231 vi
= get_varinfo (temp
.var
);
2232 vi
->is_artificial_var
= 1;
2233 vi
->is_heap_var
= 1;
2234 temp
.type
= INCLUDES
;
2236 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2241 temp
.var
= anything_id
;
2244 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2250 temp
.type
= ADDRESSOF
;
2251 temp
.var
= anything_id
;
2253 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2260 switch (TREE_CODE (t
))
2264 get_constraint_for (TREE_OPERAND (t
, 0), results
);
2269 case ARRAY_RANGE_REF
:
2271 get_constraint_for_component_ref (t
, results
);
2275 temp
.type
= ADDRESSOF
;
2276 temp
.var
= anything_id
;
2278 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2285 switch (TREE_CODE (t
))
2289 case NON_LVALUE_EXPR
:
2291 tree op
= TREE_OPERAND (t
, 0);
2293 /* Cast from non-pointer to pointers are bad news for us.
2294 Anything else, we see through */
2295 if (!(POINTER_TYPE_P (TREE_TYPE (t
))
2296 && ! POINTER_TYPE_P (TREE_TYPE (op
))))
2298 get_constraint_for (op
, results
);
2306 temp
.type
= ADDRESSOF
;
2307 temp
.var
= anything_id
;
2309 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2314 case tcc_exceptional
:
2316 switch (TREE_CODE (t
))
2320 get_constraint_for (PHI_RESULT (t
), results
);
2326 struct constraint_expr temp
;
2327 temp
= get_constraint_exp_from_ssa_var (t
);
2328 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2334 temp
.type
= ADDRESSOF
;
2335 temp
.var
= anything_id
;
2337 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2342 case tcc_declaration
:
2344 struct constraint_expr temp
;
2345 temp
= get_constraint_exp_from_ssa_var (t
);
2346 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2351 temp
.type
= ADDRESSOF
;
2352 temp
.var
= anything_id
;
2354 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2361 /* Handle the structure copy case where we have a simple structure copy
2362 between LHS and RHS that is of SIZE (in bits)
2364 For each field of the lhs variable (lhsfield)
2365 For each field of the rhs variable at lhsfield.offset (rhsfield)
2366 add the constraint lhsfield = rhsfield
2368 If we fail due to some kind of type unsafety or other thing we
2369 can't handle, return false. We expect the caller to collapse the
2370 variable in that case. */
2373 do_simple_structure_copy (const struct constraint_expr lhs
,
2374 const struct constraint_expr rhs
,
2375 const unsigned HOST_WIDE_INT size
)
2377 varinfo_t p
= get_varinfo (lhs
.var
);
2378 unsigned HOST_WIDE_INT pstart
, last
;
2380 last
= p
->offset
+ size
;
2381 for (; p
&& p
->offset
< last
; p
= p
->next
)
2384 struct constraint_expr templhs
= lhs
;
2385 struct constraint_expr temprhs
= rhs
;
2386 unsigned HOST_WIDE_INT fieldoffset
;
2388 templhs
.var
= p
->id
;
2389 q
= get_varinfo (temprhs
.var
);
2390 fieldoffset
= p
->offset
- pstart
;
2391 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2394 temprhs
.var
= q
->id
;
2395 process_constraint (new_constraint (templhs
, temprhs
));
2401 /* Handle the structure copy case where we have a structure copy between a
2402 aggregate on the LHS and a dereference of a pointer on the RHS
2403 that is of SIZE (in bits)
2405 For each field of the lhs variable (lhsfield)
2406 rhs.offset = lhsfield->offset
2407 add the constraint lhsfield = rhs
2411 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2412 const struct constraint_expr rhs
,
2413 const unsigned HOST_WIDE_INT size
)
2415 varinfo_t p
= get_varinfo (lhs
.var
);
2416 unsigned HOST_WIDE_INT pstart
,last
;
2418 last
= p
->offset
+ size
;
2420 for (; p
&& p
->offset
< last
; p
= p
->next
)
2423 struct constraint_expr templhs
= lhs
;
2424 struct constraint_expr temprhs
= rhs
;
2425 unsigned HOST_WIDE_INT fieldoffset
;
2428 if (templhs
.type
== SCALAR
)
2429 templhs
.var
= p
->id
;
2431 templhs
.offset
= p
->offset
;
2433 q
= get_varinfo (temprhs
.var
);
2434 fieldoffset
= p
->offset
- pstart
;
2435 temprhs
.offset
+= fieldoffset
;
2436 process_constraint (new_constraint (templhs
, temprhs
));
2440 /* Handle the structure copy case where we have a structure copy
2441 between a aggregate on the RHS and a dereference of a pointer on
2442 the LHS that is of SIZE (in bits)
2444 For each field of the rhs variable (rhsfield)
2445 lhs.offset = rhsfield->offset
2446 add the constraint lhs = rhsfield
2450 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2451 const struct constraint_expr rhs
,
2452 const unsigned HOST_WIDE_INT size
)
2454 varinfo_t p
= get_varinfo (rhs
.var
);
2455 unsigned HOST_WIDE_INT pstart
,last
;
2457 last
= p
->offset
+ size
;
2459 for (; p
&& p
->offset
< last
; p
= p
->next
)
2462 struct constraint_expr templhs
= lhs
;
2463 struct constraint_expr temprhs
= rhs
;
2464 unsigned HOST_WIDE_INT fieldoffset
;
2467 if (temprhs
.type
== SCALAR
)
2468 temprhs
.var
= p
->id
;
2470 temprhs
.offset
= p
->offset
;
2472 q
= get_varinfo (templhs
.var
);
2473 fieldoffset
= p
->offset
- pstart
;
2474 templhs
.offset
+= fieldoffset
;
2475 process_constraint (new_constraint (templhs
, temprhs
));
2479 /* Sometimes, frontends like to give us bad type information. This
2480 function will collapse all the fields from VAR to the end of VAR,
2481 into VAR, so that we treat those fields as a single variable.
2482 We return the variable they were collapsed into. */
2485 collapse_rest_of_var (unsigned int var
)
2487 varinfo_t currvar
= get_varinfo (var
);
2490 for (field
= currvar
->next
; field
; field
= field
->next
)
2493 fprintf (dump_file
, "Type safety: Collapsing var %s into %s\n",
2494 field
->name
, currvar
->name
);
2496 gcc_assert (!field
->collapsed_to
);
2497 field
->collapsed_to
= currvar
;
2500 currvar
->next
= NULL
;
2501 currvar
->size
= currvar
->fullsize
- currvar
->offset
;
2506 /* Handle aggregate copies by expanding into copies of the respective
2507 fields of the structures. */
2510 do_structure_copy (tree lhsop
, tree rhsop
)
2512 struct constraint_expr lhs
, rhs
, tmp
;
2513 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
2515 unsigned HOST_WIDE_INT lhssize
;
2516 unsigned HOST_WIDE_INT rhssize
;
2518 get_constraint_for (lhsop
, &lhsc
);
2519 get_constraint_for (rhsop
, &rhsc
);
2520 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
2521 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
2522 lhs
= *(VEC_last (ce_s
, lhsc
));
2523 rhs
= *(VEC_last (ce_s
, rhsc
));
2525 VEC_free (ce_s
, heap
, lhsc
);
2526 VEC_free (ce_s
, heap
, rhsc
);
2528 /* If we have special var = x, swap it around. */
2529 if (lhs
.var
<= integer_id
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2536 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2537 possible it's something we could handle. However, most cases falling
2538 into this are dealing with transparent unions, which are slightly
2540 if (rhs
.type
== ADDRESSOF
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2542 rhs
.type
= ADDRESSOF
;
2543 rhs
.var
= anything_id
;
2546 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2547 that special var. */
2548 if (rhs
.var
<= integer_id
)
2550 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2552 struct constraint_expr templhs
= lhs
;
2553 struct constraint_expr temprhs
= rhs
;
2555 if (templhs
.type
== SCALAR
)
2556 templhs
.var
= p
->id
;
2558 templhs
.offset
+= p
->offset
;
2559 process_constraint (new_constraint (templhs
, temprhs
));
2564 tree rhstype
= TREE_TYPE (rhsop
);
2565 tree lhstype
= TREE_TYPE (lhsop
);
2569 lhstypesize
= DECL_P (lhsop
) ? DECL_SIZE (lhsop
) : TYPE_SIZE (lhstype
);
2570 rhstypesize
= DECL_P (rhsop
) ? DECL_SIZE (rhsop
) : TYPE_SIZE (rhstype
);
2572 /* If we have a variably sized types on the rhs or lhs, and a deref
2573 constraint, add the constraint, lhsconstraint = &ANYTHING.
2574 This is conservatively correct because either the lhs is an unknown
2575 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2576 constraint, and every variable it can point to must be unknown sized
2577 anyway, so we don't need to worry about fields at all. */
2578 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
2579 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
2581 rhs
.var
= anything_id
;
2582 rhs
.type
= ADDRESSOF
;
2584 process_constraint (new_constraint (lhs
, rhs
));
2588 /* The size only really matters insofar as we don't set more or less of
2589 the variable. If we hit an unknown size var, the size should be the
2590 whole darn thing. */
2591 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
2594 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
2596 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
2599 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
2602 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
2604 if (!do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
)))
2606 lhs
.var
= collapse_rest_of_var (lhs
.var
);
2607 rhs
.var
= collapse_rest_of_var (rhs
.var
);
2612 process_constraint (new_constraint (lhs
, rhs
));
2615 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2616 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2617 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
2618 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2621 tree pointedtotype
= lhstype
;
2624 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
2625 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
2626 do_structure_copy (tmpvar
, rhsop
);
2627 do_structure_copy (lhsop
, tmpvar
);
2632 /* Update related alias information kept in AI. This is used when
2633 building name tags, alias sets and deciding grouping heuristics.
2634 STMT is the statement to process. This function also updates
2635 ADDRESSABLE_VARS. */
2638 update_alias_info (tree stmt
, struct alias_info
*ai
)
2641 use_operand_p use_p
;
2643 enum escape_type stmt_escape_type
= is_escape_site (stmt
);
2646 if (stmt_escape_type
== ESCAPE_TO_CALL
2647 || stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
2649 ai
->num_calls_found
++;
2650 if (stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
2651 ai
->num_pure_const_calls_found
++;
2654 /* Mark all the variables whose address are taken by the statement. */
2655 addr_taken
= addresses_taken (stmt
);
2658 bitmap_ior_into (gimple_addressable_vars (cfun
), addr_taken
);
2660 /* If STMT is an escape point, all the addresses taken by it are
2662 if (stmt_escape_type
!= NO_ESCAPE
)
2667 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
2669 tree rvar
= referenced_var (i
);
2670 if (!unmodifiable_var_p (rvar
))
2671 mark_call_clobbered (rvar
, stmt_escape_type
);
2676 /* Process each operand use. If an operand may be aliased, keep
2677 track of how many times it's being used. For pointers, determine
2678 whether they are dereferenced by the statement, or whether their
2679 value escapes, etc. */
2680 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2684 struct ptr_info_def
*pi
;
2685 bool is_store
, is_potential_deref
;
2686 unsigned num_uses
, num_derefs
;
2688 op
= USE_FROM_PTR (use_p
);
2690 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2691 to the set of addressable variables. */
2692 if (TREE_CODE (op
) == ADDR_EXPR
)
2694 bitmap addressable_vars
= gimple_addressable_vars (cfun
);
2696 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
);
2697 gcc_assert (addressable_vars
);
2699 /* PHI nodes don't have annotations for pinning the set
2700 of addresses taken, so we collect them here.
2702 FIXME, should we allow PHI nodes to have annotations
2703 so that they can be treated like regular statements?
2704 Currently, they are treated as second-class
2706 add_to_addressable_set (TREE_OPERAND (op
, 0),
2711 /* Ignore constants. */
2712 if (TREE_CODE (op
) != SSA_NAME
)
2715 var
= SSA_NAME_VAR (op
);
2716 v_ann
= var_ann (var
);
2718 /* The base variable of an ssa name must be a GIMPLE register, and thus
2719 it cannot be aliased. */
2720 gcc_assert (!may_be_aliased (var
));
2722 /* We are only interested in pointers. */
2723 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
2726 pi
= get_ptr_info (op
);
2728 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2729 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
)))
2731 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
));
2732 VEC_safe_push (tree
, heap
, ai
->processed_ptrs
, op
);
2735 /* If STMT is a PHI node, then it will not have pointer
2736 dereferences and it will not be an escape point. */
2737 if (TREE_CODE (stmt
) == PHI_NODE
)
2740 /* Determine whether OP is a dereferenced pointer, and if STMT
2741 is an escape point, whether OP escapes. */
2742 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
2744 /* Handle a corner case involving address expressions of the
2745 form '&PTR->FLD'. The problem with these expressions is that
2746 they do not represent a dereference of PTR. However, if some
2747 other transformation propagates them into an INDIRECT_REF
2748 expression, we end up with '*(&PTR->FLD)' which is folded
2751 So, if the original code had no other dereferences of PTR,
2752 the aliaser will not create memory tags for it, and when
2753 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
2754 memory operations will receive no V_MAY_DEF/VUSE operands.
2756 One solution would be to have count_uses_and_derefs consider
2757 &PTR->FLD a dereference of PTR. But that is wrong, since it
2758 is not really a dereference but an offset calculation.
2760 What we do here is to recognize these special ADDR_EXPR
2761 nodes. Since these expressions are never GIMPLE values (they
2762 are not GIMPLE invariants), they can only appear on the RHS
2763 of an assignment and their base address is always an
2764 INDIRECT_REF expression. */
2765 is_potential_deref
= false;
2766 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
2767 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == ADDR_EXPR
2768 && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt
, 1)))
2770 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
2771 this represents a potential dereference of PTR. */
2772 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
2773 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
2774 if (TREE_CODE (base
) == INDIRECT_REF
2775 && TREE_OPERAND (base
, 0) == op
)
2776 is_potential_deref
= true;
2779 if (num_derefs
> 0 || is_potential_deref
)
2781 /* Mark OP as dereferenced. In a subsequent pass,
2782 dereferenced pointers that point to a set of
2783 variables will be assigned a name tag to alias
2784 all the variables OP points to. */
2785 pi
->is_dereferenced
= 1;
2787 /* Keep track of how many time we've dereferenced each
2789 NUM_REFERENCES_INC (v_ann
);
2791 /* If this is a store operation, mark OP as being
2792 dereferenced to store, otherwise mark it as being
2793 dereferenced to load. */
2795 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
2797 bitmap_set_bit (ai
->dereferenced_ptrs_load
, DECL_UID (var
));
2800 if (stmt_escape_type
!= NO_ESCAPE
&& num_derefs
< num_uses
)
2802 /* If STMT is an escape point and STMT contains at
2803 least one direct use of OP, then the value of OP
2804 escapes and so the pointed-to variables need to
2805 be marked call-clobbered. */
2806 pi
->value_escapes_p
= 1;
2807 pi
->escape_mask
|= stmt_escape_type
;
2809 /* If the statement makes a function call, assume
2810 that pointer OP will be dereferenced in a store
2811 operation inside the called function. */
2812 if (get_call_expr_in (stmt
)
2813 || stmt_escape_type
== ESCAPE_STORED_IN_GLOBAL
)
2815 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
2816 pi
->is_dereferenced
= 1;
2821 if (TREE_CODE (stmt
) == PHI_NODE
)
2824 /* Update reference counter for definitions to any
2825 potentially aliased variable. This is used in the alias
2826 grouping heuristics. */
2827 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
2829 tree var
= SSA_NAME_VAR (op
);
2830 var_ann_t ann
= var_ann (var
);
2831 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
2832 if (may_be_aliased (var
))
2833 NUM_REFERENCES_INC (ann
);
2837 /* Mark variables in V_MAY_DEF operands as being written to. */
2838 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
2840 tree var
= DECL_P (op
) ? op
: SSA_NAME_VAR (op
);
2841 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
2846 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
2847 Expressions of the type PTR + CST can be handled in two ways:
2849 1- If the constraint for PTR is ADDRESSOF for a non-structure
2850 variable, then we can use it directly because adding or
2851 subtracting a constant may not alter the original ADDRESSOF
2852 constraint (i.e., pointer arithmetic may not legally go outside
2853 an object's boundaries).
2855 2- If the constraint for PTR is ADDRESSOF for a structure variable,
2856 then if CST is a compile-time constant that can be used as an
2857 offset, we can determine which sub-variable will be pointed-to
2860 Return true if the expression is handled. For any other kind of
2861 expression, return false so that each operand can be added as a
2862 separate constraint by the caller. */
2865 handle_ptr_arith (VEC (ce_s
, heap
) *lhsc
, tree expr
)
2868 struct constraint_expr
*c
, *c2
;
2871 VEC (ce_s
, heap
) *temp
= NULL
;
2872 unsigned int rhsoffset
= 0;
2874 if (TREE_CODE (expr
) != PLUS_EXPR
2875 && TREE_CODE (expr
) != MINUS_EXPR
)
2878 op0
= TREE_OPERAND (expr
, 0);
2879 op1
= TREE_OPERAND (expr
, 1);
2881 get_constraint_for (op0
, &temp
);
2882 if (POINTER_TYPE_P (TREE_TYPE (op0
))
2883 && TREE_CODE (op1
) == INTEGER_CST
2884 && TREE_CODE (expr
) == PLUS_EXPR
)
2886 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
2890 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
2891 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
2893 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
2895 varinfo_t temp
= get_varinfo (c2
->var
);
2897 /* An access one after the end of an array is valid,
2898 so simply punt on accesses we cannot resolve. */
2899 temp
= first_vi_for_offset (temp
, rhsoffset
);
2906 c2
->offset
= rhsoffset
;
2907 process_constraint (new_constraint (*c
, *c2
));
2910 VEC_free (ce_s
, heap
, temp
);
2916 /* Walk statement T setting up aliasing constraints according to the
2917 references found in T. This function is the main part of the
2918 constraint builder. AI points to auxiliary alias information used
2919 when building alias sets and computing alias grouping heuristics. */
2922 find_func_aliases (tree origt
)
2925 VEC(ce_s
, heap
) *lhsc
= NULL
;
2926 VEC(ce_s
, heap
) *rhsc
= NULL
;
2927 struct constraint_expr
*c
;
2929 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
2930 t
= TREE_OPERAND (t
, 0);
2932 /* Now build constraints expressions. */
2933 if (TREE_CODE (t
) == PHI_NODE
)
2935 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))));
2937 /* Only care about pointers and structures containing
2939 if (could_have_pointers (PHI_RESULT (t
)))
2944 /* For a phi node, assign all the arguments to
2946 get_constraint_for (PHI_RESULT (t
), &lhsc
);
2947 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
2950 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
2952 STRIP_NOPS (strippedrhs
);
2953 rhstype
= TREE_TYPE (strippedrhs
);
2954 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
2956 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
2958 struct constraint_expr
*c2
;
2959 while (VEC_length (ce_s
, rhsc
) > 0)
2961 c2
= VEC_last (ce_s
, rhsc
);
2962 process_constraint (new_constraint (*c
, *c2
));
2963 VEC_pop (ce_s
, rhsc
);
2969 /* In IPA mode, we need to generate constraints to pass call
2970 arguments through their calls. There are two case, either a
2971 modify_expr when we are returning a value, or just a plain
2972 call_expr when we are not. */
2973 else if (in_ipa_mode
2974 && ((TREE_CODE (t
) == GIMPLE_MODIFY_STMT
2975 && TREE_CODE (GIMPLE_STMT_OPERAND (t
, 1)) == CALL_EXPR
2976 && !(call_expr_flags (GIMPLE_STMT_OPERAND (t
, 1))
2977 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
2978 || (TREE_CODE (t
) == CALL_EXPR
2979 && !(call_expr_flags (t
)
2980 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
2989 if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
2991 lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
2992 rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
2999 decl
= get_callee_fndecl (rhsop
);
3001 /* If we can directly resolve the function being called, do so.
3002 Otherwise, it must be some sort of indirect expression that
3003 we should still be able to handle. */
3006 varid
= get_id_for_tree (decl
);
3010 decl
= TREE_OPERAND (rhsop
, 0);
3011 varid
= get_id_for_tree (decl
);
3014 /* Assign all the passed arguments to the appropriate incoming
3015 parameters of the function. */
3016 fi
= get_varinfo (varid
);
3017 arglist
= TREE_OPERAND (rhsop
, 1);
3019 for (;arglist
; arglist
= TREE_CHAIN (arglist
))
3021 tree arg
= TREE_VALUE (arglist
);
3022 struct constraint_expr lhs
;
3023 struct constraint_expr
*rhsp
;
3025 get_constraint_for (arg
, &rhsc
);
3026 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3035 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3038 while (VEC_length (ce_s
, rhsc
) != 0)
3040 rhsp
= VEC_last (ce_s
, rhsc
);
3041 process_constraint (new_constraint (lhs
, *rhsp
));
3042 VEC_pop (ce_s
, rhsc
);
3046 /* If we are returning a value, assign it to the result. */
3049 struct constraint_expr rhs
;
3050 struct constraint_expr
*lhsp
;
3053 get_constraint_for (lhsop
, &lhsc
);
3054 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3063 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3066 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3067 process_constraint (new_constraint (*lhsp
, rhs
));
3070 /* Otherwise, just a regular assignment statement. */
3071 else if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
3073 tree lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
3074 tree rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
3077 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3078 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
)
3079 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop
))
3080 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
))
3082 do_structure_copy (lhsop
, rhsop
);
3086 /* Only care about operations with pointers, structures
3087 containing pointers, dereferences, and call expressions. */
3088 if (could_have_pointers (lhsop
)
3089 || TREE_CODE (rhsop
) == CALL_EXPR
)
3091 get_constraint_for (lhsop
, &lhsc
);
3092 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3094 /* RHS that consist of unary operations,
3095 exceptional types, or bare decls/constants, get
3096 handled directly by get_constraint_for. */
3098 case tcc_declaration
:
3100 case tcc_exceptional
:
3101 case tcc_expression
:
3106 get_constraint_for (rhsop
, &rhsc
);
3107 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3109 struct constraint_expr
*c2
;
3112 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3113 process_constraint (new_constraint (*c
, *c2
));
3121 /* For pointer arithmetic of the form
3122 PTR + CST, we can simply use PTR's
3123 constraint because pointer arithmetic is
3124 not allowed to go out of bounds. */
3125 if (handle_ptr_arith (lhsc
, rhsop
))
3130 /* Otherwise, walk each operand. Notice that we
3131 can't use the operand interface because we need
3132 to process expressions other than simple operands
3133 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3135 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
3137 tree op
= TREE_OPERAND (rhsop
, i
);
3140 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3141 get_constraint_for (op
, &rhsc
);
3142 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3144 struct constraint_expr
*c2
;
3145 while (VEC_length (ce_s
, rhsc
) > 0)
3147 c2
= VEC_last (ce_s
, rhsc
);
3148 process_constraint (new_constraint (*c
, *c2
));
3149 VEC_pop (ce_s
, rhsc
);
3158 /* After promoting variables and computing aliasing we will
3159 need to re-scan most statements. FIXME: Try to minimize the
3160 number of statements re-scanned. It's not really necessary to
3161 re-scan *all* statements. */
3162 mark_stmt_modified (origt
);
3163 VEC_free (ce_s
, heap
, rhsc
);
3164 VEC_free (ce_s
, heap
, lhsc
);
3168 /* Find the first varinfo in the same variable as START that overlaps with
3170 Effectively, walk the chain of fields for the variable START to find the
3171 first field that overlaps with OFFSET.
3172 Return NULL if we can't find one. */
3175 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3177 varinfo_t curr
= start
;
3180 /* We may not find a variable in the field list with the actual
3181 offset when when we have glommed a structure to a variable.
3182 In that case, however, offset should still be within the size
3184 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3192 /* Insert the varinfo FIELD into the field list for BASE, at the front
3196 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3198 varinfo_t prev
= base
;
3199 varinfo_t curr
= base
->next
;
3205 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3209 insert_into_field_list_sorted (varinfo_t base
, varinfo_t field
)
3211 varinfo_t prev
= base
;
3212 varinfo_t curr
= base
->next
;
3223 if (field
->offset
<= curr
->offset
)
3228 field
->next
= prev
->next
;
3233 /* qsort comparison function for two fieldoff's PA and PB */
3236 fieldoff_compare (const void *pa
, const void *pb
)
3238 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3239 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3240 HOST_WIDE_INT foasize
, fobsize
;
3242 if (foa
->offset
!= fob
->offset
)
3243 return foa
->offset
- fob
->offset
;
3245 foasize
= TREE_INT_CST_LOW (foa
->size
);
3246 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3247 return foasize
- fobsize
;
3250 /* Sort a fieldstack according to the field offset and sizes. */
3252 sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3254 qsort (VEC_address (fieldoff_s
, fieldstack
),
3255 VEC_length (fieldoff_s
, fieldstack
),
3256 sizeof (fieldoff_s
),
3260 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3261 of TYPE onto fieldstack, recording their offsets along the way.
3262 OFFSET is used to keep track of the offset in this entire structure, rather
3263 than just the immediately containing structure. Returns the number
3265 HAS_UNION is set to true if we find a union type as a field of
3269 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3270 HOST_WIDE_INT offset
, bool *has_union
)
3275 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3277 fieldoff_s
*real_part
, *img_part
;
3278 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3279 real_part
->type
= TREE_TYPE (type
);
3280 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3281 real_part
->offset
= offset
;
3282 real_part
->decl
= NULL_TREE
;
3284 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3285 img_part
->type
= TREE_TYPE (type
);
3286 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3287 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3288 img_part
->decl
= NULL_TREE
;
3293 if (TREE_CODE (type
) == ARRAY_TYPE
)
3295 tree sz
= TYPE_SIZE (type
);
3296 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3301 || ! host_integerp (sz
, 1)
3302 || TREE_INT_CST_LOW (sz
) == 0
3304 || ! host_integerp (elsz
, 1)
3305 || TREE_INT_CST_LOW (elsz
) == 0)
3308 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3309 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3312 for (i
= 0; i
< nr
; ++i
)
3318 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3319 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3322 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3324 else if (!(pushed
= push_fields_onto_fieldstack
3325 (TREE_TYPE (type
), fieldstack
,
3326 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
)))
3327 /* Empty structures may have actual size, like in C++. So
3328 see if we didn't push any subfields and the size is
3329 nonzero, push the field onto the stack */
3336 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3337 pair
->type
= TREE_TYPE (type
);
3339 pair
->decl
= NULL_TREE
;
3340 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3350 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3351 if (TREE_CODE (field
) == FIELD_DECL
)
3357 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3358 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3361 if (!var_can_have_subvars (field
))
3363 else if (!(pushed
= push_fields_onto_fieldstack
3364 (TREE_TYPE (field
), fieldstack
,
3365 offset
+ bitpos_of_field (field
), has_union
))
3366 && DECL_SIZE (field
)
3367 && !integer_zerop (DECL_SIZE (field
)))
3368 /* Empty structures may have actual size, like in C++. So
3369 see if we didn't push any subfields and the size is
3370 nonzero, push the field onto the stack */
3377 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3378 pair
->type
= TREE_TYPE (field
);
3379 pair
->size
= DECL_SIZE (field
);
3381 pair
->offset
= offset
+ bitpos_of_field (field
);
3391 /* Create a constraint from ANYTHING variable to VI. */
3393 make_constraint_from_anything (varinfo_t vi
)
3395 struct constraint_expr lhs
, rhs
;
3401 rhs
.var
= anything_id
;
3403 rhs
.type
= INCLUDES
;
3404 process_constraint (new_constraint (lhs
, rhs
));
3407 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3408 if it is a varargs function. */
3411 count_num_arguments (tree decl
, bool *is_varargs
)
3416 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3420 if (TREE_VALUE (t
) == void_type_node
)
3430 /* Creation function node for DECL, using NAME, and return the index
3431 of the variable we've created for the function. */
3434 create_function_info_for (tree decl
, const char *name
)
3436 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3440 bool is_varargs
= false;
3442 /* Create the variable info. */
3444 vi
= new_var_info (decl
, index
, name
, index
);
3449 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3450 insert_id_for_tree (vi
->decl
, index
);
3451 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3455 /* If it's varargs, we don't know how many arguments it has, so we
3462 vi
->is_unknown_size_var
= true;
3467 arg
= DECL_ARGUMENTS (decl
);
3469 /* Set up variables for each argument. */
3470 for (i
= 1; i
< vi
->fullsize
; i
++)
3473 const char *newname
;
3475 unsigned int newindex
;
3476 tree argdecl
= decl
;
3481 newindex
= VEC_length (varinfo_t
, varmap
);
3482 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3483 newname
= ggc_strdup (tempname
);
3486 argvi
= new_var_info (argdecl
, newindex
,newname
, newindex
);
3487 argvi
->decl
= argdecl
;
3488 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3491 argvi
->fullsize
= vi
->fullsize
;
3492 argvi
->has_union
= false;
3493 insert_into_field_list_sorted (vi
, argvi
);
3494 stats
.total_vars
++;
3497 insert_id_for_tree (arg
, newindex
);
3498 arg
= TREE_CHAIN (arg
);
3502 /* Create a variable for the return var. */
3503 if (DECL_RESULT (decl
) != NULL
3504 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3507 const char *newname
;
3509 unsigned int newindex
;
3510 tree resultdecl
= decl
;
3514 if (DECL_RESULT (decl
))
3515 resultdecl
= DECL_RESULT (decl
);
3517 newindex
= VEC_length (varinfo_t
, varmap
);
3518 asprintf (&tempname
, "%s.result", name
);
3519 newname
= ggc_strdup (tempname
);
3522 resultvi
= new_var_info (resultdecl
, newindex
, newname
, newindex
);
3523 resultvi
->decl
= resultdecl
;
3524 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3525 resultvi
->offset
= i
;
3527 resultvi
->fullsize
= vi
->fullsize
;
3528 resultvi
->has_union
= false;
3529 insert_into_field_list_sorted (vi
, resultvi
);
3530 stats
.total_vars
++;
3531 if (DECL_RESULT (decl
))
3532 insert_id_for_tree (DECL_RESULT (decl
), newindex
);
3538 /* Return true if FIELDSTACK contains fields that overlap.
3539 FIELDSTACK is assumed to be sorted by offset. */
3542 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3544 fieldoff_s
*fo
= NULL
;
3546 HOST_WIDE_INT lastoffset
= -1;
3548 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3550 if (fo
->offset
== lastoffset
)
3552 lastoffset
= fo
->offset
;
3557 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3558 This will also create any varinfo structures necessary for fields
3562 create_variable_info_for (tree decl
, const char *name
)
3564 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3566 tree
decltype = TREE_TYPE (decl
);
3567 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
3568 bool notokay
= false;
3570 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
3571 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
3573 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
3574 return create_function_info_for (decl
, name
);
3576 hasunion
= TREE_CODE (decltype) == UNION_TYPE
3577 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
3578 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
3580 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
3583 VEC_free (fieldoff_s
, heap
, fieldstack
);
3589 /* If the variable doesn't have subvars, we may end up needing to
3590 sort the field list and create fake variables for all the
3592 vi
= new_var_info (decl
, index
, name
, index
);
3595 vi
->has_union
= hasunion
;
3597 || TREE_CODE (declsize
) != INTEGER_CST
3598 || TREE_CODE (decltype) == UNION_TYPE
3599 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
3601 vi
->is_unknown_size_var
= true;
3607 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
3608 vi
->size
= vi
->fullsize
;
3611 insert_id_for_tree (vi
->decl
, index
);
3612 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3613 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3614 make_constraint_from_anything (vi
);
3617 if (use_field_sensitive
3619 && !vi
->is_unknown_size_var
3620 && var_can_have_subvars (decl
)
3621 && VEC_length (fieldoff_s
, fieldstack
) <= MAX_FIELDS_FOR_FIELD_SENSITIVE
)
3623 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
3624 fieldoff_s
*fo
= NULL
;
3627 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3630 || TREE_CODE (fo
->size
) != INTEGER_CST
3638 /* We can't sort them if we have a field with a variable sized type,
3639 which will make notokay = true. In that case, we are going to return
3640 without creating varinfos for the fields anyway, so sorting them is a
3644 sort_fieldstack (fieldstack
);
3645 /* Due to some C++ FE issues, like PR 22488, we might end up
3646 what appear to be overlapping fields even though they,
3647 in reality, do not overlap. Until the C++ FE is fixed,
3648 we will simply disable field-sensitivity for these cases. */
3649 notokay
= check_for_overlaps (fieldstack
);
3653 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
3654 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
3656 if (fo
== NULL
|| notokay
)
3658 vi
->is_unknown_size_var
= 1;
3661 VEC_free (fieldoff_s
, heap
, fieldstack
);
3665 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
3666 vi
->offset
= fo
->offset
;
3667 for (i
= VEC_length (fieldoff_s
, fieldstack
) - 1;
3668 i
>= 1 && VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
3672 const char *newname
= "NULL";
3675 newindex
= VEC_length (varinfo_t
, varmap
);
3679 asprintf (&tempname
, "%s.%s",
3680 vi
->name
, alias_get_name (fo
->decl
));
3682 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
,
3683 vi
->name
, fo
->offset
);
3684 newname
= ggc_strdup (tempname
);
3687 newvi
= new_var_info (decl
, newindex
, newname
, newindex
);
3688 newvi
->offset
= fo
->offset
;
3689 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
3690 newvi
->fullsize
= vi
->fullsize
;
3691 insert_into_field_list (vi
, newvi
);
3692 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
3693 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3694 make_constraint_from_anything (newvi
);
3698 VEC_free (fieldoff_s
, heap
, fieldstack
);
3703 /* Print out the points-to solution for VAR to FILE. */
3706 dump_solution_for_var (FILE *file
, unsigned int var
)
3708 varinfo_t vi
= get_varinfo (var
);
3712 if (vi
->node
!= var
)
3714 varinfo_t vipt
= get_varinfo (vi
->node
);
3715 fprintf (file
, "%s = same as %s\n", vi
->name
, vipt
->name
);
3719 fprintf (file
, "%s = { ", vi
->name
);
3720 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi
->node
)->solution
, 0, i
, bi
)
3722 fprintf (file
, "%s ", get_varinfo (i
)->name
);
3724 fprintf (file
, "}\n");
3728 /* Print the points-to solution for VAR to stdout. */
3731 debug_solution_for_var (unsigned int var
)
3733 dump_solution_for_var (stdout
, var
);
3736 /* Create varinfo structures for all of the variables in the
3737 function for intraprocedural mode. */
3740 intra_create_variable_infos (void)
3743 struct constraint_expr lhs
, rhs
;
3745 /* For each incoming pointer argument arg, ARG = ANYTHING or a
3746 dummy variable if flag_argument_noalias > 2. */
3747 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
3750 unsigned int arg_id
;
3752 if (!could_have_pointers (t
))
3755 arg_id
= get_id_for_tree (t
);
3757 /* With flag_argument_noalias greater than two means that the incoming
3758 argument cannot alias anything except for itself so create a HEAP
3760 if (POINTER_TYPE_P (TREE_TYPE (t
))
3761 && flag_argument_noalias
> 2)
3764 tree heapvar
= heapvar_lookup (t
);
3769 lhs
.var
= get_id_for_tree (t
);
3771 if (heapvar
== NULL_TREE
)
3773 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)),
3775 get_var_ann (heapvar
)->is_heapvar
= 1;
3776 DECL_EXTERNAL (heapvar
) = 1;
3777 if (gimple_referenced_vars (cfun
))
3778 add_referenced_var (heapvar
);
3779 heapvar_insert (t
, heapvar
);
3781 id
= get_id_for_tree (heapvar
);
3782 vi
= get_varinfo (id
);
3783 vi
->is_artificial_var
= 1;
3784 vi
->is_heap_var
= 1;
3786 rhs
.type
= INCLUDES
;
3788 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
3790 struct constraint_expr temp
= lhs
;
3792 process_constraint (new_constraint (temp
, rhs
));
3797 for (p
= get_varinfo (arg_id
); p
; p
= p
->next
)
3798 make_constraint_from_anything (p
);
3803 /* Set bits in INTO corresponding to the variable uids in solution set
3804 FROM, which came from variable PTR.
3805 For variables that are actually dereferenced, we also use type
3806 based alias analysis to prune the points-to sets. */
3809 set_uids_in_ptset (tree ptr
, bitmap into
, bitmap from
)
3814 HOST_WIDE_INT ptr_alias_set
= get_alias_set (TREE_TYPE (ptr
));
3816 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
3818 varinfo_t vi
= get_varinfo (i
);
3819 unsigned HOST_WIDE_INT var_alias_set
;
3821 /* The only artificial variables that are allowed in a may-alias
3822 set are heap variables. */
3823 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
3826 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
3828 /* Variables containing unions may need to be converted to
3829 their SFT's, because SFT's can have unions and we cannot. */
3830 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
3831 bitmap_set_bit (into
, DECL_UID (sv
->var
));
3833 else if (TREE_CODE (vi
->decl
) == VAR_DECL
3834 || TREE_CODE (vi
->decl
) == PARM_DECL
)
3836 if (var_can_have_subvars (vi
->decl
)
3837 && get_subvars_for_var (vi
->decl
))
3839 /* If VI->DECL is an aggregate for which we created
3840 SFTs, add the SFT corresponding to VI->OFFSET. */
3841 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
3844 var_alias_set
= get_alias_set (sft
);
3845 if (!vi
->directly_dereferenced
3846 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
3847 bitmap_set_bit (into
, DECL_UID (sft
));
3852 /* Otherwise, just add VI->DECL to the alias set.
3853 Don't type prune artificial vars. */
3854 if (vi
->is_artificial_var
)
3855 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
3858 var_alias_set
= get_alias_set (vi
->decl
);
3859 if (!vi
->directly_dereferenced
3860 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
3861 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
3869 static bool have_alias_info
= false;
3871 /* The list of SMT's that are in use by our pointer variables. This
3872 is the set of SMT's for all pointers that can point to anything. */
3873 static bitmap used_smts
;
3875 /* Due to the ordering of points-to set calculation and SMT
3876 calculation being a bit co-dependent, we can't just calculate SMT
3877 used info whenever we want, we have to calculate it around the time
3878 that find_what_p_points_to is called. */
3880 /* Mark which SMT's are in use by points-to anything variables. */
3883 set_used_smts (void)
3887 used_smts
= BITMAP_ALLOC (&ptabitmap_obstack
);
3889 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, vi
); i
++)
3891 tree var
= vi
->decl
;
3894 struct ptr_info_def
*pi
= NULL
;
3896 /* For parm decls, the pointer info may be under the default
3898 if (TREE_CODE (vi
->decl
) == PARM_DECL
3899 && gimple_default_def (cfun
, var
))
3900 pi
= SSA_NAME_PTR_INFO (gimple_default_def (cfun
, var
));
3901 else if (TREE_CODE (var
) == SSA_NAME
)
3902 pi
= SSA_NAME_PTR_INFO (var
);
3904 /* Skip the special variables and those without their own
3906 if (vi
->is_special_var
|| vi
->node
!= vi
->id
|| !SSA_VAR_P (var
)
3907 || (pi
&& !pi
->is_dereferenced
)
3908 || (TREE_CODE (var
) == VAR_DECL
&& !may_be_aliased (var
))
3909 || !POINTER_TYPE_P (TREE_TYPE (var
)))
3912 if (TREE_CODE (var
) == SSA_NAME
)
3913 var
= SSA_NAME_VAR (var
);
3919 smt
= va
->symbol_mem_tag
;
3920 if (smt
&& bitmap_bit_p (vi
->solution
, anything_id
))
3921 bitmap_set_bit (used_smts
, DECL_UID (smt
));
3925 /* Merge the necessary SMT's into the solution set for VI, which is
3926 P's varinfo. This involves merging all SMT's that are a subset of
3927 the SMT necessary for P. */
3930 merge_smts_into (tree p
, varinfo_t vi
)
3935 VEC(tree
, gc
) *aliases
;
3938 if (TREE_CODE (p
) == SSA_NAME
)
3939 var
= SSA_NAME_VAR (p
);
3941 smt
= var_ann (var
)->symbol_mem_tag
;
3944 HOST_WIDE_INT smtset
= get_alias_set (TREE_TYPE (smt
));
3946 /* Need to set the SMT subsets first before this
3947 will work properly. */
3948 bitmap_set_bit (vi
->finished_solution
, DECL_UID (smt
));
3949 EXECUTE_IF_SET_IN_BITMAP (used_smts
, 0, i
, bi
)
3951 tree newsmt
= referenced_var (i
);
3952 tree newsmttype
= TREE_TYPE (newsmt
);
3954 if (alias_set_subset_of (get_alias_set (newsmttype
),
3956 bitmap_set_bit (vi
->finished_solution
, i
);
3959 aliases
= var_ann (smt
)->may_aliases
;
3964 for (k
= 0; VEC_iterate (tree
, aliases
, k
, al
); k
++)
3965 bitmap_set_bit (vi
->finished_solution
,
3971 /* Given a pointer variable P, fill in its points-to set, or return
3973 Rather than return false for variables that point-to anything, we
3974 instead find the corresponding SMT, and merge in it's aliases. In
3975 addition to these aliases, we also set the bits for the SMT's
3976 themselves and their subsets, as SMT's are still in use by
3977 non-SSA_NAME's, and pruning may eliminate every one of their
3978 aliases. In such a case, if we did not include the right set of
3979 SMT's in the points-to set of the variable, we'd end up with
3980 statements that do not conflict but should. */
3983 find_what_p_points_to (tree p
)
3985 unsigned int id
= 0;
3988 if (!have_alias_info
)
3991 /* For parameters, get at the points-to set for the actual parm
3993 if (TREE_CODE (p
) == SSA_NAME
3994 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
3995 && gimple_default_def (cfun
, SSA_NAME_VAR (p
)) == p
)
3996 lookup_p
= SSA_NAME_VAR (p
);
3998 if (lookup_id_for_tree (lookup_p
, &id
))
4000 varinfo_t vi
= get_varinfo (id
);
4002 if (vi
->is_artificial_var
)
4005 /* See if this is a field or a structure. */
4006 if (vi
->size
!= vi
->fullsize
)
4008 /* Nothing currently asks about structure fields directly,
4009 but when they do, we need code here to hand back the
4011 if (!var_can_have_subvars (vi
->decl
)
4012 || get_subvars_for_var (vi
->decl
) == NULL
)
4017 struct ptr_info_def
*pi
= get_ptr_info (p
);
4020 bool was_pt_anything
= false;
4022 if (!pi
->is_dereferenced
)
4025 /* This variable may have been collapsed, let's get the real
4027 vi
= get_varinfo (vi
->node
);
4029 /* Translate artificial variables into SSA_NAME_PTR_INFO
4031 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4033 varinfo_t vi
= get_varinfo (i
);
4035 if (vi
->is_artificial_var
)
4037 /* FIXME. READONLY should be handled better so that
4038 flow insensitive aliasing can disregard writable
4040 if (vi
->id
== nothing_id
)
4042 else if (vi
->id
== anything_id
)
4043 was_pt_anything
= 1;
4044 else if (vi
->id
== readonly_id
)
4045 was_pt_anything
= 1;
4046 else if (vi
->id
== integer_id
)
4047 was_pt_anything
= 1;
4048 else if (vi
->is_heap_var
)
4049 pi
->pt_global_mem
= 1;
4053 /* Share the final set of variables between the SSA_NAME
4054 pointer infos for collapsed nodes that are collapsed to
4055 non-special variables. This is because special vars have
4056 no real types associated with them, so while we know the
4057 pointers are equivalent to them, we need to generate the
4058 solution separately since it will include SMT's from the
4059 original non-collapsed variable. */
4060 if (!vi
->is_special_var
&& vi
->finished_solution
)
4062 pi
->pt_vars
= vi
->finished_solution
;
4066 vi
->finished_solution
= BITMAP_GGC_ALLOC ();
4068 /* Instead of using pt_anything, we instead merge in the SMT
4069 aliases for the underlying SMT. */
4070 if (was_pt_anything
)
4072 merge_smts_into (p
, vi
);
4073 pi
->pt_global_mem
= 1;
4076 set_uids_in_ptset (vi
->decl
, vi
->finished_solution
, vi
->solution
);
4077 pi
->pt_vars
= vi
->finished_solution
;
4080 if (bitmap_empty_p (pi
->pt_vars
))
4092 /* Dump points-to information to OUTFILE. */
4095 dump_sa_points_to_info (FILE *outfile
)
4099 fprintf (outfile
, "\nPoints-to sets\n\n");
4101 if (dump_flags
& TDF_STATS
)
4103 fprintf (outfile
, "Stats:\n");
4104 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4105 fprintf (outfile
, "Statically unified vars: %d\n",
4106 stats
.unified_vars_static
);
4107 fprintf (outfile
, "Collapsed vars: %d\n", stats
.collapsed_vars
);
4108 fprintf (outfile
, "Dynamically unified vars: %d\n",
4109 stats
.unified_vars_dynamic
);
4110 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4111 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4114 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4115 dump_solution_for_var (outfile
, i
);
4119 /* Debug points-to information to stderr. */
4122 debug_sa_points_to_info (void)
4124 dump_sa_points_to_info (stderr
);
4128 /* Initialize the always-existing constraint variables for NULL
4129 ANYTHING, READONLY, and INTEGER */
4132 init_base_vars (void)
4134 struct constraint_expr lhs
, rhs
;
4136 /* Create the NULL variable, used to represent that a variable points
4138 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4139 var_nothing
= new_var_info (nothing_tree
, 0, "NULL", 0);
4140 insert_id_for_tree (nothing_tree
, 0);
4141 var_nothing
->is_artificial_var
= 1;
4142 var_nothing
->offset
= 0;
4143 var_nothing
->size
= ~0;
4144 var_nothing
->fullsize
= ~0;
4145 var_nothing
->is_special_var
= 1;
4147 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4149 /* Create the ANYTHING variable, used to represent that a variable
4150 points to some unknown piece of memory. */
4151 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4152 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING", 1);
4153 insert_id_for_tree (anything_tree
, 1);
4154 var_anything
->is_artificial_var
= 1;
4155 var_anything
->size
= ~0;
4156 var_anything
->offset
= 0;
4157 var_anything
->next
= NULL
;
4158 var_anything
->fullsize
= ~0;
4159 var_anything
->is_special_var
= 1;
4162 /* Anything points to anything. This makes deref constraints just
4163 work in the presence of linked list and other p = *p type loops,
4164 by saying that *ANYTHING = ANYTHING. */
4165 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4167 lhs
.var
= anything_id
;
4169 rhs
.type
= INCLUDES
;
4170 rhs
.var
= anything_id
;
4172 var_anything
->address_taken
= true;
4174 /* This specifically does not use process_constraint because
4175 process_constraint ignores all anything = anything constraints, since all
4176 but this one are redundant. */
4177 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4179 /* Create the READONLY variable, used to represent that a variable
4180 points to readonly memory. */
4181 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4182 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY", 2);
4183 var_readonly
->is_artificial_var
= 1;
4184 var_readonly
->offset
= 0;
4185 var_readonly
->size
= ~0;
4186 var_readonly
->fullsize
= ~0;
4187 var_readonly
->next
= NULL
;
4188 var_readonly
->is_special_var
= 1;
4189 insert_id_for_tree (readonly_tree
, 2);
4191 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4193 /* readonly memory points to anything, in order to make deref
4194 easier. In reality, it points to anything the particular
4195 readonly variable can point to, but we don't track this
4198 lhs
.var
= readonly_id
;
4200 rhs
.type
= INCLUDES
;
4201 rhs
.var
= anything_id
;
4204 process_constraint (new_constraint (lhs
, rhs
));
4206 /* Create the INTEGER variable, used to represent that a variable points
4208 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4209 var_integer
= new_var_info (integer_tree
, 3, "INTEGER", 3);
4210 insert_id_for_tree (integer_tree
, 3);
4211 var_integer
->is_artificial_var
= 1;
4212 var_integer
->size
= ~0;
4213 var_integer
->fullsize
= ~0;
4214 var_integer
->offset
= 0;
4215 var_integer
->next
= NULL
;
4216 var_integer
->is_special_var
= 1;
4218 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4220 /* INTEGER = ANYTHING, because we don't know where a dereference of
4221 a random integer will point to. */
4223 lhs
.var
= integer_id
;
4225 rhs
.type
= INCLUDES
;
4226 rhs
.var
= anything_id
;
4228 process_constraint (new_constraint (lhs
, rhs
));
4231 /* Initialize things necessary to perform PTA */
4234 init_alias_vars (void)
4236 bitmap_obstack_initialize (&ptabitmap_obstack
);
4237 bitmap_obstack_initialize (&predbitmap_obstack
);
4239 constraint_pool
= create_alloc_pool ("Constraint pool",
4240 sizeof (struct constraint
), 30);
4241 variable_info_pool
= create_alloc_pool ("Variable info pool",
4242 sizeof (struct variable_info
), 30);
4243 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4244 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4245 id_for_tree
= htab_create (10, tree_id_hash
, tree_id_eq
, free
);
4246 memset (&stats
, 0, sizeof (stats
));
4251 /* Create points-to sets for the current function. See the comments
4252 at the start of the file for an algorithmic overview. */
4255 compute_points_to_sets (struct alias_info
*ai
)
4259 timevar_push (TV_TREE_PTA
);
4263 intra_create_variable_infos ();
4265 /* Now walk all statements and derive aliases. */
4268 block_stmt_iterator bsi
;
4271 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4273 if (is_gimple_reg (PHI_RESULT (phi
)))
4275 find_func_aliases (phi
);
4276 /* Update various related attributes like escaped
4277 addresses, pointer dereferences for loads and stores.
4278 This is used when creating name tags and alias
4280 update_alias_info (phi
, ai
);
4284 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4286 tree stmt
= bsi_stmt (bsi
);
4288 find_func_aliases (stmt
);
4289 /* Update various related attributes like escaped
4290 addresses, pointer dereferences for loads and stores.
4291 This is used when creating name tags and alias
4293 update_alias_info (stmt
, ai
);
4297 build_constraint_graph ();
4301 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4302 dump_constraints (dump_file
);
4307 "\nCollapsing static cycles and doing variable "
4310 find_and_collapse_graph_cycles (graph
, false);
4311 perform_var_substitution (graph
);
4314 fprintf (dump_file
, "\nSolving graph:\n");
4316 solve_graph (graph
);
4319 dump_sa_points_to_info (dump_file
);
4321 have_alias_info
= true;
4323 timevar_pop (TV_TREE_PTA
);
4327 /* Delete created points-to sets. */
4330 delete_points_to_sets (void)
4335 htab_delete (id_for_tree
);
4336 bitmap_obstack_release (&ptabitmap_obstack
);
4337 bitmap_obstack_release (&predbitmap_obstack
);
4338 VEC_free (constraint_t
, heap
, constraints
);
4340 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4341 VEC_free (constraint_t
, heap
, v
->complex);
4343 free (graph
->preds
);
4344 free (graph
->succs
);
4347 VEC_free (varinfo_t
, heap
, varmap
);
4348 free_alloc_pool (variable_info_pool
);
4349 free_alloc_pool (constraint_pool
);
4350 have_alias_info
= false;
4353 /* Return true if we should execute IPA PTA. */
4357 return (flag_unit_at_a_time
!= 0
4359 /* Don't bother doing anything if the program has errors. */
4360 && !(errorcount
|| sorrycount
));
4363 /* Execute the driver for IPA PTA. */
4365 ipa_pta_execute (void)
4367 struct cgraph_node
*node
;
4369 init_alias_heapvars ();
4372 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4374 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
4378 varid
= create_function_info_for (node
->decl
,
4379 cgraph_node_name (node
));
4380 if (node
->local
.externally_visible
)
4382 varinfo_t fi
= get_varinfo (varid
);
4383 for (; fi
; fi
= fi
->next
)
4384 make_constraint_from_anything (fi
);
4388 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4390 if (node
->analyzed
&& cgraph_is_master_clone (node
))
4392 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
4394 tree old_func_decl
= current_function_decl
;
4397 "Generating constraints for %s\n",
4398 cgraph_node_name (node
));
4400 current_function_decl
= node
->decl
;
4402 FOR_EACH_BB_FN (bb
, cfun
)
4404 block_stmt_iterator bsi
;
4407 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4409 if (is_gimple_reg (PHI_RESULT (phi
)))
4411 find_func_aliases (phi
);
4415 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4417 tree stmt
= bsi_stmt (bsi
);
4418 find_func_aliases (stmt
);
4421 current_function_decl
= old_func_decl
;
4426 /* Make point to anything. */
4430 build_constraint_graph ();
4434 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4435 dump_constraints (dump_file
);
4440 "\nCollapsing static cycles and doing variable "
4443 find_and_collapse_graph_cycles (graph
, false);
4444 perform_var_substitution (graph
);
4447 fprintf (dump_file
, "\nSolving graph:\n");
4449 solve_graph (graph
);
4452 dump_sa_points_to_info (dump_file
);
4455 delete_alias_heapvars ();
4456 delete_points_to_sets ();
4460 struct tree_opt_pass pass_ipa_pta
=
4463 gate_ipa_pta
, /* gate */
4464 ipa_pta_execute
, /* execute */
4467 0, /* static_pass_number */
4468 TV_IPA_PTA
, /* tv_id */
4469 0, /* properties_required */
4470 0, /* properties_provided */
4471 0, /* properties_destroyed */
4472 0, /* todo_flags_start */
4473 0, /* todo_flags_finish */
4477 /* Initialize the heapvar for statement mapping. */
4479 init_alias_heapvars (void)
4481 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
,
4486 delete_alias_heapvars (void)
4488 htab_delete (heapvar_for_stmt
);
4492 #include "gt-tree-ssa-structalias.h"