1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
43 #include "tree-gimple.h"
47 #include "tree-pass.h"
49 #include "alloc-pool.h"
50 #include "splay-tree.h"
52 #include "tree-ssa-structalias.h"
55 #include "pointer-set.h"
57 /* The idea behind this analyzer is to generate set constraints from the
58 program, then solve the resulting constraints in order to generate the
61 Set constraints are a way of modeling program analysis problems that
62 involve sets. They consist of an inclusion constraint language,
63 describing the variables (each variable is a set) and operations that
64 are involved on the variables, and a set of rules that derive facts
65 from these operations. To solve a system of set constraints, you derive
66 all possible facts under the rules, which gives you the correct sets
69 See "Efficient Field-sensitive pointer analysis for C" by "David
70 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
71 http://citeseer.ist.psu.edu/pearce04efficient.html
73 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
74 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
75 http://citeseer.ist.psu.edu/heintze01ultrafast.html
77 There are three types of real constraint expressions, DEREF,
78 ADDRESSOF, and SCALAR. Each constraint expression consists
79 of a constraint type, a variable, and an offset.
81 SCALAR is a constraint expression type used to represent x, whether
82 it appears on the LHS or the RHS of a statement.
83 DEREF is a constraint expression type used to represent *x, whether
84 it appears on the LHS or the RHS of a statement.
85 ADDRESSOF is a constraint expression used to represent &x, whether
86 it appears on the LHS or the RHS of a statement.
88 Each pointer variable in the program is assigned an integer id, and
89 each field of a structure variable is assigned an integer id as well.
91 Structure variables are linked to their list of fields through a "next
92 field" in each variable that points to the next field in offset
94 Each variable for a structure field has
96 1. "size", that tells the size in bits of that field.
97 2. "fullsize, that tells the size in bits of the entire structure.
98 3. "offset", that tells the offset in bits from the beginning of the
99 structure to this field.
111 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
112 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
113 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
116 In order to solve the system of set constraints, the following is
119 1. Each constraint variable x has a solution set associated with it,
122 2. Constraints are separated into direct, copy, and complex.
123 Direct constraints are ADDRESSOF constraints that require no extra
124 processing, such as P = &Q
125 Copy constraints are those of the form P = Q.
126 Complex constraints are all the constraints involving dereferences
127 and offsets (including offsetted copies).
129 3. All direct constraints of the form P = &Q are processed, such
130 that Q is added to Sol(P)
132 4. All complex constraints for a given constraint variable are stored in a
133 linked list attached to that variable's node.
135 5. A directed graph is built out of the copy constraints. Each
136 constraint variable is a node in the graph, and an edge from
137 Q to P is added for each copy constraint of the form P = Q
139 6. The graph is then walked, and solution sets are
140 propagated along the copy edges, such that an edge from Q to P
141 causes Sol(P) <- Sol(P) union Sol(Q).
143 7. As we visit each node, all complex constraints associated with
144 that node are processed by adding appropriate copy edges to the graph, or the
145 appropriate variables to the solution set.
147 8. The process of walking the graph is iterated until no solution
150 Prior to walking the graph in steps 6 and 7, We perform static
151 cycle elimination on the constraint graph, as well
152 as off-line variable substitution.
154 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
155 on and turned into anything), but isn't. You can just see what offset
156 inside the pointed-to struct it's going to access.
158 TODO: Constant bounded arrays can be handled as if they were structs of the
159 same number of elements.
161 TODO: Modeling heap and incoming pointers becomes much better if we
162 add fields to them as we discover them, which we could do.
164 TODO: We could handle unions, but to be honest, it's probably not
165 worth the pain or slowdown. */
167 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map
)))
168 htab_t heapvar_for_stmt
;
170 static bool use_field_sensitive
= true;
171 static int in_ipa_mode
= 0;
173 /* Used for predecessor bitmaps. */
174 static bitmap_obstack predbitmap_obstack
;
176 /* Used for points-to sets. */
177 static bitmap_obstack pta_obstack
;
179 /* Used for oldsolution members of variables. */
180 static bitmap_obstack oldpta_obstack
;
182 /* Used for per-solver-iteration bitmaps. */
183 static bitmap_obstack iteration_obstack
;
185 static unsigned int create_variable_info_for (tree
, const char *);
186 typedef struct constraint_graph
*constraint_graph_t
;
187 static void unify_nodes (constraint_graph_t
, unsigned int, unsigned int, bool);
189 DEF_VEC_P(constraint_t
);
190 DEF_VEC_ALLOC_P(constraint_t
,heap
);
192 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
194 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
196 static struct constraint_stats
198 unsigned int total_vars
;
199 unsigned int nonpointer_vars
;
200 unsigned int unified_vars_static
;
201 unsigned int unified_vars_dynamic
;
202 unsigned int iterations
;
203 unsigned int num_edges
;
204 unsigned int num_implicit_edges
;
205 unsigned int points_to_sets_created
;
210 /* ID of this variable */
213 /* Name of this variable */
216 /* Tree that this variable is associated with. */
219 /* Offset of this variable, in bits, from the base variable */
220 unsigned HOST_WIDE_INT offset
;
222 /* Size of the variable, in bits. */
223 unsigned HOST_WIDE_INT size
;
225 /* Full size of the base variable, in bits. */
226 unsigned HOST_WIDE_INT fullsize
;
228 /* A link to the variable for the next field in this structure. */
229 struct variable_info
*next
;
231 /* True if the variable is directly the target of a dereference.
232 This is used to track which variables are *actually* dereferenced
233 so we can prune their points to listed. */
234 unsigned int directly_dereferenced
:1;
236 /* True if this is a variable created by the constraint analysis, such as
237 heap variables and constraints we had to break up. */
238 unsigned int is_artificial_var
:1;
240 /* True if this is a special variable whose solution set should not be
242 unsigned int is_special_var
:1;
244 /* True for variables whose size is not known or variable. */
245 unsigned int is_unknown_size_var
:1;
247 /* True for variables that have unions somewhere in them. */
248 unsigned int has_union
:1;
250 /* True if this is a heap variable. */
251 unsigned int is_heap_var
:1;
253 /* True if we may not use TBAA to prune references to this
254 variable. This is used for C++ placement new. */
255 unsigned int no_tbaa_pruning
: 1;
257 /* Points-to set for this variable. */
260 /* Old points-to set for this variable. */
263 /* Variable ids represented by this node. */
266 /* Variable id this was collapsed to due to type unsafety. This
267 should be unused completely after build_succ_graph, or something
269 struct variable_info
*collapsed_to
;
271 typedef struct variable_info
*varinfo_t
;
273 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
275 /* Pool of variable info structures. */
276 static alloc_pool variable_info_pool
;
278 DEF_VEC_P(varinfo_t
);
280 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
282 /* Table of variable info structures for constraint variables.
283 Indexed directly by variable info id. */
284 static VEC(varinfo_t
,heap
) *varmap
;
286 /* Return the varmap element N */
288 static inline varinfo_t
289 get_varinfo (unsigned int n
)
291 return VEC_index (varinfo_t
, varmap
, n
);
294 /* Return the varmap element N, following the collapsed_to link. */
296 static inline varinfo_t
297 get_varinfo_fc (unsigned int n
)
299 varinfo_t v
= VEC_index (varinfo_t
, varmap
, n
);
302 return v
->collapsed_to
;
306 /* Variable that represents the unknown pointer. */
307 static varinfo_t var_anything
;
308 static tree anything_tree
;
309 static unsigned int anything_id
;
311 /* Variable that represents the NULL pointer. */
312 static varinfo_t var_nothing
;
313 static tree nothing_tree
;
314 static unsigned int nothing_id
;
316 /* Variable that represents read only memory. */
317 static varinfo_t var_readonly
;
318 static tree readonly_tree
;
319 static unsigned int readonly_id
;
321 /* Variable that represents integers. This is used for when people do things
323 static varinfo_t var_integer
;
324 static tree integer_tree
;
325 static unsigned int integer_id
;
327 /* Lookup a heap var for FROM, and return it if we find one. */
330 heapvar_lookup (tree from
)
332 struct tree_map
*h
, in
;
335 h
= (struct tree_map
*) htab_find_with_hash (heapvar_for_stmt
, &in
,
336 htab_hash_pointer (from
));
342 /* Insert a mapping FROM->TO in the heap var for statement
346 heapvar_insert (tree from
, tree to
)
351 h
= GGC_NEW (struct tree_map
);
352 h
->hash
= htab_hash_pointer (from
);
355 loc
= htab_find_slot_with_hash (heapvar_for_stmt
, h
, h
->hash
, INSERT
);
356 *(struct tree_map
**) loc
= h
;
359 /* Return a new variable info structure consisting for a variable
360 named NAME, and using constraint graph node NODE. */
363 new_var_info (tree t
, unsigned int id
, const char *name
)
365 varinfo_t ret
= (varinfo_t
) pool_alloc (variable_info_pool
);
371 ret
->directly_dereferenced
= false;
372 ret
->is_artificial_var
= false;
373 ret
->is_heap_var
= false;
374 ret
->is_special_var
= false;
375 ret
->is_unknown_size_var
= false;
376 ret
->has_union
= false;
378 if (TREE_CODE (var
) == SSA_NAME
)
379 var
= SSA_NAME_VAR (var
);
380 ret
->no_tbaa_pruning
= (DECL_P (var
)
381 && POINTER_TYPE_P (TREE_TYPE (var
))
382 && DECL_NO_TBAA_P (var
));
383 ret
->solution
= BITMAP_ALLOC (&pta_obstack
);
384 ret
->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
386 ret
->collapsed_to
= NULL
;
390 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
392 /* An expression that appears in a constraint. */
394 struct constraint_expr
396 /* Constraint type. */
397 constraint_expr_type type
;
399 /* Variable we are referring to in the constraint. */
402 /* Offset, in bits, of this constraint from the beginning of
403 variables it ends up referring to.
405 IOW, in a deref constraint, we would deref, get the result set,
406 then add OFFSET to each member. */
407 unsigned HOST_WIDE_INT offset
;
410 typedef struct constraint_expr ce_s
;
412 DEF_VEC_ALLOC_O(ce_s
, heap
);
413 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
414 static void do_deref (VEC (ce_s
, heap
) **);
416 /* Our set constraints are made up of two constraint expressions, one
419 As described in the introduction, our set constraints each represent an
420 operation between set valued variables.
424 struct constraint_expr lhs
;
425 struct constraint_expr rhs
;
428 /* List of constraints that we use to build the constraint graph from. */
430 static VEC(constraint_t
,heap
) *constraints
;
431 static alloc_pool constraint_pool
;
435 DEF_VEC_ALLOC_I(int, heap
);
437 /* The constraint graph is represented as an array of bitmaps
438 containing successor nodes. */
440 struct constraint_graph
442 /* Size of this graph, which may be different than the number of
443 nodes in the variable map. */
446 /* Explicit successors of each node. */
449 /* Implicit predecessors of each node (Used for variable
451 bitmap
*implicit_preds
;
453 /* Explicit predecessors of each node (Used for variable substitution). */
456 /* Indirect cycle representatives, or -1 if the node has no indirect
458 int *indirect_cycles
;
460 /* Representative node for a node. rep[a] == a unless the node has
464 /* Equivalence class representative for a node. This is used for
465 variable substitution. */
468 /* Label for each node, used during variable substitution. */
471 /* Bitmap of nodes where the bit is set if the node is a direct
472 node. Used for variable substitution. */
473 sbitmap direct_nodes
;
475 /* Vector of complex constraints for each graph node. Complex
476 constraints are those involving dereferences or offsets that are
478 VEC(constraint_t
,heap
) **complex;
481 static constraint_graph_t graph
;
483 /* During variable substitution and the offline version of indirect
484 cycle finding, we create nodes to represent dereferences and
485 address taken constraints. These represent where these start and
487 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
488 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
489 #define FIRST_ADDR_NODE (LAST_REF_NODE + 1)
491 /* Return the representative node for NODE, if NODE has been unioned
493 This function performs path compression along the way to finding
494 the representative. */
497 find (unsigned int node
)
499 gcc_assert (node
< graph
->size
);
500 if (graph
->rep
[node
] != node
)
501 return graph
->rep
[node
] = find (graph
->rep
[node
]);
505 /* Union the TO and FROM nodes to the TO nodes.
506 Note that at some point in the future, we may want to do
507 union-by-rank, in which case we are going to have to return the
508 node we unified to. */
511 unite (unsigned int to
, unsigned int from
)
513 gcc_assert (to
< graph
->size
&& from
< graph
->size
);
514 if (to
!= from
&& graph
->rep
[from
] != to
)
516 graph
->rep
[from
] = to
;
522 /* Create a new constraint consisting of LHS and RHS expressions. */
525 new_constraint (const struct constraint_expr lhs
,
526 const struct constraint_expr rhs
)
528 constraint_t ret
= (constraint_t
) pool_alloc (constraint_pool
);
534 /* Print out constraint C to FILE. */
537 dump_constraint (FILE *file
, constraint_t c
)
539 if (c
->lhs
.type
== ADDRESSOF
)
541 else if (c
->lhs
.type
== DEREF
)
543 fprintf (file
, "%s", get_varinfo_fc (c
->lhs
.var
)->name
);
544 if (c
->lhs
.offset
!= 0)
545 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
546 fprintf (file
, " = ");
547 if (c
->rhs
.type
== ADDRESSOF
)
549 else if (c
->rhs
.type
== DEREF
)
551 fprintf (file
, "%s", get_varinfo_fc (c
->rhs
.var
)->name
);
552 if (c
->rhs
.offset
!= 0)
553 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
554 fprintf (file
, "\n");
557 /* Print out constraint C to stderr. */
560 debug_constraint (constraint_t c
)
562 dump_constraint (stderr
, c
);
565 /* Print out all constraints to FILE */
568 dump_constraints (FILE *file
)
572 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
573 dump_constraint (file
, c
);
576 /* Print out all constraints to stderr. */
579 debug_constraints (void)
581 dump_constraints (stderr
);
586 The solver is a simple worklist solver, that works on the following
589 sbitmap changed_nodes = all zeroes;
591 For each node that is not already collapsed:
593 set bit in changed nodes
595 while (changed_count > 0)
597 compute topological ordering for constraint graph
599 find and collapse cycles in the constraint graph (updating
600 changed if necessary)
602 for each node (n) in the graph in topological order:
605 Process each complex constraint associated with the node,
606 updating changed if necessary.
608 For each outgoing edge from n, propagate the solution from n to
609 the destination of the edge, updating changed as necessary.
613 /* Return true if two constraint expressions A and B are equal. */
616 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
618 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
621 /* Return true if constraint expression A is less than constraint expression
622 B. This is just arbitrary, but consistent, in order to give them an
626 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
628 if (a
.type
== b
.type
)
631 return a
.offset
< b
.offset
;
633 return a
.var
< b
.var
;
636 return a
.type
< b
.type
;
639 /* Return true if constraint A is less than constraint B. This is just
640 arbitrary, but consistent, in order to give them an ordering. */
643 constraint_less (const constraint_t a
, const constraint_t b
)
645 if (constraint_expr_less (a
->lhs
, b
->lhs
))
647 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
650 return constraint_expr_less (a
->rhs
, b
->rhs
);
653 /* Return true if two constraints A and B are equal. */
656 constraint_equal (struct constraint a
, struct constraint b
)
658 return constraint_expr_equal (a
.lhs
, b
.lhs
)
659 && constraint_expr_equal (a
.rhs
, b
.rhs
);
663 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
666 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
667 struct constraint lookfor
)
675 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
676 if (place
>= VEC_length (constraint_t
, vec
))
678 found
= VEC_index (constraint_t
, vec
, place
);
679 if (!constraint_equal (*found
, lookfor
))
684 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
687 constraint_set_union (VEC(constraint_t
,heap
) **to
,
688 VEC(constraint_t
,heap
) **from
)
693 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
695 if (constraint_vec_find (*to
, *c
) == NULL
)
697 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
699 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
704 /* Take a solution set SET, add OFFSET to each member of the set, and
705 overwrite SET with the result when done. */
708 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
710 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
714 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
716 /* If this is a properly sized variable, only add offset if it's
717 less than end. Otherwise, it is globbed to a single
720 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
722 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
723 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
726 bitmap_set_bit (result
, v
->id
);
728 else if (get_varinfo (i
)->is_artificial_var
729 || get_varinfo (i
)->has_union
730 || get_varinfo (i
)->is_unknown_size_var
)
732 bitmap_set_bit (result
, i
);
736 bitmap_copy (set
, result
);
737 BITMAP_FREE (result
);
740 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
744 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
747 return bitmap_ior_into (to
, from
);
753 tmp
= BITMAP_ALLOC (&iteration_obstack
);
754 bitmap_copy (tmp
, from
);
755 solution_set_add (tmp
, inc
);
756 res
= bitmap_ior_into (to
, tmp
);
762 /* Insert constraint C into the list of complex constraints for graph
766 insert_into_complex (constraint_graph_t graph
,
767 unsigned int var
, constraint_t c
)
769 VEC (constraint_t
, heap
) *complex = graph
->complex[var
];
770 unsigned int place
= VEC_lower_bound (constraint_t
, complex, c
,
773 /* Only insert constraints that do not already exist. */
774 if (place
>= VEC_length (constraint_t
, complex)
775 || !constraint_equal (*c
, *VEC_index (constraint_t
, complex, place
)))
776 VEC_safe_insert (constraint_t
, heap
, graph
->complex[var
], place
, c
);
780 /* Condense two variable nodes into a single variable node, by moving
781 all associated info from SRC to TO. */
784 merge_node_constraints (constraint_graph_t graph
, unsigned int to
,
790 gcc_assert (find (from
) == to
);
792 /* Move all complex constraints from src node into to node */
793 for (i
= 0; VEC_iterate (constraint_t
, graph
->complex[from
], i
, c
); i
++)
795 /* In complex constraints for node src, we may have either
796 a = *src, and *src = a, or an offseted constraint which are
797 always added to the rhs node's constraints. */
799 if (c
->rhs
.type
== DEREF
)
801 else if (c
->lhs
.type
== DEREF
)
806 constraint_set_union (&graph
->complex[to
], &graph
->complex[from
]);
807 VEC_free (constraint_t
, heap
, graph
->complex[from
]);
808 graph
->complex[from
] = NULL
;
812 /* Remove edges involving NODE from GRAPH. */
815 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
817 if (graph
->succs
[node
])
818 BITMAP_FREE (graph
->succs
[node
]);
821 /* Merge GRAPH nodes FROM and TO into node TO. */
824 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
827 if (graph
->indirect_cycles
[from
] != -1)
829 /* If we have indirect cycles with the from node, and we have
830 none on the to node, the to node has indirect cycles from the
831 from node now that they are unified.
832 If indirect cycles exist on both, unify the nodes that they
833 are in a cycle with, since we know they are in a cycle with
835 if (graph
->indirect_cycles
[to
] == -1)
837 graph
->indirect_cycles
[to
] = graph
->indirect_cycles
[from
];
841 unsigned int tonode
= find (graph
->indirect_cycles
[to
]);
842 unsigned int fromnode
= find (graph
->indirect_cycles
[from
]);
844 if (unite (tonode
, fromnode
))
845 unify_nodes (graph
, tonode
, fromnode
, true);
849 /* Merge all the successor edges. */
850 if (graph
->succs
[from
])
852 if (!graph
->succs
[to
])
853 graph
->succs
[to
] = BITMAP_ALLOC (&pta_obstack
);
854 bitmap_ior_into (graph
->succs
[to
],
858 clear_edges_for_node (graph
, from
);
862 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
863 it doesn't exist in the graph already. */
866 add_implicit_graph_edge (constraint_graph_t graph
, unsigned int to
,
872 if (!graph
->implicit_preds
[to
])
873 graph
->implicit_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
875 if (!bitmap_bit_p (graph
->implicit_preds
[to
], from
))
877 stats
.num_implicit_edges
++;
878 bitmap_set_bit (graph
->implicit_preds
[to
], from
);
882 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
883 it doesn't exist in the graph already.
884 Return false if the edge already existed, true otherwise. */
887 add_pred_graph_edge (constraint_graph_t graph
, unsigned int to
,
890 if (!graph
->preds
[to
])
891 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
892 if (!bitmap_bit_p (graph
->preds
[to
], from
))
893 bitmap_set_bit (graph
->preds
[to
], from
);
896 /* Add a graph edge to GRAPH, going from FROM to TO if
897 it doesn't exist in the graph already.
898 Return false if the edge already existed, true otherwise. */
901 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
912 if (!graph
->succs
[from
])
913 graph
->succs
[from
] = BITMAP_ALLOC (&pta_obstack
);
914 if (!bitmap_bit_p (graph
->succs
[from
], to
))
917 if (to
< FIRST_REF_NODE
&& from
< FIRST_REF_NODE
)
919 bitmap_set_bit (graph
->succs
[from
], to
);
926 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
929 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
932 return (graph
->succs
[dest
]
933 && bitmap_bit_p (graph
->succs
[dest
], src
));
936 /* Build the constraint graph, adding only predecessor edges right now. */
939 build_pred_graph (void)
945 graph
= XNEW (struct constraint_graph
);
946 graph
->size
= (VEC_length (varinfo_t
, varmap
)) * 3;
947 graph
->succs
= XCNEWVEC (bitmap
, graph
->size
);
948 graph
->implicit_preds
= XCNEWVEC (bitmap
, graph
->size
);
949 graph
->preds
= XCNEWVEC (bitmap
, graph
->size
);
950 graph
->indirect_cycles
= XNEWVEC (int, VEC_length (varinfo_t
, varmap
));
951 graph
->label
= XCNEWVEC (unsigned int, graph
->size
);
952 graph
->rep
= XNEWVEC (unsigned int, graph
->size
);
953 graph
->eq_rep
= XNEWVEC (int, graph
->size
);
954 graph
->complex = XCNEWVEC (VEC(constraint_t
, heap
) *,
955 VEC_length (varinfo_t
, varmap
));
956 graph
->direct_nodes
= sbitmap_alloc (graph
->size
);
957 sbitmap_zero (graph
->direct_nodes
);
959 for (j
= 0; j
< FIRST_REF_NODE
; j
++)
961 if (!get_varinfo (j
)->is_special_var
)
962 SET_BIT (graph
->direct_nodes
, j
);
965 for (j
= 0; j
< graph
->size
; j
++)
968 graph
->eq_rep
[j
] = -1;
971 for (j
= 0; j
< VEC_length (varinfo_t
, varmap
); j
++)
972 graph
->indirect_cycles
[j
] = -1;
974 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
976 struct constraint_expr lhs
= c
->lhs
;
977 struct constraint_expr rhs
= c
->rhs
;
978 unsigned int lhsvar
= get_varinfo_fc (lhs
.var
)->id
;
979 unsigned int rhsvar
= get_varinfo_fc (rhs
.var
)->id
;
981 if (lhs
.type
== DEREF
)
984 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
985 add_pred_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
986 if (rhs
.type
== ADDRESSOF
)
987 RESET_BIT (graph
->direct_nodes
, rhsvar
);
989 else if (rhs
.type
== DEREF
)
992 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
993 add_pred_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
995 RESET_BIT (graph
->direct_nodes
, lhsvar
);
997 else if (rhs
.type
== ADDRESSOF
)
1000 add_pred_graph_edge (graph
, lhsvar
, FIRST_ADDR_NODE
+ rhsvar
);
1001 /* Implicitly, *x = y */
1002 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1004 RESET_BIT (graph
->direct_nodes
, rhsvar
);
1006 else if (lhsvar
> anything_id
1007 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1010 add_pred_graph_edge (graph
, lhsvar
, rhsvar
);
1011 /* Implicitly, *x = *y */
1012 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
,
1013 FIRST_REF_NODE
+ rhsvar
);
1015 else if (lhs
.offset
!= 0 || rhs
.offset
!= 0)
1017 if (rhs
.offset
!= 0)
1018 RESET_BIT (graph
->direct_nodes
, lhs
.var
);
1019 if (lhs
.offset
!= 0)
1020 RESET_BIT (graph
->direct_nodes
, rhs
.var
);
1025 /* Build the constraint graph, adding successor edges. */
1028 build_succ_graph (void)
1033 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1035 struct constraint_expr lhs
;
1036 struct constraint_expr rhs
;
1037 unsigned int lhsvar
;
1038 unsigned int rhsvar
;
1045 lhsvar
= find (get_varinfo_fc (lhs
.var
)->id
);
1046 rhsvar
= find (get_varinfo_fc (rhs
.var
)->id
);
1048 if (lhs
.type
== DEREF
)
1050 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1051 add_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1053 else if (rhs
.type
== DEREF
)
1055 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1056 add_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1058 else if (rhs
.type
== ADDRESSOF
)
1061 gcc_assert (find (get_varinfo_fc (rhs
.var
)->id
)
1062 == get_varinfo_fc (rhs
.var
)->id
);
1063 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1065 else if (lhsvar
> anything_id
1066 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1068 add_graph_edge (graph
, lhsvar
, rhsvar
);
1074 /* Changed variables on the last iteration. */
1075 static unsigned int changed_count
;
1076 static sbitmap changed
;
1078 DEF_VEC_I(unsigned);
1079 DEF_VEC_ALLOC_I(unsigned,heap
);
1082 /* Strongly Connected Component visitation info. */
1089 unsigned int *node_mapping
;
1091 VEC(unsigned,heap
) *scc_stack
;
1095 /* Recursive routine to find strongly connected components in GRAPH.
1096 SI is the SCC info to store the information in, and N is the id of current
1097 graph node we are processing.
1099 This is Tarjan's strongly connected component finding algorithm, as
1100 modified by Nuutila to keep only non-root nodes on the stack.
1101 The algorithm can be found in "On finding the strongly connected
1102 connected components in a directed graph" by Esko Nuutila and Eljas
1103 Soisalon-Soininen, in Information Processing Letters volume 49,
1104 number 1, pages 9-14. */
1107 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1111 unsigned int my_dfs
;
1113 SET_BIT (si
->visited
, n
);
1114 si
->dfs
[n
] = si
->current_index
++;
1115 my_dfs
= si
->dfs
[n
];
1117 /* Visit all the successors. */
1118 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
1122 if (i
> LAST_REF_NODE
)
1126 if (TEST_BIT (si
->roots
, w
))
1129 if (!TEST_BIT (si
->visited
, w
))
1130 scc_visit (graph
, si
, w
);
1132 unsigned int t
= find (w
);
1133 unsigned int nnode
= find (n
);
1134 gcc_assert (nnode
== n
);
1136 if (si
->dfs
[t
] < si
->dfs
[nnode
])
1137 si
->dfs
[n
] = si
->dfs
[t
];
1141 /* See if any components have been identified. */
1142 if (si
->dfs
[n
] == my_dfs
)
1144 if (VEC_length (unsigned, si
->scc_stack
) > 0
1145 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1147 bitmap scc
= BITMAP_ALLOC (NULL
);
1148 bool have_ref_node
= n
>= FIRST_REF_NODE
;
1149 unsigned int lowest_node
;
1152 bitmap_set_bit (scc
, n
);
1154 while (VEC_length (unsigned, si
->scc_stack
) != 0
1155 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1157 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1159 bitmap_set_bit (scc
, w
);
1160 if (w
>= FIRST_REF_NODE
)
1161 have_ref_node
= true;
1164 lowest_node
= bitmap_first_set_bit (scc
);
1165 gcc_assert (lowest_node
< FIRST_REF_NODE
);
1166 EXECUTE_IF_SET_IN_BITMAP (scc
, 0, i
, bi
)
1168 if (i
< FIRST_REF_NODE
)
1170 /* Mark this node for collapsing. */
1171 if (unite (lowest_node
, i
))
1172 unify_nodes (graph
, lowest_node
, i
, false);
1176 unite (lowest_node
, i
);
1177 graph
->indirect_cycles
[i
- FIRST_REF_NODE
] = lowest_node
;
1181 SET_BIT (si
->roots
, n
);
1184 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1187 /* Unify node FROM into node TO, updating the changed count if
1188 necessary when UPDATE_CHANGED is true. */
1191 unify_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1192 bool update_changed
)
1195 gcc_assert (to
!= from
&& find (to
) == to
);
1196 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1197 fprintf (dump_file
, "Unifying %s to %s\n",
1198 get_varinfo (from
)->name
,
1199 get_varinfo (to
)->name
);
1202 stats
.unified_vars_dynamic
++;
1204 stats
.unified_vars_static
++;
1206 merge_graph_nodes (graph
, to
, from
);
1207 merge_node_constraints (graph
, to
, from
);
1209 if (get_varinfo (from
)->no_tbaa_pruning
)
1210 get_varinfo (to
)->no_tbaa_pruning
= true;
1212 if (update_changed
&& TEST_BIT (changed
, from
))
1214 RESET_BIT (changed
, from
);
1215 if (!TEST_BIT (changed
, to
))
1216 SET_BIT (changed
, to
);
1219 gcc_assert (changed_count
> 0);
1224 /* If the solution changes because of the merging, we need to mark
1225 the variable as changed. */
1226 if (bitmap_ior_into (get_varinfo (to
)->solution
,
1227 get_varinfo (from
)->solution
))
1229 if (update_changed
&& !TEST_BIT (changed
, to
))
1231 SET_BIT (changed
, to
);
1236 BITMAP_FREE (get_varinfo (from
)->solution
);
1237 BITMAP_FREE (get_varinfo (from
)->oldsolution
);
1239 if (stats
.iterations
> 0)
1241 BITMAP_FREE (get_varinfo (to
)->oldsolution
);
1242 get_varinfo (to
)->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
1245 if (valid_graph_edge (graph
, to
, to
))
1247 if (graph
->succs
[to
])
1248 bitmap_clear_bit (graph
->succs
[to
], to
);
1252 /* Information needed to compute the topological ordering of a graph. */
1256 /* sbitmap of visited nodes. */
1258 /* Array that stores the topological order of the graph, *in
1260 VEC(unsigned,heap
) *topo_order
;
1264 /* Initialize and return a topological info structure. */
1266 static struct topo_info
*
1267 init_topo_info (void)
1269 size_t size
= VEC_length (varinfo_t
, varmap
);
1270 struct topo_info
*ti
= XNEW (struct topo_info
);
1271 ti
->visited
= sbitmap_alloc (size
);
1272 sbitmap_zero (ti
->visited
);
1273 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1278 /* Free the topological sort info pointed to by TI. */
1281 free_topo_info (struct topo_info
*ti
)
1283 sbitmap_free (ti
->visited
);
1284 VEC_free (unsigned, heap
, ti
->topo_order
);
1288 /* Visit the graph in topological order, and store the order in the
1289 topo_info structure. */
1292 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1298 SET_BIT (ti
->visited
, n
);
1300 if (graph
->succs
[n
])
1301 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[n
], 0, j
, bi
)
1303 if (!TEST_BIT (ti
->visited
, j
))
1304 topo_visit (graph
, ti
, j
);
1307 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1310 /* Return true if variable N + OFFSET is a legal field of N. */
1313 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1315 varinfo_t ninfo
= get_varinfo (n
);
1317 /* For things we've globbed to single variables, any offset into the
1318 variable acts like the entire variable, so that it becomes offset
1320 if (ninfo
->is_special_var
1321 || ninfo
->is_artificial_var
1322 || ninfo
->is_unknown_size_var
)
1327 return (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1330 /* Process a constraint C that represents *x = &y. */
1333 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1334 constraint_t c
, bitmap delta
)
1336 unsigned int rhs
= c
->rhs
.var
;
1340 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1341 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1343 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1344 if (type_safe (j
, &offset
) && !(get_varinfo (j
)->is_special_var
))
1346 /* *x != NULL && *x != ANYTHING*/
1350 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1352 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1356 sol
= get_varinfo (t
)->solution
;
1357 if (!bitmap_bit_p (sol
, rhs
))
1359 bitmap_set_bit (sol
, rhs
);
1360 if (!TEST_BIT (changed
, t
))
1362 SET_BIT (changed
, t
);
1367 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1368 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1373 /* Process a constraint C that represents x = *y, using DELTA as the
1374 starting solution. */
1377 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1380 unsigned int lhs
= find (c
->lhs
.var
);
1382 bitmap sol
= get_varinfo (lhs
)->solution
;
1386 if (bitmap_bit_p (delta
, anything_id
))
1388 flag
= !bitmap_bit_p (sol
, anything_id
);
1390 bitmap_set_bit (sol
, anything_id
);
1393 /* For each variable j in delta (Sol(y)), add
1394 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1395 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1397 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1398 if (type_safe (j
, &roffset
))
1401 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1404 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1409 /* Adding edges from the special vars is pointless.
1410 They don't have sets that can change. */
1411 if (get_varinfo (t
) ->is_special_var
)
1412 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1413 else if (add_graph_edge (graph
, lhs
, t
))
1414 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1416 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1417 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1422 /* If the LHS solution changed, mark the var as changed. */
1425 get_varinfo (lhs
)->solution
= sol
;
1426 if (!TEST_BIT (changed
, lhs
))
1428 SET_BIT (changed
, lhs
);
1434 /* Process a constraint C that represents *x = y. */
1437 do_ds_constraint (constraint_t c
, bitmap delta
)
1439 unsigned int rhs
= find (c
->rhs
.var
);
1440 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1441 bitmap sol
= get_varinfo (rhs
)->solution
;
1445 if (bitmap_bit_p (sol
, anything_id
))
1447 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1449 varinfo_t jvi
= get_varinfo (j
);
1451 unsigned int loff
= c
->lhs
.offset
;
1452 unsigned HOST_WIDE_INT fieldoffset
= jvi
->offset
+ loff
;
1455 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1460 if (!bitmap_bit_p (get_varinfo (t
)->solution
, anything_id
))
1462 bitmap_set_bit (get_varinfo (t
)->solution
, anything_id
);
1463 if (!TEST_BIT (changed
, t
))
1465 SET_BIT (changed
, t
);
1473 /* For each member j of delta (Sol(x)), add an edge from y to j and
1474 union Sol(y) into Sol(j) */
1475 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1477 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1478 if (type_safe (j
, &loff
) && !(get_varinfo (j
)->is_special_var
))
1482 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1485 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1489 tmp
= get_varinfo (t
)->solution
;
1491 if (set_union_with_increment (tmp
, sol
, roff
))
1493 get_varinfo (t
)->solution
= tmp
;
1495 sol
= get_varinfo (rhs
)->solution
;
1496 if (!TEST_BIT (changed
, t
))
1498 SET_BIT (changed
, t
);
1503 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1504 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1508 /* Handle a non-simple (simple meaning requires no iteration),
1509 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1512 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1514 if (c
->lhs
.type
== DEREF
)
1516 if (c
->rhs
.type
== ADDRESSOF
)
1519 do_da_constraint (graph
, c
, delta
);
1524 do_ds_constraint (c
, delta
);
1527 else if (c
->rhs
.type
== DEREF
)
1530 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1531 do_sd_constraint (graph
, c
, delta
);
1540 gcc_assert (c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
);
1541 t
= find (c
->rhs
.var
);
1542 solution
= get_varinfo (t
)->solution
;
1543 t
= find (c
->lhs
.var
);
1544 tmp
= get_varinfo (t
)->solution
;
1546 flag
= set_union_with_increment (tmp
, solution
, c
->rhs
.offset
);
1550 get_varinfo (t
)->solution
= tmp
;
1551 if (!TEST_BIT (changed
, t
))
1553 SET_BIT (changed
, t
);
1560 /* Initialize and return a new SCC info structure. */
1562 static struct scc_info
*
1563 init_scc_info (size_t size
)
1565 struct scc_info
*si
= XNEW (struct scc_info
);
1568 si
->current_index
= 0;
1569 si
->visited
= sbitmap_alloc (size
);
1570 sbitmap_zero (si
->visited
);
1571 si
->roots
= sbitmap_alloc (size
);
1572 sbitmap_zero (si
->roots
);
1573 si
->node_mapping
= XNEWVEC (unsigned int, size
);
1574 si
->dfs
= XCNEWVEC (unsigned int, size
);
1576 for (i
= 0; i
< size
; i
++)
1577 si
->node_mapping
[i
] = i
;
1579 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1583 /* Free an SCC info structure pointed to by SI */
1586 free_scc_info (struct scc_info
*si
)
1588 sbitmap_free (si
->visited
);
1589 sbitmap_free (si
->roots
);
1590 free (si
->node_mapping
);
1592 VEC_free (unsigned, heap
, si
->scc_stack
);
1597 /* Find indirect cycles in GRAPH that occur, using strongly connected
1598 components, and note them in the indirect cycles map.
1600 This technique comes from Ben Hardekopf and Calvin Lin,
1601 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1602 Lines of Code", submitted to PLDI 2007. */
1605 find_indirect_cycles (constraint_graph_t graph
)
1608 unsigned int size
= graph
->size
;
1609 struct scc_info
*si
= init_scc_info (size
);
1611 for (i
= 0; i
< MIN (LAST_REF_NODE
, size
); i
++ )
1612 if (!TEST_BIT (si
->visited
, i
) && find (i
) == i
)
1613 scc_visit (graph
, si
, i
);
1618 /* Compute a topological ordering for GRAPH, and store the result in the
1619 topo_info structure TI. */
1622 compute_topo_order (constraint_graph_t graph
,
1623 struct topo_info
*ti
)
1626 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1628 for (i
= 0; i
!= size
; ++i
)
1629 if (!TEST_BIT (ti
->visited
, i
) && find (i
) == i
)
1630 topo_visit (graph
, ti
, i
);
1633 /* Perform offline variable substitution.
1635 This is a linear time way of identifying variables that must have
1636 equivalent points-to sets, including those caused by static cycles,
1637 and single entry subgraphs, in the constraint graph.
1639 The technique is described in "Off-line variable substitution for
1640 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1641 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56.
1643 There is an optimal way to do this involving hash based value
1644 numbering, once the technique is published i will implement it
1647 The general method of finding equivalence classes is as follows:
1648 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1649 Add fake nodes (ADDRESS nodes) and edges for a = &b constraints.
1650 Initialize all non-REF/ADDRESS nodes to be direct nodes
1651 For each SCC in the predecessor graph:
1652 for each member (x) of the SCC
1653 if x is not a direct node:
1654 set rootnode(SCC) to be not a direct node
1655 collapse node x into rootnode(SCC).
1656 if rootnode(SCC) is not a direct node:
1657 label rootnode(SCC) with a new equivalence class
1659 if all labeled predecessors of rootnode(SCC) have the same
1661 label rootnode(SCC) with this label
1663 label rootnode(SCC) with a new equivalence class
1665 All direct nodes with the same equivalence class can be replaced
1666 with a single representative node.
1667 All unlabeled nodes (label == 0) are not pointers and all edges
1668 involving them can be eliminated.
1669 We perform these optimizations during move_complex_constraints.
1672 static int equivalence_class
;
1674 /* Recursive routine to find strongly connected components in GRAPH,
1675 and label it's nodes with equivalence classes.
1676 This is used during variable substitution to find cycles involving
1677 the regular or implicit predecessors, and label them as equivalent.
1678 The SCC finding algorithm used is the same as that for scc_visit. */
1681 label_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1685 unsigned int my_dfs
;
1687 gcc_assert (si
->node_mapping
[n
] == n
);
1688 SET_BIT (si
->visited
, n
);
1689 si
->dfs
[n
] = si
->current_index
++;
1690 my_dfs
= si
->dfs
[n
];
1692 /* Visit all the successors. */
1693 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
1695 unsigned int w
= si
->node_mapping
[i
];
1697 if (TEST_BIT (si
->roots
, w
))
1700 if (!TEST_BIT (si
->visited
, w
))
1701 label_visit (graph
, si
, w
);
1703 unsigned int t
= si
->node_mapping
[w
];
1704 unsigned int nnode
= si
->node_mapping
[n
];
1705 gcc_assert (nnode
== n
);
1707 if (si
->dfs
[t
] < si
->dfs
[nnode
])
1708 si
->dfs
[n
] = si
->dfs
[t
];
1712 /* Visit all the implicit predecessors. */
1713 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->implicit_preds
[n
], 0, i
, bi
)
1715 unsigned int w
= si
->node_mapping
[i
];
1717 if (TEST_BIT (si
->roots
, w
))
1720 if (!TEST_BIT (si
->visited
, w
))
1721 label_visit (graph
, si
, w
);
1723 unsigned int t
= si
->node_mapping
[w
];
1724 unsigned int nnode
= si
->node_mapping
[n
];
1725 gcc_assert (nnode
== n
);
1727 if (si
->dfs
[t
] < si
->dfs
[nnode
])
1728 si
->dfs
[n
] = si
->dfs
[t
];
1732 /* See if any components have been identified. */
1733 if (si
->dfs
[n
] == my_dfs
)
1735 while (VEC_length (unsigned, si
->scc_stack
) != 0
1736 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1738 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1739 si
->node_mapping
[w
] = n
;
1741 if (!TEST_BIT (graph
->direct_nodes
, w
))
1742 RESET_BIT (graph
->direct_nodes
, n
);
1744 SET_BIT (si
->roots
, n
);
1746 if (!TEST_BIT (graph
->direct_nodes
, n
))
1748 graph
->label
[n
] = equivalence_class
++;
1752 unsigned int size
= 0;
1753 unsigned int firstlabel
= ~0;
1755 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
1757 unsigned int j
= si
->node_mapping
[i
];
1759 if (j
== n
|| graph
->label
[j
] == 0)
1762 if (firstlabel
== (unsigned int)~0)
1764 firstlabel
= graph
->label
[j
];
1767 else if (graph
->label
[j
] != firstlabel
)
1772 graph
->label
[n
] = 0;
1774 graph
->label
[n
] = firstlabel
;
1776 graph
->label
[n
] = equivalence_class
++;
1780 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1783 /* Perform offline variable substitution, discovering equivalence
1784 classes, and eliminating non-pointer variables. */
1786 static struct scc_info
*
1787 perform_var_substitution (constraint_graph_t graph
)
1790 unsigned int size
= graph
->size
;
1791 struct scc_info
*si
= init_scc_info (size
);
1793 bitmap_obstack_initialize (&iteration_obstack
);
1794 equivalence_class
= 0;
1796 /* We only need to visit the non-address nodes for labeling
1797 purposes, as the address nodes will never have any predecessors,
1798 because &x never appears on the LHS of a constraint. */
1799 for (i
= 0; i
< LAST_REF_NODE
; i
++)
1800 if (!TEST_BIT (si
->visited
, si
->node_mapping
[i
]))
1801 label_visit (graph
, si
, si
->node_mapping
[i
]);
1803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1804 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
1806 bool direct_node
= TEST_BIT (graph
->direct_nodes
, i
);
1808 "Equivalence class for %s node id %d:%s is %d\n",
1809 direct_node
? "Direct node" : "Indirect node", i
,
1810 get_varinfo (i
)->name
,
1811 graph
->label
[si
->node_mapping
[i
]]);
1814 /* Quickly eliminate our non-pointer variables. */
1816 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
1818 unsigned int node
= si
->node_mapping
[i
];
1820 if (graph
->label
[node
] == 0 && TEST_BIT (graph
->direct_nodes
, node
))
1822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1824 "%s is a non-pointer variable, eliminating edges.\n",
1825 get_varinfo (node
)->name
);
1826 stats
.nonpointer_vars
++;
1827 clear_edges_for_node (graph
, node
);
1833 /* Free information that was only necessary for variable
1837 free_var_substitution_info (struct scc_info
*si
)
1840 free (graph
->label
);
1841 free (graph
->eq_rep
);
1842 sbitmap_free (graph
->direct_nodes
);
1843 bitmap_obstack_release (&iteration_obstack
);
1846 /* Return an existing node that is equivalent to NODE, which has
1847 equivalence class LABEL, if one exists. Return NODE otherwise. */
1850 find_equivalent_node (constraint_graph_t graph
,
1851 unsigned int node
, unsigned int label
)
1853 /* If the address version of this variable is unused, we can
1854 substitute it for anything else with the same label.
1855 Otherwise, we know the pointers are equivalent, but not the
1858 if (graph
->label
[FIRST_ADDR_NODE
+ node
] == 0)
1860 gcc_assert (label
< graph
->size
);
1862 if (graph
->eq_rep
[label
] != -1)
1864 /* Unify the two variables since we know they are equivalent. */
1865 if (unite (graph
->eq_rep
[label
], node
))
1866 unify_nodes (graph
, graph
->eq_rep
[label
], node
, false);
1867 return graph
->eq_rep
[label
];
1871 graph
->eq_rep
[label
] = node
;
1877 /* Move complex constraints to the appropriate nodes, and collapse
1878 variables we've discovered are equivalent during variable
1879 substitution. SI is the SCC_INFO that is the result of
1880 perform_variable_substitution. */
1883 move_complex_constraints (constraint_graph_t graph
,
1884 struct scc_info
*si
)
1890 for (j
= 0; j
< graph
->size
; j
++)
1891 gcc_assert (find (j
) == j
);
1893 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1895 struct constraint_expr lhs
= c
->lhs
;
1896 struct constraint_expr rhs
= c
->rhs
;
1897 unsigned int lhsvar
= find (get_varinfo_fc (lhs
.var
)->id
);
1898 unsigned int rhsvar
= find (get_varinfo_fc (rhs
.var
)->id
);
1899 unsigned int lhsnode
, rhsnode
;
1900 unsigned int lhslabel
, rhslabel
;
1902 lhsnode
= si
->node_mapping
[lhsvar
];
1903 rhsnode
= si
->node_mapping
[rhsvar
];
1904 lhslabel
= graph
->label
[lhsnode
];
1905 rhslabel
= graph
->label
[rhsnode
];
1907 /* See if it is really a non-pointer variable, and if so, ignore
1911 if (!TEST_BIT (graph
->direct_nodes
, lhsnode
))
1912 lhslabel
= graph
->label
[lhsnode
] = equivalence_class
++;
1915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1918 fprintf (dump_file
, "%s is a non-pointer variable,"
1919 "ignoring constraint:",
1920 get_varinfo (lhs
.var
)->name
);
1921 dump_constraint (dump_file
, c
);
1923 VEC_replace (constraint_t
, constraints
, i
, NULL
);
1930 if (!TEST_BIT (graph
->direct_nodes
, rhsnode
))
1931 rhslabel
= graph
->label
[rhsnode
] = equivalence_class
++;
1934 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1937 fprintf (dump_file
, "%s is a non-pointer variable,"
1938 "ignoring constraint:",
1939 get_varinfo (rhs
.var
)->name
);
1940 dump_constraint (dump_file
, c
);
1942 VEC_replace (constraint_t
, constraints
, i
, NULL
);
1947 lhsvar
= find_equivalent_node (graph
, lhsvar
, lhslabel
);
1948 rhsvar
= find_equivalent_node (graph
, rhsvar
, rhslabel
);
1949 c
->lhs
.var
= lhsvar
;
1950 c
->rhs
.var
= rhsvar
;
1952 if (lhs
.type
== DEREF
)
1954 if (rhs
.type
== ADDRESSOF
|| rhsvar
> anything_id
)
1955 insert_into_complex (graph
, lhsvar
, c
);
1957 else if (rhs
.type
== DEREF
)
1959 if (!(get_varinfo (lhsvar
)->is_special_var
))
1960 insert_into_complex (graph
, rhsvar
, c
);
1962 else if (rhs
.type
!= ADDRESSOF
&& lhsvar
> anything_id
1963 && (lhs
.offset
!= 0 || rhs
.offset
!= 0))
1965 insert_into_complex (graph
, rhsvar
, c
);
1971 /* Eliminate indirect cycles involving NODE. Return true if NODE was
1972 part of an SCC, false otherwise. */
1975 eliminate_indirect_cycles (unsigned int node
)
1977 if (graph
->indirect_cycles
[node
] != -1
1978 && !bitmap_empty_p (get_varinfo (node
)->solution
))
1981 VEC(unsigned,heap
) *queue
= NULL
;
1983 unsigned int to
= find (graph
->indirect_cycles
[node
]);
1986 /* We can't touch the solution set and call unify_nodes
1987 at the same time, because unify_nodes is going to do
1988 bitmap unions into it. */
1990 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node
)->solution
, 0, i
, bi
)
1992 if (find (i
) == i
&& i
!= to
)
1995 VEC_safe_push (unsigned, heap
, queue
, i
);
2000 VEC_iterate (unsigned, queue
, queuepos
, i
);
2003 unify_nodes (graph
, to
, i
, true);
2005 VEC_free (unsigned, heap
, queue
);
2011 /* Solve the constraint graph GRAPH using our worklist solver.
2012 This is based on the PW* family of solvers from the "Efficient Field
2013 Sensitive Pointer Analysis for C" paper.
2014 It works by iterating over all the graph nodes, processing the complex
2015 constraints and propagating the copy constraints, until everything stops
2016 changed. This corresponds to steps 6-8 in the solving list given above. */
2019 solve_graph (constraint_graph_t graph
)
2021 unsigned int size
= VEC_length (varinfo_t
, varmap
);
2026 changed
= sbitmap_alloc (size
);
2027 sbitmap_zero (changed
);
2029 /* Mark all initial non-collapsed nodes as changed. */
2030 for (i
= 0; i
< size
; i
++)
2032 varinfo_t ivi
= get_varinfo (i
);
2033 if (find (i
) == i
&& !bitmap_empty_p (ivi
->solution
)
2034 && ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
2035 || VEC_length (constraint_t
, graph
->complex[i
]) > 0))
2037 SET_BIT (changed
, i
);
2042 /* Allocate a bitmap to be used to store the changed bits. */
2043 pts
= BITMAP_ALLOC (&pta_obstack
);
2045 while (changed_count
> 0)
2048 struct topo_info
*ti
= init_topo_info ();
2051 bitmap_obstack_initialize (&iteration_obstack
);
2053 compute_topo_order (graph
, ti
);
2055 while (VEC_length (unsigned, ti
->topo_order
) != 0)
2058 i
= VEC_pop (unsigned, ti
->topo_order
);
2060 /* If this variable is not a representative, skip it. */
2064 /* In certain indirect cycle cases, we may merge this
2065 variable to another. */
2066 if (eliminate_indirect_cycles (i
) && find (i
) != i
)
2069 /* If the node has changed, we need to process the
2070 complex constraints and outgoing edges again. */
2071 if (TEST_BIT (changed
, i
))
2076 VEC(constraint_t
,heap
) *complex = graph
->complex[i
];
2077 bool solution_empty
;
2079 RESET_BIT (changed
, i
);
2082 /* Compute the changed set of solution bits. */
2083 bitmap_and_compl (pts
, get_varinfo (i
)->solution
,
2084 get_varinfo (i
)->oldsolution
);
2086 if (bitmap_empty_p (pts
))
2089 bitmap_ior_into (get_varinfo (i
)->oldsolution
, pts
);
2091 solution
= get_varinfo (i
)->solution
;
2092 solution_empty
= bitmap_empty_p (solution
);
2094 /* Process the complex constraints */
2095 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
2097 /* The only complex constraint that can change our
2098 solution to non-empty, given an empty solution,
2099 is a constraint where the lhs side is receiving
2100 some set from elsewhere. */
2101 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2102 do_complex_constraint (graph
, c
, pts
);
2105 solution_empty
= bitmap_empty_p (solution
);
2107 if (!solution_empty
)
2111 /* Propagate solution to all successors. */
2112 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
2118 unsigned int to
= find (j
);
2119 tmp
= get_varinfo (to
)->solution
;
2122 /* Don't try to propagate to ourselves. */
2126 flag
= set_union_with_increment (tmp
, pts
, 0);
2130 get_varinfo (to
)->solution
= tmp
;
2131 if (!TEST_BIT (changed
, to
))
2133 SET_BIT (changed
, to
);
2141 free_topo_info (ti
);
2142 bitmap_obstack_release (&iteration_obstack
);
2146 sbitmap_free (changed
);
2147 bitmap_obstack_release (&oldpta_obstack
);
2150 /* Map from trees to variable infos. */
2151 static struct pointer_map_t
*vi_for_tree
;
2154 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2157 insert_vi_for_tree (tree t
, varinfo_t vi
)
2159 void **slot
= pointer_map_insert (vi_for_tree
, t
);
2161 gcc_assert (*slot
== NULL
);
2165 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2166 exist in the map, return NULL, otherwise, return the varinfo we found. */
2169 lookup_vi_for_tree (tree t
)
2171 void **slot
= pointer_map_contains (vi_for_tree
, t
);
2175 return (varinfo_t
) *slot
;
2178 /* Return a printable name for DECL */
2181 alias_get_name (tree decl
)
2183 const char *res
= get_name (decl
);
2185 int num_printed
= 0;
2194 if (TREE_CODE (decl
) == SSA_NAME
)
2196 num_printed
= asprintf (&temp
, "%s_%u",
2197 alias_get_name (SSA_NAME_VAR (decl
)),
2198 SSA_NAME_VERSION (decl
));
2200 else if (DECL_P (decl
))
2202 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2204 if (num_printed
> 0)
2206 res
= ggc_strdup (temp
);
2212 /* Find the variable id for tree T in the map.
2213 If T doesn't exist in the map, create an entry for it and return it. */
2216 get_vi_for_tree (tree t
)
2218 void **slot
= pointer_map_contains (vi_for_tree
, t
);
2220 return get_varinfo (create_variable_info_for (t
, alias_get_name (t
)));
2222 return (varinfo_t
) *slot
;
2225 /* Get a constraint expression from an SSA_VAR_P node. */
2227 static struct constraint_expr
2228 get_constraint_exp_from_ssa_var (tree t
)
2230 struct constraint_expr cexpr
;
2232 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
2234 /* For parameters, get at the points-to set for the actual parm
2236 if (TREE_CODE (t
) == SSA_NAME
2237 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2238 && SSA_NAME_IS_DEFAULT_DEF (t
))
2239 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
2241 cexpr
.type
= SCALAR
;
2243 cexpr
.var
= get_vi_for_tree (t
)->id
;
2244 /* If we determine the result is "anything", and we know this is readonly,
2245 say it points to readonly memory instead. */
2246 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
2248 cexpr
.type
= ADDRESSOF
;
2249 cexpr
.var
= readonly_id
;
2256 /* Process a completed constraint T, and add it to the constraint
2260 process_constraint (constraint_t t
)
2262 struct constraint_expr rhs
= t
->rhs
;
2263 struct constraint_expr lhs
= t
->lhs
;
2265 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
2266 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
2268 if (lhs
.type
== DEREF
)
2269 get_varinfo (lhs
.var
)->directly_dereferenced
= true;
2270 if (rhs
.type
== DEREF
)
2271 get_varinfo (rhs
.var
)->directly_dereferenced
= true;
2273 if (!use_field_sensitive
)
2279 /* ANYTHING == ANYTHING is pointless. */
2280 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
2283 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2284 else if (lhs
.var
== anything_id
&& lhs
.type
== ADDRESSOF
)
2289 process_constraint (t
);
2291 /* This can happen in our IR with things like n->a = *p */
2292 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
2294 /* Split into tmp = *rhs, *lhs = tmp */
2295 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
2296 tree pointertype
= TREE_TYPE (rhsdecl
);
2297 tree pointedtotype
= TREE_TYPE (pointertype
);
2298 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
2299 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2301 /* If this is an aggregate of known size, we should have passed
2302 this off to do_structure_copy, and it should have broken it
2304 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
2305 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
2307 process_constraint (new_constraint (tmplhs
, rhs
));
2308 process_constraint (new_constraint (lhs
, tmplhs
));
2312 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
2313 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2317 /* Return true if T is a variable of a type that could contain
2321 could_have_pointers (tree t
)
2323 tree type
= TREE_TYPE (t
);
2325 if (POINTER_TYPE_P (type
)
2326 || AGGREGATE_TYPE_P (type
)
2327 || TREE_CODE (type
) == COMPLEX_TYPE
)
2333 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2336 static unsigned HOST_WIDE_INT
2337 bitpos_of_field (const tree fdecl
)
2340 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
2341 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
2344 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
2345 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
2349 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2350 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2353 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
2354 const unsigned HOST_WIDE_INT fieldsize
,
2355 const unsigned HOST_WIDE_INT accesspos
,
2356 const unsigned HOST_WIDE_INT accesssize
)
2358 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
2360 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
2362 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
2368 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2371 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
)
2374 HOST_WIDE_INT bitsize
= -1;
2375 HOST_WIDE_INT bitmaxsize
= -1;
2376 HOST_WIDE_INT bitpos
;
2378 struct constraint_expr
*result
;
2379 unsigned int beforelength
= VEC_length (ce_s
, *results
);
2381 /* Some people like to do cute things like take the address of
2384 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
2385 forzero
= TREE_OPERAND (forzero
, 0);
2387 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
2389 struct constraint_expr temp
;
2392 temp
.var
= integer_id
;
2394 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2398 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
2400 /* String constants are readonly, so there is nothing to really do
2402 if (TREE_CODE (t
) == STRING_CST
)
2405 get_constraint_for (t
, results
);
2406 result
= VEC_last (ce_s
, *results
);
2407 result
->offset
= bitpos
;
2409 gcc_assert (beforelength
+ 1 == VEC_length (ce_s
, *results
));
2411 /* This can also happen due to weird offsetof type macros. */
2412 if (TREE_CODE (t
) != ADDR_EXPR
&& result
->type
== ADDRESSOF
)
2413 result
->type
= SCALAR
;
2415 if (result
->type
== SCALAR
)
2417 /* In languages like C, you can access one past the end of an
2418 array. You aren't allowed to dereference it, so we can
2419 ignore this constraint. When we handle pointer subtraction,
2420 we may have to do something cute here. */
2422 if (result
->offset
< get_varinfo (result
->var
)->fullsize
2425 /* It's also not true that the constraint will actually start at the
2426 right offset, it may start in some padding. We only care about
2427 setting the constraint to the first actual field it touches, so
2430 for (curr
= get_varinfo (result
->var
); curr
; curr
= curr
->next
)
2432 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2433 result
->offset
, bitmaxsize
))
2435 result
->var
= curr
->id
;
2439 /* assert that we found *some* field there. The user couldn't be
2440 accessing *only* padding. */
2441 /* Still the user could access one past the end of an array
2442 embedded in a struct resulting in accessing *only* padding. */
2443 gcc_assert (curr
|| ref_contains_array_ref (orig_t
));
2445 else if (bitmaxsize
== 0)
2447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2448 fprintf (dump_file
, "Access to zero-sized part of variable,"
2452 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2453 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2460 /* Dereference the constraint expression CONS, and return the result.
2461 DEREF (ADDRESSOF) = SCALAR
2462 DEREF (SCALAR) = DEREF
2463 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2464 This is needed so that we can handle dereferencing DEREF constraints. */
2467 do_deref (VEC (ce_s
, heap
) **constraints
)
2469 struct constraint_expr
*c
;
2472 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
2474 if (c
->type
== SCALAR
)
2476 else if (c
->type
== ADDRESSOF
)
2478 else if (c
->type
== DEREF
)
2480 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "dereftmp");
2481 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2482 process_constraint (new_constraint (tmplhs
, *c
));
2483 c
->var
= tmplhs
.var
;
2490 /* Given a tree T, return the constraint expression for it. */
2493 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
2495 struct constraint_expr temp
;
2497 /* x = integer is all glommed to a single variable, which doesn't
2498 point to anything by itself. That is, of course, unless it is an
2499 integer constant being treated as a pointer, in which case, we
2500 will return that this is really the addressof anything. This
2501 happens below, since it will fall into the default case. The only
2502 case we know something about an integer treated like a pointer is
2503 when it is the NULL pointer, and then we just say it points to
2505 if (TREE_CODE (t
) == INTEGER_CST
2506 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2508 temp
.var
= integer_id
;
2511 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2514 else if (TREE_CODE (t
) == INTEGER_CST
2515 && integer_zerop (t
))
2517 temp
.var
= nothing_id
;
2518 temp
.type
= ADDRESSOF
;
2520 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2524 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2526 case tcc_expression
:
2529 switch (TREE_CODE (t
))
2533 struct constraint_expr
*c
;
2535 tree exp
= TREE_OPERAND (t
, 0);
2536 tree pttype
= TREE_TYPE (TREE_TYPE (t
));
2538 get_constraint_for (exp
, results
);
2540 /* Make sure we capture constraints to all elements
2542 if ((handled_component_p (exp
)
2543 && ref_contains_array_ref (exp
))
2544 || TREE_CODE (TREE_TYPE (exp
)) == ARRAY_TYPE
)
2546 struct constraint_expr
*origrhs
;
2548 struct constraint_expr tmp
;
2550 if (VEC_length (ce_s
, *results
) == 0)
2553 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2554 origrhs
= VEC_last (ce_s
, *results
);
2556 VEC_pop (ce_s
, *results
);
2557 origvar
= get_varinfo (origrhs
->var
);
2558 for (; origvar
; origvar
= origvar
->next
)
2560 tmp
.var
= origvar
->id
;
2561 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2564 else if (VEC_length (ce_s
, *results
) == 1
2565 && (AGGREGATE_TYPE_P (pttype
)
2566 || TREE_CODE (pttype
) == COMPLEX_TYPE
))
2568 struct constraint_expr
*origrhs
;
2570 struct constraint_expr tmp
;
2572 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2573 origrhs
= VEC_last (ce_s
, *results
);
2575 VEC_pop (ce_s
, *results
);
2576 origvar
= get_varinfo (origrhs
->var
);
2577 for (; origvar
; origvar
= origvar
->next
)
2579 tmp
.var
= origvar
->id
;
2580 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2584 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
2586 if (c
->type
== DEREF
)
2589 c
->type
= ADDRESSOF
;
2595 /* XXX: In interprocedural mode, if we didn't have the
2596 body, we would need to do *each pointer argument =
2598 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2601 tree heapvar
= heapvar_lookup (t
);
2603 if (heapvar
== NULL
)
2605 heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2606 DECL_EXTERNAL (heapvar
) = 1;
2607 get_var_ann (heapvar
)->is_heapvar
= 1;
2608 if (gimple_referenced_vars (cfun
))
2609 add_referenced_var (heapvar
);
2610 heapvar_insert (t
, heapvar
);
2613 temp
.var
= create_variable_info_for (heapvar
,
2614 alias_get_name (heapvar
));
2616 vi
= get_varinfo (temp
.var
);
2617 vi
->is_artificial_var
= 1;
2618 vi
->is_heap_var
= 1;
2619 temp
.type
= ADDRESSOF
;
2621 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2626 temp
.var
= anything_id
;
2629 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2635 temp
.type
= ADDRESSOF
;
2636 temp
.var
= anything_id
;
2638 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2645 switch (TREE_CODE (t
))
2649 get_constraint_for (TREE_OPERAND (t
, 0), results
);
2654 case ARRAY_RANGE_REF
:
2656 get_constraint_for_component_ref (t
, results
);
2660 temp
.type
= ADDRESSOF
;
2661 temp
.var
= anything_id
;
2663 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2670 switch (TREE_CODE (t
))
2674 case NON_LVALUE_EXPR
:
2676 tree op
= TREE_OPERAND (t
, 0);
2678 /* Cast from non-pointer to pointers are bad news for us.
2679 Anything else, we see through */
2680 if (!(POINTER_TYPE_P (TREE_TYPE (t
))
2681 && ! POINTER_TYPE_P (TREE_TYPE (op
))))
2683 get_constraint_for (op
, results
);
2691 temp
.type
= ADDRESSOF
;
2692 temp
.var
= anything_id
;
2694 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2699 case tcc_exceptional
:
2701 switch (TREE_CODE (t
))
2705 get_constraint_for (PHI_RESULT (t
), results
);
2711 struct constraint_expr temp
;
2712 temp
= get_constraint_exp_from_ssa_var (t
);
2713 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2719 temp
.type
= ADDRESSOF
;
2720 temp
.var
= anything_id
;
2722 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2727 case tcc_declaration
:
2729 struct constraint_expr temp
;
2730 temp
= get_constraint_exp_from_ssa_var (t
);
2731 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2736 temp
.type
= ADDRESSOF
;
2737 temp
.var
= anything_id
;
2739 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2746 /* Handle the structure copy case where we have a simple structure copy
2747 between LHS and RHS that is of SIZE (in bits)
2749 For each field of the lhs variable (lhsfield)
2750 For each field of the rhs variable at lhsfield.offset (rhsfield)
2751 add the constraint lhsfield = rhsfield
2753 If we fail due to some kind of type unsafety or other thing we
2754 can't handle, return false. We expect the caller to collapse the
2755 variable in that case. */
2758 do_simple_structure_copy (const struct constraint_expr lhs
,
2759 const struct constraint_expr rhs
,
2760 const unsigned HOST_WIDE_INT size
)
2762 varinfo_t p
= get_varinfo (lhs
.var
);
2763 unsigned HOST_WIDE_INT pstart
, last
;
2765 last
= p
->offset
+ size
;
2766 for (; p
&& p
->offset
< last
; p
= p
->next
)
2769 struct constraint_expr templhs
= lhs
;
2770 struct constraint_expr temprhs
= rhs
;
2771 unsigned HOST_WIDE_INT fieldoffset
;
2773 templhs
.var
= p
->id
;
2774 q
= get_varinfo (temprhs
.var
);
2775 fieldoffset
= p
->offset
- pstart
;
2776 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2779 temprhs
.var
= q
->id
;
2780 process_constraint (new_constraint (templhs
, temprhs
));
2786 /* Handle the structure copy case where we have a structure copy between a
2787 aggregate on the LHS and a dereference of a pointer on the RHS
2788 that is of SIZE (in bits)
2790 For each field of the lhs variable (lhsfield)
2791 rhs.offset = lhsfield->offset
2792 add the constraint lhsfield = rhs
2796 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2797 const struct constraint_expr rhs
,
2798 const unsigned HOST_WIDE_INT size
)
2800 varinfo_t p
= get_varinfo (lhs
.var
);
2801 unsigned HOST_WIDE_INT pstart
,last
;
2803 last
= p
->offset
+ size
;
2805 for (; p
&& p
->offset
< last
; p
= p
->next
)
2808 struct constraint_expr templhs
= lhs
;
2809 struct constraint_expr temprhs
= rhs
;
2810 unsigned HOST_WIDE_INT fieldoffset
;
2813 if (templhs
.type
== SCALAR
)
2814 templhs
.var
= p
->id
;
2816 templhs
.offset
= p
->offset
;
2818 q
= get_varinfo (temprhs
.var
);
2819 fieldoffset
= p
->offset
- pstart
;
2820 temprhs
.offset
+= fieldoffset
;
2821 process_constraint (new_constraint (templhs
, temprhs
));
2825 /* Handle the structure copy case where we have a structure copy
2826 between an aggregate on the RHS and a dereference of a pointer on
2827 the LHS that is of SIZE (in bits)
2829 For each field of the rhs variable (rhsfield)
2830 lhs.offset = rhsfield->offset
2831 add the constraint lhs = rhsfield
2835 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2836 const struct constraint_expr rhs
,
2837 const unsigned HOST_WIDE_INT size
)
2839 varinfo_t p
= get_varinfo (rhs
.var
);
2840 unsigned HOST_WIDE_INT pstart
,last
;
2842 last
= p
->offset
+ size
;
2844 for (; p
&& p
->offset
< last
; p
= p
->next
)
2847 struct constraint_expr templhs
= lhs
;
2848 struct constraint_expr temprhs
= rhs
;
2849 unsigned HOST_WIDE_INT fieldoffset
;
2852 if (temprhs
.type
== SCALAR
)
2853 temprhs
.var
= p
->id
;
2855 temprhs
.offset
= p
->offset
;
2857 q
= get_varinfo (templhs
.var
);
2858 fieldoffset
= p
->offset
- pstart
;
2859 templhs
.offset
+= fieldoffset
;
2860 process_constraint (new_constraint (templhs
, temprhs
));
2864 /* Sometimes, frontends like to give us bad type information. This
2865 function will collapse all the fields from VAR to the end of VAR,
2866 into VAR, so that we treat those fields as a single variable.
2867 We return the variable they were collapsed into. */
2870 collapse_rest_of_var (unsigned int var
)
2872 varinfo_t currvar
= get_varinfo (var
);
2875 for (field
= currvar
->next
; field
; field
= field
->next
)
2878 fprintf (dump_file
, "Type safety: Collapsing var %s into %s\n",
2879 field
->name
, currvar
->name
);
2881 gcc_assert (!field
->collapsed_to
);
2882 field
->collapsed_to
= currvar
;
2885 currvar
->next
= NULL
;
2886 currvar
->size
= currvar
->fullsize
- currvar
->offset
;
2891 /* Handle aggregate copies by expanding into copies of the respective
2892 fields of the structures. */
2895 do_structure_copy (tree lhsop
, tree rhsop
)
2897 struct constraint_expr lhs
, rhs
, tmp
;
2898 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
2900 unsigned HOST_WIDE_INT lhssize
;
2901 unsigned HOST_WIDE_INT rhssize
;
2903 get_constraint_for (lhsop
, &lhsc
);
2904 get_constraint_for (rhsop
, &rhsc
);
2905 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
2906 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
2907 lhs
= *(VEC_last (ce_s
, lhsc
));
2908 rhs
= *(VEC_last (ce_s
, rhsc
));
2910 VEC_free (ce_s
, heap
, lhsc
);
2911 VEC_free (ce_s
, heap
, rhsc
);
2913 /* If we have special var = x, swap it around. */
2914 if (lhs
.var
<= integer_id
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2921 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2922 possible it's something we could handle. However, most cases falling
2923 into this are dealing with transparent unions, which are slightly
2925 if (rhs
.type
== ADDRESSOF
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2927 rhs
.type
= ADDRESSOF
;
2928 rhs
.var
= anything_id
;
2931 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2932 that special var. */
2933 if (rhs
.var
<= integer_id
)
2935 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2937 struct constraint_expr templhs
= lhs
;
2938 struct constraint_expr temprhs
= rhs
;
2940 if (templhs
.type
== SCALAR
)
2941 templhs
.var
= p
->id
;
2943 templhs
.offset
+= p
->offset
;
2944 process_constraint (new_constraint (templhs
, temprhs
));
2949 tree rhstype
= TREE_TYPE (rhsop
);
2950 tree lhstype
= TREE_TYPE (lhsop
);
2954 lhstypesize
= DECL_P (lhsop
) ? DECL_SIZE (lhsop
) : TYPE_SIZE (lhstype
);
2955 rhstypesize
= DECL_P (rhsop
) ? DECL_SIZE (rhsop
) : TYPE_SIZE (rhstype
);
2957 /* If we have a variably sized types on the rhs or lhs, and a deref
2958 constraint, add the constraint, lhsconstraint = &ANYTHING.
2959 This is conservatively correct because either the lhs is an unknown
2960 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2961 constraint, and every variable it can point to must be unknown sized
2962 anyway, so we don't need to worry about fields at all. */
2963 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
2964 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
2966 rhs
.var
= anything_id
;
2967 rhs
.type
= ADDRESSOF
;
2969 process_constraint (new_constraint (lhs
, rhs
));
2973 /* The size only really matters insofar as we don't set more or less of
2974 the variable. If we hit an unknown size var, the size should be the
2975 whole darn thing. */
2976 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
2979 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
2981 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
2984 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
2987 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
2989 if (!do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
)))
2991 lhs
.var
= collapse_rest_of_var (lhs
.var
);
2992 rhs
.var
= collapse_rest_of_var (rhs
.var
);
2997 process_constraint (new_constraint (lhs
, rhs
));
3000 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
3001 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
3002 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
3003 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
3006 tree pointedtotype
= lhstype
;
3009 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
3010 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
3011 do_structure_copy (tmpvar
, rhsop
);
3012 do_structure_copy (lhsop
, tmpvar
);
3018 /* Update related alias information kept in AI. This is used when
3019 building name tags, alias sets and deciding grouping heuristics.
3020 STMT is the statement to process. This function also updates
3021 ADDRESSABLE_VARS. */
3024 update_alias_info (tree stmt
, struct alias_info
*ai
)
3027 use_operand_p use_p
;
3029 bool stmt_dereferences_ptr_p
;
3030 enum escape_type stmt_escape_type
= is_escape_site (stmt
);
3031 struct mem_ref_stats_d
*mem_ref_stats
= gimple_mem_ref_stats (cfun
);
3033 stmt_dereferences_ptr_p
= false;
3035 if (stmt_escape_type
== ESCAPE_TO_CALL
3036 || stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
3038 mem_ref_stats
->num_call_sites
++;
3039 if (stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
3040 mem_ref_stats
->num_pure_const_call_sites
++;
3042 else if (stmt_escape_type
== ESCAPE_TO_ASM
)
3043 mem_ref_stats
->num_asm_sites
++;
3045 /* Mark all the variables whose address are taken by the statement. */
3046 addr_taken
= addresses_taken (stmt
);
3049 bitmap_ior_into (gimple_addressable_vars (cfun
), addr_taken
);
3051 /* If STMT is an escape point, all the addresses taken by it are
3053 if (stmt_escape_type
!= NO_ESCAPE
)
3058 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
3060 tree rvar
= referenced_var (i
);
3061 if (!unmodifiable_var_p (rvar
))
3062 mark_call_clobbered (rvar
, stmt_escape_type
);
3067 /* Process each operand use. For pointers, determine whether they
3068 are dereferenced by the statement, or whether their value
3070 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
3074 struct ptr_info_def
*pi
;
3075 unsigned num_uses
, num_loads
, num_stores
;
3077 op
= USE_FROM_PTR (use_p
);
3079 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3080 to the set of addressable variables. */
3081 if (TREE_CODE (op
) == ADDR_EXPR
)
3083 bitmap addressable_vars
= gimple_addressable_vars (cfun
);
3085 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
);
3086 gcc_assert (addressable_vars
);
3088 /* PHI nodes don't have annotations for pinning the set
3089 of addresses taken, so we collect them here.
3091 FIXME, should we allow PHI nodes to have annotations
3092 so that they can be treated like regular statements?
3093 Currently, they are treated as second-class
3095 add_to_addressable_set (TREE_OPERAND (op
, 0), &addressable_vars
);
3099 /* Ignore constants (they may occur in PHI node arguments). */
3100 if (TREE_CODE (op
) != SSA_NAME
)
3103 var
= SSA_NAME_VAR (op
);
3104 v_ann
= var_ann (var
);
3106 /* The base variable of an SSA name must be a GIMPLE register, and thus
3107 it cannot be aliased. */
3108 gcc_assert (!may_be_aliased (var
));
3110 /* We are only interested in pointers. */
3111 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
3114 pi
= get_ptr_info (op
);
3116 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3117 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
)))
3119 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
));
3120 VEC_safe_push (tree
, heap
, ai
->processed_ptrs
, op
);
3123 /* If STMT is a PHI node, then it will not have pointer
3124 dereferences and it will not be an escape point. */
3125 if (TREE_CODE (stmt
) == PHI_NODE
)
3128 /* Determine whether OP is a dereferenced pointer, and if STMT
3129 is an escape point, whether OP escapes. */
3130 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_loads
, &num_stores
);
3132 /* Handle a corner case involving address expressions of the
3133 form '&PTR->FLD'. The problem with these expressions is that
3134 they do not represent a dereference of PTR. However, if some
3135 other transformation propagates them into an INDIRECT_REF
3136 expression, we end up with '*(&PTR->FLD)' which is folded
3139 So, if the original code had no other dereferences of PTR,
3140 the aliaser will not create memory tags for it, and when
3141 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3142 memory operations will receive no VDEF/VUSE operands.
3144 One solution would be to have count_uses_and_derefs consider
3145 &PTR->FLD a dereference of PTR. But that is wrong, since it
3146 is not really a dereference but an offset calculation.
3148 What we do here is to recognize these special ADDR_EXPR
3149 nodes. Since these expressions are never GIMPLE values (they
3150 are not GIMPLE invariants), they can only appear on the RHS
3151 of an assignment and their base address is always an
3152 INDIRECT_REF expression. */
3153 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
3154 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == ADDR_EXPR
3155 && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt
, 1)))
3157 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3158 this represents a potential dereference of PTR. */
3159 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3160 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
3161 if (TREE_CODE (base
) == INDIRECT_REF
3162 && TREE_OPERAND (base
, 0) == op
)
3166 if (num_loads
+ num_stores
> 0)
3168 /* Mark OP as dereferenced. In a subsequent pass,
3169 dereferenced pointers that point to a set of
3170 variables will be assigned a name tag to alias
3171 all the variables OP points to. */
3172 pi
->is_dereferenced
= 1;
3174 /* If this is a store operation, mark OP as being
3175 dereferenced to store, otherwise mark it as being
3176 dereferenced to load. */
3178 pointer_set_insert (ai
->dereferenced_ptrs_store
, var
);
3180 pointer_set_insert (ai
->dereferenced_ptrs_load
, var
);
3182 /* Update the frequency estimate for all the dereferences of
3184 update_mem_sym_stats_from_stmt (op
, stmt
, num_loads
, num_stores
);
3186 /* Indicate that STMT contains pointer dereferences. */
3187 stmt_dereferences_ptr_p
= true;
3190 if (stmt_escape_type
!= NO_ESCAPE
&& num_loads
+ num_stores
< num_uses
)
3192 /* If STMT is an escape point and STMT contains at
3193 least one direct use of OP, then the value of OP
3194 escapes and so the pointed-to variables need to
3195 be marked call-clobbered. */
3196 pi
->value_escapes_p
= 1;
3197 pi
->escape_mask
|= stmt_escape_type
;
3199 /* If the statement makes a function call, assume
3200 that pointer OP will be dereferenced in a store
3201 operation inside the called function. */
3202 if (get_call_expr_in (stmt
)
3203 || stmt_escape_type
== ESCAPE_STORED_IN_GLOBAL
)
3205 pointer_set_insert (ai
->dereferenced_ptrs_store
, var
);
3206 pi
->is_dereferenced
= 1;
3211 if (TREE_CODE (stmt
) == PHI_NODE
)
3214 /* Mark stored variables in STMT as being written to and update the
3215 memory reference stats for all memory symbols referenced by STMT. */
3216 if (stmt_references_memory_p (stmt
))
3221 mem_ref_stats
->num_mem_stmts
++;
3223 /* Notice that we only update memory reference stats for symbols
3224 loaded and stored by the statement if the statement does not
3225 contain pointer dereferences and it is not a call/asm site.
3226 This is to avoid double accounting problems when creating
3227 memory partitions. After computing points-to information,
3228 pointer dereference statistics are used to update the
3229 reference stats of the pointed-to variables, so here we
3230 should only update direct references to symbols.
3232 Indirect references are not updated here for two reasons: (1)
3233 The first time we compute alias information, the sets
3234 LOADED/STORED are empty for pointer dereferences, (2) After
3235 partitioning, LOADED/STORED may have references to
3236 partitions, not the original pointed-to variables. So, if we
3237 always counted LOADED/STORED here and during partitioning, we
3238 would count many symbols more than once.
3240 This does cause some imprecision when a statement has a
3241 combination of direct symbol references and pointer
3242 dereferences (e.g., MEMORY_VAR = *PTR) or if a call site has
3243 memory symbols in its argument list, but these cases do not
3244 occur so frequently as to constitute a serious problem. */
3245 if (STORED_SYMS (stmt
))
3246 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt
), 0, i
, bi
)
3248 tree sym
= referenced_var (i
);
3249 pointer_set_insert (ai
->written_vars
, sym
);
3250 if (!stmt_dereferences_ptr_p
3251 && stmt_escape_type
!= ESCAPE_TO_CALL
3252 && stmt_escape_type
!= ESCAPE_TO_PURE_CONST
3253 && stmt_escape_type
!= ESCAPE_TO_ASM
)
3254 update_mem_sym_stats_from_stmt (sym
, stmt
, 0, 1);
3257 if (!stmt_dereferences_ptr_p
3258 && LOADED_SYMS (stmt
)
3259 && stmt_escape_type
!= ESCAPE_TO_CALL
3260 && stmt_escape_type
!= ESCAPE_TO_PURE_CONST
3261 && stmt_escape_type
!= ESCAPE_TO_ASM
)
3262 EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt
), 0, i
, bi
)
3263 update_mem_sym_stats_from_stmt (referenced_var (i
), stmt
, 1, 0);
3268 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3269 Expressions of the type PTR + CST can be handled in two ways:
3271 1- If the constraint for PTR is ADDRESSOF for a non-structure
3272 variable, then we can use it directly because adding or
3273 subtracting a constant may not alter the original ADDRESSOF
3274 constraint (i.e., pointer arithmetic may not legally go outside
3275 an object's boundaries).
3277 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3278 then if CST is a compile-time constant that can be used as an
3279 offset, we can determine which sub-variable will be pointed-to
3282 Return true if the expression is handled. For any other kind of
3283 expression, return false so that each operand can be added as a
3284 separate constraint by the caller. */
3287 handle_ptr_arith (VEC (ce_s
, heap
) *lhsc
, tree expr
)
3290 struct constraint_expr
*c
, *c2
;
3293 VEC (ce_s
, heap
) *temp
= NULL
;
3294 unsigned HOST_WIDE_INT rhsoffset
= 0;
3296 if (TREE_CODE (expr
) != POINTER_PLUS_EXPR
)
3299 op0
= TREE_OPERAND (expr
, 0);
3300 op1
= TREE_OPERAND (expr
, 1);
3301 gcc_assert (POINTER_TYPE_P (TREE_TYPE (op0
)));
3303 get_constraint_for (op0
, &temp
);
3305 /* We can only handle positive offsets that do not overflow
3306 if we multiply it by BITS_PER_UNIT. */
3307 if (host_integerp (op1
, 1))
3309 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
3311 if (rhsoffset
/ BITS_PER_UNIT
!= TREE_INT_CST_LOW (op1
))
3315 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
3316 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
3318 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
3320 varinfo_t temp
= get_varinfo (c2
->var
);
3322 /* An access one after the end of an array is valid,
3323 so simply punt on accesses we cannot resolve. */
3324 temp
= first_vi_for_offset (temp
, rhsoffset
);
3331 c2
->offset
= rhsoffset
;
3332 process_constraint (new_constraint (*c
, *c2
));
3335 VEC_free (ce_s
, heap
, temp
);
3341 /* Walk statement T setting up aliasing constraints according to the
3342 references found in T. This function is the main part of the
3343 constraint builder. AI points to auxiliary alias information used
3344 when building alias sets and computing alias grouping heuristics. */
3347 find_func_aliases (tree origt
)
3350 VEC(ce_s
, heap
) *lhsc
= NULL
;
3351 VEC(ce_s
, heap
) *rhsc
= NULL
;
3352 struct constraint_expr
*c
;
3354 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
3355 t
= TREE_OPERAND (t
, 0);
3357 /* Now build constraints expressions. */
3358 if (TREE_CODE (t
) == PHI_NODE
)
3360 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))));
3362 /* Only care about pointers and structures containing
3364 if (could_have_pointers (PHI_RESULT (t
)))
3369 /* For a phi node, assign all the arguments to
3371 get_constraint_for (PHI_RESULT (t
), &lhsc
);
3372 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
3375 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
3377 STRIP_NOPS (strippedrhs
);
3378 rhstype
= TREE_TYPE (strippedrhs
);
3379 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
3381 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3383 struct constraint_expr
*c2
;
3384 while (VEC_length (ce_s
, rhsc
) > 0)
3386 c2
= VEC_last (ce_s
, rhsc
);
3387 process_constraint (new_constraint (*c
, *c2
));
3388 VEC_pop (ce_s
, rhsc
);
3394 /* In IPA mode, we need to generate constraints to pass call
3395 arguments through their calls. There are two cases, either a
3396 GIMPLE_MODIFY_STMT when we are returning a value, or just a plain
3397 CALL_EXPR when we are not. */
3398 else if (in_ipa_mode
3399 && ((TREE_CODE (t
) == GIMPLE_MODIFY_STMT
3400 && TREE_CODE (GIMPLE_STMT_OPERAND (t
, 1)) == CALL_EXPR
3401 && !(call_expr_flags (GIMPLE_STMT_OPERAND (t
, 1))
3402 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
3403 || (TREE_CODE (t
) == CALL_EXPR
3404 && !(call_expr_flags (t
)
3405 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
3410 call_expr_arg_iterator iter
;
3414 if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
3416 lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
3417 rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
3424 decl
= get_callee_fndecl (rhsop
);
3426 /* If we can directly resolve the function being called, do so.
3427 Otherwise, it must be some sort of indirect expression that
3428 we should still be able to handle. */
3431 fi
= get_vi_for_tree (decl
);
3435 decl
= CALL_EXPR_FN (rhsop
);
3436 fi
= get_vi_for_tree (decl
);
3439 /* Assign all the passed arguments to the appropriate incoming
3440 parameters of the function. */
3442 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, rhsop
)
3444 struct constraint_expr lhs
;
3445 struct constraint_expr
*rhsp
;
3447 get_constraint_for (arg
, &rhsc
);
3448 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3457 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3460 while (VEC_length (ce_s
, rhsc
) != 0)
3462 rhsp
= VEC_last (ce_s
, rhsc
);
3463 process_constraint (new_constraint (lhs
, *rhsp
));
3464 VEC_pop (ce_s
, rhsc
);
3469 /* If we are returning a value, assign it to the result. */
3472 struct constraint_expr rhs
;
3473 struct constraint_expr
*lhsp
;
3476 get_constraint_for (lhsop
, &lhsc
);
3477 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3486 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3489 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3490 process_constraint (new_constraint (*lhsp
, rhs
));
3493 /* Otherwise, just a regular assignment statement. */
3494 else if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
3496 tree lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
3497 tree rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
3500 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3501 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
)
3502 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop
))
3503 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
))
3505 do_structure_copy (lhsop
, rhsop
);
3509 /* Only care about operations with pointers, structures
3510 containing pointers, dereferences, and call expressions. */
3511 if (could_have_pointers (lhsop
)
3512 || TREE_CODE (rhsop
) == CALL_EXPR
)
3514 get_constraint_for (lhsop
, &lhsc
);
3515 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3517 /* RHS that consist of unary operations,
3518 exceptional types, or bare decls/constants, get
3519 handled directly by get_constraint_for. */
3521 case tcc_declaration
:
3523 case tcc_exceptional
:
3524 case tcc_expression
:
3530 get_constraint_for (rhsop
, &rhsc
);
3531 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3533 struct constraint_expr
*c2
;
3536 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3537 process_constraint (new_constraint (*c
, *c2
));
3545 /* For pointer arithmetic of the form
3546 PTR + CST, we can simply use PTR's
3547 constraint because pointer arithmetic is
3548 not allowed to go out of bounds. */
3549 if (handle_ptr_arith (lhsc
, rhsop
))
3554 /* Otherwise, walk each operand. Notice that we
3555 can't use the operand interface because we need
3556 to process expressions other than simple operands
3557 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3559 for (i
= 0; i
< TREE_OPERAND_LENGTH (rhsop
); i
++)
3561 tree op
= TREE_OPERAND (rhsop
, i
);
3564 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3565 get_constraint_for (op
, &rhsc
);
3566 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3568 struct constraint_expr
*c2
;
3569 while (VEC_length (ce_s
, rhsc
) > 0)
3571 c2
= VEC_last (ce_s
, rhsc
);
3572 process_constraint (new_constraint (*c
, *c2
));
3573 VEC_pop (ce_s
, rhsc
);
3581 else if (TREE_CODE (t
) == CHANGE_DYNAMIC_TYPE_EXPR
)
3585 get_constraint_for (CHANGE_DYNAMIC_TYPE_LOCATION (t
), &lhsc
);
3586 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); ++j
)
3587 get_varinfo (c
->var
)->no_tbaa_pruning
= true;
3590 /* After promoting variables and computing aliasing we will
3591 need to re-scan most statements. FIXME: Try to minimize the
3592 number of statements re-scanned. It's not really necessary to
3593 re-scan *all* statements. */
3594 mark_stmt_modified (origt
);
3595 VEC_free (ce_s
, heap
, rhsc
);
3596 VEC_free (ce_s
, heap
, lhsc
);
3600 /* Find the first varinfo in the same variable as START that overlaps with
3602 Effectively, walk the chain of fields for the variable START to find the
3603 first field that overlaps with OFFSET.
3604 Return NULL if we can't find one. */
3607 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3609 varinfo_t curr
= start
;
3612 /* We may not find a variable in the field list with the actual
3613 offset when when we have glommed a structure to a variable.
3614 In that case, however, offset should still be within the size
3616 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3624 /* Insert the varinfo FIELD into the field list for BASE, at the front
3628 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3630 varinfo_t prev
= base
;
3631 varinfo_t curr
= base
->next
;
3637 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3641 insert_into_field_list_sorted (varinfo_t base
, varinfo_t field
)
3643 varinfo_t prev
= base
;
3644 varinfo_t curr
= base
->next
;
3655 if (field
->offset
<= curr
->offset
)
3660 field
->next
= prev
->next
;
3665 /* qsort comparison function for two fieldoff's PA and PB */
3668 fieldoff_compare (const void *pa
, const void *pb
)
3670 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3671 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3672 HOST_WIDE_INT foasize
, fobsize
;
3674 if (foa
->offset
!= fob
->offset
)
3675 return foa
->offset
- fob
->offset
;
3677 foasize
= TREE_INT_CST_LOW (foa
->size
);
3678 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3679 return foasize
- fobsize
;
3682 /* Sort a fieldstack according to the field offset and sizes. */
3684 sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3686 qsort (VEC_address (fieldoff_s
, fieldstack
),
3687 VEC_length (fieldoff_s
, fieldstack
),
3688 sizeof (fieldoff_s
),
3692 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3693 of TYPE onto fieldstack, recording their offsets along the way.
3694 OFFSET is used to keep track of the offset in this entire structure, rather
3695 than just the immediately containing structure. Returns the number
3697 HAS_UNION is set to true if we find a union type as a field of
3698 TYPE. ADDRESSABLE_TYPE is the type of the outermost object that could have
3699 its address taken. */
3702 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3703 HOST_WIDE_INT offset
, bool *has_union
,
3704 tree addressable_type
)
3709 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3711 fieldoff_s
*real_part
, *img_part
;
3712 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3713 real_part
->type
= TREE_TYPE (type
);
3714 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3715 real_part
->offset
= offset
;
3716 real_part
->decl
= NULL_TREE
;
3717 real_part
->alias_set
= -1;
3719 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3720 img_part
->type
= TREE_TYPE (type
);
3721 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3722 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3723 img_part
->decl
= NULL_TREE
;
3724 img_part
->alias_set
= -1;
3729 if (TREE_CODE (type
) == ARRAY_TYPE
)
3731 tree sz
= TYPE_SIZE (type
);
3732 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3737 || ! host_integerp (sz
, 1)
3738 || TREE_INT_CST_LOW (sz
) == 0
3740 || ! host_integerp (elsz
, 1)
3741 || TREE_INT_CST_LOW (elsz
) == 0)
3744 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3745 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3748 for (i
= 0; i
< nr
; ++i
)
3754 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3755 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3758 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3760 else if (!(pushed
= push_fields_onto_fieldstack
3761 (TREE_TYPE (type
), fieldstack
,
3762 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
,
3764 /* Empty structures may have actual size, like in C++. So
3765 see if we didn't push any subfields and the size is
3766 nonzero, push the field onto the stack */
3773 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3774 pair
->type
= TREE_TYPE (type
);
3776 pair
->decl
= NULL_TREE
;
3777 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3778 pair
->alias_set
= -1;
3788 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3789 if (TREE_CODE (field
) == FIELD_DECL
)
3795 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3796 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3799 if (!var_can_have_subvars (field
))
3801 else if (!(pushed
= push_fields_onto_fieldstack
3802 (TREE_TYPE (field
), fieldstack
,
3803 offset
+ bitpos_of_field (field
), has_union
,
3804 (DECL_NONADDRESSABLE_P (field
)
3806 : TREE_TYPE (field
))))
3807 && DECL_SIZE (field
)
3808 && !integer_zerop (DECL_SIZE (field
)))
3809 /* Empty structures may have actual size, like in C++. So
3810 see if we didn't push any subfields and the size is
3811 nonzero, push the field onto the stack */
3818 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3819 pair
->type
= TREE_TYPE (field
);
3820 pair
->size
= DECL_SIZE (field
);
3822 pair
->offset
= offset
+ bitpos_of_field (field
);
3823 if (DECL_NONADDRESSABLE_P (field
))
3824 pair
->alias_set
= get_alias_set (addressable_type
);
3826 pair
->alias_set
= -1;
3836 /* Create a constraint from ANYTHING variable to VI. */
3838 make_constraint_from_anything (varinfo_t vi
)
3840 struct constraint_expr lhs
, rhs
;
3846 rhs
.var
= anything_id
;
3848 rhs
.type
= ADDRESSOF
;
3849 process_constraint (new_constraint (lhs
, rhs
));
3852 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3853 if it is a varargs function. */
3856 count_num_arguments (tree decl
, bool *is_varargs
)
3861 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3865 if (TREE_VALUE (t
) == void_type_node
)
3875 /* Creation function node for DECL, using NAME, and return the index
3876 of the variable we've created for the function. */
3879 create_function_info_for (tree decl
, const char *name
)
3881 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3885 bool is_varargs
= false;
3887 /* Create the variable info. */
3889 vi
= new_var_info (decl
, index
, name
);
3894 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3895 insert_vi_for_tree (vi
->decl
, vi
);
3896 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3900 /* If it's varargs, we don't know how many arguments it has, so we
3907 vi
->is_unknown_size_var
= true;
3912 arg
= DECL_ARGUMENTS (decl
);
3914 /* Set up variables for each argument. */
3915 for (i
= 1; i
< vi
->fullsize
; i
++)
3918 const char *newname
;
3920 unsigned int newindex
;
3921 tree argdecl
= decl
;
3926 newindex
= VEC_length (varinfo_t
, varmap
);
3927 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3928 newname
= ggc_strdup (tempname
);
3931 argvi
= new_var_info (argdecl
, newindex
, newname
);
3932 argvi
->decl
= argdecl
;
3933 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3936 argvi
->fullsize
= vi
->fullsize
;
3937 argvi
->has_union
= false;
3938 insert_into_field_list_sorted (vi
, argvi
);
3939 stats
.total_vars
++;
3942 insert_vi_for_tree (arg
, argvi
);
3943 arg
= TREE_CHAIN (arg
);
3947 /* Create a variable for the return var. */
3948 if (DECL_RESULT (decl
) != NULL
3949 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3952 const char *newname
;
3954 unsigned int newindex
;
3955 tree resultdecl
= decl
;
3959 if (DECL_RESULT (decl
))
3960 resultdecl
= DECL_RESULT (decl
);
3962 newindex
= VEC_length (varinfo_t
, varmap
);
3963 asprintf (&tempname
, "%s.result", name
);
3964 newname
= ggc_strdup (tempname
);
3967 resultvi
= new_var_info (resultdecl
, newindex
, newname
);
3968 resultvi
->decl
= resultdecl
;
3969 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3970 resultvi
->offset
= i
;
3972 resultvi
->fullsize
= vi
->fullsize
;
3973 resultvi
->has_union
= false;
3974 insert_into_field_list_sorted (vi
, resultvi
);
3975 stats
.total_vars
++;
3976 if (DECL_RESULT (decl
))
3977 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
3983 /* Return true if FIELDSTACK contains fields that overlap.
3984 FIELDSTACK is assumed to be sorted by offset. */
3987 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3989 fieldoff_s
*fo
= NULL
;
3991 HOST_WIDE_INT lastoffset
= -1;
3993 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3995 if (fo
->offset
== lastoffset
)
3997 lastoffset
= fo
->offset
;
4002 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4003 This will also create any varinfo structures necessary for fields
4007 create_variable_info_for (tree decl
, const char *name
)
4009 unsigned int index
= VEC_length (varinfo_t
, varmap
);
4011 tree
decltype = TREE_TYPE (decl
);
4012 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
4013 bool notokay
= false;
4015 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
4016 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
4018 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
4019 return create_function_info_for (decl
, name
);
4021 hasunion
= TREE_CODE (decltype) == UNION_TYPE
4022 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
4023 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
4025 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
,
4029 VEC_free (fieldoff_s
, heap
, fieldstack
);
4035 /* If the variable doesn't have subvars, we may end up needing to
4036 sort the field list and create fake variables for all the
4038 vi
= new_var_info (decl
, index
, name
);
4041 vi
->has_union
= hasunion
;
4043 || TREE_CODE (declsize
) != INTEGER_CST
4044 || TREE_CODE (decltype) == UNION_TYPE
4045 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
4047 vi
->is_unknown_size_var
= true;
4053 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
4054 vi
->size
= vi
->fullsize
;
4057 insert_vi_for_tree (vi
->decl
, vi
);
4058 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
4059 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
4060 make_constraint_from_anything (vi
);
4063 if (use_field_sensitive
4065 && !vi
->is_unknown_size_var
4066 && var_can_have_subvars (decl
)
4067 && VEC_length (fieldoff_s
, fieldstack
) <= MAX_FIELDS_FOR_FIELD_SENSITIVE
)
4069 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
4070 fieldoff_s
*fo
= NULL
;
4073 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
4076 || TREE_CODE (fo
->size
) != INTEGER_CST
4084 /* We can't sort them if we have a field with a variable sized type,
4085 which will make notokay = true. In that case, we are going to return
4086 without creating varinfos for the fields anyway, so sorting them is a
4090 sort_fieldstack (fieldstack
);
4091 /* Due to some C++ FE issues, like PR 22488, we might end up
4092 what appear to be overlapping fields even though they,
4093 in reality, do not overlap. Until the C++ FE is fixed,
4094 we will simply disable field-sensitivity for these cases. */
4095 notokay
= check_for_overlaps (fieldstack
);
4099 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
4100 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
4102 if (fo
== NULL
|| notokay
)
4104 vi
->is_unknown_size_var
= 1;
4107 VEC_free (fieldoff_s
, heap
, fieldstack
);
4111 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
4112 vi
->offset
= fo
->offset
;
4113 for (i
= VEC_length (fieldoff_s
, fieldstack
) - 1;
4114 i
>= 1 && VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
4118 const char *newname
= "NULL";
4121 newindex
= VEC_length (varinfo_t
, varmap
);
4125 asprintf (&tempname
, "%s.%s",
4126 vi
->name
, alias_get_name (fo
->decl
));
4128 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
,
4129 vi
->name
, fo
->offset
);
4130 newname
= ggc_strdup (tempname
);
4133 newvi
= new_var_info (decl
, newindex
, newname
);
4134 newvi
->offset
= fo
->offset
;
4135 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
4136 newvi
->fullsize
= vi
->fullsize
;
4137 insert_into_field_list (vi
, newvi
);
4138 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
4139 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
4140 make_constraint_from_anything (newvi
);
4144 VEC_free (fieldoff_s
, heap
, fieldstack
);
4149 /* Print out the points-to solution for VAR to FILE. */
4152 dump_solution_for_var (FILE *file
, unsigned int var
)
4154 varinfo_t vi
= get_varinfo (var
);
4158 if (find (var
) != var
)
4160 varinfo_t vipt
= get_varinfo (find (var
));
4161 fprintf (file
, "%s = same as %s\n", vi
->name
, vipt
->name
);
4165 fprintf (file
, "%s = { ", vi
->name
);
4166 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4168 fprintf (file
, "%s ", get_varinfo (i
)->name
);
4170 fprintf (file
, "}");
4171 if (vi
->no_tbaa_pruning
)
4172 fprintf (file
, " no-tbaa-pruning");
4173 fprintf (file
, "\n");
4177 /* Print the points-to solution for VAR to stdout. */
4180 debug_solution_for_var (unsigned int var
)
4182 dump_solution_for_var (stdout
, var
);
4185 /* Create varinfo structures for all of the variables in the
4186 function for intraprocedural mode. */
4189 intra_create_variable_infos (void)
4192 struct constraint_expr lhs
, rhs
;
4194 /* For each incoming pointer argument arg, create the constraint ARG
4195 = ANYTHING or a dummy variable if flag_argument_noalias is set. */
4196 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
4200 if (!could_have_pointers (t
))
4203 /* If flag_argument_noalias is set, then function pointer
4204 arguments are guaranteed not to point to each other. In that
4205 case, create an artificial variable PARM_NOALIAS and the
4206 constraint ARG = &PARM_NOALIAS. */
4207 if (POINTER_TYPE_P (TREE_TYPE (t
)) && flag_argument_noalias
> 0)
4210 tree heapvar
= heapvar_lookup (t
);
4214 lhs
.var
= get_vi_for_tree (t
)->id
;
4216 if (heapvar
== NULL_TREE
)
4219 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)),
4221 DECL_EXTERNAL (heapvar
) = 1;
4222 if (gimple_referenced_vars (cfun
))
4223 add_referenced_var (heapvar
);
4225 heapvar_insert (t
, heapvar
);
4227 ann
= get_var_ann (heapvar
);
4228 if (flag_argument_noalias
== 1)
4229 ann
->noalias_state
= NO_ALIAS
;
4230 else if (flag_argument_noalias
== 2)
4231 ann
->noalias_state
= NO_ALIAS_GLOBAL
;
4232 else if (flag_argument_noalias
== 3)
4233 ann
->noalias_state
= NO_ALIAS_ANYTHING
;
4238 vi
= get_vi_for_tree (heapvar
);
4239 vi
->is_artificial_var
= 1;
4240 vi
->is_heap_var
= 1;
4242 rhs
.type
= ADDRESSOF
;
4244 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4246 struct constraint_expr temp
= lhs
;
4248 process_constraint (new_constraint (temp
, rhs
));
4253 varinfo_t arg_vi
= get_vi_for_tree (t
);
4255 for (p
= arg_vi
; p
; p
= p
->next
)
4256 make_constraint_from_anything (p
);
4261 /* Structure used to put solution bitmaps in a hashtable so they can
4262 be shared among variables with the same points-to set. */
4264 typedef struct shared_bitmap_info
4268 } *shared_bitmap_info_t
;
4270 static htab_t shared_bitmap_table
;
4272 /* Hash function for a shared_bitmap_info_t */
4275 shared_bitmap_hash (const void *p
)
4277 const shared_bitmap_info_t bi
= (shared_bitmap_info_t
) p
;
4278 return bi
->hashcode
;
4281 /* Equality function for two shared_bitmap_info_t's. */
4284 shared_bitmap_eq (const void *p1
, const void *p2
)
4286 const shared_bitmap_info_t sbi1
= (shared_bitmap_info_t
) p1
;
4287 const shared_bitmap_info_t sbi2
= (shared_bitmap_info_t
) p2
;
4288 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
4291 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4292 existing instance if there is one, NULL otherwise. */
4295 shared_bitmap_lookup (bitmap pt_vars
)
4298 struct shared_bitmap_info sbi
;
4300 sbi
.pt_vars
= pt_vars
;
4301 sbi
.hashcode
= bitmap_hash (pt_vars
);
4303 slot
= htab_find_slot_with_hash (shared_bitmap_table
, &sbi
,
4304 sbi
.hashcode
, NO_INSERT
);
4308 return ((shared_bitmap_info_t
) *slot
)->pt_vars
;
4312 /* Add a bitmap to the shared bitmap hashtable. */
4315 shared_bitmap_add (bitmap pt_vars
)
4318 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
4320 sbi
->pt_vars
= pt_vars
;
4321 sbi
->hashcode
= bitmap_hash (pt_vars
);
4323 slot
= htab_find_slot_with_hash (shared_bitmap_table
, sbi
,
4324 sbi
->hashcode
, INSERT
);
4325 gcc_assert (!*slot
);
4326 *slot
= (void *) sbi
;
4330 /* Set bits in INTO corresponding to the variable uids in solution set
4331 FROM, which came from variable PTR.
4332 For variables that are actually dereferenced, we also use type
4333 based alias analysis to prune the points-to sets.
4334 IS_DEREFED is true if PTR was directly dereferenced, which we use to
4335 help determine whether we are we are allowed to prune using TBAA.
4336 If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
4340 set_uids_in_ptset (tree ptr
, bitmap into
, bitmap from
, bool is_derefed
,
4341 bool no_tbaa_pruning
)
4346 HOST_WIDE_INT ptr_alias_set
= get_alias_set (TREE_TYPE (ptr
));
4348 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
4350 varinfo_t vi
= get_varinfo (i
);
4351 unsigned HOST_WIDE_INT var_alias_set
;
4353 /* The only artificial variables that are allowed in a may-alias
4354 set are heap variables. */
4355 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
4358 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
4360 /* Variables containing unions may need to be converted to
4361 their SFT's, because SFT's can have unions and we cannot. */
4362 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
4363 bitmap_set_bit (into
, DECL_UID (sv
->var
));
4365 else if (TREE_CODE (vi
->decl
) == VAR_DECL
4366 || TREE_CODE (vi
->decl
) == PARM_DECL
4367 || TREE_CODE (vi
->decl
) == RESULT_DECL
)
4369 if (var_can_have_subvars (vi
->decl
)
4370 && get_subvars_for_var (vi
->decl
))
4372 /* If VI->DECL is an aggregate for which we created
4373 SFTs, add the SFT corresponding to VI->OFFSET. */
4374 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
4377 var_alias_set
= get_alias_set (sft
);
4379 || (!is_derefed
&& !vi
->directly_dereferenced
)
4380 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
4381 bitmap_set_bit (into
, DECL_UID (sft
));
4386 /* Otherwise, just add VI->DECL to the alias set.
4387 Don't type prune artificial vars. */
4388 if (vi
->is_artificial_var
)
4389 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4392 var_alias_set
= get_alias_set (vi
->decl
);
4394 || (!is_derefed
&& !vi
->directly_dereferenced
)
4395 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
4396 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4404 static bool have_alias_info
= false;
4406 /* The list of SMT's that are in use by our pointer variables. This
4407 is the set of SMT's for all pointers that can point to anything. */
4408 static bitmap used_smts
;
4410 /* Due to the ordering of points-to set calculation and SMT
4411 calculation being a bit co-dependent, we can't just calculate SMT
4412 used info whenever we want, we have to calculate it around the time
4413 that find_what_p_points_to is called. */
4415 /* Mark which SMT's are in use by points-to anything variables. */
4418 set_used_smts (void)
4422 used_smts
= BITMAP_ALLOC (&pta_obstack
);
4424 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, vi
); i
++)
4426 tree var
= vi
->decl
;
4429 struct ptr_info_def
*pi
= NULL
;
4431 /* For parm decls, the pointer info may be under the default
4433 if (TREE_CODE (vi
->decl
) == PARM_DECL
4434 && gimple_default_def (cfun
, var
))
4435 pi
= SSA_NAME_PTR_INFO (gimple_default_def (cfun
, var
));
4436 else if (TREE_CODE (var
) == SSA_NAME
)
4437 pi
= SSA_NAME_PTR_INFO (var
);
4439 /* Skip the special variables and those without their own
4441 if (vi
->is_special_var
|| find (vi
->id
) != vi
->id
4443 || (pi
&& !pi
->is_dereferenced
)
4444 || (TREE_CODE (var
) == VAR_DECL
&& !may_be_aliased (var
))
4445 || !POINTER_TYPE_P (TREE_TYPE (var
)))
4448 if (TREE_CODE (var
) == SSA_NAME
)
4449 var
= SSA_NAME_VAR (var
);
4455 smt
= va
->symbol_mem_tag
;
4456 if (smt
&& bitmap_bit_p (vi
->solution
, anything_id
))
4457 bitmap_set_bit (used_smts
, DECL_UID (smt
));
4461 /* Merge the necessary SMT's into the bitmap INTO, which is
4462 P's varinfo. This involves merging all SMT's that are a subset of
4463 the SMT necessary for P. */
4466 merge_smts_into (tree p
, bitmap solution
)
4474 if (TREE_CODE (p
) == SSA_NAME
)
4475 var
= SSA_NAME_VAR (p
);
4477 smt
= var_ann (var
)->symbol_mem_tag
;
4480 HOST_WIDE_INT smtset
= get_alias_set (TREE_TYPE (smt
));
4482 /* Need to set the SMT subsets first before this
4483 will work properly. */
4484 bitmap_set_bit (solution
, DECL_UID (smt
));
4485 EXECUTE_IF_SET_IN_BITMAP (used_smts
, 0, i
, bi
)
4487 tree newsmt
= referenced_var (i
);
4488 tree newsmttype
= TREE_TYPE (newsmt
);
4490 if (alias_set_subset_of (get_alias_set (newsmttype
),
4492 bitmap_set_bit (solution
, i
);
4495 aliases
= MTAG_ALIASES (smt
);
4497 bitmap_ior_into (solution
, aliases
);
4501 /* Given a pointer variable P, fill in its points-to set, or return
4503 Rather than return false for variables that point-to anything, we
4504 instead find the corresponding SMT, and merge in it's aliases. In
4505 addition to these aliases, we also set the bits for the SMT's
4506 themselves and their subsets, as SMT's are still in use by
4507 non-SSA_NAME's, and pruning may eliminate every one of their
4508 aliases. In such a case, if we did not include the right set of
4509 SMT's in the points-to set of the variable, we'd end up with
4510 statements that do not conflict but should. */
4513 find_what_p_points_to (tree p
)
4518 if (!have_alias_info
)
4521 /* For parameters, get at the points-to set for the actual parm
4523 if (TREE_CODE (p
) == SSA_NAME
4524 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
4525 && SSA_NAME_IS_DEFAULT_DEF (p
))
4526 lookup_p
= SSA_NAME_VAR (p
);
4528 vi
= lookup_vi_for_tree (lookup_p
);
4531 if (vi
->is_artificial_var
)
4534 /* See if this is a field or a structure. */
4535 if (vi
->size
!= vi
->fullsize
)
4537 /* Nothing currently asks about structure fields directly,
4538 but when they do, we need code here to hand back the
4540 if (!var_can_have_subvars (vi
->decl
)
4541 || get_subvars_for_var (vi
->decl
) == NULL
)
4546 struct ptr_info_def
*pi
= get_ptr_info (p
);
4549 bool was_pt_anything
= false;
4550 bitmap finished_solution
;
4553 if (!pi
->is_dereferenced
)
4556 /* This variable may have been collapsed, let's get the real
4558 vi
= get_varinfo (find (vi
->id
));
4560 /* Translate artificial variables into SSA_NAME_PTR_INFO
4562 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4564 varinfo_t vi
= get_varinfo (i
);
4566 if (vi
->is_artificial_var
)
4568 /* FIXME. READONLY should be handled better so that
4569 flow insensitive aliasing can disregard writable
4571 if (vi
->id
== nothing_id
)
4573 else if (vi
->id
== anything_id
)
4574 was_pt_anything
= 1;
4575 else if (vi
->id
== readonly_id
)
4576 was_pt_anything
= 1;
4577 else if (vi
->id
== integer_id
)
4578 was_pt_anything
= 1;
4579 else if (vi
->is_heap_var
)
4580 pi
->pt_global_mem
= 1;
4584 /* Share the final set of variables when possible. */
4586 finished_solution
= BITMAP_GGC_ALLOC ();
4587 stats
.points_to_sets_created
++;
4589 /* Instead of using pt_anything, we merge in the SMT aliases
4590 for the underlying SMT. In addition, if they could have
4591 pointed to anything, they could point to global memory.
4592 But we cannot do that for ref-all pointers because these
4593 aliases have not been computed yet. */
4594 if (was_pt_anything
)
4596 if (PTR_IS_REF_ALL (p
))
4598 pi
->pt_anything
= 1;
4602 merge_smts_into (p
, finished_solution
);
4603 pi
->pt_global_mem
= 1;
4606 set_uids_in_ptset (vi
->decl
, finished_solution
, vi
->solution
,
4607 vi
->directly_dereferenced
,
4608 vi
->no_tbaa_pruning
);
4609 result
= shared_bitmap_lookup (finished_solution
);
4613 shared_bitmap_add (finished_solution
);
4614 pi
->pt_vars
= finished_solution
;
4618 pi
->pt_vars
= result
;
4619 bitmap_clear (finished_solution
);
4622 if (bitmap_empty_p (pi
->pt_vars
))
4634 /* Dump points-to information to OUTFILE. */
4637 dump_sa_points_to_info (FILE *outfile
)
4641 fprintf (outfile
, "\nPoints-to sets\n\n");
4643 if (dump_flags
& TDF_STATS
)
4645 fprintf (outfile
, "Stats:\n");
4646 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4647 fprintf (outfile
, "Non-pointer vars: %d\n",
4648 stats
.nonpointer_vars
);
4649 fprintf (outfile
, "Statically unified vars: %d\n",
4650 stats
.unified_vars_static
);
4651 fprintf (outfile
, "Dynamically unified vars: %d\n",
4652 stats
.unified_vars_dynamic
);
4653 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4654 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4655 fprintf (outfile
, "Number of implicit edges: %d\n",
4656 stats
.num_implicit_edges
);
4659 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4660 dump_solution_for_var (outfile
, i
);
4664 /* Debug points-to information to stderr. */
4667 debug_sa_points_to_info (void)
4669 dump_sa_points_to_info (stderr
);
4673 /* Initialize the always-existing constraint variables for NULL
4674 ANYTHING, READONLY, and INTEGER */
4677 init_base_vars (void)
4679 struct constraint_expr lhs
, rhs
;
4681 /* Create the NULL variable, used to represent that a variable points
4683 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4684 var_nothing
= new_var_info (nothing_tree
, 0, "NULL");
4685 insert_vi_for_tree (nothing_tree
, var_nothing
);
4686 var_nothing
->is_artificial_var
= 1;
4687 var_nothing
->offset
= 0;
4688 var_nothing
->size
= ~0;
4689 var_nothing
->fullsize
= ~0;
4690 var_nothing
->is_special_var
= 1;
4692 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4694 /* Create the ANYTHING variable, used to represent that a variable
4695 points to some unknown piece of memory. */
4696 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4697 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING");
4698 insert_vi_for_tree (anything_tree
, var_anything
);
4699 var_anything
->is_artificial_var
= 1;
4700 var_anything
->size
= ~0;
4701 var_anything
->offset
= 0;
4702 var_anything
->next
= NULL
;
4703 var_anything
->fullsize
= ~0;
4704 var_anything
->is_special_var
= 1;
4707 /* Anything points to anything. This makes deref constraints just
4708 work in the presence of linked list and other p = *p type loops,
4709 by saying that *ANYTHING = ANYTHING. */
4710 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4712 lhs
.var
= anything_id
;
4714 rhs
.type
= ADDRESSOF
;
4715 rhs
.var
= anything_id
;
4718 /* This specifically does not use process_constraint because
4719 process_constraint ignores all anything = anything constraints, since all
4720 but this one are redundant. */
4721 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4723 /* Create the READONLY variable, used to represent that a variable
4724 points to readonly memory. */
4725 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4726 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY");
4727 var_readonly
->is_artificial_var
= 1;
4728 var_readonly
->offset
= 0;
4729 var_readonly
->size
= ~0;
4730 var_readonly
->fullsize
= ~0;
4731 var_readonly
->next
= NULL
;
4732 var_readonly
->is_special_var
= 1;
4733 insert_vi_for_tree (readonly_tree
, var_readonly
);
4735 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4737 /* readonly memory points to anything, in order to make deref
4738 easier. In reality, it points to anything the particular
4739 readonly variable can point to, but we don't track this
4742 lhs
.var
= readonly_id
;
4744 rhs
.type
= ADDRESSOF
;
4745 rhs
.var
= anything_id
;
4748 process_constraint (new_constraint (lhs
, rhs
));
4750 /* Create the INTEGER variable, used to represent that a variable points
4752 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4753 var_integer
= new_var_info (integer_tree
, 3, "INTEGER");
4754 insert_vi_for_tree (integer_tree
, var_integer
);
4755 var_integer
->is_artificial_var
= 1;
4756 var_integer
->size
= ~0;
4757 var_integer
->fullsize
= ~0;
4758 var_integer
->offset
= 0;
4759 var_integer
->next
= NULL
;
4760 var_integer
->is_special_var
= 1;
4762 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4764 /* INTEGER = ANYTHING, because we don't know where a dereference of
4765 a random integer will point to. */
4767 lhs
.var
= integer_id
;
4769 rhs
.type
= ADDRESSOF
;
4770 rhs
.var
= anything_id
;
4772 process_constraint (new_constraint (lhs
, rhs
));
4775 /* Initialize things necessary to perform PTA */
4778 init_alias_vars (void)
4780 bitmap_obstack_initialize (&pta_obstack
);
4781 bitmap_obstack_initialize (&oldpta_obstack
);
4782 bitmap_obstack_initialize (&predbitmap_obstack
);
4784 constraint_pool
= create_alloc_pool ("Constraint pool",
4785 sizeof (struct constraint
), 30);
4786 variable_info_pool
= create_alloc_pool ("Variable info pool",
4787 sizeof (struct variable_info
), 30);
4788 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4789 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4790 vi_for_tree
= pointer_map_create ();
4792 memset (&stats
, 0, sizeof (stats
));
4793 shared_bitmap_table
= htab_create (511, shared_bitmap_hash
,
4794 shared_bitmap_eq
, free
);
4798 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
4799 predecessor edges. */
4802 remove_preds_and_fake_succs (constraint_graph_t graph
)
4806 /* Clear the implicit ref and address nodes from the successor
4808 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
4810 if (graph
->succs
[i
])
4811 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
4812 FIRST_REF_NODE
* 2);
4815 /* Free the successor list for the non-ref nodes. */
4816 for (i
= FIRST_REF_NODE
; i
< graph
->size
; i
++)
4818 if (graph
->succs
[i
])
4819 BITMAP_FREE (graph
->succs
[i
]);
4822 /* Now reallocate the size of the successor list as, and blow away
4823 the predecessor bitmaps. */
4824 graph
->size
= VEC_length (varinfo_t
, varmap
);
4825 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
4827 free (graph
->implicit_preds
);
4828 graph
->implicit_preds
= NULL
;
4829 free (graph
->preds
);
4830 graph
->preds
= NULL
;
4831 bitmap_obstack_release (&predbitmap_obstack
);
4834 /* Compute the set of variables we can't TBAA prune. */
4837 compute_tbaa_pruning (void)
4839 unsigned int size
= VEC_length (varinfo_t
, varmap
);
4844 changed
= sbitmap_alloc (size
);
4845 sbitmap_zero (changed
);
4847 /* Mark all initial no_tbaa_pruning nodes as changed. */
4849 for (i
= 0; i
< size
; ++i
)
4851 varinfo_t ivi
= get_varinfo (i
);
4853 if (find (i
) == i
&& ivi
->no_tbaa_pruning
)
4856 if ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
4857 || VEC_length (constraint_t
, graph
->complex[i
]) > 0)
4859 SET_BIT (changed
, i
);
4865 while (changed_count
> 0)
4867 struct topo_info
*ti
= init_topo_info ();
4870 bitmap_obstack_initialize (&iteration_obstack
);
4872 compute_topo_order (graph
, ti
);
4874 while (VEC_length (unsigned, ti
->topo_order
) != 0)
4878 i
= VEC_pop (unsigned, ti
->topo_order
);
4880 /* If this variable is not a representative, skip it. */
4884 /* If the node has changed, we need to process the complex
4885 constraints and outgoing edges again. */
4886 if (TEST_BIT (changed
, i
))
4890 VEC(constraint_t
,heap
) *complex = graph
->complex[i
];
4892 RESET_BIT (changed
, i
);
4895 /* Process the complex copy constraints. */
4896 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); ++j
)
4898 if (c
->lhs
.type
== SCALAR
&& c
->rhs
.type
== SCALAR
)
4900 varinfo_t lhsvi
= get_varinfo (find (c
->lhs
.var
));
4902 if (!lhsvi
->no_tbaa_pruning
)
4904 lhsvi
->no_tbaa_pruning
= true;
4905 if (!TEST_BIT (changed
, lhsvi
->id
))
4907 SET_BIT (changed
, lhsvi
->id
);
4914 /* Propagate to all successors. */
4915 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
], 0, j
, bi
)
4917 unsigned int to
= find (j
);
4918 varinfo_t tovi
= get_varinfo (to
);
4920 /* Don't propagate to ourselves. */
4924 if (!tovi
->no_tbaa_pruning
)
4926 tovi
->no_tbaa_pruning
= true;
4927 if (!TEST_BIT (changed
, to
))
4929 SET_BIT (changed
, to
);
4937 free_topo_info (ti
);
4938 bitmap_obstack_release (&iteration_obstack
);
4941 sbitmap_free (changed
);
4945 for (i
= 0; i
< size
; ++i
)
4947 varinfo_t ivi
= get_varinfo (i
);
4948 varinfo_t ivip
= get_varinfo (find (i
));
4950 if (ivip
->no_tbaa_pruning
)
4952 tree var
= ivi
->decl
;
4954 if (TREE_CODE (var
) == SSA_NAME
)
4955 var
= SSA_NAME_VAR (var
);
4957 if (POINTER_TYPE_P (TREE_TYPE (var
)))
4959 DECL_NO_TBAA_P (var
) = 1;
4961 /* Tell the RTL layer that this pointer can alias
4963 DECL_POINTER_ALIAS_SET (var
) = 0;
4970 /* Create points-to sets for the current function. See the comments
4971 at the start of the file for an algorithmic overview. */
4974 compute_points_to_sets (struct alias_info
*ai
)
4976 struct scc_info
*si
;
4979 timevar_push (TV_TREE_PTA
);
4982 init_alias_heapvars ();
4984 intra_create_variable_infos ();
4986 /* Now walk all statements and derive aliases. */
4989 block_stmt_iterator bsi
;
4992 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
4994 if (is_gimple_reg (PHI_RESULT (phi
)))
4996 find_func_aliases (phi
);
4998 /* Update various related attributes like escaped
4999 addresses, pointer dereferences for loads and stores.
5000 This is used when creating name tags and alias
5002 update_alias_info (phi
, ai
);
5006 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
5008 tree stmt
= bsi_stmt (bsi
);
5010 find_func_aliases (stmt
);
5012 /* Update various related attributes like escaped
5013 addresses, pointer dereferences for loads and stores.
5014 This is used when creating name tags and alias
5016 update_alias_info (stmt
, ai
);
5018 /* The information in CHANGE_DYNAMIC_TYPE_EXPR nodes has now
5019 been captured, and we can remove them. */
5020 if (TREE_CODE (stmt
) == CHANGE_DYNAMIC_TYPE_EXPR
)
5021 bsi_remove (&bsi
, true);
5030 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
5031 dump_constraints (dump_file
);
5036 "\nCollapsing static cycles and doing variable "
5038 build_pred_graph ();
5039 si
= perform_var_substitution (graph
);
5040 move_complex_constraints (graph
, si
);
5041 free_var_substitution_info (si
);
5043 build_succ_graph ();
5044 find_indirect_cycles (graph
);
5046 /* Implicit nodes and predecessors are no longer necessary at this
5048 remove_preds_and_fake_succs (graph
);
5051 fprintf (dump_file
, "\nSolving graph:\n");
5053 solve_graph (graph
);
5055 compute_tbaa_pruning ();
5058 dump_sa_points_to_info (dump_file
);
5060 have_alias_info
= true;
5062 timevar_pop (TV_TREE_PTA
);
5066 /* Delete created points-to sets. */
5069 delete_points_to_sets (void)
5074 htab_delete (shared_bitmap_table
);
5075 if (dump_file
&& (dump_flags
& TDF_STATS
))
5076 fprintf (dump_file
, "Points to sets created:%d\n",
5077 stats
.points_to_sets_created
);
5079 pointer_map_destroy (vi_for_tree
);
5080 bitmap_obstack_release (&pta_obstack
);
5081 VEC_free (constraint_t
, heap
, constraints
);
5083 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
5084 VEC_free (constraint_t
, heap
, graph
->complex[i
]);
5085 free (graph
->complex);
5088 free (graph
->succs
);
5089 free (graph
->indirect_cycles
);
5092 VEC_free (varinfo_t
, heap
, varmap
);
5093 free_alloc_pool (variable_info_pool
);
5094 free_alloc_pool (constraint_pool
);
5095 have_alias_info
= false;
5098 /* Return true if we should execute IPA PTA. */
5102 return (flag_unit_at_a_time
!= 0
5104 /* Don't bother doing anything if the program has errors. */
5105 && !(errorcount
|| sorrycount
));
5108 /* Execute the driver for IPA PTA. */
5110 ipa_pta_execute (void)
5112 struct cgraph_node
*node
;
5113 struct scc_info
*si
;
5116 init_alias_heapvars ();
5119 for (node
= cgraph_nodes
; node
; node
= node
->next
)
5121 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
5125 varid
= create_function_info_for (node
->decl
,
5126 cgraph_node_name (node
));
5127 if (node
->local
.externally_visible
)
5129 varinfo_t fi
= get_varinfo (varid
);
5130 for (; fi
; fi
= fi
->next
)
5131 make_constraint_from_anything (fi
);
5135 for (node
= cgraph_nodes
; node
; node
= node
->next
)
5137 if (node
->analyzed
&& cgraph_is_master_clone (node
))
5139 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
5141 tree old_func_decl
= current_function_decl
;
5144 "Generating constraints for %s\n",
5145 cgraph_node_name (node
));
5147 current_function_decl
= node
->decl
;
5149 FOR_EACH_BB_FN (bb
, cfun
)
5151 block_stmt_iterator bsi
;
5154 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
5156 if (is_gimple_reg (PHI_RESULT (phi
)))
5158 find_func_aliases (phi
);
5162 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
5164 tree stmt
= bsi_stmt (bsi
);
5165 find_func_aliases (stmt
);
5168 current_function_decl
= old_func_decl
;
5173 /* Make point to anything. */
5181 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
5182 dump_constraints (dump_file
);
5187 "\nCollapsing static cycles and doing variable "
5190 build_pred_graph ();
5191 si
= perform_var_substitution (graph
);
5192 move_complex_constraints (graph
, si
);
5193 free_var_substitution_info (si
);
5195 build_succ_graph ();
5196 find_indirect_cycles (graph
);
5198 /* Implicit nodes and predecessors are no longer necessary at this
5200 remove_preds_and_fake_succs (graph
);
5203 fprintf (dump_file
, "\nSolving graph:\n");
5205 solve_graph (graph
);
5208 dump_sa_points_to_info (dump_file
);
5211 delete_alias_heapvars ();
5212 delete_points_to_sets ();
5216 struct tree_opt_pass pass_ipa_pta
=
5219 gate_ipa_pta
, /* gate */
5220 ipa_pta_execute
, /* execute */
5223 0, /* static_pass_number */
5224 TV_IPA_PTA
, /* tv_id */
5225 0, /* properties_required */
5226 0, /* properties_provided */
5227 0, /* properties_destroyed */
5228 0, /* todo_flags_start */
5229 0, /* todo_flags_finish */
5233 /* Initialize the heapvar for statement mapping. */
5235 init_alias_heapvars (void)
5237 if (!heapvar_for_stmt
)
5238 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
,
5243 delete_alias_heapvars (void)
5245 htab_delete (heapvar_for_stmt
);
5246 heapvar_for_stmt
= NULL
;
5250 #include "gt-tree-ssa-structalias.h"