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 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 if (TREE_CODE (op1
) == INTEGER_CST
)
3306 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
3308 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
3309 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
3311 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
3313 varinfo_t temp
= get_varinfo (c2
->var
);
3315 /* An access one after the end of an array is valid,
3316 so simply punt on accesses we cannot resolve. */
3317 temp
= first_vi_for_offset (temp
, rhsoffset
);
3324 c2
->offset
= rhsoffset
;
3325 process_constraint (new_constraint (*c
, *c2
));
3328 VEC_free (ce_s
, heap
, temp
);
3334 /* Walk statement T setting up aliasing constraints according to the
3335 references found in T. This function is the main part of the
3336 constraint builder. AI points to auxiliary alias information used
3337 when building alias sets and computing alias grouping heuristics. */
3340 find_func_aliases (tree origt
)
3343 VEC(ce_s
, heap
) *lhsc
= NULL
;
3344 VEC(ce_s
, heap
) *rhsc
= NULL
;
3345 struct constraint_expr
*c
;
3347 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
3348 t
= TREE_OPERAND (t
, 0);
3350 /* Now build constraints expressions. */
3351 if (TREE_CODE (t
) == PHI_NODE
)
3353 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))));
3355 /* Only care about pointers and structures containing
3357 if (could_have_pointers (PHI_RESULT (t
)))
3362 /* For a phi node, assign all the arguments to
3364 get_constraint_for (PHI_RESULT (t
), &lhsc
);
3365 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
3368 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
3370 STRIP_NOPS (strippedrhs
);
3371 rhstype
= TREE_TYPE (strippedrhs
);
3372 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
3374 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3376 struct constraint_expr
*c2
;
3377 while (VEC_length (ce_s
, rhsc
) > 0)
3379 c2
= VEC_last (ce_s
, rhsc
);
3380 process_constraint (new_constraint (*c
, *c2
));
3381 VEC_pop (ce_s
, rhsc
);
3387 /* In IPA mode, we need to generate constraints to pass call
3388 arguments through their calls. There are two cases, either a
3389 GIMPLE_MODIFY_STMT when we are returning a value, or just a plain
3390 CALL_EXPR when we are not. */
3391 else if (in_ipa_mode
3392 && ((TREE_CODE (t
) == GIMPLE_MODIFY_STMT
3393 && TREE_CODE (GIMPLE_STMT_OPERAND (t
, 1)) == CALL_EXPR
3394 && !(call_expr_flags (GIMPLE_STMT_OPERAND (t
, 1))
3395 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
3396 || (TREE_CODE (t
) == CALL_EXPR
3397 && !(call_expr_flags (t
)
3398 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
3403 call_expr_arg_iterator iter
;
3407 if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
3409 lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
3410 rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
3417 decl
= get_callee_fndecl (rhsop
);
3419 /* If we can directly resolve the function being called, do so.
3420 Otherwise, it must be some sort of indirect expression that
3421 we should still be able to handle. */
3424 fi
= get_vi_for_tree (decl
);
3428 decl
= CALL_EXPR_FN (rhsop
);
3429 fi
= get_vi_for_tree (decl
);
3432 /* Assign all the passed arguments to the appropriate incoming
3433 parameters of the function. */
3435 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, rhsop
)
3437 struct constraint_expr lhs
;
3438 struct constraint_expr
*rhsp
;
3440 get_constraint_for (arg
, &rhsc
);
3441 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3450 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3453 while (VEC_length (ce_s
, rhsc
) != 0)
3455 rhsp
= VEC_last (ce_s
, rhsc
);
3456 process_constraint (new_constraint (lhs
, *rhsp
));
3457 VEC_pop (ce_s
, rhsc
);
3462 /* If we are returning a value, assign it to the result. */
3465 struct constraint_expr rhs
;
3466 struct constraint_expr
*lhsp
;
3469 get_constraint_for (lhsop
, &lhsc
);
3470 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3479 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3482 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3483 process_constraint (new_constraint (*lhsp
, rhs
));
3486 /* Otherwise, just a regular assignment statement. */
3487 else if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
3489 tree lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
3490 tree rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
3493 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3494 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
)
3495 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop
))
3496 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
))
3498 do_structure_copy (lhsop
, rhsop
);
3502 /* Only care about operations with pointers, structures
3503 containing pointers, dereferences, and call expressions. */
3504 if (could_have_pointers (lhsop
)
3505 || TREE_CODE (rhsop
) == CALL_EXPR
)
3507 get_constraint_for (lhsop
, &lhsc
);
3508 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3510 /* RHS that consist of unary operations,
3511 exceptional types, or bare decls/constants, get
3512 handled directly by get_constraint_for. */
3514 case tcc_declaration
:
3516 case tcc_exceptional
:
3517 case tcc_expression
:
3523 get_constraint_for (rhsop
, &rhsc
);
3524 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3526 struct constraint_expr
*c2
;
3529 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3530 process_constraint (new_constraint (*c
, *c2
));
3538 /* For pointer arithmetic of the form
3539 PTR + CST, we can simply use PTR's
3540 constraint because pointer arithmetic is
3541 not allowed to go out of bounds. */
3542 if (handle_ptr_arith (lhsc
, rhsop
))
3547 /* Otherwise, walk each operand. Notice that we
3548 can't use the operand interface because we need
3549 to process expressions other than simple operands
3550 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3552 for (i
= 0; i
< TREE_OPERAND_LENGTH (rhsop
); i
++)
3554 tree op
= TREE_OPERAND (rhsop
, i
);
3557 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3558 get_constraint_for (op
, &rhsc
);
3559 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3561 struct constraint_expr
*c2
;
3562 while (VEC_length (ce_s
, rhsc
) > 0)
3564 c2
= VEC_last (ce_s
, rhsc
);
3565 process_constraint (new_constraint (*c
, *c2
));
3566 VEC_pop (ce_s
, rhsc
);
3574 else if (TREE_CODE (t
) == CHANGE_DYNAMIC_TYPE_EXPR
)
3578 get_constraint_for (CHANGE_DYNAMIC_TYPE_LOCATION (t
), &lhsc
);
3579 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); ++j
)
3580 get_varinfo (c
->var
)->no_tbaa_pruning
= true;
3583 /* After promoting variables and computing aliasing we will
3584 need to re-scan most statements. FIXME: Try to minimize the
3585 number of statements re-scanned. It's not really necessary to
3586 re-scan *all* statements. */
3587 mark_stmt_modified (origt
);
3588 VEC_free (ce_s
, heap
, rhsc
);
3589 VEC_free (ce_s
, heap
, lhsc
);
3593 /* Find the first varinfo in the same variable as START that overlaps with
3595 Effectively, walk the chain of fields for the variable START to find the
3596 first field that overlaps with OFFSET.
3597 Return NULL if we can't find one. */
3600 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3602 varinfo_t curr
= start
;
3605 /* We may not find a variable in the field list with the actual
3606 offset when when we have glommed a structure to a variable.
3607 In that case, however, offset should still be within the size
3609 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3617 /* Insert the varinfo FIELD into the field list for BASE, at the front
3621 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3623 varinfo_t prev
= base
;
3624 varinfo_t curr
= base
->next
;
3630 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3634 insert_into_field_list_sorted (varinfo_t base
, varinfo_t field
)
3636 varinfo_t prev
= base
;
3637 varinfo_t curr
= base
->next
;
3648 if (field
->offset
<= curr
->offset
)
3653 field
->next
= prev
->next
;
3658 /* qsort comparison function for two fieldoff's PA and PB */
3661 fieldoff_compare (const void *pa
, const void *pb
)
3663 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3664 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3665 HOST_WIDE_INT foasize
, fobsize
;
3667 if (foa
->offset
!= fob
->offset
)
3668 return foa
->offset
- fob
->offset
;
3670 foasize
= TREE_INT_CST_LOW (foa
->size
);
3671 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3672 return foasize
- fobsize
;
3675 /* Sort a fieldstack according to the field offset and sizes. */
3677 sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3679 qsort (VEC_address (fieldoff_s
, fieldstack
),
3680 VEC_length (fieldoff_s
, fieldstack
),
3681 sizeof (fieldoff_s
),
3685 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3686 of TYPE onto fieldstack, recording their offsets along the way.
3687 OFFSET is used to keep track of the offset in this entire structure, rather
3688 than just the immediately containing structure. Returns the number
3690 HAS_UNION is set to true if we find a union type as a field of
3694 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3695 HOST_WIDE_INT offset
, bool *has_union
)
3700 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3702 fieldoff_s
*real_part
, *img_part
;
3703 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3704 real_part
->type
= TREE_TYPE (type
);
3705 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3706 real_part
->offset
= offset
;
3707 real_part
->decl
= NULL_TREE
;
3709 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3710 img_part
->type
= TREE_TYPE (type
);
3711 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3712 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3713 img_part
->decl
= NULL_TREE
;
3718 if (TREE_CODE (type
) == ARRAY_TYPE
)
3720 tree sz
= TYPE_SIZE (type
);
3721 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3726 || ! host_integerp (sz
, 1)
3727 || TREE_INT_CST_LOW (sz
) == 0
3729 || ! host_integerp (elsz
, 1)
3730 || TREE_INT_CST_LOW (elsz
) == 0)
3733 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3734 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3737 for (i
= 0; i
< nr
; ++i
)
3743 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3744 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3747 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3749 else if (!(pushed
= push_fields_onto_fieldstack
3750 (TREE_TYPE (type
), fieldstack
,
3751 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
)))
3752 /* Empty structures may have actual size, like in C++. So
3753 see if we didn't push any subfields and the size is
3754 nonzero, push the field onto the stack */
3761 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3762 pair
->type
= TREE_TYPE (type
);
3764 pair
->decl
= NULL_TREE
;
3765 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3775 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3776 if (TREE_CODE (field
) == FIELD_DECL
)
3782 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3783 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3786 if (!var_can_have_subvars (field
))
3788 else if (!(pushed
= push_fields_onto_fieldstack
3789 (TREE_TYPE (field
), fieldstack
,
3790 offset
+ bitpos_of_field (field
), has_union
))
3791 && DECL_SIZE (field
)
3792 && !integer_zerop (DECL_SIZE (field
)))
3793 /* Empty structures may have actual size, like in C++. So
3794 see if we didn't push any subfields and the size is
3795 nonzero, push the field onto the stack */
3802 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3803 pair
->type
= TREE_TYPE (field
);
3804 pair
->size
= DECL_SIZE (field
);
3806 pair
->offset
= offset
+ bitpos_of_field (field
);
3816 /* Create a constraint from ANYTHING variable to VI. */
3818 make_constraint_from_anything (varinfo_t vi
)
3820 struct constraint_expr lhs
, rhs
;
3826 rhs
.var
= anything_id
;
3828 rhs
.type
= ADDRESSOF
;
3829 process_constraint (new_constraint (lhs
, rhs
));
3832 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3833 if it is a varargs function. */
3836 count_num_arguments (tree decl
, bool *is_varargs
)
3841 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3845 if (TREE_VALUE (t
) == void_type_node
)
3855 /* Creation function node for DECL, using NAME, and return the index
3856 of the variable we've created for the function. */
3859 create_function_info_for (tree decl
, const char *name
)
3861 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3865 bool is_varargs
= false;
3867 /* Create the variable info. */
3869 vi
= new_var_info (decl
, index
, name
);
3874 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3875 insert_vi_for_tree (vi
->decl
, vi
);
3876 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3880 /* If it's varargs, we don't know how many arguments it has, so we
3887 vi
->is_unknown_size_var
= true;
3892 arg
= DECL_ARGUMENTS (decl
);
3894 /* Set up variables for each argument. */
3895 for (i
= 1; i
< vi
->fullsize
; i
++)
3898 const char *newname
;
3900 unsigned int newindex
;
3901 tree argdecl
= decl
;
3906 newindex
= VEC_length (varinfo_t
, varmap
);
3907 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3908 newname
= ggc_strdup (tempname
);
3911 argvi
= new_var_info (argdecl
, newindex
, newname
);
3912 argvi
->decl
= argdecl
;
3913 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3916 argvi
->fullsize
= vi
->fullsize
;
3917 argvi
->has_union
= false;
3918 insert_into_field_list_sorted (vi
, argvi
);
3919 stats
.total_vars
++;
3922 insert_vi_for_tree (arg
, argvi
);
3923 arg
= TREE_CHAIN (arg
);
3927 /* Create a variable for the return var. */
3928 if (DECL_RESULT (decl
) != NULL
3929 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3932 const char *newname
;
3934 unsigned int newindex
;
3935 tree resultdecl
= decl
;
3939 if (DECL_RESULT (decl
))
3940 resultdecl
= DECL_RESULT (decl
);
3942 newindex
= VEC_length (varinfo_t
, varmap
);
3943 asprintf (&tempname
, "%s.result", name
);
3944 newname
= ggc_strdup (tempname
);
3947 resultvi
= new_var_info (resultdecl
, newindex
, newname
);
3948 resultvi
->decl
= resultdecl
;
3949 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3950 resultvi
->offset
= i
;
3952 resultvi
->fullsize
= vi
->fullsize
;
3953 resultvi
->has_union
= false;
3954 insert_into_field_list_sorted (vi
, resultvi
);
3955 stats
.total_vars
++;
3956 if (DECL_RESULT (decl
))
3957 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
3963 /* Return true if FIELDSTACK contains fields that overlap.
3964 FIELDSTACK is assumed to be sorted by offset. */
3967 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3969 fieldoff_s
*fo
= NULL
;
3971 HOST_WIDE_INT lastoffset
= -1;
3973 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3975 if (fo
->offset
== lastoffset
)
3977 lastoffset
= fo
->offset
;
3982 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3983 This will also create any varinfo structures necessary for fields
3987 create_variable_info_for (tree decl
, const char *name
)
3989 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3991 tree
decltype = TREE_TYPE (decl
);
3992 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
3993 bool notokay
= false;
3995 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
3996 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
3998 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
3999 return create_function_info_for (decl
, name
);
4001 hasunion
= TREE_CODE (decltype) == UNION_TYPE
4002 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
4003 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
4005 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
4008 VEC_free (fieldoff_s
, heap
, fieldstack
);
4014 /* If the variable doesn't have subvars, we may end up needing to
4015 sort the field list and create fake variables for all the
4017 vi
= new_var_info (decl
, index
, name
);
4020 vi
->has_union
= hasunion
;
4022 || TREE_CODE (declsize
) != INTEGER_CST
4023 || TREE_CODE (decltype) == UNION_TYPE
4024 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
4026 vi
->is_unknown_size_var
= true;
4032 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
4033 vi
->size
= vi
->fullsize
;
4036 insert_vi_for_tree (vi
->decl
, vi
);
4037 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
4038 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
4039 make_constraint_from_anything (vi
);
4042 if (use_field_sensitive
4044 && !vi
->is_unknown_size_var
4045 && var_can_have_subvars (decl
)
4046 && VEC_length (fieldoff_s
, fieldstack
) <= MAX_FIELDS_FOR_FIELD_SENSITIVE
)
4048 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
4049 fieldoff_s
*fo
= NULL
;
4052 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
4055 || TREE_CODE (fo
->size
) != INTEGER_CST
4063 /* We can't sort them if we have a field with a variable sized type,
4064 which will make notokay = true. In that case, we are going to return
4065 without creating varinfos for the fields anyway, so sorting them is a
4069 sort_fieldstack (fieldstack
);
4070 /* Due to some C++ FE issues, like PR 22488, we might end up
4071 what appear to be overlapping fields even though they,
4072 in reality, do not overlap. Until the C++ FE is fixed,
4073 we will simply disable field-sensitivity for these cases. */
4074 notokay
= check_for_overlaps (fieldstack
);
4078 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
4079 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
4081 if (fo
== NULL
|| notokay
)
4083 vi
->is_unknown_size_var
= 1;
4086 VEC_free (fieldoff_s
, heap
, fieldstack
);
4090 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
4091 vi
->offset
= fo
->offset
;
4092 for (i
= VEC_length (fieldoff_s
, fieldstack
) - 1;
4093 i
>= 1 && VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
4097 const char *newname
= "NULL";
4100 newindex
= VEC_length (varinfo_t
, varmap
);
4104 asprintf (&tempname
, "%s.%s",
4105 vi
->name
, alias_get_name (fo
->decl
));
4107 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
,
4108 vi
->name
, fo
->offset
);
4109 newname
= ggc_strdup (tempname
);
4112 newvi
= new_var_info (decl
, newindex
, newname
);
4113 newvi
->offset
= fo
->offset
;
4114 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
4115 newvi
->fullsize
= vi
->fullsize
;
4116 insert_into_field_list (vi
, newvi
);
4117 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
4118 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
4119 make_constraint_from_anything (newvi
);
4123 VEC_free (fieldoff_s
, heap
, fieldstack
);
4128 /* Print out the points-to solution for VAR to FILE. */
4131 dump_solution_for_var (FILE *file
, unsigned int var
)
4133 varinfo_t vi
= get_varinfo (var
);
4137 if (find (var
) != var
)
4139 varinfo_t vipt
= get_varinfo (find (var
));
4140 fprintf (file
, "%s = same as %s\n", vi
->name
, vipt
->name
);
4144 fprintf (file
, "%s = { ", vi
->name
);
4145 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4147 fprintf (file
, "%s ", get_varinfo (i
)->name
);
4149 fprintf (file
, "}");
4150 if (vi
->no_tbaa_pruning
)
4151 fprintf (file
, " no-tbaa-pruning");
4152 fprintf (file
, "\n");
4156 /* Print the points-to solution for VAR to stdout. */
4159 debug_solution_for_var (unsigned int var
)
4161 dump_solution_for_var (stdout
, var
);
4164 /* Create varinfo structures for all of the variables in the
4165 function for intraprocedural mode. */
4168 intra_create_variable_infos (void)
4171 struct constraint_expr lhs
, rhs
;
4173 /* For each incoming pointer argument arg, create the constraint ARG
4174 = ANYTHING or a dummy variable if flag_argument_noalias is set. */
4175 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
4179 if (!could_have_pointers (t
))
4182 /* If flag_argument_noalias is set, then function pointer
4183 arguments are guaranteed not to point to each other. In that
4184 case, create an artificial variable PARM_NOALIAS and the
4185 constraint ARG = &PARM_NOALIAS. */
4186 if (POINTER_TYPE_P (TREE_TYPE (t
)) && flag_argument_noalias
> 0)
4189 tree heapvar
= heapvar_lookup (t
);
4193 lhs
.var
= get_vi_for_tree (t
)->id
;
4195 if (heapvar
== NULL_TREE
)
4198 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)),
4200 DECL_EXTERNAL (heapvar
) = 1;
4201 if (gimple_referenced_vars (cfun
))
4202 add_referenced_var (heapvar
);
4204 heapvar_insert (t
, heapvar
);
4206 ann
= get_var_ann (heapvar
);
4207 if (flag_argument_noalias
== 1)
4208 ann
->noalias_state
= NO_ALIAS
;
4209 else if (flag_argument_noalias
== 2)
4210 ann
->noalias_state
= NO_ALIAS_GLOBAL
;
4211 else if (flag_argument_noalias
== 3)
4212 ann
->noalias_state
= NO_ALIAS_ANYTHING
;
4217 vi
= get_vi_for_tree (heapvar
);
4218 vi
->is_artificial_var
= 1;
4219 vi
->is_heap_var
= 1;
4221 rhs
.type
= ADDRESSOF
;
4223 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4225 struct constraint_expr temp
= lhs
;
4227 process_constraint (new_constraint (temp
, rhs
));
4232 varinfo_t arg_vi
= get_vi_for_tree (t
);
4234 for (p
= arg_vi
; p
; p
= p
->next
)
4235 make_constraint_from_anything (p
);
4240 /* Structure used to put solution bitmaps in a hashtable so they can
4241 be shared among variables with the same points-to set. */
4243 typedef struct shared_bitmap_info
4247 } *shared_bitmap_info_t
;
4249 static htab_t shared_bitmap_table
;
4251 /* Hash function for a shared_bitmap_info_t */
4254 shared_bitmap_hash (const void *p
)
4256 const shared_bitmap_info_t bi
= (shared_bitmap_info_t
) p
;
4257 return bi
->hashcode
;
4260 /* Equality function for two shared_bitmap_info_t's. */
4263 shared_bitmap_eq (const void *p1
, const void *p2
)
4265 const shared_bitmap_info_t sbi1
= (shared_bitmap_info_t
) p1
;
4266 const shared_bitmap_info_t sbi2
= (shared_bitmap_info_t
) p2
;
4267 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
4270 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4271 existing instance if there is one, NULL otherwise. */
4274 shared_bitmap_lookup (bitmap pt_vars
)
4277 struct shared_bitmap_info sbi
;
4279 sbi
.pt_vars
= pt_vars
;
4280 sbi
.hashcode
= bitmap_hash (pt_vars
);
4282 slot
= htab_find_slot_with_hash (shared_bitmap_table
, &sbi
,
4283 sbi
.hashcode
, NO_INSERT
);
4287 return ((shared_bitmap_info_t
) *slot
)->pt_vars
;
4291 /* Add a bitmap to the shared bitmap hashtable. */
4294 shared_bitmap_add (bitmap pt_vars
)
4297 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
4299 sbi
->pt_vars
= pt_vars
;
4300 sbi
->hashcode
= bitmap_hash (pt_vars
);
4302 slot
= htab_find_slot_with_hash (shared_bitmap_table
, sbi
,
4303 sbi
->hashcode
, INSERT
);
4304 gcc_assert (!*slot
);
4305 *slot
= (void *) sbi
;
4309 /* Set bits in INTO corresponding to the variable uids in solution set
4310 FROM, which came from variable PTR.
4311 For variables that are actually dereferenced, we also use type
4312 based alias analysis to prune the points-to sets.
4313 IS_DEREFED is true if PTR was directly dereferenced, which we use to
4314 help determine whether we are we are allowed to prune using TBAA.
4315 If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
4319 set_uids_in_ptset (tree ptr
, bitmap into
, bitmap from
, bool is_derefed
,
4320 bool no_tbaa_pruning
)
4325 HOST_WIDE_INT ptr_alias_set
= get_alias_set (TREE_TYPE (ptr
));
4327 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
4329 varinfo_t vi
= get_varinfo (i
);
4330 unsigned HOST_WIDE_INT var_alias_set
;
4332 /* The only artificial variables that are allowed in a may-alias
4333 set are heap variables. */
4334 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
4337 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
4339 /* Variables containing unions may need to be converted to
4340 their SFT's, because SFT's can have unions and we cannot. */
4341 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
4342 bitmap_set_bit (into
, DECL_UID (sv
->var
));
4344 else if (TREE_CODE (vi
->decl
) == VAR_DECL
4345 || TREE_CODE (vi
->decl
) == PARM_DECL
)
4347 if (var_can_have_subvars (vi
->decl
)
4348 && get_subvars_for_var (vi
->decl
))
4350 /* If VI->DECL is an aggregate for which we created
4351 SFTs, add the SFT corresponding to VI->OFFSET. */
4352 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
4355 var_alias_set
= get_alias_set (sft
);
4357 || (!is_derefed
&& !vi
->directly_dereferenced
)
4358 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
4359 bitmap_set_bit (into
, DECL_UID (sft
));
4364 /* Otherwise, just add VI->DECL to the alias set.
4365 Don't type prune artificial vars. */
4366 if (vi
->is_artificial_var
)
4367 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4370 var_alias_set
= get_alias_set (vi
->decl
);
4372 || (!is_derefed
&& !vi
->directly_dereferenced
)
4373 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
4374 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4382 static bool have_alias_info
= false;
4384 /* The list of SMT's that are in use by our pointer variables. This
4385 is the set of SMT's for all pointers that can point to anything. */
4386 static bitmap used_smts
;
4388 /* Due to the ordering of points-to set calculation and SMT
4389 calculation being a bit co-dependent, we can't just calculate SMT
4390 used info whenever we want, we have to calculate it around the time
4391 that find_what_p_points_to is called. */
4393 /* Mark which SMT's are in use by points-to anything variables. */
4396 set_used_smts (void)
4400 used_smts
= BITMAP_ALLOC (&pta_obstack
);
4402 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, vi
); i
++)
4404 tree var
= vi
->decl
;
4407 struct ptr_info_def
*pi
= NULL
;
4409 /* For parm decls, the pointer info may be under the default
4411 if (TREE_CODE (vi
->decl
) == PARM_DECL
4412 && gimple_default_def (cfun
, var
))
4413 pi
= SSA_NAME_PTR_INFO (gimple_default_def (cfun
, var
));
4414 else if (TREE_CODE (var
) == SSA_NAME
)
4415 pi
= SSA_NAME_PTR_INFO (var
);
4417 /* Skip the special variables and those without their own
4419 if (vi
->is_special_var
|| find (vi
->id
) != vi
->id
4421 || (pi
&& !pi
->is_dereferenced
)
4422 || (TREE_CODE (var
) == VAR_DECL
&& !may_be_aliased (var
))
4423 || !POINTER_TYPE_P (TREE_TYPE (var
)))
4426 if (TREE_CODE (var
) == SSA_NAME
)
4427 var
= SSA_NAME_VAR (var
);
4433 smt
= va
->symbol_mem_tag
;
4434 if (smt
&& bitmap_bit_p (vi
->solution
, anything_id
))
4435 bitmap_set_bit (used_smts
, DECL_UID (smt
));
4439 /* Merge the necessary SMT's into the bitmap INTO, which is
4440 P's varinfo. This involves merging all SMT's that are a subset of
4441 the SMT necessary for P. */
4444 merge_smts_into (tree p
, bitmap solution
)
4452 if (TREE_CODE (p
) == SSA_NAME
)
4453 var
= SSA_NAME_VAR (p
);
4455 smt
= var_ann (var
)->symbol_mem_tag
;
4458 HOST_WIDE_INT smtset
= get_alias_set (TREE_TYPE (smt
));
4460 /* Need to set the SMT subsets first before this
4461 will work properly. */
4462 bitmap_set_bit (solution
, DECL_UID (smt
));
4463 EXECUTE_IF_SET_IN_BITMAP (used_smts
, 0, i
, bi
)
4465 tree newsmt
= referenced_var (i
);
4466 tree newsmttype
= TREE_TYPE (newsmt
);
4468 if (alias_set_subset_of (get_alias_set (newsmttype
),
4470 bitmap_set_bit (solution
, i
);
4473 aliases
= MTAG_ALIASES (smt
);
4475 bitmap_ior_into (solution
, aliases
);
4479 /* Given a pointer variable P, fill in its points-to set, or return
4481 Rather than return false for variables that point-to anything, we
4482 instead find the corresponding SMT, and merge in it's aliases. In
4483 addition to these aliases, we also set the bits for the SMT's
4484 themselves and their subsets, as SMT's are still in use by
4485 non-SSA_NAME's, and pruning may eliminate every one of their
4486 aliases. In such a case, if we did not include the right set of
4487 SMT's in the points-to set of the variable, we'd end up with
4488 statements that do not conflict but should. */
4491 find_what_p_points_to (tree p
)
4496 if (!have_alias_info
)
4499 /* For parameters, get at the points-to set for the actual parm
4501 if (TREE_CODE (p
) == SSA_NAME
4502 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
4503 && SSA_NAME_IS_DEFAULT_DEF (p
))
4504 lookup_p
= SSA_NAME_VAR (p
);
4506 vi
= lookup_vi_for_tree (lookup_p
);
4509 if (vi
->is_artificial_var
)
4512 /* See if this is a field or a structure. */
4513 if (vi
->size
!= vi
->fullsize
)
4515 /* Nothing currently asks about structure fields directly,
4516 but when they do, we need code here to hand back the
4518 if (!var_can_have_subvars (vi
->decl
)
4519 || get_subvars_for_var (vi
->decl
) == NULL
)
4524 struct ptr_info_def
*pi
= get_ptr_info (p
);
4527 bool was_pt_anything
= false;
4528 bitmap finished_solution
;
4531 if (!pi
->is_dereferenced
)
4534 /* This variable may have been collapsed, let's get the real
4536 vi
= get_varinfo (find (vi
->id
));
4538 /* Translate artificial variables into SSA_NAME_PTR_INFO
4540 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4542 varinfo_t vi
= get_varinfo (i
);
4544 if (vi
->is_artificial_var
)
4546 /* FIXME. READONLY should be handled better so that
4547 flow insensitive aliasing can disregard writable
4549 if (vi
->id
== nothing_id
)
4551 else if (vi
->id
== anything_id
)
4552 was_pt_anything
= 1;
4553 else if (vi
->id
== readonly_id
)
4554 was_pt_anything
= 1;
4555 else if (vi
->id
== integer_id
)
4556 was_pt_anything
= 1;
4557 else if (vi
->is_heap_var
)
4558 pi
->pt_global_mem
= 1;
4562 /* Share the final set of variables when possible. */
4564 finished_solution
= BITMAP_GGC_ALLOC ();
4565 stats
.points_to_sets_created
++;
4567 /* Instead of using pt_anything, we merge in the SMT aliases
4568 for the underlying SMT. In addition, if they could have
4569 pointed to anything, they could point to global memory.
4570 But we cannot do that for ref-all pointers because these
4571 aliases have not been computed yet. */
4572 if (was_pt_anything
)
4574 if (PTR_IS_REF_ALL (p
))
4576 pi
->pt_anything
= 1;
4580 merge_smts_into (p
, finished_solution
);
4581 pi
->pt_global_mem
= 1;
4584 set_uids_in_ptset (vi
->decl
, finished_solution
, vi
->solution
,
4585 vi
->directly_dereferenced
,
4586 vi
->no_tbaa_pruning
);
4587 result
= shared_bitmap_lookup (finished_solution
);
4591 shared_bitmap_add (finished_solution
);
4592 pi
->pt_vars
= finished_solution
;
4596 pi
->pt_vars
= result
;
4597 bitmap_clear (finished_solution
);
4600 if (bitmap_empty_p (pi
->pt_vars
))
4612 /* Dump points-to information to OUTFILE. */
4615 dump_sa_points_to_info (FILE *outfile
)
4619 fprintf (outfile
, "\nPoints-to sets\n\n");
4621 if (dump_flags
& TDF_STATS
)
4623 fprintf (outfile
, "Stats:\n");
4624 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4625 fprintf (outfile
, "Non-pointer vars: %d\n",
4626 stats
.nonpointer_vars
);
4627 fprintf (outfile
, "Statically unified vars: %d\n",
4628 stats
.unified_vars_static
);
4629 fprintf (outfile
, "Dynamically unified vars: %d\n",
4630 stats
.unified_vars_dynamic
);
4631 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4632 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4633 fprintf (outfile
, "Number of implicit edges: %d\n",
4634 stats
.num_implicit_edges
);
4637 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4638 dump_solution_for_var (outfile
, i
);
4642 /* Debug points-to information to stderr. */
4645 debug_sa_points_to_info (void)
4647 dump_sa_points_to_info (stderr
);
4651 /* Initialize the always-existing constraint variables for NULL
4652 ANYTHING, READONLY, and INTEGER */
4655 init_base_vars (void)
4657 struct constraint_expr lhs
, rhs
;
4659 /* Create the NULL variable, used to represent that a variable points
4661 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4662 var_nothing
= new_var_info (nothing_tree
, 0, "NULL");
4663 insert_vi_for_tree (nothing_tree
, var_nothing
);
4664 var_nothing
->is_artificial_var
= 1;
4665 var_nothing
->offset
= 0;
4666 var_nothing
->size
= ~0;
4667 var_nothing
->fullsize
= ~0;
4668 var_nothing
->is_special_var
= 1;
4670 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4672 /* Create the ANYTHING variable, used to represent that a variable
4673 points to some unknown piece of memory. */
4674 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4675 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING");
4676 insert_vi_for_tree (anything_tree
, var_anything
);
4677 var_anything
->is_artificial_var
= 1;
4678 var_anything
->size
= ~0;
4679 var_anything
->offset
= 0;
4680 var_anything
->next
= NULL
;
4681 var_anything
->fullsize
= ~0;
4682 var_anything
->is_special_var
= 1;
4685 /* Anything points to anything. This makes deref constraints just
4686 work in the presence of linked list and other p = *p type loops,
4687 by saying that *ANYTHING = ANYTHING. */
4688 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4690 lhs
.var
= anything_id
;
4692 rhs
.type
= ADDRESSOF
;
4693 rhs
.var
= anything_id
;
4696 /* This specifically does not use process_constraint because
4697 process_constraint ignores all anything = anything constraints, since all
4698 but this one are redundant. */
4699 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4701 /* Create the READONLY variable, used to represent that a variable
4702 points to readonly memory. */
4703 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4704 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY");
4705 var_readonly
->is_artificial_var
= 1;
4706 var_readonly
->offset
= 0;
4707 var_readonly
->size
= ~0;
4708 var_readonly
->fullsize
= ~0;
4709 var_readonly
->next
= NULL
;
4710 var_readonly
->is_special_var
= 1;
4711 insert_vi_for_tree (readonly_tree
, var_readonly
);
4713 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4715 /* readonly memory points to anything, in order to make deref
4716 easier. In reality, it points to anything the particular
4717 readonly variable can point to, but we don't track this
4720 lhs
.var
= readonly_id
;
4722 rhs
.type
= ADDRESSOF
;
4723 rhs
.var
= anything_id
;
4726 process_constraint (new_constraint (lhs
, rhs
));
4728 /* Create the INTEGER variable, used to represent that a variable points
4730 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4731 var_integer
= new_var_info (integer_tree
, 3, "INTEGER");
4732 insert_vi_for_tree (integer_tree
, var_integer
);
4733 var_integer
->is_artificial_var
= 1;
4734 var_integer
->size
= ~0;
4735 var_integer
->fullsize
= ~0;
4736 var_integer
->offset
= 0;
4737 var_integer
->next
= NULL
;
4738 var_integer
->is_special_var
= 1;
4740 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4742 /* INTEGER = ANYTHING, because we don't know where a dereference of
4743 a random integer will point to. */
4745 lhs
.var
= integer_id
;
4747 rhs
.type
= ADDRESSOF
;
4748 rhs
.var
= anything_id
;
4750 process_constraint (new_constraint (lhs
, rhs
));
4753 /* Initialize things necessary to perform PTA */
4756 init_alias_vars (void)
4758 bitmap_obstack_initialize (&pta_obstack
);
4759 bitmap_obstack_initialize (&oldpta_obstack
);
4760 bitmap_obstack_initialize (&predbitmap_obstack
);
4762 constraint_pool
= create_alloc_pool ("Constraint pool",
4763 sizeof (struct constraint
), 30);
4764 variable_info_pool
= create_alloc_pool ("Variable info pool",
4765 sizeof (struct variable_info
), 30);
4766 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4767 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4768 vi_for_tree
= pointer_map_create ();
4770 memset (&stats
, 0, sizeof (stats
));
4771 shared_bitmap_table
= htab_create (511, shared_bitmap_hash
,
4772 shared_bitmap_eq
, free
);
4776 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
4777 predecessor edges. */
4780 remove_preds_and_fake_succs (constraint_graph_t graph
)
4784 /* Clear the implicit ref and address nodes from the successor
4786 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
4788 if (graph
->succs
[i
])
4789 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
4790 FIRST_REF_NODE
* 2);
4793 /* Free the successor list for the non-ref nodes. */
4794 for (i
= FIRST_REF_NODE
; i
< graph
->size
; i
++)
4796 if (graph
->succs
[i
])
4797 BITMAP_FREE (graph
->succs
[i
]);
4800 /* Now reallocate the size of the successor list as, and blow away
4801 the predecessor bitmaps. */
4802 graph
->size
= VEC_length (varinfo_t
, varmap
);
4803 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
4805 free (graph
->implicit_preds
);
4806 graph
->implicit_preds
= NULL
;
4807 free (graph
->preds
);
4808 graph
->preds
= NULL
;
4809 bitmap_obstack_release (&predbitmap_obstack
);
4812 /* Compute the set of variables we can't TBAA prune. */
4815 compute_tbaa_pruning (void)
4817 unsigned int size
= VEC_length (varinfo_t
, varmap
);
4822 changed
= sbitmap_alloc (size
);
4823 sbitmap_zero (changed
);
4825 /* Mark all initial no_tbaa_pruning nodes as changed. */
4827 for (i
= 0; i
< size
; ++i
)
4829 varinfo_t ivi
= get_varinfo (i
);
4831 if (find (i
) == i
&& ivi
->no_tbaa_pruning
)
4834 if ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
4835 || VEC_length (constraint_t
, graph
->complex[i
]) > 0)
4837 SET_BIT (changed
, i
);
4843 while (changed_count
> 0)
4845 struct topo_info
*ti
= init_topo_info ();
4848 bitmap_obstack_initialize (&iteration_obstack
);
4850 compute_topo_order (graph
, ti
);
4852 while (VEC_length (unsigned, ti
->topo_order
) != 0)
4856 i
= VEC_pop (unsigned, ti
->topo_order
);
4858 /* If this variable is not a representative, skip it. */
4862 /* If the node has changed, we need to process the complex
4863 constraints and outgoing edges again. */
4864 if (TEST_BIT (changed
, i
))
4868 VEC(constraint_t
,heap
) *complex = graph
->complex[i
];
4870 RESET_BIT (changed
, i
);
4873 /* Process the complex copy constraints. */
4874 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); ++j
)
4876 if (c
->lhs
.type
== SCALAR
&& c
->rhs
.type
== SCALAR
)
4878 varinfo_t lhsvi
= get_varinfo (find (c
->lhs
.var
));
4880 if (!lhsvi
->no_tbaa_pruning
)
4882 lhsvi
->no_tbaa_pruning
= true;
4883 if (!TEST_BIT (changed
, lhsvi
->id
))
4885 SET_BIT (changed
, lhsvi
->id
);
4892 /* Propagate to all successors. */
4893 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
], 0, j
, bi
)
4895 unsigned int to
= find (j
);
4896 varinfo_t tovi
= get_varinfo (to
);
4898 /* Don't propagate to ourselves. */
4902 if (!tovi
->no_tbaa_pruning
)
4904 tovi
->no_tbaa_pruning
= true;
4905 if (!TEST_BIT (changed
, to
))
4907 SET_BIT (changed
, to
);
4915 free_topo_info (ti
);
4916 bitmap_obstack_release (&iteration_obstack
);
4919 sbitmap_free (changed
);
4923 for (i
= 0; i
< size
; ++i
)
4925 varinfo_t ivi
= get_varinfo (i
);
4926 varinfo_t ivip
= get_varinfo (find (i
));
4928 if (ivip
->no_tbaa_pruning
)
4930 tree var
= ivi
->decl
;
4932 if (TREE_CODE (var
) == SSA_NAME
)
4933 var
= SSA_NAME_VAR (var
);
4935 if (POINTER_TYPE_P (TREE_TYPE (var
)))
4937 DECL_NO_TBAA_P (var
) = 1;
4939 /* Tell the RTL layer that this pointer can alias
4941 DECL_POINTER_ALIAS_SET (var
) = 0;
4948 /* Create points-to sets for the current function. See the comments
4949 at the start of the file for an algorithmic overview. */
4952 compute_points_to_sets (struct alias_info
*ai
)
4954 struct scc_info
*si
;
4957 timevar_push (TV_TREE_PTA
);
4960 init_alias_heapvars ();
4962 intra_create_variable_infos ();
4964 /* Now walk all statements and derive aliases. */
4967 block_stmt_iterator bsi
;
4970 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
4972 if (is_gimple_reg (PHI_RESULT (phi
)))
4974 find_func_aliases (phi
);
4976 /* Update various related attributes like escaped
4977 addresses, pointer dereferences for loads and stores.
4978 This is used when creating name tags and alias
4980 update_alias_info (phi
, ai
);
4984 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
4986 tree stmt
= bsi_stmt (bsi
);
4988 find_func_aliases (stmt
);
4990 /* Update various related attributes like escaped
4991 addresses, pointer dereferences for loads and stores.
4992 This is used when creating name tags and alias
4994 update_alias_info (stmt
, ai
);
4996 /* The information in CHANGE_DYNAMIC_TYPE_EXPR nodes has now
4997 been captured, and we can remove them. */
4998 if (TREE_CODE (stmt
) == CHANGE_DYNAMIC_TYPE_EXPR
)
4999 bsi_remove (&bsi
, true);
5008 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
5009 dump_constraints (dump_file
);
5014 "\nCollapsing static cycles and doing variable "
5016 build_pred_graph ();
5017 si
= perform_var_substitution (graph
);
5018 move_complex_constraints (graph
, si
);
5019 free_var_substitution_info (si
);
5021 build_succ_graph ();
5022 find_indirect_cycles (graph
);
5024 /* Implicit nodes and predecessors are no longer necessary at this
5026 remove_preds_and_fake_succs (graph
);
5029 fprintf (dump_file
, "\nSolving graph:\n");
5031 solve_graph (graph
);
5033 compute_tbaa_pruning ();
5036 dump_sa_points_to_info (dump_file
);
5038 have_alias_info
= true;
5040 timevar_pop (TV_TREE_PTA
);
5044 /* Delete created points-to sets. */
5047 delete_points_to_sets (void)
5052 htab_delete (shared_bitmap_table
);
5053 if (dump_file
&& (dump_flags
& TDF_STATS
))
5054 fprintf (dump_file
, "Points to sets created:%d\n",
5055 stats
.points_to_sets_created
);
5057 pointer_map_destroy (vi_for_tree
);
5058 bitmap_obstack_release (&pta_obstack
);
5059 VEC_free (constraint_t
, heap
, constraints
);
5061 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
5062 VEC_free (constraint_t
, heap
, graph
->complex[i
]);
5063 free (graph
->complex);
5066 free (graph
->succs
);
5067 free (graph
->indirect_cycles
);
5070 VEC_free (varinfo_t
, heap
, varmap
);
5071 free_alloc_pool (variable_info_pool
);
5072 free_alloc_pool (constraint_pool
);
5073 have_alias_info
= false;
5076 /* Return true if we should execute IPA PTA. */
5080 return (flag_unit_at_a_time
!= 0
5082 /* Don't bother doing anything if the program has errors. */
5083 && !(errorcount
|| sorrycount
));
5086 /* Execute the driver for IPA PTA. */
5088 ipa_pta_execute (void)
5090 struct cgraph_node
*node
;
5091 struct scc_info
*si
;
5094 init_alias_heapvars ();
5097 for (node
= cgraph_nodes
; node
; node
= node
->next
)
5099 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
5103 varid
= create_function_info_for (node
->decl
,
5104 cgraph_node_name (node
));
5105 if (node
->local
.externally_visible
)
5107 varinfo_t fi
= get_varinfo (varid
);
5108 for (; fi
; fi
= fi
->next
)
5109 make_constraint_from_anything (fi
);
5113 for (node
= cgraph_nodes
; node
; node
= node
->next
)
5115 if (node
->analyzed
&& cgraph_is_master_clone (node
))
5117 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
5119 tree old_func_decl
= current_function_decl
;
5122 "Generating constraints for %s\n",
5123 cgraph_node_name (node
));
5125 current_function_decl
= node
->decl
;
5127 FOR_EACH_BB_FN (bb
, cfun
)
5129 block_stmt_iterator bsi
;
5132 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
5134 if (is_gimple_reg (PHI_RESULT (phi
)))
5136 find_func_aliases (phi
);
5140 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
5142 tree stmt
= bsi_stmt (bsi
);
5143 find_func_aliases (stmt
);
5146 current_function_decl
= old_func_decl
;
5151 /* Make point to anything. */
5159 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
5160 dump_constraints (dump_file
);
5165 "\nCollapsing static cycles and doing variable "
5168 build_pred_graph ();
5169 si
= perform_var_substitution (graph
);
5170 move_complex_constraints (graph
, si
);
5171 free_var_substitution_info (si
);
5173 build_succ_graph ();
5174 find_indirect_cycles (graph
);
5176 /* Implicit nodes and predecessors are no longer necessary at this
5178 remove_preds_and_fake_succs (graph
);
5181 fprintf (dump_file
, "\nSolving graph:\n");
5183 solve_graph (graph
);
5186 dump_sa_points_to_info (dump_file
);
5189 delete_alias_heapvars ();
5190 delete_points_to_sets ();
5194 struct tree_opt_pass pass_ipa_pta
=
5197 gate_ipa_pta
, /* gate */
5198 ipa_pta_execute
, /* execute */
5201 0, /* static_pass_number */
5202 TV_IPA_PTA
, /* tv_id */
5203 0, /* properties_required */
5204 0, /* properties_provided */
5205 0, /* properties_destroyed */
5206 0, /* todo_flags_start */
5207 0, /* todo_flags_finish */
5211 /* Initialize the heapvar for statement mapping. */
5213 init_alias_heapvars (void)
5215 if (!heapvar_for_stmt
)
5216 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
,
5221 delete_alias_heapvars (void)
5223 htab_delete (heapvar_for_stmt
);
5224 heapvar_for_stmt
= NULL
;
5228 #include "gt-tree-ssa-structalias.h"