1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
43 #include "tree-gimple.h"
47 #include "tree-pass.h"
49 #include "alloc-pool.h"
50 #include "splay-tree.h"
52 #include "tree-ssa-structalias.h"
55 /* The idea behind this analyzer is to generate set constraints from the
56 program, then solve the resulting constraints in order to generate the
59 Set constraints are a way of modeling program analysis problems that
60 involve sets. They consist of an inclusion constraint language,
61 describing the variables (each variable is a set) and operations that
62 are involved on the variables, and a set of rules that derive facts
63 from these operations. To solve a system of set constraints, you derive
64 all possible facts under the rules, which gives you the correct sets
67 See "Efficient Field-sensitive pointer analysis for C" by "David
68 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
69 http://citeseer.ist.psu.edu/pearce04efficient.html
71 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
72 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
73 http://citeseer.ist.psu.edu/heintze01ultrafast.html
75 There are three types of constraint expressions, DEREF, ADDRESSOF, and
76 SCALAR. Each constraint expression consists of a constraint type,
77 a variable, and an offset.
79 SCALAR is a constraint expression type used to represent x, whether
80 it appears on the LHS or the RHS of a statement.
81 DEREF is a constraint expression type used to represent *x, whether
82 it appears on the LHS or the RHS of a statement.
83 ADDRESSOF is a constraint expression used to represent &x, whether
84 it appears on the LHS or the RHS of a statement.
86 Each pointer variable in the program is assigned an integer id, and
87 each field of a structure variable is assigned an integer id as well.
89 Structure variables are linked to their list of fields through a "next
90 field" in each variable that points to the next field in offset
92 Each variable for a structure field has
94 1. "size", that tells the size in bits of that field.
95 2. "fullsize, that tells the size in bits of the entire structure.
96 3. "offset", that tells the offset in bits from the beginning of the
97 structure to this field.
109 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
110 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
111 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
114 In order to solve the system of set constraints, the following is
117 1. Each constraint variable x has a solution set associated with it,
120 2. Constraints are separated into direct, copy, and complex.
121 Direct constraints are ADDRESSOF constraints that require no extra
122 processing, such as P = &Q
123 Copy constraints are those of the form P = Q.
124 Complex constraints are all the constraints involving dereferences.
126 3. All direct constraints of the form P = &Q are processed, such
127 that Q is added to Sol(P)
129 4. All complex constraints for a given constraint variable are stored in a
130 linked list attached to that variable's node.
132 5. A directed graph is built out of the copy constraints. Each
133 constraint variable is a node in the graph, and an edge from
134 Q to P is added for each copy constraint of the form P = Q
136 6. The graph is then walked, and solution sets are
137 propagated along the copy edges, such that an edge from Q to P
138 causes Sol(P) <- Sol(P) union Sol(Q).
140 7. As we visit each node, all complex constraints associated with
141 that node are processed by adding appropriate copy edges to the graph, or the
142 appropriate variables to the solution set.
144 8. The process of walking the graph is iterated until no solution
147 Prior to walking the graph in steps 6 and 7, We perform static
148 cycle elimination on the constraint graph, as well
149 as off-line variable substitution.
151 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
152 on and turned into anything), but isn't. You can just see what offset
153 inside the pointed-to struct it's going to access.
155 TODO: Constant bounded arrays can be handled as if they were structs of the
156 same number of elements.
158 TODO: Modeling heap and incoming pointers becomes much better if we
159 add fields to them as we discover them, which we could do.
161 TODO: We could handle unions, but to be honest, it's probably not
162 worth the pain or slowdown. */
164 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map
)))
165 htab_t heapvar_for_stmt
;
167 /* One variable to represent all non-local accesses. */
170 static bool use_field_sensitive
= true;
171 static int in_ipa_mode
= 0;
172 static bitmap_obstack predbitmap_obstack
;
173 static bitmap_obstack ptabitmap_obstack
;
174 static bitmap_obstack iteration_obstack
;
176 static unsigned int create_variable_info_for (tree
, const char *);
177 static void build_constraint_graph (void);
179 DEF_VEC_P(constraint_t
);
180 DEF_VEC_ALLOC_P(constraint_t
,heap
);
182 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
184 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
186 static struct constraint_stats
188 unsigned int total_vars
;
189 unsigned int collapsed_vars
;
190 unsigned int unified_vars_static
;
191 unsigned int unified_vars_dynamic
;
192 unsigned int iterations
;
193 unsigned int num_edges
;
198 /* ID of this variable */
201 /* Name of this variable */
204 /* Tree that this variable is associated with. */
207 /* Offset of this variable, in bits, from the base variable */
208 unsigned HOST_WIDE_INT offset
;
210 /* Size of the variable, in bits. */
211 unsigned HOST_WIDE_INT size
;
213 /* Full size of the base variable, in bits. */
214 unsigned HOST_WIDE_INT fullsize
;
216 /* A link to the variable for the next field in this structure. */
217 struct variable_info
*next
;
219 /* Node in the graph that represents the constraints and points-to
220 solution for the variable. */
223 /* True if the address of this variable is taken. Needed for
224 variable substitution. */
225 unsigned int address_taken
:1;
227 /* True if this variable is the target of a dereference. Needed for
228 variable substitution. */
229 unsigned int indirect_target
:1;
231 /* True if the variable is directly the target of a dereference.
232 This is used to track which variables are *actually* dereferenced
233 so we can prune their points to listed. This is equivalent to the
234 indirect_target flag when no merging of variables happens. */
235 unsigned int directly_dereferenced
:1;
237 /* True if this is a variable created by the constraint analysis, such as
238 heap variables and constraints we had to break up. */
239 unsigned int is_artificial_var
:1;
241 /* True if this is a special variable whose solution set should not be
243 unsigned int is_special_var
:1;
245 /* True for variables whose size is not known or variable. */
246 unsigned int is_unknown_size_var
:1;
248 /* True for variables that have unions somewhere in them. */
249 unsigned int has_union
:1;
251 /* True if this is a heap variable. */
252 unsigned int is_heap_var
:1;
254 /* Points-to set for this variable. */
257 /* Variable ids represented by this node. */
260 /* Vector of complex constraints for this node. Complex
261 constraints are those involving dereferences. */
262 VEC(constraint_t
,heap
) *complex;
264 /* Variable id this was collapsed to due to type unsafety.
265 This should be unused completely after build_constraint_graph, or
266 something is broken. */
267 struct variable_info
*collapsed_to
;
269 typedef struct variable_info
*varinfo_t
;
271 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
273 /* Pool of variable info structures. */
274 static alloc_pool variable_info_pool
;
276 DEF_VEC_P(varinfo_t
);
278 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
280 /* Table of variable info structures for constraint variables. Indexed directly
281 by variable info id. */
282 static VEC(varinfo_t
,heap
) *varmap
;
284 /* Return the varmap element N */
286 static inline varinfo_t
287 get_varinfo (unsigned int n
)
289 return VEC_index(varinfo_t
, varmap
, n
);
292 /* Return the varmap element N, following the collapsed_to link. */
294 static inline varinfo_t
295 get_varinfo_fc (unsigned int n
)
297 varinfo_t v
= VEC_index(varinfo_t
, varmap
, n
);
300 return v
->collapsed_to
;
304 /* Variable that represents the unknown pointer. */
305 static varinfo_t var_anything
;
306 static tree anything_tree
;
307 static unsigned int anything_id
;
309 /* Variable that represents the NULL pointer. */
310 static varinfo_t var_nothing
;
311 static tree nothing_tree
;
312 static unsigned int nothing_id
;
314 /* Variable that represents read only memory. */
315 static varinfo_t var_readonly
;
316 static tree readonly_tree
;
317 static unsigned int readonly_id
;
319 /* Variable that represents integers. This is used for when people do things
321 static varinfo_t var_integer
;
322 static tree integer_tree
;
323 static unsigned int integer_id
;
325 /* Variable that represents escaped variables. This is used to give
326 incoming pointer variables a better set than ANYTHING. */
327 static varinfo_t var_escaped_vars
;
328 static tree escaped_vars_tree
;
329 static unsigned int escaped_vars_id
;
331 /* Variable that represents non-local variables before we expand it to
332 one for each type. */
333 static unsigned int nonlocal_vars_id
;
335 /* Lookup a heap var for FROM, and return it if we find one. */
338 heapvar_lookup (tree from
)
340 struct tree_map
*h
, in
;
343 h
= htab_find_with_hash (heapvar_for_stmt
, &in
, htab_hash_pointer (from
));
349 /* Insert a mapping FROM->TO in the heap var for statement
353 heapvar_insert (tree from
, tree to
)
358 h
= ggc_alloc (sizeof (struct tree_map
));
359 h
->hash
= htab_hash_pointer (from
);
362 loc
= htab_find_slot_with_hash (heapvar_for_stmt
, h
, h
->hash
, INSERT
);
363 *(struct tree_map
**) loc
= h
;
366 /* Return a new variable info structure consisting for a variable
367 named NAME, and using constraint graph node NODE. */
370 new_var_info (tree t
, unsigned int id
, const char *name
, unsigned int node
)
372 varinfo_t ret
= pool_alloc (variable_info_pool
);
378 ret
->address_taken
= false;
379 ret
->indirect_target
= false;
380 ret
->directly_dereferenced
= false;
381 ret
->is_artificial_var
= false;
382 ret
->is_heap_var
= false;
383 ret
->is_special_var
= false;
384 ret
->is_unknown_size_var
= false;
385 ret
->has_union
= false;
386 ret
->solution
= BITMAP_ALLOC (&ptabitmap_obstack
);
387 ret
->variables
= BITMAP_ALLOC (&ptabitmap_obstack
);
390 ret
->collapsed_to
= NULL
;
394 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
396 /* An expression that appears in a constraint. */
398 struct constraint_expr
400 /* Constraint type. */
401 constraint_expr_type type
;
403 /* Variable we are referring to in the constraint. */
406 /* Offset, in bits, of this constraint from the beginning of
407 variables it ends up referring to.
409 IOW, in a deref constraint, we would deref, get the result set,
410 then add OFFSET to each member. */
411 unsigned HOST_WIDE_INT offset
;
414 typedef struct constraint_expr ce_s
;
416 DEF_VEC_ALLOC_O(ce_s
, heap
);
417 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
418 static void do_deref (VEC (ce_s
, heap
) **);
420 /* Our set constraints are made up of two constraint expressions, one
423 As described in the introduction, our set constraints each represent an
424 operation between set valued variables.
428 struct constraint_expr lhs
;
429 struct constraint_expr rhs
;
432 /* List of constraints that we use to build the constraint graph from. */
434 static VEC(constraint_t
,heap
) *constraints
;
435 static alloc_pool constraint_pool
;
437 /* An edge in the weighted constraint graph. The edges are weighted,
438 with a bit set in weights meaning their is an edge with that
440 We don't keep the src in the edge, because we always know what it
443 struct constraint_edge
449 typedef struct constraint_edge
*constraint_edge_t
;
450 static alloc_pool constraint_edge_pool
;
452 /* Return a new constraint edge from SRC to DEST. */
454 static constraint_edge_t
455 new_constraint_edge (unsigned int dest
)
457 constraint_edge_t ret
= pool_alloc (constraint_edge_pool
);
463 DEF_VEC_P(constraint_edge_t
);
464 DEF_VEC_ALLOC_P(constraint_edge_t
,heap
);
467 /* The constraint graph is represented internally in two different
468 ways. The overwhelming majority of edges in the constraint graph
469 are zero weigh edges, and thus, using a vector of contrainst_edge_t
470 is a waste of time and memory, since they have no weights. We
471 simply use a bitmap to store the preds and succs for each node.
472 The weighted edges are stored as a set of adjacency vectors, one
473 per variable. succs[x] is the vector of successors for variable x,
474 and preds[x] is the vector of predecessors for variable x. IOW,
475 all edges are "forward" edges, which is not like our CFG. So
476 remember that preds[x]->src == x, and succs[x]->src == x. */
478 struct constraint_graph
480 bitmap
*zero_weight_succs
;
481 bitmap
*zero_weight_preds
;
482 VEC(constraint_edge_t
,heap
) **succs
;
483 VEC(constraint_edge_t
,heap
) **preds
;
486 typedef struct constraint_graph
*constraint_graph_t
;
488 static constraint_graph_t graph
;
489 static int graph_size
;
491 /* Create a new constraint consisting of LHS and RHS expressions. */
494 new_constraint (const struct constraint_expr lhs
,
495 const struct constraint_expr rhs
)
497 constraint_t ret
= pool_alloc (constraint_pool
);
503 /* Print out constraint C to FILE. */
506 dump_constraint (FILE *file
, constraint_t c
)
508 if (c
->lhs
.type
== ADDRESSOF
)
510 else if (c
->lhs
.type
== DEREF
)
512 fprintf (file
, "%s", get_varinfo_fc (c
->lhs
.var
)->name
);
513 if (c
->lhs
.offset
!= 0)
514 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
515 fprintf (file
, " = ");
516 if (c
->rhs
.type
== ADDRESSOF
)
518 else if (c
->rhs
.type
== DEREF
)
520 fprintf (file
, "%s", get_varinfo_fc (c
->rhs
.var
)->name
);
521 if (c
->rhs
.offset
!= 0)
522 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
523 fprintf (file
, "\n");
526 /* Print out constraint C to stderr. */
529 debug_constraint (constraint_t c
)
531 dump_constraint (stderr
, c
);
534 /* Print out all constraints to FILE */
537 dump_constraints (FILE *file
)
541 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
542 dump_constraint (file
, c
);
545 /* Print out all constraints to stderr. */
548 debug_constraints (void)
550 dump_constraints (stderr
);
555 The solver is a simple worklist solver, that works on the following
558 sbitmap changed_nodes = all ones;
559 changed_count = number of nodes;
560 For each node that was already collapsed:
563 while (changed_count > 0)
565 compute topological ordering for constraint graph
567 find and collapse cycles in the constraint graph (updating
568 changed if necessary)
570 for each node (n) in the graph in topological order:
573 Process each complex constraint associated with the node,
574 updating changed if necessary.
576 For each outgoing edge from n, propagate the solution from n to
577 the destination of the edge, updating changed as necessary.
581 /* Return true if two constraint expressions A and B are equal. */
584 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
586 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
589 /* Return true if constraint expression A is less than constraint expression
590 B. This is just arbitrary, but consistent, in order to give them an
594 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
596 if (a
.type
== b
.type
)
599 return a
.offset
< b
.offset
;
601 return a
.var
< b
.var
;
604 return a
.type
< b
.type
;
607 /* Return true if constraint A is less than constraint B. This is just
608 arbitrary, but consistent, in order to give them an ordering. */
611 constraint_less (const constraint_t a
, const constraint_t b
)
613 if (constraint_expr_less (a
->lhs
, b
->lhs
))
615 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
618 return constraint_expr_less (a
->rhs
, b
->rhs
);
621 /* Return true if two constraints A and B are equal. */
624 constraint_equal (struct constraint a
, struct constraint b
)
626 return constraint_expr_equal (a
.lhs
, b
.lhs
)
627 && constraint_expr_equal (a
.rhs
, b
.rhs
);
631 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
634 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
635 struct constraint lookfor
)
643 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
644 if (place
>= VEC_length (constraint_t
, vec
))
646 found
= VEC_index (constraint_t
, vec
, place
);
647 if (!constraint_equal (*found
, lookfor
))
652 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
655 constraint_set_union (VEC(constraint_t
,heap
) **to
,
656 VEC(constraint_t
,heap
) **from
)
661 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
663 if (constraint_vec_find (*to
, *c
) == NULL
)
665 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
667 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
672 /* Take a solution set SET, add OFFSET to each member of the set, and
673 overwrite SET with the result when done. */
676 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
678 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
682 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
684 /* If this is a properly sized variable, only add offset if it's
685 less than end. Otherwise, it is globbed to a single
688 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
690 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
691 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
694 bitmap_set_bit (result
, v
->id
);
696 else if (get_varinfo (i
)->is_artificial_var
697 || get_varinfo (i
)->has_union
698 || get_varinfo (i
)->is_unknown_size_var
)
700 bitmap_set_bit (result
, i
);
704 bitmap_copy (set
, result
);
705 BITMAP_FREE (result
);
708 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
712 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
715 return bitmap_ior_into (to
, from
);
721 tmp
= BITMAP_ALLOC (&iteration_obstack
);
722 bitmap_copy (tmp
, from
);
723 solution_set_add (tmp
, inc
);
724 res
= bitmap_ior_into (to
, tmp
);
730 /* Insert constraint C into the list of complex constraints for VAR. */
733 insert_into_complex (unsigned int var
, constraint_t c
)
735 varinfo_t vi
= get_varinfo (var
);
736 unsigned int place
= VEC_lower_bound (constraint_t
, vi
->complex, c
,
738 VEC_safe_insert (constraint_t
, heap
, vi
->complex, place
, c
);
742 /* Compare two constraint edges A and B, return true if they are equal. */
745 constraint_edge_equal (struct constraint_edge a
, struct constraint_edge b
)
747 return a
.dest
== b
.dest
;
750 /* Compare two constraint edges, return true if A is less than B */
753 constraint_edge_less (const constraint_edge_t a
, const constraint_edge_t b
)
755 if (a
->dest
< b
->dest
)
760 /* Find the constraint edge that matches LOOKFOR, in VEC.
761 Return the edge, if found, NULL otherwise. */
763 static constraint_edge_t
764 constraint_edge_vec_find (VEC(constraint_edge_t
,heap
) *vec
,
765 struct constraint_edge lookfor
)
768 constraint_edge_t edge
= NULL
;
770 place
= VEC_lower_bound (constraint_edge_t
, vec
, &lookfor
,
771 constraint_edge_less
);
772 if (place
>= VEC_length (constraint_edge_t
, vec
))
774 edge
= VEC_index (constraint_edge_t
, vec
, place
);
775 if (!constraint_edge_equal (*edge
, lookfor
))
780 /* Condense two variable nodes into a single variable node, by moving
781 all associated info from SRC to TO. */
784 condense_varmap_nodes (unsigned int to
, unsigned int src
)
786 varinfo_t tovi
= get_varinfo (to
);
787 varinfo_t srcvi
= get_varinfo (src
);
792 /* the src node, and all its variables, are now the to node. */
794 EXECUTE_IF_SET_IN_BITMAP (srcvi
->variables
, 0, i
, bi
)
795 get_varinfo (i
)->node
= to
;
797 /* Merge the src node variables and the to node variables. */
798 bitmap_set_bit (tovi
->variables
, src
);
799 bitmap_ior_into (tovi
->variables
, srcvi
->variables
);
800 bitmap_clear (srcvi
->variables
);
802 /* Move all complex constraints from src node into to node */
803 for (i
= 0; VEC_iterate (constraint_t
, srcvi
->complex, i
, c
); i
++)
805 /* In complex constraints for node src, we may have either
806 a = *src, and *src = a. */
808 if (c
->rhs
.type
== DEREF
)
813 constraint_set_union (&tovi
->complex, &srcvi
->complex);
814 VEC_free (constraint_t
, heap
, srcvi
->complex);
815 srcvi
->complex = NULL
;
818 /* Erase an edge from SRC to SRC from GRAPH. This routine only
819 handles self-edges (e.g. an edge from a to a). */
822 erase_graph_self_edge (constraint_graph_t graph
, unsigned int src
)
824 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[src
];
825 VEC(constraint_edge_t
,heap
) *succvec
= graph
->succs
[src
];
826 struct constraint_edge edge
;
831 /* Remove from the successors. */
832 place
= VEC_lower_bound (constraint_edge_t
, succvec
, &edge
,
833 constraint_edge_less
);
835 /* Make sure we found the edge. */
836 #ifdef ENABLE_CHECKING
838 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, succvec
, place
);
839 gcc_assert (constraint_edge_equal (*tmp
, edge
));
842 VEC_ordered_remove (constraint_edge_t
, succvec
, place
);
844 /* Remove from the predecessors. */
845 place
= VEC_lower_bound (constraint_edge_t
, predvec
, &edge
,
846 constraint_edge_less
);
848 /* Make sure we found the edge. */
849 #ifdef ENABLE_CHECKING
851 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, predvec
, place
);
852 gcc_assert (constraint_edge_equal (*tmp
, edge
));
855 VEC_ordered_remove (constraint_edge_t
, predvec
, place
);
858 /* Remove edges involving NODE from GRAPH. */
861 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
863 VEC(constraint_edge_t
,heap
) *succvec
= graph
->succs
[node
];
864 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[node
];
867 constraint_edge_t c
= NULL
;
870 /* Walk the successors, erase the associated preds. */
872 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[node
], 0, j
, bi
)
874 bitmap_clear_bit (graph
->zero_weight_preds
[j
], node
);
876 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
880 struct constraint_edge lookfor
;
881 constraint_edge_t result
;
884 place
= VEC_lower_bound (constraint_edge_t
, graph
->preds
[c
->dest
],
885 &lookfor
, constraint_edge_less
);
886 result
= VEC_ordered_remove (constraint_edge_t
,
887 graph
->preds
[c
->dest
], place
);
888 pool_free (constraint_edge_pool
, result
);
891 /* Walk the preds, erase the associated succs. */
893 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_preds
[node
], 0, j
, bi
)
895 bitmap_clear_bit (graph
->zero_weight_succs
[j
], node
);
897 for (i
=0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
901 struct constraint_edge lookfor
;
902 constraint_edge_t result
;
905 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[c
->dest
],
906 &lookfor
, constraint_edge_less
);
907 result
= VEC_ordered_remove (constraint_edge_t
,
908 graph
->succs
[c
->dest
], place
);
909 pool_free (constraint_edge_pool
, result
);
913 if (graph
->zero_weight_preds
[node
])
915 BITMAP_FREE (graph
->zero_weight_preds
[node
]);
916 graph
->zero_weight_preds
[node
] = NULL
;
919 if (graph
->zero_weight_succs
[node
])
921 BITMAP_FREE (graph
->zero_weight_succs
[node
]);
922 graph
->zero_weight_succs
[node
] = NULL
;
925 VEC_free (constraint_edge_t
, heap
, graph
->preds
[node
]);
926 VEC_free (constraint_edge_t
, heap
, graph
->succs
[node
]);
927 graph
->preds
[node
] = NULL
;
928 graph
->succs
[node
] = NULL
;
931 static bool edge_added
= false;
933 /* Add edge (src, dest) to the graph. */
936 add_graph_edge (constraint_graph_t graph
, unsigned int src
, unsigned int dest
)
939 VEC(constraint_edge_t
,heap
) *vec
;
940 struct constraint_edge newe
;
943 vec
= graph
->preds
[src
];
944 place
= VEC_lower_bound (constraint_edge_t
, vec
, &newe
,
945 constraint_edge_less
);
946 if (place
== VEC_length (constraint_edge_t
, vec
)
947 || VEC_index (constraint_edge_t
, vec
, place
)->dest
!= dest
)
949 constraint_edge_t edge
= new_constraint_edge (dest
);
951 VEC_safe_insert (constraint_edge_t
, heap
, graph
->preds
[src
],
953 edge
= new_constraint_edge (src
);
955 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[dest
],
956 edge
, constraint_edge_less
);
957 VEC_safe_insert (constraint_edge_t
, heap
, graph
->succs
[dest
],
968 /* Return the bitmap representing the weights of edge (SRC, DEST). */
971 get_graph_weights (constraint_graph_t graph
, unsigned int src
,
974 constraint_edge_t edge
;
975 VEC(constraint_edge_t
,heap
) *vec
;
976 struct constraint_edge lookfor
;
980 vec
= graph
->preds
[src
];
981 edge
= constraint_edge_vec_find (vec
, lookfor
);
982 gcc_assert (edge
!= NULL
);
983 return &edge
->weights
;
986 /* Allocate graph weight bitmap for the edges associated with SRC and
987 DEST in GRAPH. Both the pred and the succ edges share a single
988 bitmap, so we need to set both edges to that bitmap. */
991 allocate_graph_weights (constraint_graph_t graph
, unsigned int src
,
995 constraint_edge_t edge
;
996 VEC(constraint_edge_t
,heap
) *vec
;
997 struct constraint_edge lookfor
;
999 result
= BITMAP_ALLOC (&ptabitmap_obstack
);
1001 /* Set the pred weight. */
1002 lookfor
.dest
= dest
;
1003 vec
= graph
->preds
[src
];
1004 edge
= constraint_edge_vec_find (vec
, lookfor
);
1005 gcc_assert (edge
!= NULL
);
1006 edge
->weights
= result
;
1008 /* Set the succ weight. */
1010 vec
= graph
->succs
[dest
];
1011 edge
= constraint_edge_vec_find (vec
, lookfor
);
1012 gcc_assert (edge
!= NULL
);
1013 edge
->weights
= result
;
1019 /* Merge GRAPH nodes FROM and TO into node TO. */
1022 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1025 VEC(constraint_edge_t
,heap
) *succvec
= graph
->succs
[from
];
1026 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[from
];
1028 constraint_edge_t c
;
1032 /* Merge all the zero weighted predecessor edges. */
1033 if (graph
->zero_weight_preds
[from
])
1035 if (!graph
->zero_weight_preds
[to
])
1036 graph
->zero_weight_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1038 EXECUTE_IF_SET_IN_BITMAP (graph
->zero_weight_preds
[from
], 0, j
, bi
)
1042 bitmap_clear_bit (graph
->zero_weight_succs
[j
], from
);
1043 bitmap_set_bit (graph
->zero_weight_succs
[j
], to
);
1046 bitmap_ior_into (graph
->zero_weight_preds
[to
],
1047 graph
->zero_weight_preds
[from
]);
1050 /* Merge all the zero weighted successor edges. */
1051 if (graph
->zero_weight_succs
[from
])
1053 if (!graph
->zero_weight_succs
[to
])
1054 graph
->zero_weight_succs
[to
] = BITMAP_ALLOC (&ptabitmap_obstack
);
1055 EXECUTE_IF_SET_IN_BITMAP (graph
->zero_weight_succs
[from
], 0, j
, bi
)
1057 bitmap_clear_bit (graph
->zero_weight_preds
[j
], from
);
1058 bitmap_set_bit (graph
->zero_weight_preds
[j
], to
);
1060 bitmap_ior_into (graph
->zero_weight_succs
[to
],
1061 graph
->zero_weight_succs
[from
]);
1064 /* Merge all the nonzero weighted predecessor edges. */
1065 for (i
= 0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
1067 unsigned int d
= c
->dest
;
1071 if (c
->dest
== from
)
1074 add_graph_edge (graph
, to
, d
);
1076 temp
= *(get_graph_weights (graph
, from
, c
->dest
));
1079 weights
= get_graph_weights (graph
, to
, d
);
1081 *weights
= allocate_graph_weights (graph
, to
, d
);
1083 bitmap_ior_into (*weights
, temp
);
1088 /* Merge all the nonzero weighted successor edges. */
1089 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
1091 unsigned int d
= c
->dest
;
1095 if (c
->dest
== from
)
1098 add_graph_edge (graph
, d
, to
);
1100 temp
= *(get_graph_weights (graph
, c
->dest
, from
));
1103 weights
= get_graph_weights (graph
, d
, to
);
1105 *weights
= allocate_graph_weights (graph
, d
, to
);
1106 bitmap_ior_into (*weights
, temp
);
1109 clear_edges_for_node (graph
, from
);
1112 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
1113 it doesn't exist in the graph already.
1114 Return false if the edge already existed, true otherwise. */
1117 int_add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1118 unsigned int from
, unsigned HOST_WIDE_INT weight
)
1120 if (to
== from
&& weight
== 0)
1130 if (!graph
->zero_weight_preds
[to
])
1131 graph
->zero_weight_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1132 if (!graph
->zero_weight_succs
[from
])
1133 graph
->zero_weight_succs
[from
] = BITMAP_ALLOC (&ptabitmap_obstack
);
1134 if (!bitmap_bit_p (graph
->zero_weight_succs
[from
], to
))
1139 bitmap_set_bit (graph
->zero_weight_preds
[to
], from
);
1140 bitmap_set_bit (graph
->zero_weight_succs
[from
], to
);
1147 r
= add_graph_edge (graph
, to
, from
);
1148 weights
= get_graph_weights (graph
, to
, from
);
1153 *weights
= allocate_graph_weights (graph
, to
, from
);
1154 bitmap_set_bit (*weights
, weight
);
1158 r
|= !bitmap_bit_p (*weights
, weight
);
1159 bitmap_set_bit (*weights
, weight
);
1168 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1171 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
1174 struct constraint_edge lookfor
;
1177 return (graph
->zero_weight_succs
[dest
]
1178 && bitmap_bit_p (graph
->zero_weight_succs
[dest
], src
))
1179 || constraint_edge_vec_find (graph
->succs
[dest
], lookfor
) != NULL
;
1182 /* Return true if {DEST, SRC} is an existing weighted graph edge (IE has
1183 a weight other than 0) in GRAPH. */
1185 valid_weighted_graph_edge (constraint_graph_t graph
, unsigned int src
,
1188 struct constraint_edge lookfor
;
1191 return graph
->preds
[src
]
1192 && constraint_edge_vec_find (graph
->succs
[dest
], lookfor
) != NULL
;
1196 /* Build the constraint graph. */
1199 build_constraint_graph (void)
1204 graph
= XNEW (struct constraint_graph
);
1205 graph_size
= VEC_length (varinfo_t
, varmap
) + 1;
1206 graph
->succs
= XCNEWVEC (VEC(constraint_edge_t
,heap
) *, graph_size
);
1207 graph
->preds
= XCNEWVEC (VEC(constraint_edge_t
,heap
) *, graph_size
);
1208 graph
->zero_weight_succs
= XCNEWVEC (bitmap
, graph_size
);
1209 graph
->zero_weight_preds
= XCNEWVEC (bitmap
, graph_size
);
1211 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1213 struct constraint_expr lhs
= c
->lhs
;
1214 struct constraint_expr rhs
= c
->rhs
;
1215 unsigned int lhsvar
= get_varinfo_fc (lhs
.var
)->id
;
1216 unsigned int rhsvar
= get_varinfo_fc (rhs
.var
)->id
;
1218 if (lhs
.type
== DEREF
)
1220 /* *x = y or *x = &y (complex) */
1221 if (rhs
.type
== ADDRESSOF
|| rhsvar
> anything_id
)
1222 insert_into_complex (lhsvar
, c
);
1224 else if (rhs
.type
== DEREF
)
1226 /* !special var= *y */
1227 if (!(get_varinfo (lhsvar
)->is_special_var
))
1228 insert_into_complex (rhsvar
, c
);
1230 else if (rhs
.type
== ADDRESSOF
)
1233 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1235 else if (lhsvar
> anything_id
)
1237 /* Ignore 0 weighted self edges, as they can't possibly contribute
1239 if (lhsvar
!= rhsvar
|| rhs
.offset
!= 0 || lhs
.offset
!= 0)
1241 /* x = y (simple) */
1242 int_add_graph_edge (graph
, lhs
.var
, rhs
.var
, rhs
.offset
);
1250 /* Changed variables on the last iteration. */
1251 static unsigned int changed_count
;
1252 static sbitmap changed
;
1254 DEF_VEC_I(unsigned);
1255 DEF_VEC_ALLOC_I(unsigned,heap
);
1258 /* Strongly Connected Component visitation info. */
1263 sbitmap in_component
;
1265 unsigned int *visited_index
;
1266 VEC(unsigned,heap
) *scc_stack
;
1267 VEC(unsigned,heap
) *unification_queue
;
1271 /* Recursive routine to find strongly connected components in GRAPH.
1272 SI is the SCC info to store the information in, and N is the id of current
1273 graph node we are processing.
1275 This is Tarjan's strongly connected component finding algorithm, as
1276 modified by Nuutila to keep only non-root nodes on the stack.
1277 The algorithm can be found in "On finding the strongly connected
1278 connected components in a directed graph" by Esko Nuutila and Eljas
1279 Soisalon-Soininen, in Information Processing Letters volume 49,
1280 number 1, pages 9-14. */
1283 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1288 gcc_assert (get_varinfo (n
)->node
== n
);
1289 SET_BIT (si
->visited
, n
);
1290 RESET_BIT (si
->in_component
, n
);
1291 si
->visited_index
[n
] = si
->current_index
++;
1293 /* Visit all the successors. */
1294 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[n
], 0, i
, bi
)
1297 if (!TEST_BIT (si
->visited
, w
))
1298 scc_visit (graph
, si
, w
);
1299 if (!TEST_BIT (si
->in_component
, w
))
1301 unsigned int t
= get_varinfo (w
)->node
;
1302 unsigned int nnode
= get_varinfo (n
)->node
;
1303 if (si
->visited_index
[t
] < si
->visited_index
[nnode
])
1304 get_varinfo (n
)->node
= t
;
1308 /* See if any components have been identified. */
1309 if (get_varinfo (n
)->node
== n
)
1311 unsigned int t
= si
->visited_index
[n
];
1312 SET_BIT (si
->in_component
, n
);
1313 while (VEC_length (unsigned, si
->scc_stack
) != 0
1314 && t
< si
->visited_index
[VEC_last (unsigned, si
->scc_stack
)])
1316 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1317 get_varinfo (w
)->node
= n
;
1318 SET_BIT (si
->in_component
, w
);
1319 /* Mark this node for collapsing. */
1320 VEC_safe_push (unsigned, heap
, si
->unification_queue
, w
);
1324 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1328 /* Collapse two variables into one variable. */
1331 collapse_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
)
1333 bitmap tosol
, fromsol
;
1335 condense_varmap_nodes (to
, from
);
1336 tosol
= get_varinfo (to
)->solution
;
1337 fromsol
= get_varinfo (from
)->solution
;
1338 bitmap_ior_into (tosol
, fromsol
);
1339 merge_graph_nodes (graph
, to
, from
);
1341 if (valid_graph_edge (graph
, to
, to
))
1343 if (graph
->zero_weight_preds
[to
])
1345 bitmap_clear_bit (graph
->zero_weight_preds
[to
], to
);
1346 bitmap_clear_bit (graph
->zero_weight_succs
[to
], to
);
1348 if (valid_weighted_graph_edge (graph
, to
, to
))
1350 bitmap weights
= *(get_graph_weights (graph
, to
, to
));
1351 if (!weights
|| bitmap_empty_p (weights
))
1352 erase_graph_self_edge (graph
, to
);
1355 BITMAP_FREE (fromsol
);
1356 get_varinfo (to
)->address_taken
|= get_varinfo (from
)->address_taken
;
1357 get_varinfo (to
)->indirect_target
|= get_varinfo (from
)->indirect_target
;
1361 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1362 SI is the Strongly Connected Components information structure that tells us
1363 what components to unify.
1364 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1365 count should be updated to reflect the unification. */
1368 process_unification_queue (constraint_graph_t graph
, struct scc_info
*si
,
1369 bool update_changed
)
1372 bitmap tmp
= BITMAP_ALLOC (update_changed
? &iteration_obstack
: NULL
);
1375 /* We proceed as follows:
1377 For each component in the queue (components are delineated by
1378 when current_queue_element->node != next_queue_element->node):
1380 rep = representative node for component
1382 For each node (tounify) to be unified in the component,
1383 merge the solution for tounify into tmp bitmap
1385 clear solution for tounify
1387 merge edges from tounify into rep
1389 merge complex constraints from tounify into rep
1391 update changed count to note that tounify will never change
1394 Merge tmp into solution for rep, marking rep changed if this
1395 changed rep's solution.
1397 Delete any 0 weighted self-edges we now have for rep. */
1398 while (i
!= VEC_length (unsigned, si
->unification_queue
))
1400 unsigned int tounify
= VEC_index (unsigned, si
->unification_queue
, i
);
1401 unsigned int n
= get_varinfo (tounify
)->node
;
1403 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1404 fprintf (dump_file
, "Unifying %s to %s\n",
1405 get_varinfo (tounify
)->name
,
1406 get_varinfo (n
)->name
);
1408 stats
.unified_vars_dynamic
++;
1410 stats
.unified_vars_static
++;
1411 bitmap_ior_into (tmp
, get_varinfo (tounify
)->solution
);
1412 merge_graph_nodes (graph
, n
, tounify
);
1413 condense_varmap_nodes (n
, tounify
);
1415 if (update_changed
&& TEST_BIT (changed
, tounify
))
1417 RESET_BIT (changed
, tounify
);
1418 if (!TEST_BIT (changed
, n
))
1419 SET_BIT (changed
, n
);
1422 gcc_assert (changed_count
> 0);
1427 bitmap_clear (get_varinfo (tounify
)->solution
);
1430 /* If we've either finished processing the entire queue, or
1431 finished processing all nodes for component n, update the solution for
1433 if (i
== VEC_length (unsigned, si
->unification_queue
)
1434 || get_varinfo (VEC_index (unsigned, si
->unification_queue
, i
))->node
!= n
)
1436 /* If the solution changes because of the merging, we need to mark
1437 the variable as changed. */
1438 if (bitmap_ior_into (get_varinfo (n
)->solution
, tmp
))
1440 if (update_changed
&& !TEST_BIT (changed
, n
))
1442 SET_BIT (changed
, n
);
1448 if (valid_graph_edge (graph
, n
, n
))
1450 if (graph
->zero_weight_succs
[n
])
1452 if (graph
->zero_weight_preds
[n
])
1453 bitmap_clear_bit (graph
->zero_weight_preds
[n
], n
);
1454 bitmap_clear_bit (graph
->zero_weight_succs
[n
], n
);
1456 if (valid_weighted_graph_edge (graph
, n
, n
))
1458 bitmap weights
= *(get_graph_weights (graph
, n
, n
));
1459 if (!weights
|| bitmap_empty_p (weights
))
1460 erase_graph_self_edge (graph
, n
);
1469 /* Information needed to compute the topological ordering of a graph. */
1473 /* sbitmap of visited nodes. */
1475 /* Array that stores the topological order of the graph, *in
1477 VEC(unsigned,heap
) *topo_order
;
1481 /* Initialize and return a topological info structure. */
1483 static struct topo_info
*
1484 init_topo_info (void)
1486 size_t size
= VEC_length (varinfo_t
, varmap
);
1487 struct topo_info
*ti
= XNEW (struct topo_info
);
1488 ti
->visited
= sbitmap_alloc (size
);
1489 sbitmap_zero (ti
->visited
);
1490 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1495 /* Free the topological sort info pointed to by TI. */
1498 free_topo_info (struct topo_info
*ti
)
1500 sbitmap_free (ti
->visited
);
1501 VEC_free (unsigned, heap
, ti
->topo_order
);
1505 /* Visit the graph in topological order, and store the order in the
1506 topo_info structure. */
1509 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1512 VEC(constraint_edge_t
,heap
) *succs
= graph
->succs
[n
];
1515 constraint_edge_t c
;
1519 SET_BIT (ti
->visited
, n
);
1520 if (VEC_length (constraint_edge_t
, succs
) != 0)
1522 temp
= BITMAP_ALLOC (&iteration_obstack
);
1523 if (graph
->zero_weight_succs
[n
])
1524 bitmap_ior_into (temp
, graph
->zero_weight_succs
[n
]);
1525 for (i
= 0; VEC_iterate (constraint_edge_t
, succs
, i
, c
); i
++)
1526 bitmap_set_bit (temp
, c
->dest
);
1529 temp
= graph
->zero_weight_succs
[n
];
1532 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, j
, bi
)
1534 if (!TEST_BIT (ti
->visited
, j
))
1535 topo_visit (graph
, ti
, j
);
1537 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1540 /* Return true if variable N + OFFSET is a legal field of N. */
1543 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1545 varinfo_t ninfo
= get_varinfo (n
);
1547 /* For things we've globbed to single variables, any offset into the
1548 variable acts like the entire variable, so that it becomes offset
1550 if (ninfo
->is_special_var
1551 || ninfo
->is_artificial_var
1552 || ninfo
->is_unknown_size_var
)
1557 return (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1560 /* Process a constraint C that represents *x = &y. */
1563 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1564 constraint_t c
, bitmap delta
)
1566 unsigned int rhs
= c
->rhs
.var
;
1570 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1571 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1573 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1574 if (type_safe (j
, &offset
) && !(get_varinfo (j
)->is_special_var
))
1576 /* *x != NULL && *x != ANYTHING*/
1580 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1582 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1586 sol
= get_varinfo (t
)->solution
;
1587 if (!bitmap_bit_p (sol
, rhs
))
1589 bitmap_set_bit (sol
, rhs
);
1590 if (!TEST_BIT (changed
, t
))
1592 SET_BIT (changed
, t
);
1597 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1598 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1603 /* Process a constraint C that represents x = *y, using DELTA as the
1604 starting solution. */
1607 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1610 unsigned int lhs
= get_varinfo (c
->lhs
.var
)->node
;
1612 bitmap sol
= get_varinfo (lhs
)->solution
;
1616 if (bitmap_bit_p (delta
, anything_id
))
1618 flag
= !bitmap_bit_p (sol
, anything_id
);
1620 bitmap_set_bit (sol
, anything_id
);
1623 /* For each variable j in delta (Sol(y)), add
1624 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1625 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1627 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1628 if (type_safe (j
, &roffset
))
1631 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1634 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1639 /* Adding edges from the special vars is pointless.
1640 They don't have sets that can change. */
1641 if (get_varinfo (t
) ->is_special_var
)
1642 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1643 else if (int_add_graph_edge (graph
, lhs
, t
, 0))
1644 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1646 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1647 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1652 /* If the LHS solution changed, mark the var as changed. */
1655 get_varinfo (lhs
)->solution
= sol
;
1656 if (!TEST_BIT (changed
, lhs
))
1658 SET_BIT (changed
, lhs
);
1664 /* Process a constraint C that represents *x = y. */
1667 do_ds_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1669 unsigned int rhs
= get_varinfo (c
->rhs
.var
)->node
;
1670 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1671 bitmap sol
= get_varinfo (rhs
)->solution
;
1675 if (bitmap_bit_p (sol
, anything_id
))
1677 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1679 varinfo_t jvi
= get_varinfo (j
);
1681 unsigned int loff
= c
->lhs
.offset
;
1682 unsigned HOST_WIDE_INT fieldoffset
= jvi
->offset
+ loff
;
1685 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1690 if (!bitmap_bit_p (get_varinfo (t
)->solution
, anything_id
))
1692 bitmap_set_bit (get_varinfo (t
)->solution
, anything_id
);
1693 if (!TEST_BIT (changed
, t
))
1695 SET_BIT (changed
, t
);
1703 /* For each member j of delta (Sol(x)), add an edge from y to j and
1704 union Sol(y) into Sol(j) */
1705 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1707 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1708 if (type_safe (j
, &loff
) && !(get_varinfo(j
)->is_special_var
))
1712 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1714 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1718 if (int_add_graph_edge (graph
, t
, rhs
, roff
))
1720 bitmap tmp
= get_varinfo (t
)->solution
;
1721 if (set_union_with_increment (tmp
, sol
, roff
))
1723 get_varinfo (t
)->solution
= tmp
;
1725 sol
= get_varinfo (rhs
)->solution
;
1726 if (!TEST_BIT (changed
, t
))
1728 SET_BIT (changed
, t
);
1734 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1735 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1739 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1740 constraint (IE *x = &y, x = *y, and *x = y). */
1743 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1745 if (c
->lhs
.type
== DEREF
)
1747 if (c
->rhs
.type
== ADDRESSOF
)
1750 do_da_constraint (graph
, c
, delta
);
1755 do_ds_constraint (graph
, c
, delta
);
1761 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1762 do_sd_constraint (graph
, c
, delta
);
1766 /* Initialize and return a new SCC info structure. */
1768 static struct scc_info
*
1769 init_scc_info (void)
1771 struct scc_info
*si
= XNEW (struct scc_info
);
1772 size_t size
= VEC_length (varinfo_t
, varmap
);
1774 si
->current_index
= 0;
1775 si
->visited
= sbitmap_alloc (size
);
1776 sbitmap_zero (si
->visited
);
1777 si
->in_component
= sbitmap_alloc (size
);
1778 sbitmap_ones (si
->in_component
);
1779 si
->visited_index
= XCNEWVEC (unsigned int, size
+ 1);
1780 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1781 si
->unification_queue
= VEC_alloc (unsigned, heap
, 1);
1785 /* Free an SCC info structure pointed to by SI */
1788 free_scc_info (struct scc_info
*si
)
1790 sbitmap_free (si
->visited
);
1791 sbitmap_free (si
->in_component
);
1792 free (si
->visited_index
);
1793 VEC_free (unsigned, heap
, si
->scc_stack
);
1794 VEC_free (unsigned, heap
, si
->unification_queue
);
1799 /* Find cycles in GRAPH that occur, using strongly connected components, and
1800 collapse the cycles into a single representative node. if UPDATE_CHANGED
1801 is true, then update the changed sbitmap to note those nodes whose
1802 solutions have changed as a result of collapsing. */
1805 find_and_collapse_graph_cycles (constraint_graph_t graph
, bool update_changed
)
1808 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1809 struct scc_info
*si
= init_scc_info ();
1811 for (i
= 0; i
!= size
; ++i
)
1812 if (!TEST_BIT (si
->visited
, i
) && get_varinfo (i
)->node
== i
)
1813 scc_visit (graph
, si
, i
);
1815 process_unification_queue (graph
, si
, update_changed
);
1819 /* Compute a topological ordering for GRAPH, and store the result in the
1820 topo_info structure TI. */
1823 compute_topo_order (constraint_graph_t graph
,
1824 struct topo_info
*ti
)
1827 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1829 for (i
= 0; i
!= size
; ++i
)
1830 if (!TEST_BIT (ti
->visited
, i
) && get_varinfo (i
)->node
== i
)
1831 topo_visit (graph
, ti
, i
);
1834 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1837 bitmap_other_than_zero_bit_set (bitmap b
)
1842 if (bitmap_empty_p (b
))
1844 EXECUTE_IF_SET_IN_BITMAP (b
, 1, i
, bi
)
1849 /* Perform offline variable substitution.
1851 This is a linear time way of identifying variables that must have
1852 equivalent points-to sets, including those caused by static cycles,
1853 and single entry subgraphs, in the constraint graph.
1855 The technique is described in "Off-line variable substitution for
1856 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1857 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1860 perform_var_substitution (constraint_graph_t graph
)
1862 struct topo_info
*ti
= init_topo_info ();
1864 bitmap_obstack_initialize (&iteration_obstack
);
1865 /* Compute the topological ordering of the graph, then visit each
1866 node in topological order. */
1867 compute_topo_order (graph
, ti
);
1869 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1871 unsigned int i
= VEC_pop (unsigned, ti
->topo_order
);
1873 varinfo_t vi
= get_varinfo (i
);
1874 bool okay_to_elim
= false;
1875 unsigned int root
= VEC_length (varinfo_t
, varmap
);
1876 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[i
];
1877 constraint_edge_t ce
= NULL
;
1882 /* We can't eliminate things whose address is taken, or which is
1883 the target of a dereference. */
1884 if (vi
->address_taken
|| vi
->indirect_target
)
1887 /* See if all predecessors of I are ripe for elimination */
1888 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_preds
[i
], 0, k
, bi
)
1891 w
= get_varinfo (k
)->node
;
1893 /* We can't eliminate the node if one of the predecessors is
1894 part of a different strongly connected component. */
1898 okay_to_elim
= true;
1902 okay_to_elim
= false;
1906 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1907 then Solution(i) is a subset of Solution (w), where w is a
1908 predecessor in the graph.
1909 Corollary: If all predecessors of i have the same
1910 points-to set, then i has that same points-to set as
1911 those predecessors. */
1912 tmp
= BITMAP_ALLOC (NULL
);
1913 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1914 get_varinfo (w
)->solution
);
1915 if (!bitmap_empty_p (tmp
))
1917 okay_to_elim
= false;
1926 VEC_iterate (constraint_edge_t
, predvec
, pred
, ce
);
1931 weight
= *(get_graph_weights (graph
, i
, ce
->dest
));
1933 /* We can't eliminate variables that have nonzero weighted
1934 edges between them. */
1935 if (weight
&& bitmap_other_than_zero_bit_set (weight
))
1937 okay_to_elim
= false;
1940 w
= get_varinfo (ce
->dest
)->node
;
1942 /* We can't eliminate the node if one of the predecessors is
1943 part of a different strongly connected component. */
1947 okay_to_elim
= true;
1951 okay_to_elim
= false;
1955 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1956 then Solution(i) is a subset of Solution (w), where w is a
1957 predecessor in the graph.
1958 Corollary: If all predecessors of i have the same
1959 points-to set, then i has that same points-to set as
1960 those predecessors. */
1961 tmp
= BITMAP_ALLOC (NULL
);
1962 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1963 get_varinfo (w
)->solution
);
1964 if (!bitmap_empty_p (tmp
))
1966 okay_to_elim
= false;
1973 /* See if the root is different than the original node.
1974 If so, we've found an equivalence. */
1975 if (root
!= get_varinfo (i
)->node
&& okay_to_elim
)
1977 /* Found an equivalence */
1978 get_varinfo (i
)->node
= root
;
1979 collapse_nodes (graph
, root
, i
);
1980 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1981 fprintf (dump_file
, "Collapsing %s into %s\n",
1982 get_varinfo (i
)->name
,
1983 get_varinfo (root
)->name
);
1984 stats
.collapsed_vars
++;
1988 bitmap_obstack_release (&iteration_obstack
);
1989 free_topo_info (ti
);
1992 /* Solve the constraint graph GRAPH using our worklist solver.
1993 This is based on the PW* family of solvers from the "Efficient Field
1994 Sensitive Pointer Analysis for C" paper.
1995 It works by iterating over all the graph nodes, processing the complex
1996 constraints and propagating the copy constraints, until everything stops
1997 changed. This corresponds to steps 6-8 in the solving list given above. */
2000 solve_graph (constraint_graph_t graph
)
2002 unsigned int size
= VEC_length (varinfo_t
, varmap
);
2005 changed_count
= size
;
2006 changed
= sbitmap_alloc (size
);
2007 sbitmap_ones (changed
);
2009 /* The already collapsed/unreachable nodes will never change, so we
2010 need to account for them in changed_count. */
2011 for (i
= 0; i
< size
; i
++)
2012 if (get_varinfo (i
)->node
!= i
)
2015 while (changed_count
> 0)
2018 struct topo_info
*ti
= init_topo_info ();
2021 bitmap_obstack_initialize (&iteration_obstack
);
2025 /* We already did cycle elimination once, when we did
2026 variable substitution, so we don't need it again for the
2028 if (stats
.iterations
> 1)
2029 find_and_collapse_graph_cycles (graph
, true);
2034 compute_topo_order (graph
, ti
);
2036 while (VEC_length (unsigned, ti
->topo_order
) != 0)
2038 i
= VEC_pop (unsigned, ti
->topo_order
);
2039 gcc_assert (get_varinfo (i
)->node
== i
);
2041 /* If the node has changed, we need to process the
2042 complex constraints and outgoing edges again. */
2043 if (TEST_BIT (changed
, i
))
2047 constraint_edge_t e
= NULL
;
2050 VEC(constraint_t
,heap
) *complex = get_varinfo (i
)->complex;
2051 VEC(constraint_edge_t
,heap
) *succs
;
2052 bool solution_empty
;
2054 RESET_BIT (changed
, i
);
2057 solution
= get_varinfo (i
)->solution
;
2058 solution_empty
= bitmap_empty_p (solution
);
2060 /* Process the complex constraints */
2061 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
2063 /* The only complex constraint that can change our
2064 solution to non-empty, given an empty solution,
2065 is a constraint where the lhs side is receiving
2066 some set from elsewhere. */
2067 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2068 do_complex_constraint (graph
, c
, solution
);
2071 solution_empty
= bitmap_empty_p (solution
);
2073 if (!solution_empty
)
2075 /* Propagate solution to all successors. */
2076 succs
= graph
->succs
[i
];
2078 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[i
],
2081 bitmap tmp
= get_varinfo (j
)->solution
;
2084 flag
= set_union_with_increment (tmp
, solution
, 0);
2088 get_varinfo (j
)->solution
= tmp
;
2089 if (!TEST_BIT (changed
, j
))
2091 SET_BIT (changed
, j
);
2096 for (j
= 0; VEC_iterate (constraint_edge_t
, succs
, j
, e
); j
++)
2098 bitmap tmp
= get_varinfo (e
->dest
)->solution
;
2101 bitmap weights
= e
->weights
;
2104 gcc_assert (weights
&& !bitmap_empty_p (weights
));
2105 EXECUTE_IF_SET_IN_BITMAP (weights
, 0, k
, bi
)
2106 flag
|= set_union_with_increment (tmp
, solution
, k
);
2110 get_varinfo (e
->dest
)->solution
= tmp
;
2111 if (!TEST_BIT (changed
, e
->dest
))
2113 SET_BIT (changed
, e
->dest
);
2121 free_topo_info (ti
);
2122 bitmap_obstack_release (&iteration_obstack
);
2125 sbitmap_free (changed
);
2129 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2131 /* Map from trees to variable ids. */
2132 static htab_t id_for_tree
;
2134 typedef struct tree_id
2140 /* Hash a tree id structure. */
2143 tree_id_hash (const void *p
)
2145 const tree_id_t ta
= (tree_id_t
) p
;
2146 return htab_hash_pointer (ta
->t
);
2149 /* Return true if the tree in P1 and the tree in P2 are the same. */
2152 tree_id_eq (const void *p1
, const void *p2
)
2154 const tree_id_t ta1
= (tree_id_t
) p1
;
2155 const tree_id_t ta2
= (tree_id_t
) p2
;
2156 return ta1
->t
== ta2
->t
;
2159 /* Insert ID as the variable id for tree T in the hashtable. */
2162 insert_id_for_tree (tree t
, int id
)
2165 struct tree_id finder
;
2169 slot
= htab_find_slot (id_for_tree
, &finder
, INSERT
);
2170 gcc_assert (*slot
== NULL
);
2171 new_pair
= XNEW (struct tree_id
);
2174 *slot
= (void *)new_pair
;
2177 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
2178 exist in the hash table, return false, otherwise, return true and
2179 set *ID to the id we found. */
2182 lookup_id_for_tree (tree t
, unsigned int *id
)
2185 struct tree_id finder
;
2188 pair
= htab_find (id_for_tree
, &finder
);
2195 /* Return a printable name for DECL */
2198 alias_get_name (tree decl
)
2200 const char *res
= get_name (decl
);
2202 int num_printed
= 0;
2211 if (TREE_CODE (decl
) == SSA_NAME
)
2213 num_printed
= asprintf (&temp
, "%s_%u",
2214 alias_get_name (SSA_NAME_VAR (decl
)),
2215 SSA_NAME_VERSION (decl
));
2217 else if (DECL_P (decl
))
2219 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2221 if (num_printed
> 0)
2223 res
= ggc_strdup (temp
);
2229 /* Find the variable id for tree T in the hashtable.
2230 If T doesn't exist in the hash table, create an entry for it. */
2233 get_id_for_tree (tree t
)
2236 struct tree_id finder
;
2239 pair
= htab_find (id_for_tree
, &finder
);
2241 return create_variable_info_for (t
, alias_get_name (t
));
2246 /* Get a constraint expression from an SSA_VAR_P node. */
2248 static struct constraint_expr
2249 get_constraint_exp_from_ssa_var (tree t
)
2251 struct constraint_expr cexpr
;
2253 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
2255 /* For parameters, get at the points-to set for the actual parm
2257 if (TREE_CODE (t
) == SSA_NAME
2258 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2259 && default_def (SSA_NAME_VAR (t
)) == t
)
2260 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
2262 cexpr
.type
= SCALAR
;
2264 cexpr
.var
= get_id_for_tree (t
);
2265 /* If we determine the result is "anything", and we know this is readonly,
2266 say it points to readonly memory instead. */
2267 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
2269 cexpr
.type
= ADDRESSOF
;
2270 cexpr
.var
= readonly_id
;
2277 /* Process a completed constraint T, and add it to the constraint
2281 process_constraint (constraint_t t
)
2283 struct constraint_expr rhs
= t
->rhs
;
2284 struct constraint_expr lhs
= t
->lhs
;
2286 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
2287 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
2289 if (lhs
.type
== DEREF
)
2290 get_varinfo (lhs
.var
)->directly_dereferenced
= true;
2291 if (rhs
.type
== DEREF
)
2292 get_varinfo (rhs
.var
)->directly_dereferenced
= true;
2294 /* ANYTHING == ANYTHING is pointless. */
2295 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
2298 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2299 else if (lhs
.var
== anything_id
&& lhs
.type
== ADDRESSOF
)
2304 process_constraint (t
);
2306 /* This can happen in our IR with things like n->a = *p */
2307 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
2309 /* Split into tmp = *rhs, *lhs = tmp */
2310 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
2311 tree pointertype
= TREE_TYPE (rhsdecl
);
2312 tree pointedtotype
= TREE_TYPE (pointertype
);
2313 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
2314 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2316 /* If this is an aggregate of known size, we should have passed
2317 this off to do_structure_copy, and it should have broken it
2319 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
2320 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
2322 process_constraint (new_constraint (tmplhs
, rhs
));
2323 process_constraint (new_constraint (lhs
, tmplhs
));
2325 else if (rhs
.type
== ADDRESSOF
)
2328 gcc_assert (rhs
.offset
== 0);
2330 /* No need to mark address taken simply because of escaped vars
2332 if (lhs
.var
!= escaped_vars_id
)
2333 for (vi
= get_varinfo (rhs
.var
); vi
!= NULL
; vi
= vi
->next
)
2334 vi
->address_taken
= true;
2336 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2340 if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2341 get_varinfo (lhs
.var
)->indirect_target
= true;
2342 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2346 /* Return true if T is a variable of a type that could contain
2350 could_have_pointers (tree t
)
2352 tree type
= TREE_TYPE (t
);
2354 if (POINTER_TYPE_P (type
) || AGGREGATE_TYPE_P (type
)
2355 || TREE_CODE (type
) == COMPLEX_TYPE
)
2360 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2363 static unsigned HOST_WIDE_INT
2364 bitpos_of_field (const tree fdecl
)
2367 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
2368 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
2371 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
2372 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
2376 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2377 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2380 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
2381 const unsigned HOST_WIDE_INT fieldsize
,
2382 const unsigned HOST_WIDE_INT accesspos
,
2383 const unsigned HOST_WIDE_INT accesssize
)
2385 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
2387 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
2389 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
2395 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2398 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
)
2401 HOST_WIDE_INT bitsize
= -1;
2402 HOST_WIDE_INT bitmaxsize
= -1;
2403 HOST_WIDE_INT bitpos
;
2405 struct constraint_expr
*result
;
2406 unsigned int beforelength
= VEC_length (ce_s
, *results
);
2408 /* Some people like to do cute things like take the address of
2411 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
2412 forzero
= TREE_OPERAND (forzero
, 0);
2414 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
2416 struct constraint_expr temp
;
2419 temp
.var
= integer_id
;
2421 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2425 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
2427 /* String constants's are readonly, so there is nothing to really do
2429 if (TREE_CODE (t
) == STRING_CST
)
2432 get_constraint_for (t
, results
);
2433 result
= VEC_last (ce_s
, *results
);
2434 result
->offset
= bitpos
;
2436 gcc_assert (beforelength
+ 1 == VEC_length (ce_s
, *results
));
2438 /* This can also happen due to weird offsetof type macros. */
2439 if (TREE_CODE (t
) != ADDR_EXPR
&& result
->type
== ADDRESSOF
)
2440 result
->type
= SCALAR
;
2442 if (result
->type
== SCALAR
)
2444 /* In languages like C, you can access one past the end of an
2445 array. You aren't allowed to dereference it, so we can
2446 ignore this constraint. When we handle pointer subtraction,
2447 we may have to do something cute here. */
2449 if (result
->offset
< get_varinfo (result
->var
)->fullsize
2452 /* It's also not true that the constraint will actually start at the
2453 right offset, it may start in some padding. We only care about
2454 setting the constraint to the first actual field it touches, so
2457 for (curr
= get_varinfo (result
->var
); curr
; curr
= curr
->next
)
2459 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2460 result
->offset
, bitmaxsize
))
2462 result
->var
= curr
->id
;
2466 /* assert that we found *some* field there. The user couldn't be
2467 accessing *only* padding. */
2468 /* Still the user could access one past the end of an array
2469 embedded in a struct resulting in accessing *only* padding. */
2470 gcc_assert (curr
|| ref_contains_array_ref (orig_t
));
2472 else if (bitmaxsize
== 0)
2474 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2475 fprintf (dump_file
, "Access to zero-sized part of variable,"
2479 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2480 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2487 /* Dereference the constraint expression CONS, and return the result.
2488 DEREF (ADDRESSOF) = SCALAR
2489 DEREF (SCALAR) = DEREF
2490 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2491 This is needed so that we can handle dereferencing DEREF constraints. */
2494 do_deref (VEC (ce_s
, heap
) **constraints
)
2496 struct constraint_expr
*c
;
2498 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
2500 if (c
->type
== SCALAR
)
2502 else if (c
->type
== ADDRESSOF
)
2504 else if (c
->type
== DEREF
)
2506 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "dereftmp");
2507 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2508 process_constraint (new_constraint (tmplhs
, *c
));
2509 c
->var
= tmplhs
.var
;
2516 /* Create a nonlocal variable of TYPE to represent nonlocals we can
2520 create_nonlocal_var (tree type
)
2522 tree nonlocal
= create_tmp_var_raw (type
, "NONLOCAL");
2524 if (referenced_vars
)
2525 add_referenced_var (nonlocal
);
2527 DECL_EXTERNAL (nonlocal
) = 1;
2531 /* Given a tree T, return the constraint expression for it. */
2534 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
2536 struct constraint_expr temp
;
2538 /* x = integer is all glommed to a single variable, which doesn't
2539 point to anything by itself. That is, of course, unless it is an
2540 integer constant being treated as a pointer, in which case, we
2541 will return that this is really the addressof anything. This
2542 happens below, since it will fall into the default case. The only
2543 case we know something about an integer treated like a pointer is
2544 when it is the NULL pointer, and then we just say it points to
2546 if (TREE_CODE (t
) == INTEGER_CST
2547 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2549 temp
.var
= integer_id
;
2552 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2555 else if (TREE_CODE (t
) == INTEGER_CST
2556 && integer_zerop (t
))
2558 temp
.var
= nothing_id
;
2559 temp
.type
= ADDRESSOF
;
2561 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2565 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2567 case tcc_expression
:
2569 switch (TREE_CODE (t
))
2573 struct constraint_expr
*c
;
2575 tree exp
= TREE_OPERAND (t
, 0);
2576 tree pttype
= TREE_TYPE (TREE_TYPE (t
));
2578 get_constraint_for (exp
, results
);
2579 /* Make sure we capture constraints to all elements
2581 if ((handled_component_p (exp
)
2582 && ref_contains_array_ref (exp
))
2583 || TREE_CODE (TREE_TYPE (exp
)) == ARRAY_TYPE
)
2585 struct constraint_expr
*origrhs
;
2587 struct constraint_expr tmp
;
2589 if (VEC_length (ce_s
, *results
) == 0)
2592 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2593 origrhs
= VEC_last (ce_s
, *results
);
2595 VEC_pop (ce_s
, *results
);
2596 origvar
= get_varinfo (origrhs
->var
);
2597 for (; origvar
; origvar
= origvar
->next
)
2599 tmp
.var
= origvar
->id
;
2600 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2603 else if (VEC_length (ce_s
, *results
) == 1
2604 && (AGGREGATE_TYPE_P (pttype
)
2605 || TREE_CODE (pttype
) == COMPLEX_TYPE
))
2607 struct constraint_expr
*origrhs
;
2609 struct constraint_expr tmp
;
2611 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2612 origrhs
= VEC_last (ce_s
, *results
);
2614 VEC_pop (ce_s
, *results
);
2615 origvar
= get_varinfo (origrhs
->var
);
2616 for (; origvar
; origvar
= origvar
->next
)
2618 tmp
.var
= origvar
->id
;
2619 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2623 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
2625 if (c
->type
== DEREF
)
2628 c
->type
= ADDRESSOF
;
2634 /* XXX: In interprocedural mode, if we didn't have the
2635 body, we would need to do *each pointer argument =
2637 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2640 tree heapvar
= heapvar_lookup (t
);
2642 if (heapvar
== NULL
)
2644 heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2645 DECL_EXTERNAL (heapvar
) = 1;
2646 if (referenced_vars
)
2647 add_referenced_var (heapvar
);
2648 heapvar_insert (t
, heapvar
);
2651 temp
.var
= create_variable_info_for (heapvar
,
2652 alias_get_name (heapvar
));
2654 vi
= get_varinfo (temp
.var
);
2655 vi
->is_artificial_var
= 1;
2656 vi
->is_heap_var
= 1;
2657 temp
.type
= ADDRESSOF
;
2659 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2664 temp
.var
= escaped_vars_id
;
2667 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2673 temp
.type
= ADDRESSOF
;
2674 temp
.var
= anything_id
;
2676 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2683 switch (TREE_CODE (t
))
2687 get_constraint_for (TREE_OPERAND (t
, 0), results
);
2692 case ARRAY_RANGE_REF
:
2694 get_constraint_for_component_ref (t
, results
);
2698 temp
.type
= ADDRESSOF
;
2699 temp
.var
= anything_id
;
2701 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2708 switch (TREE_CODE (t
))
2712 case NON_LVALUE_EXPR
:
2714 tree op
= TREE_OPERAND (t
, 0);
2716 /* Cast from non-pointer to pointers are bad news for us.
2717 Anything else, we see through */
2718 if (!(POINTER_TYPE_P (TREE_TYPE (t
))
2719 && ! POINTER_TYPE_P (TREE_TYPE (op
))))
2721 get_constraint_for (op
, results
);
2729 temp
.type
= ADDRESSOF
;
2730 temp
.var
= anything_id
;
2732 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2737 case tcc_exceptional
:
2739 switch (TREE_CODE (t
))
2743 get_constraint_for (PHI_RESULT (t
), results
);
2749 struct constraint_expr temp
;
2750 temp
= get_constraint_exp_from_ssa_var (t
);
2751 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2757 temp
.type
= ADDRESSOF
;
2758 temp
.var
= anything_id
;
2760 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2765 case tcc_declaration
:
2767 struct constraint_expr temp
;
2768 temp
= get_constraint_exp_from_ssa_var (t
);
2769 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2774 temp
.type
= ADDRESSOF
;
2775 temp
.var
= anything_id
;
2777 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2784 /* Handle the structure copy case where we have a simple structure copy
2785 between LHS and RHS that is of SIZE (in bits)
2787 For each field of the lhs variable (lhsfield)
2788 For each field of the rhs variable at lhsfield.offset (rhsfield)
2789 add the constraint lhsfield = rhsfield
2791 If we fail due to some kind of type unsafety or other thing we
2792 can't handle, return false. We expect the caller to collapse the
2793 variable in that case. */
2796 do_simple_structure_copy (const struct constraint_expr lhs
,
2797 const struct constraint_expr rhs
,
2798 const unsigned HOST_WIDE_INT size
)
2800 varinfo_t p
= get_varinfo (lhs
.var
);
2801 unsigned HOST_WIDE_INT pstart
, last
;
2803 last
= p
->offset
+ size
;
2804 for (; p
&& p
->offset
< last
; p
= p
->next
)
2807 struct constraint_expr templhs
= lhs
;
2808 struct constraint_expr temprhs
= rhs
;
2809 unsigned HOST_WIDE_INT fieldoffset
;
2811 templhs
.var
= p
->id
;
2812 q
= get_varinfo (temprhs
.var
);
2813 fieldoffset
= p
->offset
- pstart
;
2814 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2817 temprhs
.var
= q
->id
;
2818 process_constraint (new_constraint (templhs
, temprhs
));
2824 /* Handle the structure copy case where we have a structure copy between a
2825 aggregate on the LHS and a dereference of a pointer on the RHS
2826 that is of SIZE (in bits)
2828 For each field of the lhs variable (lhsfield)
2829 rhs.offset = lhsfield->offset
2830 add the constraint lhsfield = rhs
2834 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2835 const struct constraint_expr rhs
,
2836 const unsigned HOST_WIDE_INT size
)
2838 varinfo_t p
= get_varinfo (lhs
.var
);
2839 unsigned HOST_WIDE_INT pstart
,last
;
2841 last
= p
->offset
+ size
;
2843 for (; p
&& p
->offset
< last
; p
= p
->next
)
2846 struct constraint_expr templhs
= lhs
;
2847 struct constraint_expr temprhs
= rhs
;
2848 unsigned HOST_WIDE_INT fieldoffset
;
2851 if (templhs
.type
== SCALAR
)
2852 templhs
.var
= p
->id
;
2854 templhs
.offset
= p
->offset
;
2856 q
= get_varinfo (temprhs
.var
);
2857 fieldoffset
= p
->offset
- pstart
;
2858 temprhs
.offset
+= fieldoffset
;
2859 process_constraint (new_constraint (templhs
, temprhs
));
2863 /* Handle the structure copy case where we have a structure copy
2864 between a aggregate on the RHS and a dereference of a pointer on
2865 the LHS that is of SIZE (in bits)
2867 For each field of the rhs variable (rhsfield)
2868 lhs.offset = rhsfield->offset
2869 add the constraint lhs = rhsfield
2873 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2874 const struct constraint_expr rhs
,
2875 const unsigned HOST_WIDE_INT size
)
2877 varinfo_t p
= get_varinfo (rhs
.var
);
2878 unsigned HOST_WIDE_INT pstart
,last
;
2880 last
= p
->offset
+ size
;
2882 for (; p
&& p
->offset
< last
; p
= p
->next
)
2885 struct constraint_expr templhs
= lhs
;
2886 struct constraint_expr temprhs
= rhs
;
2887 unsigned HOST_WIDE_INT fieldoffset
;
2890 if (temprhs
.type
== SCALAR
)
2891 temprhs
.var
= p
->id
;
2893 temprhs
.offset
= p
->offset
;
2895 q
= get_varinfo (templhs
.var
);
2896 fieldoffset
= p
->offset
- pstart
;
2897 templhs
.offset
+= fieldoffset
;
2898 process_constraint (new_constraint (templhs
, temprhs
));
2902 /* Sometimes, frontends like to give us bad type information. This
2903 function will collapse all the fields from VAR to the end of VAR,
2904 into VAR, so that we treat those fields as a single variable.
2905 We return the variable they were collapsed into. */
2908 collapse_rest_of_var (unsigned int var
)
2910 varinfo_t currvar
= get_varinfo (var
);
2913 for (field
= currvar
->next
; field
; field
= field
->next
)
2916 fprintf (dump_file
, "Type safety: Collapsing var %s into %s\n",
2917 field
->name
, currvar
->name
);
2919 gcc_assert (!field
->collapsed_to
);
2920 field
->collapsed_to
= currvar
;
2923 currvar
->next
= NULL
;
2924 currvar
->size
= currvar
->fullsize
- currvar
->offset
;
2929 /* Handle aggregate copies by expanding into copies of the respective
2930 fields of the structures. */
2933 do_structure_copy (tree lhsop
, tree rhsop
)
2935 struct constraint_expr lhs
, rhs
, tmp
;
2936 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
2938 unsigned HOST_WIDE_INT lhssize
;
2939 unsigned HOST_WIDE_INT rhssize
;
2941 get_constraint_for (lhsop
, &lhsc
);
2942 get_constraint_for (rhsop
, &rhsc
);
2943 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
2944 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
2945 lhs
= *(VEC_last (ce_s
, lhsc
));
2946 rhs
= *(VEC_last (ce_s
, rhsc
));
2948 VEC_free (ce_s
, heap
, lhsc
);
2949 VEC_free (ce_s
, heap
, rhsc
);
2951 /* If we have special var = x, swap it around. */
2952 if (lhs
.var
<= integer_id
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2959 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2960 possible it's something we could handle. However, most cases falling
2961 into this are dealing with transparent unions, which are slightly
2963 if (rhs
.type
== ADDRESSOF
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2965 rhs
.type
= ADDRESSOF
;
2966 rhs
.var
= anything_id
;
2969 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2970 that special var. */
2971 if (rhs
.var
<= integer_id
)
2973 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2975 struct constraint_expr templhs
= lhs
;
2976 struct constraint_expr temprhs
= rhs
;
2978 if (templhs
.type
== SCALAR
)
2979 templhs
.var
= p
->id
;
2981 templhs
.offset
+= p
->offset
;
2982 process_constraint (new_constraint (templhs
, temprhs
));
2987 tree rhstype
= TREE_TYPE (rhsop
);
2988 tree lhstype
= TREE_TYPE (lhsop
);
2992 lhstypesize
= DECL_P (lhsop
) ? DECL_SIZE (lhsop
) : TYPE_SIZE (lhstype
);
2993 rhstypesize
= DECL_P (rhsop
) ? DECL_SIZE (rhsop
) : TYPE_SIZE (rhstype
);
2995 /* If we have a variably sized types on the rhs or lhs, and a deref
2996 constraint, add the constraint, lhsconstraint = &ANYTHING.
2997 This is conservatively correct because either the lhs is an unknown
2998 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2999 constraint, and every variable it can point to must be unknown sized
3000 anyway, so we don't need to worry about fields at all. */
3001 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
3002 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
3004 rhs
.var
= anything_id
;
3005 rhs
.type
= ADDRESSOF
;
3007 process_constraint (new_constraint (lhs
, rhs
));
3011 /* The size only really matters insofar as we don't set more or less of
3012 the variable. If we hit an unknown size var, the size should be the
3013 whole darn thing. */
3014 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
3017 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
3019 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
3022 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
3025 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
3027 if (!do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
)))
3029 lhs
.var
= collapse_rest_of_var (lhs
.var
);
3030 rhs
.var
= collapse_rest_of_var (rhs
.var
);
3035 process_constraint (new_constraint (lhs
, rhs
));
3038 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
3039 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
3040 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
3041 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
3044 tree pointedtotype
= lhstype
;
3047 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
3048 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
3049 do_structure_copy (tmpvar
, rhsop
);
3050 do_structure_copy (lhsop
, tmpvar
);
3055 /* Update related alias information kept in AI. This is used when
3056 building name tags, alias sets and deciding grouping heuristics.
3057 STMT is the statement to process. This function also updates
3058 ADDRESSABLE_VARS. */
3061 update_alias_info (tree stmt
, struct alias_info
*ai
)
3064 use_operand_p use_p
;
3066 enum escape_type stmt_escape_type
= is_escape_site (stmt
);
3069 if (stmt_escape_type
== ESCAPE_TO_CALL
3070 || stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
3072 ai
->num_calls_found
++;
3073 if (stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
3074 ai
->num_pure_const_calls_found
++;
3077 /* Mark all the variables whose address are taken by the statement. */
3078 addr_taken
= addresses_taken (stmt
);
3081 bitmap_ior_into (addressable_vars
, addr_taken
);
3083 /* If STMT is an escape point, all the addresses taken by it are
3085 if (stmt_escape_type
!= NO_ESCAPE
)
3090 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
3092 tree rvar
= referenced_var (i
);
3093 if (!unmodifiable_var_p (rvar
))
3094 mark_call_clobbered (rvar
, stmt_escape_type
);
3099 /* Process each operand use. If an operand may be aliased, keep
3100 track of how many times it's being used. For pointers, determine
3101 whether they are dereferenced by the statement, or whether their
3102 value escapes, etc. */
3103 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
3107 struct ptr_info_def
*pi
;
3108 bool is_store
, is_potential_deref
;
3109 unsigned num_uses
, num_derefs
;
3111 op
= USE_FROM_PTR (use_p
);
3113 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3114 to the set of addressable variables. */
3115 if (TREE_CODE (op
) == ADDR_EXPR
)
3117 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
);
3119 /* PHI nodes don't have annotations for pinning the set
3120 of addresses taken, so we collect them here.
3122 FIXME, should we allow PHI nodes to have annotations
3123 so that they can be treated like regular statements?
3124 Currently, they are treated as second-class
3126 add_to_addressable_set (TREE_OPERAND (op
, 0), &addressable_vars
);
3130 /* Ignore constants. */
3131 if (TREE_CODE (op
) != SSA_NAME
)
3134 var
= SSA_NAME_VAR (op
);
3135 v_ann
= var_ann (var
);
3137 /* The base variable of an ssa name must be a GIMPLE register, and thus
3138 it cannot be aliased. */
3139 gcc_assert (!may_be_aliased (var
));
3141 /* We are only interested in pointers. */
3142 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
3145 pi
= get_ptr_info (op
);
3147 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3148 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
)))
3150 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
));
3151 VEC_safe_push (tree
, heap
, ai
->processed_ptrs
, op
);
3154 /* If STMT is a PHI node, then it will not have pointer
3155 dereferences and it will not be an escape point. */
3156 if (TREE_CODE (stmt
) == PHI_NODE
)
3159 /* Determine whether OP is a dereferenced pointer, and if STMT
3160 is an escape point, whether OP escapes. */
3161 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
3163 /* Handle a corner case involving address expressions of the
3164 form '&PTR->FLD'. The problem with these expressions is that
3165 they do not represent a dereference of PTR. However, if some
3166 other transformation propagates them into an INDIRECT_REF
3167 expression, we end up with '*(&PTR->FLD)' which is folded
3170 So, if the original code had no other dereferences of PTR,
3171 the aliaser will not create memory tags for it, and when
3172 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3173 memory operations will receive no V_MAY_DEF/VUSE operands.
3175 One solution would be to have count_uses_and_derefs consider
3176 &PTR->FLD a dereference of PTR. But that is wrong, since it
3177 is not really a dereference but an offset calculation.
3179 What we do here is to recognize these special ADDR_EXPR
3180 nodes. Since these expressions are never GIMPLE values (they
3181 are not GIMPLE invariants), they can only appear on the RHS
3182 of an assignment and their base address is always an
3183 INDIRECT_REF expression. */
3184 is_potential_deref
= false;
3185 if (TREE_CODE (stmt
) == MODIFY_EXPR
3186 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ADDR_EXPR
3187 && !is_gimple_val (TREE_OPERAND (stmt
, 1)))
3189 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3190 this represents a potential dereference of PTR. */
3191 tree rhs
= TREE_OPERAND (stmt
, 1);
3192 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
3193 if (TREE_CODE (base
) == INDIRECT_REF
3194 && TREE_OPERAND (base
, 0) == op
)
3195 is_potential_deref
= true;
3198 if (num_derefs
> 0 || is_potential_deref
)
3200 /* Mark OP as dereferenced. In a subsequent pass,
3201 dereferenced pointers that point to a set of
3202 variables will be assigned a name tag to alias
3203 all the variables OP points to. */
3204 pi
->is_dereferenced
= 1;
3206 /* Keep track of how many time we've dereferenced each
3208 NUM_REFERENCES_INC (v_ann
);
3210 /* If this is a store operation, mark OP as being
3211 dereferenced to store, otherwise mark it as being
3212 dereferenced to load. */
3214 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
3216 bitmap_set_bit (ai
->dereferenced_ptrs_load
, DECL_UID (var
));
3219 if (stmt_escape_type
!= NO_ESCAPE
&& num_derefs
< num_uses
)
3221 /* If STMT is an escape point and STMT contains at
3222 least one direct use of OP, then the value of OP
3223 escapes and so the pointed-to variables need to
3224 be marked call-clobbered. */
3225 pi
->value_escapes_p
= 1;
3226 pi
->escape_mask
|= stmt_escape_type
;
3228 /* If the statement makes a function call, assume
3229 that pointer OP will be dereferenced in a store
3230 operation inside the called function. */
3231 if (get_call_expr_in (stmt
)
3232 || stmt_escape_type
== ESCAPE_STORED_IN_GLOBAL
)
3234 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
3235 pi
->is_dereferenced
= 1;
3240 if (TREE_CODE (stmt
) == PHI_NODE
)
3243 /* Update reference counter for definitions to any
3244 potentially aliased variable. This is used in the alias
3245 grouping heuristics. */
3246 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3248 tree var
= SSA_NAME_VAR (op
);
3249 var_ann_t ann
= var_ann (var
);
3250 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
3251 if (may_be_aliased (var
))
3252 NUM_REFERENCES_INC (ann
);
3256 /* Mark variables in V_MAY_DEF operands as being written to. */
3257 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
3259 tree var
= DECL_P (op
) ? op
: SSA_NAME_VAR (op
);
3260 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
3265 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3266 Expressions of the type PTR + CST can be handled in two ways:
3268 1- If the constraint for PTR is ADDRESSOF for a non-structure
3269 variable, then we can use it directly because adding or
3270 subtracting a constant may not alter the original ADDRESSOF
3271 constraint (i.e., pointer arithmetic may not legally go outside
3272 an object's boundaries).
3274 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3275 then if CST is a compile-time constant that can be used as an
3276 offset, we can determine which sub-variable will be pointed-to
3279 Return true if the expression is handled. For any other kind of
3280 expression, return false so that each operand can be added as a
3281 separate constraint by the caller. */
3284 handle_ptr_arith (VEC (ce_s
, heap
) *lhsc
, tree expr
)
3287 struct constraint_expr
*c
, *c2
;
3290 VEC (ce_s
, heap
) *temp
= NULL
;
3291 unsigned int rhsoffset
= 0;
3293 if (TREE_CODE (expr
) != PLUS_EXPR
3294 && TREE_CODE (expr
) != MINUS_EXPR
)
3297 op0
= TREE_OPERAND (expr
, 0);
3298 op1
= TREE_OPERAND (expr
, 1);
3300 get_constraint_for (op0
, &temp
);
3301 if (POINTER_TYPE_P (TREE_TYPE (op0
))
3302 && TREE_CODE (op1
) == INTEGER_CST
3303 && TREE_CODE (expr
) == PLUS_EXPR
)
3305 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
3310 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
3311 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
3313 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
3315 varinfo_t temp
= get_varinfo (c2
->var
);
3317 /* An access one after the end of an array is valid,
3318 so simply punt on accesses we cannot resolve. */
3319 temp
= first_vi_for_offset (temp
, rhsoffset
);
3326 c2
->offset
= rhsoffset
;
3327 process_constraint (new_constraint (*c
, *c2
));
3330 VEC_free (ce_s
, heap
, temp
);
3336 /* Walk statement T setting up aliasing constraints according to the
3337 references found in T. This function is the main part of the
3338 constraint builder. AI points to auxiliary alias information used
3339 when building alias sets and computing alias grouping heuristics. */
3342 find_func_aliases (tree origt
)
3345 VEC(ce_s
, heap
) *lhsc
= NULL
;
3346 VEC(ce_s
, heap
) *rhsc
= NULL
;
3347 struct constraint_expr
*c
;
3349 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
3350 t
= TREE_OPERAND (t
, 0);
3352 /* Now build constraints expressions. */
3353 if (TREE_CODE (t
) == PHI_NODE
)
3355 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))));
3357 /* Only care about pointers and structures containing
3359 if (could_have_pointers (PHI_RESULT (t
)))
3364 /* For a phi node, assign all the arguments to
3366 get_constraint_for (PHI_RESULT (t
), &lhsc
);
3367 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
3370 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
3372 STRIP_NOPS (strippedrhs
);
3373 rhstype
= TREE_TYPE (strippedrhs
);
3374 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
3376 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3378 struct constraint_expr
*c2
;
3379 while (VEC_length (ce_s
, rhsc
) > 0)
3381 c2
= VEC_last (ce_s
, rhsc
);
3382 process_constraint (new_constraint (*c
, *c2
));
3383 VEC_pop (ce_s
, rhsc
);
3389 /* In IPA mode, we need to generate constraints to pass call
3390 arguments through their calls. There are two case, either a
3391 modify_expr when we are returning a value, or just a plain
3392 call_expr when we are not. */
3393 else if (in_ipa_mode
3394 && ((TREE_CODE (t
) == MODIFY_EXPR
3395 && TREE_CODE (TREE_OPERAND (t
, 1)) == CALL_EXPR
3396 && !(call_expr_flags (TREE_OPERAND (t
, 1))
3397 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
3398 || (TREE_CODE (t
) == CALL_EXPR
3399 && !(call_expr_flags (t
)
3400 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
3409 if (TREE_CODE (t
) == MODIFY_EXPR
)
3411 lhsop
= TREE_OPERAND (t
, 0);
3412 rhsop
= TREE_OPERAND (t
, 1);
3419 decl
= get_callee_fndecl (rhsop
);
3421 /* If we can directly resolve the function being called, do so.
3422 Otherwise, it must be some sort of indirect expression that
3423 we should still be able to handle. */
3426 varid
= get_id_for_tree (decl
);
3430 decl
= TREE_OPERAND (rhsop
, 0);
3431 varid
= get_id_for_tree (decl
);
3434 /* Assign all the passed arguments to the appropriate incoming
3435 parameters of the function. */
3436 fi
= get_varinfo (varid
);
3437 arglist
= TREE_OPERAND (rhsop
, 1);
3439 for (;arglist
; arglist
= TREE_CHAIN (arglist
))
3441 tree arg
= TREE_VALUE (arglist
);
3442 struct constraint_expr lhs
;
3443 struct constraint_expr
*rhsp
;
3445 get_constraint_for (arg
, &rhsc
);
3446 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3455 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3458 while (VEC_length (ce_s
, rhsc
) != 0)
3460 rhsp
= VEC_last (ce_s
, rhsc
);
3461 process_constraint (new_constraint (lhs
, *rhsp
));
3462 VEC_pop (ce_s
, rhsc
);
3466 /* If we are returning a value, assign it to the result. */
3469 struct constraint_expr rhs
;
3470 struct constraint_expr
*lhsp
;
3473 get_constraint_for (lhsop
, &lhsc
);
3474 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3483 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3486 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3487 process_constraint (new_constraint (*lhsp
, rhs
));
3490 /* Otherwise, just a regular assignment statement. */
3491 else if (TREE_CODE (t
) == MODIFY_EXPR
)
3493 tree lhsop
= TREE_OPERAND (t
, 0);
3494 tree rhsop
= TREE_OPERAND (t
, 1);
3497 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3498 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
)
3499 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop
))
3500 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
))
3502 do_structure_copy (lhsop
, rhsop
);
3506 /* Only care about operations with pointers, structures
3507 containing pointers, dereferences, and call expressions. */
3508 if (could_have_pointers (lhsop
)
3509 || TREE_CODE (rhsop
) == CALL_EXPR
)
3511 get_constraint_for (lhsop
, &lhsc
);
3512 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3514 /* RHS that consist of unary operations,
3515 exceptional types, or bare decls/constants, get
3516 handled directly by get_constraint_for. */
3518 case tcc_declaration
:
3520 case tcc_exceptional
:
3521 case tcc_expression
:
3526 get_constraint_for (rhsop
, &rhsc
);
3527 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3529 struct constraint_expr
*c2
;
3532 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3533 process_constraint (new_constraint (*c
, *c2
));
3541 /* For pointer arithmetic of the form
3542 PTR + CST, we can simply use PTR's
3543 constraint because pointer arithmetic is
3544 not allowed to go out of bounds. */
3545 if (handle_ptr_arith (lhsc
, rhsop
))
3550 /* Otherwise, walk each operand. Notice that we
3551 can't use the operand interface because we need
3552 to process expressions other than simple operands
3553 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3555 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
3557 tree op
= TREE_OPERAND (rhsop
, i
);
3560 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3561 get_constraint_for (op
, &rhsc
);
3562 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3564 struct constraint_expr
*c2
;
3565 while (VEC_length (ce_s
, rhsc
) > 0)
3567 c2
= VEC_last (ce_s
, rhsc
);
3568 process_constraint (new_constraint (*c
, *c2
));
3569 VEC_pop (ce_s
, rhsc
);
3578 /* After promoting variables and computing aliasing we will
3579 need to re-scan most statements. FIXME: Try to minimize the
3580 number of statements re-scanned. It's not really necessary to
3581 re-scan *all* statements. */
3582 mark_stmt_modified (origt
);
3583 VEC_free (ce_s
, heap
, rhsc
);
3584 VEC_free (ce_s
, heap
, lhsc
);
3588 /* Find the first varinfo in the same variable as START that overlaps with
3590 Effectively, walk the chain of fields for the variable START to find the
3591 first field that overlaps with OFFSET.
3592 Return NULL if we can't find one. */
3595 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3597 varinfo_t curr
= start
;
3600 /* We may not find a variable in the field list with the actual
3601 offset when when we have glommed a structure to a variable.
3602 In that case, however, offset should still be within the size
3604 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3612 /* Insert the varinfo FIELD into the field list for BASE, at the front
3616 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3618 varinfo_t prev
= base
;
3619 varinfo_t curr
= base
->next
;
3625 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3629 insert_into_field_list_sorted (varinfo_t base
, varinfo_t field
)
3631 varinfo_t prev
= base
;
3632 varinfo_t curr
= base
->next
;
3643 if (field
->offset
<= curr
->offset
)
3648 field
->next
= prev
->next
;
3653 /* qsort comparison function for two fieldoff's PA and PB */
3656 fieldoff_compare (const void *pa
, const void *pb
)
3658 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3659 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3660 HOST_WIDE_INT foasize
, fobsize
;
3662 if (foa
->offset
!= fob
->offset
)
3663 return foa
->offset
- fob
->offset
;
3665 foasize
= TREE_INT_CST_LOW (foa
->size
);
3666 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3667 return foasize
- fobsize
;
3670 /* Sort a fieldstack according to the field offset and sizes. */
3672 sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3674 qsort (VEC_address (fieldoff_s
, fieldstack
),
3675 VEC_length (fieldoff_s
, fieldstack
),
3676 sizeof (fieldoff_s
),
3680 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3681 of TYPE onto fieldstack, recording their offsets along the way.
3682 OFFSET is used to keep track of the offset in this entire structure, rather
3683 than just the immediately containing structure. Returns the number
3685 HAS_UNION is set to true if we find a union type as a field of
3689 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3690 HOST_WIDE_INT offset
, bool *has_union
)
3695 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3697 fieldoff_s
*real_part
, *img_part
;
3698 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3699 real_part
->type
= TREE_TYPE (type
);
3700 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3701 real_part
->offset
= offset
;
3702 real_part
->decl
= NULL_TREE
;
3704 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3705 img_part
->type
= TREE_TYPE (type
);
3706 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3707 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3708 img_part
->decl
= NULL_TREE
;
3713 if (TREE_CODE (type
) == ARRAY_TYPE
)
3715 tree sz
= TYPE_SIZE (type
);
3716 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3721 || ! host_integerp (sz
, 1)
3722 || TREE_INT_CST_LOW (sz
) == 0
3724 || ! host_integerp (elsz
, 1)
3725 || TREE_INT_CST_LOW (elsz
) == 0)
3728 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3729 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3732 for (i
= 0; i
< nr
; ++i
)
3738 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3739 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3742 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3744 else if (!(pushed
= push_fields_onto_fieldstack
3745 (TREE_TYPE (type
), fieldstack
,
3746 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
)))
3747 /* Empty structures may have actual size, like in C++. So
3748 see if we didn't push any subfields and the size is
3749 nonzero, push the field onto the stack */
3756 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3757 pair
->type
= TREE_TYPE (type
);
3759 pair
->decl
= NULL_TREE
;
3760 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3770 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3771 if (TREE_CODE (field
) == FIELD_DECL
)
3777 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3778 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3781 if (!var_can_have_subvars (field
))
3783 else if (!(pushed
= push_fields_onto_fieldstack
3784 (TREE_TYPE (field
), fieldstack
,
3785 offset
+ bitpos_of_field (field
), has_union
))
3786 && DECL_SIZE (field
)
3787 && !integer_zerop (DECL_SIZE (field
)))
3788 /* Empty structures may have actual size, like in C++. So
3789 see if we didn't push any subfields and the size is
3790 nonzero, push the field onto the stack */
3797 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3798 pair
->type
= TREE_TYPE (field
);
3799 pair
->size
= DECL_SIZE (field
);
3801 pair
->offset
= offset
+ bitpos_of_field (field
);
3811 /* Create a constraint from ESCAPED_VARS variable to VI. */
3813 make_constraint_from_escaped (varinfo_t vi
)
3815 struct constraint_expr lhs
, rhs
;
3821 rhs
.var
= escaped_vars_id
;
3824 process_constraint (new_constraint (lhs
, rhs
));
3827 /* Create a constraint to the ESCAPED_VARS variable from constraint
3831 make_constraint_to_escaped (struct constraint_expr rhs
)
3833 struct constraint_expr lhs
;
3835 lhs
.var
= escaped_vars_id
;
3839 process_constraint (new_constraint (lhs
, rhs
));
3842 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3843 if it is a varargs function. */
3846 count_num_arguments (tree decl
, bool *is_varargs
)
3851 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3855 if (TREE_VALUE (t
) == void_type_node
)
3865 /* Creation function node for DECL, using NAME, and return the index
3866 of the variable we've created for the function. */
3869 create_function_info_for (tree decl
, const char *name
)
3871 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3875 bool is_varargs
= false;
3877 /* Create the variable info. */
3879 vi
= new_var_info (decl
, index
, name
, index
);
3884 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3885 insert_id_for_tree (vi
->decl
, index
);
3886 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3890 /* If it's varargs, we don't know how many arguments it has, so we
3897 vi
->is_unknown_size_var
= true;
3902 arg
= DECL_ARGUMENTS (decl
);
3904 /* Set up variables for each argument. */
3905 for (i
= 1; i
< vi
->fullsize
; i
++)
3908 const char *newname
;
3910 unsigned int newindex
;
3911 tree argdecl
= decl
;
3916 newindex
= VEC_length (varinfo_t
, varmap
);
3917 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3918 newname
= ggc_strdup (tempname
);
3921 argvi
= new_var_info (argdecl
, newindex
,newname
, newindex
);
3922 argvi
->decl
= argdecl
;
3923 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3926 argvi
->fullsize
= vi
->fullsize
;
3927 argvi
->has_union
= false;
3928 insert_into_field_list_sorted (vi
, argvi
);
3929 stats
.total_vars
++;
3932 insert_id_for_tree (arg
, newindex
);
3933 arg
= TREE_CHAIN (arg
);
3937 /* Create a variable for the return var. */
3938 if (DECL_RESULT (decl
) != NULL
3939 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3942 const char *newname
;
3944 unsigned int newindex
;
3945 tree resultdecl
= decl
;
3949 if (DECL_RESULT (decl
))
3950 resultdecl
= DECL_RESULT (decl
);
3952 newindex
= VEC_length (varinfo_t
, varmap
);
3953 asprintf (&tempname
, "%s.result", name
);
3954 newname
= ggc_strdup (tempname
);
3957 resultvi
= new_var_info (resultdecl
, newindex
, newname
, newindex
);
3958 resultvi
->decl
= resultdecl
;
3959 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3960 resultvi
->offset
= i
;
3962 resultvi
->fullsize
= vi
->fullsize
;
3963 resultvi
->has_union
= false;
3964 insert_into_field_list_sorted (vi
, resultvi
);
3965 stats
.total_vars
++;
3966 if (DECL_RESULT (decl
))
3967 insert_id_for_tree (DECL_RESULT (decl
), newindex
);
3973 /* Return true if FIELDSTACK contains fields that overlap.
3974 FIELDSTACK is assumed to be sorted by offset. */
3977 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3979 fieldoff_s
*fo
= NULL
;
3981 HOST_WIDE_INT lastoffset
= -1;
3983 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3985 if (fo
->offset
== lastoffset
)
3987 lastoffset
= fo
->offset
;
3992 /* This function is called through walk_tree to walk global
3993 initializers looking for constraints we need to add to the
3997 find_global_initializers (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
4000 varinfo_t vi
= (varinfo_t
)viv
;
4003 switch (TREE_CODE (t
))
4005 /* Dereferences and addressofs are the only important things
4006 here, and i don't even remember if dereferences are legal
4007 here in initializers. */
4011 struct constraint_expr
*c
;
4014 VEC(ce_s
, heap
) *rhsc
= NULL
;
4015 get_constraint_for (t
, &rhsc
);
4016 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
4018 struct constraint_expr lhs
;
4023 process_constraint (new_constraint (lhs
, *c
));
4026 VEC_free (ce_s
, heap
, rhsc
);
4030 /* We might not have walked this because we skip
4031 DECL_EXTERNALs during the initial scan. */
4032 if (referenced_vars
)
4035 if (referenced_var_check_and_insert (t
))
4036 mark_sym_for_renaming (t
);
4045 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4046 This will also create any varinfo structures necessary for fields
4050 create_variable_info_for (tree decl
, const char *name
)
4052 unsigned int index
= VEC_length (varinfo_t
, varmap
);
4054 tree
decltype = TREE_TYPE (decl
);
4055 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
4056 bool notokay
= false;
4058 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
4059 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
4061 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
4062 return create_function_info_for (decl
, name
);
4064 hasunion
= TREE_CODE (decltype) == UNION_TYPE
4065 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
4066 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
4068 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
4071 VEC_free (fieldoff_s
, heap
, fieldstack
);
4077 /* If the variable doesn't have subvars, we may end up needing to
4078 sort the field list and create fake variables for all the
4080 vi
= new_var_info (decl
, index
, name
, index
);
4083 vi
->has_union
= hasunion
;
4085 || TREE_CODE (declsize
) != INTEGER_CST
4086 || TREE_CODE (decltype) == UNION_TYPE
4087 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
4089 vi
->is_unknown_size_var
= true;
4095 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
4096 vi
->size
= vi
->fullsize
;
4099 insert_id_for_tree (vi
->decl
, index
);
4100 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
4101 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
4103 make_constraint_from_escaped (vi
);
4105 /* If the variable can't be aliased, there is no point in
4106 putting it in the set of nonlocal vars. */
4107 if (may_be_aliased (vi
->decl
))
4109 struct constraint_expr rhs
;
4111 rhs
.type
= ADDRESSOF
;
4113 make_constraint_to_escaped (rhs
);
4116 if (TREE_CODE (decl
) != FUNCTION_DECL
&& DECL_INITIAL (decl
))
4118 walk_tree_without_duplicates (&DECL_INITIAL (decl
),
4119 find_global_initializers
,
4125 if (use_field_sensitive
4127 && !vi
->is_unknown_size_var
4128 && var_can_have_subvars (decl
)
4129 && VEC_length (fieldoff_s
, fieldstack
) <= MAX_FIELDS_FOR_FIELD_SENSITIVE
)
4131 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
4132 fieldoff_s
*fo
= NULL
;
4135 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
4138 || TREE_CODE (fo
->size
) != INTEGER_CST
4146 /* We can't sort them if we have a field with a variable sized type,
4147 which will make notokay = true. In that case, we are going to return
4148 without creating varinfos for the fields anyway, so sorting them is a
4152 sort_fieldstack (fieldstack
);
4153 /* Due to some C++ FE issues, like PR 22488, we might end up
4154 what appear to be overlapping fields even though they,
4155 in reality, do not overlap. Until the C++ FE is fixed,
4156 we will simply disable field-sensitivity for these cases. */
4157 notokay
= check_for_overlaps (fieldstack
);
4161 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
4162 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
4164 if (fo
== NULL
|| notokay
)
4166 vi
->is_unknown_size_var
= 1;
4169 VEC_free (fieldoff_s
, heap
, fieldstack
);
4173 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
4174 vi
->offset
= fo
->offset
;
4175 for (i
= VEC_length (fieldoff_s
, fieldstack
) - 1;
4176 i
>= 1 && VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
4180 const char *newname
= "NULL";
4183 newindex
= VEC_length (varinfo_t
, varmap
);
4187 asprintf (&tempname
, "%s.%s",
4188 vi
->name
, alias_get_name (fo
->decl
));
4190 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
,
4191 vi
->name
, fo
->offset
);
4192 newname
= ggc_strdup (tempname
);
4195 newvi
= new_var_info (decl
, newindex
, newname
, newindex
);
4196 newvi
->offset
= fo
->offset
;
4197 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
4198 newvi
->fullsize
= vi
->fullsize
;
4199 insert_into_field_list (vi
, newvi
);
4200 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
4201 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
4203 /* If the variable can't be aliased, there is no point in
4204 putting it in the set of nonlocal vars. */
4205 if (may_be_aliased (vi
->decl
))
4207 struct constraint_expr rhs
;
4210 rhs
.type
= ADDRESSOF
;
4212 make_constraint_to_escaped (rhs
);
4214 make_constraint_from_escaped (newvi
);
4219 VEC_free (fieldoff_s
, heap
, fieldstack
);
4224 /* Print out the points-to solution for VAR to FILE. */
4227 dump_solution_for_var (FILE *file
, unsigned int var
)
4229 varinfo_t vi
= get_varinfo (var
);
4233 fprintf (file
, "%s = { ", vi
->name
);
4234 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi
->node
)->solution
, 0, i
, bi
)
4236 fprintf (file
, "%s ", get_varinfo (i
)->name
);
4238 fprintf (file
, "}\n");
4241 /* Print the points-to solution for VAR to stdout. */
4244 debug_solution_for_var (unsigned int var
)
4246 dump_solution_for_var (stdout
, var
);
4249 /* Create varinfo structures for all of the variables in the
4250 function for intraprocedural mode. */
4253 intra_create_variable_infos (void)
4256 struct constraint_expr lhs
, rhs
;
4257 varinfo_t nonlocal_vi
;
4259 /* For each incoming pointer argument arg, ARG = ESCAPED_VARS or a
4260 dummy variable if flag_argument_noalias > 2. */
4261 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
4264 unsigned int arg_id
;
4266 if (!could_have_pointers (t
))
4269 arg_id
= get_id_for_tree (t
);
4271 /* With flag_argument_noalias greater than two means that the incoming
4272 argument cannot alias anything except for itself so create a HEAP
4274 if (POINTER_TYPE_P (TREE_TYPE (t
))
4275 && flag_argument_noalias
> 2)
4278 tree heapvar
= heapvar_lookup (t
);
4283 lhs
.var
= get_id_for_tree (t
);
4285 if (heapvar
== NULL_TREE
)
4287 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)),
4289 DECL_EXTERNAL (heapvar
) = 1;
4290 if (referenced_vars
)
4291 add_referenced_var (heapvar
);
4292 heapvar_insert (t
, heapvar
);
4294 id
= get_id_for_tree (heapvar
);
4295 vi
= get_varinfo (id
);
4296 vi
->is_artificial_var
= 1;
4297 vi
->is_heap_var
= 1;
4299 rhs
.type
= ADDRESSOF
;
4301 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4303 struct constraint_expr temp
= lhs
;
4305 process_constraint (new_constraint (temp
, rhs
));
4310 for (p
= get_varinfo (arg_id
); p
; p
= p
->next
)
4311 make_constraint_from_escaped (p
);
4315 nonlocal_all
= create_nonlocal_var (void_type_node
);
4317 /* Create variable info for the nonlocal var if it does not
4319 nonlocal_vars_id
= create_variable_info_for (nonlocal_all
,
4320 get_name (nonlocal_all
));
4321 nonlocal_vi
= get_varinfo (nonlocal_vars_id
);
4322 nonlocal_vi
->is_artificial_var
= 1;
4323 nonlocal_vi
->is_heap_var
= 1;
4324 nonlocal_vi
->is_unknown_size_var
= 1;
4325 nonlocal_vi
->directly_dereferenced
= true;
4327 rhs
.var
= nonlocal_vars_id
;
4328 rhs
.type
= ADDRESSOF
;
4331 lhs
.var
= escaped_vars_id
;
4335 process_constraint (new_constraint (lhs
, rhs
));
4338 /* Set bits in INTO corresponding to the variable uids in solution set
4339 FROM, which came from variable PTR.
4340 For variables that are actually dereferenced, we also use type
4341 based alias analysis to prune the points-to sets. */
4344 set_uids_in_ptset (tree ptr
, bitmap into
, bitmap from
)
4349 unsigned HOST_WIDE_INT ptr_alias_set
= get_alias_set (TREE_TYPE (ptr
));
4351 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
4353 varinfo_t vi
= get_varinfo (i
);
4354 unsigned HOST_WIDE_INT var_alias_set
;
4356 /* The only artificial variables that are allowed in a may-alias
4357 set are heap variables. */
4358 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
4361 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
4363 /* Variables containing unions may need to be converted to
4364 their SFT's, because SFT's can have unions and we cannot. */
4365 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
4366 bitmap_set_bit (into
, DECL_UID (sv
->var
));
4368 else if (TREE_CODE (vi
->decl
) == VAR_DECL
4369 || TREE_CODE (vi
->decl
) == PARM_DECL
)
4371 if (var_can_have_subvars (vi
->decl
)
4372 && get_subvars_for_var (vi
->decl
))
4374 /* If VI->DECL is an aggregate for which we created
4375 SFTs, add the SFT corresponding to VI->OFFSET. */
4376 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
4379 var_alias_set
= get_alias_set (sft
);
4380 if (!vi
->directly_dereferenced
4381 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
4382 bitmap_set_bit (into
, DECL_UID (sft
));
4387 /* Otherwise, just add VI->DECL to the alias set.
4388 Don't type prune artificial vars. */
4389 if (vi
->is_artificial_var
)
4390 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4393 var_alias_set
= get_alias_set (vi
->decl
);
4394 if (!vi
->directly_dereferenced
4395 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
4396 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4404 static bool have_alias_info
= false;
4406 /* Given a pointer variable P, fill in its points-to set, or return
4407 false if we can't. */
4410 find_what_p_points_to (tree p
)
4412 unsigned int id
= 0;
4415 if (!have_alias_info
)
4418 /* For parameters, get at the points-to set for the actual parm
4420 if (TREE_CODE (p
) == SSA_NAME
4421 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
4422 && default_def (SSA_NAME_VAR (p
)) == p
)
4423 lookup_p
= SSA_NAME_VAR (p
);
4425 if (lookup_id_for_tree (lookup_p
, &id
))
4427 varinfo_t vi
= get_varinfo (id
);
4429 if (vi
->is_artificial_var
)
4432 /* See if this is a field or a structure. */
4433 if (vi
->size
!= vi
->fullsize
)
4435 /* Nothing currently asks about structure fields directly,
4436 but when they do, we need code here to hand back the
4438 if (!var_can_have_subvars (vi
->decl
)
4439 || get_subvars_for_var (vi
->decl
) == NULL
)
4444 struct ptr_info_def
*pi
= get_ptr_info (p
);
4448 /* This variable may have been collapsed, let's get the real
4450 vi
= get_varinfo (vi
->node
);
4452 /* Translate artificial variables into SSA_NAME_PTR_INFO
4454 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4456 varinfo_t vi
= get_varinfo (i
);
4458 if (vi
->is_artificial_var
)
4460 /* FIXME. READONLY should be handled better so that
4461 flow insensitive aliasing can disregard writable
4463 if (vi
->id
== nothing_id
)
4465 else if (vi
->id
== anything_id
)
4466 pi
->pt_anything
= 1;
4467 else if (vi
->id
== readonly_id
)
4468 pi
->pt_anything
= 1;
4469 else if (vi
->id
== integer_id
)
4470 pi
->pt_anything
= 1;
4471 else if (vi
->is_heap_var
)
4472 pi
->pt_global_mem
= 1;
4476 if (pi
->pt_anything
)
4480 pi
->pt_vars
= BITMAP_GGC_ALLOC ();
4482 set_uids_in_ptset (vi
->decl
, pi
->pt_vars
, vi
->solution
);
4484 if (bitmap_empty_p (pi
->pt_vars
))
4496 /* Dump points-to information to OUTFILE. */
4499 dump_sa_points_to_info (FILE *outfile
)
4503 fprintf (outfile
, "\nPoints-to sets\n\n");
4505 if (dump_flags
& TDF_STATS
)
4507 fprintf (outfile
, "Stats:\n");
4508 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4509 fprintf (outfile
, "Statically unified vars: %d\n",
4510 stats
.unified_vars_static
);
4511 fprintf (outfile
, "Collapsed vars: %d\n", stats
.collapsed_vars
);
4512 fprintf (outfile
, "Dynamically unified vars: %d\n",
4513 stats
.unified_vars_dynamic
);
4514 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4515 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4518 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4519 dump_solution_for_var (outfile
, i
);
4523 /* Debug points-to information to stderr. */
4526 debug_sa_points_to_info (void)
4528 dump_sa_points_to_info (stderr
);
4532 /* Initialize the always-existing constraint variables for NULL
4533 ANYTHING, READONLY, and INTEGER */
4536 init_base_vars (void)
4538 struct constraint_expr lhs
, rhs
;
4540 /* Create the NULL variable, used to represent that a variable points
4542 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4543 var_nothing
= new_var_info (nothing_tree
, 0, "NULL", 0);
4544 insert_id_for_tree (nothing_tree
, 0);
4545 var_nothing
->is_artificial_var
= 1;
4546 var_nothing
->offset
= 0;
4547 var_nothing
->size
= ~0;
4548 var_nothing
->fullsize
= ~0;
4549 var_nothing
->is_special_var
= 1;
4551 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4553 /* Create the ANYTHING variable, used to represent that a variable
4554 points to some unknown piece of memory. */
4555 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4556 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING", 1);
4557 insert_id_for_tree (anything_tree
, 1);
4558 var_anything
->is_artificial_var
= 1;
4559 var_anything
->size
= ~0;
4560 var_anything
->offset
= 0;
4561 var_anything
->next
= NULL
;
4562 var_anything
->fullsize
= ~0;
4563 var_anything
->is_special_var
= 1;
4566 /* Anything points to anything. This makes deref constraints just
4567 work in the presence of linked list and other p = *p type loops,
4568 by saying that *ANYTHING = ANYTHING. */
4569 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4571 lhs
.var
= anything_id
;
4573 rhs
.type
= ADDRESSOF
;
4574 rhs
.var
= anything_id
;
4576 var_anything
->address_taken
= true;
4578 /* This specifically does not use process_constraint because
4579 process_constraint ignores all anything = anything constraints, since all
4580 but this one are redundant. */
4581 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4583 /* Create the READONLY variable, used to represent that a variable
4584 points to readonly memory. */
4585 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4586 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY", 2);
4587 var_readonly
->is_artificial_var
= 1;
4588 var_readonly
->offset
= 0;
4589 var_readonly
->size
= ~0;
4590 var_readonly
->fullsize
= ~0;
4591 var_readonly
->next
= NULL
;
4592 var_readonly
->is_special_var
= 1;
4593 insert_id_for_tree (readonly_tree
, 2);
4595 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4597 /* readonly memory points to anything, in order to make deref
4598 easier. In reality, it points to anything the particular
4599 readonly variable can point to, but we don't track this
4602 lhs
.var
= readonly_id
;
4604 rhs
.type
= ADDRESSOF
;
4605 rhs
.var
= anything_id
;
4608 process_constraint (new_constraint (lhs
, rhs
));
4610 /* Create the INTEGER variable, used to represent that a variable points
4612 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4613 var_integer
= new_var_info (integer_tree
, 3, "INTEGER", 3);
4614 insert_id_for_tree (integer_tree
, 3);
4615 var_integer
->is_artificial_var
= 1;
4616 var_integer
->size
= ~0;
4617 var_integer
->fullsize
= ~0;
4618 var_integer
->offset
= 0;
4619 var_integer
->next
= NULL
;
4620 var_integer
->is_special_var
= 1;
4622 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4624 /* INTEGER = ANYTHING, because we don't know where a dereference of
4625 a random integer will point to. */
4627 lhs
.var
= integer_id
;
4629 rhs
.type
= ADDRESSOF
;
4630 rhs
.var
= anything_id
;
4632 process_constraint (new_constraint (lhs
, rhs
));
4634 /* Create the ESCAPED_VARS variable used to represent variables that
4635 escape this function. */
4636 escaped_vars_tree
= create_tmp_var_raw (void_type_node
, "ESCAPED_VARS");
4637 var_escaped_vars
= new_var_info (escaped_vars_tree
, 4, "ESCAPED_VARS", 4);
4638 insert_id_for_tree (escaped_vars_tree
, 4);
4639 var_escaped_vars
->is_artificial_var
= 1;
4640 var_escaped_vars
->size
= ~0;
4641 var_escaped_vars
->fullsize
= ~0;
4642 var_escaped_vars
->offset
= 0;
4643 var_escaped_vars
->next
= NULL
;
4644 escaped_vars_id
= 4;
4645 VEC_safe_push (varinfo_t
, heap
, varmap
, var_escaped_vars
);
4647 /* ESCAPED_VARS = *ESCAPED_VARS */
4649 lhs
.var
= escaped_vars_id
;
4652 rhs
.var
= escaped_vars_id
;
4654 process_constraint (new_constraint (lhs
, rhs
));
4658 /* Initialize things necessary to perform PTA */
4661 init_alias_vars (void)
4663 bitmap_obstack_initialize (&ptabitmap_obstack
);
4664 bitmap_obstack_initialize (&predbitmap_obstack
);
4666 constraint_pool
= create_alloc_pool ("Constraint pool",
4667 sizeof (struct constraint
), 30);
4668 variable_info_pool
= create_alloc_pool ("Variable info pool",
4669 sizeof (struct variable_info
), 30);
4670 constraint_edge_pool
= create_alloc_pool ("Constraint edges",
4671 sizeof (struct constraint_edge
), 30);
4673 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4674 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4675 id_for_tree
= htab_create (10, tree_id_hash
, tree_id_eq
, free
);
4676 memset (&stats
, 0, sizeof (stats
));
4681 /* Given a statement STMT, generate necessary constraints to
4682 escaped_vars for the escaping variables. */
4685 find_escape_constraints (tree stmt
)
4687 enum escape_type stmt_escape_type
= is_escape_site (stmt
);
4689 VEC(ce_s
, heap
) *rhsc
= NULL
;
4690 struct constraint_expr
*c
;
4693 if (stmt_escape_type
== NO_ESCAPE
)
4696 if (TREE_CODE (stmt
) == RETURN_EXPR
)
4698 /* Returns are either bare, with an embedded MODIFY_EXPR, or
4699 just a plain old expression. */
4700 if (!TREE_OPERAND (stmt
, 0))
4702 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
4703 rhs
= TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
4705 rhs
= TREE_OPERAND (stmt
, 0);
4707 get_constraint_for (rhs
, &rhsc
);
4708 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
4709 make_constraint_to_escaped (*c
);
4710 VEC_free (ce_s
, heap
, rhsc
);
4713 else if (TREE_CODE (stmt
) == ASM_EXPR
)
4715 /* Whatever the inputs of the ASM are, escape. */
4718 for (arg
= ASM_INPUTS (stmt
); arg
; arg
= TREE_CHAIN (arg
))
4721 get_constraint_for (TREE_VALUE (arg
), &rhsc
);
4722 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
4723 make_constraint_to_escaped (*c
);
4724 VEC_free (ce_s
, heap
, rhsc
);
4728 else if (TREE_CODE (stmt
) == CALL_EXPR
4729 || (TREE_CODE (stmt
) == MODIFY_EXPR
4730 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
))
4732 /* Calls cause all of the arguments passed in to escape. */
4735 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
4736 stmt
= TREE_OPERAND (stmt
, 1);
4737 for (arg
= TREE_OPERAND (stmt
, 1); arg
; arg
= TREE_CHAIN (arg
))
4739 if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg
))))
4742 get_constraint_for (TREE_VALUE (arg
), &rhsc
);
4743 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
4744 make_constraint_to_escaped (*c
);
4745 VEC_free (ce_s
, heap
, rhsc
);
4752 gcc_assert (TREE_CODE (stmt
) == MODIFY_EXPR
);
4755 gcc_assert (stmt_escape_type
== ESCAPE_BAD_CAST
4756 || stmt_escape_type
== ESCAPE_STORED_IN_GLOBAL
4757 || stmt_escape_type
== ESCAPE_UNKNOWN
);
4758 rhs
= TREE_OPERAND (stmt
, 1);
4760 /* Look through casts for the real escaping variable.
4761 Constants don't really escape, so ignore them.
4762 Otherwise, whatever escapes must be on our RHS. */
4763 if (TREE_CODE (rhs
) == NOP_EXPR
4764 || TREE_CODE (rhs
) == CONVERT_EXPR
4765 || TREE_CODE (rhs
) == NON_LVALUE_EXPR
)
4767 get_constraint_for (TREE_OPERAND (rhs
, 0), &rhsc
);
4769 else if (CONSTANT_CLASS_P (rhs
))
4773 get_constraint_for (rhs
, &rhsc
);
4775 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
4776 make_constraint_to_escaped (*c
);
4777 VEC_free (ce_s
, heap
, rhsc
);
4780 /* Create points-to sets for the current function. See the comments
4781 at the start of the file for an algorithmic overview. */
4784 compute_points_to_sets (struct alias_info
*ai
)
4788 timevar_push (TV_TREE_PTA
);
4792 intra_create_variable_infos ();
4794 /* Now walk all statements and derive aliases. */
4797 block_stmt_iterator bsi
;
4800 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4802 if (is_gimple_reg (PHI_RESULT (phi
)))
4804 find_func_aliases (phi
);
4805 /* Update various related attributes like escaped
4806 addresses, pointer dereferences for loads and stores.
4807 This is used when creating name tags and alias
4809 update_alias_info (phi
, ai
);
4813 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4815 tree stmt
= bsi_stmt (bsi
);
4817 find_func_aliases (stmt
);
4818 find_escape_constraints (stmt
);
4819 /* Update various related attributes like escaped
4820 addresses, pointer dereferences for loads and stores.
4821 This is used when creating name tags and alias
4823 update_alias_info (stmt
, ai
);
4827 build_constraint_graph ();
4831 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4832 dump_constraints (dump_file
);
4837 "\nCollapsing static cycles and doing variable "
4840 find_and_collapse_graph_cycles (graph
, false);
4841 perform_var_substitution (graph
);
4844 fprintf (dump_file
, "\nSolving graph:\n");
4846 solve_graph (graph
);
4849 dump_sa_points_to_info (dump_file
);
4851 have_alias_info
= true;
4853 timevar_pop (TV_TREE_PTA
);
4857 /* Delete created points-to sets. */
4860 delete_points_to_sets (void)
4865 htab_delete (id_for_tree
);
4866 bitmap_obstack_release (&ptabitmap_obstack
);
4867 bitmap_obstack_release (&predbitmap_obstack
);
4868 VEC_free (constraint_t
, heap
, constraints
);
4870 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4872 /* Nonlocal vars may add more varinfos. */
4873 if (i
>= graph_size
)
4876 VEC_free (constraint_edge_t
, heap
, graph
->succs
[i
]);
4877 VEC_free (constraint_edge_t
, heap
, graph
->preds
[i
]);
4878 VEC_free (constraint_t
, heap
, v
->complex);
4880 free (graph
->zero_weight_preds
);
4881 free (graph
->zero_weight_succs
);
4882 free (graph
->succs
);
4883 free (graph
->preds
);
4886 VEC_free (varinfo_t
, heap
, varmap
);
4887 free_alloc_pool (variable_info_pool
);
4888 free_alloc_pool (constraint_pool
);
4889 free_alloc_pool (constraint_edge_pool
);
4891 have_alias_info
= false;
4894 /* Return true if we should execute IPA PTA. */
4898 return (flag_unit_at_a_time
!= 0
4900 /* Don't bother doing anything if the program has errors. */
4901 && !(errorcount
|| sorrycount
));
4904 /* Execute the driver for IPA PTA. */
4906 ipa_pta_execute (void)
4908 struct cgraph_node
*node
;
4910 init_alias_heapvars ();
4913 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4915 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
4919 varid
= create_function_info_for (node
->decl
,
4920 cgraph_node_name (node
));
4921 if (node
->local
.externally_visible
)
4923 varinfo_t fi
= get_varinfo (varid
);
4924 for (; fi
; fi
= fi
->next
)
4925 make_constraint_from_escaped (fi
);
4929 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4931 if (node
->analyzed
&& cgraph_is_master_clone (node
))
4933 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
4935 tree old_func_decl
= current_function_decl
;
4938 "Generating constraints for %s\n",
4939 cgraph_node_name (node
));
4941 current_function_decl
= node
->decl
;
4943 FOR_EACH_BB_FN (bb
, cfun
)
4945 block_stmt_iterator bsi
;
4948 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4950 if (is_gimple_reg (PHI_RESULT (phi
)))
4952 find_func_aliases (phi
);
4956 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4958 tree stmt
= bsi_stmt (bsi
);
4959 find_func_aliases (stmt
);
4962 current_function_decl
= old_func_decl
;
4967 /* Make point to anything. */
4971 build_constraint_graph ();
4975 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4976 dump_constraints (dump_file
);
4981 "\nCollapsing static cycles and doing variable "
4984 find_and_collapse_graph_cycles (graph
, false);
4985 perform_var_substitution (graph
);
4988 fprintf (dump_file
, "\nSolving graph:\n");
4990 solve_graph (graph
);
4993 dump_sa_points_to_info (dump_file
);
4995 delete_alias_heapvars ();
4996 delete_points_to_sets ();
5000 struct tree_opt_pass pass_ipa_pta
=
5003 gate_ipa_pta
, /* gate */
5004 ipa_pta_execute
, /* execute */
5007 0, /* static_pass_number */
5008 TV_IPA_PTA
, /* tv_id */
5009 0, /* properties_required */
5010 0, /* properties_provided */
5011 0, /* properties_destroyed */
5012 0, /* todo_flags_start */
5013 0, /* todo_flags_finish */
5017 /* Initialize the heapvar for statement mapping. */
5019 init_alias_heapvars (void)
5021 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
,
5023 nonlocal_all
= NULL_TREE
;
5027 delete_alias_heapvars (void)
5029 nonlocal_all
= NULL_TREE
;
5030 htab_delete (heapvar_for_stmt
);
5034 #include "gt-tree-ssa-structalias.h"