1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dberlin@dberlin.org>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or
11 (at your option) any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
30 #include "basic-block.h"
33 #include "tree-flow.h"
34 #include "tree-inline.h"
40 #include "tree-pass.h"
42 #include "alloc-pool.h"
43 #include "splay-tree.h"
47 #include "pointer-set.h"
49 /* The idea behind this analyzer is to generate set constraints from the
50 program, then solve the resulting constraints in order to generate the
53 Set constraints are a way of modeling program analysis problems that
54 involve sets. They consist of an inclusion constraint language,
55 describing the variables (each variable is a set) and operations that
56 are involved on the variables, and a set of rules that derive facts
57 from these operations. To solve a system of set constraints, you derive
58 all possible facts under the rules, which gives you the correct sets
61 See "Efficient Field-sensitive pointer analysis for C" by "David
62 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
63 http://citeseer.ist.psu.edu/pearce04efficient.html
65 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
66 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
67 http://citeseer.ist.psu.edu/heintze01ultrafast.html
69 There are three types of real constraint expressions, DEREF,
70 ADDRESSOF, and SCALAR. Each constraint expression consists
71 of a constraint type, a variable, and an offset.
73 SCALAR is a constraint expression type used to represent x, whether
74 it appears on the LHS or the RHS of a statement.
75 DEREF is a constraint expression type used to represent *x, whether
76 it appears on the LHS or the RHS of a statement.
77 ADDRESSOF is a constraint expression used to represent &x, whether
78 it appears on the LHS or the RHS of a statement.
80 Each pointer variable in the program is assigned an integer id, and
81 each field of a structure variable is assigned an integer id as well.
83 Structure variables are linked to their list of fields through a "next
84 field" in each variable that points to the next field in offset
86 Each variable for a structure field has
88 1. "size", that tells the size in bits of that field.
89 2. "fullsize, that tells the size in bits of the entire structure.
90 3. "offset", that tells the offset in bits from the beginning of the
91 structure to this field.
103 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
104 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
105 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
108 In order to solve the system of set constraints, the following is
111 1. Each constraint variable x has a solution set associated with it,
114 2. Constraints are separated into direct, copy, and complex.
115 Direct constraints are ADDRESSOF constraints that require no extra
116 processing, such as P = &Q
117 Copy constraints are those of the form P = Q.
118 Complex constraints are all the constraints involving dereferences
119 and offsets (including offsetted copies).
121 3. All direct constraints of the form P = &Q are processed, such
122 that Q is added to Sol(P)
124 4. All complex constraints for a given constraint variable are stored in a
125 linked list attached to that variable's node.
127 5. A directed graph is built out of the copy constraints. Each
128 constraint variable is a node in the graph, and an edge from
129 Q to P is added for each copy constraint of the form P = Q
131 6. The graph is then walked, and solution sets are
132 propagated along the copy edges, such that an edge from Q to P
133 causes Sol(P) <- Sol(P) union Sol(Q).
135 7. As we visit each node, all complex constraints associated with
136 that node are processed by adding appropriate copy edges to the graph, or the
137 appropriate variables to the solution set.
139 8. The process of walking the graph is iterated until no solution
142 Prior to walking the graph in steps 6 and 7, We perform static
143 cycle elimination on the constraint graph, as well
144 as off-line variable substitution.
146 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
147 on and turned into anything), but isn't. You can just see what offset
148 inside the pointed-to struct it's going to access.
150 TODO: Constant bounded arrays can be handled as if they were structs of the
151 same number of elements.
153 TODO: Modeling heap and incoming pointers becomes much better if we
154 add fields to them as we discover them, which we could do.
156 TODO: We could handle unions, but to be honest, it's probably not
157 worth the pain or slowdown. */
159 /* IPA-PTA optimizations possible.
161 When the indirect function called is ANYTHING we can add disambiguation
162 based on the function signatures (or simply the parameter count which
163 is the varinfo size). We also do not need to consider functions that
164 do not have their address taken.
166 The is_global_var bit which marks escape points is overly conservative
167 in IPA mode. Split it to is_escape_point and is_global_var - only
168 externally visible globals are escape points in IPA mode. This is
169 also needed to fix the pt_solution_includes_global predicate
170 (and thus ptr_deref_may_alias_global_p).
172 The way we introduce DECL_PT_UID to avoid fixing up all points-to
173 sets in the translation unit when we copy a DECL during inlining
174 pessimizes precision. The advantage is that the DECL_PT_UID keeps
175 compile-time and memory usage overhead low - the points-to sets
176 do not grow or get unshared as they would during a fixup phase.
177 An alternative solution is to delay IPA PTA until after all
178 inlining transformations have been applied.
180 The way we propagate clobber/use information isn't optimized.
181 It should use a new complex constraint that properly filters
182 out local variables of the callee (though that would make
183 the sets invalid after inlining). OTOH we might as well
184 admit defeat to WHOPR and simply do all the clobber/use analysis
185 and propagation after PTA finished but before we threw away
186 points-to information for memory variables. WHOPR and PTA
187 do not play along well anyway - the whole constraint solving
188 would need to be done in WPA phase and it will be very interesting
189 to apply the results to local SSA names during LTRANS phase.
191 We probably should compute a per-function unit-ESCAPE solution
192 propagating it simply like the clobber / uses solutions. The
193 solution can go alongside the non-IPA espaced solution and be
194 used to query which vars escape the unit through a function.
196 We never put function decls in points-to sets so we do not
197 keep the set of called functions for indirect calls.
199 And probably more. */
200 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct heapvar_map
)))
201 htab_t heapvar_for_stmt
;
203 static bool use_field_sensitive
= true;
204 static int in_ipa_mode
= 0;
206 /* Used for predecessor bitmaps. */
207 static bitmap_obstack predbitmap_obstack
;
209 /* Used for points-to sets. */
210 static bitmap_obstack pta_obstack
;
212 /* Used for oldsolution members of variables. */
213 static bitmap_obstack oldpta_obstack
;
215 /* Used for per-solver-iteration bitmaps. */
216 static bitmap_obstack iteration_obstack
;
218 static unsigned int create_variable_info_for (tree
, const char *);
219 typedef struct constraint_graph
*constraint_graph_t
;
220 static void unify_nodes (constraint_graph_t
, unsigned int, unsigned int, bool);
223 typedef struct constraint
*constraint_t
;
225 DEF_VEC_P(constraint_t
);
226 DEF_VEC_ALLOC_P(constraint_t
,heap
);
228 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
230 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
232 static struct constraint_stats
234 unsigned int total_vars
;
235 unsigned int nonpointer_vars
;
236 unsigned int unified_vars_static
;
237 unsigned int unified_vars_dynamic
;
238 unsigned int iterations
;
239 unsigned int num_edges
;
240 unsigned int num_implicit_edges
;
241 unsigned int points_to_sets_created
;
246 /* ID of this variable */
249 /* True if this is a variable created by the constraint analysis, such as
250 heap variables and constraints we had to break up. */
251 unsigned int is_artificial_var
: 1;
253 /* True if this is a special variable whose solution set should not be
255 unsigned int is_special_var
: 1;
257 /* True for variables whose size is not known or variable. */
258 unsigned int is_unknown_size_var
: 1;
260 /* True for (sub-)fields that represent a whole variable. */
261 unsigned int is_full_var
: 1;
263 /* True if this is a heap variable. */
264 unsigned int is_heap_var
: 1;
266 /* True if this is a variable tracking a restrict pointer source. */
267 unsigned int is_restrict_var
: 1;
269 /* True if this field may contain pointers. */
270 unsigned int may_have_pointers
: 1;
272 /* True if this field has only restrict qualified pointers. */
273 unsigned int only_restrict_pointers
: 1;
275 /* True if this represents a global variable. */
276 unsigned int is_global_var
: 1;
278 /* True if this represents a IPA function info. */
279 unsigned int is_fn_info
: 1;
281 /* A link to the variable for the next field in this structure. */
282 struct variable_info
*next
;
284 /* Offset of this variable, in bits, from the base variable */
285 unsigned HOST_WIDE_INT offset
;
287 /* Size of the variable, in bits. */
288 unsigned HOST_WIDE_INT size
;
290 /* Full size of the base variable, in bits. */
291 unsigned HOST_WIDE_INT fullsize
;
293 /* Name of this variable */
296 /* Tree that this variable is associated with. */
299 /* Points-to set for this variable. */
302 /* Old points-to set for this variable. */
305 typedef struct variable_info
*varinfo_t
;
307 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
308 static varinfo_t
first_or_preceding_vi_for_offset (varinfo_t
,
309 unsigned HOST_WIDE_INT
);
310 static varinfo_t
lookup_vi_for_tree (tree
);
312 /* Pool of variable info structures. */
313 static alloc_pool variable_info_pool
;
315 DEF_VEC_P(varinfo_t
);
317 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
319 /* Table of variable info structures for constraint variables.
320 Indexed directly by variable info id. */
321 static VEC(varinfo_t
,heap
) *varmap
;
323 /* Return the varmap element N */
325 static inline varinfo_t
326 get_varinfo (unsigned int n
)
328 return VEC_index (varinfo_t
, varmap
, n
);
331 /* Static IDs for the special variables. */
332 enum { nothing_id
= 0, anything_id
= 1, readonly_id
= 2,
333 escaped_id
= 3, nonlocal_id
= 4,
334 storedanything_id
= 5, integer_id
= 6 };
336 struct GTY(()) heapvar_map
{
338 unsigned HOST_WIDE_INT offset
;
342 heapvar_map_eq (const void *p1
, const void *p2
)
344 const struct heapvar_map
*h1
= (const struct heapvar_map
*)p1
;
345 const struct heapvar_map
*h2
= (const struct heapvar_map
*)p2
;
346 return (h1
->map
.base
.from
== h2
->map
.base
.from
347 && h1
->offset
== h2
->offset
);
351 heapvar_map_hash (struct heapvar_map
*h
)
353 return iterative_hash_host_wide_int (h
->offset
,
354 htab_hash_pointer (h
->map
.base
.from
));
357 /* Lookup a heap var for FROM, and return it if we find one. */
360 heapvar_lookup (tree from
, unsigned HOST_WIDE_INT offset
)
362 struct heapvar_map
*h
, in
;
363 in
.map
.base
.from
= from
;
365 h
= (struct heapvar_map
*) htab_find_with_hash (heapvar_for_stmt
, &in
,
366 heapvar_map_hash (&in
));
372 /* Insert a mapping FROM->TO in the heap var for statement
376 heapvar_insert (tree from
, unsigned HOST_WIDE_INT offset
, tree to
)
378 struct heapvar_map
*h
;
381 h
= ggc_alloc_heapvar_map ();
382 h
->map
.base
.from
= from
;
384 h
->map
.hash
= heapvar_map_hash (h
);
386 loc
= htab_find_slot_with_hash (heapvar_for_stmt
, h
, h
->map
.hash
, INSERT
);
387 gcc_assert (*loc
== NULL
);
388 *(struct heapvar_map
**) loc
= h
;
391 /* Return a new variable info structure consisting for a variable
392 named NAME, and using constraint graph node NODE. Append it
393 to the vector of variable info structures. */
396 new_var_info (tree t
, const char *name
)
398 unsigned index
= VEC_length (varinfo_t
, varmap
);
399 varinfo_t ret
= (varinfo_t
) pool_alloc (variable_info_pool
);
404 /* Vars without decl are artificial and do not have sub-variables. */
405 ret
->is_artificial_var
= (t
== NULL_TREE
);
406 ret
->is_special_var
= false;
407 ret
->is_unknown_size_var
= false;
408 ret
->is_full_var
= (t
== NULL_TREE
);
409 ret
->is_heap_var
= false;
410 ret
->is_restrict_var
= false;
411 ret
->may_have_pointers
= true;
412 ret
->only_restrict_pointers
= false;
413 ret
->is_global_var
= (t
== NULL_TREE
);
414 ret
->is_fn_info
= false;
416 ret
->is_global_var
= is_global_var (t
);
417 ret
->solution
= BITMAP_ALLOC (&pta_obstack
);
418 ret
->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
423 VEC_safe_push (varinfo_t
, heap
, varmap
, ret
);
429 /* A map mapping call statements to per-stmt variables for uses
430 and clobbers specific to the call. */
431 struct pointer_map_t
*call_stmt_vars
;
433 /* Lookup or create the variable for the call statement CALL. */
436 get_call_vi (gimple call
)
441 slot_p
= pointer_map_insert (call_stmt_vars
, call
);
443 return (varinfo_t
) *slot_p
;
445 vi
= new_var_info (NULL_TREE
, "CALLUSED");
449 vi
->is_full_var
= true;
451 vi
->next
= vi2
= new_var_info (NULL_TREE
, "CALLCLOBBERED");
455 vi2
->is_full_var
= true;
457 *slot_p
= (void *) vi
;
461 /* Lookup the variable for the call statement CALL representing
462 the uses. Returns NULL if there is nothing special about this call. */
465 lookup_call_use_vi (gimple call
)
469 slot_p
= pointer_map_contains (call_stmt_vars
, call
);
471 return (varinfo_t
) *slot_p
;
476 /* Lookup the variable for the call statement CALL representing
477 the clobbers. Returns NULL if there is nothing special about this call. */
480 lookup_call_clobber_vi (gimple call
)
482 varinfo_t uses
= lookup_call_use_vi (call
);
489 /* Lookup or create the variable for the call statement CALL representing
493 get_call_use_vi (gimple call
)
495 return get_call_vi (call
);
498 /* Lookup or create the variable for the call statement CALL representing
501 static varinfo_t ATTRIBUTE_UNUSED
502 get_call_clobber_vi (gimple call
)
504 return get_call_vi (call
)->next
;
508 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
510 /* An expression that appears in a constraint. */
512 struct constraint_expr
514 /* Constraint type. */
515 constraint_expr_type type
;
517 /* Variable we are referring to in the constraint. */
520 /* Offset, in bits, of this constraint from the beginning of
521 variables it ends up referring to.
523 IOW, in a deref constraint, we would deref, get the result set,
524 then add OFFSET to each member. */
525 HOST_WIDE_INT offset
;
528 /* Use 0x8000... as special unknown offset. */
529 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
531 typedef struct constraint_expr ce_s
;
533 DEF_VEC_ALLOC_O(ce_s
, heap
);
534 static void get_constraint_for_1 (tree
, VEC(ce_s
, heap
) **, bool);
535 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
536 static void do_deref (VEC (ce_s
, heap
) **);
538 /* Our set constraints are made up of two constraint expressions, one
541 As described in the introduction, our set constraints each represent an
542 operation between set valued variables.
546 struct constraint_expr lhs
;
547 struct constraint_expr rhs
;
550 /* List of constraints that we use to build the constraint graph from. */
552 static VEC(constraint_t
,heap
) *constraints
;
553 static alloc_pool constraint_pool
;
555 /* The constraint graph is represented as an array of bitmaps
556 containing successor nodes. */
558 struct constraint_graph
560 /* Size of this graph, which may be different than the number of
561 nodes in the variable map. */
564 /* Explicit successors of each node. */
567 /* Implicit predecessors of each node (Used for variable
569 bitmap
*implicit_preds
;
571 /* Explicit predecessors of each node (Used for variable substitution). */
574 /* Indirect cycle representatives, or -1 if the node has no indirect
576 int *indirect_cycles
;
578 /* Representative node for a node. rep[a] == a unless the node has
582 /* Equivalence class representative for a label. This is used for
583 variable substitution. */
586 /* Pointer equivalence label for a node. All nodes with the same
587 pointer equivalence label can be unified together at some point
588 (either during constraint optimization or after the constraint
592 /* Pointer equivalence representative for a label. This is used to
593 handle nodes that are pointer equivalent but not location
594 equivalent. We can unite these once the addressof constraints
595 are transformed into initial points-to sets. */
598 /* Pointer equivalence label for each node, used during variable
600 unsigned int *pointer_label
;
602 /* Location equivalence label for each node, used during location
603 equivalence finding. */
604 unsigned int *loc_label
;
606 /* Pointed-by set for each node, used during location equivalence
607 finding. This is pointed-by rather than pointed-to, because it
608 is constructed using the predecessor graph. */
611 /* Points to sets for pointer equivalence. This is *not* the actual
612 points-to sets for nodes. */
615 /* Bitmap of nodes where the bit is set if the node is a direct
616 node. Used for variable substitution. */
617 sbitmap direct_nodes
;
619 /* Bitmap of nodes where the bit is set if the node is address
620 taken. Used for variable substitution. */
621 bitmap address_taken
;
623 /* Vector of complex constraints for each graph node. Complex
624 constraints are those involving dereferences or offsets that are
626 VEC(constraint_t
,heap
) **complex;
629 static constraint_graph_t graph
;
631 /* During variable substitution and the offline version of indirect
632 cycle finding, we create nodes to represent dereferences and
633 address taken constraints. These represent where these start and
635 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
636 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
638 /* Return the representative node for NODE, if NODE has been unioned
640 This function performs path compression along the way to finding
641 the representative. */
644 find (unsigned int node
)
646 gcc_assert (node
< graph
->size
);
647 if (graph
->rep
[node
] != node
)
648 return graph
->rep
[node
] = find (graph
->rep
[node
]);
652 /* Union the TO and FROM nodes to the TO nodes.
653 Note that at some point in the future, we may want to do
654 union-by-rank, in which case we are going to have to return the
655 node we unified to. */
658 unite (unsigned int to
, unsigned int from
)
660 gcc_assert (to
< graph
->size
&& from
< graph
->size
);
661 if (to
!= from
&& graph
->rep
[from
] != to
)
663 graph
->rep
[from
] = to
;
669 /* Create a new constraint consisting of LHS and RHS expressions. */
672 new_constraint (const struct constraint_expr lhs
,
673 const struct constraint_expr rhs
)
675 constraint_t ret
= (constraint_t
) pool_alloc (constraint_pool
);
681 /* Print out constraint C to FILE. */
684 dump_constraint (FILE *file
, constraint_t c
)
686 if (c
->lhs
.type
== ADDRESSOF
)
688 else if (c
->lhs
.type
== DEREF
)
690 fprintf (file
, "%s", get_varinfo (c
->lhs
.var
)->name
);
691 if (c
->lhs
.offset
== UNKNOWN_OFFSET
)
692 fprintf (file
, " + UNKNOWN");
693 else if (c
->lhs
.offset
!= 0)
694 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
695 fprintf (file
, " = ");
696 if (c
->rhs
.type
== ADDRESSOF
)
698 else if (c
->rhs
.type
== DEREF
)
700 fprintf (file
, "%s", get_varinfo (c
->rhs
.var
)->name
);
701 if (c
->rhs
.offset
== UNKNOWN_OFFSET
)
702 fprintf (file
, " + UNKNOWN");
703 else if (c
->rhs
.offset
!= 0)
704 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
705 fprintf (file
, "\n");
709 void debug_constraint (constraint_t
);
710 void debug_constraints (void);
711 void debug_constraint_graph (void);
712 void debug_solution_for_var (unsigned int);
713 void debug_sa_points_to_info (void);
715 /* Print out constraint C to stderr. */
718 debug_constraint (constraint_t c
)
720 dump_constraint (stderr
, c
);
723 /* Print out all constraints to FILE */
726 dump_constraints (FILE *file
, int from
)
730 for (i
= from
; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
731 dump_constraint (file
, c
);
734 /* Print out all constraints to stderr. */
737 debug_constraints (void)
739 dump_constraints (stderr
, 0);
742 /* Print out to FILE the edge in the constraint graph that is created by
743 constraint c. The edge may have a label, depending on the type of
744 constraint that it represents. If complex1, e.g: a = *b, then the label
745 is "=*", if complex2, e.g: *a = b, then the label is "*=", if
746 complex with an offset, e.g: a = b + 8, then the label is "+".
747 Otherwise the edge has no label. */
750 dump_constraint_edge (FILE *file
, constraint_t c
)
752 if (c
->rhs
.type
!= ADDRESSOF
)
754 const char *src
= get_varinfo (c
->rhs
.var
)->name
;
755 const char *dst
= get_varinfo (c
->lhs
.var
)->name
;
756 fprintf (file
, " \"%s\" -> \"%s\" ", src
, dst
);
757 /* Due to preprocessing of constraints, instructions like *a = *b are
758 illegal; thus, we do not have to handle such cases. */
759 if (c
->lhs
.type
== DEREF
)
760 fprintf (file
, " [ label=\"*=\" ] ;\n");
761 else if (c
->rhs
.type
== DEREF
)
762 fprintf (file
, " [ label=\"=*\" ] ;\n");
765 /* We must check the case where the constraint is an offset.
766 In this case, it is treated as a complex constraint. */
767 if (c
->rhs
.offset
!= c
->lhs
.offset
)
768 fprintf (file
, " [ label=\"+\" ] ;\n");
770 fprintf (file
, " ;\n");
775 /* Print the constraint graph in dot format. */
778 dump_constraint_graph (FILE *file
)
780 unsigned int i
=0, size
;
783 /* Only print the graph if it has already been initialized: */
787 /* Print the constraints used to produce the constraint graph. The
788 constraints will be printed as comments in the dot file: */
789 fprintf (file
, "\n\n/* Constraints used in the constraint graph:\n");
790 dump_constraints (file
, 0);
791 fprintf (file
, "*/\n");
793 /* Prints the header of the dot file: */
794 fprintf (file
, "\n\n// The constraint graph in dot format:\n");
795 fprintf (file
, "strict digraph {\n");
796 fprintf (file
, " node [\n shape = box\n ]\n");
797 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
798 fprintf (file
, "\n // List of nodes in the constraint graph:\n");
800 /* The next lines print the nodes in the graph. In order to get the
801 number of nodes in the graph, we must choose the minimum between the
802 vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
803 yet been initialized, then graph->size == 0, otherwise we must only
804 read nodes that have an entry in VEC (varinfo_t, varmap). */
805 size
= VEC_length (varinfo_t
, varmap
);
806 size
= size
< graph
->size
? size
: graph
->size
;
807 for (i
= 0; i
< size
; i
++)
809 const char *name
= get_varinfo (graph
->rep
[i
])->name
;
810 fprintf (file
, " \"%s\" ;\n", name
);
813 /* Go over the list of constraints printing the edges in the constraint
815 fprintf (file
, "\n // The constraint edges:\n");
816 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
818 dump_constraint_edge (file
, c
);
820 /* Prints the tail of the dot file. By now, only the closing bracket. */
821 fprintf (file
, "}\n\n\n");
824 /* Print out the constraint graph to stderr. */
827 debug_constraint_graph (void)
829 dump_constraint_graph (stderr
);
834 The solver is a simple worklist solver, that works on the following
837 sbitmap changed_nodes = all zeroes;
839 For each node that is not already collapsed:
841 set bit in changed nodes
843 while (changed_count > 0)
845 compute topological ordering for constraint graph
847 find and collapse cycles in the constraint graph (updating
848 changed if necessary)
850 for each node (n) in the graph in topological order:
853 Process each complex constraint associated with the node,
854 updating changed if necessary.
856 For each outgoing edge from n, propagate the solution from n to
857 the destination of the edge, updating changed as necessary.
861 /* Return true if two constraint expressions A and B are equal. */
864 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
866 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
869 /* Return true if constraint expression A is less than constraint expression
870 B. This is just arbitrary, but consistent, in order to give them an
874 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
876 if (a
.type
== b
.type
)
879 return a
.offset
< b
.offset
;
881 return a
.var
< b
.var
;
884 return a
.type
< b
.type
;
887 /* Return true if constraint A is less than constraint B. This is just
888 arbitrary, but consistent, in order to give them an ordering. */
891 constraint_less (const constraint_t a
, const constraint_t b
)
893 if (constraint_expr_less (a
->lhs
, b
->lhs
))
895 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
898 return constraint_expr_less (a
->rhs
, b
->rhs
);
901 /* Return true if two constraints A and B are equal. */
904 constraint_equal (struct constraint a
, struct constraint b
)
906 return constraint_expr_equal (a
.lhs
, b
.lhs
)
907 && constraint_expr_equal (a
.rhs
, b
.rhs
);
911 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
914 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
915 struct constraint lookfor
)
923 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
924 if (place
>= VEC_length (constraint_t
, vec
))
926 found
= VEC_index (constraint_t
, vec
, place
);
927 if (!constraint_equal (*found
, lookfor
))
932 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
935 constraint_set_union (VEC(constraint_t
,heap
) **to
,
936 VEC(constraint_t
,heap
) **from
)
941 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
943 if (constraint_vec_find (*to
, *c
) == NULL
)
945 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
947 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
952 /* Expands the solution in SET to all sub-fields of variables included.
953 Union the expanded result into RESULT. */
956 solution_set_expand (bitmap result
, bitmap set
)
962 /* In a first pass record all variables we need to add all
963 sub-fields off. This avoids quadratic behavior. */
964 EXECUTE_IF_SET_IN_BITMAP (set
, 0, j
, bi
)
966 varinfo_t v
= get_varinfo (j
);
967 if (v
->is_artificial_var
970 v
= lookup_vi_for_tree (v
->decl
);
972 vars
= BITMAP_ALLOC (NULL
);
973 bitmap_set_bit (vars
, v
->id
);
976 /* In the second pass now do the addition to the solution and
977 to speed up solving add it to the delta as well. */
980 EXECUTE_IF_SET_IN_BITMAP (vars
, 0, j
, bi
)
982 varinfo_t v
= get_varinfo (j
);
983 for (; v
!= NULL
; v
= v
->next
)
984 bitmap_set_bit (result
, v
->id
);
990 /* Take a solution set SET, add OFFSET to each member of the set, and
991 overwrite SET with the result when done. */
994 solution_set_add (bitmap set
, HOST_WIDE_INT offset
)
996 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
1000 /* If the offset is unknown we have to expand the solution to
1002 if (offset
== UNKNOWN_OFFSET
)
1004 solution_set_expand (set
, set
);
1008 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
1010 varinfo_t vi
= get_varinfo (i
);
1012 /* If this is a variable with just one field just set its bit
1014 if (vi
->is_artificial_var
1015 || vi
->is_unknown_size_var
1017 bitmap_set_bit (result
, i
);
1020 unsigned HOST_WIDE_INT fieldoffset
= vi
->offset
+ offset
;
1022 /* If the offset makes the pointer point to before the
1023 variable use offset zero for the field lookup. */
1025 && fieldoffset
> vi
->offset
)
1029 vi
= first_or_preceding_vi_for_offset (vi
, fieldoffset
);
1031 bitmap_set_bit (result
, vi
->id
);
1032 /* If the result is not exactly at fieldoffset include the next
1033 field as well. See get_constraint_for_ptr_offset for more
1035 if (vi
->offset
!= fieldoffset
1036 && vi
->next
!= NULL
)
1037 bitmap_set_bit (result
, vi
->next
->id
);
1041 bitmap_copy (set
, result
);
1042 BITMAP_FREE (result
);
1045 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
1049 set_union_with_increment (bitmap to
, bitmap from
, HOST_WIDE_INT inc
)
1052 return bitmap_ior_into (to
, from
);
1058 tmp
= BITMAP_ALLOC (&iteration_obstack
);
1059 bitmap_copy (tmp
, from
);
1060 solution_set_add (tmp
, inc
);
1061 res
= bitmap_ior_into (to
, tmp
);
1067 /* Insert constraint C into the list of complex constraints for graph
1071 insert_into_complex (constraint_graph_t graph
,
1072 unsigned int var
, constraint_t c
)
1074 VEC (constraint_t
, heap
) *complex = graph
->complex[var
];
1075 unsigned int place
= VEC_lower_bound (constraint_t
, complex, c
,
1078 /* Only insert constraints that do not already exist. */
1079 if (place
>= VEC_length (constraint_t
, complex)
1080 || !constraint_equal (*c
, *VEC_index (constraint_t
, complex, place
)))
1081 VEC_safe_insert (constraint_t
, heap
, graph
->complex[var
], place
, c
);
1085 /* Condense two variable nodes into a single variable node, by moving
1086 all associated info from SRC to TO. */
1089 merge_node_constraints (constraint_graph_t graph
, unsigned int to
,
1095 gcc_assert (find (from
) == to
);
1097 /* Move all complex constraints from src node into to node */
1098 for (i
= 0; VEC_iterate (constraint_t
, graph
->complex[from
], i
, c
); i
++)
1100 /* In complex constraints for node src, we may have either
1101 a = *src, and *src = a, or an offseted constraint which are
1102 always added to the rhs node's constraints. */
1104 if (c
->rhs
.type
== DEREF
)
1106 else if (c
->lhs
.type
== DEREF
)
1111 constraint_set_union (&graph
->complex[to
], &graph
->complex[from
]);
1112 VEC_free (constraint_t
, heap
, graph
->complex[from
]);
1113 graph
->complex[from
] = NULL
;
1117 /* Remove edges involving NODE from GRAPH. */
1120 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
1122 if (graph
->succs
[node
])
1123 BITMAP_FREE (graph
->succs
[node
]);
1126 /* Merge GRAPH nodes FROM and TO into node TO. */
1129 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1132 if (graph
->indirect_cycles
[from
] != -1)
1134 /* If we have indirect cycles with the from node, and we have
1135 none on the to node, the to node has indirect cycles from the
1136 from node now that they are unified.
1137 If indirect cycles exist on both, unify the nodes that they
1138 are in a cycle with, since we know they are in a cycle with
1140 if (graph
->indirect_cycles
[to
] == -1)
1141 graph
->indirect_cycles
[to
] = graph
->indirect_cycles
[from
];
1144 /* Merge all the successor edges. */
1145 if (graph
->succs
[from
])
1147 if (!graph
->succs
[to
])
1148 graph
->succs
[to
] = BITMAP_ALLOC (&pta_obstack
);
1149 bitmap_ior_into (graph
->succs
[to
],
1150 graph
->succs
[from
]);
1153 clear_edges_for_node (graph
, from
);
1157 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1158 it doesn't exist in the graph already. */
1161 add_implicit_graph_edge (constraint_graph_t graph
, unsigned int to
,
1167 if (!graph
->implicit_preds
[to
])
1168 graph
->implicit_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1170 if (bitmap_set_bit (graph
->implicit_preds
[to
], from
))
1171 stats
.num_implicit_edges
++;
1174 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1175 it doesn't exist in the graph already.
1176 Return false if the edge already existed, true otherwise. */
1179 add_pred_graph_edge (constraint_graph_t graph
, unsigned int to
,
1182 if (!graph
->preds
[to
])
1183 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1184 bitmap_set_bit (graph
->preds
[to
], from
);
1187 /* Add a graph edge to GRAPH, going from FROM to TO if
1188 it doesn't exist in the graph already.
1189 Return false if the edge already existed, true otherwise. */
1192 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1203 if (!graph
->succs
[from
])
1204 graph
->succs
[from
] = BITMAP_ALLOC (&pta_obstack
);
1205 if (bitmap_set_bit (graph
->succs
[from
], to
))
1208 if (to
< FIRST_REF_NODE
&& from
< FIRST_REF_NODE
)
1216 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1219 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
1222 return (graph
->succs
[dest
]
1223 && bitmap_bit_p (graph
->succs
[dest
], src
));
1226 /* Initialize the constraint graph structure to contain SIZE nodes. */
1229 init_graph (unsigned int size
)
1233 graph
= XCNEW (struct constraint_graph
);
1235 graph
->succs
= XCNEWVEC (bitmap
, graph
->size
);
1236 graph
->indirect_cycles
= XNEWVEC (int, graph
->size
);
1237 graph
->rep
= XNEWVEC (unsigned int, graph
->size
);
1238 graph
->complex = XCNEWVEC (VEC(constraint_t
, heap
) *, size
);
1239 graph
->pe
= XCNEWVEC (unsigned int, graph
->size
);
1240 graph
->pe_rep
= XNEWVEC (int, graph
->size
);
1242 for (j
= 0; j
< graph
->size
; j
++)
1245 graph
->pe_rep
[j
] = -1;
1246 graph
->indirect_cycles
[j
] = -1;
1250 /* Build the constraint graph, adding only predecessor edges right now. */
1253 build_pred_graph (void)
1259 graph
->implicit_preds
= XCNEWVEC (bitmap
, graph
->size
);
1260 graph
->preds
= XCNEWVEC (bitmap
, graph
->size
);
1261 graph
->pointer_label
= XCNEWVEC (unsigned int, graph
->size
);
1262 graph
->loc_label
= XCNEWVEC (unsigned int, graph
->size
);
1263 graph
->pointed_by
= XCNEWVEC (bitmap
, graph
->size
);
1264 graph
->points_to
= XCNEWVEC (bitmap
, graph
->size
);
1265 graph
->eq_rep
= XNEWVEC (int, graph
->size
);
1266 graph
->direct_nodes
= sbitmap_alloc (graph
->size
);
1267 graph
->address_taken
= BITMAP_ALLOC (&predbitmap_obstack
);
1268 sbitmap_zero (graph
->direct_nodes
);
1270 for (j
= 0; j
< FIRST_REF_NODE
; j
++)
1272 if (!get_varinfo (j
)->is_special_var
)
1273 SET_BIT (graph
->direct_nodes
, j
);
1276 for (j
= 0; j
< graph
->size
; j
++)
1277 graph
->eq_rep
[j
] = -1;
1279 for (j
= 0; j
< VEC_length (varinfo_t
, varmap
); j
++)
1280 graph
->indirect_cycles
[j
] = -1;
1282 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1284 struct constraint_expr lhs
= c
->lhs
;
1285 struct constraint_expr rhs
= c
->rhs
;
1286 unsigned int lhsvar
= lhs
.var
;
1287 unsigned int rhsvar
= rhs
.var
;
1289 if (lhs
.type
== DEREF
)
1292 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1293 add_pred_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1295 else if (rhs
.type
== DEREF
)
1298 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1299 add_pred_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1301 RESET_BIT (graph
->direct_nodes
, lhsvar
);
1303 else if (rhs
.type
== ADDRESSOF
)
1308 if (graph
->points_to
[lhsvar
] == NULL
)
1309 graph
->points_to
[lhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1310 bitmap_set_bit (graph
->points_to
[lhsvar
], rhsvar
);
1312 if (graph
->pointed_by
[rhsvar
] == NULL
)
1313 graph
->pointed_by
[rhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1314 bitmap_set_bit (graph
->pointed_by
[rhsvar
], lhsvar
);
1316 /* Implicitly, *x = y */
1317 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1319 /* All related variables are no longer direct nodes. */
1320 RESET_BIT (graph
->direct_nodes
, rhsvar
);
1321 v
= get_varinfo (rhsvar
);
1322 if (!v
->is_full_var
)
1324 v
= lookup_vi_for_tree (v
->decl
);
1327 RESET_BIT (graph
->direct_nodes
, v
->id
);
1332 bitmap_set_bit (graph
->address_taken
, rhsvar
);
1334 else if (lhsvar
> anything_id
1335 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1338 add_pred_graph_edge (graph
, lhsvar
, rhsvar
);
1339 /* Implicitly, *x = *y */
1340 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
,
1341 FIRST_REF_NODE
+ rhsvar
);
1343 else if (lhs
.offset
!= 0 || rhs
.offset
!= 0)
1345 if (rhs
.offset
!= 0)
1346 RESET_BIT (graph
->direct_nodes
, lhs
.var
);
1347 else if (lhs
.offset
!= 0)
1348 RESET_BIT (graph
->direct_nodes
, rhs
.var
);
1353 /* Build the constraint graph, adding successor edges. */
1356 build_succ_graph (void)
1361 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1363 struct constraint_expr lhs
;
1364 struct constraint_expr rhs
;
1365 unsigned int lhsvar
;
1366 unsigned int rhsvar
;
1373 lhsvar
= find (lhs
.var
);
1374 rhsvar
= find (rhs
.var
);
1376 if (lhs
.type
== DEREF
)
1378 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1379 add_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1381 else if (rhs
.type
== DEREF
)
1383 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1384 add_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1386 else if (rhs
.type
== ADDRESSOF
)
1389 gcc_assert (find (rhs
.var
) == rhs
.var
);
1390 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1392 else if (lhsvar
> anything_id
1393 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1395 add_graph_edge (graph
, lhsvar
, rhsvar
);
1399 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1400 receive pointers. */
1401 t
= find (storedanything_id
);
1402 for (i
= integer_id
+ 1; i
< FIRST_REF_NODE
; ++i
)
1404 if (!TEST_BIT (graph
->direct_nodes
, i
)
1405 && get_varinfo (i
)->may_have_pointers
)
1406 add_graph_edge (graph
, find (i
), t
);
1409 /* Everything stored to ANYTHING also potentially escapes. */
1410 add_graph_edge (graph
, find (escaped_id
), t
);
1414 /* Changed variables on the last iteration. */
1415 static unsigned int changed_count
;
1416 static sbitmap changed
;
1418 /* Strongly Connected Component visitation info. */
1425 unsigned int *node_mapping
;
1427 VEC(unsigned,heap
) *scc_stack
;
1431 /* Recursive routine to find strongly connected components in GRAPH.
1432 SI is the SCC info to store the information in, and N is the id of current
1433 graph node we are processing.
1435 This is Tarjan's strongly connected component finding algorithm, as
1436 modified by Nuutila to keep only non-root nodes on the stack.
1437 The algorithm can be found in "On finding the strongly connected
1438 connected components in a directed graph" by Esko Nuutila and Eljas
1439 Soisalon-Soininen, in Information Processing Letters volume 49,
1440 number 1, pages 9-14. */
1443 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1447 unsigned int my_dfs
;
1449 SET_BIT (si
->visited
, n
);
1450 si
->dfs
[n
] = si
->current_index
++;
1451 my_dfs
= si
->dfs
[n
];
1453 /* Visit all the successors. */
1454 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
1458 if (i
> LAST_REF_NODE
)
1462 if (TEST_BIT (si
->deleted
, w
))
1465 if (!TEST_BIT (si
->visited
, w
))
1466 scc_visit (graph
, si
, w
);
1468 unsigned int t
= find (w
);
1469 unsigned int nnode
= find (n
);
1470 gcc_assert (nnode
== n
);
1472 if (si
->dfs
[t
] < si
->dfs
[nnode
])
1473 si
->dfs
[n
] = si
->dfs
[t
];
1477 /* See if any components have been identified. */
1478 if (si
->dfs
[n
] == my_dfs
)
1480 if (VEC_length (unsigned, si
->scc_stack
) > 0
1481 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1483 bitmap scc
= BITMAP_ALLOC (NULL
);
1484 unsigned int lowest_node
;
1487 bitmap_set_bit (scc
, n
);
1489 while (VEC_length (unsigned, si
->scc_stack
) != 0
1490 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1492 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1494 bitmap_set_bit (scc
, w
);
1497 lowest_node
= bitmap_first_set_bit (scc
);
1498 gcc_assert (lowest_node
< FIRST_REF_NODE
);
1500 /* Collapse the SCC nodes into a single node, and mark the
1502 EXECUTE_IF_SET_IN_BITMAP (scc
, 0, i
, bi
)
1504 if (i
< FIRST_REF_NODE
)
1506 if (unite (lowest_node
, i
))
1507 unify_nodes (graph
, lowest_node
, i
, false);
1511 unite (lowest_node
, i
);
1512 graph
->indirect_cycles
[i
- FIRST_REF_NODE
] = lowest_node
;
1516 SET_BIT (si
->deleted
, n
);
1519 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1522 /* Unify node FROM into node TO, updating the changed count if
1523 necessary when UPDATE_CHANGED is true. */
1526 unify_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1527 bool update_changed
)
1530 gcc_assert (to
!= from
&& find (to
) == to
);
1531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1532 fprintf (dump_file
, "Unifying %s to %s\n",
1533 get_varinfo (from
)->name
,
1534 get_varinfo (to
)->name
);
1537 stats
.unified_vars_dynamic
++;
1539 stats
.unified_vars_static
++;
1541 merge_graph_nodes (graph
, to
, from
);
1542 merge_node_constraints (graph
, to
, from
);
1544 /* Mark TO as changed if FROM was changed. If TO was already marked
1545 as changed, decrease the changed count. */
1547 if (update_changed
&& TEST_BIT (changed
, from
))
1549 RESET_BIT (changed
, from
);
1550 if (!TEST_BIT (changed
, to
))
1551 SET_BIT (changed
, to
);
1554 gcc_assert (changed_count
> 0);
1558 if (get_varinfo (from
)->solution
)
1560 /* If the solution changes because of the merging, we need to mark
1561 the variable as changed. */
1562 if (bitmap_ior_into (get_varinfo (to
)->solution
,
1563 get_varinfo (from
)->solution
))
1565 if (update_changed
&& !TEST_BIT (changed
, to
))
1567 SET_BIT (changed
, to
);
1572 BITMAP_FREE (get_varinfo (from
)->solution
);
1573 BITMAP_FREE (get_varinfo (from
)->oldsolution
);
1575 if (stats
.iterations
> 0)
1577 BITMAP_FREE (get_varinfo (to
)->oldsolution
);
1578 get_varinfo (to
)->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
1581 if (valid_graph_edge (graph
, to
, to
))
1583 if (graph
->succs
[to
])
1584 bitmap_clear_bit (graph
->succs
[to
], to
);
1588 /* Information needed to compute the topological ordering of a graph. */
1592 /* sbitmap of visited nodes. */
1594 /* Array that stores the topological order of the graph, *in
1596 VEC(unsigned,heap
) *topo_order
;
1600 /* Initialize and return a topological info structure. */
1602 static struct topo_info
*
1603 init_topo_info (void)
1605 size_t size
= graph
->size
;
1606 struct topo_info
*ti
= XNEW (struct topo_info
);
1607 ti
->visited
= sbitmap_alloc (size
);
1608 sbitmap_zero (ti
->visited
);
1609 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1614 /* Free the topological sort info pointed to by TI. */
1617 free_topo_info (struct topo_info
*ti
)
1619 sbitmap_free (ti
->visited
);
1620 VEC_free (unsigned, heap
, ti
->topo_order
);
1624 /* Visit the graph in topological order, and store the order in the
1625 topo_info structure. */
1628 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1634 SET_BIT (ti
->visited
, n
);
1636 if (graph
->succs
[n
])
1637 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[n
], 0, j
, bi
)
1639 if (!TEST_BIT (ti
->visited
, j
))
1640 topo_visit (graph
, ti
, j
);
1643 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1646 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1647 starting solution for y. */
1650 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1653 unsigned int lhs
= c
->lhs
.var
;
1655 bitmap sol
= get_varinfo (lhs
)->solution
;
1658 HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1660 /* Our IL does not allow this. */
1661 gcc_assert (c
->lhs
.offset
== 0);
1663 /* If the solution of Y contains anything it is good enough to transfer
1665 if (bitmap_bit_p (delta
, anything_id
))
1667 flag
|= bitmap_set_bit (sol
, anything_id
);
1671 /* If we do not know at with offset the rhs is dereferenced compute
1672 the reachability set of DELTA, conservatively assuming it is
1673 dereferenced at all valid offsets. */
1674 if (roffset
== UNKNOWN_OFFSET
)
1676 solution_set_expand (delta
, delta
);
1677 /* No further offset processing is necessary. */
1681 /* For each variable j in delta (Sol(y)), add
1682 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1683 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1685 varinfo_t v
= get_varinfo (j
);
1686 HOST_WIDE_INT fieldoffset
= v
->offset
+ roffset
;
1690 fieldoffset
= v
->offset
;
1691 else if (roffset
!= 0)
1692 v
= first_vi_for_offset (v
, fieldoffset
);
1693 /* If the access is outside of the variable we can ignore it. */
1701 /* Adding edges from the special vars is pointless.
1702 They don't have sets that can change. */
1703 if (get_varinfo (t
)->is_special_var
)
1704 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1705 /* Merging the solution from ESCAPED needlessly increases
1706 the set. Use ESCAPED as representative instead. */
1707 else if (v
->id
== escaped_id
)
1708 flag
|= bitmap_set_bit (sol
, escaped_id
);
1709 else if (v
->may_have_pointers
1710 && add_graph_edge (graph
, lhs
, t
))
1711 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1713 /* If the variable is not exactly at the requested offset
1714 we have to include the next one. */
1715 if (v
->offset
== (unsigned HOST_WIDE_INT
)fieldoffset
1720 fieldoffset
= v
->offset
;
1726 /* If the LHS solution changed, mark the var as changed. */
1729 get_varinfo (lhs
)->solution
= sol
;
1730 if (!TEST_BIT (changed
, lhs
))
1732 SET_BIT (changed
, lhs
);
1738 /* Process a constraint C that represents *(x + off) = y using DELTA
1739 as the starting solution for x. */
1742 do_ds_constraint (constraint_t c
, bitmap delta
)
1744 unsigned int rhs
= c
->rhs
.var
;
1745 bitmap sol
= get_varinfo (rhs
)->solution
;
1748 HOST_WIDE_INT loff
= c
->lhs
.offset
;
1749 bool escaped_p
= false;
1751 /* Our IL does not allow this. */
1752 gcc_assert (c
->rhs
.offset
== 0);
1754 /* If the solution of y contains ANYTHING simply use the ANYTHING
1755 solution. This avoids needlessly increasing the points-to sets. */
1756 if (bitmap_bit_p (sol
, anything_id
))
1757 sol
= get_varinfo (find (anything_id
))->solution
;
1759 /* If the solution for x contains ANYTHING we have to merge the
1760 solution of y into all pointer variables which we do via
1762 if (bitmap_bit_p (delta
, anything_id
))
1764 unsigned t
= find (storedanything_id
);
1765 if (add_graph_edge (graph
, t
, rhs
))
1767 if (bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1769 if (!TEST_BIT (changed
, t
))
1771 SET_BIT (changed
, t
);
1779 /* If we do not know at with offset the rhs is dereferenced compute
1780 the reachability set of DELTA, conservatively assuming it is
1781 dereferenced at all valid offsets. */
1782 if (loff
== UNKNOWN_OFFSET
)
1784 solution_set_expand (delta
, delta
);
1788 /* For each member j of delta (Sol(x)), add an edge from y to j and
1789 union Sol(y) into Sol(j) */
1790 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1792 varinfo_t v
= get_varinfo (j
);
1794 HOST_WIDE_INT fieldoffset
= v
->offset
+ loff
;
1797 fieldoffset
= v
->offset
;
1799 v
= first_vi_for_offset (v
, fieldoffset
);
1800 /* If the access is outside of the variable we can ignore it. */
1806 if (v
->may_have_pointers
)
1808 /* If v is a global variable then this is an escape point. */
1809 if (v
->is_global_var
1812 t
= find (escaped_id
);
1813 if (add_graph_edge (graph
, t
, rhs
)
1814 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
)
1815 && !TEST_BIT (changed
, t
))
1817 SET_BIT (changed
, t
);
1820 /* Enough to let rhs escape once. */
1824 if (v
->is_special_var
)
1828 if (add_graph_edge (graph
, t
, rhs
)
1829 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
)
1830 && !TEST_BIT (changed
, t
))
1832 SET_BIT (changed
, t
);
1837 /* If the variable is not exactly at the requested offset
1838 we have to include the next one. */
1839 if (v
->offset
== (unsigned HOST_WIDE_INT
)fieldoffset
1844 fieldoffset
= v
->offset
;
1850 /* Handle a non-simple (simple meaning requires no iteration),
1851 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1854 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1856 if (c
->lhs
.type
== DEREF
)
1858 if (c
->rhs
.type
== ADDRESSOF
)
1865 do_ds_constraint (c
, delta
);
1868 else if (c
->rhs
.type
== DEREF
)
1871 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1872 do_sd_constraint (graph
, c
, delta
);
1880 gcc_assert (c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
);
1881 solution
= get_varinfo (c
->rhs
.var
)->solution
;
1882 tmp
= get_varinfo (c
->lhs
.var
)->solution
;
1884 flag
= set_union_with_increment (tmp
, solution
, c
->rhs
.offset
);
1888 get_varinfo (c
->lhs
.var
)->solution
= tmp
;
1889 if (!TEST_BIT (changed
, c
->lhs
.var
))
1891 SET_BIT (changed
, c
->lhs
.var
);
1898 /* Initialize and return a new SCC info structure. */
1900 static struct scc_info
*
1901 init_scc_info (size_t size
)
1903 struct scc_info
*si
= XNEW (struct scc_info
);
1906 si
->current_index
= 0;
1907 si
->visited
= sbitmap_alloc (size
);
1908 sbitmap_zero (si
->visited
);
1909 si
->deleted
= sbitmap_alloc (size
);
1910 sbitmap_zero (si
->deleted
);
1911 si
->node_mapping
= XNEWVEC (unsigned int, size
);
1912 si
->dfs
= XCNEWVEC (unsigned int, size
);
1914 for (i
= 0; i
< size
; i
++)
1915 si
->node_mapping
[i
] = i
;
1917 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1921 /* Free an SCC info structure pointed to by SI */
1924 free_scc_info (struct scc_info
*si
)
1926 sbitmap_free (si
->visited
);
1927 sbitmap_free (si
->deleted
);
1928 free (si
->node_mapping
);
1930 VEC_free (unsigned, heap
, si
->scc_stack
);
1935 /* Find indirect cycles in GRAPH that occur, using strongly connected
1936 components, and note them in the indirect cycles map.
1938 This technique comes from Ben Hardekopf and Calvin Lin,
1939 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1940 Lines of Code", submitted to PLDI 2007. */
1943 find_indirect_cycles (constraint_graph_t graph
)
1946 unsigned int size
= graph
->size
;
1947 struct scc_info
*si
= init_scc_info (size
);
1949 for (i
= 0; i
< MIN (LAST_REF_NODE
, size
); i
++ )
1950 if (!TEST_BIT (si
->visited
, i
) && find (i
) == i
)
1951 scc_visit (graph
, si
, i
);
1956 /* Compute a topological ordering for GRAPH, and store the result in the
1957 topo_info structure TI. */
1960 compute_topo_order (constraint_graph_t graph
,
1961 struct topo_info
*ti
)
1964 unsigned int size
= graph
->size
;
1966 for (i
= 0; i
!= size
; ++i
)
1967 if (!TEST_BIT (ti
->visited
, i
) && find (i
) == i
)
1968 topo_visit (graph
, ti
, i
);
1971 /* Structure used to for hash value numbering of pointer equivalence
1974 typedef struct equiv_class_label
1977 unsigned int equivalence_class
;
1979 } *equiv_class_label_t
;
1980 typedef const struct equiv_class_label
*const_equiv_class_label_t
;
1982 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1984 static htab_t pointer_equiv_class_table
;
1986 /* A hashtable for mapping a bitmap of labels->location equivalence
1988 static htab_t location_equiv_class_table
;
1990 /* Hash function for a equiv_class_label_t */
1993 equiv_class_label_hash (const void *p
)
1995 const_equiv_class_label_t
const ecl
= (const_equiv_class_label_t
) p
;
1996 return ecl
->hashcode
;
1999 /* Equality function for two equiv_class_label_t's. */
2002 equiv_class_label_eq (const void *p1
, const void *p2
)
2004 const_equiv_class_label_t
const eql1
= (const_equiv_class_label_t
) p1
;
2005 const_equiv_class_label_t
const eql2
= (const_equiv_class_label_t
) p2
;
2006 return (eql1
->hashcode
== eql2
->hashcode
2007 && bitmap_equal_p (eql1
->labels
, eql2
->labels
));
2010 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
2014 equiv_class_lookup (htab_t table
, bitmap labels
)
2017 struct equiv_class_label ecl
;
2019 ecl
.labels
= labels
;
2020 ecl
.hashcode
= bitmap_hash (labels
);
2022 slot
= htab_find_slot_with_hash (table
, &ecl
,
2023 ecl
.hashcode
, NO_INSERT
);
2027 return ((equiv_class_label_t
) *slot
)->equivalence_class
;
2031 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
2035 equiv_class_add (htab_t table
, unsigned int equivalence_class
,
2039 equiv_class_label_t ecl
= XNEW (struct equiv_class_label
);
2041 ecl
->labels
= labels
;
2042 ecl
->equivalence_class
= equivalence_class
;
2043 ecl
->hashcode
= bitmap_hash (labels
);
2045 slot
= htab_find_slot_with_hash (table
, ecl
,
2046 ecl
->hashcode
, INSERT
);
2047 gcc_assert (!*slot
);
2048 *slot
= (void *) ecl
;
2051 /* Perform offline variable substitution.
2053 This is a worst case quadratic time way of identifying variables
2054 that must have equivalent points-to sets, including those caused by
2055 static cycles, and single entry subgraphs, in the constraint graph.
2057 The technique is described in "Exploiting Pointer and Location
2058 Equivalence to Optimize Pointer Analysis. In the 14th International
2059 Static Analysis Symposium (SAS), August 2007." It is known as the
2060 "HU" algorithm, and is equivalent to value numbering the collapsed
2061 constraint graph including evaluating unions.
2063 The general method of finding equivalence classes is as follows:
2064 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
2065 Initialize all non-REF nodes to be direct nodes.
2066 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
2068 For each constraint containing the dereference, we also do the same
2071 We then compute SCC's in the graph and unify nodes in the same SCC,
2074 For each non-collapsed node x:
2075 Visit all unvisited explicit incoming edges.
2076 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
2078 Lookup the equivalence class for pts(x).
2079 If we found one, equivalence_class(x) = found class.
2080 Otherwise, equivalence_class(x) = new class, and new_class is
2081 added to the lookup table.
2083 All direct nodes with the same equivalence class can be replaced
2084 with a single representative node.
2085 All unlabeled nodes (label == 0) are not pointers and all edges
2086 involving them can be eliminated.
2087 We perform these optimizations during rewrite_constraints
2089 In addition to pointer equivalence class finding, we also perform
2090 location equivalence class finding. This is the set of variables
2091 that always appear together in points-to sets. We use this to
2092 compress the size of the points-to sets. */
2094 /* Current maximum pointer equivalence class id. */
2095 static int pointer_equiv_class
;
2097 /* Current maximum location equivalence class id. */
2098 static int location_equiv_class
;
2100 /* Recursive routine to find strongly connected components in GRAPH,
2101 and label it's nodes with DFS numbers. */
2104 condense_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2108 unsigned int my_dfs
;
2110 gcc_assert (si
->node_mapping
[n
] == n
);
2111 SET_BIT (si
->visited
, n
);
2112 si
->dfs
[n
] = si
->current_index
++;
2113 my_dfs
= si
->dfs
[n
];
2115 /* Visit all the successors. */
2116 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2118 unsigned int w
= si
->node_mapping
[i
];
2120 if (TEST_BIT (si
->deleted
, w
))
2123 if (!TEST_BIT (si
->visited
, w
))
2124 condense_visit (graph
, si
, w
);
2126 unsigned int t
= si
->node_mapping
[w
];
2127 unsigned int nnode
= si
->node_mapping
[n
];
2128 gcc_assert (nnode
== n
);
2130 if (si
->dfs
[t
] < si
->dfs
[nnode
])
2131 si
->dfs
[n
] = si
->dfs
[t
];
2135 /* Visit all the implicit predecessors. */
2136 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->implicit_preds
[n
], 0, i
, bi
)
2138 unsigned int w
= si
->node_mapping
[i
];
2140 if (TEST_BIT (si
->deleted
, w
))
2143 if (!TEST_BIT (si
->visited
, w
))
2144 condense_visit (graph
, si
, w
);
2146 unsigned int t
= si
->node_mapping
[w
];
2147 unsigned int nnode
= si
->node_mapping
[n
];
2148 gcc_assert (nnode
== n
);
2150 if (si
->dfs
[t
] < si
->dfs
[nnode
])
2151 si
->dfs
[n
] = si
->dfs
[t
];
2155 /* See if any components have been identified. */
2156 if (si
->dfs
[n
] == my_dfs
)
2158 while (VEC_length (unsigned, si
->scc_stack
) != 0
2159 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
2161 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
2162 si
->node_mapping
[w
] = n
;
2164 if (!TEST_BIT (graph
->direct_nodes
, w
))
2165 RESET_BIT (graph
->direct_nodes
, n
);
2167 /* Unify our nodes. */
2168 if (graph
->preds
[w
])
2170 if (!graph
->preds
[n
])
2171 graph
->preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2172 bitmap_ior_into (graph
->preds
[n
], graph
->preds
[w
]);
2174 if (graph
->implicit_preds
[w
])
2176 if (!graph
->implicit_preds
[n
])
2177 graph
->implicit_preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2178 bitmap_ior_into (graph
->implicit_preds
[n
],
2179 graph
->implicit_preds
[w
]);
2181 if (graph
->points_to
[w
])
2183 if (!graph
->points_to
[n
])
2184 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2185 bitmap_ior_into (graph
->points_to
[n
],
2186 graph
->points_to
[w
]);
2189 SET_BIT (si
->deleted
, n
);
2192 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
2195 /* Label pointer equivalences. */
2198 label_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2202 SET_BIT (si
->visited
, n
);
2204 if (!graph
->points_to
[n
])
2205 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2207 /* Label and union our incoming edges's points to sets. */
2208 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2210 unsigned int w
= si
->node_mapping
[i
];
2211 if (!TEST_BIT (si
->visited
, w
))
2212 label_visit (graph
, si
, w
);
2214 /* Skip unused edges */
2215 if (w
== n
|| graph
->pointer_label
[w
] == 0)
2218 if (graph
->points_to
[w
])
2219 bitmap_ior_into(graph
->points_to
[n
], graph
->points_to
[w
]);
2221 /* Indirect nodes get fresh variables. */
2222 if (!TEST_BIT (graph
->direct_nodes
, n
))
2223 bitmap_set_bit (graph
->points_to
[n
], FIRST_REF_NODE
+ n
);
2225 if (!bitmap_empty_p (graph
->points_to
[n
]))
2227 unsigned int label
= equiv_class_lookup (pointer_equiv_class_table
,
2228 graph
->points_to
[n
]);
2231 label
= pointer_equiv_class
++;
2232 equiv_class_add (pointer_equiv_class_table
,
2233 label
, graph
->points_to
[n
]);
2235 graph
->pointer_label
[n
] = label
;
2239 /* Perform offline variable substitution, discovering equivalence
2240 classes, and eliminating non-pointer variables. */
2242 static struct scc_info
*
2243 perform_var_substitution (constraint_graph_t graph
)
2246 unsigned int size
= graph
->size
;
2247 struct scc_info
*si
= init_scc_info (size
);
2249 bitmap_obstack_initialize (&iteration_obstack
);
2250 pointer_equiv_class_table
= htab_create (511, equiv_class_label_hash
,
2251 equiv_class_label_eq
, free
);
2252 location_equiv_class_table
= htab_create (511, equiv_class_label_hash
,
2253 equiv_class_label_eq
, free
);
2254 pointer_equiv_class
= 1;
2255 location_equiv_class
= 1;
2257 /* Condense the nodes, which means to find SCC's, count incoming
2258 predecessors, and unite nodes in SCC's. */
2259 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2260 if (!TEST_BIT (si
->visited
, si
->node_mapping
[i
]))
2261 condense_visit (graph
, si
, si
->node_mapping
[i
]);
2263 sbitmap_zero (si
->visited
);
2264 /* Actually the label the nodes for pointer equivalences */
2265 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2266 if (!TEST_BIT (si
->visited
, si
->node_mapping
[i
]))
2267 label_visit (graph
, si
, si
->node_mapping
[i
]);
2269 /* Calculate location equivalence labels. */
2270 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2277 if (!graph
->pointed_by
[i
])
2279 pointed_by
= BITMAP_ALLOC (&iteration_obstack
);
2281 /* Translate the pointed-by mapping for pointer equivalence
2283 EXECUTE_IF_SET_IN_BITMAP (graph
->pointed_by
[i
], 0, j
, bi
)
2285 bitmap_set_bit (pointed_by
,
2286 graph
->pointer_label
[si
->node_mapping
[j
]]);
2288 /* The original pointed_by is now dead. */
2289 BITMAP_FREE (graph
->pointed_by
[i
]);
2291 /* Look up the location equivalence label if one exists, or make
2293 label
= equiv_class_lookup (location_equiv_class_table
,
2297 label
= location_equiv_class
++;
2298 equiv_class_add (location_equiv_class_table
,
2303 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2304 fprintf (dump_file
, "Found location equivalence for node %s\n",
2305 get_varinfo (i
)->name
);
2306 BITMAP_FREE (pointed_by
);
2308 graph
->loc_label
[i
] = label
;
2312 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2313 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2315 bool direct_node
= TEST_BIT (graph
->direct_nodes
, i
);
2317 "Equivalence classes for %s node id %d:%s are pointer: %d"
2319 direct_node
? "Direct node" : "Indirect node", i
,
2320 get_varinfo (i
)->name
,
2321 graph
->pointer_label
[si
->node_mapping
[i
]],
2322 graph
->loc_label
[si
->node_mapping
[i
]]);
2325 /* Quickly eliminate our non-pointer variables. */
2327 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2329 unsigned int node
= si
->node_mapping
[i
];
2331 if (graph
->pointer_label
[node
] == 0)
2333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2335 "%s is a non-pointer variable, eliminating edges.\n",
2336 get_varinfo (node
)->name
);
2337 stats
.nonpointer_vars
++;
2338 clear_edges_for_node (graph
, node
);
2345 /* Free information that was only necessary for variable
2349 free_var_substitution_info (struct scc_info
*si
)
2352 free (graph
->pointer_label
);
2353 free (graph
->loc_label
);
2354 free (graph
->pointed_by
);
2355 free (graph
->points_to
);
2356 free (graph
->eq_rep
);
2357 sbitmap_free (graph
->direct_nodes
);
2358 htab_delete (pointer_equiv_class_table
);
2359 htab_delete (location_equiv_class_table
);
2360 bitmap_obstack_release (&iteration_obstack
);
2363 /* Return an existing node that is equivalent to NODE, which has
2364 equivalence class LABEL, if one exists. Return NODE otherwise. */
2367 find_equivalent_node (constraint_graph_t graph
,
2368 unsigned int node
, unsigned int label
)
2370 /* If the address version of this variable is unused, we can
2371 substitute it for anything else with the same label.
2372 Otherwise, we know the pointers are equivalent, but not the
2373 locations, and we can unite them later. */
2375 if (!bitmap_bit_p (graph
->address_taken
, node
))
2377 gcc_assert (label
< graph
->size
);
2379 if (graph
->eq_rep
[label
] != -1)
2381 /* Unify the two variables since we know they are equivalent. */
2382 if (unite (graph
->eq_rep
[label
], node
))
2383 unify_nodes (graph
, graph
->eq_rep
[label
], node
, false);
2384 return graph
->eq_rep
[label
];
2388 graph
->eq_rep
[label
] = node
;
2389 graph
->pe_rep
[label
] = node
;
2394 gcc_assert (label
< graph
->size
);
2395 graph
->pe
[node
] = label
;
2396 if (graph
->pe_rep
[label
] == -1)
2397 graph
->pe_rep
[label
] = node
;
2403 /* Unite pointer equivalent but not location equivalent nodes in
2404 GRAPH. This may only be performed once variable substitution is
2408 unite_pointer_equivalences (constraint_graph_t graph
)
2412 /* Go through the pointer equivalences and unite them to their
2413 representative, if they aren't already. */
2414 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2416 unsigned int label
= graph
->pe
[i
];
2419 int label_rep
= graph
->pe_rep
[label
];
2421 if (label_rep
== -1)
2424 label_rep
= find (label_rep
);
2425 if (label_rep
>= 0 && unite (label_rep
, find (i
)))
2426 unify_nodes (graph
, label_rep
, i
, false);
2431 /* Move complex constraints to the GRAPH nodes they belong to. */
2434 move_complex_constraints (constraint_graph_t graph
)
2439 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
2443 struct constraint_expr lhs
= c
->lhs
;
2444 struct constraint_expr rhs
= c
->rhs
;
2446 if (lhs
.type
== DEREF
)
2448 insert_into_complex (graph
, lhs
.var
, c
);
2450 else if (rhs
.type
== DEREF
)
2452 if (!(get_varinfo (lhs
.var
)->is_special_var
))
2453 insert_into_complex (graph
, rhs
.var
, c
);
2455 else if (rhs
.type
!= ADDRESSOF
&& lhs
.var
> anything_id
2456 && (lhs
.offset
!= 0 || rhs
.offset
!= 0))
2458 insert_into_complex (graph
, rhs
.var
, c
);
2465 /* Optimize and rewrite complex constraints while performing
2466 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2467 result of perform_variable_substitution. */
2470 rewrite_constraints (constraint_graph_t graph
,
2471 struct scc_info
*si
)
2477 for (j
= 0; j
< graph
->size
; j
++)
2478 gcc_assert (find (j
) == j
);
2480 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
2482 struct constraint_expr lhs
= c
->lhs
;
2483 struct constraint_expr rhs
= c
->rhs
;
2484 unsigned int lhsvar
= find (lhs
.var
);
2485 unsigned int rhsvar
= find (rhs
.var
);
2486 unsigned int lhsnode
, rhsnode
;
2487 unsigned int lhslabel
, rhslabel
;
2489 lhsnode
= si
->node_mapping
[lhsvar
];
2490 rhsnode
= si
->node_mapping
[rhsvar
];
2491 lhslabel
= graph
->pointer_label
[lhsnode
];
2492 rhslabel
= graph
->pointer_label
[rhsnode
];
2494 /* See if it is really a non-pointer variable, and if so, ignore
2498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2501 fprintf (dump_file
, "%s is a non-pointer variable,"
2502 "ignoring constraint:",
2503 get_varinfo (lhs
.var
)->name
);
2504 dump_constraint (dump_file
, c
);
2506 VEC_replace (constraint_t
, constraints
, i
, NULL
);
2512 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2515 fprintf (dump_file
, "%s is a non-pointer variable,"
2516 "ignoring constraint:",
2517 get_varinfo (rhs
.var
)->name
);
2518 dump_constraint (dump_file
, c
);
2520 VEC_replace (constraint_t
, constraints
, i
, NULL
);
2524 lhsvar
= find_equivalent_node (graph
, lhsvar
, lhslabel
);
2525 rhsvar
= find_equivalent_node (graph
, rhsvar
, rhslabel
);
2526 c
->lhs
.var
= lhsvar
;
2527 c
->rhs
.var
= rhsvar
;
2532 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2533 part of an SCC, false otherwise. */
2536 eliminate_indirect_cycles (unsigned int node
)
2538 if (graph
->indirect_cycles
[node
] != -1
2539 && !bitmap_empty_p (get_varinfo (node
)->solution
))
2542 VEC(unsigned,heap
) *queue
= NULL
;
2544 unsigned int to
= find (graph
->indirect_cycles
[node
]);
2547 /* We can't touch the solution set and call unify_nodes
2548 at the same time, because unify_nodes is going to do
2549 bitmap unions into it. */
2551 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node
)->solution
, 0, i
, bi
)
2553 if (find (i
) == i
&& i
!= to
)
2556 VEC_safe_push (unsigned, heap
, queue
, i
);
2561 VEC_iterate (unsigned, queue
, queuepos
, i
);
2564 unify_nodes (graph
, to
, i
, true);
2566 VEC_free (unsigned, heap
, queue
);
2572 /* Solve the constraint graph GRAPH using our worklist solver.
2573 This is based on the PW* family of solvers from the "Efficient Field
2574 Sensitive Pointer Analysis for C" paper.
2575 It works by iterating over all the graph nodes, processing the complex
2576 constraints and propagating the copy constraints, until everything stops
2577 changed. This corresponds to steps 6-8 in the solving list given above. */
2580 solve_graph (constraint_graph_t graph
)
2582 unsigned int size
= graph
->size
;
2587 changed
= sbitmap_alloc (size
);
2588 sbitmap_zero (changed
);
2590 /* Mark all initial non-collapsed nodes as changed. */
2591 for (i
= 0; i
< size
; i
++)
2593 varinfo_t ivi
= get_varinfo (i
);
2594 if (find (i
) == i
&& !bitmap_empty_p (ivi
->solution
)
2595 && ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
2596 || VEC_length (constraint_t
, graph
->complex[i
]) > 0))
2598 SET_BIT (changed
, i
);
2603 /* Allocate a bitmap to be used to store the changed bits. */
2604 pts
= BITMAP_ALLOC (&pta_obstack
);
2606 while (changed_count
> 0)
2609 struct topo_info
*ti
= init_topo_info ();
2612 bitmap_obstack_initialize (&iteration_obstack
);
2614 compute_topo_order (graph
, ti
);
2616 while (VEC_length (unsigned, ti
->topo_order
) != 0)
2619 i
= VEC_pop (unsigned, ti
->topo_order
);
2621 /* If this variable is not a representative, skip it. */
2625 /* In certain indirect cycle cases, we may merge this
2626 variable to another. */
2627 if (eliminate_indirect_cycles (i
) && find (i
) != i
)
2630 /* If the node has changed, we need to process the
2631 complex constraints and outgoing edges again. */
2632 if (TEST_BIT (changed
, i
))
2637 VEC(constraint_t
,heap
) *complex = graph
->complex[i
];
2638 bool solution_empty
;
2640 RESET_BIT (changed
, i
);
2643 /* Compute the changed set of solution bits. */
2644 bitmap_and_compl (pts
, get_varinfo (i
)->solution
,
2645 get_varinfo (i
)->oldsolution
);
2647 if (bitmap_empty_p (pts
))
2650 bitmap_ior_into (get_varinfo (i
)->oldsolution
, pts
);
2652 solution
= get_varinfo (i
)->solution
;
2653 solution_empty
= bitmap_empty_p (solution
);
2655 /* Process the complex constraints */
2656 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
2658 /* XXX: This is going to unsort the constraints in
2659 some cases, which will occasionally add duplicate
2660 constraints during unification. This does not
2661 affect correctness. */
2662 c
->lhs
.var
= find (c
->lhs
.var
);
2663 c
->rhs
.var
= find (c
->rhs
.var
);
2665 /* The only complex constraint that can change our
2666 solution to non-empty, given an empty solution,
2667 is a constraint where the lhs side is receiving
2668 some set from elsewhere. */
2669 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2670 do_complex_constraint (graph
, c
, pts
);
2673 solution_empty
= bitmap_empty_p (solution
);
2675 if (!solution_empty
)
2678 unsigned eff_escaped_id
= find (escaped_id
);
2680 /* Propagate solution to all successors. */
2681 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
2687 unsigned int to
= find (j
);
2688 tmp
= get_varinfo (to
)->solution
;
2691 /* Don't try to propagate to ourselves. */
2695 /* If we propagate from ESCAPED use ESCAPED as
2697 if (i
== eff_escaped_id
)
2698 flag
= bitmap_set_bit (tmp
, escaped_id
);
2700 flag
= set_union_with_increment (tmp
, pts
, 0);
2704 get_varinfo (to
)->solution
= tmp
;
2705 if (!TEST_BIT (changed
, to
))
2707 SET_BIT (changed
, to
);
2715 free_topo_info (ti
);
2716 bitmap_obstack_release (&iteration_obstack
);
2720 sbitmap_free (changed
);
2721 bitmap_obstack_release (&oldpta_obstack
);
2724 /* Map from trees to variable infos. */
2725 static struct pointer_map_t
*vi_for_tree
;
2728 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2731 insert_vi_for_tree (tree t
, varinfo_t vi
)
2733 void **slot
= pointer_map_insert (vi_for_tree
, t
);
2735 gcc_assert (*slot
== NULL
);
2739 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2740 exist in the map, return NULL, otherwise, return the varinfo we found. */
2743 lookup_vi_for_tree (tree t
)
2745 void **slot
= pointer_map_contains (vi_for_tree
, t
);
2749 return (varinfo_t
) *slot
;
2752 /* Return a printable name for DECL */
2755 alias_get_name (tree decl
)
2759 int num_printed
= 0;
2761 if (DECL_ASSEMBLER_NAME_SET_P (decl
))
2762 res
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
2764 res
= get_name (decl
);
2772 if (TREE_CODE (decl
) == SSA_NAME
)
2774 num_printed
= asprintf (&temp
, "%s_%u",
2775 alias_get_name (SSA_NAME_VAR (decl
)),
2776 SSA_NAME_VERSION (decl
));
2778 else if (DECL_P (decl
))
2780 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2782 if (num_printed
> 0)
2784 res
= ggc_strdup (temp
);
2790 /* Find the variable id for tree T in the map.
2791 If T doesn't exist in the map, create an entry for it and return it. */
2794 get_vi_for_tree (tree t
)
2796 void **slot
= pointer_map_contains (vi_for_tree
, t
);
2798 return get_varinfo (create_variable_info_for (t
, alias_get_name (t
)));
2800 return (varinfo_t
) *slot
;
2803 /* Get a scalar constraint expression for a new temporary variable. */
2805 static struct constraint_expr
2806 new_scalar_tmp_constraint_exp (const char *name
)
2808 struct constraint_expr tmp
;
2811 vi
= new_var_info (NULL_TREE
, name
);
2815 vi
->is_full_var
= 1;
2824 /* Get a constraint expression vector from an SSA_VAR_P node.
2825 If address_p is true, the result will be taken its address of. */
2828 get_constraint_for_ssa_var (tree t
, VEC(ce_s
, heap
) **results
, bool address_p
)
2830 struct constraint_expr cexpr
;
2833 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2834 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
2836 /* For parameters, get at the points-to set for the actual parm
2838 if (TREE_CODE (t
) == SSA_NAME
2839 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2840 && SSA_NAME_IS_DEFAULT_DEF (t
))
2842 get_constraint_for_ssa_var (SSA_NAME_VAR (t
), results
, address_p
);
2846 vi
= get_vi_for_tree (t
);
2848 cexpr
.type
= SCALAR
;
2850 /* If we determine the result is "anything", and we know this is readonly,
2851 say it points to readonly memory instead. */
2852 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
2855 cexpr
.type
= ADDRESSOF
;
2856 cexpr
.var
= readonly_id
;
2859 /* If we are not taking the address of the constraint expr, add all
2860 sub-fiels of the variable as well. */
2862 && !vi
->is_full_var
)
2864 for (; vi
; vi
= vi
->next
)
2867 VEC_safe_push (ce_s
, heap
, *results
, &cexpr
);
2872 VEC_safe_push (ce_s
, heap
, *results
, &cexpr
);
2875 /* Process constraint T, performing various simplifications and then
2876 adding it to our list of overall constraints. */
2879 process_constraint (constraint_t t
)
2881 struct constraint_expr rhs
= t
->rhs
;
2882 struct constraint_expr lhs
= t
->lhs
;
2884 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
2885 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
2887 /* If we didn't get any useful constraint from the lhs we get
2888 &ANYTHING as fallback from get_constraint_for. Deal with
2889 it here by turning it into *ANYTHING. */
2890 if (lhs
.type
== ADDRESSOF
2891 && lhs
.var
== anything_id
)
2894 /* ADDRESSOF on the lhs is invalid. */
2895 gcc_assert (lhs
.type
!= ADDRESSOF
);
2897 /* We shouldn't add constraints from things that cannot have pointers.
2898 It's not completely trivial to avoid in the callers, so do it here. */
2899 if (rhs
.type
!= ADDRESSOF
2900 && !get_varinfo (rhs
.var
)->may_have_pointers
)
2903 /* Likewise adding to the solution of a non-pointer var isn't useful. */
2904 if (!get_varinfo (lhs
.var
)->may_have_pointers
)
2907 /* This can happen in our IR with things like n->a = *p */
2908 if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
2910 /* Split into tmp = *rhs, *lhs = tmp */
2911 struct constraint_expr tmplhs
;
2912 tmplhs
= new_scalar_tmp_constraint_exp ("doubledereftmp");
2913 process_constraint (new_constraint (tmplhs
, rhs
));
2914 process_constraint (new_constraint (lhs
, tmplhs
));
2916 else if (rhs
.type
== ADDRESSOF
&& lhs
.type
== DEREF
)
2918 /* Split into tmp = &rhs, *lhs = tmp */
2919 struct constraint_expr tmplhs
;
2920 tmplhs
= new_scalar_tmp_constraint_exp ("derefaddrtmp");
2921 process_constraint (new_constraint (tmplhs
, rhs
));
2922 process_constraint (new_constraint (lhs
, tmplhs
));
2926 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
2927 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2931 /* Return true if T is a type that could contain pointers. */
2934 type_could_have_pointers (tree type
)
2936 if (POINTER_TYPE_P (type
))
2939 if (TREE_CODE (type
) == ARRAY_TYPE
)
2940 return type_could_have_pointers (TREE_TYPE (type
));
2942 /* A function or method can consume pointers.
2943 ??? We could be more precise here. */
2944 if (TREE_CODE (type
) == FUNCTION_TYPE
2945 || TREE_CODE (type
) == METHOD_TYPE
)
2948 return AGGREGATE_TYPE_P (type
);
2951 /* Return true if T is a variable of a type that could contain
2955 could_have_pointers (tree t
)
2957 return (((TREE_CODE (t
) == VAR_DECL
2958 || TREE_CODE (t
) == PARM_DECL
2959 || TREE_CODE (t
) == RESULT_DECL
)
2960 && (TREE_PUBLIC (t
) || DECL_EXTERNAL (t
) || TREE_ADDRESSABLE (t
)))
2961 || type_could_have_pointers (TREE_TYPE (t
)));
2964 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2967 static HOST_WIDE_INT
2968 bitpos_of_field (const tree fdecl
)
2971 if (!host_integerp (DECL_FIELD_OFFSET (fdecl
), 0)
2972 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl
), 0))
2975 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl
)) * 8
2976 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl
)));
2980 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2981 resulting constraint expressions in *RESULTS. */
2984 get_constraint_for_ptr_offset (tree ptr
, tree offset
,
2985 VEC (ce_s
, heap
) **results
)
2987 struct constraint_expr c
;
2989 HOST_WIDE_INT rhsunitoffset
, rhsoffset
;
2991 /* If we do not do field-sensitive PTA adding offsets to pointers
2992 does not change the points-to solution. */
2993 if (!use_field_sensitive
)
2995 get_constraint_for (ptr
, results
);
2999 /* If the offset is not a non-negative integer constant that fits
3000 in a HOST_WIDE_INT, we have to fall back to a conservative
3001 solution which includes all sub-fields of all pointed-to
3002 variables of ptr. */
3003 if (offset
== NULL_TREE
3004 || !host_integerp (offset
, 0))
3005 rhsoffset
= UNKNOWN_OFFSET
;
3008 /* Make sure the bit-offset also fits. */
3009 rhsunitoffset
= TREE_INT_CST_LOW (offset
);
3010 rhsoffset
= rhsunitoffset
* BITS_PER_UNIT
;
3011 if (rhsunitoffset
!= rhsoffset
/ BITS_PER_UNIT
)
3012 rhsoffset
= UNKNOWN_OFFSET
;
3015 get_constraint_for (ptr
, results
);
3019 /* As we are eventually appending to the solution do not use
3020 VEC_iterate here. */
3021 n
= VEC_length (ce_s
, *results
);
3022 for (j
= 0; j
< n
; j
++)
3025 c
= *VEC_index (ce_s
, *results
, j
);
3026 curr
= get_varinfo (c
.var
);
3028 if (c
.type
== ADDRESSOF
3029 /* If this varinfo represents a full variable just use it. */
3030 && curr
->is_full_var
)
3032 else if (c
.type
== ADDRESSOF
3033 /* If we do not know the offset add all subfields. */
3034 && rhsoffset
== UNKNOWN_OFFSET
)
3036 varinfo_t temp
= lookup_vi_for_tree (curr
->decl
);
3039 struct constraint_expr c2
;
3041 c2
.type
= ADDRESSOF
;
3043 if (c2
.var
!= c
.var
)
3044 VEC_safe_push (ce_s
, heap
, *results
, &c2
);
3049 else if (c
.type
== ADDRESSOF
)
3052 unsigned HOST_WIDE_INT offset
= curr
->offset
+ rhsoffset
;
3054 /* Search the sub-field which overlaps with the
3055 pointed-to offset. If the result is outside of the variable
3056 we have to provide a conservative result, as the variable is
3057 still reachable from the resulting pointer (even though it
3058 technically cannot point to anything). The last and first
3059 sub-fields are such conservative results.
3060 ??? If we always had a sub-field for &object + 1 then
3061 we could represent this in a more precise way. */
3063 && curr
->offset
< offset
)
3065 temp
= first_or_preceding_vi_for_offset (curr
, offset
);
3067 /* If the found variable is not exactly at the pointed to
3068 result, we have to include the next variable in the
3069 solution as well. Otherwise two increments by offset / 2
3070 do not result in the same or a conservative superset
3072 if (temp
->offset
!= offset
3073 && temp
->next
!= NULL
)
3075 struct constraint_expr c2
;
3076 c2
.var
= temp
->next
->id
;
3077 c2
.type
= ADDRESSOF
;
3079 VEC_safe_push (ce_s
, heap
, *results
, &c2
);
3085 c
.offset
= rhsoffset
;
3087 VEC_replace (ce_s
, *results
, j
, &c
);
3092 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3093 If address_p is true the result will be taken its address of. */
3096 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
,
3100 HOST_WIDE_INT bitsize
= -1;
3101 HOST_WIDE_INT bitmaxsize
= -1;
3102 HOST_WIDE_INT bitpos
;
3104 struct constraint_expr
*result
;
3106 /* Some people like to do cute things like take the address of
3109 while (handled_component_p (forzero
)
3110 || INDIRECT_REF_P (forzero
))
3111 forzero
= TREE_OPERAND (forzero
, 0);
3113 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
3115 struct constraint_expr temp
;
3118 temp
.var
= integer_id
;
3120 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
3124 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
3126 /* Pretend to take the address of the base, we'll take care of
3127 adding the required subset of sub-fields below. */
3128 get_constraint_for_1 (t
, results
, true);
3129 gcc_assert (VEC_length (ce_s
, *results
) == 1);
3130 result
= VEC_last (ce_s
, *results
);
3132 if (result
->type
== SCALAR
3133 && get_varinfo (result
->var
)->is_full_var
)
3134 /* For single-field vars do not bother about the offset. */
3136 else if (result
->type
== SCALAR
)
3138 /* In languages like C, you can access one past the end of an
3139 array. You aren't allowed to dereference it, so we can
3140 ignore this constraint. When we handle pointer subtraction,
3141 we may have to do something cute here. */
3143 if ((unsigned HOST_WIDE_INT
)bitpos
< get_varinfo (result
->var
)->fullsize
3146 /* It's also not true that the constraint will actually start at the
3147 right offset, it may start in some padding. We only care about
3148 setting the constraint to the first actual field it touches, so
3150 struct constraint_expr cexpr
= *result
;
3152 VEC_pop (ce_s
, *results
);
3154 for (curr
= get_varinfo (cexpr
.var
); curr
; curr
= curr
->next
)
3156 if (ranges_overlap_p (curr
->offset
, curr
->size
,
3157 bitpos
, bitmaxsize
))
3159 cexpr
.var
= curr
->id
;
3160 VEC_safe_push (ce_s
, heap
, *results
, &cexpr
);
3165 /* If we are going to take the address of this field then
3166 to be able to compute reachability correctly add at least
3167 the last field of the variable. */
3169 && VEC_length (ce_s
, *results
) == 0)
3171 curr
= get_varinfo (cexpr
.var
);
3172 while (curr
->next
!= NULL
)
3174 cexpr
.var
= curr
->id
;
3175 VEC_safe_push (ce_s
, heap
, *results
, &cexpr
);
3178 /* Assert that we found *some* field there. The user couldn't be
3179 accessing *only* padding. */
3180 /* Still the user could access one past the end of an array
3181 embedded in a struct resulting in accessing *only* padding. */
3182 gcc_assert (VEC_length (ce_s
, *results
) >= 1
3183 || ref_contains_array_ref (orig_t
));
3185 else if (bitmaxsize
== 0)
3187 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3188 fprintf (dump_file
, "Access to zero-sized part of variable,"
3192 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3193 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
3195 else if (result
->type
== DEREF
)
3197 /* If we do not know exactly where the access goes say so. Note
3198 that only for non-structure accesses we know that we access
3199 at most one subfiled of any variable. */
3201 || bitsize
!= bitmaxsize
3202 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t
)))
3203 result
->offset
= UNKNOWN_OFFSET
;
3205 result
->offset
= bitpos
;
3207 else if (result
->type
== ADDRESSOF
)
3209 /* We can end up here for component references on a
3210 VIEW_CONVERT_EXPR <>(&foobar). */
3211 result
->type
= SCALAR
;
3212 result
->var
= anything_id
;
3220 /* Dereference the constraint expression CONS, and return the result.
3221 DEREF (ADDRESSOF) = SCALAR
3222 DEREF (SCALAR) = DEREF
3223 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3224 This is needed so that we can handle dereferencing DEREF constraints. */
3227 do_deref (VEC (ce_s
, heap
) **constraints
)
3229 struct constraint_expr
*c
;
3232 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
3234 if (c
->type
== SCALAR
)
3236 else if (c
->type
== ADDRESSOF
)
3238 else if (c
->type
== DEREF
)
3240 struct constraint_expr tmplhs
;
3241 tmplhs
= new_scalar_tmp_constraint_exp ("dereftmp");
3242 process_constraint (new_constraint (tmplhs
, *c
));
3243 c
->var
= tmplhs
.var
;
3250 static void get_constraint_for_1 (tree
, VEC (ce_s
, heap
) **, bool);
3252 /* Given a tree T, return the constraint expression for taking the
3256 get_constraint_for_address_of (tree t
, VEC (ce_s
, heap
) **results
)
3258 struct constraint_expr
*c
;
3261 get_constraint_for_1 (t
, results
, true);
3263 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
3265 if (c
->type
== DEREF
)
3268 c
->type
= ADDRESSOF
;
3272 /* Given a tree T, return the constraint expression for it. */
3275 get_constraint_for_1 (tree t
, VEC (ce_s
, heap
) **results
, bool address_p
)
3277 struct constraint_expr temp
;
3279 /* x = integer is all glommed to a single variable, which doesn't
3280 point to anything by itself. That is, of course, unless it is an
3281 integer constant being treated as a pointer, in which case, we
3282 will return that this is really the addressof anything. This
3283 happens below, since it will fall into the default case. The only
3284 case we know something about an integer treated like a pointer is
3285 when it is the NULL pointer, and then we just say it points to
3288 Do not do that if -fno-delete-null-pointer-checks though, because
3289 in that case *NULL does not fail, so it _should_ alias *anything.
3290 It is not worth adding a new option or renaming the existing one,
3291 since this case is relatively obscure. */
3292 if ((TREE_CODE (t
) == INTEGER_CST
3293 && integer_zerop (t
))
3294 /* The only valid CONSTRUCTORs in gimple with pointer typed
3295 elements are zero-initializer. But in IPA mode we also
3296 process global initializers, so verify at least. */
3297 || (TREE_CODE (t
) == CONSTRUCTOR
3298 && CONSTRUCTOR_NELTS (t
) == 0))
3300 if (flag_delete_null_pointer_checks
)
3301 temp
.var
= nothing_id
;
3303 temp
.var
= anything_id
;
3304 temp
.type
= ADDRESSOF
;
3306 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
3310 /* String constants are read-only. */
3311 if (TREE_CODE (t
) == STRING_CST
)
3313 temp
.var
= readonly_id
;
3316 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
3320 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
3322 case tcc_expression
:
3324 switch (TREE_CODE (t
))
3327 get_constraint_for_address_of (TREE_OPERAND (t
, 0), results
);
3335 switch (TREE_CODE (t
))
3339 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, address_p
);
3344 case ARRAY_RANGE_REF
:
3346 get_constraint_for_component_ref (t
, results
, address_p
);
3348 case VIEW_CONVERT_EXPR
:
3349 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, address_p
);
3351 /* We are missing handling for TARGET_MEM_REF here. */
3356 case tcc_exceptional
:
3358 switch (TREE_CODE (t
))
3362 get_constraint_for_ssa_var (t
, results
, address_p
);
3369 VEC (ce_s
, heap
) *tmp
= NULL
;
3370 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t
), i
, val
)
3372 struct constraint_expr
*rhsp
;
3374 get_constraint_for_1 (val
, &tmp
, address_p
);
3375 for (j
= 0; VEC_iterate (ce_s
, tmp
, j
, rhsp
); ++j
)
3376 VEC_safe_push (ce_s
, heap
, *results
, rhsp
);
3377 VEC_truncate (ce_s
, tmp
, 0);
3379 VEC_free (ce_s
, heap
, tmp
);
3380 /* We do not know whether the constructor was complete,
3381 so technically we have to add &NOTHING or &ANYTHING
3382 like we do for an empty constructor as well. */
3389 case tcc_declaration
:
3391 get_constraint_for_ssa_var (t
, results
, address_p
);
3397 /* The default fallback is a constraint from anything. */
3398 temp
.type
= ADDRESSOF
;
3399 temp
.var
= anything_id
;
3401 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
3404 /* Given a gimple tree T, return the constraint expression vector for it. */
3407 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
3409 gcc_assert (VEC_length (ce_s
, *results
) == 0);
3411 get_constraint_for_1 (t
, results
, false);
3415 /* Efficiently generates constraints from all entries in *RHSC to all
3416 entries in *LHSC. */
3419 process_all_all_constraints (VEC (ce_s
, heap
) *lhsc
, VEC (ce_s
, heap
) *rhsc
)
3421 struct constraint_expr
*lhsp
, *rhsp
;
3424 if (VEC_length (ce_s
, lhsc
) <= 1
3425 || VEC_length (ce_s
, rhsc
) <= 1)
3427 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, lhsp
); ++i
)
3428 for (j
= 0; VEC_iterate (ce_s
, rhsc
, j
, rhsp
); ++j
)
3429 process_constraint (new_constraint (*lhsp
, *rhsp
));
3433 struct constraint_expr tmp
;
3434 tmp
= new_scalar_tmp_constraint_exp ("allalltmp");
3435 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, rhsp
); ++i
)
3436 process_constraint (new_constraint (tmp
, *rhsp
));
3437 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, lhsp
); ++i
)
3438 process_constraint (new_constraint (*lhsp
, tmp
));
3442 /* Handle aggregate copies by expanding into copies of the respective
3443 fields of the structures. */
3446 do_structure_copy (tree lhsop
, tree rhsop
)
3448 struct constraint_expr
*lhsp
, *rhsp
;
3449 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
3452 get_constraint_for (lhsop
, &lhsc
);
3453 get_constraint_for (rhsop
, &rhsc
);
3454 lhsp
= VEC_index (ce_s
, lhsc
, 0);
3455 rhsp
= VEC_index (ce_s
, rhsc
, 0);
3456 if (lhsp
->type
== DEREF
3457 || (lhsp
->type
== ADDRESSOF
&& lhsp
->var
== anything_id
)
3458 || rhsp
->type
== DEREF
)
3460 if (lhsp
->type
== DEREF
)
3462 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
3463 lhsp
->offset
= UNKNOWN_OFFSET
;
3465 if (rhsp
->type
== DEREF
)
3467 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
3468 rhsp
->offset
= UNKNOWN_OFFSET
;
3470 process_all_all_constraints (lhsc
, rhsc
);
3472 else if (lhsp
->type
== SCALAR
3473 && (rhsp
->type
== SCALAR
3474 || rhsp
->type
== ADDRESSOF
))
3476 HOST_WIDE_INT lhssize
, lhsmaxsize
, lhsoffset
;
3477 HOST_WIDE_INT rhssize
, rhsmaxsize
, rhsoffset
;
3479 get_ref_base_and_extent (lhsop
, &lhsoffset
, &lhssize
, &lhsmaxsize
);
3480 get_ref_base_and_extent (rhsop
, &rhsoffset
, &rhssize
, &rhsmaxsize
);
3481 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
);)
3483 varinfo_t lhsv
, rhsv
;
3484 rhsp
= VEC_index (ce_s
, rhsc
, k
);
3485 lhsv
= get_varinfo (lhsp
->var
);
3486 rhsv
= get_varinfo (rhsp
->var
);
3487 if (lhsv
->may_have_pointers
3488 && ranges_overlap_p (lhsv
->offset
+ rhsoffset
, lhsv
->size
,
3489 rhsv
->offset
+ lhsoffset
, rhsv
->size
))
3490 process_constraint (new_constraint (*lhsp
, *rhsp
));
3491 if (lhsv
->offset
+ rhsoffset
+ lhsv
->size
3492 > rhsv
->offset
+ lhsoffset
+ rhsv
->size
)
3495 if (k
>= VEC_length (ce_s
, rhsc
))
3505 VEC_free (ce_s
, heap
, lhsc
);
3506 VEC_free (ce_s
, heap
, rhsc
);
3509 /* Create a constraint ID = OP. */
3512 make_constraint_to (unsigned id
, tree op
)
3514 VEC(ce_s
, heap
) *rhsc
= NULL
;
3515 struct constraint_expr
*c
;
3516 struct constraint_expr includes
;
3520 includes
.offset
= 0;
3521 includes
.type
= SCALAR
;
3523 get_constraint_for (op
, &rhsc
);
3524 for (j
= 0; VEC_iterate (ce_s
, rhsc
, j
, c
); j
++)
3525 process_constraint (new_constraint (includes
, *c
));
3526 VEC_free (ce_s
, heap
, rhsc
);
3529 /* Create a constraint ID = &FROM. */
3532 make_constraint_from (varinfo_t vi
, int from
)
3534 struct constraint_expr lhs
, rhs
;
3542 rhs
.type
= ADDRESSOF
;
3543 process_constraint (new_constraint (lhs
, rhs
));
3546 /* Create a constraint ID = FROM. */
3549 make_copy_constraint (varinfo_t vi
, int from
)
3551 struct constraint_expr lhs
, rhs
;
3560 process_constraint (new_constraint (lhs
, rhs
));
3563 /* Make constraints necessary to make OP escape. */
3566 make_escape_constraint (tree op
)
3568 make_constraint_to (escaped_id
, op
);
3571 /* Add constraints to that the solution of VI is transitively closed. */
3574 make_transitive_closure_constraints (varinfo_t vi
)
3576 struct constraint_expr lhs
, rhs
;
3585 process_constraint (new_constraint (lhs
, rhs
));
3587 /* VAR = VAR + UNKNOWN; */
3593 rhs
.offset
= UNKNOWN_OFFSET
;
3594 process_constraint (new_constraint (lhs
, rhs
));
3597 /* Create a new artificial heap variable with NAME.
3598 Return the created variable. */
3601 make_heapvar_for (varinfo_t lhs
, const char *name
)
3604 tree heapvar
= heapvar_lookup (lhs
->decl
, lhs
->offset
);
3606 if (heapvar
== NULL_TREE
)
3609 heapvar
= create_tmp_var_raw (ptr_type_node
, name
);
3610 DECL_EXTERNAL (heapvar
) = 1;
3612 heapvar_insert (lhs
->decl
, lhs
->offset
, heapvar
);
3614 ann
= get_var_ann (heapvar
);
3615 ann
->is_heapvar
= 1;
3618 /* For global vars we need to add a heapvar to the list of referenced
3619 vars of a different function than it was created for originally. */
3620 if (cfun
&& gimple_referenced_vars (cfun
))
3621 add_referenced_var (heapvar
);
3623 vi
= new_var_info (heapvar
, name
);
3624 vi
->is_artificial_var
= true;
3625 vi
->is_heap_var
= true;
3626 vi
->is_unknown_size_var
= true;
3630 vi
->is_full_var
= true;
3631 insert_vi_for_tree (heapvar
, vi
);
3636 /* Create a new artificial heap variable with NAME and make a
3637 constraint from it to LHS. Return the created variable. */
3640 make_constraint_from_heapvar (varinfo_t lhs
, const char *name
)
3642 varinfo_t vi
= make_heapvar_for (lhs
, name
);
3643 make_constraint_from (lhs
, vi
->id
);
3648 /* Create a new artificial heap variable with NAME and make a
3649 constraint from it to LHS. Set flags according to a tag used
3650 for tracking restrict pointers. */
3653 make_constraint_from_restrict (varinfo_t lhs
, const char *name
)
3656 vi
= make_constraint_from_heapvar (lhs
, name
);
3657 vi
->is_restrict_var
= 1;
3658 vi
->is_global_var
= 0;
3659 vi
->is_special_var
= 1;
3660 vi
->may_have_pointers
= 0;
3663 /* In IPA mode there are varinfos for different aspects of reach
3664 function designator. One for the points-to set of the return
3665 value, one for the variables that are clobbered by the function,
3666 one for its uses and one for each parameter (including a single
3667 glob for remaining variadic arguments). */
3669 enum { fi_clobbers
= 1, fi_uses
= 2,
3670 fi_static_chain
= 3, fi_result
= 4, fi_parm_base
= 5 };
3672 /* Get a constraint for the requested part of a function designator FI
3673 when operating in IPA mode. */
3675 static struct constraint_expr
3676 get_function_part_constraint (varinfo_t fi
, unsigned part
)
3678 struct constraint_expr c
;
3680 gcc_assert (in_ipa_mode
);
3682 if (fi
->id
== anything_id
)
3684 /* ??? We probably should have a ANYFN special variable. */
3685 c
.var
= anything_id
;
3689 else if (TREE_CODE (fi
->decl
) == FUNCTION_DECL
)
3691 varinfo_t ai
= first_vi_for_offset (fi
, part
);
3695 c
.var
= anything_id
;
3709 /* For non-IPA mode, generate constraints necessary for a call on the
3713 handle_rhs_call (gimple stmt
, VEC(ce_s
, heap
) **results
)
3715 struct constraint_expr rhsc
;
3717 bool returns_uses
= false;
3719 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3721 tree arg
= gimple_call_arg (stmt
, i
);
3722 int flags
= gimple_call_arg_flags (stmt
, i
);
3724 /* If the argument is not used or it does not contain pointers
3725 we can ignore it. */
3726 if ((flags
& EAF_UNUSED
)
3727 || !could_have_pointers (arg
))
3730 /* As we compute ESCAPED context-insensitive we do not gain
3731 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3732 set. The argument would still get clobbered through the
3734 ??? We might get away with less (and more precise) constraints
3735 if using a temporary for transitively closing things. */
3736 if ((flags
& EAF_NOCLOBBER
)
3737 && (flags
& EAF_NOESCAPE
))
3739 varinfo_t uses
= get_call_use_vi (stmt
);
3740 if (!(flags
& EAF_DIRECT
))
3741 make_transitive_closure_constraints (uses
);
3742 make_constraint_to (uses
->id
, arg
);
3743 returns_uses
= true;
3745 else if (flags
& EAF_NOESCAPE
)
3747 varinfo_t uses
= get_call_use_vi (stmt
);
3748 varinfo_t clobbers
= get_call_clobber_vi (stmt
);
3749 if (!(flags
& EAF_DIRECT
))
3751 make_transitive_closure_constraints (uses
);
3752 make_transitive_closure_constraints (clobbers
);
3754 make_constraint_to (uses
->id
, arg
);
3755 make_constraint_to (clobbers
->id
, arg
);
3756 returns_uses
= true;
3759 make_escape_constraint (arg
);
3762 /* If we added to the calls uses solution make sure we account for
3763 pointers to it to be returned. */
3766 rhsc
.var
= get_call_use_vi (stmt
)->id
;
3769 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3772 /* The static chain escapes as well. */
3773 if (gimple_call_chain (stmt
))
3774 make_escape_constraint (gimple_call_chain (stmt
));
3776 /* And if we applied NRV the address of the return slot escapes as well. */
3777 if (gimple_call_return_slot_opt_p (stmt
)
3778 && gimple_call_lhs (stmt
) != NULL_TREE
3779 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
3781 VEC(ce_s
, heap
) *tmpc
= NULL
;
3782 struct constraint_expr lhsc
, *c
;
3783 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
3784 lhsc
.var
= escaped_id
;
3787 for (i
= 0; VEC_iterate (ce_s
, tmpc
, i
, c
); ++i
)
3788 process_constraint (new_constraint (lhsc
, *c
));
3789 VEC_free(ce_s
, heap
, tmpc
);
3792 /* Regular functions return nonlocal memory. */
3793 rhsc
.var
= nonlocal_id
;
3796 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3799 /* For non-IPA mode, generate constraints necessary for a call
3800 that returns a pointer and assigns it to LHS. This simply makes
3801 the LHS point to global and escaped variables. */
3804 handle_lhs_call (gimple stmt
, tree lhs
, int flags
, VEC(ce_s
, heap
) *rhsc
,
3807 VEC(ce_s
, heap
) *lhsc
= NULL
;
3809 get_constraint_for (lhs
, &lhsc
);
3810 /* If the store is to a global decl make sure to
3811 add proper escape constraints. */
3812 lhs
= get_base_address (lhs
);
3815 && is_global_var (lhs
))
3817 struct constraint_expr tmpc
;
3818 tmpc
.var
= escaped_id
;
3821 VEC_safe_push (ce_s
, heap
, lhsc
, &tmpc
);
3824 /* If the call returns an argument unmodified override the rhs
3826 flags
= gimple_call_return_flags (stmt
);
3827 if (flags
& ERF_RETURNS_ARG
3828 && (flags
& ERF_RETURN_ARG_MASK
) < gimple_call_num_args (stmt
))
3832 arg
= gimple_call_arg (stmt
, flags
& ERF_RETURN_ARG_MASK
);
3833 get_constraint_for (arg
, &rhsc
);
3834 process_all_all_constraints (lhsc
, rhsc
);
3835 VEC_free (ce_s
, heap
, rhsc
);
3837 else if (flags
& ERF_NOALIAS
)
3840 struct constraint_expr tmpc
;
3842 vi
= make_heapvar_for (get_vi_for_tree (lhs
), "HEAP");
3843 /* We delay marking allocated storage global until we know if
3845 DECL_EXTERNAL (vi
->decl
) = 0;
3846 vi
->is_global_var
= 0;
3847 /* If this is not a real malloc call assume the memory was
3848 initialized and thus may point to global memory. All
3849 builtin functions with the malloc attribute behave in a sane way. */
3851 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
3852 make_constraint_from (vi
, nonlocal_id
);
3855 tmpc
.type
= ADDRESSOF
;
3856 VEC_safe_push (ce_s
, heap
, rhsc
, &tmpc
);
3859 process_all_all_constraints (lhsc
, rhsc
);
3861 VEC_free (ce_s
, heap
, lhsc
);
3864 /* For non-IPA mode, generate constraints necessary for a call of a
3865 const function that returns a pointer in the statement STMT. */
3868 handle_const_call (gimple stmt
, VEC(ce_s
, heap
) **results
)
3870 struct constraint_expr rhsc
;
3873 /* Treat nested const functions the same as pure functions as far
3874 as the static chain is concerned. */
3875 if (gimple_call_chain (stmt
))
3877 varinfo_t uses
= get_call_use_vi (stmt
);
3878 make_transitive_closure_constraints (uses
);
3879 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
3880 rhsc
.var
= uses
->id
;
3883 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3886 /* May return arguments. */
3887 for (k
= 0; k
< gimple_call_num_args (stmt
); ++k
)
3889 tree arg
= gimple_call_arg (stmt
, k
);
3891 if (could_have_pointers (arg
))
3893 VEC(ce_s
, heap
) *argc
= NULL
;
3895 struct constraint_expr
*argp
;
3896 get_constraint_for (arg
, &argc
);
3897 for (i
= 0; VEC_iterate (ce_s
, argc
, i
, argp
); ++i
)
3898 VEC_safe_push (ce_s
, heap
, *results
, argp
);
3899 VEC_free(ce_s
, heap
, argc
);
3903 /* May return addresses of globals. */
3904 rhsc
.var
= nonlocal_id
;
3906 rhsc
.type
= ADDRESSOF
;
3907 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3910 /* For non-IPA mode, generate constraints necessary for a call to a
3911 pure function in statement STMT. */
3914 handle_pure_call (gimple stmt
, VEC(ce_s
, heap
) **results
)
3916 struct constraint_expr rhsc
;
3918 varinfo_t uses
= NULL
;
3920 /* Memory reached from pointer arguments is call-used. */
3921 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3923 tree arg
= gimple_call_arg (stmt
, i
);
3925 if (could_have_pointers (arg
))
3929 uses
= get_call_use_vi (stmt
);
3930 make_transitive_closure_constraints (uses
);
3932 make_constraint_to (uses
->id
, arg
);
3936 /* The static chain is used as well. */
3937 if (gimple_call_chain (stmt
))
3941 uses
= get_call_use_vi (stmt
);
3942 make_transitive_closure_constraints (uses
);
3944 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
3947 /* Pure functions may return call-used and nonlocal memory. */
3950 rhsc
.var
= uses
->id
;
3953 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3955 rhsc
.var
= nonlocal_id
;
3958 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3962 /* Return the varinfo for the callee of CALL. */
3965 get_fi_for_callee (gimple call
)
3969 /* If we can directly resolve the function being called, do so.
3970 Otherwise, it must be some sort of indirect expression that
3971 we should still be able to handle. */
3972 decl
= gimple_call_fndecl (call
);
3974 return get_vi_for_tree (decl
);
3976 decl
= gimple_call_fn (call
);
3977 /* The function can be either an SSA name pointer or,
3978 worse, an OBJ_TYPE_REF. In this case we have no
3979 clue and should be getting ANYFN (well, ANYTHING for now). */
3980 if (TREE_CODE (decl
) == SSA_NAME
)
3982 if (TREE_CODE (decl
) == SSA_NAME
3983 && TREE_CODE (SSA_NAME_VAR (decl
)) == PARM_DECL
3984 && SSA_NAME_IS_DEFAULT_DEF (decl
))
3985 decl
= SSA_NAME_VAR (decl
);
3986 return get_vi_for_tree (decl
);
3988 else if (TREE_CODE (decl
) == INTEGER_CST
3989 || TREE_CODE (decl
) == OBJ_TYPE_REF
)
3990 return get_varinfo (anything_id
);
3995 /* Walk statement T setting up aliasing constraints according to the
3996 references found in T. This function is the main part of the
3997 constraint builder. AI points to auxiliary alias information used
3998 when building alias sets and computing alias grouping heuristics. */
4001 find_func_aliases (gimple origt
)
4004 VEC(ce_s
, heap
) *lhsc
= NULL
;
4005 VEC(ce_s
, heap
) *rhsc
= NULL
;
4006 struct constraint_expr
*c
;
4009 /* Now build constraints expressions. */
4010 if (gimple_code (t
) == GIMPLE_PHI
)
4012 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t
))));
4014 /* Only care about pointers and structures containing
4016 if (could_have_pointers (gimple_phi_result (t
)))
4021 /* For a phi node, assign all the arguments to
4023 get_constraint_for (gimple_phi_result (t
), &lhsc
);
4024 for (i
= 0; i
< gimple_phi_num_args (t
); i
++)
4026 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
4028 STRIP_NOPS (strippedrhs
);
4029 get_constraint_for (gimple_phi_arg_def (t
, i
), &rhsc
);
4031 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
4033 struct constraint_expr
*c2
;
4034 while (VEC_length (ce_s
, rhsc
) > 0)
4036 c2
= VEC_last (ce_s
, rhsc
);
4037 process_constraint (new_constraint (*c
, *c2
));
4038 VEC_pop (ce_s
, rhsc
);
4044 /* In IPA mode, we need to generate constraints to pass call
4045 arguments through their calls. There are two cases,
4046 either a GIMPLE_CALL returning a value, or just a plain
4047 GIMPLE_CALL when we are not.
4049 In non-ipa mode, we need to generate constraints for each
4050 pointer passed by address. */
4051 else if (is_gimple_call (t
))
4053 tree fndecl
= gimple_call_fndecl (t
);
4054 if (fndecl
!= NULL_TREE
4055 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
4056 /* ??? All builtins that are handled here need to be handled
4057 in the alias-oracle query functions explicitly! */
4058 switch (DECL_FUNCTION_CODE (fndecl
))
4060 /* All the following functions return a pointer to the same object
4061 as their first argument points to. The functions do not add
4062 to the ESCAPED solution. The functions make the first argument
4063 pointed to memory point to what the second argument pointed to
4064 memory points to. */
4065 case BUILT_IN_STRCPY
:
4066 case BUILT_IN_STRNCPY
:
4067 case BUILT_IN_BCOPY
:
4068 case BUILT_IN_MEMCPY
:
4069 case BUILT_IN_MEMMOVE
:
4070 case BUILT_IN_MEMPCPY
:
4071 case BUILT_IN_STPCPY
:
4072 case BUILT_IN_STPNCPY
:
4073 case BUILT_IN_STRCAT
:
4074 case BUILT_IN_STRNCAT
:
4076 tree res
= gimple_call_lhs (t
);
4077 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4078 == BUILT_IN_BCOPY
? 1 : 0));
4079 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4080 == BUILT_IN_BCOPY
? 0 : 1));
4081 if (res
!= NULL_TREE
)
4083 get_constraint_for (res
, &lhsc
);
4084 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY
4085 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY
4086 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY
)
4087 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &rhsc
);
4089 get_constraint_for (dest
, &rhsc
);
4090 process_all_all_constraints (lhsc
, rhsc
);
4091 VEC_free (ce_s
, heap
, lhsc
);
4092 VEC_free (ce_s
, heap
, rhsc
);
4094 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4095 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4098 process_all_all_constraints (lhsc
, rhsc
);
4099 VEC_free (ce_s
, heap
, lhsc
);
4100 VEC_free (ce_s
, heap
, rhsc
);
4103 case BUILT_IN_MEMSET
:
4105 tree res
= gimple_call_lhs (t
);
4106 tree dest
= gimple_call_arg (t
, 0);
4109 struct constraint_expr ac
;
4110 if (res
!= NULL_TREE
)
4112 get_constraint_for (res
, &lhsc
);
4113 get_constraint_for (dest
, &rhsc
);
4114 process_all_all_constraints (lhsc
, rhsc
);
4115 VEC_free (ce_s
, heap
, lhsc
);
4116 VEC_free (ce_s
, heap
, rhsc
);
4118 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4120 if (flag_delete_null_pointer_checks
4121 && integer_zerop (gimple_call_arg (t
, 1)))
4123 ac
.type
= ADDRESSOF
;
4124 ac
.var
= nothing_id
;
4129 ac
.var
= integer_id
;
4132 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, lhsp
); ++i
)
4133 process_constraint (new_constraint (*lhsp
, ac
));
4134 VEC_free (ce_s
, heap
, lhsc
);
4137 /* All the following functions do not return pointers, do not
4138 modify the points-to sets of memory reachable from their
4139 arguments and do not add to the ESCAPED solution. */
4140 case BUILT_IN_SINCOS
:
4141 case BUILT_IN_SINCOSF
:
4142 case BUILT_IN_SINCOSL
:
4143 case BUILT_IN_FREXP
:
4144 case BUILT_IN_FREXPF
:
4145 case BUILT_IN_FREXPL
:
4146 case BUILT_IN_GAMMA_R
:
4147 case BUILT_IN_GAMMAF_R
:
4148 case BUILT_IN_GAMMAL_R
:
4149 case BUILT_IN_LGAMMA_R
:
4150 case BUILT_IN_LGAMMAF_R
:
4151 case BUILT_IN_LGAMMAL_R
:
4153 case BUILT_IN_MODFF
:
4154 case BUILT_IN_MODFL
:
4155 case BUILT_IN_REMQUO
:
4156 case BUILT_IN_REMQUOF
:
4157 case BUILT_IN_REMQUOL
:
4160 /* Trampolines are special - they set up passing the static
4162 case BUILT_IN_INIT_TRAMPOLINE
:
4164 tree tramp
= gimple_call_arg (t
, 0);
4165 tree nfunc
= gimple_call_arg (t
, 1);
4166 tree frame
= gimple_call_arg (t
, 2);
4168 struct constraint_expr lhs
, *rhsp
;
4171 varinfo_t nfi
= NULL
;
4172 gcc_assert (TREE_CODE (nfunc
) == ADDR_EXPR
);
4173 nfi
= lookup_vi_for_tree (TREE_OPERAND (nfunc
, 0));
4176 lhs
= get_function_part_constraint (nfi
, fi_static_chain
);
4177 get_constraint_for (frame
, &rhsc
);
4178 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, rhsp
); ++i
)
4179 process_constraint (new_constraint (lhs
, *rhsp
));
4180 VEC_free (ce_s
, heap
, rhsc
);
4182 /* Make the frame point to the function for
4183 the trampoline adjustment call. */
4184 get_constraint_for (tramp
, &lhsc
);
4186 get_constraint_for (nfunc
, &rhsc
);
4187 process_all_all_constraints (lhsc
, rhsc
);
4188 VEC_free (ce_s
, heap
, rhsc
);
4189 VEC_free (ce_s
, heap
, lhsc
);
4194 /* Else fallthru to generic handling which will let
4195 the frame escape. */
4198 case BUILT_IN_ADJUST_TRAMPOLINE
:
4200 tree tramp
= gimple_call_arg (t
, 0);
4201 tree res
= gimple_call_lhs (t
);
4202 if (in_ipa_mode
&& res
)
4204 get_constraint_for (res
, &lhsc
);
4205 get_constraint_for (tramp
, &rhsc
);
4207 process_all_all_constraints (lhsc
, rhsc
);
4208 VEC_free (ce_s
, heap
, rhsc
);
4209 VEC_free (ce_s
, heap
, lhsc
);
4213 /* Variadic argument handling needs to be handled in IPA
4215 case BUILT_IN_VA_START
:
4219 tree valist
= gimple_call_arg (t
, 0);
4220 struct constraint_expr rhs
, *lhsp
;
4222 /* The va_list gets access to pointers in variadic
4224 fi
= lookup_vi_for_tree (cfun
->decl
);
4225 gcc_assert (fi
!= NULL
);
4226 get_constraint_for (valist
, &lhsc
);
4228 rhs
= get_function_part_constraint (fi
, ~0);
4229 rhs
.type
= ADDRESSOF
;
4230 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, lhsp
); ++i
)
4231 process_constraint (new_constraint (*lhsp
, rhs
));
4232 VEC_free (ce_s
, heap
, lhsc
);
4233 /* va_list is clobbered. */
4234 make_constraint_to (get_call_clobber_vi (t
)->id
, valist
);
4239 /* va_end doesn't have any effect that matters. */
4240 case BUILT_IN_VA_END
:
4242 /* Alternate return. Simply give up for now. */
4243 case BUILT_IN_RETURN
:
4247 || !(fi
= get_vi_for_tree (cfun
->decl
)))
4248 make_constraint_from (get_varinfo (escaped_id
), anything_id
);
4249 else if (in_ipa_mode
4252 struct constraint_expr lhs
, rhs
;
4253 lhs
= get_function_part_constraint (fi
, fi_result
);
4254 rhs
.var
= anything_id
;
4257 process_constraint (new_constraint (lhs
, rhs
));
4261 /* printf-style functions may have hooks to set pointers to
4262 point to somewhere into the generated string. Leave them
4263 for a later excercise... */
4265 /* Fallthru to general call handling. */;
4269 && (!(fi
= lookup_vi_for_tree (fndecl
))
4270 || !fi
->is_fn_info
)))
4272 VEC(ce_s
, heap
) *rhsc
= NULL
;
4273 int flags
= gimple_call_flags (t
);
4275 /* Const functions can return their arguments and addresses
4276 of global memory but not of escaped memory. */
4277 if (flags
& (ECF_CONST
|ECF_NOVOPS
))
4279 if (gimple_call_lhs (t
)
4280 && could_have_pointers (gimple_call_lhs (t
)))
4281 handle_const_call (t
, &rhsc
);
4283 /* Pure functions can return addresses in and of memory
4284 reachable from their arguments, but they are not an escape
4285 point for reachable memory of their arguments. */
4286 else if (flags
& (ECF_PURE
|ECF_LOOPING_CONST_OR_PURE
))
4287 handle_pure_call (t
, &rhsc
);
4289 handle_rhs_call (t
, &rhsc
);
4290 if (gimple_call_lhs (t
)
4291 && could_have_pointers (gimple_call_lhs (t
)))
4292 handle_lhs_call (t
, gimple_call_lhs (t
), flags
, rhsc
, fndecl
);
4293 VEC_free (ce_s
, heap
, rhsc
);
4300 fi
= get_fi_for_callee (t
);
4302 /* Assign all the passed arguments to the appropriate incoming
4303 parameters of the function. */
4304 for (j
= 0; j
< gimple_call_num_args (t
); j
++)
4306 struct constraint_expr lhs
;
4307 struct constraint_expr
*rhsp
;
4308 tree arg
= gimple_call_arg (t
, j
);
4310 if (!could_have_pointers (arg
))
4313 get_constraint_for (arg
, &rhsc
);
4314 lhs
= get_function_part_constraint (fi
, fi_parm_base
+ j
);
4315 while (VEC_length (ce_s
, rhsc
) != 0)
4317 rhsp
= VEC_last (ce_s
, rhsc
);
4318 process_constraint (new_constraint (lhs
, *rhsp
));
4319 VEC_pop (ce_s
, rhsc
);
4323 /* If we are returning a value, assign it to the result. */
4324 lhsop
= gimple_call_lhs (t
);
4326 && type_could_have_pointers (TREE_TYPE (lhsop
)))
4328 struct constraint_expr rhs
;
4329 struct constraint_expr
*lhsp
;
4331 get_constraint_for (lhsop
, &lhsc
);
4332 rhs
= get_function_part_constraint (fi
, fi_result
);
4334 && DECL_RESULT (fndecl
)
4335 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4337 VEC(ce_s
, heap
) *tem
= NULL
;
4338 VEC_safe_push (ce_s
, heap
, tem
, &rhs
);
4340 rhs
= *VEC_index (ce_s
, tem
, 0);
4341 VEC_free(ce_s
, heap
, tem
);
4343 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
4344 process_constraint (new_constraint (*lhsp
, rhs
));
4347 /* If we pass the result decl by reference, honor that. */
4350 && DECL_RESULT (fndecl
)
4351 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4353 struct constraint_expr lhs
;
4354 struct constraint_expr
*rhsp
;
4356 get_constraint_for_address_of (lhsop
, &rhsc
);
4357 lhs
= get_function_part_constraint (fi
, fi_result
);
4358 for (j
= 0; VEC_iterate (ce_s
, rhsc
, j
, rhsp
); j
++)
4359 process_constraint (new_constraint (lhs
, *rhsp
));
4360 VEC_free (ce_s
, heap
, rhsc
);
4363 /* If we use a static chain, pass it along. */
4364 if (gimple_call_chain (t
))
4366 struct constraint_expr lhs
;
4367 struct constraint_expr
*rhsp
;
4369 get_constraint_for (gimple_call_chain (t
), &rhsc
);
4370 lhs
= get_function_part_constraint (fi
, fi_static_chain
);
4371 for (j
= 0; VEC_iterate (ce_s
, rhsc
, j
, rhsp
); j
++)
4372 process_constraint (new_constraint (lhs
, *rhsp
));
4376 /* Otherwise, just a regular assignment statement. Only care about
4377 operations with pointer result, others are dealt with as escape
4378 points if they have pointer operands. */
4379 else if (is_gimple_assign (t
)
4380 && type_could_have_pointers (TREE_TYPE (gimple_assign_lhs (t
))))
4382 /* Otherwise, just a regular assignment statement. */
4383 tree lhsop
= gimple_assign_lhs (t
);
4384 tree rhsop
= (gimple_num_ops (t
) == 2) ? gimple_assign_rhs1 (t
) : NULL
;
4386 if (rhsop
&& AGGREGATE_TYPE_P (TREE_TYPE (lhsop
)))
4387 do_structure_copy (lhsop
, rhsop
);
4390 struct constraint_expr temp
;
4391 get_constraint_for (lhsop
, &lhsc
);
4393 if (gimple_assign_rhs_code (t
) == POINTER_PLUS_EXPR
)
4394 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4395 gimple_assign_rhs2 (t
), &rhsc
);
4396 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t
))
4397 && !(POINTER_TYPE_P (gimple_expr_type (t
))
4398 && !POINTER_TYPE_P (TREE_TYPE (rhsop
))))
4399 || gimple_assign_single_p (t
))
4400 get_constraint_for (rhsop
, &rhsc
);
4403 temp
.type
= ADDRESSOF
;
4404 temp
.var
= anything_id
;
4406 VEC_safe_push (ce_s
, heap
, rhsc
, &temp
);
4408 process_all_all_constraints (lhsc
, rhsc
);
4410 /* If there is a store to a global variable the rhs escapes. */
4411 if ((lhsop
= get_base_address (lhsop
)) != NULL_TREE
4413 && is_global_var (lhsop
)
4415 || DECL_EXTERNAL (lhsop
) || TREE_PUBLIC (lhsop
)))
4416 make_escape_constraint (rhsop
);
4417 /* If this is a conversion of a non-restrict pointer to a
4418 restrict pointer track it with a new heapvar. */
4419 else if (gimple_assign_cast_p (t
)
4420 && POINTER_TYPE_P (TREE_TYPE (rhsop
))
4421 && POINTER_TYPE_P (TREE_TYPE (lhsop
))
4422 && !TYPE_RESTRICT (TREE_TYPE (rhsop
))
4423 && TYPE_RESTRICT (TREE_TYPE (lhsop
)))
4424 make_constraint_from_restrict (get_vi_for_tree (lhsop
),
4427 /* For conversions of pointers to non-pointers the pointer escapes. */
4428 else if (gimple_assign_cast_p (t
)
4429 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (t
)))
4430 && !POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (t
))))
4432 make_escape_constraint (gimple_assign_rhs1 (t
));
4434 /* Handle escapes through return. */
4435 else if (gimple_code (t
) == GIMPLE_RETURN
4436 && gimple_return_retval (t
) != NULL_TREE
4437 && could_have_pointers (gimple_return_retval (t
)))
4441 || !(fi
= get_vi_for_tree (cfun
->decl
)))
4442 make_escape_constraint (gimple_return_retval (t
));
4443 else if (in_ipa_mode
4446 struct constraint_expr lhs
;
4447 struct constraint_expr
*rhsp
;
4450 lhs
= get_function_part_constraint (fi
, fi_result
);
4451 get_constraint_for (gimple_return_retval (t
), &rhsc
);
4452 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, rhsp
); i
++)
4453 process_constraint (new_constraint (lhs
, *rhsp
));
4456 /* Handle asms conservatively by adding escape constraints to everything. */
4457 else if (gimple_code (t
) == GIMPLE_ASM
)
4459 unsigned i
, noutputs
;
4460 const char **oconstraints
;
4461 const char *constraint
;
4462 bool allows_mem
, allows_reg
, is_inout
;
4464 noutputs
= gimple_asm_noutputs (t
);
4465 oconstraints
= XALLOCAVEC (const char *, noutputs
);
4467 for (i
= 0; i
< noutputs
; ++i
)
4469 tree link
= gimple_asm_output_op (t
, i
);
4470 tree op
= TREE_VALUE (link
);
4472 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4473 oconstraints
[i
] = constraint
;
4474 parse_output_constraint (&constraint
, i
, 0, 0, &allows_mem
,
4475 &allows_reg
, &is_inout
);
4477 /* A memory constraint makes the address of the operand escape. */
4478 if (!allows_reg
&& allows_mem
)
4479 make_escape_constraint (build_fold_addr_expr (op
));
4481 /* The asm may read global memory, so outputs may point to
4482 any global memory. */
4483 if (op
&& could_have_pointers (op
))
4485 VEC(ce_s
, heap
) *lhsc
= NULL
;
4486 struct constraint_expr rhsc
, *lhsp
;
4488 get_constraint_for (op
, &lhsc
);
4489 rhsc
.var
= nonlocal_id
;
4492 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
4493 process_constraint (new_constraint (*lhsp
, rhsc
));
4494 VEC_free (ce_s
, heap
, lhsc
);
4497 for (i
= 0; i
< gimple_asm_ninputs (t
); ++i
)
4499 tree link
= gimple_asm_input_op (t
, i
);
4500 tree op
= TREE_VALUE (link
);
4502 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4504 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0, oconstraints
,
4505 &allows_mem
, &allows_reg
);
4507 /* A memory constraint makes the address of the operand escape. */
4508 if (!allows_reg
&& allows_mem
)
4509 make_escape_constraint (build_fold_addr_expr (op
));
4510 /* Strictly we'd only need the constraint to ESCAPED if
4511 the asm clobbers memory, otherwise using something
4512 along the lines of per-call clobbers/uses would be enough. */
4513 else if (op
&& could_have_pointers (op
))
4514 make_escape_constraint (op
);
4518 VEC_free (ce_s
, heap
, rhsc
);
4519 VEC_free (ce_s
, heap
, lhsc
);
4523 /* Create a constraint adding to the clobber set of FI the memory
4524 pointed to by PTR. */
4527 process_ipa_clobber (varinfo_t fi
, tree ptr
)
4529 VEC(ce_s
, heap
) *ptrc
= NULL
;
4530 struct constraint_expr
*c
, lhs
;
4532 get_constraint_for (ptr
, &ptrc
);
4533 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4534 for (i
= 0; VEC_iterate (ce_s
, ptrc
, i
, c
); i
++)
4535 process_constraint (new_constraint (lhs
, *c
));
4536 VEC_free (ce_s
, heap
, ptrc
);
4539 /* Walk statement T setting up clobber and use constraints according to the
4540 references found in T. This function is a main part of the
4541 IPA constraint builder. */
4544 find_func_clobbers (gimple origt
)
4547 VEC(ce_s
, heap
) *lhsc
= NULL
;
4548 VEC(ce_s
, heap
) *rhsc
= NULL
;
4551 /* Add constraints for clobbered/used in IPA mode.
4552 We are not interested in what automatic variables are clobbered
4553 or used as we only use the information in the caller to which
4554 they do not escape. */
4555 gcc_assert (in_ipa_mode
);
4557 /* If the stmt refers to memory in any way it better had a VUSE. */
4558 if (gimple_vuse (t
) == NULL_TREE
)
4561 /* We'd better have function information for the current function. */
4562 fi
= lookup_vi_for_tree (cfun
->decl
);
4563 gcc_assert (fi
!= NULL
);
4565 /* Account for stores in assignments and calls. */
4566 if (gimple_vdef (t
) != NULL_TREE
4567 && gimple_has_lhs (t
))
4569 tree lhs
= gimple_get_lhs (t
);
4571 while (handled_component_p (tem
))
4572 tem
= TREE_OPERAND (tem
, 0);
4574 && !auto_var_in_fn_p (tem
, cfun
->decl
))
4575 || INDIRECT_REF_P (tem
))
4577 struct constraint_expr lhsc
, *rhsp
;
4579 lhsc
= get_function_part_constraint (fi
, fi_clobbers
);
4580 get_constraint_for_address_of (lhs
, &rhsc
);
4581 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, rhsp
); i
++)
4582 process_constraint (new_constraint (lhsc
, *rhsp
));
4583 VEC_free (ce_s
, heap
, rhsc
);
4587 /* Account for uses in assigments and returns. */
4588 if (gimple_assign_single_p (t
)
4589 || (gimple_code (t
) == GIMPLE_RETURN
4590 && gimple_return_retval (t
) != NULL_TREE
))
4592 tree rhs
= (gimple_assign_single_p (t
)
4593 ? gimple_assign_rhs1 (t
) : gimple_return_retval (t
));
4595 while (handled_component_p (tem
))
4596 tem
= TREE_OPERAND (tem
, 0);
4598 && !auto_var_in_fn_p (tem
, cfun
->decl
))
4599 || INDIRECT_REF_P (tem
))
4601 struct constraint_expr lhs
, *rhsp
;
4603 lhs
= get_function_part_constraint (fi
, fi_uses
);
4604 get_constraint_for_address_of (rhs
, &rhsc
);
4605 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, rhsp
); i
++)
4606 process_constraint (new_constraint (lhs
, *rhsp
));
4607 VEC_free (ce_s
, heap
, rhsc
);
4611 if (is_gimple_call (t
))
4613 varinfo_t cfi
= NULL
;
4614 tree decl
= gimple_call_fndecl (t
);
4615 struct constraint_expr lhs
, rhs
;
4618 /* For builtins we do not have separate function info. For those
4619 we do not generate escapes for we have to generate clobbers/uses. */
4621 && DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
4622 switch (DECL_FUNCTION_CODE (decl
))
4624 /* The following functions use and clobber memory pointed to
4625 by their arguments. */
4626 case BUILT_IN_STRCPY
:
4627 case BUILT_IN_STRNCPY
:
4628 case BUILT_IN_BCOPY
:
4629 case BUILT_IN_MEMCPY
:
4630 case BUILT_IN_MEMMOVE
:
4631 case BUILT_IN_MEMPCPY
:
4632 case BUILT_IN_STPCPY
:
4633 case BUILT_IN_STPNCPY
:
4634 case BUILT_IN_STRCAT
:
4635 case BUILT_IN_STRNCAT
:
4637 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
4638 == BUILT_IN_BCOPY
? 1 : 0));
4639 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
4640 == BUILT_IN_BCOPY
? 0 : 1));
4642 struct constraint_expr
*rhsp
, *lhsp
;
4643 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4644 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4645 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, lhsp
); i
++)
4646 process_constraint (new_constraint (lhs
, *lhsp
));
4647 VEC_free (ce_s
, heap
, lhsc
);
4648 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4649 lhs
= get_function_part_constraint (fi
, fi_uses
);
4650 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, rhsp
); i
++)
4651 process_constraint (new_constraint (lhs
, *rhsp
));
4652 VEC_free (ce_s
, heap
, rhsc
);
4655 /* The following function clobbers memory pointed to by
4657 case BUILT_IN_MEMSET
:
4659 tree dest
= gimple_call_arg (t
, 0);
4662 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4663 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4664 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, lhsp
); i
++)
4665 process_constraint (new_constraint (lhs
, *lhsp
));
4666 VEC_free (ce_s
, heap
, lhsc
);
4669 /* The following functions clobber their second and third
4671 case BUILT_IN_SINCOS
:
4672 case BUILT_IN_SINCOSF
:
4673 case BUILT_IN_SINCOSL
:
4675 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
4676 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
4679 /* The following functions clobber their second argument. */
4680 case BUILT_IN_FREXP
:
4681 case BUILT_IN_FREXPF
:
4682 case BUILT_IN_FREXPL
:
4683 case BUILT_IN_LGAMMA_R
:
4684 case BUILT_IN_LGAMMAF_R
:
4685 case BUILT_IN_LGAMMAL_R
:
4686 case BUILT_IN_GAMMA_R
:
4687 case BUILT_IN_GAMMAF_R
:
4688 case BUILT_IN_GAMMAL_R
:
4690 case BUILT_IN_MODFF
:
4691 case BUILT_IN_MODFL
:
4693 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
4696 /* The following functions clobber their third argument. */
4697 case BUILT_IN_REMQUO
:
4698 case BUILT_IN_REMQUOF
:
4699 case BUILT_IN_REMQUOL
:
4701 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
4704 /* The following functions neither read nor clobber memory. */
4707 /* Trampolines are of no interest to us. */
4708 case BUILT_IN_INIT_TRAMPOLINE
:
4709 case BUILT_IN_ADJUST_TRAMPOLINE
:
4711 case BUILT_IN_VA_START
:
4712 case BUILT_IN_VA_END
:
4714 /* printf-style functions may have hooks to set pointers to
4715 point to somewhere into the generated string. Leave them
4716 for a later excercise... */
4718 /* Fallthru to general call handling. */;
4721 /* Parameters passed by value are used. */
4722 lhs
= get_function_part_constraint (fi
, fi_uses
);
4723 for (i
= 0; i
< gimple_call_num_args (t
); i
++)
4725 struct constraint_expr
*rhsp
;
4726 tree arg
= gimple_call_arg (t
, i
);
4728 if (TREE_CODE (arg
) == SSA_NAME
4729 || is_gimple_min_invariant (arg
))
4732 get_constraint_for_address_of (arg
, &rhsc
);
4733 for (j
= 0; VEC_iterate (ce_s
, rhsc
, j
, rhsp
); j
++)
4734 process_constraint (new_constraint (lhs
, *rhsp
));
4735 VEC_free (ce_s
, heap
, rhsc
);
4738 /* Build constraints for propagating clobbers/uses along the
4740 cfi
= get_fi_for_callee (t
);
4741 if (cfi
->id
== anything_id
)
4743 if (gimple_vdef (t
))
4744 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
4746 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
4751 /* For callees without function info (that's external functions),
4752 ESCAPED is clobbered and used. */
4753 if (gimple_call_fndecl (t
)
4754 && !cfi
->is_fn_info
)
4758 if (gimple_vdef (t
))
4759 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
4761 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
), escaped_id
);
4763 /* Also honor the call statement use/clobber info. */
4764 if ((vi
= lookup_call_clobber_vi (t
)) != NULL
)
4765 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
4767 if ((vi
= lookup_call_use_vi (t
)) != NULL
)
4768 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
),
4773 /* Otherwise the caller clobbers and uses what the callee does.
4774 ??? This should use a new complex constraint that filters
4775 local variables of the callee. */
4776 if (gimple_vdef (t
))
4778 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4779 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
4780 process_constraint (new_constraint (lhs
, rhs
));
4782 lhs
= get_function_part_constraint (fi
, fi_uses
);
4783 rhs
= get_function_part_constraint (cfi
, fi_uses
);
4784 process_constraint (new_constraint (lhs
, rhs
));
4786 else if (gimple_code (t
) == GIMPLE_ASM
)
4788 /* ??? Ick. We can do better. */
4789 if (gimple_vdef (t
))
4790 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
4792 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
4796 VEC_free (ce_s
, heap
, rhsc
);
4800 /* Find the first varinfo in the same variable as START that overlaps with
4801 OFFSET. Return NULL if we can't find one. */
4804 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
4806 /* If the offset is outside of the variable, bail out. */
4807 if (offset
>= start
->fullsize
)
4810 /* If we cannot reach offset from start, lookup the first field
4811 and start from there. */
4812 if (start
->offset
> offset
)
4813 start
= lookup_vi_for_tree (start
->decl
);
4817 /* We may not find a variable in the field list with the actual
4818 offset when when we have glommed a structure to a variable.
4819 In that case, however, offset should still be within the size
4821 if (offset
>= start
->offset
4822 && (offset
- start
->offset
) < start
->size
)
4831 /* Find the first varinfo in the same variable as START that overlaps with
4832 OFFSET. If there is no such varinfo the varinfo directly preceding
4833 OFFSET is returned. */
4836 first_or_preceding_vi_for_offset (varinfo_t start
,
4837 unsigned HOST_WIDE_INT offset
)
4839 /* If we cannot reach offset from start, lookup the first field
4840 and start from there. */
4841 if (start
->offset
> offset
)
4842 start
= lookup_vi_for_tree (start
->decl
);
4844 /* We may not find a variable in the field list with the actual
4845 offset when when we have glommed a structure to a variable.
4846 In that case, however, offset should still be within the size
4848 If we got beyond the offset we look for return the field
4849 directly preceding offset which may be the last field. */
4851 && offset
>= start
->offset
4852 && !((offset
- start
->offset
) < start
->size
))
4853 start
= start
->next
;
4859 /* This structure is used during pushing fields onto the fieldstack
4860 to track the offset of the field, since bitpos_of_field gives it
4861 relative to its immediate containing type, and we want it relative
4862 to the ultimate containing object. */
4866 /* Offset from the base of the base containing object to this field. */
4867 HOST_WIDE_INT offset
;
4869 /* Size, in bits, of the field. */
4870 unsigned HOST_WIDE_INT size
;
4872 unsigned has_unknown_size
: 1;
4874 unsigned may_have_pointers
: 1;
4876 unsigned only_restrict_pointers
: 1;
4878 typedef struct fieldoff fieldoff_s
;
4880 DEF_VEC_O(fieldoff_s
);
4881 DEF_VEC_ALLOC_O(fieldoff_s
,heap
);
4883 /* qsort comparison function for two fieldoff's PA and PB */
4886 fieldoff_compare (const void *pa
, const void *pb
)
4888 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
4889 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
4890 unsigned HOST_WIDE_INT foasize
, fobsize
;
4892 if (foa
->offset
< fob
->offset
)
4894 else if (foa
->offset
> fob
->offset
)
4897 foasize
= foa
->size
;
4898 fobsize
= fob
->size
;
4899 if (foasize
< fobsize
)
4901 else if (foasize
> fobsize
)
4906 /* Sort a fieldstack according to the field offset and sizes. */
4908 sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
4910 qsort (VEC_address (fieldoff_s
, fieldstack
),
4911 VEC_length (fieldoff_s
, fieldstack
),
4912 sizeof (fieldoff_s
),
4916 /* Return true if V is a tree that we can have subvars for.
4917 Normally, this is any aggregate type. Also complex
4918 types which are not gimple registers can have subvars. */
4921 var_can_have_subvars (const_tree v
)
4923 /* Volatile variables should never have subvars. */
4924 if (TREE_THIS_VOLATILE (v
))
4927 /* Non decls or memory tags can never have subvars. */
4931 /* Aggregates without overlapping fields can have subvars. */
4932 if (TREE_CODE (TREE_TYPE (v
)) == RECORD_TYPE
)
4938 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4939 the fields of TYPE onto fieldstack, recording their offsets along
4942 OFFSET is used to keep track of the offset in this entire
4943 structure, rather than just the immediately containing structure.
4944 Returns false if the caller is supposed to handle the field we
4948 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
4949 HOST_WIDE_INT offset
, bool must_have_pointers_p
)
4952 bool empty_p
= true;
4954 if (TREE_CODE (type
) != RECORD_TYPE
)
4957 /* If the vector of fields is growing too big, bail out early.
4958 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4960 if (VEC_length (fieldoff_s
, *fieldstack
) > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
4963 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
4964 if (TREE_CODE (field
) == FIELD_DECL
)
4967 HOST_WIDE_INT foff
= bitpos_of_field (field
);
4969 if (!var_can_have_subvars (field
)
4970 || TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
4971 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
)
4973 else if (!push_fields_onto_fieldstack
4974 (TREE_TYPE (field
), fieldstack
, offset
+ foff
,
4975 must_have_pointers_p
)
4976 && (DECL_SIZE (field
)
4977 && !integer_zerop (DECL_SIZE (field
))))
4978 /* Empty structures may have actual size, like in C++. So
4979 see if we didn't push any subfields and the size is
4980 nonzero, push the field onto the stack. */
4985 fieldoff_s
*pair
= NULL
;
4986 bool has_unknown_size
= false;
4988 if (!VEC_empty (fieldoff_s
, *fieldstack
))
4989 pair
= VEC_last (fieldoff_s
, *fieldstack
);
4991 if (!DECL_SIZE (field
)
4992 || !host_integerp (DECL_SIZE (field
), 1))
4993 has_unknown_size
= true;
4995 /* If adjacent fields do not contain pointers merge them. */
4997 && !pair
->may_have_pointers
4998 && !pair
->has_unknown_size
4999 && !has_unknown_size
5000 && pair
->offset
+ (HOST_WIDE_INT
)pair
->size
== offset
+ foff
5001 && !must_have_pointers_p
5002 && !could_have_pointers (field
))
5004 pair
->size
+= TREE_INT_CST_LOW (DECL_SIZE (field
));
5008 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
5009 pair
->offset
= offset
+ foff
;
5010 pair
->has_unknown_size
= has_unknown_size
;
5011 if (!has_unknown_size
)
5012 pair
->size
= TREE_INT_CST_LOW (DECL_SIZE (field
));
5015 pair
->may_have_pointers
5016 = must_have_pointers_p
|| could_have_pointers (field
);
5017 pair
->only_restrict_pointers
5018 = (!has_unknown_size
5019 && POINTER_TYPE_P (TREE_TYPE (field
))
5020 && TYPE_RESTRICT (TREE_TYPE (field
)));
5030 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5031 if it is a varargs function. */
5034 count_num_arguments (tree decl
, bool *is_varargs
)
5036 unsigned int num
= 0;
5039 /* Capture named arguments for K&R functions. They do not
5040 have a prototype and thus no TYPE_ARG_TYPES. */
5041 for (t
= DECL_ARGUMENTS (decl
); t
; t
= TREE_CHAIN (t
))
5044 /* Check if the function has variadic arguments. */
5045 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
)); t
; t
= TREE_CHAIN (t
))
5046 if (TREE_VALUE (t
) == void_type_node
)
5054 /* Creation function node for DECL, using NAME, and return the index
5055 of the variable we've created for the function. */
5058 create_function_info_for (tree decl
, const char *name
)
5060 struct function
*fn
= DECL_STRUCT_FUNCTION (decl
);
5061 varinfo_t vi
, prev_vi
;
5064 bool is_varargs
= false;
5065 unsigned int num_args
= count_num_arguments (decl
, &is_varargs
);
5067 /* Create the variable info. */
5069 vi
= new_var_info (decl
, name
);
5072 vi
->fullsize
= fi_parm_base
+ num_args
;
5074 vi
->may_have_pointers
= false;
5077 insert_vi_for_tree (vi
->decl
, vi
);
5081 /* Create a variable for things the function clobbers and one for
5082 things the function uses. */
5084 varinfo_t clobbervi
, usevi
;
5085 const char *newname
;
5088 asprintf (&tempname
, "%s.clobber", name
);
5089 newname
= ggc_strdup (tempname
);
5092 clobbervi
= new_var_info (NULL
, newname
);
5093 clobbervi
->offset
= fi_clobbers
;
5094 clobbervi
->size
= 1;
5095 clobbervi
->fullsize
= vi
->fullsize
;
5096 clobbervi
->is_full_var
= true;
5097 clobbervi
->is_global_var
= false;
5098 gcc_assert (prev_vi
->offset
< clobbervi
->offset
);
5099 prev_vi
->next
= clobbervi
;
5100 prev_vi
= clobbervi
;
5102 asprintf (&tempname
, "%s.use", name
);
5103 newname
= ggc_strdup (tempname
);
5106 usevi
= new_var_info (NULL
, newname
);
5107 usevi
->offset
= fi_uses
;
5109 usevi
->fullsize
= vi
->fullsize
;
5110 usevi
->is_full_var
= true;
5111 usevi
->is_global_var
= false;
5112 gcc_assert (prev_vi
->offset
< usevi
->offset
);
5113 prev_vi
->next
= usevi
;
5117 /* And one for the static chain. */
5118 if (fn
->static_chain_decl
!= NULL_TREE
)
5121 const char *newname
;
5124 asprintf (&tempname
, "%s.chain", name
);
5125 newname
= ggc_strdup (tempname
);
5128 chainvi
= new_var_info (fn
->static_chain_decl
, newname
);
5129 chainvi
->offset
= fi_static_chain
;
5131 chainvi
->fullsize
= vi
->fullsize
;
5132 chainvi
->is_full_var
= true;
5133 chainvi
->is_global_var
= false;
5134 gcc_assert (prev_vi
->offset
< chainvi
->offset
);
5135 prev_vi
->next
= chainvi
;
5137 insert_vi_for_tree (fn
->static_chain_decl
, chainvi
);
5140 /* Create a variable for the return var. */
5141 if (DECL_RESULT (decl
) != NULL
5142 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
5145 const char *newname
;
5147 tree resultdecl
= decl
;
5149 if (DECL_RESULT (decl
))
5150 resultdecl
= DECL_RESULT (decl
);
5152 asprintf (&tempname
, "%s.result", name
);
5153 newname
= ggc_strdup (tempname
);
5156 resultvi
= new_var_info (resultdecl
, newname
);
5157 resultvi
->offset
= fi_result
;
5159 resultvi
->fullsize
= vi
->fullsize
;
5160 resultvi
->is_full_var
= true;
5161 if (DECL_RESULT (decl
))
5162 resultvi
->may_have_pointers
= could_have_pointers (DECL_RESULT (decl
));
5163 gcc_assert (prev_vi
->offset
< resultvi
->offset
);
5164 prev_vi
->next
= resultvi
;
5166 if (DECL_RESULT (decl
))
5167 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
5170 /* Set up variables for each argument. */
5171 arg
= DECL_ARGUMENTS (decl
);
5172 for (i
= 0; i
< num_args
; i
++)
5175 const char *newname
;
5177 tree argdecl
= decl
;
5182 asprintf (&tempname
, "%s.arg%d", name
, i
);
5183 newname
= ggc_strdup (tempname
);
5186 argvi
= new_var_info (argdecl
, newname
);
5187 argvi
->offset
= fi_parm_base
+ i
;
5189 argvi
->is_full_var
= true;
5190 argvi
->fullsize
= vi
->fullsize
;
5192 argvi
->may_have_pointers
= could_have_pointers (arg
);
5193 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5194 prev_vi
->next
= argvi
;
5198 insert_vi_for_tree (arg
, argvi
);
5199 arg
= TREE_CHAIN (arg
);
5203 /* Add one representative for all further args. */
5207 const char *newname
;
5211 asprintf (&tempname
, "%s.varargs", name
);
5212 newname
= ggc_strdup (tempname
);
5215 /* We need sth that can be pointed to for va_start. */
5216 decl
= create_tmp_var_raw (ptr_type_node
, name
);
5219 argvi
= new_var_info (decl
, newname
);
5220 argvi
->offset
= fi_parm_base
+ num_args
;
5222 argvi
->is_full_var
= true;
5223 argvi
->is_heap_var
= true;
5224 argvi
->fullsize
= vi
->fullsize
;
5225 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5226 prev_vi
->next
= argvi
;
5234 /* Return true if FIELDSTACK contains fields that overlap.
5235 FIELDSTACK is assumed to be sorted by offset. */
5238 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
5240 fieldoff_s
*fo
= NULL
;
5242 HOST_WIDE_INT lastoffset
= -1;
5244 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
5246 if (fo
->offset
== lastoffset
)
5248 lastoffset
= fo
->offset
;
5253 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5254 This will also create any varinfo structures necessary for fields
5258 create_variable_info_for_1 (tree decl
, const char *name
)
5260 varinfo_t vi
, newvi
;
5261 tree decl_type
= TREE_TYPE (decl
);
5262 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decl_type
);
5263 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
5268 || !host_integerp (declsize
, 1))
5270 vi
= new_var_info (decl
, name
);
5274 vi
->is_unknown_size_var
= true;
5275 vi
->is_full_var
= true;
5276 vi
->may_have_pointers
= could_have_pointers (decl
);
5280 /* Collect field information. */
5281 if (use_field_sensitive
5282 && var_can_have_subvars (decl
)
5283 /* ??? Force us to not use subfields for global initializers
5284 in IPA mode. Else we'd have to parse arbitrary initializers. */
5286 && is_global_var (decl
)
5287 && DECL_INITIAL (decl
)))
5289 fieldoff_s
*fo
= NULL
;
5290 bool notokay
= false;
5293 push_fields_onto_fieldstack (decl_type
, &fieldstack
, 0,
5295 || DECL_EXTERNAL (decl
)
5296 || TREE_ADDRESSABLE (decl
));
5298 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
5299 if (fo
->has_unknown_size
5306 /* We can't sort them if we have a field with a variable sized type,
5307 which will make notokay = true. In that case, we are going to return
5308 without creating varinfos for the fields anyway, so sorting them is a
5312 sort_fieldstack (fieldstack
);
5313 /* Due to some C++ FE issues, like PR 22488, we might end up
5314 what appear to be overlapping fields even though they,
5315 in reality, do not overlap. Until the C++ FE is fixed,
5316 we will simply disable field-sensitivity for these cases. */
5317 notokay
= check_for_overlaps (fieldstack
);
5321 VEC_free (fieldoff_s
, heap
, fieldstack
);
5324 /* If we didn't end up collecting sub-variables create a full
5325 variable for the decl. */
5326 if (VEC_length (fieldoff_s
, fieldstack
) <= 1
5327 || VEC_length (fieldoff_s
, fieldstack
) > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5329 vi
= new_var_info (decl
, name
);
5331 vi
->may_have_pointers
= could_have_pointers (decl
);
5332 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
5333 vi
->size
= vi
->fullsize
;
5334 vi
->is_full_var
= true;
5335 VEC_free (fieldoff_s
, heap
, fieldstack
);
5339 vi
= new_var_info (decl
, name
);
5340 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
5341 for (i
= 0, newvi
= vi
;
5342 VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
5343 ++i
, newvi
= newvi
->next
)
5345 const char *newname
= "NULL";
5350 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
5351 "+" HOST_WIDE_INT_PRINT_DEC
, name
, fo
->offset
, fo
->size
);
5352 newname
= ggc_strdup (tempname
);
5355 newvi
->name
= newname
;
5356 newvi
->offset
= fo
->offset
;
5357 newvi
->size
= fo
->size
;
5358 newvi
->fullsize
= vi
->fullsize
;
5359 newvi
->may_have_pointers
= fo
->may_have_pointers
;
5360 newvi
->only_restrict_pointers
= fo
->only_restrict_pointers
;
5361 if (i
+ 1 < VEC_length (fieldoff_s
, fieldstack
))
5362 newvi
->next
= new_var_info (decl
, name
);
5365 VEC_free (fieldoff_s
, heap
, fieldstack
);
5371 create_variable_info_for (tree decl
, const char *name
)
5373 varinfo_t vi
= create_variable_info_for_1 (decl
, name
);
5374 unsigned int id
= vi
->id
;
5376 insert_vi_for_tree (decl
, vi
);
5378 /* Create initial constraints for globals. */
5379 for (; vi
; vi
= vi
->next
)
5381 if (!vi
->may_have_pointers
5382 || !vi
->is_global_var
)
5385 /* Mark global restrict qualified pointers. */
5386 if ((POINTER_TYPE_P (TREE_TYPE (decl
))
5387 && TYPE_RESTRICT (TREE_TYPE (decl
)))
5388 || vi
->only_restrict_pointers
)
5389 make_constraint_from_restrict (vi
, "GLOBAL_RESTRICT");
5391 /* For escaped variables initialize them from nonlocal. */
5393 || DECL_EXTERNAL (decl
) || TREE_PUBLIC (decl
))
5394 make_copy_constraint (vi
, nonlocal_id
);
5396 /* If this is a global variable with an initializer and we are in
5397 IPA mode generate constraints for it. In non-IPA mode
5398 the initializer from nonlocal is all we need. */
5400 && DECL_INITIAL (decl
))
5402 VEC (ce_s
, heap
) *rhsc
= NULL
;
5403 struct constraint_expr lhs
, *rhsp
;
5405 get_constraint_for (DECL_INITIAL (decl
), &rhsc
);
5409 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, rhsp
); ++i
)
5410 process_constraint (new_constraint (lhs
, *rhsp
));
5411 /* If this is a variable that escapes from the unit
5412 the initializer escapes as well. */
5413 if (DECL_EXTERNAL (decl
) || TREE_PUBLIC (decl
))
5415 lhs
.var
= escaped_id
;
5418 for (i
= 0; VEC_iterate (ce_s
, rhsc
, i
, rhsp
); ++i
)
5419 process_constraint (new_constraint (lhs
, *rhsp
));
5421 VEC_free (ce_s
, heap
, rhsc
);
5428 /* Print out the points-to solution for VAR to FILE. */
5431 dump_solution_for_var (FILE *file
, unsigned int var
)
5433 varinfo_t vi
= get_varinfo (var
);
5437 /* Dump the solution for unified vars anyway, this avoids difficulties
5438 in scanning dumps in the testsuite. */
5439 fprintf (file
, "%s = { ", vi
->name
);
5440 vi
= get_varinfo (find (var
));
5441 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
5442 fprintf (file
, "%s ", get_varinfo (i
)->name
);
5443 fprintf (file
, "}");
5445 /* But note when the variable was unified. */
5447 fprintf (file
, " same as %s", vi
->name
);
5449 fprintf (file
, "\n");
5452 /* Print the points-to solution for VAR to stdout. */
5455 debug_solution_for_var (unsigned int var
)
5457 dump_solution_for_var (stdout
, var
);
5460 /* Create varinfo structures for all of the variables in the
5461 function for intraprocedural mode. */
5464 intra_create_variable_infos (void)
5468 /* For each incoming pointer argument arg, create the constraint ARG
5469 = NONLOCAL or a dummy variable if it is a restrict qualified
5470 passed-by-reference argument. */
5471 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
5475 if (!could_have_pointers (t
))
5478 /* For restrict qualified pointers to objects passed by
5479 reference build a real representative for the pointed-to object. */
5480 if (DECL_BY_REFERENCE (t
)
5481 && POINTER_TYPE_P (TREE_TYPE (t
))
5482 && TYPE_RESTRICT (TREE_TYPE (t
)))
5484 struct constraint_expr lhsc
, rhsc
;
5486 tree heapvar
= heapvar_lookup (t
, 0);
5487 if (heapvar
== NULL_TREE
)
5490 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)),
5492 DECL_EXTERNAL (heapvar
) = 1;
5493 heapvar_insert (t
, 0, heapvar
);
5494 ann
= get_var_ann (heapvar
);
5495 ann
->is_heapvar
= 1;
5497 if (gimple_referenced_vars (cfun
))
5498 add_referenced_var (heapvar
);
5499 lhsc
.var
= get_vi_for_tree (t
)->id
;
5502 rhsc
.var
= (vi
= get_vi_for_tree (heapvar
))->id
;
5503 rhsc
.type
= ADDRESSOF
;
5505 process_constraint (new_constraint (lhsc
, rhsc
));
5506 vi
->is_restrict_var
= 1;
5510 for (p
= get_vi_for_tree (t
); p
; p
= p
->next
)
5512 if (p
->may_have_pointers
)
5513 make_constraint_from (p
, nonlocal_id
);
5514 if (p
->only_restrict_pointers
)
5515 make_constraint_from_restrict (p
, "PARM_RESTRICT");
5517 if (POINTER_TYPE_P (TREE_TYPE (t
))
5518 && TYPE_RESTRICT (TREE_TYPE (t
)))
5519 make_constraint_from_restrict (get_vi_for_tree (t
), "PARM_RESTRICT");
5522 /* Add a constraint for a result decl that is passed by reference. */
5523 if (DECL_RESULT (cfun
->decl
)
5524 && DECL_BY_REFERENCE (DECL_RESULT (cfun
->decl
)))
5526 varinfo_t p
, result_vi
= get_vi_for_tree (DECL_RESULT (cfun
->decl
));
5528 for (p
= result_vi
; p
; p
= p
->next
)
5529 make_constraint_from (p
, nonlocal_id
);
5532 /* Add a constraint for the incoming static chain parameter. */
5533 if (cfun
->static_chain_decl
!= NULL_TREE
)
5535 varinfo_t p
, chain_vi
= get_vi_for_tree (cfun
->static_chain_decl
);
5537 for (p
= chain_vi
; p
; p
= p
->next
)
5538 make_constraint_from (p
, nonlocal_id
);
5542 /* Structure used to put solution bitmaps in a hashtable so they can
5543 be shared among variables with the same points-to set. */
5545 typedef struct shared_bitmap_info
5549 } *shared_bitmap_info_t
;
5550 typedef const struct shared_bitmap_info
*const_shared_bitmap_info_t
;
5552 static htab_t shared_bitmap_table
;
5554 /* Hash function for a shared_bitmap_info_t */
5557 shared_bitmap_hash (const void *p
)
5559 const_shared_bitmap_info_t
const bi
= (const_shared_bitmap_info_t
) p
;
5560 return bi
->hashcode
;
5563 /* Equality function for two shared_bitmap_info_t's. */
5566 shared_bitmap_eq (const void *p1
, const void *p2
)
5568 const_shared_bitmap_info_t
const sbi1
= (const_shared_bitmap_info_t
) p1
;
5569 const_shared_bitmap_info_t
const sbi2
= (const_shared_bitmap_info_t
) p2
;
5570 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
5573 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
5574 existing instance if there is one, NULL otherwise. */
5577 shared_bitmap_lookup (bitmap pt_vars
)
5580 struct shared_bitmap_info sbi
;
5582 sbi
.pt_vars
= pt_vars
;
5583 sbi
.hashcode
= bitmap_hash (pt_vars
);
5585 slot
= htab_find_slot_with_hash (shared_bitmap_table
, &sbi
,
5586 sbi
.hashcode
, NO_INSERT
);
5590 return ((shared_bitmap_info_t
) *slot
)->pt_vars
;
5594 /* Add a bitmap to the shared bitmap hashtable. */
5597 shared_bitmap_add (bitmap pt_vars
)
5600 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
5602 sbi
->pt_vars
= pt_vars
;
5603 sbi
->hashcode
= bitmap_hash (pt_vars
);
5605 slot
= htab_find_slot_with_hash (shared_bitmap_table
, sbi
,
5606 sbi
->hashcode
, INSERT
);
5607 gcc_assert (!*slot
);
5608 *slot
= (void *) sbi
;
5612 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
5615 set_uids_in_ptset (bitmap into
, bitmap from
, struct pt_solution
*pt
)
5620 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
5622 varinfo_t vi
= get_varinfo (i
);
5624 /* The only artificial variables that are allowed in a may-alias
5625 set are heap variables. */
5626 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
5629 if (TREE_CODE (vi
->decl
) == VAR_DECL
5630 || TREE_CODE (vi
->decl
) == PARM_DECL
5631 || TREE_CODE (vi
->decl
) == RESULT_DECL
)
5633 /* If we are in IPA mode we will not recompute points-to
5634 sets after inlining so make sure they stay valid. */
5636 && !DECL_PT_UID_SET_P (vi
->decl
))
5637 SET_DECL_PT_UID (vi
->decl
, DECL_UID (vi
->decl
));
5639 /* Add the decl to the points-to set. Note that the points-to
5640 set contains global variables. */
5641 bitmap_set_bit (into
, DECL_PT_UID (vi
->decl
));
5642 if (vi
->is_global_var
)
5643 pt
->vars_contains_global
= true;
5649 /* Compute the points-to solution *PT for the variable VI. */
5652 find_what_var_points_to (varinfo_t orig_vi
, struct pt_solution
*pt
)
5656 bitmap finished_solution
;
5660 memset (pt
, 0, sizeof (struct pt_solution
));
5662 /* This variable may have been collapsed, let's get the real
5664 vi
= get_varinfo (find (orig_vi
->id
));
5666 /* Translate artificial variables into SSA_NAME_PTR_INFO
5668 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
5670 varinfo_t vi
= get_varinfo (i
);
5672 if (vi
->is_artificial_var
)
5674 if (vi
->id
== nothing_id
)
5676 else if (vi
->id
== escaped_id
)
5679 pt
->ipa_escaped
= 1;
5683 else if (vi
->id
== nonlocal_id
)
5685 else if (vi
->is_heap_var
)
5686 /* We represent heapvars in the points-to set properly. */
5688 else if (vi
->id
== readonly_id
)
5691 else if (vi
->id
== anything_id
5692 || vi
->id
== integer_id
)
5695 if (vi
->is_restrict_var
)
5696 pt
->vars_contains_restrict
= true;
5699 /* Instead of doing extra work, simply do not create
5700 elaborate points-to information for pt_anything pointers. */
5702 && (orig_vi
->is_artificial_var
5703 || !pt
->vars_contains_restrict
))
5706 /* Share the final set of variables when possible. */
5707 finished_solution
= BITMAP_GGC_ALLOC ();
5708 stats
.points_to_sets_created
++;
5710 set_uids_in_ptset (finished_solution
, vi
->solution
, pt
);
5711 result
= shared_bitmap_lookup (finished_solution
);
5714 shared_bitmap_add (finished_solution
);
5715 pt
->vars
= finished_solution
;
5720 bitmap_clear (finished_solution
);
5724 /* Given a pointer variable P, fill in its points-to set. */
5727 find_what_p_points_to (tree p
)
5729 struct ptr_info_def
*pi
;
5733 /* For parameters, get at the points-to set for the actual parm
5735 if (TREE_CODE (p
) == SSA_NAME
5736 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
5737 && SSA_NAME_IS_DEFAULT_DEF (p
))
5738 lookup_p
= SSA_NAME_VAR (p
);
5740 vi
= lookup_vi_for_tree (lookup_p
);
5744 pi
= get_ptr_info (p
);
5745 find_what_var_points_to (vi
, &pi
->pt
);
5749 /* Query statistics for points-to solutions. */
5752 unsigned HOST_WIDE_INT pt_solution_includes_may_alias
;
5753 unsigned HOST_WIDE_INT pt_solution_includes_no_alias
;
5754 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias
;
5755 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias
;
5759 dump_pta_stats (FILE *s
)
5761 fprintf (s
, "\nPTA query stats:\n");
5762 fprintf (s
, " pt_solution_includes: "
5763 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
5764 HOST_WIDE_INT_PRINT_DEC
" queries\n",
5765 pta_stats
.pt_solution_includes_no_alias
,
5766 pta_stats
.pt_solution_includes_no_alias
5767 + pta_stats
.pt_solution_includes_may_alias
);
5768 fprintf (s
, " pt_solutions_intersect: "
5769 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
5770 HOST_WIDE_INT_PRINT_DEC
" queries\n",
5771 pta_stats
.pt_solutions_intersect_no_alias
,
5772 pta_stats
.pt_solutions_intersect_no_alias
5773 + pta_stats
.pt_solutions_intersect_may_alias
);
5777 /* Reset the points-to solution *PT to a conservative default
5778 (point to anything). */
5781 pt_solution_reset (struct pt_solution
*pt
)
5783 memset (pt
, 0, sizeof (struct pt_solution
));
5784 pt
->anything
= true;
5787 /* Set the points-to solution *PT to point only to the variables
5788 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
5789 global variables and VARS_CONTAINS_RESTRICT specifies whether
5790 it contains restrict tag variables. */
5793 pt_solution_set (struct pt_solution
*pt
, bitmap vars
,
5794 bool vars_contains_global
, bool vars_contains_restrict
)
5796 memset (pt
, 0, sizeof (struct pt_solution
));
5798 pt
->vars_contains_global
= vars_contains_global
;
5799 pt
->vars_contains_restrict
= vars_contains_restrict
;
5802 /* Computes the union of the points-to solutions *DEST and *SRC and
5803 stores the result in *DEST. This changes the points-to bitmap
5804 of *DEST and thus may not be used if that might be shared.
5805 The points-to bitmap of *SRC and *DEST will not be shared after
5806 this function if they were not before. */
5809 pt_solution_ior_into (struct pt_solution
*dest
, struct pt_solution
*src
)
5811 dest
->anything
|= src
->anything
;
5814 pt_solution_reset (dest
);
5818 dest
->nonlocal
|= src
->nonlocal
;
5819 dest
->escaped
|= src
->escaped
;
5820 dest
->ipa_escaped
|= src
->ipa_escaped
;
5821 dest
->null
|= src
->null
;
5822 dest
->vars_contains_global
|= src
->vars_contains_global
;
5823 dest
->vars_contains_restrict
|= src
->vars_contains_restrict
;
5828 dest
->vars
= BITMAP_GGC_ALLOC ();
5829 bitmap_ior_into (dest
->vars
, src
->vars
);
5832 /* Return true if the points-to solution *PT is empty. */
5835 pt_solution_empty_p (struct pt_solution
*pt
)
5842 && !bitmap_empty_p (pt
->vars
))
5845 /* If the solution includes ESCAPED, check if that is empty. */
5847 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
5850 /* If the solution includes ESCAPED, check if that is empty. */
5852 && !pt_solution_empty_p (&ipa_escaped_pt
))
5858 /* Return true if the points-to solution *PT includes global memory. */
5861 pt_solution_includes_global (struct pt_solution
*pt
)
5865 || pt
->vars_contains_global
)
5869 return pt_solution_includes_global (&cfun
->gimple_df
->escaped
);
5871 if (pt
->ipa_escaped
)
5872 return pt_solution_includes_global (&ipa_escaped_pt
);
5874 /* ??? This predicate is not correct for the IPA-PTA solution
5875 as we do not properly distinguish between unit escape points
5876 and global variables. */
5877 if (cfun
->gimple_df
->ipa_pta
)
5883 /* Return true if the points-to solution *PT includes the variable
5884 declaration DECL. */
5887 pt_solution_includes_1 (struct pt_solution
*pt
, const_tree decl
)
5893 && is_global_var (decl
))
5897 && bitmap_bit_p (pt
->vars
, DECL_PT_UID (decl
)))
5900 /* If the solution includes ESCAPED, check it. */
5902 && pt_solution_includes_1 (&cfun
->gimple_df
->escaped
, decl
))
5905 /* If the solution includes ESCAPED, check it. */
5907 && pt_solution_includes_1 (&ipa_escaped_pt
, decl
))
5914 pt_solution_includes (struct pt_solution
*pt
, const_tree decl
)
5916 bool res
= pt_solution_includes_1 (pt
, decl
);
5918 ++pta_stats
.pt_solution_includes_may_alias
;
5920 ++pta_stats
.pt_solution_includes_no_alias
;
5924 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
5928 pt_solutions_intersect_1 (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
5930 if (pt1
->anything
|| pt2
->anything
)
5933 /* If either points to unknown global memory and the other points to
5934 any global memory they alias. */
5937 || pt2
->vars_contains_global
))
5939 && pt1
->vars_contains_global
))
5942 /* Check the escaped solution if required. */
5943 if ((pt1
->escaped
|| pt2
->escaped
)
5944 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
5946 /* If both point to escaped memory and that solution
5947 is not empty they alias. */
5948 if (pt1
->escaped
&& pt2
->escaped
)
5951 /* If either points to escaped memory see if the escaped solution
5952 intersects with the other. */
5954 && pt_solutions_intersect_1 (&cfun
->gimple_df
->escaped
, pt2
))
5956 && pt_solutions_intersect_1 (&cfun
->gimple_df
->escaped
, pt1
)))
5960 /* Check the escaped solution if required.
5961 ??? Do we need to check the local against the IPA escaped sets? */
5962 if ((pt1
->ipa_escaped
|| pt2
->ipa_escaped
)
5963 && !pt_solution_empty_p (&ipa_escaped_pt
))
5965 /* If both point to escaped memory and that solution
5966 is not empty they alias. */
5967 if (pt1
->ipa_escaped
&& pt2
->ipa_escaped
)
5970 /* If either points to escaped memory see if the escaped solution
5971 intersects with the other. */
5972 if ((pt1
->ipa_escaped
5973 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt2
))
5974 || (pt2
->ipa_escaped
5975 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt1
)))
5979 /* Now both pointers alias if their points-to solution intersects. */
5982 && bitmap_intersect_p (pt1
->vars
, pt2
->vars
));
5986 pt_solutions_intersect (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
5988 bool res
= pt_solutions_intersect_1 (pt1
, pt2
);
5990 ++pta_stats
.pt_solutions_intersect_may_alias
;
5992 ++pta_stats
.pt_solutions_intersect_no_alias
;
5996 /* Return true if both points-to solutions PT1 and PT2 for two restrict
5997 qualified pointers are possibly based on the same pointer. */
6000 pt_solutions_same_restrict_base (struct pt_solution
*pt1
,
6001 struct pt_solution
*pt2
)
6003 /* If we deal with points-to solutions of two restrict qualified
6004 pointers solely rely on the pointed-to variable bitmap intersection.
6005 For two pointers that are based on each other the bitmaps will
6007 if (pt1
->vars_contains_restrict
6008 && pt2
->vars_contains_restrict
)
6010 gcc_assert (pt1
->vars
&& pt2
->vars
);
6011 return bitmap_intersect_p (pt1
->vars
, pt2
->vars
);
6018 /* Dump points-to information to OUTFILE. */
6021 dump_sa_points_to_info (FILE *outfile
)
6025 fprintf (outfile
, "\nPoints-to sets\n\n");
6027 if (dump_flags
& TDF_STATS
)
6029 fprintf (outfile
, "Stats:\n");
6030 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
6031 fprintf (outfile
, "Non-pointer vars: %d\n",
6032 stats
.nonpointer_vars
);
6033 fprintf (outfile
, "Statically unified vars: %d\n",
6034 stats
.unified_vars_static
);
6035 fprintf (outfile
, "Dynamically unified vars: %d\n",
6036 stats
.unified_vars_dynamic
);
6037 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
6038 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
6039 fprintf (outfile
, "Number of implicit edges: %d\n",
6040 stats
.num_implicit_edges
);
6043 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
6045 varinfo_t vi
= get_varinfo (i
);
6046 if (!vi
->may_have_pointers
)
6048 dump_solution_for_var (outfile
, i
);
6053 /* Debug points-to information to stderr. */
6056 debug_sa_points_to_info (void)
6058 dump_sa_points_to_info (stderr
);
6062 /* Initialize the always-existing constraint variables for NULL
6063 ANYTHING, READONLY, and INTEGER */
6066 init_base_vars (void)
6068 struct constraint_expr lhs
, rhs
;
6069 varinfo_t var_anything
;
6070 varinfo_t var_nothing
;
6071 varinfo_t var_readonly
;
6072 varinfo_t var_escaped
;
6073 varinfo_t var_nonlocal
;
6074 varinfo_t var_storedanything
;
6075 varinfo_t var_integer
;
6077 /* Create the NULL variable, used to represent that a variable points
6079 var_nothing
= new_var_info (NULL_TREE
, "NULL");
6080 gcc_assert (var_nothing
->id
== nothing_id
);
6081 var_nothing
->is_artificial_var
= 1;
6082 var_nothing
->offset
= 0;
6083 var_nothing
->size
= ~0;
6084 var_nothing
->fullsize
= ~0;
6085 var_nothing
->is_special_var
= 1;
6086 var_nothing
->may_have_pointers
= 0;
6087 var_nothing
->is_global_var
= 0;
6089 /* Create the ANYTHING variable, used to represent that a variable
6090 points to some unknown piece of memory. */
6091 var_anything
= new_var_info (NULL_TREE
, "ANYTHING");
6092 gcc_assert (var_anything
->id
== anything_id
);
6093 var_anything
->is_artificial_var
= 1;
6094 var_anything
->size
= ~0;
6095 var_anything
->offset
= 0;
6096 var_anything
->next
= NULL
;
6097 var_anything
->fullsize
= ~0;
6098 var_anything
->is_special_var
= 1;
6100 /* Anything points to anything. This makes deref constraints just
6101 work in the presence of linked list and other p = *p type loops,
6102 by saying that *ANYTHING = ANYTHING. */
6104 lhs
.var
= anything_id
;
6106 rhs
.type
= ADDRESSOF
;
6107 rhs
.var
= anything_id
;
6110 /* This specifically does not use process_constraint because
6111 process_constraint ignores all anything = anything constraints, since all
6112 but this one are redundant. */
6113 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
6115 /* Create the READONLY variable, used to represent that a variable
6116 points to readonly memory. */
6117 var_readonly
= new_var_info (NULL_TREE
, "READONLY");
6118 gcc_assert (var_readonly
->id
== readonly_id
);
6119 var_readonly
->is_artificial_var
= 1;
6120 var_readonly
->offset
= 0;
6121 var_readonly
->size
= ~0;
6122 var_readonly
->fullsize
= ~0;
6123 var_readonly
->next
= NULL
;
6124 var_readonly
->is_special_var
= 1;
6126 /* readonly memory points to anything, in order to make deref
6127 easier. In reality, it points to anything the particular
6128 readonly variable can point to, but we don't track this
6131 lhs
.var
= readonly_id
;
6133 rhs
.type
= ADDRESSOF
;
6134 rhs
.var
= readonly_id
; /* FIXME */
6136 process_constraint (new_constraint (lhs
, rhs
));
6138 /* Create the ESCAPED variable, used to represent the set of escaped
6140 var_escaped
= new_var_info (NULL_TREE
, "ESCAPED");
6141 gcc_assert (var_escaped
->id
== escaped_id
);
6142 var_escaped
->is_artificial_var
= 1;
6143 var_escaped
->offset
= 0;
6144 var_escaped
->size
= ~0;
6145 var_escaped
->fullsize
= ~0;
6146 var_escaped
->is_special_var
= 0;
6148 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6150 var_nonlocal
= new_var_info (NULL_TREE
, "NONLOCAL");
6151 gcc_assert (var_nonlocal
->id
== nonlocal_id
);
6152 var_nonlocal
->is_artificial_var
= 1;
6153 var_nonlocal
->offset
= 0;
6154 var_nonlocal
->size
= ~0;
6155 var_nonlocal
->fullsize
= ~0;
6156 var_nonlocal
->is_special_var
= 1;
6158 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6160 lhs
.var
= escaped_id
;
6163 rhs
.var
= escaped_id
;
6165 process_constraint (new_constraint (lhs
, rhs
));
6167 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6168 whole variable escapes. */
6170 lhs
.var
= escaped_id
;
6173 rhs
.var
= escaped_id
;
6174 rhs
.offset
= UNKNOWN_OFFSET
;
6175 process_constraint (new_constraint (lhs
, rhs
));
6177 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6178 everything pointed to by escaped points to what global memory can
6181 lhs
.var
= escaped_id
;
6184 rhs
.var
= nonlocal_id
;
6186 process_constraint (new_constraint (lhs
, rhs
));
6188 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6189 global memory may point to global memory and escaped memory. */
6191 lhs
.var
= nonlocal_id
;
6193 rhs
.type
= ADDRESSOF
;
6194 rhs
.var
= nonlocal_id
;
6196 process_constraint (new_constraint (lhs
, rhs
));
6197 rhs
.type
= ADDRESSOF
;
6198 rhs
.var
= escaped_id
;
6200 process_constraint (new_constraint (lhs
, rhs
));
6202 /* Create the STOREDANYTHING variable, used to represent the set of
6203 variables stored to *ANYTHING. */
6204 var_storedanything
= new_var_info (NULL_TREE
, "STOREDANYTHING");
6205 gcc_assert (var_storedanything
->id
== storedanything_id
);
6206 var_storedanything
->is_artificial_var
= 1;
6207 var_storedanything
->offset
= 0;
6208 var_storedanything
->size
= ~0;
6209 var_storedanything
->fullsize
= ~0;
6210 var_storedanything
->is_special_var
= 0;
6212 /* Create the INTEGER variable, used to represent that a variable points
6213 to what an INTEGER "points to". */
6214 var_integer
= new_var_info (NULL_TREE
, "INTEGER");
6215 gcc_assert (var_integer
->id
== integer_id
);
6216 var_integer
->is_artificial_var
= 1;
6217 var_integer
->size
= ~0;
6218 var_integer
->fullsize
= ~0;
6219 var_integer
->offset
= 0;
6220 var_integer
->next
= NULL
;
6221 var_integer
->is_special_var
= 1;
6223 /* INTEGER = ANYTHING, because we don't know where a dereference of
6224 a random integer will point to. */
6226 lhs
.var
= integer_id
;
6228 rhs
.type
= ADDRESSOF
;
6229 rhs
.var
= anything_id
;
6231 process_constraint (new_constraint (lhs
, rhs
));
6234 /* Initialize things necessary to perform PTA */
6237 init_alias_vars (void)
6239 use_field_sensitive
= (MAX_FIELDS_FOR_FIELD_SENSITIVE
> 1);
6241 bitmap_obstack_initialize (&pta_obstack
);
6242 bitmap_obstack_initialize (&oldpta_obstack
);
6243 bitmap_obstack_initialize (&predbitmap_obstack
);
6245 constraint_pool
= create_alloc_pool ("Constraint pool",
6246 sizeof (struct constraint
), 30);
6247 variable_info_pool
= create_alloc_pool ("Variable info pool",
6248 sizeof (struct variable_info
), 30);
6249 constraints
= VEC_alloc (constraint_t
, heap
, 8);
6250 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
6251 vi_for_tree
= pointer_map_create ();
6252 call_stmt_vars
= pointer_map_create ();
6254 memset (&stats
, 0, sizeof (stats
));
6255 shared_bitmap_table
= htab_create (511, shared_bitmap_hash
,
6256 shared_bitmap_eq
, free
);
6260 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6261 predecessor edges. */
6264 remove_preds_and_fake_succs (constraint_graph_t graph
)
6268 /* Clear the implicit ref and address nodes from the successor
6270 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
6272 if (graph
->succs
[i
])
6273 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
6274 FIRST_REF_NODE
* 2);
6277 /* Free the successor list for the non-ref nodes. */
6278 for (i
= FIRST_REF_NODE
; i
< graph
->size
; i
++)
6280 if (graph
->succs
[i
])
6281 BITMAP_FREE (graph
->succs
[i
]);
6284 /* Now reallocate the size of the successor list as, and blow away
6285 the predecessor bitmaps. */
6286 graph
->size
= VEC_length (varinfo_t
, varmap
);
6287 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
6289 free (graph
->implicit_preds
);
6290 graph
->implicit_preds
= NULL
;
6291 free (graph
->preds
);
6292 graph
->preds
= NULL
;
6293 bitmap_obstack_release (&predbitmap_obstack
);
6296 /* Initialize the heapvar for statement mapping. */
6299 init_alias_heapvars (void)
6301 if (!heapvar_for_stmt
)
6302 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, heapvar_map_eq
,
6306 /* Delete the heapvar for statement mapping. */
6309 delete_alias_heapvars (void)
6311 if (heapvar_for_stmt
)
6312 htab_delete (heapvar_for_stmt
);
6313 heapvar_for_stmt
= NULL
;
6316 /* Solve the constraint set. */
6319 solve_constraints (void)
6321 struct scc_info
*si
;
6325 "\nCollapsing static cycles and doing variable "
6328 init_graph (VEC_length (varinfo_t
, varmap
) * 2);
6331 fprintf (dump_file
, "Building predecessor graph\n");
6332 build_pred_graph ();
6335 fprintf (dump_file
, "Detecting pointer and location "
6337 si
= perform_var_substitution (graph
);
6340 fprintf (dump_file
, "Rewriting constraints and unifying "
6342 rewrite_constraints (graph
, si
);
6344 build_succ_graph ();
6345 free_var_substitution_info (si
);
6347 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
6348 dump_constraint_graph (dump_file
);
6350 move_complex_constraints (graph
);
6353 fprintf (dump_file
, "Uniting pointer but not location equivalent "
6355 unite_pointer_equivalences (graph
);
6358 fprintf (dump_file
, "Finding indirect cycles\n");
6359 find_indirect_cycles (graph
);
6361 /* Implicit nodes and predecessors are no longer necessary at this
6363 remove_preds_and_fake_succs (graph
);
6366 fprintf (dump_file
, "Solving graph\n");
6368 solve_graph (graph
);
6371 dump_sa_points_to_info (dump_file
);
6374 /* Create points-to sets for the current function. See the comments
6375 at the start of the file for an algorithmic overview. */
6378 compute_points_to_sets (void)
6384 timevar_push (TV_TREE_PTA
);
6387 init_alias_heapvars ();
6389 intra_create_variable_infos ();
6391 /* Now walk all statements and build the constraint set. */
6394 gimple_stmt_iterator gsi
;
6396 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6398 gimple phi
= gsi_stmt (gsi
);
6400 if (is_gimple_reg (gimple_phi_result (phi
)))
6401 find_func_aliases (phi
);
6404 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6406 gimple stmt
= gsi_stmt (gsi
);
6408 find_func_aliases (stmt
);
6414 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
6415 dump_constraints (dump_file
, 0);
6418 /* From the constraints compute the points-to sets. */
6419 solve_constraints ();
6421 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
6422 find_what_var_points_to (get_varinfo (escaped_id
),
6423 &cfun
->gimple_df
->escaped
);
6425 /* Make sure the ESCAPED solution (which is used as placeholder in
6426 other solutions) does not reference itself. This simplifies
6427 points-to solution queries. */
6428 cfun
->gimple_df
->escaped
.escaped
= 0;
6430 /* Mark escaped HEAP variables as global. */
6431 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, vi
); ++i
)
6433 && !vi
->is_restrict_var
6434 && !vi
->is_global_var
)
6435 DECL_EXTERNAL (vi
->decl
) = vi
->is_global_var
6436 = pt_solution_includes (&cfun
->gimple_df
->escaped
, vi
->decl
);
6438 /* Compute the points-to sets for pointer SSA_NAMEs. */
6439 for (i
= 0; i
< num_ssa_names
; ++i
)
6441 tree ptr
= ssa_name (i
);
6443 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
6444 find_what_p_points_to (ptr
);
6447 /* Compute the call-used/clobbered sets. */
6450 gimple_stmt_iterator gsi
;
6452 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6454 gimple stmt
= gsi_stmt (gsi
);
6455 struct pt_solution
*pt
;
6456 if (!is_gimple_call (stmt
))
6459 pt
= gimple_call_use_set (stmt
);
6460 if (gimple_call_flags (stmt
) & ECF_CONST
)
6461 memset (pt
, 0, sizeof (struct pt_solution
));
6462 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
6464 find_what_var_points_to (vi
, pt
);
6465 /* Escaped (and thus nonlocal) variables are always
6466 implicitly used by calls. */
6467 /* ??? ESCAPED can be empty even though NONLOCAL
6474 /* If there is nothing special about this call then
6475 we have made everything that is used also escape. */
6476 *pt
= cfun
->gimple_df
->escaped
;
6480 pt
= gimple_call_clobber_set (stmt
);
6481 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
6482 memset (pt
, 0, sizeof (struct pt_solution
));
6483 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
6485 find_what_var_points_to (vi
, pt
);
6486 /* Escaped (and thus nonlocal) variables are always
6487 implicitly clobbered by calls. */
6488 /* ??? ESCAPED can be empty even though NONLOCAL
6495 /* If there is nothing special about this call then
6496 we have made everything that is used also escape. */
6497 *pt
= cfun
->gimple_df
->escaped
;
6503 timevar_pop (TV_TREE_PTA
);
6507 /* Delete created points-to sets. */
6510 delete_points_to_sets (void)
6514 htab_delete (shared_bitmap_table
);
6515 if (dump_file
&& (dump_flags
& TDF_STATS
))
6516 fprintf (dump_file
, "Points to sets created:%d\n",
6517 stats
.points_to_sets_created
);
6519 pointer_map_destroy (vi_for_tree
);
6520 pointer_map_destroy (call_stmt_vars
);
6521 bitmap_obstack_release (&pta_obstack
);
6522 VEC_free (constraint_t
, heap
, constraints
);
6524 for (i
= 0; i
< graph
->size
; i
++)
6525 VEC_free (constraint_t
, heap
, graph
->complex[i
]);
6526 free (graph
->complex);
6529 free (graph
->succs
);
6531 free (graph
->pe_rep
);
6532 free (graph
->indirect_cycles
);
6535 VEC_free (varinfo_t
, heap
, varmap
);
6536 free_alloc_pool (variable_info_pool
);
6537 free_alloc_pool (constraint_pool
);
6541 /* Compute points-to information for every SSA_NAME pointer in the
6542 current function and compute the transitive closure of escaped
6543 variables to re-initialize the call-clobber states of local variables. */
6546 compute_may_aliases (void)
6548 if (cfun
->gimple_df
->ipa_pta
)
6552 fprintf (dump_file
, "\nNot re-computing points-to information "
6553 "because IPA points-to information is available.\n\n");
6555 /* But still dump what we have remaining it. */
6556 dump_alias_info (dump_file
);
6558 if (dump_flags
& TDF_DETAILS
)
6559 dump_referenced_vars (dump_file
);
6565 /* For each pointer P_i, determine the sets of variables that P_i may
6566 point-to. Compute the reachability set of escaped and call-used
6568 compute_points_to_sets ();
6570 /* Debugging dumps. */
6573 dump_alias_info (dump_file
);
6575 if (dump_flags
& TDF_DETAILS
)
6576 dump_referenced_vars (dump_file
);
6579 /* Deallocate memory used by aliasing data structures and the internal
6580 points-to solution. */
6581 delete_points_to_sets ();
6583 gcc_assert (!need_ssa_update_p (cfun
));
6589 gate_tree_pta (void)
6591 return flag_tree_pta
;
6594 /* A dummy pass to cause points-to information to be computed via
6595 TODO_rebuild_alias. */
6597 struct gimple_opt_pass pass_build_alias
=
6602 gate_tree_pta
, /* gate */
6606 0, /* static_pass_number */
6607 TV_NONE
, /* tv_id */
6608 PROP_cfg
| PROP_ssa
, /* properties_required */
6609 0, /* properties_provided */
6610 0, /* properties_destroyed */
6611 0, /* todo_flags_start */
6612 TODO_rebuild_alias
| TODO_dump_func
/* todo_flags_finish */
6616 /* A dummy pass to cause points-to information to be computed via
6617 TODO_rebuild_alias. */
6619 struct gimple_opt_pass pass_build_ealias
=
6623 "ealias", /* name */
6624 gate_tree_pta
, /* gate */
6628 0, /* static_pass_number */
6629 TV_NONE
, /* tv_id */
6630 PROP_cfg
| PROP_ssa
, /* properties_required */
6631 0, /* properties_provided */
6632 0, /* properties_destroyed */
6633 0, /* todo_flags_start */
6634 TODO_rebuild_alias
| TODO_dump_func
/* todo_flags_finish */
6639 /* Return true if we should execute IPA PTA. */
6645 /* Don't bother doing anything if the program has errors. */
6649 /* IPA PTA solutions for ESCAPED. */
6650 struct pt_solution ipa_escaped_pt
6651 = { true, false, false, false, false, false, false, NULL
};
6653 /* Execute the driver for IPA PTA. */
6655 ipa_pta_execute (void)
6657 struct cgraph_node
*node
;
6658 struct varpool_node
*var
;
6663 init_alias_heapvars ();
6666 /* Build the constraints. */
6667 for (node
= cgraph_nodes
; node
; node
= node
->next
)
6669 struct cgraph_node
*alias
;
6672 /* Nodes without a body are not interesting. Especially do not
6673 visit clones at this point for now - we get duplicate decls
6674 there for inline clones at least. */
6675 if (!gimple_has_body_p (node
->decl
)
6679 vi
= create_function_info_for (node
->decl
,
6680 alias_get_name (node
->decl
));
6682 /* Associate the varinfo node with all aliases. */
6683 for (alias
= node
->same_body
; alias
; alias
= alias
->next
)
6684 insert_vi_for_tree (alias
->decl
, vi
);
6687 /* Create constraints for global variables and their initializers. */
6688 for (var
= varpool_nodes
; var
; var
= var
->next
)
6690 struct varpool_node
*alias
;
6693 vi
= get_vi_for_tree (var
->decl
);
6695 /* Associate the varinfo node with all aliases. */
6696 for (alias
= var
->extra_name
; alias
; alias
= alias
->next
)
6697 insert_vi_for_tree (alias
->decl
, vi
);
6703 "Generating constraints for global initializers\n\n");
6704 dump_constraints (dump_file
, 0);
6705 fprintf (dump_file
, "\n");
6707 from
= VEC_length (constraint_t
, constraints
);
6709 for (node
= cgraph_nodes
; node
; node
= node
->next
)
6711 struct function
*func
;
6715 /* Nodes without a body are not interesting. */
6716 if (!gimple_has_body_p (node
->decl
)
6723 "Generating constraints for %s", cgraph_node_name (node
));
6724 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
6725 fprintf (dump_file
, " (%s)",
6726 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node
->decl
)));
6727 fprintf (dump_file
, "\n");
6730 func
= DECL_STRUCT_FUNCTION (node
->decl
);
6731 old_func_decl
= current_function_decl
;
6733 current_function_decl
= node
->decl
;
6735 /* For externally visible functions use local constraints for
6736 their arguments. For local functions we see all callers
6737 and thus do not need initial constraints for parameters. */
6738 if (node
->local
.externally_visible
)
6739 intra_create_variable_infos ();
6741 /* Build constriants for the function body. */
6742 FOR_EACH_BB_FN (bb
, func
)
6744 gimple_stmt_iterator gsi
;
6746 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
6749 gimple phi
= gsi_stmt (gsi
);
6751 if (is_gimple_reg (gimple_phi_result (phi
)))
6752 find_func_aliases (phi
);
6755 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6757 gimple stmt
= gsi_stmt (gsi
);
6759 find_func_aliases (stmt
);
6760 find_func_clobbers (stmt
);
6764 current_function_decl
= old_func_decl
;
6769 fprintf (dump_file
, "\n");
6770 dump_constraints (dump_file
, from
);
6771 fprintf (dump_file
, "\n");
6773 from
= VEC_length (constraint_t
, constraints
);
6776 /* From the constraints compute the points-to sets. */
6777 solve_constraints ();
6779 /* Compute the global points-to sets for ESCAPED.
6780 ??? Note that the computed escape set is not correct
6781 for the whole unit as we fail to consider graph edges to
6782 externally visible functions. */
6783 find_what_var_points_to (get_varinfo (escaped_id
), &ipa_escaped_pt
);
6785 /* Make sure the ESCAPED solution (which is used as placeholder in
6786 other solutions) does not reference itself. This simplifies
6787 points-to solution queries. */
6788 ipa_escaped_pt
.ipa_escaped
= 0;
6790 /* Assign the points-to sets to the SSA names in the unit. */
6791 for (node
= cgraph_nodes
; node
; node
= node
->next
)
6794 struct function
*fn
;
6798 struct pt_solution uses
, clobbers
;
6799 struct cgraph_edge
*e
;
6801 /* Nodes without a body are not interesting. */
6802 if (!gimple_has_body_p (node
->decl
)
6806 fn
= DECL_STRUCT_FUNCTION (node
->decl
);
6808 /* Compute the points-to sets for pointer SSA_NAMEs. */
6809 for (i
= 0; VEC_iterate (tree
, fn
->gimple_df
->ssa_names
, i
, ptr
); ++i
)
6812 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
6813 find_what_p_points_to (ptr
);
6816 /* Compute the call-use and call-clobber sets for all direct calls. */
6817 fi
= lookup_vi_for_tree (node
->decl
);
6818 gcc_assert (fi
->is_fn_info
);
6819 find_what_var_points_to (first_vi_for_offset (fi
, fi_clobbers
),
6821 find_what_var_points_to (first_vi_for_offset (fi
, fi_uses
), &uses
);
6822 for (e
= node
->callers
; e
; e
= e
->next_caller
)
6827 *gimple_call_clobber_set (e
->call_stmt
) = clobbers
;
6828 *gimple_call_use_set (e
->call_stmt
) = uses
;
6831 /* Compute the call-use and call-clobber sets for indirect calls
6832 and calls to external functions. */
6833 FOR_EACH_BB_FN (bb
, fn
)
6835 gimple_stmt_iterator gsi
;
6837 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6839 gimple stmt
= gsi_stmt (gsi
);
6840 struct pt_solution
*pt
;
6844 if (!is_gimple_call (stmt
))
6847 /* Handle direct calls to external functions. */
6848 decl
= gimple_call_fndecl (stmt
);
6850 && (!(fi
= lookup_vi_for_tree (decl
))
6851 || !fi
->is_fn_info
))
6853 pt
= gimple_call_use_set (stmt
);
6854 if (gimple_call_flags (stmt
) & ECF_CONST
)
6855 memset (pt
, 0, sizeof (struct pt_solution
));
6856 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
6858 find_what_var_points_to (vi
, pt
);
6859 /* Escaped (and thus nonlocal) variables are always
6860 implicitly used by calls. */
6861 /* ??? ESCAPED can be empty even though NONLOCAL
6864 pt
->ipa_escaped
= 1;
6868 /* If there is nothing special about this call then
6869 we have made everything that is used also escape. */
6870 *pt
= ipa_escaped_pt
;
6874 pt
= gimple_call_clobber_set (stmt
);
6875 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
6876 memset (pt
, 0, sizeof (struct pt_solution
));
6877 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
6879 find_what_var_points_to (vi
, pt
);
6880 /* Escaped (and thus nonlocal) variables are always
6881 implicitly clobbered by calls. */
6882 /* ??? ESCAPED can be empty even though NONLOCAL
6885 pt
->ipa_escaped
= 1;
6889 /* If there is nothing special about this call then
6890 we have made everything that is used also escape. */
6891 *pt
= ipa_escaped_pt
;
6896 /* Handle indirect calls. */
6898 && (fi
= get_fi_for_callee (stmt
)))
6900 /* We need to accumulate all clobbers/uses of all possible
6902 fi
= get_varinfo (find (fi
->id
));
6903 /* If we cannot constrain the set of functions we'll end up
6904 calling we end up using/clobbering everything. */
6905 if (bitmap_bit_p (fi
->solution
, anything_id
)
6906 || bitmap_bit_p (fi
->solution
, nonlocal_id
)
6907 || bitmap_bit_p (fi
->solution
, escaped_id
))
6909 pt_solution_reset (gimple_call_clobber_set (stmt
));
6910 pt_solution_reset (gimple_call_use_set (stmt
));
6916 struct pt_solution
*uses
, *clobbers
;
6918 uses
= gimple_call_use_set (stmt
);
6919 clobbers
= gimple_call_clobber_set (stmt
);
6920 memset (uses
, 0, sizeof (struct pt_solution
));
6921 memset (clobbers
, 0, sizeof (struct pt_solution
));
6922 EXECUTE_IF_SET_IN_BITMAP (fi
->solution
, 0, i
, bi
)
6924 struct pt_solution sol
;
6926 vi
= get_varinfo (i
);
6927 if (!vi
->is_fn_info
)
6929 /* ??? We could be more precise here? */
6931 uses
->ipa_escaped
= 1;
6932 clobbers
->nonlocal
= 1;
6933 clobbers
->ipa_escaped
= 1;
6937 if (!uses
->anything
)
6939 find_what_var_points_to
6940 (first_vi_for_offset (vi
, fi_uses
), &sol
);
6941 pt_solution_ior_into (uses
, &sol
);
6943 if (!clobbers
->anything
)
6945 find_what_var_points_to
6946 (first_vi_for_offset (vi
, fi_clobbers
), &sol
);
6947 pt_solution_ior_into (clobbers
, &sol
);
6955 fn
->gimple_df
->ipa_pta
= true;
6958 delete_points_to_sets ();
6965 struct simple_ipa_opt_pass pass_ipa_pta
=
6970 gate_ipa_pta
, /* gate */
6971 ipa_pta_execute
, /* execute */
6974 0, /* static_pass_number */
6975 TV_IPA_PTA
, /* tv_id */
6976 0, /* properties_required */
6977 0, /* properties_provided */
6978 0, /* properties_destroyed */
6979 0, /* todo_flags_start */
6980 TODO_update_ssa
/* todo_flags_finish */
6985 #include "gt-tree-ssa-structalias.h"