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
125 and offsets (including offsetted copies).
127 3. All direct constraints of the form P = &Q are processed, such
128 that Q is added to Sol(P)
130 4. All complex constraints for a given constraint variable are stored in a
131 linked list attached to that variable's node.
133 5. A directed graph is built out of the copy constraints. Each
134 constraint variable is a node in the graph, and an edge from
135 Q to P is added for each copy constraint of the form P = Q
137 6. The graph is then walked, and solution sets are
138 propagated along the copy edges, such that an edge from Q to P
139 causes Sol(P) <- Sol(P) union Sol(Q).
141 7. As we visit each node, all complex constraints associated with
142 that node are processed by adding appropriate copy edges to the graph, or the
143 appropriate variables to the solution set.
145 8. The process of walking the graph is iterated until no solution
148 Prior to walking the graph in steps 6 and 7, We perform static
149 cycle elimination on the constraint graph, as well
150 as off-line variable substitution.
152 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
153 on and turned into anything), but isn't. You can just see what offset
154 inside the pointed-to struct it's going to access.
156 TODO: Constant bounded arrays can be handled as if they were structs of the
157 same number of elements.
159 TODO: Modeling heap and incoming pointers becomes much better if we
160 add fields to them as we discover them, which we could do.
162 TODO: We could handle unions, but to be honest, it's probably not
163 worth the pain or slowdown. */
165 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map
)))
166 htab_t heapvar_for_stmt
;
168 static bool use_field_sensitive
= true;
169 static int in_ipa_mode
= 0;
170 static bitmap_obstack predbitmap_obstack
;
171 static bitmap_obstack ptabitmap_obstack
;
172 static bitmap_obstack iteration_obstack
;
174 static unsigned int create_variable_info_for (tree
, const char *);
175 static void build_constraint_graph (void);
177 DEF_VEC_P(constraint_t
);
178 DEF_VEC_ALLOC_P(constraint_t
,heap
);
180 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
182 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
184 static struct constraint_stats
186 unsigned int total_vars
;
187 unsigned int collapsed_vars
;
188 unsigned int unified_vars_static
;
189 unsigned int unified_vars_dynamic
;
190 unsigned int iterations
;
191 unsigned int num_edges
;
196 /* ID of this variable */
199 /* Name of this variable */
202 /* Tree that this variable is associated with. */
205 /* Offset of this variable, in bits, from the base variable */
206 unsigned HOST_WIDE_INT offset
;
208 /* Size of the variable, in bits. */
209 unsigned HOST_WIDE_INT size
;
211 /* Full size of the base variable, in bits. */
212 unsigned HOST_WIDE_INT fullsize
;
214 /* A link to the variable for the next field in this structure. */
215 struct variable_info
*next
;
217 /* Node in the graph that represents the constraints and points-to
218 solution for the variable. */
221 /* True if the address of this variable is taken. Needed for
222 variable substitution. */
223 unsigned int address_taken
:1;
225 /* True if this variable is the target of a dereference. Needed for
226 variable substitution. */
227 unsigned int indirect_target
:1;
229 /* True if the variable is directly the target of a dereference.
230 This is used to track which variables are *actually* dereferenced
231 so we can prune their points to listed. This is equivalent to the
232 indirect_target flag when no merging of variables happens. */
233 unsigned int directly_dereferenced
:1;
235 /* True if this is a variable created by the constraint analysis, such as
236 heap variables and constraints we had to break up. */
237 unsigned int is_artificial_var
:1;
239 /* True if this is a special variable whose solution set should not be
241 unsigned int is_special_var
:1;
243 /* True for variables whose size is not known or variable. */
244 unsigned int is_unknown_size_var
:1;
246 /* True for variables that have unions somewhere in them. */
247 unsigned int has_union
:1;
249 /* True if this is a heap variable. */
250 unsigned int is_heap_var
:1;
252 /* Points-to set for this variable. */
255 /* Variable ids represented by this node. */
258 /* Vector of complex constraints for this node. Complex
259 constraints are those involving dereferences. */
260 VEC(constraint_t
,heap
) *complex;
262 /* Variable id this was collapsed to due to type unsafety.
263 This should be unused completely after build_constraint_graph, or
264 something is broken. */
265 struct variable_info
*collapsed_to
;
267 typedef struct variable_info
*varinfo_t
;
269 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
271 /* Pool of variable info structures. */
272 static alloc_pool variable_info_pool
;
274 DEF_VEC_P(varinfo_t
);
276 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
278 /* Table of variable info structures for constraint variables. Indexed directly
279 by variable info id. */
280 static VEC(varinfo_t
,heap
) *varmap
;
282 /* Return the varmap element N */
284 static inline varinfo_t
285 get_varinfo (unsigned int n
)
287 return VEC_index(varinfo_t
, varmap
, n
);
290 /* Return the varmap element N, following the collapsed_to link. */
292 static inline varinfo_t
293 get_varinfo_fc (unsigned int n
)
295 varinfo_t v
= VEC_index(varinfo_t
, varmap
, n
);
298 return v
->collapsed_to
;
302 /* Variable that represents the unknown pointer. */
303 static varinfo_t var_anything
;
304 static tree anything_tree
;
305 static unsigned int anything_id
;
307 /* Variable that represents the NULL pointer. */
308 static varinfo_t var_nothing
;
309 static tree nothing_tree
;
310 static unsigned int nothing_id
;
312 /* Variable that represents read only memory. */
313 static varinfo_t var_readonly
;
314 static tree readonly_tree
;
315 static unsigned int readonly_id
;
317 /* Variable that represents integers. This is used for when people do things
319 static varinfo_t var_integer
;
320 static tree integer_tree
;
321 static unsigned int integer_id
;
323 /* Variable that represents escaped variables. This is used to give
324 incoming pointer variables a better set than ANYTHING. */
325 static varinfo_t var_escaped_vars
;
326 static tree escaped_vars_tree
;
327 static unsigned int escaped_vars_id
;
329 /* Variable that represents non-local variables before we expand it to
330 one for each type. */
331 static unsigned int nonlocal_vars_id
;
333 /* Lookup a heap var for FROM, and return it if we find one. */
336 heapvar_lookup (tree from
)
338 struct tree_map
*h
, in
;
341 h
= htab_find_with_hash (heapvar_for_stmt
, &in
, htab_hash_pointer (from
));
347 /* Insert a mapping FROM->TO in the heap var for statement
351 heapvar_insert (tree from
, tree to
)
356 h
= ggc_alloc (sizeof (struct tree_map
));
357 h
->hash
= htab_hash_pointer (from
);
360 loc
= htab_find_slot_with_hash (heapvar_for_stmt
, h
, h
->hash
, INSERT
);
361 *(struct tree_map
**) loc
= h
;
364 /* Return a new variable info structure consisting for a variable
365 named NAME, and using constraint graph node NODE. */
368 new_var_info (tree t
, unsigned int id
, const char *name
, unsigned int node
)
370 varinfo_t ret
= pool_alloc (variable_info_pool
);
376 ret
->address_taken
= false;
377 ret
->indirect_target
= false;
378 ret
->directly_dereferenced
= false;
379 ret
->is_artificial_var
= false;
380 ret
->is_heap_var
= false;
381 ret
->is_special_var
= false;
382 ret
->is_unknown_size_var
= false;
383 ret
->has_union
= false;
384 ret
->solution
= BITMAP_ALLOC (&ptabitmap_obstack
);
385 ret
->variables
= BITMAP_ALLOC (&ptabitmap_obstack
);
388 ret
->collapsed_to
= NULL
;
392 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
394 /* An expression that appears in a constraint. */
396 struct constraint_expr
398 /* Constraint type. */
399 constraint_expr_type type
;
401 /* Variable we are referring to in the constraint. */
404 /* Offset, in bits, of this constraint from the beginning of
405 variables it ends up referring to.
407 IOW, in a deref constraint, we would deref, get the result set,
408 then add OFFSET to each member. */
409 unsigned HOST_WIDE_INT offset
;
412 typedef struct constraint_expr ce_s
;
414 DEF_VEC_ALLOC_O(ce_s
, heap
);
415 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
416 static void do_deref (VEC (ce_s
, heap
) **);
418 /* Our set constraints are made up of two constraint expressions, one
421 As described in the introduction, our set constraints each represent an
422 operation between set valued variables.
426 struct constraint_expr lhs
;
427 struct constraint_expr rhs
;
430 /* List of constraints that we use to build the constraint graph from. */
432 static VEC(constraint_t
,heap
) *constraints
;
433 static alloc_pool constraint_pool
;
436 /* The constraint graph is represented as an array of bitmaps
437 containing successor nodes. */
439 struct constraint_graph
445 typedef struct constraint_graph
*constraint_graph_t
;
447 static constraint_graph_t graph
;
448 static int graph_size
;
450 /* Create a new constraint consisting of LHS and RHS expressions. */
453 new_constraint (const struct constraint_expr lhs
,
454 const struct constraint_expr rhs
)
456 constraint_t ret
= pool_alloc (constraint_pool
);
462 /* Print out constraint C to FILE. */
465 dump_constraint (FILE *file
, constraint_t c
)
467 if (c
->lhs
.type
== ADDRESSOF
)
469 else if (c
->lhs
.type
== DEREF
)
471 fprintf (file
, "%s", get_varinfo_fc (c
->lhs
.var
)->name
);
472 if (c
->lhs
.offset
!= 0)
473 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
474 fprintf (file
, " = ");
475 if (c
->rhs
.type
== ADDRESSOF
)
477 else if (c
->rhs
.type
== DEREF
)
479 fprintf (file
, "%s", get_varinfo_fc (c
->rhs
.var
)->name
);
480 if (c
->rhs
.offset
!= 0)
481 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
482 fprintf (file
, "\n");
485 /* Print out constraint C to stderr. */
488 debug_constraint (constraint_t c
)
490 dump_constraint (stderr
, c
);
493 /* Print out all constraints to FILE */
496 dump_constraints (FILE *file
)
500 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
501 dump_constraint (file
, c
);
504 /* Print out all constraints to stderr. */
507 debug_constraints (void)
509 dump_constraints (stderr
);
514 The solver is a simple worklist solver, that works on the following
517 sbitmap changed_nodes = all ones;
518 changed_count = number of nodes;
519 For each node that was already collapsed:
522 while (changed_count > 0)
524 compute topological ordering for constraint graph
526 find and collapse cycles in the constraint graph (updating
527 changed if necessary)
529 for each node (n) in the graph in topological order:
532 Process each complex constraint associated with the node,
533 updating changed if necessary.
535 For each outgoing edge from n, propagate the solution from n to
536 the destination of the edge, updating changed as necessary.
540 /* Return true if two constraint expressions A and B are equal. */
543 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
545 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
548 /* Return true if constraint expression A is less than constraint expression
549 B. This is just arbitrary, but consistent, in order to give them an
553 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
555 if (a
.type
== b
.type
)
558 return a
.offset
< b
.offset
;
560 return a
.var
< b
.var
;
563 return a
.type
< b
.type
;
566 /* Return true if constraint A is less than constraint B. This is just
567 arbitrary, but consistent, in order to give them an ordering. */
570 constraint_less (const constraint_t a
, const constraint_t b
)
572 if (constraint_expr_less (a
->lhs
, b
->lhs
))
574 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
577 return constraint_expr_less (a
->rhs
, b
->rhs
);
580 /* Return true if two constraints A and B are equal. */
583 constraint_equal (struct constraint a
, struct constraint b
)
585 return constraint_expr_equal (a
.lhs
, b
.lhs
)
586 && constraint_expr_equal (a
.rhs
, b
.rhs
);
590 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
593 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
594 struct constraint lookfor
)
602 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
603 if (place
>= VEC_length (constraint_t
, vec
))
605 found
= VEC_index (constraint_t
, vec
, place
);
606 if (!constraint_equal (*found
, lookfor
))
611 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
614 constraint_set_union (VEC(constraint_t
,heap
) **to
,
615 VEC(constraint_t
,heap
) **from
)
620 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
622 if (constraint_vec_find (*to
, *c
) == NULL
)
624 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
626 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
631 /* Take a solution set SET, add OFFSET to each member of the set, and
632 overwrite SET with the result when done. */
635 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
637 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
641 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
643 /* If this is a properly sized variable, only add offset if it's
644 less than end. Otherwise, it is globbed to a single
647 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
649 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
650 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
653 bitmap_set_bit (result
, v
->id
);
655 else if (get_varinfo (i
)->is_artificial_var
656 || get_varinfo (i
)->has_union
657 || get_varinfo (i
)->is_unknown_size_var
)
659 bitmap_set_bit (result
, i
);
663 bitmap_copy (set
, result
);
664 BITMAP_FREE (result
);
667 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
671 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
674 return bitmap_ior_into (to
, from
);
680 tmp
= BITMAP_ALLOC (&iteration_obstack
);
681 bitmap_copy (tmp
, from
);
682 solution_set_add (tmp
, inc
);
683 res
= bitmap_ior_into (to
, tmp
);
689 /* Insert constraint C into the list of complex constraints for VAR. */
692 insert_into_complex (unsigned int var
, constraint_t c
)
694 varinfo_t vi
= get_varinfo (var
);
695 unsigned int place
= VEC_lower_bound (constraint_t
, vi
->complex, c
,
697 VEC_safe_insert (constraint_t
, heap
, vi
->complex, place
, c
);
701 /* Condense two variable nodes into a single variable node, by moving
702 all associated info from SRC to TO. */
705 condense_varmap_nodes (unsigned int to
, unsigned int src
)
707 varinfo_t tovi
= get_varinfo (to
);
708 varinfo_t srcvi
= get_varinfo (src
);
713 /* the src node, and all its variables, are now the to node. */
715 EXECUTE_IF_SET_IN_BITMAP (srcvi
->variables
, 0, i
, bi
)
716 get_varinfo (i
)->node
= to
;
718 /* Merge the src node variables and the to node variables. */
719 bitmap_set_bit (tovi
->variables
, src
);
720 bitmap_ior_into (tovi
->variables
, srcvi
->variables
);
721 bitmap_clear (srcvi
->variables
);
723 /* Move all complex constraints from src node into to node */
724 for (i
= 0; VEC_iterate (constraint_t
, srcvi
->complex, i
, c
); i
++)
726 /* In complex constraints for node src, we may have either
727 a = *src, and *src = a. */
729 if (c
->rhs
.type
== DEREF
)
734 constraint_set_union (&tovi
->complex, &srcvi
->complex);
735 VEC_free (constraint_t
, heap
, srcvi
->complex);
736 srcvi
->complex = NULL
;
740 /* Remove edges involving NODE from GRAPH. */
743 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
748 /* Walk the successors, erase the associated preds. */
750 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[node
], 0, j
, bi
)
752 bitmap_clear_bit (graph
->preds
[j
], node
);
755 /* Walk the preds, erase the associated succs. */
757 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[node
], 0, j
, bi
)
759 bitmap_clear_bit (graph
->succs
[j
], node
);
762 if (graph
->preds
[node
])
764 BITMAP_FREE (graph
->preds
[node
]);
765 graph
->preds
[node
] = NULL
;
768 if (graph
->succs
[node
])
770 BITMAP_FREE (graph
->succs
[node
]);
771 graph
->succs
[node
] = NULL
;
775 static bool edge_added
= false;
777 /* Merge GRAPH nodes FROM and TO into node TO. */
780 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
786 /* Merge all the predecessor edges. */
787 if (graph
->preds
[from
])
789 if (!graph
->preds
[to
])
790 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
792 EXECUTE_IF_SET_IN_BITMAP (graph
->preds
[from
], 0, j
, bi
)
796 bitmap_clear_bit (graph
->succs
[j
], from
);
797 bitmap_set_bit (graph
->succs
[j
], to
);
800 bitmap_ior_into (graph
->preds
[to
],
804 /* Merge all the successor edges. */
805 if (graph
->succs
[from
])
807 if (!graph
->succs
[to
])
808 graph
->succs
[to
] = BITMAP_ALLOC (&ptabitmap_obstack
);
809 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[from
], 0, j
, bi
)
811 bitmap_clear_bit (graph
->preds
[j
], from
);
812 bitmap_set_bit (graph
->preds
[j
], to
);
814 bitmap_ior_into (graph
->succs
[to
],
818 clear_edges_for_node (graph
, from
);
821 /* Add a graph edge to GRAPH, going from TO to FROM if
822 it doesn't exist in the graph already.
823 Return false if the edge already existed, true otherwise. */
826 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
837 if (!graph
->preds
[to
])
838 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
839 if (!graph
->succs
[from
])
840 graph
->succs
[from
] = BITMAP_ALLOC (&ptabitmap_obstack
);
841 if (!bitmap_bit_p (graph
->succs
[from
], to
))
846 bitmap_set_bit (graph
->preds
[to
], from
);
847 bitmap_set_bit (graph
->succs
[from
], to
);
854 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
857 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
860 return (graph
->succs
[dest
]
861 && bitmap_bit_p (graph
->succs
[dest
], src
));
864 /* Build the constraint graph. */
867 build_constraint_graph (void)
872 graph
= XNEW (struct constraint_graph
);
873 graph_size
= VEC_length (varinfo_t
, varmap
) + 1;
874 graph
->succs
= XCNEWVEC (bitmap
, graph_size
);
875 graph
->preds
= XCNEWVEC (bitmap
, graph_size
);
877 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
879 struct constraint_expr lhs
= c
->lhs
;
880 struct constraint_expr rhs
= c
->rhs
;
881 unsigned int lhsvar
= get_varinfo_fc (lhs
.var
)->id
;
882 unsigned int rhsvar
= get_varinfo_fc (rhs
.var
)->id
;
884 if (lhs
.type
== DEREF
)
886 /* *x = y or *x = &y (complex) */
887 if (rhs
.type
== ADDRESSOF
|| rhsvar
> anything_id
)
888 insert_into_complex (lhsvar
, c
);
890 else if (rhs
.type
== DEREF
)
892 /* !special var= *y */
893 if (!(get_varinfo (lhsvar
)->is_special_var
))
894 insert_into_complex (rhsvar
, c
);
896 else if (rhs
.type
== ADDRESSOF
)
899 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
901 else if (lhsvar
> anything_id
)
903 /* Ignore self edges, as they can't possibly contribute
905 if (lhsvar
!= rhsvar
|| rhs
.offset
!= 0 || lhs
.offset
!= 0)
907 if (rhs
.offset
!= 0 || lhs
.offset
!= 0)
908 insert_into_complex (lhsvar
, c
);
910 add_graph_edge (graph
, lhs
.var
, rhs
.var
);
918 /* Changed variables on the last iteration. */
919 static unsigned int changed_count
;
920 static sbitmap changed
;
923 DEF_VEC_ALLOC_I(unsigned,heap
);
926 /* Strongly Connected Component visitation info. */
931 sbitmap in_component
;
933 unsigned int *visited_index
;
934 VEC(unsigned,heap
) *scc_stack
;
935 VEC(unsigned,heap
) *unification_queue
;
939 /* Recursive routine to find strongly connected components in GRAPH.
940 SI is the SCC info to store the information in, and N is the id of current
941 graph node we are processing.
943 This is Tarjan's strongly connected component finding algorithm, as
944 modified by Nuutila to keep only non-root nodes on the stack.
945 The algorithm can be found in "On finding the strongly connected
946 connected components in a directed graph" by Esko Nuutila and Eljas
947 Soisalon-Soininen, in Information Processing Letters volume 49,
948 number 1, pages 9-14. */
951 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
956 gcc_assert (get_varinfo (n
)->node
== n
);
957 SET_BIT (si
->visited
, n
);
958 RESET_BIT (si
->in_component
, n
);
959 si
->visited_index
[n
] = si
->current_index
++;
961 /* Visit all the successors. */
962 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
965 if (!TEST_BIT (si
->visited
, w
))
966 scc_visit (graph
, si
, w
);
967 if (!TEST_BIT (si
->in_component
, w
))
969 unsigned int t
= get_varinfo (w
)->node
;
970 unsigned int nnode
= get_varinfo (n
)->node
;
971 if (si
->visited_index
[t
] < si
->visited_index
[nnode
])
972 get_varinfo (n
)->node
= t
;
976 /* See if any components have been identified. */
977 if (get_varinfo (n
)->node
== n
)
979 unsigned int t
= si
->visited_index
[n
];
980 SET_BIT (si
->in_component
, n
);
981 while (VEC_length (unsigned, si
->scc_stack
) != 0
982 && t
< si
->visited_index
[VEC_last (unsigned, si
->scc_stack
)])
984 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
985 get_varinfo (w
)->node
= n
;
986 SET_BIT (si
->in_component
, w
);
987 /* Mark this node for collapsing. */
988 VEC_safe_push (unsigned, heap
, si
->unification_queue
, w
);
992 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
996 /* Collapse two variables into one variable. */
999 collapse_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
)
1001 bitmap tosol
, fromsol
;
1003 condense_varmap_nodes (to
, from
);
1004 tosol
= get_varinfo (to
)->solution
;
1005 fromsol
= get_varinfo (from
)->solution
;
1006 bitmap_ior_into (tosol
, fromsol
);
1007 merge_graph_nodes (graph
, to
, from
);
1009 if (valid_graph_edge (graph
, to
, to
))
1011 if (graph
->preds
[to
])
1013 bitmap_clear_bit (graph
->preds
[to
], to
);
1014 bitmap_clear_bit (graph
->succs
[to
], to
);
1017 BITMAP_FREE (fromsol
);
1018 get_varinfo (to
)->address_taken
|= get_varinfo (from
)->address_taken
;
1019 get_varinfo (to
)->indirect_target
|= get_varinfo (from
)->indirect_target
;
1023 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1024 SI is the Strongly Connected Components information structure that tells us
1025 what components to unify.
1026 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1027 count should be updated to reflect the unification. */
1030 process_unification_queue (constraint_graph_t graph
, struct scc_info
*si
,
1031 bool update_changed
)
1034 bitmap tmp
= BITMAP_ALLOC (update_changed
? &iteration_obstack
: NULL
);
1037 /* We proceed as follows:
1039 For each component in the queue (components are delineated by
1040 when current_queue_element->node != next_queue_element->node):
1042 rep = representative node for component
1044 For each node (tounify) to be unified in the component,
1045 merge the solution for tounify into tmp bitmap
1047 clear solution for tounify
1049 merge edges from tounify into rep
1051 merge complex constraints from tounify into rep
1053 update changed count to note that tounify will never change
1056 Merge tmp into solution for rep, marking rep changed if this
1057 changed rep's solution.
1059 Delete any self-edges we now have for rep. */
1060 while (i
!= VEC_length (unsigned, si
->unification_queue
))
1062 unsigned int tounify
= VEC_index (unsigned, si
->unification_queue
, i
);
1063 unsigned int n
= get_varinfo (tounify
)->node
;
1065 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1066 fprintf (dump_file
, "Unifying %s to %s\n",
1067 get_varinfo (tounify
)->name
,
1068 get_varinfo (n
)->name
);
1070 stats
.unified_vars_dynamic
++;
1072 stats
.unified_vars_static
++;
1073 bitmap_ior_into (tmp
, get_varinfo (tounify
)->solution
);
1074 merge_graph_nodes (graph
, n
, tounify
);
1075 condense_varmap_nodes (n
, tounify
);
1077 if (update_changed
&& TEST_BIT (changed
, tounify
))
1079 RESET_BIT (changed
, tounify
);
1080 if (!TEST_BIT (changed
, n
))
1081 SET_BIT (changed
, n
);
1084 gcc_assert (changed_count
> 0);
1089 bitmap_clear (get_varinfo (tounify
)->solution
);
1092 /* If we've either finished processing the entire queue, or
1093 finished processing all nodes for component n, update the solution for
1095 if (i
== VEC_length (unsigned, si
->unification_queue
)
1096 || get_varinfo (VEC_index (unsigned, si
->unification_queue
, i
))->node
!= n
)
1098 /* If the solution changes because of the merging, we need to mark
1099 the variable as changed. */
1100 if (bitmap_ior_into (get_varinfo (n
)->solution
, tmp
))
1102 if (update_changed
&& !TEST_BIT (changed
, n
))
1104 SET_BIT (changed
, n
);
1110 if (valid_graph_edge (graph
, n
, n
))
1112 if (graph
->succs
[n
])
1114 if (graph
->preds
[n
])
1115 bitmap_clear_bit (graph
->preds
[n
], n
);
1116 bitmap_clear_bit (graph
->succs
[n
], n
);
1125 /* Information needed to compute the topological ordering of a graph. */
1129 /* sbitmap of visited nodes. */
1131 /* Array that stores the topological order of the graph, *in
1133 VEC(unsigned,heap
) *topo_order
;
1137 /* Initialize and return a topological info structure. */
1139 static struct topo_info
*
1140 init_topo_info (void)
1142 size_t size
= VEC_length (varinfo_t
, varmap
);
1143 struct topo_info
*ti
= XNEW (struct topo_info
);
1144 ti
->visited
= sbitmap_alloc (size
);
1145 sbitmap_zero (ti
->visited
);
1146 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1151 /* Free the topological sort info pointed to by TI. */
1154 free_topo_info (struct topo_info
*ti
)
1156 sbitmap_free (ti
->visited
);
1157 VEC_free (unsigned, heap
, ti
->topo_order
);
1161 /* Visit the graph in topological order, and store the order in the
1162 topo_info structure. */
1165 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1172 SET_BIT (ti
->visited
, n
);
1173 temp
= graph
->succs
[n
];
1176 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, j
, bi
)
1178 if (!TEST_BIT (ti
->visited
, j
))
1179 topo_visit (graph
, ti
, j
);
1181 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1184 /* Return true if variable N + OFFSET is a legal field of N. */
1187 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1189 varinfo_t ninfo
= get_varinfo (n
);
1191 /* For things we've globbed to single variables, any offset into the
1192 variable acts like the entire variable, so that it becomes offset
1194 if (ninfo
->is_special_var
1195 || ninfo
->is_artificial_var
1196 || ninfo
->is_unknown_size_var
)
1201 return (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1204 /* Process a constraint C that represents *x = &y. */
1207 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1208 constraint_t c
, bitmap delta
)
1210 unsigned int rhs
= c
->rhs
.var
;
1214 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1215 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1217 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1218 if (type_safe (j
, &offset
) && !(get_varinfo (j
)->is_special_var
))
1220 /* *x != NULL && *x != ANYTHING*/
1224 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1226 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1230 sol
= get_varinfo (t
)->solution
;
1231 if (!bitmap_bit_p (sol
, rhs
))
1233 bitmap_set_bit (sol
, rhs
);
1234 if (!TEST_BIT (changed
, t
))
1236 SET_BIT (changed
, t
);
1241 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1242 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1247 /* Process a constraint C that represents x = *y, using DELTA as the
1248 starting solution. */
1251 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1254 unsigned int lhs
= get_varinfo (c
->lhs
.var
)->node
;
1256 bitmap sol
= get_varinfo (lhs
)->solution
;
1260 if (bitmap_bit_p (delta
, anything_id
))
1262 flag
= !bitmap_bit_p (sol
, anything_id
);
1264 bitmap_set_bit (sol
, anything_id
);
1267 /* For each variable j in delta (Sol(y)), add
1268 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1269 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1271 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1272 if (type_safe (j
, &roffset
))
1275 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1278 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1283 /* Adding edges from the special vars is pointless.
1284 They don't have sets that can change. */
1285 if (get_varinfo (t
) ->is_special_var
)
1286 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1287 else if (add_graph_edge (graph
, lhs
, t
))
1288 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1290 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1291 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1296 /* If the LHS solution changed, mark the var as changed. */
1299 get_varinfo (lhs
)->solution
= sol
;
1300 if (!TEST_BIT (changed
, lhs
))
1302 SET_BIT (changed
, lhs
);
1308 /* Process a constraint C that represents *x = y. */
1311 do_ds_constraint (constraint_t c
, bitmap delta
)
1313 unsigned int rhs
= get_varinfo (c
->rhs
.var
)->node
;
1314 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1315 bitmap sol
= get_varinfo (rhs
)->solution
;
1319 if (bitmap_bit_p (sol
, anything_id
))
1321 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1323 varinfo_t jvi
= get_varinfo (j
);
1325 unsigned int loff
= c
->lhs
.offset
;
1326 unsigned HOST_WIDE_INT fieldoffset
= jvi
->offset
+ loff
;
1329 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1334 if (!bitmap_bit_p (get_varinfo (t
)->solution
, anything_id
))
1336 bitmap_set_bit (get_varinfo (t
)->solution
, anything_id
);
1337 if (!TEST_BIT (changed
, t
))
1339 SET_BIT (changed
, t
);
1347 /* For each member j of delta (Sol(x)), add an edge from y to j and
1348 union Sol(y) into Sol(j) */
1349 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1351 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1352 if (type_safe (j
, &loff
) && !(get_varinfo(j
)->is_special_var
))
1356 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1359 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1363 tmp
= get_varinfo (t
)->solution
;
1365 if (set_union_with_increment (tmp
, sol
, roff
))
1367 get_varinfo (t
)->solution
= tmp
;
1369 sol
= get_varinfo (rhs
)->solution
;
1370 if (!TEST_BIT (changed
, t
))
1372 SET_BIT (changed
, t
);
1377 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1378 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1382 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1383 constraint (IE *x = &y, x = *y, and *x = y). */
1386 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1388 if (c
->lhs
.type
== DEREF
)
1390 if (c
->rhs
.type
== ADDRESSOF
)
1393 do_da_constraint (graph
, c
, delta
);
1398 do_ds_constraint (c
, delta
);
1401 else if (c
->rhs
.type
== DEREF
)
1404 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1405 do_sd_constraint (graph
, c
, delta
);
1414 gcc_assert(c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
);
1415 t
= get_varinfo (c
->rhs
.var
)->node
;
1416 solution
= get_varinfo (t
)->solution
;
1417 t
= get_varinfo (c
->lhs
.var
)->node
;
1418 tmp
= get_varinfo (t
)->solution
;
1420 flag
= set_union_with_increment (tmp
, solution
, c
->rhs
.offset
);
1424 get_varinfo (t
)->solution
= tmp
;
1425 if (!TEST_BIT (changed
, c
->lhs
.var
))
1427 SET_BIT (changed
, c
->lhs
.var
);
1434 /* Initialize and return a new SCC info structure. */
1436 static struct scc_info
*
1437 init_scc_info (void)
1439 struct scc_info
*si
= XNEW (struct scc_info
);
1440 size_t size
= VEC_length (varinfo_t
, varmap
);
1442 si
->current_index
= 0;
1443 si
->visited
= sbitmap_alloc (size
);
1444 sbitmap_zero (si
->visited
);
1445 si
->in_component
= sbitmap_alloc (size
);
1446 sbitmap_ones (si
->in_component
);
1447 si
->visited_index
= XCNEWVEC (unsigned int, size
+ 1);
1448 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1449 si
->unification_queue
= VEC_alloc (unsigned, heap
, 1);
1453 /* Free an SCC info structure pointed to by SI */
1456 free_scc_info (struct scc_info
*si
)
1458 sbitmap_free (si
->visited
);
1459 sbitmap_free (si
->in_component
);
1460 free (si
->visited_index
);
1461 VEC_free (unsigned, heap
, si
->scc_stack
);
1462 VEC_free (unsigned, heap
, si
->unification_queue
);
1467 /* Find cycles in GRAPH that occur, using strongly connected components, and
1468 collapse the cycles into a single representative node. if UPDATE_CHANGED
1469 is true, then update the changed sbitmap to note those nodes whose
1470 solutions have changed as a result of collapsing. */
1473 find_and_collapse_graph_cycles (constraint_graph_t graph
, bool update_changed
)
1476 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1477 struct scc_info
*si
= init_scc_info ();
1479 for (i
= 0; i
!= size
; ++i
)
1480 if (!TEST_BIT (si
->visited
, i
) && get_varinfo (i
)->node
== i
)
1481 scc_visit (graph
, si
, i
);
1483 process_unification_queue (graph
, si
, update_changed
);
1487 /* Compute a topological ordering for GRAPH, and store the result in the
1488 topo_info structure TI. */
1491 compute_topo_order (constraint_graph_t graph
,
1492 struct topo_info
*ti
)
1495 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1497 for (i
= 0; i
!= size
; ++i
)
1498 if (!TEST_BIT (ti
->visited
, i
) && get_varinfo (i
)->node
== i
)
1499 topo_visit (graph
, ti
, i
);
1502 /* Perform offline variable substitution.
1504 This is a linear time way of identifying variables that must have
1505 equivalent points-to sets, including those caused by static cycles,
1506 and single entry subgraphs, in the constraint graph.
1508 The technique is described in "Off-line variable substitution for
1509 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1510 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1513 perform_var_substitution (constraint_graph_t graph
)
1515 struct topo_info
*ti
= init_topo_info ();
1517 bitmap_obstack_initialize (&iteration_obstack
);
1518 /* Compute the topological ordering of the graph, then visit each
1519 node in topological order. */
1520 compute_topo_order (graph
, ti
);
1522 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1524 unsigned int i
= VEC_pop (unsigned, ti
->topo_order
);
1525 varinfo_t vi
= get_varinfo (i
);
1526 bool okay_to_elim
= false;
1527 unsigned int root
= VEC_length (varinfo_t
, varmap
);
1532 /* We can't eliminate things whose address is taken, or which is
1533 the target of a dereference. */
1534 if (vi
->address_taken
|| vi
->indirect_target
)
1537 /* See if all predecessors of I are ripe for elimination */
1538 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[i
], 0, k
, bi
)
1541 w
= get_varinfo (k
)->node
;
1543 /* We can't eliminate the node if one of the predecessors is
1544 part of a different strongly connected component. */
1548 okay_to_elim
= true;
1552 okay_to_elim
= false;
1556 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1557 then Solution(i) is a subset of Solution (w), where w is a
1558 predecessor in the graph.
1559 Corollary: If all predecessors of i have the same
1560 points-to set, then i has that same points-to set as
1561 those predecessors. */
1562 tmp
= BITMAP_ALLOC (NULL
);
1563 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1564 get_varinfo (w
)->solution
);
1565 if (!bitmap_empty_p (tmp
))
1567 okay_to_elim
= false;
1574 /* See if the root is different than the original node.
1575 If so, we've found an equivalence. */
1576 if (root
!= get_varinfo (i
)->node
&& okay_to_elim
)
1578 /* Found an equivalence */
1579 get_varinfo (i
)->node
= root
;
1580 collapse_nodes (graph
, root
, i
);
1581 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1582 fprintf (dump_file
, "Collapsing %s into %s\n",
1583 get_varinfo (i
)->name
,
1584 get_varinfo (root
)->name
);
1585 stats
.collapsed_vars
++;
1589 bitmap_obstack_release (&iteration_obstack
);
1590 free_topo_info (ti
);
1593 /* Solve the constraint graph GRAPH using our worklist solver.
1594 This is based on the PW* family of solvers from the "Efficient Field
1595 Sensitive Pointer Analysis for C" paper.
1596 It works by iterating over all the graph nodes, processing the complex
1597 constraints and propagating the copy constraints, until everything stops
1598 changed. This corresponds to steps 6-8 in the solving list given above. */
1601 solve_graph (constraint_graph_t graph
)
1603 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1606 changed_count
= size
;
1607 changed
= sbitmap_alloc (size
);
1608 sbitmap_ones (changed
);
1610 /* The already collapsed/unreachable nodes will never change, so we
1611 need to account for them in changed_count. */
1612 for (i
= 0; i
< size
; i
++)
1613 if (get_varinfo (i
)->node
!= i
)
1616 while (changed_count
> 0)
1619 struct topo_info
*ti
= init_topo_info ();
1622 bitmap_obstack_initialize (&iteration_obstack
);
1626 /* We already did cycle elimination once, when we did
1627 variable substitution, so we don't need it again for the
1629 if (stats
.iterations
> 1)
1630 find_and_collapse_graph_cycles (graph
, true);
1635 compute_topo_order (graph
, ti
);
1637 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1639 i
= VEC_pop (unsigned, ti
->topo_order
);
1640 gcc_assert (get_varinfo (i
)->node
== i
);
1642 /* If the node has changed, we need to process the
1643 complex constraints and outgoing edges again. */
1644 if (TEST_BIT (changed
, i
))
1650 VEC(constraint_t
,heap
) *complex = get_varinfo (i
)->complex;
1651 bool solution_empty
;
1653 RESET_BIT (changed
, i
);
1656 solution
= get_varinfo (i
)->solution
;
1657 solution_empty
= bitmap_empty_p (solution
);
1659 /* Process the complex constraints */
1660 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
1662 /* The only complex constraint that can change our
1663 solution to non-empty, given an empty solution,
1664 is a constraint where the lhs side is receiving
1665 some set from elsewhere. */
1666 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
1667 do_complex_constraint (graph
, c
, solution
);
1670 solution_empty
= bitmap_empty_p (solution
);
1672 if (!solution_empty
)
1674 /* Propagate solution to all successors. */
1675 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
1678 bitmap tmp
= get_varinfo (j
)->solution
;
1681 gcc_assert (get_varinfo (j
)->node
== j
);
1683 flag
= set_union_with_increment (tmp
, solution
, 0);
1687 get_varinfo (j
)->solution
= tmp
;
1688 if (!TEST_BIT (changed
, j
))
1690 SET_BIT (changed
, j
);
1698 free_topo_info (ti
);
1699 bitmap_obstack_release (&iteration_obstack
);
1702 sbitmap_free (changed
);
1706 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1708 /* Map from trees to variable ids. */
1709 static htab_t id_for_tree
;
1711 typedef struct tree_id
1717 /* Hash a tree id structure. */
1720 tree_id_hash (const void *p
)
1722 const tree_id_t ta
= (tree_id_t
) p
;
1723 return htab_hash_pointer (ta
->t
);
1726 /* Return true if the tree in P1 and the tree in P2 are the same. */
1729 tree_id_eq (const void *p1
, const void *p2
)
1731 const tree_id_t ta1
= (tree_id_t
) p1
;
1732 const tree_id_t ta2
= (tree_id_t
) p2
;
1733 return ta1
->t
== ta2
->t
;
1736 /* Insert ID as the variable id for tree T in the hashtable. */
1739 insert_id_for_tree (tree t
, int id
)
1742 struct tree_id finder
;
1746 slot
= htab_find_slot (id_for_tree
, &finder
, INSERT
);
1747 gcc_assert (*slot
== NULL
);
1748 new_pair
= XNEW (struct tree_id
);
1751 *slot
= (void *)new_pair
;
1754 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1755 exist in the hash table, return false, otherwise, return true and
1756 set *ID to the id we found. */
1759 lookup_id_for_tree (tree t
, unsigned int *id
)
1762 struct tree_id finder
;
1765 pair
= htab_find (id_for_tree
, &finder
);
1772 /* Return a printable name for DECL */
1775 alias_get_name (tree decl
)
1777 const char *res
= get_name (decl
);
1779 int num_printed
= 0;
1788 if (TREE_CODE (decl
) == SSA_NAME
)
1790 num_printed
= asprintf (&temp
, "%s_%u",
1791 alias_get_name (SSA_NAME_VAR (decl
)),
1792 SSA_NAME_VERSION (decl
));
1794 else if (DECL_P (decl
))
1796 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
1798 if (num_printed
> 0)
1800 res
= ggc_strdup (temp
);
1806 /* Find the variable id for tree T in the hashtable.
1807 If T doesn't exist in the hash table, create an entry for it. */
1810 get_id_for_tree (tree t
)
1813 struct tree_id finder
;
1816 pair
= htab_find (id_for_tree
, &finder
);
1818 return create_variable_info_for (t
, alias_get_name (t
));
1823 /* Get a constraint expression from an SSA_VAR_P node. */
1825 static struct constraint_expr
1826 get_constraint_exp_from_ssa_var (tree t
)
1828 struct constraint_expr cexpr
;
1830 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
1832 /* For parameters, get at the points-to set for the actual parm
1834 if (TREE_CODE (t
) == SSA_NAME
1835 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
1836 && gimple_default_def (cfun
, SSA_NAME_VAR (t
)) == t
)
1837 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
1839 cexpr
.type
= SCALAR
;
1841 cexpr
.var
= get_id_for_tree (t
);
1842 /* If we determine the result is "anything", and we know this is readonly,
1843 say it points to readonly memory instead. */
1844 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
1846 cexpr
.type
= ADDRESSOF
;
1847 cexpr
.var
= readonly_id
;
1854 /* Process a completed constraint T, and add it to the constraint
1858 process_constraint (constraint_t t
)
1860 struct constraint_expr rhs
= t
->rhs
;
1861 struct constraint_expr lhs
= t
->lhs
;
1863 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
1864 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
1866 if (lhs
.type
== DEREF
)
1867 get_varinfo (lhs
.var
)->directly_dereferenced
= true;
1868 if (rhs
.type
== DEREF
)
1869 get_varinfo (rhs
.var
)->directly_dereferenced
= true;
1871 /* ANYTHING == ANYTHING is pointless. */
1872 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
1875 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1876 else if (lhs
.var
== anything_id
&& lhs
.type
== ADDRESSOF
)
1881 process_constraint (t
);
1883 /* This can happen in our IR with things like n->a = *p */
1884 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
1886 /* Split into tmp = *rhs, *lhs = tmp */
1887 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
1888 tree pointertype
= TREE_TYPE (rhsdecl
);
1889 tree pointedtotype
= TREE_TYPE (pointertype
);
1890 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
1891 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
1893 /* If this is an aggregate of known size, we should have passed
1894 this off to do_structure_copy, and it should have broken it
1896 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
1897 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
1899 process_constraint (new_constraint (tmplhs
, rhs
));
1900 process_constraint (new_constraint (lhs
, tmplhs
));
1902 else if (rhs
.type
== ADDRESSOF
)
1905 gcc_assert (rhs
.offset
== 0);
1907 /* No need to mark address taken simply because of escaped vars
1909 if (lhs
.var
!= escaped_vars_id
)
1910 for (vi
= get_varinfo (rhs
.var
); vi
!= NULL
; vi
= vi
->next
)
1911 vi
->address_taken
= true;
1913 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
1917 if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
1918 get_varinfo (lhs
.var
)->indirect_target
= true;
1919 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
1923 /* Return true if T is a variable of a type that could contain
1927 could_have_pointers (tree t
)
1929 tree type
= TREE_TYPE (t
);
1931 if (POINTER_TYPE_P (type
) || AGGREGATE_TYPE_P (type
)
1932 || TREE_CODE (type
) == COMPLEX_TYPE
)
1937 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1940 static unsigned HOST_WIDE_INT
1941 bitpos_of_field (const tree fdecl
)
1944 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
1945 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
1948 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
1949 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
1953 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1954 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1957 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
1958 const unsigned HOST_WIDE_INT fieldsize
,
1959 const unsigned HOST_WIDE_INT accesspos
,
1960 const unsigned HOST_WIDE_INT accesssize
)
1962 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
1964 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
1966 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
1972 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1975 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
)
1978 HOST_WIDE_INT bitsize
= -1;
1979 HOST_WIDE_INT bitmaxsize
= -1;
1980 HOST_WIDE_INT bitpos
;
1982 struct constraint_expr
*result
;
1983 unsigned int beforelength
= VEC_length (ce_s
, *results
);
1985 /* Some people like to do cute things like take the address of
1988 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
1989 forzero
= TREE_OPERAND (forzero
, 0);
1991 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
1993 struct constraint_expr temp
;
1996 temp
.var
= integer_id
;
1998 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2002 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
2004 /* String constants are readonly, so there is nothing to really do
2006 if (TREE_CODE (t
) == STRING_CST
)
2009 get_constraint_for (t
, results
);
2010 result
= VEC_last (ce_s
, *results
);
2011 result
->offset
= bitpos
;
2013 gcc_assert (beforelength
+ 1 == VEC_length (ce_s
, *results
));
2015 /* This can also happen due to weird offsetof type macros. */
2016 if (TREE_CODE (t
) != ADDR_EXPR
&& result
->type
== ADDRESSOF
)
2017 result
->type
= SCALAR
;
2019 if (result
->type
== SCALAR
)
2021 /* In languages like C, you can access one past the end of an
2022 array. You aren't allowed to dereference it, so we can
2023 ignore this constraint. When we handle pointer subtraction,
2024 we may have to do something cute here. */
2026 if (result
->offset
< get_varinfo (result
->var
)->fullsize
2029 /* It's also not true that the constraint will actually start at the
2030 right offset, it may start in some padding. We only care about
2031 setting the constraint to the first actual field it touches, so
2034 for (curr
= get_varinfo (result
->var
); curr
; curr
= curr
->next
)
2036 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2037 result
->offset
, bitmaxsize
))
2039 result
->var
= curr
->id
;
2043 /* assert that we found *some* field there. The user couldn't be
2044 accessing *only* padding. */
2045 /* Still the user could access one past the end of an array
2046 embedded in a struct resulting in accessing *only* padding. */
2047 gcc_assert (curr
|| ref_contains_array_ref (orig_t
));
2049 else if (bitmaxsize
== 0)
2051 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2052 fprintf (dump_file
, "Access to zero-sized part of variable,"
2056 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2057 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2064 /* Dereference the constraint expression CONS, and return the result.
2065 DEREF (ADDRESSOF) = SCALAR
2066 DEREF (SCALAR) = DEREF
2067 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2068 This is needed so that we can handle dereferencing DEREF constraints. */
2071 do_deref (VEC (ce_s
, heap
) **constraints
)
2073 struct constraint_expr
*c
;
2075 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
2077 if (c
->type
== SCALAR
)
2079 else if (c
->type
== ADDRESSOF
)
2081 else if (c
->type
== DEREF
)
2083 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "dereftmp");
2084 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2085 process_constraint (new_constraint (tmplhs
, *c
));
2086 c
->var
= tmplhs
.var
;
2093 /* Create a nonlocal variable of TYPE to represent nonlocals we can
2097 create_nonlocal_var (tree type
)
2099 tree nonlocal
= create_tmp_var_raw (type
, "NONLOCAL");
2101 if (gimple_referenced_vars (cfun
))
2102 add_referenced_var (nonlocal
);
2104 DECL_EXTERNAL (nonlocal
) = 1;
2108 /* Given a tree T, return the constraint expression for it. */
2111 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
2113 struct constraint_expr temp
;
2115 /* x = integer is all glommed to a single variable, which doesn't
2116 point to anything by itself. That is, of course, unless it is an
2117 integer constant being treated as a pointer, in which case, we
2118 will return that this is really the addressof anything. This
2119 happens below, since it will fall into the default case. The only
2120 case we know something about an integer treated like a pointer is
2121 when it is the NULL pointer, and then we just say it points to
2123 if (TREE_CODE (t
) == INTEGER_CST
2124 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2126 temp
.var
= integer_id
;
2129 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2132 else if (TREE_CODE (t
) == INTEGER_CST
2133 && integer_zerop (t
))
2135 temp
.var
= nothing_id
;
2136 temp
.type
= ADDRESSOF
;
2138 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2142 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2144 case tcc_expression
:
2146 switch (TREE_CODE (t
))
2150 struct constraint_expr
*c
;
2152 tree exp
= TREE_OPERAND (t
, 0);
2153 tree pttype
= TREE_TYPE (TREE_TYPE (t
));
2155 get_constraint_for (exp
, results
);
2156 /* Make sure we capture constraints to all elements
2158 if ((handled_component_p (exp
)
2159 && ref_contains_array_ref (exp
))
2160 || TREE_CODE (TREE_TYPE (exp
)) == ARRAY_TYPE
)
2162 struct constraint_expr
*origrhs
;
2164 struct constraint_expr tmp
;
2166 if (VEC_length (ce_s
, *results
) == 0)
2169 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2170 origrhs
= VEC_last (ce_s
, *results
);
2172 VEC_pop (ce_s
, *results
);
2173 origvar
= get_varinfo (origrhs
->var
);
2174 for (; origvar
; origvar
= origvar
->next
)
2176 tmp
.var
= origvar
->id
;
2177 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2180 else if (VEC_length (ce_s
, *results
) == 1
2181 && (AGGREGATE_TYPE_P (pttype
)
2182 || TREE_CODE (pttype
) == COMPLEX_TYPE
))
2184 struct constraint_expr
*origrhs
;
2186 struct constraint_expr tmp
;
2188 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2189 origrhs
= VEC_last (ce_s
, *results
);
2191 VEC_pop (ce_s
, *results
);
2192 origvar
= get_varinfo (origrhs
->var
);
2193 for (; origvar
; origvar
= origvar
->next
)
2195 tmp
.var
= origvar
->id
;
2196 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2200 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
2202 if (c
->type
== DEREF
)
2205 c
->type
= ADDRESSOF
;
2211 /* XXX: In interprocedural mode, if we didn't have the
2212 body, we would need to do *each pointer argument =
2214 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2217 tree heapvar
= heapvar_lookup (t
);
2219 if (heapvar
== NULL
)
2221 heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2222 DECL_EXTERNAL (heapvar
) = 1;
2223 get_var_ann (heapvar
)->is_heapvar
= 1;
2224 if (gimple_referenced_vars (cfun
))
2225 add_referenced_var (heapvar
);
2226 heapvar_insert (t
, heapvar
);
2229 temp
.var
= create_variable_info_for (heapvar
,
2230 alias_get_name (heapvar
));
2232 vi
= get_varinfo (temp
.var
);
2233 vi
->is_artificial_var
= 1;
2234 vi
->is_heap_var
= 1;
2235 temp
.type
= ADDRESSOF
;
2237 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2242 temp
.var
= escaped_vars_id
;
2245 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2251 temp
.type
= ADDRESSOF
;
2252 temp
.var
= anything_id
;
2254 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2261 switch (TREE_CODE (t
))
2265 get_constraint_for (TREE_OPERAND (t
, 0), results
);
2270 case ARRAY_RANGE_REF
:
2272 get_constraint_for_component_ref (t
, results
);
2276 temp
.type
= ADDRESSOF
;
2277 temp
.var
= anything_id
;
2279 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2286 switch (TREE_CODE (t
))
2290 case NON_LVALUE_EXPR
:
2292 tree op
= TREE_OPERAND (t
, 0);
2294 /* Cast from non-pointer to pointers are bad news for us.
2295 Anything else, we see through */
2296 if (!(POINTER_TYPE_P (TREE_TYPE (t
))
2297 && ! POINTER_TYPE_P (TREE_TYPE (op
))))
2299 get_constraint_for (op
, results
);
2307 temp
.type
= ADDRESSOF
;
2308 temp
.var
= anything_id
;
2310 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2315 case tcc_exceptional
:
2317 switch (TREE_CODE (t
))
2321 get_constraint_for (PHI_RESULT (t
), results
);
2327 struct constraint_expr temp
;
2328 temp
= get_constraint_exp_from_ssa_var (t
);
2329 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2335 temp
.type
= ADDRESSOF
;
2336 temp
.var
= anything_id
;
2338 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2343 case tcc_declaration
:
2345 struct constraint_expr temp
;
2346 temp
= get_constraint_exp_from_ssa_var (t
);
2347 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2352 temp
.type
= ADDRESSOF
;
2353 temp
.var
= anything_id
;
2355 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2362 /* Handle the structure copy case where we have a simple structure copy
2363 between LHS and RHS that is of SIZE (in bits)
2365 For each field of the lhs variable (lhsfield)
2366 For each field of the rhs variable at lhsfield.offset (rhsfield)
2367 add the constraint lhsfield = rhsfield
2369 If we fail due to some kind of type unsafety or other thing we
2370 can't handle, return false. We expect the caller to collapse the
2371 variable in that case. */
2374 do_simple_structure_copy (const struct constraint_expr lhs
,
2375 const struct constraint_expr rhs
,
2376 const unsigned HOST_WIDE_INT size
)
2378 varinfo_t p
= get_varinfo (lhs
.var
);
2379 unsigned HOST_WIDE_INT pstart
, last
;
2381 last
= p
->offset
+ size
;
2382 for (; p
&& p
->offset
< last
; p
= p
->next
)
2385 struct constraint_expr templhs
= lhs
;
2386 struct constraint_expr temprhs
= rhs
;
2387 unsigned HOST_WIDE_INT fieldoffset
;
2389 templhs
.var
= p
->id
;
2390 q
= get_varinfo (temprhs
.var
);
2391 fieldoffset
= p
->offset
- pstart
;
2392 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2395 temprhs
.var
= q
->id
;
2396 process_constraint (new_constraint (templhs
, temprhs
));
2402 /* Handle the structure copy case where we have a structure copy between a
2403 aggregate on the LHS and a dereference of a pointer on the RHS
2404 that is of SIZE (in bits)
2406 For each field of the lhs variable (lhsfield)
2407 rhs.offset = lhsfield->offset
2408 add the constraint lhsfield = rhs
2412 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2413 const struct constraint_expr rhs
,
2414 const unsigned HOST_WIDE_INT size
)
2416 varinfo_t p
= get_varinfo (lhs
.var
);
2417 unsigned HOST_WIDE_INT pstart
,last
;
2419 last
= p
->offset
+ size
;
2421 for (; p
&& p
->offset
< last
; p
= p
->next
)
2424 struct constraint_expr templhs
= lhs
;
2425 struct constraint_expr temprhs
= rhs
;
2426 unsigned HOST_WIDE_INT fieldoffset
;
2429 if (templhs
.type
== SCALAR
)
2430 templhs
.var
= p
->id
;
2432 templhs
.offset
= p
->offset
;
2434 q
= get_varinfo (temprhs
.var
);
2435 fieldoffset
= p
->offset
- pstart
;
2436 temprhs
.offset
+= fieldoffset
;
2437 process_constraint (new_constraint (templhs
, temprhs
));
2441 /* Handle the structure copy case where we have a structure copy
2442 between a aggregate on the RHS and a dereference of a pointer on
2443 the LHS that is of SIZE (in bits)
2445 For each field of the rhs variable (rhsfield)
2446 lhs.offset = rhsfield->offset
2447 add the constraint lhs = rhsfield
2451 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2452 const struct constraint_expr rhs
,
2453 const unsigned HOST_WIDE_INT size
)
2455 varinfo_t p
= get_varinfo (rhs
.var
);
2456 unsigned HOST_WIDE_INT pstart
,last
;
2458 last
= p
->offset
+ size
;
2460 for (; p
&& p
->offset
< last
; p
= p
->next
)
2463 struct constraint_expr templhs
= lhs
;
2464 struct constraint_expr temprhs
= rhs
;
2465 unsigned HOST_WIDE_INT fieldoffset
;
2468 if (temprhs
.type
== SCALAR
)
2469 temprhs
.var
= p
->id
;
2471 temprhs
.offset
= p
->offset
;
2473 q
= get_varinfo (templhs
.var
);
2474 fieldoffset
= p
->offset
- pstart
;
2475 templhs
.offset
+= fieldoffset
;
2476 process_constraint (new_constraint (templhs
, temprhs
));
2480 /* Sometimes, frontends like to give us bad type information. This
2481 function will collapse all the fields from VAR to the end of VAR,
2482 into VAR, so that we treat those fields as a single variable.
2483 We return the variable they were collapsed into. */
2486 collapse_rest_of_var (unsigned int var
)
2488 varinfo_t currvar
= get_varinfo (var
);
2491 for (field
= currvar
->next
; field
; field
= field
->next
)
2494 fprintf (dump_file
, "Type safety: Collapsing var %s into %s\n",
2495 field
->name
, currvar
->name
);
2497 gcc_assert (!field
->collapsed_to
);
2498 field
->collapsed_to
= currvar
;
2501 currvar
->next
= NULL
;
2502 currvar
->size
= currvar
->fullsize
- currvar
->offset
;
2507 /* Handle aggregate copies by expanding into copies of the respective
2508 fields of the structures. */
2511 do_structure_copy (tree lhsop
, tree rhsop
)
2513 struct constraint_expr lhs
, rhs
, tmp
;
2514 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
2516 unsigned HOST_WIDE_INT lhssize
;
2517 unsigned HOST_WIDE_INT rhssize
;
2519 get_constraint_for (lhsop
, &lhsc
);
2520 get_constraint_for (rhsop
, &rhsc
);
2521 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
2522 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
2523 lhs
= *(VEC_last (ce_s
, lhsc
));
2524 rhs
= *(VEC_last (ce_s
, rhsc
));
2526 VEC_free (ce_s
, heap
, lhsc
);
2527 VEC_free (ce_s
, heap
, rhsc
);
2529 /* If we have special var = x, swap it around. */
2530 if (lhs
.var
<= integer_id
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2537 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2538 possible it's something we could handle. However, most cases falling
2539 into this are dealing with transparent unions, which are slightly
2541 if (rhs
.type
== ADDRESSOF
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2543 rhs
.type
= ADDRESSOF
;
2544 rhs
.var
= anything_id
;
2547 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2548 that special var. */
2549 if (rhs
.var
<= integer_id
)
2551 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2553 struct constraint_expr templhs
= lhs
;
2554 struct constraint_expr temprhs
= rhs
;
2556 if (templhs
.type
== SCALAR
)
2557 templhs
.var
= p
->id
;
2559 templhs
.offset
+= p
->offset
;
2560 process_constraint (new_constraint (templhs
, temprhs
));
2565 tree rhstype
= TREE_TYPE (rhsop
);
2566 tree lhstype
= TREE_TYPE (lhsop
);
2570 lhstypesize
= DECL_P (lhsop
) ? DECL_SIZE (lhsop
) : TYPE_SIZE (lhstype
);
2571 rhstypesize
= DECL_P (rhsop
) ? DECL_SIZE (rhsop
) : TYPE_SIZE (rhstype
);
2573 /* If we have a variably sized types on the rhs or lhs, and a deref
2574 constraint, add the constraint, lhsconstraint = &ANYTHING.
2575 This is conservatively correct because either the lhs is an unknown
2576 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2577 constraint, and every variable it can point to must be unknown sized
2578 anyway, so we don't need to worry about fields at all. */
2579 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
2580 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
2582 rhs
.var
= anything_id
;
2583 rhs
.type
= ADDRESSOF
;
2585 process_constraint (new_constraint (lhs
, rhs
));
2589 /* The size only really matters insofar as we don't set more or less of
2590 the variable. If we hit an unknown size var, the size should be the
2591 whole darn thing. */
2592 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
2595 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
2597 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
2600 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
2603 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
2605 if (!do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
)))
2607 lhs
.var
= collapse_rest_of_var (lhs
.var
);
2608 rhs
.var
= collapse_rest_of_var (rhs
.var
);
2613 process_constraint (new_constraint (lhs
, rhs
));
2616 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2617 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2618 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
2619 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2622 tree pointedtotype
= lhstype
;
2625 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
2626 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
2627 do_structure_copy (tmpvar
, rhsop
);
2628 do_structure_copy (lhsop
, tmpvar
);
2633 /* Update related alias information kept in AI. This is used when
2634 building name tags, alias sets and deciding grouping heuristics.
2635 STMT is the statement to process. This function also updates
2636 ADDRESSABLE_VARS. */
2639 update_alias_info (tree stmt
, struct alias_info
*ai
)
2642 use_operand_p use_p
;
2644 enum escape_type stmt_escape_type
= is_escape_site (stmt
);
2647 if (stmt_escape_type
== ESCAPE_TO_CALL
2648 || stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
2650 ai
->num_calls_found
++;
2651 if (stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
2652 ai
->num_pure_const_calls_found
++;
2655 /* Mark all the variables whose address are taken by the statement. */
2656 addr_taken
= addresses_taken (stmt
);
2659 bitmap_ior_into (gimple_addressable_vars (cfun
), addr_taken
);
2661 /* If STMT is an escape point, all the addresses taken by it are
2663 if (stmt_escape_type
!= NO_ESCAPE
)
2668 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
2670 tree rvar
= referenced_var (i
);
2671 if (!unmodifiable_var_p (rvar
))
2672 mark_call_clobbered (rvar
, stmt_escape_type
);
2677 /* Process each operand use. If an operand may be aliased, keep
2678 track of how many times it's being used. For pointers, determine
2679 whether they are dereferenced by the statement, or whether their
2680 value escapes, etc. */
2681 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2685 struct ptr_info_def
*pi
;
2686 bool is_store
, is_potential_deref
;
2687 unsigned num_uses
, num_derefs
;
2689 op
= USE_FROM_PTR (use_p
);
2691 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2692 to the set of addressable variables. */
2693 if (TREE_CODE (op
) == ADDR_EXPR
)
2695 bitmap addressable_vars
= gimple_addressable_vars (cfun
);
2697 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
);
2698 gcc_assert (addressable_vars
);
2700 /* PHI nodes don't have annotations for pinning the set
2701 of addresses taken, so we collect them here.
2703 FIXME, should we allow PHI nodes to have annotations
2704 so that they can be treated like regular statements?
2705 Currently, they are treated as second-class
2707 add_to_addressable_set (TREE_OPERAND (op
, 0),
2712 /* Ignore constants. */
2713 if (TREE_CODE (op
) != SSA_NAME
)
2716 var
= SSA_NAME_VAR (op
);
2717 v_ann
= var_ann (var
);
2719 /* The base variable of an ssa name must be a GIMPLE register, and thus
2720 it cannot be aliased. */
2721 gcc_assert (!may_be_aliased (var
));
2723 /* We are only interested in pointers. */
2724 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
2727 pi
= get_ptr_info (op
);
2729 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2730 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
)))
2732 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
));
2733 VEC_safe_push (tree
, heap
, ai
->processed_ptrs
, op
);
2736 /* If STMT is a PHI node, then it will not have pointer
2737 dereferences and it will not be an escape point. */
2738 if (TREE_CODE (stmt
) == PHI_NODE
)
2741 /* Determine whether OP is a dereferenced pointer, and if STMT
2742 is an escape point, whether OP escapes. */
2743 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
2745 /* Handle a corner case involving address expressions of the
2746 form '&PTR->FLD'. The problem with these expressions is that
2747 they do not represent a dereference of PTR. However, if some
2748 other transformation propagates them into an INDIRECT_REF
2749 expression, we end up with '*(&PTR->FLD)' which is folded
2752 So, if the original code had no other dereferences of PTR,
2753 the aliaser will not create memory tags for it, and when
2754 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
2755 memory operations will receive no V_MAY_DEF/VUSE operands.
2757 One solution would be to have count_uses_and_derefs consider
2758 &PTR->FLD a dereference of PTR. But that is wrong, since it
2759 is not really a dereference but an offset calculation.
2761 What we do here is to recognize these special ADDR_EXPR
2762 nodes. Since these expressions are never GIMPLE values (they
2763 are not GIMPLE invariants), they can only appear on the RHS
2764 of an assignment and their base address is always an
2765 INDIRECT_REF expression. */
2766 is_potential_deref
= false;
2767 if (TREE_CODE (stmt
) == MODIFY_EXPR
2768 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ADDR_EXPR
2769 && !is_gimple_val (TREE_OPERAND (stmt
, 1)))
2771 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
2772 this represents a potential dereference of PTR. */
2773 tree rhs
= TREE_OPERAND (stmt
, 1);
2774 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
2775 if (TREE_CODE (base
) == INDIRECT_REF
2776 && TREE_OPERAND (base
, 0) == op
)
2777 is_potential_deref
= true;
2780 if (num_derefs
> 0 || is_potential_deref
)
2782 /* Mark OP as dereferenced. In a subsequent pass,
2783 dereferenced pointers that point to a set of
2784 variables will be assigned a name tag to alias
2785 all the variables OP points to. */
2786 pi
->is_dereferenced
= 1;
2788 /* Keep track of how many time we've dereferenced each
2790 NUM_REFERENCES_INC (v_ann
);
2792 /* If this is a store operation, mark OP as being
2793 dereferenced to store, otherwise mark it as being
2794 dereferenced to load. */
2796 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
2798 bitmap_set_bit (ai
->dereferenced_ptrs_load
, DECL_UID (var
));
2801 if (stmt_escape_type
!= NO_ESCAPE
&& num_derefs
< num_uses
)
2803 /* If STMT is an escape point and STMT contains at
2804 least one direct use of OP, then the value of OP
2805 escapes and so the pointed-to variables need to
2806 be marked call-clobbered. */
2807 pi
->value_escapes_p
= 1;
2808 pi
->escape_mask
|= stmt_escape_type
;
2810 /* If the statement makes a function call, assume
2811 that pointer OP will be dereferenced in a store
2812 operation inside the called function. */
2813 if (get_call_expr_in (stmt
))
2815 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
2816 pi
->is_dereferenced
= 1;
2821 if (TREE_CODE (stmt
) == PHI_NODE
)
2824 /* Update reference counter for definitions to any
2825 potentially aliased variable. This is used in the alias
2826 grouping heuristics. */
2827 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
2829 tree var
= SSA_NAME_VAR (op
);
2830 var_ann_t ann
= var_ann (var
);
2831 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
2832 if (may_be_aliased (var
))
2833 NUM_REFERENCES_INC (ann
);
2837 /* Mark variables in V_MAY_DEF operands as being written to. */
2838 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
2840 tree var
= DECL_P (op
) ? op
: SSA_NAME_VAR (op
);
2841 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
2846 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
2847 Expressions of the type PTR + CST can be handled in two ways:
2849 1- If the constraint for PTR is ADDRESSOF for a non-structure
2850 variable, then we can use it directly because adding or
2851 subtracting a constant may not alter the original ADDRESSOF
2852 constraint (i.e., pointer arithmetic may not legally go outside
2853 an object's boundaries).
2855 2- If the constraint for PTR is ADDRESSOF for a structure variable,
2856 then if CST is a compile-time constant that can be used as an
2857 offset, we can determine which sub-variable will be pointed-to
2860 Return true if the expression is handled. For any other kind of
2861 expression, return false so that each operand can be added as a
2862 separate constraint by the caller. */
2865 handle_ptr_arith (VEC (ce_s
, heap
) *lhsc
, tree expr
)
2868 struct constraint_expr
*c
, *c2
;
2871 VEC (ce_s
, heap
) *temp
= NULL
;
2872 unsigned int rhsoffset
= 0;
2874 if (TREE_CODE (expr
) != PLUS_EXPR
2875 && TREE_CODE (expr
) != MINUS_EXPR
)
2878 op0
= TREE_OPERAND (expr
, 0);
2879 op1
= TREE_OPERAND (expr
, 1);
2881 get_constraint_for (op0
, &temp
);
2882 if (POINTER_TYPE_P (TREE_TYPE (op0
))
2883 && TREE_CODE (op1
) == INTEGER_CST
2884 && TREE_CODE (expr
) == PLUS_EXPR
)
2886 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
2890 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
2891 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
2893 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
2895 varinfo_t temp
= get_varinfo (c2
->var
);
2897 /* An access one after the end of an array is valid,
2898 so simply punt on accesses we cannot resolve. */
2899 temp
= first_vi_for_offset (temp
, rhsoffset
);
2906 c2
->offset
= rhsoffset
;
2907 process_constraint (new_constraint (*c
, *c2
));
2910 VEC_free (ce_s
, heap
, temp
);
2916 /* Walk statement T setting up aliasing constraints according to the
2917 references found in T. This function is the main part of the
2918 constraint builder. AI points to auxiliary alias information used
2919 when building alias sets and computing alias grouping heuristics. */
2922 find_func_aliases (tree origt
)
2925 VEC(ce_s
, heap
) *lhsc
= NULL
;
2926 VEC(ce_s
, heap
) *rhsc
= NULL
;
2927 struct constraint_expr
*c
;
2929 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
2930 t
= TREE_OPERAND (t
, 0);
2932 /* Now build constraints expressions. */
2933 if (TREE_CODE (t
) == PHI_NODE
)
2935 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))));
2937 /* Only care about pointers and structures containing
2939 if (could_have_pointers (PHI_RESULT (t
)))
2944 /* For a phi node, assign all the arguments to
2946 get_constraint_for (PHI_RESULT (t
), &lhsc
);
2947 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
2950 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
2952 STRIP_NOPS (strippedrhs
);
2953 rhstype
= TREE_TYPE (strippedrhs
);
2954 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
2956 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
2958 struct constraint_expr
*c2
;
2959 while (VEC_length (ce_s
, rhsc
) > 0)
2961 c2
= VEC_last (ce_s
, rhsc
);
2962 process_constraint (new_constraint (*c
, *c2
));
2963 VEC_pop (ce_s
, rhsc
);
2969 /* In IPA mode, we need to generate constraints to pass call
2970 arguments through their calls. There are two case, either a
2971 modify_expr when we are returning a value, or just a plain
2972 call_expr when we are not. */
2973 else if (in_ipa_mode
2974 && ((TREE_CODE (t
) == MODIFY_EXPR
2975 && TREE_CODE (TREE_OPERAND (t
, 1)) == CALL_EXPR
2976 && !(call_expr_flags (TREE_OPERAND (t
, 1))
2977 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
2978 || (TREE_CODE (t
) == CALL_EXPR
2979 && !(call_expr_flags (t
)
2980 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
2989 if (TREE_CODE (t
) == MODIFY_EXPR
)
2991 lhsop
= TREE_OPERAND (t
, 0);
2992 rhsop
= TREE_OPERAND (t
, 1);
2999 decl
= get_callee_fndecl (rhsop
);
3001 /* If we can directly resolve the function being called, do so.
3002 Otherwise, it must be some sort of indirect expression that
3003 we should still be able to handle. */
3006 varid
= get_id_for_tree (decl
);
3010 decl
= TREE_OPERAND (rhsop
, 0);
3011 varid
= get_id_for_tree (decl
);
3014 /* Assign all the passed arguments to the appropriate incoming
3015 parameters of the function. */
3016 fi
= get_varinfo (varid
);
3017 arglist
= TREE_OPERAND (rhsop
, 1);
3019 for (;arglist
; arglist
= TREE_CHAIN (arglist
))
3021 tree arg
= TREE_VALUE (arglist
);
3022 struct constraint_expr lhs
;
3023 struct constraint_expr
*rhsp
;
3025 get_constraint_for (arg
, &rhsc
);
3026 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3035 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3038 while (VEC_length (ce_s
, rhsc
) != 0)
3040 rhsp
= VEC_last (ce_s
, rhsc
);
3041 process_constraint (new_constraint (lhs
, *rhsp
));
3042 VEC_pop (ce_s
, rhsc
);
3046 /* If we are returning a value, assign it to the result. */
3049 struct constraint_expr rhs
;
3050 struct constraint_expr
*lhsp
;
3053 get_constraint_for (lhsop
, &lhsc
);
3054 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3063 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3066 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3067 process_constraint (new_constraint (*lhsp
, rhs
));
3070 /* Otherwise, just a regular assignment statement. */
3071 else if (TREE_CODE (t
) == MODIFY_EXPR
)
3073 tree lhsop
= TREE_OPERAND (t
, 0);
3074 tree rhsop
= TREE_OPERAND (t
, 1);
3077 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3078 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
)
3079 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop
))
3080 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
))
3082 do_structure_copy (lhsop
, rhsop
);
3086 /* Only care about operations with pointers, structures
3087 containing pointers, dereferences, and call expressions. */
3088 if (could_have_pointers (lhsop
)
3089 || TREE_CODE (rhsop
) == CALL_EXPR
)
3091 get_constraint_for (lhsop
, &lhsc
);
3092 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3094 /* RHS that consist of unary operations,
3095 exceptional types, or bare decls/constants, get
3096 handled directly by get_constraint_for. */
3098 case tcc_declaration
:
3100 case tcc_exceptional
:
3101 case tcc_expression
:
3106 get_constraint_for (rhsop
, &rhsc
);
3107 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3109 struct constraint_expr
*c2
;
3112 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3113 process_constraint (new_constraint (*c
, *c2
));
3121 /* For pointer arithmetic of the form
3122 PTR + CST, we can simply use PTR's
3123 constraint because pointer arithmetic is
3124 not allowed to go out of bounds. */
3125 if (handle_ptr_arith (lhsc
, rhsop
))
3130 /* Otherwise, walk each operand. Notice that we
3131 can't use the operand interface because we need
3132 to process expressions other than simple operands
3133 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3135 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
3137 tree op
= TREE_OPERAND (rhsop
, i
);
3140 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3141 get_constraint_for (op
, &rhsc
);
3142 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3144 struct constraint_expr
*c2
;
3145 while (VEC_length (ce_s
, rhsc
) > 0)
3147 c2
= VEC_last (ce_s
, rhsc
);
3148 process_constraint (new_constraint (*c
, *c2
));
3149 VEC_pop (ce_s
, rhsc
);
3158 /* After promoting variables and computing aliasing we will
3159 need to re-scan most statements. FIXME: Try to minimize the
3160 number of statements re-scanned. It's not really necessary to
3161 re-scan *all* statements. */
3162 mark_stmt_modified (origt
);
3163 VEC_free (ce_s
, heap
, rhsc
);
3164 VEC_free (ce_s
, heap
, lhsc
);
3168 /* Find the first varinfo in the same variable as START that overlaps with
3170 Effectively, walk the chain of fields for the variable START to find the
3171 first field that overlaps with OFFSET.
3172 Return NULL if we can't find one. */
3175 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3177 varinfo_t curr
= start
;
3180 /* We may not find a variable in the field list with the actual
3181 offset when when we have glommed a structure to a variable.
3182 In that case, however, offset should still be within the size
3184 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3192 /* Insert the varinfo FIELD into the field list for BASE, at the front
3196 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3198 varinfo_t prev
= base
;
3199 varinfo_t curr
= base
->next
;
3205 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3209 insert_into_field_list_sorted (varinfo_t base
, varinfo_t field
)
3211 varinfo_t prev
= base
;
3212 varinfo_t curr
= base
->next
;
3223 if (field
->offset
<= curr
->offset
)
3228 field
->next
= prev
->next
;
3233 /* qsort comparison function for two fieldoff's PA and PB */
3236 fieldoff_compare (const void *pa
, const void *pb
)
3238 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3239 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3240 HOST_WIDE_INT foasize
, fobsize
;
3242 if (foa
->offset
!= fob
->offset
)
3243 return foa
->offset
- fob
->offset
;
3245 foasize
= TREE_INT_CST_LOW (foa
->size
);
3246 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3247 return foasize
- fobsize
;
3250 /* Sort a fieldstack according to the field offset and sizes. */
3252 sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3254 qsort (VEC_address (fieldoff_s
, fieldstack
),
3255 VEC_length (fieldoff_s
, fieldstack
),
3256 sizeof (fieldoff_s
),
3260 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3261 of TYPE onto fieldstack, recording their offsets along the way.
3262 OFFSET is used to keep track of the offset in this entire structure, rather
3263 than just the immediately containing structure. Returns the number
3265 HAS_UNION is set to true if we find a union type as a field of
3269 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3270 HOST_WIDE_INT offset
, bool *has_union
)
3275 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3277 fieldoff_s
*real_part
, *img_part
;
3278 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3279 real_part
->type
= TREE_TYPE (type
);
3280 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3281 real_part
->offset
= offset
;
3282 real_part
->decl
= NULL_TREE
;
3284 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3285 img_part
->type
= TREE_TYPE (type
);
3286 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3287 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3288 img_part
->decl
= NULL_TREE
;
3293 if (TREE_CODE (type
) == ARRAY_TYPE
)
3295 tree sz
= TYPE_SIZE (type
);
3296 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3301 || ! host_integerp (sz
, 1)
3302 || TREE_INT_CST_LOW (sz
) == 0
3304 || ! host_integerp (elsz
, 1)
3305 || TREE_INT_CST_LOW (elsz
) == 0)
3308 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3309 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3312 for (i
= 0; i
< nr
; ++i
)
3318 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3319 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3322 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3324 else if (!(pushed
= push_fields_onto_fieldstack
3325 (TREE_TYPE (type
), fieldstack
,
3326 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
)))
3327 /* Empty structures may have actual size, like in C++. So
3328 see if we didn't push any subfields and the size is
3329 nonzero, push the field onto the stack */
3336 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3337 pair
->type
= TREE_TYPE (type
);
3339 pair
->decl
= NULL_TREE
;
3340 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3350 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3351 if (TREE_CODE (field
) == FIELD_DECL
)
3357 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3358 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3361 if (!var_can_have_subvars (field
))
3363 else if (!(pushed
= push_fields_onto_fieldstack
3364 (TREE_TYPE (field
), fieldstack
,
3365 offset
+ bitpos_of_field (field
), has_union
))
3366 && DECL_SIZE (field
)
3367 && !integer_zerop (DECL_SIZE (field
)))
3368 /* Empty structures may have actual size, like in C++. So
3369 see if we didn't push any subfields and the size is
3370 nonzero, push the field onto the stack */
3377 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3378 pair
->type
= TREE_TYPE (field
);
3379 pair
->size
= DECL_SIZE (field
);
3381 pair
->offset
= offset
+ bitpos_of_field (field
);
3391 /* Create a constraint from ESCAPED_VARS variable to VI. */
3393 make_constraint_from_escaped (varinfo_t vi
)
3395 struct constraint_expr lhs
, rhs
;
3401 rhs
.var
= escaped_vars_id
;
3404 process_constraint (new_constraint (lhs
, rhs
));
3407 /* Create a constraint to the ESCAPED_VARS variable from constraint
3411 make_constraint_to_escaped (struct constraint_expr rhs
)
3413 struct constraint_expr lhs
;
3415 lhs
.var
= escaped_vars_id
;
3419 process_constraint (new_constraint (lhs
, rhs
));
3422 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3423 if it is a varargs function. */
3426 count_num_arguments (tree decl
, bool *is_varargs
)
3431 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3435 if (TREE_VALUE (t
) == void_type_node
)
3445 /* Creation function node for DECL, using NAME, and return the index
3446 of the variable we've created for the function. */
3449 create_function_info_for (tree decl
, const char *name
)
3451 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3455 bool is_varargs
= false;
3457 /* Create the variable info. */
3459 vi
= new_var_info (decl
, index
, name
, index
);
3464 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3465 insert_id_for_tree (vi
->decl
, index
);
3466 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3470 /* If it's varargs, we don't know how many arguments it has, so we
3477 vi
->is_unknown_size_var
= true;
3482 arg
= DECL_ARGUMENTS (decl
);
3484 /* Set up variables for each argument. */
3485 for (i
= 1; i
< vi
->fullsize
; i
++)
3488 const char *newname
;
3490 unsigned int newindex
;
3491 tree argdecl
= decl
;
3496 newindex
= VEC_length (varinfo_t
, varmap
);
3497 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3498 newname
= ggc_strdup (tempname
);
3501 argvi
= new_var_info (argdecl
, newindex
,newname
, newindex
);
3502 argvi
->decl
= argdecl
;
3503 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3506 argvi
->fullsize
= vi
->fullsize
;
3507 argvi
->has_union
= false;
3508 insert_into_field_list_sorted (vi
, argvi
);
3509 stats
.total_vars
++;
3512 insert_id_for_tree (arg
, newindex
);
3513 arg
= TREE_CHAIN (arg
);
3517 /* Create a variable for the return var. */
3518 if (DECL_RESULT (decl
) != NULL
3519 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3522 const char *newname
;
3524 unsigned int newindex
;
3525 tree resultdecl
= decl
;
3529 if (DECL_RESULT (decl
))
3530 resultdecl
= DECL_RESULT (decl
);
3532 newindex
= VEC_length (varinfo_t
, varmap
);
3533 asprintf (&tempname
, "%s.result", name
);
3534 newname
= ggc_strdup (tempname
);
3537 resultvi
= new_var_info (resultdecl
, newindex
, newname
, newindex
);
3538 resultvi
->decl
= resultdecl
;
3539 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3540 resultvi
->offset
= i
;
3542 resultvi
->fullsize
= vi
->fullsize
;
3543 resultvi
->has_union
= false;
3544 insert_into_field_list_sorted (vi
, resultvi
);
3545 stats
.total_vars
++;
3546 if (DECL_RESULT (decl
))
3547 insert_id_for_tree (DECL_RESULT (decl
), newindex
);
3553 /* Return true if FIELDSTACK contains fields that overlap.
3554 FIELDSTACK is assumed to be sorted by offset. */
3557 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3559 fieldoff_s
*fo
= NULL
;
3561 HOST_WIDE_INT lastoffset
= -1;
3563 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3565 if (fo
->offset
== lastoffset
)
3567 lastoffset
= fo
->offset
;
3572 /* This function is called through walk_tree to walk global
3573 initializers looking for constraints we need to add to the
3577 find_global_initializers (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
3580 varinfo_t vi
= (varinfo_t
)viv
;
3583 switch (TREE_CODE (t
))
3585 /* Dereferences and addressofs are the only important things
3586 here, and i don't even remember if dereferences are legal
3587 here in initializers. */
3591 struct constraint_expr
*c
;
3594 VEC(ce_s
, heap
) *rhsc
= NULL
;
3595 get_constraint_for (t
, &rhsc
);
3596 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
3598 struct constraint_expr lhs
;
3603 process_constraint (new_constraint (lhs
, *c
));
3606 VEC_free (ce_s
, heap
, rhsc
);
3610 /* We might not have walked this because we skip
3611 DECL_EXTERNALs during the initial scan. */
3612 if (gimple_referenced_vars (cfun
))
3615 if (referenced_var_check_and_insert (t
))
3616 mark_sym_for_renaming (t
);
3625 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3626 This will also create any varinfo structures necessary for fields
3630 create_variable_info_for (tree decl
, const char *name
)
3632 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3634 tree
decltype = TREE_TYPE (decl
);
3635 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
3636 bool notokay
= false;
3638 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
3639 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
3641 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
3642 return create_function_info_for (decl
, name
);
3644 hasunion
= TREE_CODE (decltype) == UNION_TYPE
3645 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
3646 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
3648 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
3651 VEC_free (fieldoff_s
, heap
, fieldstack
);
3657 /* If the variable doesn't have subvars, we may end up needing to
3658 sort the field list and create fake variables for all the
3660 vi
= new_var_info (decl
, index
, name
, index
);
3663 vi
->has_union
= hasunion
;
3665 || TREE_CODE (declsize
) != INTEGER_CST
3666 || TREE_CODE (decltype) == UNION_TYPE
3667 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
3669 vi
->is_unknown_size_var
= true;
3675 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
3676 vi
->size
= vi
->fullsize
;
3679 insert_id_for_tree (vi
->decl
, index
);
3680 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3681 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3683 make_constraint_from_escaped (vi
);
3685 /* If the variable can't be aliased, there is no point in
3686 putting it in the set of nonlocal vars. */
3687 if (may_be_aliased (vi
->decl
))
3689 struct constraint_expr rhs
;
3691 rhs
.type
= ADDRESSOF
;
3693 make_constraint_to_escaped (rhs
);
3696 if (TREE_CODE (decl
) != FUNCTION_DECL
&& DECL_INITIAL (decl
))
3698 walk_tree_without_duplicates (&DECL_INITIAL (decl
),
3699 find_global_initializers
,
3705 if (use_field_sensitive
3707 && !vi
->is_unknown_size_var
3708 && var_can_have_subvars (decl
)
3709 && VEC_length (fieldoff_s
, fieldstack
) <= MAX_FIELDS_FOR_FIELD_SENSITIVE
)
3711 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
3712 fieldoff_s
*fo
= NULL
;
3715 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3718 || TREE_CODE (fo
->size
) != INTEGER_CST
3726 /* We can't sort them if we have a field with a variable sized type,
3727 which will make notokay = true. In that case, we are going to return
3728 without creating varinfos for the fields anyway, so sorting them is a
3732 sort_fieldstack (fieldstack
);
3733 /* Due to some C++ FE issues, like PR 22488, we might end up
3734 what appear to be overlapping fields even though they,
3735 in reality, do not overlap. Until the C++ FE is fixed,
3736 we will simply disable field-sensitivity for these cases. */
3737 notokay
= check_for_overlaps (fieldstack
);
3741 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
3742 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
3744 if (fo
== NULL
|| notokay
)
3746 vi
->is_unknown_size_var
= 1;
3749 VEC_free (fieldoff_s
, heap
, fieldstack
);
3753 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
3754 vi
->offset
= fo
->offset
;
3755 for (i
= VEC_length (fieldoff_s
, fieldstack
) - 1;
3756 i
>= 1 && VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
3760 const char *newname
= "NULL";
3763 newindex
= VEC_length (varinfo_t
, varmap
);
3767 asprintf (&tempname
, "%s.%s",
3768 vi
->name
, alias_get_name (fo
->decl
));
3770 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
,
3771 vi
->name
, fo
->offset
);
3772 newname
= ggc_strdup (tempname
);
3775 newvi
= new_var_info (decl
, newindex
, newname
, newindex
);
3776 newvi
->offset
= fo
->offset
;
3777 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
3778 newvi
->fullsize
= vi
->fullsize
;
3779 insert_into_field_list (vi
, newvi
);
3780 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
3781 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3783 /* If the variable can't be aliased, there is no point in
3784 putting it in the set of nonlocal vars. */
3785 if (may_be_aliased (vi
->decl
))
3787 struct constraint_expr rhs
;
3790 rhs
.type
= ADDRESSOF
;
3792 make_constraint_to_escaped (rhs
);
3794 make_constraint_from_escaped (newvi
);
3799 VEC_free (fieldoff_s
, heap
, fieldstack
);
3804 /* Print out the points-to solution for VAR to FILE. */
3807 dump_solution_for_var (FILE *file
, unsigned int var
)
3809 varinfo_t vi
= get_varinfo (var
);
3813 fprintf (file
, "%s = { ", vi
->name
);
3814 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi
->node
)->solution
, 0, i
, bi
)
3816 fprintf (file
, "%s ", get_varinfo (i
)->name
);
3818 fprintf (file
, "}\n");
3821 /* Print the points-to solution for VAR to stdout. */
3824 debug_solution_for_var (unsigned int var
)
3826 dump_solution_for_var (stdout
, var
);
3829 /* Create varinfo structures for all of the variables in the
3830 function for intraprocedural mode. */
3833 intra_create_variable_infos (void)
3836 struct constraint_expr lhs
, rhs
;
3837 varinfo_t nonlocal_vi
;
3839 /* For each incoming pointer argument arg, ARG = ESCAPED_VARS or a
3840 dummy variable if flag_argument_noalias > 2. */
3841 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
3844 unsigned int arg_id
;
3846 if (!could_have_pointers (t
))
3849 arg_id
= get_id_for_tree (t
);
3851 /* With flag_argument_noalias greater than two means that the incoming
3852 argument cannot alias anything except for itself so create a HEAP
3854 if (POINTER_TYPE_P (TREE_TYPE (t
))
3855 && flag_argument_noalias
> 2)
3858 tree heapvar
= heapvar_lookup (t
);
3863 lhs
.var
= get_id_for_tree (t
);
3865 if (heapvar
== NULL_TREE
)
3867 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)),
3869 get_var_ann (heapvar
)->is_heapvar
= 1;
3870 DECL_EXTERNAL (heapvar
) = 1;
3871 if (gimple_referenced_vars (cfun
))
3872 add_referenced_var (heapvar
);
3873 heapvar_insert (t
, heapvar
);
3875 id
= get_id_for_tree (heapvar
);
3876 vi
= get_varinfo (id
);
3877 vi
->is_artificial_var
= 1;
3878 vi
->is_heap_var
= 1;
3880 rhs
.type
= ADDRESSOF
;
3882 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
3884 struct constraint_expr temp
= lhs
;
3886 process_constraint (new_constraint (temp
, rhs
));
3891 for (p
= get_varinfo (arg_id
); p
; p
= p
->next
)
3892 make_constraint_from_escaped (p
);
3895 if (!gimple_nonlocal_all (cfun
))
3896 cfun
->gimple_df
->nonlocal_all
= create_nonlocal_var (void_type_node
);
3898 /* Create variable info for the nonlocal var if it does not
3900 nonlocal_vars_id
= create_variable_info_for (gimple_nonlocal_all (cfun
),
3901 get_name (gimple_nonlocal_all
3903 nonlocal_vi
= get_varinfo (nonlocal_vars_id
);
3904 nonlocal_vi
->is_artificial_var
= 1;
3905 nonlocal_vi
->is_heap_var
= 1;
3906 nonlocal_vi
->is_unknown_size_var
= 1;
3907 nonlocal_vi
->directly_dereferenced
= true;
3909 rhs
.var
= nonlocal_vars_id
;
3910 rhs
.type
= ADDRESSOF
;
3913 lhs
.var
= escaped_vars_id
;
3917 process_constraint (new_constraint (lhs
, rhs
));
3920 /* Set bits in INTO corresponding to the variable uids in solution set
3921 FROM, which came from variable PTR.
3922 For variables that are actually dereferenced, we also use type
3923 based alias analysis to prune the points-to sets. */
3926 set_uids_in_ptset (tree ptr
, bitmap into
, bitmap from
)
3931 unsigned HOST_WIDE_INT ptr_alias_set
= get_alias_set (TREE_TYPE (ptr
));
3933 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
3935 varinfo_t vi
= get_varinfo (i
);
3936 unsigned HOST_WIDE_INT var_alias_set
;
3938 /* The only artificial variables that are allowed in a may-alias
3939 set are heap variables. */
3940 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
3943 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
3945 /* Variables containing unions may need to be converted to
3946 their SFT's, because SFT's can have unions and we cannot. */
3947 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
3948 bitmap_set_bit (into
, DECL_UID (sv
->var
));
3950 else if (TREE_CODE (vi
->decl
) == VAR_DECL
3951 || TREE_CODE (vi
->decl
) == PARM_DECL
)
3953 if (var_can_have_subvars (vi
->decl
)
3954 && get_subvars_for_var (vi
->decl
))
3956 /* If VI->DECL is an aggregate for which we created
3957 SFTs, add the SFT corresponding to VI->OFFSET. */
3958 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
3961 var_alias_set
= get_alias_set (sft
);
3962 if (!vi
->directly_dereferenced
3963 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
3964 bitmap_set_bit (into
, DECL_UID (sft
));
3969 /* Otherwise, just add VI->DECL to the alias set.
3970 Don't type prune artificial vars. */
3971 if (vi
->is_artificial_var
)
3972 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
3975 var_alias_set
= get_alias_set (vi
->decl
);
3976 if (!vi
->directly_dereferenced
3977 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
3978 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
3986 static bool have_alias_info
= false;
3988 /* Given a pointer variable P, fill in its points-to set, or return
3989 false if we can't. */
3992 find_what_p_points_to (tree p
)
3994 unsigned int id
= 0;
3997 if (!have_alias_info
)
4000 /* For parameters, get at the points-to set for the actual parm
4002 if (TREE_CODE (p
) == SSA_NAME
4003 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
4004 && gimple_default_def (cfun
, SSA_NAME_VAR (p
)) == p
)
4005 lookup_p
= SSA_NAME_VAR (p
);
4007 if (lookup_id_for_tree (lookup_p
, &id
))
4009 varinfo_t vi
= get_varinfo (id
);
4011 if (vi
->is_artificial_var
)
4014 /* See if this is a field or a structure. */
4015 if (vi
->size
!= vi
->fullsize
)
4017 /* Nothing currently asks about structure fields directly,
4018 but when they do, we need code here to hand back the
4020 if (!var_can_have_subvars (vi
->decl
)
4021 || get_subvars_for_var (vi
->decl
) == NULL
)
4026 struct ptr_info_def
*pi
= get_ptr_info (p
);
4030 /* This variable may have been collapsed, let's get the real
4032 vi
= get_varinfo (vi
->node
);
4034 /* Translate artificial variables into SSA_NAME_PTR_INFO
4036 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4038 varinfo_t vi
= get_varinfo (i
);
4040 if (vi
->is_artificial_var
)
4042 /* FIXME. READONLY should be handled better so that
4043 flow insensitive aliasing can disregard writable
4045 if (vi
->id
== nothing_id
)
4047 else if (vi
->id
== anything_id
)
4048 pi
->pt_anything
= 1;
4049 else if (vi
->id
== readonly_id
)
4050 pi
->pt_anything
= 1;
4051 else if (vi
->id
== integer_id
)
4052 pi
->pt_anything
= 1;
4053 else if (vi
->is_heap_var
)
4054 pi
->pt_global_mem
= 1;
4058 if (pi
->pt_anything
)
4062 pi
->pt_vars
= BITMAP_GGC_ALLOC ();
4064 set_uids_in_ptset (vi
->decl
, pi
->pt_vars
, vi
->solution
);
4066 if (bitmap_empty_p (pi
->pt_vars
))
4078 /* Dump points-to information to OUTFILE. */
4081 dump_sa_points_to_info (FILE *outfile
)
4085 fprintf (outfile
, "\nPoints-to sets\n\n");
4087 if (dump_flags
& TDF_STATS
)
4089 fprintf (outfile
, "Stats:\n");
4090 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4091 fprintf (outfile
, "Statically unified vars: %d\n",
4092 stats
.unified_vars_static
);
4093 fprintf (outfile
, "Collapsed vars: %d\n", stats
.collapsed_vars
);
4094 fprintf (outfile
, "Dynamically unified vars: %d\n",
4095 stats
.unified_vars_dynamic
);
4096 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4097 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4100 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4101 dump_solution_for_var (outfile
, i
);
4105 /* Debug points-to information to stderr. */
4108 debug_sa_points_to_info (void)
4110 dump_sa_points_to_info (stderr
);
4114 /* Initialize the always-existing constraint variables for NULL
4115 ANYTHING, READONLY, and INTEGER */
4118 init_base_vars (void)
4120 struct constraint_expr lhs
, rhs
;
4122 /* Create the NULL variable, used to represent that a variable points
4124 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4125 var_nothing
= new_var_info (nothing_tree
, 0, "NULL", 0);
4126 insert_id_for_tree (nothing_tree
, 0);
4127 var_nothing
->is_artificial_var
= 1;
4128 var_nothing
->offset
= 0;
4129 var_nothing
->size
= ~0;
4130 var_nothing
->fullsize
= ~0;
4131 var_nothing
->is_special_var
= 1;
4133 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4135 /* Create the ANYTHING variable, used to represent that a variable
4136 points to some unknown piece of memory. */
4137 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4138 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING", 1);
4139 insert_id_for_tree (anything_tree
, 1);
4140 var_anything
->is_artificial_var
= 1;
4141 var_anything
->size
= ~0;
4142 var_anything
->offset
= 0;
4143 var_anything
->next
= NULL
;
4144 var_anything
->fullsize
= ~0;
4145 var_anything
->is_special_var
= 1;
4148 /* Anything points to anything. This makes deref constraints just
4149 work in the presence of linked list and other p = *p type loops,
4150 by saying that *ANYTHING = ANYTHING. */
4151 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4153 lhs
.var
= anything_id
;
4155 rhs
.type
= ADDRESSOF
;
4156 rhs
.var
= anything_id
;
4158 var_anything
->address_taken
= true;
4160 /* This specifically does not use process_constraint because
4161 process_constraint ignores all anything = anything constraints, since all
4162 but this one are redundant. */
4163 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4165 /* Create the READONLY variable, used to represent that a variable
4166 points to readonly memory. */
4167 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4168 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY", 2);
4169 var_readonly
->is_artificial_var
= 1;
4170 var_readonly
->offset
= 0;
4171 var_readonly
->size
= ~0;
4172 var_readonly
->fullsize
= ~0;
4173 var_readonly
->next
= NULL
;
4174 var_readonly
->is_special_var
= 1;
4175 insert_id_for_tree (readonly_tree
, 2);
4177 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4179 /* readonly memory points to anything, in order to make deref
4180 easier. In reality, it points to anything the particular
4181 readonly variable can point to, but we don't track this
4184 lhs
.var
= readonly_id
;
4186 rhs
.type
= ADDRESSOF
;
4187 rhs
.var
= anything_id
;
4190 process_constraint (new_constraint (lhs
, rhs
));
4192 /* Create the INTEGER variable, used to represent that a variable points
4194 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4195 var_integer
= new_var_info (integer_tree
, 3, "INTEGER", 3);
4196 insert_id_for_tree (integer_tree
, 3);
4197 var_integer
->is_artificial_var
= 1;
4198 var_integer
->size
= ~0;
4199 var_integer
->fullsize
= ~0;
4200 var_integer
->offset
= 0;
4201 var_integer
->next
= NULL
;
4202 var_integer
->is_special_var
= 1;
4204 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4206 /* INTEGER = ANYTHING, because we don't know where a dereference of
4207 a random integer will point to. */
4209 lhs
.var
= integer_id
;
4211 rhs
.type
= ADDRESSOF
;
4212 rhs
.var
= anything_id
;
4214 process_constraint (new_constraint (lhs
, rhs
));
4216 /* Create the ESCAPED_VARS variable used to represent variables that
4217 escape this function. */
4218 escaped_vars_tree
= create_tmp_var_raw (void_type_node
, "ESCAPED_VARS");
4219 var_escaped_vars
= new_var_info (escaped_vars_tree
, 4, "ESCAPED_VARS", 4);
4220 insert_id_for_tree (escaped_vars_tree
, 4);
4221 var_escaped_vars
->is_artificial_var
= 1;
4222 var_escaped_vars
->size
= ~0;
4223 var_escaped_vars
->fullsize
= ~0;
4224 var_escaped_vars
->offset
= 0;
4225 var_escaped_vars
->next
= NULL
;
4226 escaped_vars_id
= 4;
4227 VEC_safe_push (varinfo_t
, heap
, varmap
, var_escaped_vars
);
4229 /* ESCAPED_VARS = *ESCAPED_VARS */
4231 lhs
.var
= escaped_vars_id
;
4234 rhs
.var
= escaped_vars_id
;
4236 process_constraint (new_constraint (lhs
, rhs
));
4240 /* Initialize things necessary to perform PTA */
4243 init_alias_vars (void)
4245 bitmap_obstack_initialize (&ptabitmap_obstack
);
4246 bitmap_obstack_initialize (&predbitmap_obstack
);
4248 constraint_pool
= create_alloc_pool ("Constraint pool",
4249 sizeof (struct constraint
), 30);
4250 variable_info_pool
= create_alloc_pool ("Variable info pool",
4251 sizeof (struct variable_info
), 30);
4252 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4253 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4254 id_for_tree
= htab_create (10, tree_id_hash
, tree_id_eq
, free
);
4255 memset (&stats
, 0, sizeof (stats
));
4260 /* Given a statement STMT, generate necessary constraints to
4261 escaped_vars for the escaping variables. */
4264 find_escape_constraints (tree stmt
)
4266 enum escape_type stmt_escape_type
= is_escape_site (stmt
);
4268 VEC(ce_s
, heap
) *rhsc
= NULL
;
4269 struct constraint_expr
*c
;
4272 if (stmt_escape_type
== NO_ESCAPE
)
4275 if (TREE_CODE (stmt
) == RETURN_EXPR
)
4277 /* Returns are either bare, with an embedded MODIFY_EXPR, or
4278 just a plain old expression. */
4279 if (!TREE_OPERAND (stmt
, 0))
4281 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
4282 rhs
= TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
4284 rhs
= TREE_OPERAND (stmt
, 0);
4286 get_constraint_for (rhs
, &rhsc
);
4287 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
4288 make_constraint_to_escaped (*c
);
4289 VEC_free (ce_s
, heap
, rhsc
);
4292 else if (TREE_CODE (stmt
) == ASM_EXPR
)
4294 /* Whatever the inputs of the ASM are, escape. */
4297 for (arg
= ASM_INPUTS (stmt
); arg
; arg
= TREE_CHAIN (arg
))
4300 get_constraint_for (TREE_VALUE (arg
), &rhsc
);
4301 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
4302 make_constraint_to_escaped (*c
);
4303 VEC_free (ce_s
, heap
, rhsc
);
4307 else if (TREE_CODE (stmt
) == CALL_EXPR
4308 || (TREE_CODE (stmt
) == MODIFY_EXPR
4309 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
))
4311 /* Calls cause all of the arguments passed in to escape. */
4314 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
4315 stmt
= TREE_OPERAND (stmt
, 1);
4316 for (arg
= TREE_OPERAND (stmt
, 1); arg
; arg
= TREE_CHAIN (arg
))
4318 if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg
))))
4321 get_constraint_for (TREE_VALUE (arg
), &rhsc
);
4322 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
4323 make_constraint_to_escaped (*c
);
4324 VEC_free (ce_s
, heap
, rhsc
);
4331 gcc_assert (TREE_CODE (stmt
) == MODIFY_EXPR
);
4334 gcc_assert (stmt_escape_type
== ESCAPE_BAD_CAST
4335 || stmt_escape_type
== ESCAPE_STORED_IN_GLOBAL
4336 || stmt_escape_type
== ESCAPE_UNKNOWN
);
4337 rhs
= TREE_OPERAND (stmt
, 1);
4339 /* Look through casts for the real escaping variable.
4340 Constants don't really escape, so ignore them.
4341 Otherwise, whatever escapes must be on our RHS. */
4342 if (TREE_CODE (rhs
) == NOP_EXPR
4343 || TREE_CODE (rhs
) == CONVERT_EXPR
4344 || TREE_CODE (rhs
) == NON_LVALUE_EXPR
)
4346 get_constraint_for (TREE_OPERAND (rhs
, 0), &rhsc
);
4348 else if (CONSTANT_CLASS_P (rhs
))
4352 get_constraint_for (rhs
, &rhsc
);
4354 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, c
); i
++)
4355 make_constraint_to_escaped (*c
);
4356 VEC_free (ce_s
, heap
, rhsc
);
4359 /* Create points-to sets for the current function. See the comments
4360 at the start of the file for an algorithmic overview. */
4363 compute_points_to_sets (struct alias_info
*ai
)
4367 timevar_push (TV_TREE_PTA
);
4371 intra_create_variable_infos ();
4373 /* Now walk all statements and derive aliases. */
4376 block_stmt_iterator bsi
;
4379 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4381 if (is_gimple_reg (PHI_RESULT (phi
)))
4383 find_func_aliases (phi
);
4384 /* Update various related attributes like escaped
4385 addresses, pointer dereferences for loads and stores.
4386 This is used when creating name tags and alias
4388 update_alias_info (phi
, ai
);
4392 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4394 tree stmt
= bsi_stmt (bsi
);
4396 find_func_aliases (stmt
);
4397 find_escape_constraints (stmt
);
4398 /* Update various related attributes like escaped
4399 addresses, pointer dereferences for loads and stores.
4400 This is used when creating name tags and alias
4402 update_alias_info (stmt
, ai
);
4406 build_constraint_graph ();
4410 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4411 dump_constraints (dump_file
);
4416 "\nCollapsing static cycles and doing variable "
4419 find_and_collapse_graph_cycles (graph
, false);
4420 perform_var_substitution (graph
);
4423 fprintf (dump_file
, "\nSolving graph:\n");
4425 solve_graph (graph
);
4428 dump_sa_points_to_info (dump_file
);
4430 have_alias_info
= true;
4432 timevar_pop (TV_TREE_PTA
);
4436 /* Delete created points-to sets. */
4439 delete_points_to_sets (void)
4444 htab_delete (id_for_tree
);
4445 bitmap_obstack_release (&ptabitmap_obstack
);
4446 bitmap_obstack_release (&predbitmap_obstack
);
4447 VEC_free (constraint_t
, heap
, constraints
);
4449 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4451 /* Nonlocal vars may add more varinfos. */
4452 if (i
>= graph_size
)
4455 VEC_free (constraint_t
, heap
, v
->complex);
4457 free (graph
->preds
);
4458 free (graph
->succs
);
4461 VEC_free (varinfo_t
, heap
, varmap
);
4462 free_alloc_pool (variable_info_pool
);
4463 free_alloc_pool (constraint_pool
);
4464 have_alias_info
= false;
4467 /* Return true if we should execute IPA PTA. */
4471 return (flag_unit_at_a_time
!= 0
4473 /* Don't bother doing anything if the program has errors. */
4474 && !(errorcount
|| sorrycount
));
4477 /* Execute the driver for IPA PTA. */
4479 ipa_pta_execute (void)
4481 struct cgraph_node
*node
;
4483 init_alias_heapvars ();
4486 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4488 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
4492 varid
= create_function_info_for (node
->decl
,
4493 cgraph_node_name (node
));
4494 if (node
->local
.externally_visible
)
4496 varinfo_t fi
= get_varinfo (varid
);
4497 for (; fi
; fi
= fi
->next
)
4498 make_constraint_from_escaped (fi
);
4502 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4504 if (node
->analyzed
&& cgraph_is_master_clone (node
))
4506 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
4508 tree old_func_decl
= current_function_decl
;
4511 "Generating constraints for %s\n",
4512 cgraph_node_name (node
));
4514 current_function_decl
= node
->decl
;
4516 FOR_EACH_BB_FN (bb
, cfun
)
4518 block_stmt_iterator bsi
;
4521 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4523 if (is_gimple_reg (PHI_RESULT (phi
)))
4525 find_func_aliases (phi
);
4529 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4531 tree stmt
= bsi_stmt (bsi
);
4532 find_func_aliases (stmt
);
4535 current_function_decl
= old_func_decl
;
4540 /* Make point to anything. */
4544 build_constraint_graph ();
4548 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4549 dump_constraints (dump_file
);
4554 "\nCollapsing static cycles and doing variable "
4557 find_and_collapse_graph_cycles (graph
, false);
4558 perform_var_substitution (graph
);
4561 fprintf (dump_file
, "\nSolving graph:\n");
4563 solve_graph (graph
);
4566 dump_sa_points_to_info (dump_file
);
4568 delete_alias_heapvars ();
4569 delete_points_to_sets ();
4573 struct tree_opt_pass pass_ipa_pta
=
4576 gate_ipa_pta
, /* gate */
4577 ipa_pta_execute
, /* execute */
4580 0, /* static_pass_number */
4581 TV_IPA_PTA
, /* tv_id */
4582 0, /* properties_required */
4583 0, /* properties_provided */
4584 0, /* properties_destroyed */
4585 0, /* todo_flags_start */
4586 0, /* todo_flags_finish */
4590 /* Initialize the heapvar for statement mapping. */
4592 init_alias_heapvars (void)
4594 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
,
4596 cfun
->gimple_df
->nonlocal_all
= NULL_TREE
;
4600 delete_alias_heapvars (void)
4602 cfun
->gimple_df
->nonlocal_all
= NULL_TREE
;
4603 htab_delete (heapvar_for_stmt
);
4607 #include "gt-tree-ssa-structalias.h"