1 /* Tree based points-to analysis
2 Copyright (C) 2005-2014 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
34 #include "hard-reg-set.h"
37 #include "dominance.h"
39 #include "basic-block.h"
41 #include "stor-layout.h"
43 #include "hash-table.h"
44 #include "tree-ssa-alias.h"
45 #include "internal-fn.h"
46 #include "gimple-expr.h"
49 #include "gimple-iterator.h"
50 #include "gimple-ssa.h"
52 #include "plugin-api.h"
55 #include "stringpool.h"
56 #include "tree-ssanames.h"
57 #include "tree-into-ssa.h"
60 #include "tree-inline.h"
61 #include "diagnostic-core.h"
62 #include "tree-pass.h"
63 #include "alloc-pool.h"
64 #include "splay-tree.h"
68 /* The idea behind this analyzer is to generate set constraints from the
69 program, then solve the resulting constraints in order to generate the
72 Set constraints are a way of modeling program analysis problems that
73 involve sets. They consist of an inclusion constraint language,
74 describing the variables (each variable is a set) and operations that
75 are involved on the variables, and a set of rules that derive facts
76 from these operations. To solve a system of set constraints, you derive
77 all possible facts under the rules, which gives you the correct sets
80 See "Efficient Field-sensitive pointer analysis for C" by "David
81 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
82 http://citeseer.ist.psu.edu/pearce04efficient.html
84 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
85 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
86 http://citeseer.ist.psu.edu/heintze01ultrafast.html
88 There are three types of real constraint expressions, DEREF,
89 ADDRESSOF, and SCALAR. Each constraint expression consists
90 of a constraint type, a variable, and an offset.
92 SCALAR is a constraint expression type used to represent x, whether
93 it appears on the LHS or the RHS of a statement.
94 DEREF is a constraint expression type used to represent *x, whether
95 it appears on the LHS or the RHS of a statement.
96 ADDRESSOF is a constraint expression used to represent &x, whether
97 it appears on the LHS or the RHS of a statement.
99 Each pointer variable in the program is assigned an integer id, and
100 each field of a structure variable is assigned an integer id as well.
102 Structure variables are linked to their list of fields through a "next
103 field" in each variable that points to the next field in offset
105 Each variable for a structure field has
107 1. "size", that tells the size in bits of that field.
108 2. "fullsize, that tells the size in bits of the entire structure.
109 3. "offset", that tells the offset in bits from the beginning of the
110 structure to this field.
122 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
123 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
124 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
127 In order to solve the system of set constraints, the following is
130 1. Each constraint variable x has a solution set associated with it,
133 2. Constraints are separated into direct, copy, and complex.
134 Direct constraints are ADDRESSOF constraints that require no extra
135 processing, such as P = &Q
136 Copy constraints are those of the form P = Q.
137 Complex constraints are all the constraints involving dereferences
138 and offsets (including offsetted copies).
140 3. All direct constraints of the form P = &Q are processed, such
141 that Q is added to Sol(P)
143 4. All complex constraints for a given constraint variable are stored in a
144 linked list attached to that variable's node.
146 5. A directed graph is built out of the copy constraints. Each
147 constraint variable is a node in the graph, and an edge from
148 Q to P is added for each copy constraint of the form P = Q
150 6. The graph is then walked, and solution sets are
151 propagated along the copy edges, such that an edge from Q to P
152 causes Sol(P) <- Sol(P) union Sol(Q).
154 7. As we visit each node, all complex constraints associated with
155 that node are processed by adding appropriate copy edges to the graph, or the
156 appropriate variables to the solution set.
158 8. The process of walking the graph is iterated until no solution
161 Prior to walking the graph in steps 6 and 7, We perform static
162 cycle elimination on the constraint graph, as well
163 as off-line variable substitution.
165 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
166 on and turned into anything), but isn't. You can just see what offset
167 inside the pointed-to struct it's going to access.
169 TODO: Constant bounded arrays can be handled as if they were structs of the
170 same number of elements.
172 TODO: Modeling heap and incoming pointers becomes much better if we
173 add fields to them as we discover them, which we could do.
175 TODO: We could handle unions, but to be honest, it's probably not
176 worth the pain or slowdown. */
178 /* IPA-PTA optimizations possible.
180 When the indirect function called is ANYTHING we can add disambiguation
181 based on the function signatures (or simply the parameter count which
182 is the varinfo size). We also do not need to consider functions that
183 do not have their address taken.
185 The is_global_var bit which marks escape points is overly conservative
186 in IPA mode. Split it to is_escape_point and is_global_var - only
187 externally visible globals are escape points in IPA mode. This is
188 also needed to fix the pt_solution_includes_global predicate
189 (and thus ptr_deref_may_alias_global_p).
191 The way we introduce DECL_PT_UID to avoid fixing up all points-to
192 sets in the translation unit when we copy a DECL during inlining
193 pessimizes precision. The advantage is that the DECL_PT_UID keeps
194 compile-time and memory usage overhead low - the points-to sets
195 do not grow or get unshared as they would during a fixup phase.
196 An alternative solution is to delay IPA PTA until after all
197 inlining transformations have been applied.
199 The way we propagate clobber/use information isn't optimized.
200 It should use a new complex constraint that properly filters
201 out local variables of the callee (though that would make
202 the sets invalid after inlining). OTOH we might as well
203 admit defeat to WHOPR and simply do all the clobber/use analysis
204 and propagation after PTA finished but before we threw away
205 points-to information for memory variables. WHOPR and PTA
206 do not play along well anyway - the whole constraint solving
207 would need to be done in WPA phase and it will be very interesting
208 to apply the results to local SSA names during LTRANS phase.
210 We probably should compute a per-function unit-ESCAPE solution
211 propagating it simply like the clobber / uses solutions. The
212 solution can go alongside the non-IPA espaced solution and be
213 used to query which vars escape the unit through a function.
215 We never put function decls in points-to sets so we do not
216 keep the set of called functions for indirect calls.
218 And probably more. */
220 static bool use_field_sensitive
= true;
221 static int in_ipa_mode
= 0;
223 /* Used for predecessor bitmaps. */
224 static bitmap_obstack predbitmap_obstack
;
226 /* Used for points-to sets. */
227 static bitmap_obstack pta_obstack
;
229 /* Used for oldsolution members of variables. */
230 static bitmap_obstack oldpta_obstack
;
232 /* Used for per-solver-iteration bitmaps. */
233 static bitmap_obstack iteration_obstack
;
235 static unsigned int create_variable_info_for (tree
, const char *);
236 typedef struct constraint_graph
*constraint_graph_t
;
237 static void unify_nodes (constraint_graph_t
, unsigned int, unsigned int, bool);
240 typedef struct constraint
*constraint_t
;
243 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
245 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
247 static struct constraint_stats
249 unsigned int total_vars
;
250 unsigned int nonpointer_vars
;
251 unsigned int unified_vars_static
;
252 unsigned int unified_vars_dynamic
;
253 unsigned int iterations
;
254 unsigned int num_edges
;
255 unsigned int num_implicit_edges
;
256 unsigned int points_to_sets_created
;
261 /* ID of this variable */
264 /* True if this is a variable created by the constraint analysis, such as
265 heap variables and constraints we had to break up. */
266 unsigned int is_artificial_var
: 1;
268 /* True if this is a special variable whose solution set should not be
270 unsigned int is_special_var
: 1;
272 /* True for variables whose size is not known or variable. */
273 unsigned int is_unknown_size_var
: 1;
275 /* True for (sub-)fields that represent a whole variable. */
276 unsigned int is_full_var
: 1;
278 /* True if this is a heap variable. */
279 unsigned int is_heap_var
: 1;
281 /* True if this field may contain pointers. */
282 unsigned int may_have_pointers
: 1;
284 /* True if this field has only restrict qualified pointers. */
285 unsigned int only_restrict_pointers
: 1;
287 /* True if this represents a global variable. */
288 unsigned int is_global_var
: 1;
290 /* True if this represents a IPA function info. */
291 unsigned int is_fn_info
: 1;
293 /* The ID of the variable for the next field in this structure
294 or zero for the last field in this structure. */
297 /* The ID of the variable for the first field in this structure. */
300 /* Offset of this variable, in bits, from the base variable */
301 unsigned HOST_WIDE_INT offset
;
303 /* Size of the variable, in bits. */
304 unsigned HOST_WIDE_INT size
;
306 /* Full size of the base variable, in bits. */
307 unsigned HOST_WIDE_INT fullsize
;
309 /* Name of this variable */
312 /* Tree that this variable is associated with. */
315 /* Points-to set for this variable. */
318 /* Old points-to set for this variable. */
321 typedef struct variable_info
*varinfo_t
;
323 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
324 static varinfo_t
first_or_preceding_vi_for_offset (varinfo_t
,
325 unsigned HOST_WIDE_INT
);
326 static varinfo_t
lookup_vi_for_tree (tree
);
327 static inline bool type_can_have_subvars (const_tree
);
329 /* Pool of variable info structures. */
330 static alloc_pool variable_info_pool
;
332 /* Map varinfo to final pt_solution. */
333 static hash_map
<varinfo_t
, pt_solution
*> *final_solutions
;
334 struct obstack final_solutions_obstack
;
336 /* Table of variable info structures for constraint variables.
337 Indexed directly by variable info id. */
338 static vec
<varinfo_t
> varmap
;
340 /* Return the varmap element N */
342 static inline varinfo_t
343 get_varinfo (unsigned int n
)
348 /* Return the next variable in the list of sub-variables of VI
349 or NULL if VI is the last sub-variable. */
351 static inline varinfo_t
352 vi_next (varinfo_t vi
)
354 return get_varinfo (vi
->next
);
357 /* Static IDs for the special variables. Variable ID zero is unused
358 and used as terminator for the sub-variable chain. */
359 enum { nothing_id
= 1, anything_id
= 2, string_id
= 3,
360 escaped_id
= 4, nonlocal_id
= 5,
361 storedanything_id
= 6, integer_id
= 7 };
363 /* Return a new variable info structure consisting for a variable
364 named NAME, and using constraint graph node NODE. Append it
365 to the vector of variable info structures. */
368 new_var_info (tree t
, const char *name
)
370 unsigned index
= varmap
.length ();
371 varinfo_t ret
= (varinfo_t
) pool_alloc (variable_info_pool
);
376 /* Vars without decl are artificial and do not have sub-variables. */
377 ret
->is_artificial_var
= (t
== NULL_TREE
);
378 ret
->is_special_var
= false;
379 ret
->is_unknown_size_var
= false;
380 ret
->is_full_var
= (t
== NULL_TREE
);
381 ret
->is_heap_var
= false;
382 ret
->may_have_pointers
= true;
383 ret
->only_restrict_pointers
= false;
384 ret
->is_global_var
= (t
== NULL_TREE
);
385 ret
->is_fn_info
= false;
387 ret
->is_global_var
= (is_global_var (t
)
388 /* We have to treat even local register variables
390 || (TREE_CODE (t
) == VAR_DECL
391 && DECL_HARD_REGISTER (t
)));
392 ret
->solution
= BITMAP_ALLOC (&pta_obstack
);
393 ret
->oldsolution
= NULL
;
399 varmap
.safe_push (ret
);
405 /* A map mapping call statements to per-stmt variables for uses
406 and clobbers specific to the call. */
407 static hash_map
<gimple
, varinfo_t
> *call_stmt_vars
;
409 /* Lookup or create the variable for the call statement CALL. */
412 get_call_vi (gimple call
)
417 varinfo_t
*slot_p
= &call_stmt_vars
->get_or_insert (call
, &existed
);
421 vi
= new_var_info (NULL_TREE
, "CALLUSED");
425 vi
->is_full_var
= true;
427 vi2
= new_var_info (NULL_TREE
, "CALLCLOBBERED");
431 vi2
->is_full_var
= true;
439 /* Lookup the variable for the call statement CALL representing
440 the uses. Returns NULL if there is nothing special about this call. */
443 lookup_call_use_vi (gimple call
)
445 varinfo_t
*slot_p
= call_stmt_vars
->get (call
);
452 /* Lookup the variable for the call statement CALL representing
453 the clobbers. Returns NULL if there is nothing special about this call. */
456 lookup_call_clobber_vi (gimple call
)
458 varinfo_t uses
= lookup_call_use_vi (call
);
462 return vi_next (uses
);
465 /* Lookup or create the variable for the call statement CALL representing
469 get_call_use_vi (gimple call
)
471 return get_call_vi (call
);
474 /* Lookup or create the variable for the call statement CALL representing
477 static varinfo_t ATTRIBUTE_UNUSED
478 get_call_clobber_vi (gimple call
)
480 return vi_next (get_call_vi (call
));
484 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
486 /* An expression that appears in a constraint. */
488 struct constraint_expr
490 /* Constraint type. */
491 constraint_expr_type type
;
493 /* Variable we are referring to in the constraint. */
496 /* Offset, in bits, of this constraint from the beginning of
497 variables it ends up referring to.
499 IOW, in a deref constraint, we would deref, get the result set,
500 then add OFFSET to each member. */
501 HOST_WIDE_INT offset
;
504 /* Use 0x8000... as special unknown offset. */
505 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
507 typedef struct constraint_expr ce_s
;
508 static void get_constraint_for_1 (tree
, vec
<ce_s
> *, bool, bool);
509 static void get_constraint_for (tree
, vec
<ce_s
> *);
510 static void get_constraint_for_rhs (tree
, vec
<ce_s
> *);
511 static void do_deref (vec
<ce_s
> *);
513 /* Our set constraints are made up of two constraint expressions, one
516 As described in the introduction, our set constraints each represent an
517 operation between set valued variables.
521 struct constraint_expr lhs
;
522 struct constraint_expr rhs
;
525 /* List of constraints that we use to build the constraint graph from. */
527 static vec
<constraint_t
> constraints
;
528 static alloc_pool constraint_pool
;
530 /* The constraint graph is represented as an array of bitmaps
531 containing successor nodes. */
533 struct constraint_graph
535 /* Size of this graph, which may be different than the number of
536 nodes in the variable map. */
539 /* Explicit successors of each node. */
542 /* Implicit predecessors of each node (Used for variable
544 bitmap
*implicit_preds
;
546 /* Explicit predecessors of each node (Used for variable substitution). */
549 /* Indirect cycle representatives, or -1 if the node has no indirect
551 int *indirect_cycles
;
553 /* Representative node for a node. rep[a] == a unless the node has
557 /* Equivalence class representative for a label. This is used for
558 variable substitution. */
561 /* Pointer equivalence label for a node. All nodes with the same
562 pointer equivalence label can be unified together at some point
563 (either during constraint optimization or after the constraint
567 /* Pointer equivalence representative for a label. This is used to
568 handle nodes that are pointer equivalent but not location
569 equivalent. We can unite these once the addressof constraints
570 are transformed into initial points-to sets. */
573 /* Pointer equivalence label for each node, used during variable
575 unsigned int *pointer_label
;
577 /* Location equivalence label for each node, used during location
578 equivalence finding. */
579 unsigned int *loc_label
;
581 /* Pointed-by set for each node, used during location equivalence
582 finding. This is pointed-by rather than pointed-to, because it
583 is constructed using the predecessor graph. */
586 /* Points to sets for pointer equivalence. This is *not* the actual
587 points-to sets for nodes. */
590 /* Bitmap of nodes where the bit is set if the node is a direct
591 node. Used for variable substitution. */
592 sbitmap direct_nodes
;
594 /* Bitmap of nodes where the bit is set if the node is address
595 taken. Used for variable substitution. */
596 bitmap address_taken
;
598 /* Vector of complex constraints for each graph node. Complex
599 constraints are those involving dereferences or offsets that are
601 vec
<constraint_t
> *complex;
604 static constraint_graph_t graph
;
606 /* During variable substitution and the offline version of indirect
607 cycle finding, we create nodes to represent dereferences and
608 address taken constraints. These represent where these start and
610 #define FIRST_REF_NODE (varmap).length ()
611 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
613 /* Return the representative node for NODE, if NODE has been unioned
615 This function performs path compression along the way to finding
616 the representative. */
619 find (unsigned int node
)
621 gcc_checking_assert (node
< graph
->size
);
622 if (graph
->rep
[node
] != node
)
623 return graph
->rep
[node
] = find (graph
->rep
[node
]);
627 /* Union the TO and FROM nodes to the TO nodes.
628 Note that at some point in the future, we may want to do
629 union-by-rank, in which case we are going to have to return the
630 node we unified to. */
633 unite (unsigned int to
, unsigned int from
)
635 gcc_checking_assert (to
< graph
->size
&& from
< graph
->size
);
636 if (to
!= from
&& graph
->rep
[from
] != to
)
638 graph
->rep
[from
] = to
;
644 /* Create a new constraint consisting of LHS and RHS expressions. */
647 new_constraint (const struct constraint_expr lhs
,
648 const struct constraint_expr rhs
)
650 constraint_t ret
= (constraint_t
) pool_alloc (constraint_pool
);
656 /* Print out constraint C to FILE. */
659 dump_constraint (FILE *file
, constraint_t c
)
661 if (c
->lhs
.type
== ADDRESSOF
)
663 else if (c
->lhs
.type
== DEREF
)
665 fprintf (file
, "%s", get_varinfo (c
->lhs
.var
)->name
);
666 if (c
->lhs
.offset
== UNKNOWN_OFFSET
)
667 fprintf (file
, " + UNKNOWN");
668 else if (c
->lhs
.offset
!= 0)
669 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
670 fprintf (file
, " = ");
671 if (c
->rhs
.type
== ADDRESSOF
)
673 else if (c
->rhs
.type
== DEREF
)
675 fprintf (file
, "%s", get_varinfo (c
->rhs
.var
)->name
);
676 if (c
->rhs
.offset
== UNKNOWN_OFFSET
)
677 fprintf (file
, " + UNKNOWN");
678 else if (c
->rhs
.offset
!= 0)
679 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
683 void debug_constraint (constraint_t
);
684 void debug_constraints (void);
685 void debug_constraint_graph (void);
686 void debug_solution_for_var (unsigned int);
687 void debug_sa_points_to_info (void);
689 /* Print out constraint C to stderr. */
692 debug_constraint (constraint_t c
)
694 dump_constraint (stderr
, c
);
695 fprintf (stderr
, "\n");
698 /* Print out all constraints to FILE */
701 dump_constraints (FILE *file
, int from
)
705 for (i
= from
; constraints
.iterate (i
, &c
); i
++)
708 dump_constraint (file
, c
);
709 fprintf (file
, "\n");
713 /* Print out all constraints to stderr. */
716 debug_constraints (void)
718 dump_constraints (stderr
, 0);
721 /* Print the constraint graph in dot format. */
724 dump_constraint_graph (FILE *file
)
728 /* Only print the graph if it has already been initialized: */
732 /* Prints the header of the dot file: */
733 fprintf (file
, "strict digraph {\n");
734 fprintf (file
, " node [\n shape = box\n ]\n");
735 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
736 fprintf (file
, "\n // List of nodes and complex constraints in "
737 "the constraint graph:\n");
739 /* The next lines print the nodes in the graph together with the
740 complex constraints attached to them. */
741 for (i
= 1; i
< graph
->size
; i
++)
743 if (i
== FIRST_REF_NODE
)
747 if (i
< FIRST_REF_NODE
)
748 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
750 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
751 if (graph
->complex[i
].exists ())
755 fprintf (file
, " [label=\"\\N\\n");
756 for (j
= 0; graph
->complex[i
].iterate (j
, &c
); ++j
)
758 dump_constraint (file
, c
);
759 fprintf (file
, "\\l");
761 fprintf (file
, "\"]");
763 fprintf (file
, ";\n");
766 /* Go over the edges. */
767 fprintf (file
, "\n // Edges in the constraint graph:\n");
768 for (i
= 1; i
< graph
->size
; i
++)
774 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
], 0, j
, bi
)
776 unsigned to
= find (j
);
779 if (i
< FIRST_REF_NODE
)
780 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
782 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
783 fprintf (file
, " -> ");
784 if (to
< FIRST_REF_NODE
)
785 fprintf (file
, "\"%s\"", get_varinfo (to
)->name
);
787 fprintf (file
, "\"*%s\"", get_varinfo (to
- FIRST_REF_NODE
)->name
);
788 fprintf (file
, ";\n");
792 /* Prints the tail of the dot file. */
793 fprintf (file
, "}\n");
796 /* Print out the constraint graph to stderr. */
799 debug_constraint_graph (void)
801 dump_constraint_graph (stderr
);
806 The solver is a simple worklist solver, that works on the following
809 sbitmap changed_nodes = all zeroes;
811 For each node that is not already collapsed:
813 set bit in changed nodes
815 while (changed_count > 0)
817 compute topological ordering for constraint graph
819 find and collapse cycles in the constraint graph (updating
820 changed if necessary)
822 for each node (n) in the graph in topological order:
825 Process each complex constraint associated with the node,
826 updating changed if necessary.
828 For each outgoing edge from n, propagate the solution from n to
829 the destination of the edge, updating changed as necessary.
833 /* Return true if two constraint expressions A and B are equal. */
836 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
838 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
841 /* Return true if constraint expression A is less than constraint expression
842 B. This is just arbitrary, but consistent, in order to give them an
846 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
848 if (a
.type
== b
.type
)
851 return a
.offset
< b
.offset
;
853 return a
.var
< b
.var
;
856 return a
.type
< b
.type
;
859 /* Return true if constraint A is less than constraint B. This is just
860 arbitrary, but consistent, in order to give them an ordering. */
863 constraint_less (const constraint_t
&a
, const constraint_t
&b
)
865 if (constraint_expr_less (a
->lhs
, b
->lhs
))
867 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
870 return constraint_expr_less (a
->rhs
, b
->rhs
);
873 /* Return true if two constraints A and B are equal. */
876 constraint_equal (struct constraint a
, struct constraint b
)
878 return constraint_expr_equal (a
.lhs
, b
.lhs
)
879 && constraint_expr_equal (a
.rhs
, b
.rhs
);
883 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
886 constraint_vec_find (vec
<constraint_t
> vec
,
887 struct constraint lookfor
)
895 place
= vec
.lower_bound (&lookfor
, constraint_less
);
896 if (place
>= vec
.length ())
899 if (!constraint_equal (*found
, lookfor
))
904 /* Union two constraint vectors, TO and FROM. Put the result in TO.
905 Returns true of TO set is changed. */
908 constraint_set_union (vec
<constraint_t
> *to
,
909 vec
<constraint_t
> *from
)
913 bool any_change
= false;
915 FOR_EACH_VEC_ELT (*from
, i
, c
)
917 if (constraint_vec_find (*to
, *c
) == NULL
)
919 unsigned int place
= to
->lower_bound (c
, constraint_less
);
920 to
->safe_insert (place
, c
);
927 /* Expands the solution in SET to all sub-fields of variables included. */
930 solution_set_expand (bitmap set
, bitmap
*expanded
)
938 *expanded
= BITMAP_ALLOC (&iteration_obstack
);
940 /* In a first pass expand to the head of the variables we need to
941 add all sub-fields off. This avoids quadratic behavior. */
942 EXECUTE_IF_SET_IN_BITMAP (set
, 0, j
, bi
)
944 varinfo_t v
= get_varinfo (j
);
945 if (v
->is_artificial_var
948 bitmap_set_bit (*expanded
, v
->head
);
951 /* In the second pass now expand all head variables with subfields. */
952 EXECUTE_IF_SET_IN_BITMAP (*expanded
, 0, j
, bi
)
954 varinfo_t v
= get_varinfo (j
);
957 for (v
= vi_next (v
); v
!= NULL
; v
= vi_next (v
))
958 bitmap_set_bit (*expanded
, v
->id
);
961 /* And finally set the rest of the bits from SET. */
962 bitmap_ior_into (*expanded
, set
);
967 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
971 set_union_with_increment (bitmap to
, bitmap delta
, HOST_WIDE_INT inc
,
972 bitmap
*expanded_delta
)
974 bool changed
= false;
978 /* If the solution of DELTA contains anything it is good enough to transfer
980 if (bitmap_bit_p (delta
, anything_id
))
981 return bitmap_set_bit (to
, anything_id
);
983 /* If the offset is unknown we have to expand the solution to
985 if (inc
== UNKNOWN_OFFSET
)
987 delta
= solution_set_expand (delta
, expanded_delta
);
988 changed
|= bitmap_ior_into (to
, delta
);
992 /* For non-zero offset union the offsetted solution into the destination. */
993 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, i
, bi
)
995 varinfo_t vi
= get_varinfo (i
);
997 /* If this is a variable with just one field just set its bit
999 if (vi
->is_artificial_var
1000 || vi
->is_unknown_size_var
1002 changed
|= bitmap_set_bit (to
, i
);
1005 HOST_WIDE_INT fieldoffset
= vi
->offset
+ inc
;
1006 unsigned HOST_WIDE_INT size
= vi
->size
;
1008 /* If the offset makes the pointer point to before the
1009 variable use offset zero for the field lookup. */
1010 if (fieldoffset
< 0)
1011 vi
= get_varinfo (vi
->head
);
1013 vi
= first_or_preceding_vi_for_offset (vi
, fieldoffset
);
1017 changed
|= bitmap_set_bit (to
, vi
->id
);
1022 /* We have to include all fields that overlap the current field
1026 while (vi
->offset
< fieldoffset
+ size
);
1033 /* Insert constraint C into the list of complex constraints for graph
1037 insert_into_complex (constraint_graph_t graph
,
1038 unsigned int var
, constraint_t c
)
1040 vec
<constraint_t
> complex = graph
->complex[var
];
1041 unsigned int place
= complex.lower_bound (c
, constraint_less
);
1043 /* Only insert constraints that do not already exist. */
1044 if (place
>= complex.length ()
1045 || !constraint_equal (*c
, *complex[place
]))
1046 graph
->complex[var
].safe_insert (place
, c
);
1050 /* Condense two variable nodes into a single variable node, by moving
1051 all associated info from FROM to TO. Returns true if TO node's
1052 constraint set changes after the merge. */
1055 merge_node_constraints (constraint_graph_t graph
, unsigned int to
,
1060 bool any_change
= false;
1062 gcc_checking_assert (find (from
) == to
);
1064 /* Move all complex constraints from src node into to node */
1065 FOR_EACH_VEC_ELT (graph
->complex[from
], i
, c
)
1067 /* In complex constraints for node FROM, we may have either
1068 a = *FROM, and *FROM = a, or an offseted constraint which are
1069 always added to the rhs node's constraints. */
1071 if (c
->rhs
.type
== DEREF
)
1073 else if (c
->lhs
.type
== DEREF
)
1079 any_change
= constraint_set_union (&graph
->complex[to
],
1080 &graph
->complex[from
]);
1081 graph
->complex[from
].release ();
1086 /* Remove edges involving NODE from GRAPH. */
1089 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
1091 if (graph
->succs
[node
])
1092 BITMAP_FREE (graph
->succs
[node
]);
1095 /* Merge GRAPH nodes FROM and TO into node TO. */
1098 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1101 if (graph
->indirect_cycles
[from
] != -1)
1103 /* If we have indirect cycles with the from node, and we have
1104 none on the to node, the to node has indirect cycles from the
1105 from node now that they are unified.
1106 If indirect cycles exist on both, unify the nodes that they
1107 are in a cycle with, since we know they are in a cycle with
1109 if (graph
->indirect_cycles
[to
] == -1)
1110 graph
->indirect_cycles
[to
] = graph
->indirect_cycles
[from
];
1113 /* Merge all the successor edges. */
1114 if (graph
->succs
[from
])
1116 if (!graph
->succs
[to
])
1117 graph
->succs
[to
] = BITMAP_ALLOC (&pta_obstack
);
1118 bitmap_ior_into (graph
->succs
[to
],
1119 graph
->succs
[from
]);
1122 clear_edges_for_node (graph
, from
);
1126 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1127 it doesn't exist in the graph already. */
1130 add_implicit_graph_edge (constraint_graph_t graph
, unsigned int to
,
1136 if (!graph
->implicit_preds
[to
])
1137 graph
->implicit_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1139 if (bitmap_set_bit (graph
->implicit_preds
[to
], from
))
1140 stats
.num_implicit_edges
++;
1143 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1144 it doesn't exist in the graph already.
1145 Return false if the edge already existed, true otherwise. */
1148 add_pred_graph_edge (constraint_graph_t graph
, unsigned int to
,
1151 if (!graph
->preds
[to
])
1152 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1153 bitmap_set_bit (graph
->preds
[to
], from
);
1156 /* Add a graph edge to GRAPH, going from FROM to TO if
1157 it doesn't exist in the graph already.
1158 Return false if the edge already existed, true otherwise. */
1161 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1172 if (!graph
->succs
[from
])
1173 graph
->succs
[from
] = BITMAP_ALLOC (&pta_obstack
);
1174 if (bitmap_set_bit (graph
->succs
[from
], to
))
1177 if (to
< FIRST_REF_NODE
&& from
< FIRST_REF_NODE
)
1185 /* Initialize the constraint graph structure to contain SIZE nodes. */
1188 init_graph (unsigned int size
)
1192 graph
= XCNEW (struct constraint_graph
);
1194 graph
->succs
= XCNEWVEC (bitmap
, graph
->size
);
1195 graph
->indirect_cycles
= XNEWVEC (int, graph
->size
);
1196 graph
->rep
= XNEWVEC (unsigned int, graph
->size
);
1197 /* ??? Macros do not support template types with multiple arguments,
1198 so we use a typedef to work around it. */
1199 typedef vec
<constraint_t
> vec_constraint_t_heap
;
1200 graph
->complex = XCNEWVEC (vec_constraint_t_heap
, size
);
1201 graph
->pe
= XCNEWVEC (unsigned int, graph
->size
);
1202 graph
->pe_rep
= XNEWVEC (int, graph
->size
);
1204 for (j
= 0; j
< graph
->size
; j
++)
1207 graph
->pe_rep
[j
] = -1;
1208 graph
->indirect_cycles
[j
] = -1;
1212 /* Build the constraint graph, adding only predecessor edges right now. */
1215 build_pred_graph (void)
1221 graph
->implicit_preds
= XCNEWVEC (bitmap
, graph
->size
);
1222 graph
->preds
= XCNEWVEC (bitmap
, graph
->size
);
1223 graph
->pointer_label
= XCNEWVEC (unsigned int, graph
->size
);
1224 graph
->loc_label
= XCNEWVEC (unsigned int, graph
->size
);
1225 graph
->pointed_by
= XCNEWVEC (bitmap
, graph
->size
);
1226 graph
->points_to
= XCNEWVEC (bitmap
, graph
->size
);
1227 graph
->eq_rep
= XNEWVEC (int, graph
->size
);
1228 graph
->direct_nodes
= sbitmap_alloc (graph
->size
);
1229 graph
->address_taken
= BITMAP_ALLOC (&predbitmap_obstack
);
1230 bitmap_clear (graph
->direct_nodes
);
1232 for (j
= 1; j
< FIRST_REF_NODE
; j
++)
1234 if (!get_varinfo (j
)->is_special_var
)
1235 bitmap_set_bit (graph
->direct_nodes
, j
);
1238 for (j
= 0; j
< graph
->size
; j
++)
1239 graph
->eq_rep
[j
] = -1;
1241 for (j
= 0; j
< varmap
.length (); j
++)
1242 graph
->indirect_cycles
[j
] = -1;
1244 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1246 struct constraint_expr lhs
= c
->lhs
;
1247 struct constraint_expr rhs
= c
->rhs
;
1248 unsigned int lhsvar
= lhs
.var
;
1249 unsigned int rhsvar
= rhs
.var
;
1251 if (lhs
.type
== DEREF
)
1254 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1255 add_pred_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1257 else if (rhs
.type
== DEREF
)
1260 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1261 add_pred_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1263 bitmap_clear_bit (graph
->direct_nodes
, lhsvar
);
1265 else if (rhs
.type
== ADDRESSOF
)
1270 if (graph
->points_to
[lhsvar
] == NULL
)
1271 graph
->points_to
[lhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1272 bitmap_set_bit (graph
->points_to
[lhsvar
], rhsvar
);
1274 if (graph
->pointed_by
[rhsvar
] == NULL
)
1275 graph
->pointed_by
[rhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1276 bitmap_set_bit (graph
->pointed_by
[rhsvar
], lhsvar
);
1278 /* Implicitly, *x = y */
1279 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1281 /* All related variables are no longer direct nodes. */
1282 bitmap_clear_bit (graph
->direct_nodes
, rhsvar
);
1283 v
= get_varinfo (rhsvar
);
1284 if (!v
->is_full_var
)
1286 v
= get_varinfo (v
->head
);
1289 bitmap_clear_bit (graph
->direct_nodes
, v
->id
);
1294 bitmap_set_bit (graph
->address_taken
, rhsvar
);
1296 else if (lhsvar
> anything_id
1297 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1300 add_pred_graph_edge (graph
, lhsvar
, rhsvar
);
1301 /* Implicitly, *x = *y */
1302 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
,
1303 FIRST_REF_NODE
+ rhsvar
);
1305 else if (lhs
.offset
!= 0 || rhs
.offset
!= 0)
1307 if (rhs
.offset
!= 0)
1308 bitmap_clear_bit (graph
->direct_nodes
, lhs
.var
);
1309 else if (lhs
.offset
!= 0)
1310 bitmap_clear_bit (graph
->direct_nodes
, rhs
.var
);
1315 /* Build the constraint graph, adding successor edges. */
1318 build_succ_graph (void)
1323 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1325 struct constraint_expr lhs
;
1326 struct constraint_expr rhs
;
1327 unsigned int lhsvar
;
1328 unsigned int rhsvar
;
1335 lhsvar
= find (lhs
.var
);
1336 rhsvar
= find (rhs
.var
);
1338 if (lhs
.type
== DEREF
)
1340 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1341 add_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1343 else if (rhs
.type
== DEREF
)
1345 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1346 add_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1348 else if (rhs
.type
== ADDRESSOF
)
1351 gcc_checking_assert (find (rhs
.var
) == rhs
.var
);
1352 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1354 else if (lhsvar
> anything_id
1355 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1357 add_graph_edge (graph
, lhsvar
, rhsvar
);
1361 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1362 receive pointers. */
1363 t
= find (storedanything_id
);
1364 for (i
= integer_id
+ 1; i
< FIRST_REF_NODE
; ++i
)
1366 if (!bitmap_bit_p (graph
->direct_nodes
, i
)
1367 && get_varinfo (i
)->may_have_pointers
)
1368 add_graph_edge (graph
, find (i
), t
);
1371 /* Everything stored to ANYTHING also potentially escapes. */
1372 add_graph_edge (graph
, find (escaped_id
), t
);
1376 /* Changed variables on the last iteration. */
1377 static bitmap changed
;
1379 /* Strongly Connected Component visitation info. */
1386 unsigned int *node_mapping
;
1388 vec
<unsigned> scc_stack
;
1392 /* Recursive routine to find strongly connected components in GRAPH.
1393 SI is the SCC info to store the information in, and N is the id of current
1394 graph node we are processing.
1396 This is Tarjan's strongly connected component finding algorithm, as
1397 modified by Nuutila to keep only non-root nodes on the stack.
1398 The algorithm can be found in "On finding the strongly connected
1399 connected components in a directed graph" by Esko Nuutila and Eljas
1400 Soisalon-Soininen, in Information Processing Letters volume 49,
1401 number 1, pages 9-14. */
1404 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1408 unsigned int my_dfs
;
1410 bitmap_set_bit (si
->visited
, n
);
1411 si
->dfs
[n
] = si
->current_index
++;
1412 my_dfs
= si
->dfs
[n
];
1414 /* Visit all the successors. */
1415 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
1419 if (i
> LAST_REF_NODE
)
1423 if (bitmap_bit_p (si
->deleted
, w
))
1426 if (!bitmap_bit_p (si
->visited
, w
))
1427 scc_visit (graph
, si
, w
);
1429 unsigned int t
= find (w
);
1430 gcc_checking_assert (find (n
) == n
);
1431 if (si
->dfs
[t
] < si
->dfs
[n
])
1432 si
->dfs
[n
] = si
->dfs
[t
];
1435 /* See if any components have been identified. */
1436 if (si
->dfs
[n
] == my_dfs
)
1438 if (si
->scc_stack
.length () > 0
1439 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1441 bitmap scc
= BITMAP_ALLOC (NULL
);
1442 unsigned int lowest_node
;
1445 bitmap_set_bit (scc
, n
);
1447 while (si
->scc_stack
.length () != 0
1448 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1450 unsigned int w
= si
->scc_stack
.pop ();
1452 bitmap_set_bit (scc
, w
);
1455 lowest_node
= bitmap_first_set_bit (scc
);
1456 gcc_assert (lowest_node
< FIRST_REF_NODE
);
1458 /* Collapse the SCC nodes into a single node, and mark the
1460 EXECUTE_IF_SET_IN_BITMAP (scc
, 0, i
, bi
)
1462 if (i
< FIRST_REF_NODE
)
1464 if (unite (lowest_node
, i
))
1465 unify_nodes (graph
, lowest_node
, i
, false);
1469 unite (lowest_node
, i
);
1470 graph
->indirect_cycles
[i
- FIRST_REF_NODE
] = lowest_node
;
1474 bitmap_set_bit (si
->deleted
, n
);
1477 si
->scc_stack
.safe_push (n
);
1480 /* Unify node FROM into node TO, updating the changed count if
1481 necessary when UPDATE_CHANGED is true. */
1484 unify_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1485 bool update_changed
)
1487 gcc_checking_assert (to
!= from
&& find (to
) == to
);
1489 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1490 fprintf (dump_file
, "Unifying %s to %s\n",
1491 get_varinfo (from
)->name
,
1492 get_varinfo (to
)->name
);
1495 stats
.unified_vars_dynamic
++;
1497 stats
.unified_vars_static
++;
1499 merge_graph_nodes (graph
, to
, from
);
1500 if (merge_node_constraints (graph
, to
, from
))
1503 bitmap_set_bit (changed
, to
);
1506 /* Mark TO as changed if FROM was changed. If TO was already marked
1507 as changed, decrease the changed count. */
1510 && bitmap_clear_bit (changed
, from
))
1511 bitmap_set_bit (changed
, to
);
1512 varinfo_t fromvi
= get_varinfo (from
);
1513 if (fromvi
->solution
)
1515 /* If the solution changes because of the merging, we need to mark
1516 the variable as changed. */
1517 varinfo_t tovi
= get_varinfo (to
);
1518 if (bitmap_ior_into (tovi
->solution
, fromvi
->solution
))
1521 bitmap_set_bit (changed
, to
);
1524 BITMAP_FREE (fromvi
->solution
);
1525 if (fromvi
->oldsolution
)
1526 BITMAP_FREE (fromvi
->oldsolution
);
1528 if (stats
.iterations
> 0
1529 && tovi
->oldsolution
)
1530 BITMAP_FREE (tovi
->oldsolution
);
1532 if (graph
->succs
[to
])
1533 bitmap_clear_bit (graph
->succs
[to
], to
);
1536 /* Information needed to compute the topological ordering of a graph. */
1540 /* sbitmap of visited nodes. */
1542 /* Array that stores the topological order of the graph, *in
1544 vec
<unsigned> topo_order
;
1548 /* Initialize and return a topological info structure. */
1550 static struct topo_info
*
1551 init_topo_info (void)
1553 size_t size
= graph
->size
;
1554 struct topo_info
*ti
= XNEW (struct topo_info
);
1555 ti
->visited
= sbitmap_alloc (size
);
1556 bitmap_clear (ti
->visited
);
1557 ti
->topo_order
.create (1);
1562 /* Free the topological sort info pointed to by TI. */
1565 free_topo_info (struct topo_info
*ti
)
1567 sbitmap_free (ti
->visited
);
1568 ti
->topo_order
.release ();
1572 /* Visit the graph in topological order, and store the order in the
1573 topo_info structure. */
1576 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1582 bitmap_set_bit (ti
->visited
, n
);
1584 if (graph
->succs
[n
])
1585 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[n
], 0, j
, bi
)
1587 if (!bitmap_bit_p (ti
->visited
, j
))
1588 topo_visit (graph
, ti
, j
);
1591 ti
->topo_order
.safe_push (n
);
1594 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1595 starting solution for y. */
1598 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1599 bitmap delta
, bitmap
*expanded_delta
)
1601 unsigned int lhs
= c
->lhs
.var
;
1603 bitmap sol
= get_varinfo (lhs
)->solution
;
1606 HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1608 /* Our IL does not allow this. */
1609 gcc_checking_assert (c
->lhs
.offset
== 0);
1611 /* If the solution of Y contains anything it is good enough to transfer
1613 if (bitmap_bit_p (delta
, anything_id
))
1615 flag
|= bitmap_set_bit (sol
, anything_id
);
1619 /* If we do not know at with offset the rhs is dereferenced compute
1620 the reachability set of DELTA, conservatively assuming it is
1621 dereferenced at all valid offsets. */
1622 if (roffset
== UNKNOWN_OFFSET
)
1624 delta
= solution_set_expand (delta
, expanded_delta
);
1625 /* No further offset processing is necessary. */
1629 /* For each variable j in delta (Sol(y)), add
1630 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1631 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1633 varinfo_t v
= get_varinfo (j
);
1634 HOST_WIDE_INT fieldoffset
= v
->offset
+ roffset
;
1635 unsigned HOST_WIDE_INT size
= v
->size
;
1640 else if (roffset
!= 0)
1642 if (fieldoffset
< 0)
1643 v
= get_varinfo (v
->head
);
1645 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1648 /* We have to include all fields that overlap the current field
1649 shifted by roffset. */
1654 /* Adding edges from the special vars is pointless.
1655 They don't have sets that can change. */
1656 if (get_varinfo (t
)->is_special_var
)
1657 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1658 /* Merging the solution from ESCAPED needlessly increases
1659 the set. Use ESCAPED as representative instead. */
1660 else if (v
->id
== escaped_id
)
1661 flag
|= bitmap_set_bit (sol
, escaped_id
);
1662 else if (v
->may_have_pointers
1663 && add_graph_edge (graph
, lhs
, t
))
1664 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1672 while (v
->offset
< fieldoffset
+ size
);
1676 /* If the LHS solution changed, mark the var as changed. */
1679 get_varinfo (lhs
)->solution
= sol
;
1680 bitmap_set_bit (changed
, lhs
);
1684 /* Process a constraint C that represents *(x + off) = y using DELTA
1685 as the starting solution for x. */
1688 do_ds_constraint (constraint_t c
, bitmap delta
, bitmap
*expanded_delta
)
1690 unsigned int rhs
= c
->rhs
.var
;
1691 bitmap sol
= get_varinfo (rhs
)->solution
;
1694 HOST_WIDE_INT loff
= c
->lhs
.offset
;
1695 bool escaped_p
= false;
1697 /* Our IL does not allow this. */
1698 gcc_checking_assert (c
->rhs
.offset
== 0);
1700 /* If the solution of y contains ANYTHING simply use the ANYTHING
1701 solution. This avoids needlessly increasing the points-to sets. */
1702 if (bitmap_bit_p (sol
, anything_id
))
1703 sol
= get_varinfo (find (anything_id
))->solution
;
1705 /* If the solution for x contains ANYTHING we have to merge the
1706 solution of y into all pointer variables which we do via
1708 if (bitmap_bit_p (delta
, anything_id
))
1710 unsigned t
= find (storedanything_id
);
1711 if (add_graph_edge (graph
, t
, rhs
))
1713 if (bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1714 bitmap_set_bit (changed
, t
);
1719 /* If we do not know at with offset the rhs is dereferenced compute
1720 the reachability set of DELTA, conservatively assuming it is
1721 dereferenced at all valid offsets. */
1722 if (loff
== UNKNOWN_OFFSET
)
1724 delta
= solution_set_expand (delta
, expanded_delta
);
1728 /* For each member j of delta (Sol(x)), add an edge from y to j and
1729 union Sol(y) into Sol(j) */
1730 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1732 varinfo_t v
= get_varinfo (j
);
1734 HOST_WIDE_INT fieldoffset
= v
->offset
+ loff
;
1735 unsigned HOST_WIDE_INT size
= v
->size
;
1741 if (fieldoffset
< 0)
1742 v
= get_varinfo (v
->head
);
1744 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1747 /* We have to include all fields that overlap the current field
1751 if (v
->may_have_pointers
)
1753 /* If v is a global variable then this is an escape point. */
1754 if (v
->is_global_var
1757 t
= find (escaped_id
);
1758 if (add_graph_edge (graph
, t
, rhs
)
1759 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1760 bitmap_set_bit (changed
, t
);
1761 /* Enough to let rhs escape once. */
1765 if (v
->is_special_var
)
1769 if (add_graph_edge (graph
, t
, rhs
)
1770 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1771 bitmap_set_bit (changed
, t
);
1780 while (v
->offset
< fieldoffset
+ size
);
1784 /* Handle a non-simple (simple meaning requires no iteration),
1785 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1788 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
,
1789 bitmap
*expanded_delta
)
1791 if (c
->lhs
.type
== DEREF
)
1793 if (c
->rhs
.type
== ADDRESSOF
)
1800 do_ds_constraint (c
, delta
, expanded_delta
);
1803 else if (c
->rhs
.type
== DEREF
)
1806 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1807 do_sd_constraint (graph
, c
, delta
, expanded_delta
);
1814 gcc_checking_assert (c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
1815 && c
->rhs
.offset
!= 0 && c
->lhs
.offset
== 0);
1816 tmp
= get_varinfo (c
->lhs
.var
)->solution
;
1818 flag
= set_union_with_increment (tmp
, delta
, c
->rhs
.offset
,
1822 bitmap_set_bit (changed
, c
->lhs
.var
);
1826 /* Initialize and return a new SCC info structure. */
1828 static struct scc_info
*
1829 init_scc_info (size_t size
)
1831 struct scc_info
*si
= XNEW (struct scc_info
);
1834 si
->current_index
= 0;
1835 si
->visited
= sbitmap_alloc (size
);
1836 bitmap_clear (si
->visited
);
1837 si
->deleted
= sbitmap_alloc (size
);
1838 bitmap_clear (si
->deleted
);
1839 si
->node_mapping
= XNEWVEC (unsigned int, size
);
1840 si
->dfs
= XCNEWVEC (unsigned int, size
);
1842 for (i
= 0; i
< size
; i
++)
1843 si
->node_mapping
[i
] = i
;
1845 si
->scc_stack
.create (1);
1849 /* Free an SCC info structure pointed to by SI */
1852 free_scc_info (struct scc_info
*si
)
1854 sbitmap_free (si
->visited
);
1855 sbitmap_free (si
->deleted
);
1856 free (si
->node_mapping
);
1858 si
->scc_stack
.release ();
1863 /* Find indirect cycles in GRAPH that occur, using strongly connected
1864 components, and note them in the indirect cycles map.
1866 This technique comes from Ben Hardekopf and Calvin Lin,
1867 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1868 Lines of Code", submitted to PLDI 2007. */
1871 find_indirect_cycles (constraint_graph_t graph
)
1874 unsigned int size
= graph
->size
;
1875 struct scc_info
*si
= init_scc_info (size
);
1877 for (i
= 0; i
< MIN (LAST_REF_NODE
, size
); i
++ )
1878 if (!bitmap_bit_p (si
->visited
, i
) && find (i
) == i
)
1879 scc_visit (graph
, si
, i
);
1884 /* Compute a topological ordering for GRAPH, and store the result in the
1885 topo_info structure TI. */
1888 compute_topo_order (constraint_graph_t graph
,
1889 struct topo_info
*ti
)
1892 unsigned int size
= graph
->size
;
1894 for (i
= 0; i
!= size
; ++i
)
1895 if (!bitmap_bit_p (ti
->visited
, i
) && find (i
) == i
)
1896 topo_visit (graph
, ti
, i
);
1899 /* Structure used to for hash value numbering of pointer equivalence
1902 typedef struct equiv_class_label
1905 unsigned int equivalence_class
;
1907 } *equiv_class_label_t
;
1908 typedef const struct equiv_class_label
*const_equiv_class_label_t
;
1910 /* Equiv_class_label hashtable helpers. */
1912 struct equiv_class_hasher
: typed_free_remove
<equiv_class_label
>
1914 typedef equiv_class_label value_type
;
1915 typedef equiv_class_label compare_type
;
1916 static inline hashval_t
hash (const value_type
*);
1917 static inline bool equal (const value_type
*, const compare_type
*);
1920 /* Hash function for a equiv_class_label_t */
1923 equiv_class_hasher::hash (const value_type
*ecl
)
1925 return ecl
->hashcode
;
1928 /* Equality function for two equiv_class_label_t's. */
1931 equiv_class_hasher::equal (const value_type
*eql1
, const compare_type
*eql2
)
1933 return (eql1
->hashcode
== eql2
->hashcode
1934 && bitmap_equal_p (eql1
->labels
, eql2
->labels
));
1937 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1939 static hash_table
<equiv_class_hasher
> *pointer_equiv_class_table
;
1941 /* A hashtable for mapping a bitmap of labels->location equivalence
1943 static hash_table
<equiv_class_hasher
> *location_equiv_class_table
;
1945 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1946 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1947 is equivalent to. */
1949 static equiv_class_label
*
1950 equiv_class_lookup_or_add (hash_table
<equiv_class_hasher
> *table
,
1953 equiv_class_label
**slot
;
1954 equiv_class_label ecl
;
1956 ecl
.labels
= labels
;
1957 ecl
.hashcode
= bitmap_hash (labels
);
1958 slot
= table
->find_slot (&ecl
, INSERT
);
1961 *slot
= XNEW (struct equiv_class_label
);
1962 (*slot
)->labels
= labels
;
1963 (*slot
)->hashcode
= ecl
.hashcode
;
1964 (*slot
)->equivalence_class
= 0;
1970 /* Perform offline variable substitution.
1972 This is a worst case quadratic time way of identifying variables
1973 that must have equivalent points-to sets, including those caused by
1974 static cycles, and single entry subgraphs, in the constraint graph.
1976 The technique is described in "Exploiting Pointer and Location
1977 Equivalence to Optimize Pointer Analysis. In the 14th International
1978 Static Analysis Symposium (SAS), August 2007." It is known as the
1979 "HU" algorithm, and is equivalent to value numbering the collapsed
1980 constraint graph including evaluating unions.
1982 The general method of finding equivalence classes is as follows:
1983 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1984 Initialize all non-REF nodes to be direct nodes.
1985 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1987 For each constraint containing the dereference, we also do the same
1990 We then compute SCC's in the graph and unify nodes in the same SCC,
1993 For each non-collapsed node x:
1994 Visit all unvisited explicit incoming edges.
1995 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1997 Lookup the equivalence class for pts(x).
1998 If we found one, equivalence_class(x) = found class.
1999 Otherwise, equivalence_class(x) = new class, and new_class is
2000 added to the lookup table.
2002 All direct nodes with the same equivalence class can be replaced
2003 with a single representative node.
2004 All unlabeled nodes (label == 0) are not pointers and all edges
2005 involving them can be eliminated.
2006 We perform these optimizations during rewrite_constraints
2008 In addition to pointer equivalence class finding, we also perform
2009 location equivalence class finding. This is the set of variables
2010 that always appear together in points-to sets. We use this to
2011 compress the size of the points-to sets. */
2013 /* Current maximum pointer equivalence class id. */
2014 static int pointer_equiv_class
;
2016 /* Current maximum location equivalence class id. */
2017 static int location_equiv_class
;
2019 /* Recursive routine to find strongly connected components in GRAPH,
2020 and label it's nodes with DFS numbers. */
2023 condense_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2027 unsigned int my_dfs
;
2029 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2030 bitmap_set_bit (si
->visited
, n
);
2031 si
->dfs
[n
] = si
->current_index
++;
2032 my_dfs
= si
->dfs
[n
];
2034 /* Visit all the successors. */
2035 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2037 unsigned int w
= si
->node_mapping
[i
];
2039 if (bitmap_bit_p (si
->deleted
, w
))
2042 if (!bitmap_bit_p (si
->visited
, w
))
2043 condense_visit (graph
, si
, w
);
2045 unsigned int t
= si
->node_mapping
[w
];
2046 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2047 if (si
->dfs
[t
] < si
->dfs
[n
])
2048 si
->dfs
[n
] = si
->dfs
[t
];
2051 /* Visit all the implicit predecessors. */
2052 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->implicit_preds
[n
], 0, i
, bi
)
2054 unsigned int w
= si
->node_mapping
[i
];
2056 if (bitmap_bit_p (si
->deleted
, w
))
2059 if (!bitmap_bit_p (si
->visited
, w
))
2060 condense_visit (graph
, si
, w
);
2062 unsigned int t
= si
->node_mapping
[w
];
2063 gcc_assert (si
->node_mapping
[n
] == n
);
2064 if (si
->dfs
[t
] < si
->dfs
[n
])
2065 si
->dfs
[n
] = si
->dfs
[t
];
2068 /* See if any components have been identified. */
2069 if (si
->dfs
[n
] == my_dfs
)
2071 while (si
->scc_stack
.length () != 0
2072 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
2074 unsigned int w
= si
->scc_stack
.pop ();
2075 si
->node_mapping
[w
] = n
;
2077 if (!bitmap_bit_p (graph
->direct_nodes
, w
))
2078 bitmap_clear_bit (graph
->direct_nodes
, n
);
2080 /* Unify our nodes. */
2081 if (graph
->preds
[w
])
2083 if (!graph
->preds
[n
])
2084 graph
->preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2085 bitmap_ior_into (graph
->preds
[n
], graph
->preds
[w
]);
2087 if (graph
->implicit_preds
[w
])
2089 if (!graph
->implicit_preds
[n
])
2090 graph
->implicit_preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2091 bitmap_ior_into (graph
->implicit_preds
[n
],
2092 graph
->implicit_preds
[w
]);
2094 if (graph
->points_to
[w
])
2096 if (!graph
->points_to
[n
])
2097 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2098 bitmap_ior_into (graph
->points_to
[n
],
2099 graph
->points_to
[w
]);
2102 bitmap_set_bit (si
->deleted
, n
);
2105 si
->scc_stack
.safe_push (n
);
2108 /* Label pointer equivalences.
2110 This performs a value numbering of the constraint graph to
2111 discover which variables will always have the same points-to sets
2112 under the current set of constraints.
2114 The way it value numbers is to store the set of points-to bits
2115 generated by the constraints and graph edges. This is just used as a
2116 hash and equality comparison. The *actual set of points-to bits* is
2117 completely irrelevant, in that we don't care about being able to
2120 The equality values (currently bitmaps) just have to satisfy a few
2121 constraints, the main ones being:
2122 1. The combining operation must be order independent.
2123 2. The end result of a given set of operations must be unique iff the
2124 combination of input values is unique
2128 label_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2130 unsigned int i
, first_pred
;
2133 bitmap_set_bit (si
->visited
, n
);
2135 /* Label and union our incoming edges's points to sets. */
2137 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2139 unsigned int w
= si
->node_mapping
[i
];
2140 if (!bitmap_bit_p (si
->visited
, w
))
2141 label_visit (graph
, si
, w
);
2143 /* Skip unused edges */
2144 if (w
== n
|| graph
->pointer_label
[w
] == 0)
2147 if (graph
->points_to
[w
])
2149 if (!graph
->points_to
[n
])
2151 if (first_pred
== -1U)
2155 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2156 bitmap_ior (graph
->points_to
[n
],
2157 graph
->points_to
[first_pred
],
2158 graph
->points_to
[w
]);
2162 bitmap_ior_into (graph
->points_to
[n
], graph
->points_to
[w
]);
2166 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2167 if (!bitmap_bit_p (graph
->direct_nodes
, n
))
2169 if (!graph
->points_to
[n
])
2171 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2172 if (first_pred
!= -1U)
2173 bitmap_copy (graph
->points_to
[n
], graph
->points_to
[first_pred
]);
2175 bitmap_set_bit (graph
->points_to
[n
], FIRST_REF_NODE
+ n
);
2176 graph
->pointer_label
[n
] = pointer_equiv_class
++;
2177 equiv_class_label_t ecl
;
2178 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2179 graph
->points_to
[n
]);
2180 ecl
->equivalence_class
= graph
->pointer_label
[n
];
2184 /* If there was only a single non-empty predecessor the pointer equiv
2185 class is the same. */
2186 if (!graph
->points_to
[n
])
2188 if (first_pred
!= -1U)
2190 graph
->pointer_label
[n
] = graph
->pointer_label
[first_pred
];
2191 graph
->points_to
[n
] = graph
->points_to
[first_pred
];
2196 if (!bitmap_empty_p (graph
->points_to
[n
]))
2198 equiv_class_label_t ecl
;
2199 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2200 graph
->points_to
[n
]);
2201 if (ecl
->equivalence_class
== 0)
2202 ecl
->equivalence_class
= pointer_equiv_class
++;
2205 BITMAP_FREE (graph
->points_to
[n
]);
2206 graph
->points_to
[n
] = ecl
->labels
;
2208 graph
->pointer_label
[n
] = ecl
->equivalence_class
;
2212 /* Print the pred graph in dot format. */
2215 dump_pred_graph (struct scc_info
*si
, FILE *file
)
2219 /* Only print the graph if it has already been initialized: */
2223 /* Prints the header of the dot file: */
2224 fprintf (file
, "strict digraph {\n");
2225 fprintf (file
, " node [\n shape = box\n ]\n");
2226 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
2227 fprintf (file
, "\n // List of nodes and complex constraints in "
2228 "the constraint graph:\n");
2230 /* The next lines print the nodes in the graph together with the
2231 complex constraints attached to them. */
2232 for (i
= 1; i
< graph
->size
; i
++)
2234 if (i
== FIRST_REF_NODE
)
2236 if (si
->node_mapping
[i
] != i
)
2238 if (i
< FIRST_REF_NODE
)
2239 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2241 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2242 if (graph
->points_to
[i
]
2243 && !bitmap_empty_p (graph
->points_to
[i
]))
2245 fprintf (file
, "[label=\"%s = {", get_varinfo (i
)->name
);
2248 EXECUTE_IF_SET_IN_BITMAP (graph
->points_to
[i
], 0, j
, bi
)
2249 fprintf (file
, " %d", j
);
2250 fprintf (file
, " }\"]");
2252 fprintf (file
, ";\n");
2255 /* Go over the edges. */
2256 fprintf (file
, "\n // Edges in the constraint graph:\n");
2257 for (i
= 1; i
< graph
->size
; i
++)
2261 if (si
->node_mapping
[i
] != i
)
2263 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[i
], 0, j
, bi
)
2265 unsigned from
= si
->node_mapping
[j
];
2266 if (from
< FIRST_REF_NODE
)
2267 fprintf (file
, "\"%s\"", get_varinfo (from
)->name
);
2269 fprintf (file
, "\"*%s\"", get_varinfo (from
- FIRST_REF_NODE
)->name
);
2270 fprintf (file
, " -> ");
2271 if (i
< FIRST_REF_NODE
)
2272 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2274 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2275 fprintf (file
, ";\n");
2279 /* Prints the tail of the dot file. */
2280 fprintf (file
, "}\n");
2283 /* Perform offline variable substitution, discovering equivalence
2284 classes, and eliminating non-pointer variables. */
2286 static struct scc_info
*
2287 perform_var_substitution (constraint_graph_t graph
)
2290 unsigned int size
= graph
->size
;
2291 struct scc_info
*si
= init_scc_info (size
);
2293 bitmap_obstack_initialize (&iteration_obstack
);
2294 pointer_equiv_class_table
= new hash_table
<equiv_class_hasher
> (511);
2295 location_equiv_class_table
2296 = new hash_table
<equiv_class_hasher
> (511);
2297 pointer_equiv_class
= 1;
2298 location_equiv_class
= 1;
2300 /* Condense the nodes, which means to find SCC's, count incoming
2301 predecessors, and unite nodes in SCC's. */
2302 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2303 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2304 condense_visit (graph
, si
, si
->node_mapping
[i
]);
2306 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
2308 fprintf (dump_file
, "\n\n// The constraint graph before var-substitution "
2309 "in dot format:\n");
2310 dump_pred_graph (si
, dump_file
);
2311 fprintf (dump_file
, "\n\n");
2314 bitmap_clear (si
->visited
);
2315 /* Actually the label the nodes for pointer equivalences */
2316 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2317 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2318 label_visit (graph
, si
, si
->node_mapping
[i
]);
2320 /* Calculate location equivalence labels. */
2321 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2327 if (!graph
->pointed_by
[i
])
2329 pointed_by
= BITMAP_ALLOC (&iteration_obstack
);
2331 /* Translate the pointed-by mapping for pointer equivalence
2333 EXECUTE_IF_SET_IN_BITMAP (graph
->pointed_by
[i
], 0, j
, bi
)
2335 bitmap_set_bit (pointed_by
,
2336 graph
->pointer_label
[si
->node_mapping
[j
]]);
2338 /* The original pointed_by is now dead. */
2339 BITMAP_FREE (graph
->pointed_by
[i
]);
2341 /* Look up the location equivalence label if one exists, or make
2343 equiv_class_label_t ecl
;
2344 ecl
= equiv_class_lookup_or_add (location_equiv_class_table
, pointed_by
);
2345 if (ecl
->equivalence_class
== 0)
2346 ecl
->equivalence_class
= location_equiv_class
++;
2349 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2350 fprintf (dump_file
, "Found location equivalence for node %s\n",
2351 get_varinfo (i
)->name
);
2352 BITMAP_FREE (pointed_by
);
2354 graph
->loc_label
[i
] = ecl
->equivalence_class
;
2358 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2359 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2361 unsigned j
= si
->node_mapping
[i
];
2364 fprintf (dump_file
, "%s node id %d ",
2365 bitmap_bit_p (graph
->direct_nodes
, i
)
2366 ? "Direct" : "Indirect", i
);
2367 if (i
< FIRST_REF_NODE
)
2368 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2370 fprintf (dump_file
, "\"*%s\"",
2371 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2372 fprintf (dump_file
, " mapped to SCC leader node id %d ", j
);
2373 if (j
< FIRST_REF_NODE
)
2374 fprintf (dump_file
, "\"%s\"\n", get_varinfo (j
)->name
);
2376 fprintf (dump_file
, "\"*%s\"\n",
2377 get_varinfo (j
- FIRST_REF_NODE
)->name
);
2382 "Equivalence classes for %s node id %d ",
2383 bitmap_bit_p (graph
->direct_nodes
, i
)
2384 ? "direct" : "indirect", i
);
2385 if (i
< FIRST_REF_NODE
)
2386 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2388 fprintf (dump_file
, "\"*%s\"",
2389 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2391 ": pointer %d, location %d\n",
2392 graph
->pointer_label
[i
], graph
->loc_label
[i
]);
2396 /* Quickly eliminate our non-pointer variables. */
2398 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2400 unsigned int node
= si
->node_mapping
[i
];
2402 if (graph
->pointer_label
[node
] == 0)
2404 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2406 "%s is a non-pointer variable, eliminating edges.\n",
2407 get_varinfo (node
)->name
);
2408 stats
.nonpointer_vars
++;
2409 clear_edges_for_node (graph
, node
);
2416 /* Free information that was only necessary for variable
2420 free_var_substitution_info (struct scc_info
*si
)
2423 free (graph
->pointer_label
);
2424 free (graph
->loc_label
);
2425 free (graph
->pointed_by
);
2426 free (graph
->points_to
);
2427 free (graph
->eq_rep
);
2428 sbitmap_free (graph
->direct_nodes
);
2429 delete pointer_equiv_class_table
;
2430 pointer_equiv_class_table
= NULL
;
2431 delete location_equiv_class_table
;
2432 location_equiv_class_table
= NULL
;
2433 bitmap_obstack_release (&iteration_obstack
);
2436 /* Return an existing node that is equivalent to NODE, which has
2437 equivalence class LABEL, if one exists. Return NODE otherwise. */
2440 find_equivalent_node (constraint_graph_t graph
,
2441 unsigned int node
, unsigned int label
)
2443 /* If the address version of this variable is unused, we can
2444 substitute it for anything else with the same label.
2445 Otherwise, we know the pointers are equivalent, but not the
2446 locations, and we can unite them later. */
2448 if (!bitmap_bit_p (graph
->address_taken
, node
))
2450 gcc_checking_assert (label
< graph
->size
);
2452 if (graph
->eq_rep
[label
] != -1)
2454 /* Unify the two variables since we know they are equivalent. */
2455 if (unite (graph
->eq_rep
[label
], node
))
2456 unify_nodes (graph
, graph
->eq_rep
[label
], node
, false);
2457 return graph
->eq_rep
[label
];
2461 graph
->eq_rep
[label
] = node
;
2462 graph
->pe_rep
[label
] = node
;
2467 gcc_checking_assert (label
< graph
->size
);
2468 graph
->pe
[node
] = label
;
2469 if (graph
->pe_rep
[label
] == -1)
2470 graph
->pe_rep
[label
] = node
;
2476 /* Unite pointer equivalent but not location equivalent nodes in
2477 GRAPH. This may only be performed once variable substitution is
2481 unite_pointer_equivalences (constraint_graph_t graph
)
2485 /* Go through the pointer equivalences and unite them to their
2486 representative, if they aren't already. */
2487 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2489 unsigned int label
= graph
->pe
[i
];
2492 int label_rep
= graph
->pe_rep
[label
];
2494 if (label_rep
== -1)
2497 label_rep
= find (label_rep
);
2498 if (label_rep
>= 0 && unite (label_rep
, find (i
)))
2499 unify_nodes (graph
, label_rep
, i
, false);
2504 /* Move complex constraints to the GRAPH nodes they belong to. */
2507 move_complex_constraints (constraint_graph_t graph
)
2512 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2516 struct constraint_expr lhs
= c
->lhs
;
2517 struct constraint_expr rhs
= c
->rhs
;
2519 if (lhs
.type
== DEREF
)
2521 insert_into_complex (graph
, lhs
.var
, c
);
2523 else if (rhs
.type
== DEREF
)
2525 if (!(get_varinfo (lhs
.var
)->is_special_var
))
2526 insert_into_complex (graph
, rhs
.var
, c
);
2528 else if (rhs
.type
!= ADDRESSOF
&& lhs
.var
> anything_id
2529 && (lhs
.offset
!= 0 || rhs
.offset
!= 0))
2531 insert_into_complex (graph
, rhs
.var
, c
);
2538 /* Optimize and rewrite complex constraints while performing
2539 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2540 result of perform_variable_substitution. */
2543 rewrite_constraints (constraint_graph_t graph
,
2544 struct scc_info
*si
)
2549 #ifdef ENABLE_CHECKING
2550 for (unsigned int j
= 0; j
< graph
->size
; j
++)
2551 gcc_assert (find (j
) == j
);
2554 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2556 struct constraint_expr lhs
= c
->lhs
;
2557 struct constraint_expr rhs
= c
->rhs
;
2558 unsigned int lhsvar
= find (lhs
.var
);
2559 unsigned int rhsvar
= find (rhs
.var
);
2560 unsigned int lhsnode
, rhsnode
;
2561 unsigned int lhslabel
, rhslabel
;
2563 lhsnode
= si
->node_mapping
[lhsvar
];
2564 rhsnode
= si
->node_mapping
[rhsvar
];
2565 lhslabel
= graph
->pointer_label
[lhsnode
];
2566 rhslabel
= graph
->pointer_label
[rhsnode
];
2568 /* See if it is really a non-pointer variable, and if so, ignore
2572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2575 fprintf (dump_file
, "%s is a non-pointer variable,"
2576 "ignoring constraint:",
2577 get_varinfo (lhs
.var
)->name
);
2578 dump_constraint (dump_file
, c
);
2579 fprintf (dump_file
, "\n");
2581 constraints
[i
] = NULL
;
2587 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2590 fprintf (dump_file
, "%s is a non-pointer variable,"
2591 "ignoring constraint:",
2592 get_varinfo (rhs
.var
)->name
);
2593 dump_constraint (dump_file
, c
);
2594 fprintf (dump_file
, "\n");
2596 constraints
[i
] = NULL
;
2600 lhsvar
= find_equivalent_node (graph
, lhsvar
, lhslabel
);
2601 rhsvar
= find_equivalent_node (graph
, rhsvar
, rhslabel
);
2602 c
->lhs
.var
= lhsvar
;
2603 c
->rhs
.var
= rhsvar
;
2607 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2608 part of an SCC, false otherwise. */
2611 eliminate_indirect_cycles (unsigned int node
)
2613 if (graph
->indirect_cycles
[node
] != -1
2614 && !bitmap_empty_p (get_varinfo (node
)->solution
))
2617 auto_vec
<unsigned> queue
;
2619 unsigned int to
= find (graph
->indirect_cycles
[node
]);
2622 /* We can't touch the solution set and call unify_nodes
2623 at the same time, because unify_nodes is going to do
2624 bitmap unions into it. */
2626 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node
)->solution
, 0, i
, bi
)
2628 if (find (i
) == i
&& i
!= to
)
2631 queue
.safe_push (i
);
2636 queue
.iterate (queuepos
, &i
);
2639 unify_nodes (graph
, to
, i
, true);
2646 /* Solve the constraint graph GRAPH using our worklist solver.
2647 This is based on the PW* family of solvers from the "Efficient Field
2648 Sensitive Pointer Analysis for C" paper.
2649 It works by iterating over all the graph nodes, processing the complex
2650 constraints and propagating the copy constraints, until everything stops
2651 changed. This corresponds to steps 6-8 in the solving list given above. */
2654 solve_graph (constraint_graph_t graph
)
2656 unsigned int size
= graph
->size
;
2660 changed
= BITMAP_ALLOC (NULL
);
2662 /* Mark all initial non-collapsed nodes as changed. */
2663 for (i
= 1; i
< size
; i
++)
2665 varinfo_t ivi
= get_varinfo (i
);
2666 if (find (i
) == i
&& !bitmap_empty_p (ivi
->solution
)
2667 && ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
2668 || graph
->complex[i
].length () > 0))
2669 bitmap_set_bit (changed
, i
);
2672 /* Allocate a bitmap to be used to store the changed bits. */
2673 pts
= BITMAP_ALLOC (&pta_obstack
);
2675 while (!bitmap_empty_p (changed
))
2678 struct topo_info
*ti
= init_topo_info ();
2681 bitmap_obstack_initialize (&iteration_obstack
);
2683 compute_topo_order (graph
, ti
);
2685 while (ti
->topo_order
.length () != 0)
2688 i
= ti
->topo_order
.pop ();
2690 /* If this variable is not a representative, skip it. */
2694 /* In certain indirect cycle cases, we may merge this
2695 variable to another. */
2696 if (eliminate_indirect_cycles (i
) && find (i
) != i
)
2699 /* If the node has changed, we need to process the
2700 complex constraints and outgoing edges again. */
2701 if (bitmap_clear_bit (changed
, i
))
2706 vec
<constraint_t
> complex = graph
->complex[i
];
2707 varinfo_t vi
= get_varinfo (i
);
2708 bool solution_empty
;
2710 /* Compute the changed set of solution bits. If anything
2711 is in the solution just propagate that. */
2712 if (bitmap_bit_p (vi
->solution
, anything_id
))
2714 /* If anything is also in the old solution there is
2716 ??? But we shouldn't ended up with "changed" set ... */
2718 && bitmap_bit_p (vi
->oldsolution
, anything_id
))
2720 bitmap_copy (pts
, get_varinfo (find (anything_id
))->solution
);
2722 else if (vi
->oldsolution
)
2723 bitmap_and_compl (pts
, vi
->solution
, vi
->oldsolution
);
2725 bitmap_copy (pts
, vi
->solution
);
2727 if (bitmap_empty_p (pts
))
2730 if (vi
->oldsolution
)
2731 bitmap_ior_into (vi
->oldsolution
, pts
);
2734 vi
->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
2735 bitmap_copy (vi
->oldsolution
, pts
);
2738 solution
= vi
->solution
;
2739 solution_empty
= bitmap_empty_p (solution
);
2741 /* Process the complex constraints */
2742 bitmap expanded_pts
= NULL
;
2743 FOR_EACH_VEC_ELT (complex, j
, c
)
2745 /* XXX: This is going to unsort the constraints in
2746 some cases, which will occasionally add duplicate
2747 constraints during unification. This does not
2748 affect correctness. */
2749 c
->lhs
.var
= find (c
->lhs
.var
);
2750 c
->rhs
.var
= find (c
->rhs
.var
);
2752 /* The only complex constraint that can change our
2753 solution to non-empty, given an empty solution,
2754 is a constraint where the lhs side is receiving
2755 some set from elsewhere. */
2756 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2757 do_complex_constraint (graph
, c
, pts
, &expanded_pts
);
2759 BITMAP_FREE (expanded_pts
);
2761 solution_empty
= bitmap_empty_p (solution
);
2763 if (!solution_empty
)
2766 unsigned eff_escaped_id
= find (escaped_id
);
2768 /* Propagate solution to all successors. */
2769 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
2775 unsigned int to
= find (j
);
2776 tmp
= get_varinfo (to
)->solution
;
2779 /* Don't try to propagate to ourselves. */
2783 /* If we propagate from ESCAPED use ESCAPED as
2785 if (i
== eff_escaped_id
)
2786 flag
= bitmap_set_bit (tmp
, escaped_id
);
2788 flag
= bitmap_ior_into (tmp
, pts
);
2791 bitmap_set_bit (changed
, to
);
2796 free_topo_info (ti
);
2797 bitmap_obstack_release (&iteration_obstack
);
2801 BITMAP_FREE (changed
);
2802 bitmap_obstack_release (&oldpta_obstack
);
2805 /* Map from trees to variable infos. */
2806 static hash_map
<tree
, varinfo_t
> *vi_for_tree
;
2809 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2812 insert_vi_for_tree (tree t
, varinfo_t vi
)
2815 gcc_assert (!vi_for_tree
->put (t
, vi
));
2818 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2819 exist in the map, return NULL, otherwise, return the varinfo we found. */
2822 lookup_vi_for_tree (tree t
)
2824 varinfo_t
*slot
= vi_for_tree
->get (t
);
2831 /* Return a printable name for DECL */
2834 alias_get_name (tree decl
)
2836 const char *res
= NULL
;
2838 int num_printed
= 0;
2843 if (TREE_CODE (decl
) == SSA_NAME
)
2845 res
= get_name (decl
);
2847 num_printed
= asprintf (&temp
, "%s_%u", res
, SSA_NAME_VERSION (decl
));
2849 num_printed
= asprintf (&temp
, "_%u", SSA_NAME_VERSION (decl
));
2850 if (num_printed
> 0)
2852 res
= ggc_strdup (temp
);
2856 else if (DECL_P (decl
))
2858 if (DECL_ASSEMBLER_NAME_SET_P (decl
))
2859 res
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
2862 res
= get_name (decl
);
2865 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2866 if (num_printed
> 0)
2868 res
= ggc_strdup (temp
);
2880 /* Find the variable id for tree T in the map.
2881 If T doesn't exist in the map, create an entry for it and return it. */
2884 get_vi_for_tree (tree t
)
2886 varinfo_t
*slot
= vi_for_tree
->get (t
);
2888 return get_varinfo (create_variable_info_for (t
, alias_get_name (t
)));
2893 /* Get a scalar constraint expression for a new temporary variable. */
2895 static struct constraint_expr
2896 new_scalar_tmp_constraint_exp (const char *name
)
2898 struct constraint_expr tmp
;
2901 vi
= new_var_info (NULL_TREE
, name
);
2905 vi
->is_full_var
= 1;
2914 /* Get a constraint expression vector from an SSA_VAR_P node.
2915 If address_p is true, the result will be taken its address of. */
2918 get_constraint_for_ssa_var (tree t
, vec
<ce_s
> *results
, bool address_p
)
2920 struct constraint_expr cexpr
;
2923 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2924 gcc_assert (TREE_CODE (t
) == SSA_NAME
|| DECL_P (t
));
2926 /* For parameters, get at the points-to set for the actual parm
2928 if (TREE_CODE (t
) == SSA_NAME
2929 && SSA_NAME_IS_DEFAULT_DEF (t
)
2930 && (TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2931 || TREE_CODE (SSA_NAME_VAR (t
)) == RESULT_DECL
))
2933 get_constraint_for_ssa_var (SSA_NAME_VAR (t
), results
, address_p
);
2937 /* For global variables resort to the alias target. */
2938 if (TREE_CODE (t
) == VAR_DECL
2939 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
2941 varpool_node
*node
= varpool_node::get (t
);
2942 if (node
&& node
->alias
&& node
->analyzed
)
2944 node
= node
->ultimate_alias_target ();
2949 vi
= get_vi_for_tree (t
);
2951 cexpr
.type
= SCALAR
;
2954 /* If we are not taking the address of the constraint expr, add all
2955 sub-fiels of the variable as well. */
2957 && !vi
->is_full_var
)
2959 for (; vi
; vi
= vi_next (vi
))
2962 results
->safe_push (cexpr
);
2967 results
->safe_push (cexpr
);
2970 /* Process constraint T, performing various simplifications and then
2971 adding it to our list of overall constraints. */
2974 process_constraint (constraint_t t
)
2976 struct constraint_expr rhs
= t
->rhs
;
2977 struct constraint_expr lhs
= t
->lhs
;
2979 gcc_assert (rhs
.var
< varmap
.length ());
2980 gcc_assert (lhs
.var
< varmap
.length ());
2982 /* If we didn't get any useful constraint from the lhs we get
2983 &ANYTHING as fallback from get_constraint_for. Deal with
2984 it here by turning it into *ANYTHING. */
2985 if (lhs
.type
== ADDRESSOF
2986 && lhs
.var
== anything_id
)
2989 /* ADDRESSOF on the lhs is invalid. */
2990 gcc_assert (lhs
.type
!= ADDRESSOF
);
2992 /* We shouldn't add constraints from things that cannot have pointers.
2993 It's not completely trivial to avoid in the callers, so do it here. */
2994 if (rhs
.type
!= ADDRESSOF
2995 && !get_varinfo (rhs
.var
)->may_have_pointers
)
2998 /* Likewise adding to the solution of a non-pointer var isn't useful. */
2999 if (!get_varinfo (lhs
.var
)->may_have_pointers
)
3002 /* This can happen in our IR with things like n->a = *p */
3003 if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
3005 /* Split into tmp = *rhs, *lhs = tmp */
3006 struct constraint_expr tmplhs
;
3007 tmplhs
= new_scalar_tmp_constraint_exp ("doubledereftmp");
3008 process_constraint (new_constraint (tmplhs
, rhs
));
3009 process_constraint (new_constraint (lhs
, tmplhs
));
3011 else if (rhs
.type
== ADDRESSOF
&& lhs
.type
== DEREF
)
3013 /* Split into tmp = &rhs, *lhs = tmp */
3014 struct constraint_expr tmplhs
;
3015 tmplhs
= new_scalar_tmp_constraint_exp ("derefaddrtmp");
3016 process_constraint (new_constraint (tmplhs
, rhs
));
3017 process_constraint (new_constraint (lhs
, tmplhs
));
3021 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
3022 constraints
.safe_push (t
);
3027 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3030 static HOST_WIDE_INT
3031 bitpos_of_field (const tree fdecl
)
3033 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl
))
3034 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl
)))
3037 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl
)) * BITS_PER_UNIT
3038 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl
)));
3042 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3043 resulting constraint expressions in *RESULTS. */
3046 get_constraint_for_ptr_offset (tree ptr
, tree offset
,
3049 struct constraint_expr c
;
3051 HOST_WIDE_INT rhsoffset
;
3053 /* If we do not do field-sensitive PTA adding offsets to pointers
3054 does not change the points-to solution. */
3055 if (!use_field_sensitive
)
3057 get_constraint_for_rhs (ptr
, results
);
3061 /* If the offset is not a non-negative integer constant that fits
3062 in a HOST_WIDE_INT, we have to fall back to a conservative
3063 solution which includes all sub-fields of all pointed-to
3064 variables of ptr. */
3065 if (offset
== NULL_TREE
3066 || TREE_CODE (offset
) != INTEGER_CST
)
3067 rhsoffset
= UNKNOWN_OFFSET
;
3070 /* Sign-extend the offset. */
3071 offset_int soffset
= offset_int::from (offset
, SIGNED
);
3072 if (!wi::fits_shwi_p (soffset
))
3073 rhsoffset
= UNKNOWN_OFFSET
;
3076 /* Make sure the bit-offset also fits. */
3077 HOST_WIDE_INT rhsunitoffset
= soffset
.to_shwi ();
3078 rhsoffset
= rhsunitoffset
* BITS_PER_UNIT
;
3079 if (rhsunitoffset
!= rhsoffset
/ BITS_PER_UNIT
)
3080 rhsoffset
= UNKNOWN_OFFSET
;
3084 get_constraint_for_rhs (ptr
, results
);
3088 /* As we are eventually appending to the solution do not use
3089 vec::iterate here. */
3090 n
= results
->length ();
3091 for (j
= 0; j
< n
; j
++)
3095 curr
= get_varinfo (c
.var
);
3097 if (c
.type
== ADDRESSOF
3098 /* If this varinfo represents a full variable just use it. */
3099 && curr
->is_full_var
)
3101 else if (c
.type
== ADDRESSOF
3102 /* If we do not know the offset add all subfields. */
3103 && rhsoffset
== UNKNOWN_OFFSET
)
3105 varinfo_t temp
= get_varinfo (curr
->head
);
3108 struct constraint_expr c2
;
3110 c2
.type
= ADDRESSOF
;
3112 if (c2
.var
!= c
.var
)
3113 results
->safe_push (c2
);
3114 temp
= vi_next (temp
);
3118 else if (c
.type
== ADDRESSOF
)
3121 unsigned HOST_WIDE_INT offset
= curr
->offset
+ rhsoffset
;
3123 /* If curr->offset + rhsoffset is less than zero adjust it. */
3125 && curr
->offset
< offset
)
3128 /* We have to include all fields that overlap the current
3129 field shifted by rhsoffset. And we include at least
3130 the last or the first field of the variable to represent
3131 reachability of off-bound addresses, in particular &object + 1,
3132 conservatively correct. */
3133 temp
= first_or_preceding_vi_for_offset (curr
, offset
);
3136 temp
= vi_next (temp
);
3138 && temp
->offset
< offset
+ curr
->size
)
3140 struct constraint_expr c2
;
3142 c2
.type
= ADDRESSOF
;
3144 results
->safe_push (c2
);
3145 temp
= vi_next (temp
);
3148 else if (c
.type
== SCALAR
)
3150 gcc_assert (c
.offset
== 0);
3151 c
.offset
= rhsoffset
;
3154 /* We shouldn't get any DEREFs here. */
3162 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3163 If address_p is true the result will be taken its address of.
3164 If lhs_p is true then the constraint expression is assumed to be used
3168 get_constraint_for_component_ref (tree t
, vec
<ce_s
> *results
,
3169 bool address_p
, bool lhs_p
)
3172 HOST_WIDE_INT bitsize
= -1;
3173 HOST_WIDE_INT bitmaxsize
= -1;
3174 HOST_WIDE_INT bitpos
;
3178 /* Some people like to do cute things like take the address of
3181 while (handled_component_p (forzero
)
3182 || INDIRECT_REF_P (forzero
)
3183 || TREE_CODE (forzero
) == MEM_REF
)
3184 forzero
= TREE_OPERAND (forzero
, 0);
3186 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
3188 struct constraint_expr temp
;
3191 temp
.var
= integer_id
;
3193 results
->safe_push (temp
);
3197 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
, &reverse
);
3199 /* Pretend to take the address of the base, we'll take care of
3200 adding the required subset of sub-fields below. */
3201 get_constraint_for_1 (t
, results
, true, lhs_p
);
3202 gcc_assert (results
->length () == 1);
3203 struct constraint_expr
&result
= results
->last ();
3205 if (result
.type
== SCALAR
3206 && get_varinfo (result
.var
)->is_full_var
)
3207 /* For single-field vars do not bother about the offset. */
3209 else if (result
.type
== SCALAR
)
3211 /* In languages like C, you can access one past the end of an
3212 array. You aren't allowed to dereference it, so we can
3213 ignore this constraint. When we handle pointer subtraction,
3214 we may have to do something cute here. */
3216 if ((unsigned HOST_WIDE_INT
)bitpos
< get_varinfo (result
.var
)->fullsize
3219 /* It's also not true that the constraint will actually start at the
3220 right offset, it may start in some padding. We only care about
3221 setting the constraint to the first actual field it touches, so
3223 struct constraint_expr cexpr
= result
;
3227 for (curr
= get_varinfo (cexpr
.var
); curr
; curr
= vi_next (curr
))
3229 if (ranges_overlap_p (curr
->offset
, curr
->size
,
3230 bitpos
, bitmaxsize
))
3232 cexpr
.var
= curr
->id
;
3233 results
->safe_push (cexpr
);
3238 /* If we are going to take the address of this field then
3239 to be able to compute reachability correctly add at least
3240 the last field of the variable. */
3241 if (address_p
&& results
->length () == 0)
3243 curr
= get_varinfo (cexpr
.var
);
3244 while (curr
->next
!= 0)
3245 curr
= vi_next (curr
);
3246 cexpr
.var
= curr
->id
;
3247 results
->safe_push (cexpr
);
3249 else if (results
->length () == 0)
3250 /* Assert that we found *some* field there. The user couldn't be
3251 accessing *only* padding. */
3252 /* Still the user could access one past the end of an array
3253 embedded in a struct resulting in accessing *only* padding. */
3254 /* Or accessing only padding via type-punning to a type
3255 that has a filed just in padding space. */
3257 cexpr
.type
= SCALAR
;
3258 cexpr
.var
= anything_id
;
3260 results
->safe_push (cexpr
);
3263 else if (bitmaxsize
== 0)
3265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3266 fprintf (dump_file
, "Access to zero-sized part of variable,"
3270 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3271 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
3273 else if (result
.type
== DEREF
)
3275 /* If we do not know exactly where the access goes say so. Note
3276 that only for non-structure accesses we know that we access
3277 at most one subfiled of any variable. */
3279 || bitsize
!= bitmaxsize
3280 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t
))
3281 || result
.offset
== UNKNOWN_OFFSET
)
3282 result
.offset
= UNKNOWN_OFFSET
;
3284 result
.offset
+= bitpos
;
3286 else if (result
.type
== ADDRESSOF
)
3288 /* We can end up here for component references on a
3289 VIEW_CONVERT_EXPR <>(&foobar). */
3290 result
.type
= SCALAR
;
3291 result
.var
= anything_id
;
3299 /* Dereference the constraint expression CONS, and return the result.
3300 DEREF (ADDRESSOF) = SCALAR
3301 DEREF (SCALAR) = DEREF
3302 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3303 This is needed so that we can handle dereferencing DEREF constraints. */
3306 do_deref (vec
<ce_s
> *constraints
)
3308 struct constraint_expr
*c
;
3311 FOR_EACH_VEC_ELT (*constraints
, i
, c
)
3313 if (c
->type
== SCALAR
)
3315 else if (c
->type
== ADDRESSOF
)
3317 else if (c
->type
== DEREF
)
3319 struct constraint_expr tmplhs
;
3320 tmplhs
= new_scalar_tmp_constraint_exp ("dereftmp");
3321 process_constraint (new_constraint (tmplhs
, *c
));
3322 c
->var
= tmplhs
.var
;
3329 /* Given a tree T, return the constraint expression for taking the
3333 get_constraint_for_address_of (tree t
, vec
<ce_s
> *results
)
3335 struct constraint_expr
*c
;
3338 get_constraint_for_1 (t
, results
, true, true);
3340 FOR_EACH_VEC_ELT (*results
, i
, c
)
3342 if (c
->type
== DEREF
)
3345 c
->type
= ADDRESSOF
;
3349 /* Given a tree T, return the constraint expression for it. */
3352 get_constraint_for_1 (tree t
, vec
<ce_s
> *results
, bool address_p
,
3355 struct constraint_expr temp
;
3357 /* x = integer is all glommed to a single variable, which doesn't
3358 point to anything by itself. That is, of course, unless it is an
3359 integer constant being treated as a pointer, in which case, we
3360 will return that this is really the addressof anything. This
3361 happens below, since it will fall into the default case. The only
3362 case we know something about an integer treated like a pointer is
3363 when it is the NULL pointer, and then we just say it points to
3366 Do not do that if -fno-delete-null-pointer-checks though, because
3367 in that case *NULL does not fail, so it _should_ alias *anything.
3368 It is not worth adding a new option or renaming the existing one,
3369 since this case is relatively obscure. */
3370 if ((TREE_CODE (t
) == INTEGER_CST
3371 && integer_zerop (t
))
3372 /* The only valid CONSTRUCTORs in gimple with pointer typed
3373 elements are zero-initializer. But in IPA mode we also
3374 process global initializers, so verify at least. */
3375 || (TREE_CODE (t
) == CONSTRUCTOR
3376 && CONSTRUCTOR_NELTS (t
) == 0))
3378 if (flag_delete_null_pointer_checks
)
3379 temp
.var
= nothing_id
;
3381 temp
.var
= nonlocal_id
;
3382 temp
.type
= ADDRESSOF
;
3384 results
->safe_push (temp
);
3388 /* String constants are read-only, ideally we'd have a CONST_DECL
3390 if (TREE_CODE (t
) == STRING_CST
)
3392 temp
.var
= string_id
;
3395 results
->safe_push (temp
);
3399 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
3401 case tcc_expression
:
3403 switch (TREE_CODE (t
))
3406 get_constraint_for_address_of (TREE_OPERAND (t
, 0), results
);
3414 switch (TREE_CODE (t
))
3418 struct constraint_expr cs
;
3420 get_constraint_for_ptr_offset (TREE_OPERAND (t
, 0),
3421 TREE_OPERAND (t
, 1), results
);
3424 /* If we are not taking the address then make sure to process
3425 all subvariables we might access. */
3429 cs
= results
->last ();
3430 if (cs
.type
== DEREF
3431 && type_can_have_subvars (TREE_TYPE (t
)))
3433 /* For dereferences this means we have to defer it
3435 results
->last ().offset
= UNKNOWN_OFFSET
;
3438 if (cs
.type
!= SCALAR
)
3441 vi
= get_varinfo (cs
.var
);
3442 curr
= vi_next (vi
);
3443 if (!vi
->is_full_var
3446 unsigned HOST_WIDE_INT size
;
3447 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t
))))
3448 size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t
)));
3451 for (; curr
; curr
= vi_next (curr
))
3453 if (curr
->offset
- vi
->offset
< size
)
3456 results
->safe_push (cs
);
3465 case ARRAY_RANGE_REF
:
3467 get_constraint_for_component_ref (t
, results
, address_p
, lhs_p
);
3469 case VIEW_CONVERT_EXPR
:
3470 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, address_p
,
3473 /* We are missing handling for TARGET_MEM_REF here. */
3478 case tcc_exceptional
:
3480 switch (TREE_CODE (t
))
3484 get_constraint_for_ssa_var (t
, results
, address_p
);
3492 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t
), i
, val
)
3494 struct constraint_expr
*rhsp
;
3496 get_constraint_for_1 (val
, &tmp
, address_p
, lhs_p
);
3497 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
3498 results
->safe_push (*rhsp
);
3501 /* We do not know whether the constructor was complete,
3502 so technically we have to add &NOTHING or &ANYTHING
3503 like we do for an empty constructor as well. */
3510 case tcc_declaration
:
3512 get_constraint_for_ssa_var (t
, results
, address_p
);
3517 /* We cannot refer to automatic variables through constants. */
3518 temp
.type
= ADDRESSOF
;
3519 temp
.var
= nonlocal_id
;
3521 results
->safe_push (temp
);
3527 /* The default fallback is a constraint from anything. */
3528 temp
.type
= ADDRESSOF
;
3529 temp
.var
= anything_id
;
3531 results
->safe_push (temp
);
3534 /* Given a gimple tree T, return the constraint expression vector for it. */
3537 get_constraint_for (tree t
, vec
<ce_s
> *results
)
3539 gcc_assert (results
->length () == 0);
3541 get_constraint_for_1 (t
, results
, false, true);
3544 /* Given a gimple tree T, return the constraint expression vector for it
3545 to be used as the rhs of a constraint. */
3548 get_constraint_for_rhs (tree t
, vec
<ce_s
> *results
)
3550 gcc_assert (results
->length () == 0);
3552 get_constraint_for_1 (t
, results
, false, false);
3556 /* Efficiently generates constraints from all entries in *RHSC to all
3557 entries in *LHSC. */
3560 process_all_all_constraints (vec
<ce_s
> lhsc
,
3563 struct constraint_expr
*lhsp
, *rhsp
;
3566 if (lhsc
.length () <= 1 || rhsc
.length () <= 1)
3568 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3569 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
3570 process_constraint (new_constraint (*lhsp
, *rhsp
));
3574 struct constraint_expr tmp
;
3575 tmp
= new_scalar_tmp_constraint_exp ("allalltmp");
3576 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
3577 process_constraint (new_constraint (tmp
, *rhsp
));
3578 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3579 process_constraint (new_constraint (*lhsp
, tmp
));
3583 /* Handle aggregate copies by expanding into copies of the respective
3584 fields of the structures. */
3587 do_structure_copy (tree lhsop
, tree rhsop
)
3589 struct constraint_expr
*lhsp
, *rhsp
;
3590 auto_vec
<ce_s
> lhsc
;
3591 auto_vec
<ce_s
> rhsc
;
3594 get_constraint_for (lhsop
, &lhsc
);
3595 get_constraint_for_rhs (rhsop
, &rhsc
);
3598 if (lhsp
->type
== DEREF
3599 || (lhsp
->type
== ADDRESSOF
&& lhsp
->var
== anything_id
)
3600 || rhsp
->type
== DEREF
)
3602 if (lhsp
->type
== DEREF
)
3604 gcc_assert (lhsc
.length () == 1);
3605 lhsp
->offset
= UNKNOWN_OFFSET
;
3607 if (rhsp
->type
== DEREF
)
3609 gcc_assert (rhsc
.length () == 1);
3610 rhsp
->offset
= UNKNOWN_OFFSET
;
3612 process_all_all_constraints (lhsc
, rhsc
);
3614 else if (lhsp
->type
== SCALAR
3615 && (rhsp
->type
== SCALAR
3616 || rhsp
->type
== ADDRESSOF
))
3618 HOST_WIDE_INT lhssize
, lhsmaxsize
, lhsoffset
;
3619 HOST_WIDE_INT rhssize
, rhsmaxsize
, rhsoffset
;
3622 get_ref_base_and_extent (lhsop
, &lhsoffset
, &lhssize
, &lhsmaxsize
,
3624 get_ref_base_and_extent (rhsop
, &rhsoffset
, &rhssize
, &rhsmaxsize
,
3626 for (j
= 0; lhsc
.iterate (j
, &lhsp
);)
3628 varinfo_t lhsv
, rhsv
;
3630 lhsv
= get_varinfo (lhsp
->var
);
3631 rhsv
= get_varinfo (rhsp
->var
);
3632 if (lhsv
->may_have_pointers
3633 && (lhsv
->is_full_var
3634 || rhsv
->is_full_var
3635 || ranges_overlap_p (lhsv
->offset
+ rhsoffset
, lhsv
->size
,
3636 rhsv
->offset
+ lhsoffset
, rhsv
->size
)))
3637 process_constraint (new_constraint (*lhsp
, *rhsp
));
3638 if (!rhsv
->is_full_var
3639 && (lhsv
->is_full_var
3640 || (lhsv
->offset
+ rhsoffset
+ lhsv
->size
3641 > rhsv
->offset
+ lhsoffset
+ rhsv
->size
)))
3644 if (k
>= rhsc
.length ())
3655 /* Create constraints ID = { rhsc }. */
3658 make_constraints_to (unsigned id
, vec
<ce_s
> rhsc
)
3660 struct constraint_expr
*c
;
3661 struct constraint_expr includes
;
3665 includes
.offset
= 0;
3666 includes
.type
= SCALAR
;
3668 FOR_EACH_VEC_ELT (rhsc
, j
, c
)
3669 process_constraint (new_constraint (includes
, *c
));
3672 /* Create a constraint ID = OP. */
3675 make_constraint_to (unsigned id
, tree op
)
3677 auto_vec
<ce_s
> rhsc
;
3678 get_constraint_for_rhs (op
, &rhsc
);
3679 make_constraints_to (id
, rhsc
);
3682 /* Create a constraint ID = &FROM. */
3685 make_constraint_from (varinfo_t vi
, int from
)
3687 struct constraint_expr lhs
, rhs
;
3695 rhs
.type
= ADDRESSOF
;
3696 process_constraint (new_constraint (lhs
, rhs
));
3699 /* Create a constraint ID = FROM. */
3702 make_copy_constraint (varinfo_t vi
, int from
)
3704 struct constraint_expr lhs
, rhs
;
3713 process_constraint (new_constraint (lhs
, rhs
));
3716 /* Make constraints necessary to make OP escape. */
3719 make_escape_constraint (tree op
)
3721 make_constraint_to (escaped_id
, op
);
3724 /* Add constraints to that the solution of VI is transitively closed. */
3727 make_transitive_closure_constraints (varinfo_t vi
)
3729 struct constraint_expr lhs
, rhs
;
3737 rhs
.offset
= UNKNOWN_OFFSET
;
3738 process_constraint (new_constraint (lhs
, rhs
));
3741 /* Temporary storage for fake var decls. */
3742 struct obstack fake_var_decl_obstack
;
3744 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3747 build_fake_var_decl (tree type
)
3749 tree decl
= (tree
) XOBNEW (&fake_var_decl_obstack
, struct tree_var_decl
);
3750 memset (decl
, 0, sizeof (struct tree_var_decl
));
3751 TREE_SET_CODE (decl
, VAR_DECL
);
3752 TREE_TYPE (decl
) = type
;
3753 DECL_UID (decl
) = allocate_decl_uid ();
3754 SET_DECL_PT_UID (decl
, -1);
3755 layout_decl (decl
, 0);
3759 /* Create a new artificial heap variable with NAME.
3760 Return the created variable. */
3763 make_heapvar (const char *name
)
3768 heapvar
= build_fake_var_decl (ptr_type_node
);
3769 DECL_EXTERNAL (heapvar
) = 1;
3771 vi
= new_var_info (heapvar
, name
);
3772 vi
->is_artificial_var
= true;
3773 vi
->is_heap_var
= true;
3774 vi
->is_unknown_size_var
= true;
3778 vi
->is_full_var
= true;
3779 insert_vi_for_tree (heapvar
, vi
);
3784 /* Create a new artificial heap variable with NAME and make a
3785 constraint from it to LHS. Set flags according to a tag used
3786 for tracking restrict pointers. */
3789 make_constraint_from_restrict (varinfo_t lhs
, const char *name
)
3791 varinfo_t vi
= make_heapvar (name
);
3792 vi
->is_global_var
= 1;
3793 vi
->may_have_pointers
= 1;
3794 make_constraint_from (lhs
, vi
->id
);
3798 /* Create a new artificial heap variable with NAME and make a
3799 constraint from it to LHS. Set flags according to a tag used
3800 for tracking restrict pointers and make the artificial heap
3801 point to global memory. */
3804 make_constraint_from_global_restrict (varinfo_t lhs
, const char *name
)
3806 varinfo_t vi
= make_constraint_from_restrict (lhs
, name
);
3807 make_copy_constraint (vi
, nonlocal_id
);
3811 /* In IPA mode there are varinfos for different aspects of reach
3812 function designator. One for the points-to set of the return
3813 value, one for the variables that are clobbered by the function,
3814 one for its uses and one for each parameter (including a single
3815 glob for remaining variadic arguments). */
3817 enum { fi_clobbers
= 1, fi_uses
= 2,
3818 fi_static_chain
= 3, fi_result
= 4, fi_parm_base
= 5 };
3820 /* Get a constraint for the requested part of a function designator FI
3821 when operating in IPA mode. */
3823 static struct constraint_expr
3824 get_function_part_constraint (varinfo_t fi
, unsigned part
)
3826 struct constraint_expr c
;
3828 gcc_assert (in_ipa_mode
);
3830 if (fi
->id
== anything_id
)
3832 /* ??? We probably should have a ANYFN special variable. */
3833 c
.var
= anything_id
;
3837 else if (TREE_CODE (fi
->decl
) == FUNCTION_DECL
)
3839 varinfo_t ai
= first_vi_for_offset (fi
, part
);
3843 c
.var
= anything_id
;
3857 /* For non-IPA mode, generate constraints necessary for a call on the
3861 handle_rhs_call (gimple stmt
, vec
<ce_s
> *results
)
3863 struct constraint_expr rhsc
;
3865 bool returns_uses
= false;
3867 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3869 tree arg
= gimple_call_arg (stmt
, i
);
3870 int flags
= gimple_call_arg_flags (stmt
, i
);
3872 /* If the argument is not used we can ignore it. */
3873 if (flags
& EAF_UNUSED
)
3876 /* As we compute ESCAPED context-insensitive we do not gain
3877 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3878 set. The argument would still get clobbered through the
3880 if ((flags
& EAF_NOCLOBBER
)
3881 && (flags
& EAF_NOESCAPE
))
3883 varinfo_t uses
= get_call_use_vi (stmt
);
3884 if (!(flags
& EAF_DIRECT
))
3886 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg");
3887 make_constraint_to (tem
->id
, arg
);
3888 make_transitive_closure_constraints (tem
);
3889 make_copy_constraint (uses
, tem
->id
);
3892 make_constraint_to (uses
->id
, arg
);
3893 returns_uses
= true;
3895 else if (flags
& EAF_NOESCAPE
)
3897 struct constraint_expr lhs
, rhs
;
3898 varinfo_t uses
= get_call_use_vi (stmt
);
3899 varinfo_t clobbers
= get_call_clobber_vi (stmt
);
3900 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg");
3901 make_constraint_to (tem
->id
, arg
);
3902 if (!(flags
& EAF_DIRECT
))
3903 make_transitive_closure_constraints (tem
);
3904 make_copy_constraint (uses
, tem
->id
);
3905 make_copy_constraint (clobbers
, tem
->id
);
3906 /* Add *tem = nonlocal, do not add *tem = callused as
3907 EAF_NOESCAPE parameters do not escape to other parameters
3908 and all other uses appear in NONLOCAL as well. */
3913 rhs
.var
= nonlocal_id
;
3915 process_constraint (new_constraint (lhs
, rhs
));
3916 returns_uses
= true;
3919 make_escape_constraint (arg
);
3922 /* If we added to the calls uses solution make sure we account for
3923 pointers to it to be returned. */
3926 rhsc
.var
= get_call_use_vi (stmt
)->id
;
3929 results
->safe_push (rhsc
);
3932 /* The static chain escapes as well. */
3933 if (gimple_call_chain (stmt
))
3934 make_escape_constraint (gimple_call_chain (stmt
));
3936 /* And if we applied NRV the address of the return slot escapes as well. */
3937 if (gimple_call_return_slot_opt_p (stmt
)
3938 && gimple_call_lhs (stmt
) != NULL_TREE
3939 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
3941 auto_vec
<ce_s
> tmpc
;
3942 struct constraint_expr lhsc
, *c
;
3943 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
3944 lhsc
.var
= escaped_id
;
3947 FOR_EACH_VEC_ELT (tmpc
, i
, c
)
3948 process_constraint (new_constraint (lhsc
, *c
));
3951 /* Regular functions return nonlocal memory. */
3952 rhsc
.var
= nonlocal_id
;
3955 results
->safe_push (rhsc
);
3958 /* For non-IPA mode, generate constraints necessary for a call
3959 that returns a pointer and assigns it to LHS. This simply makes
3960 the LHS point to global and escaped variables. */
3963 handle_lhs_call (gimple stmt
, tree lhs
, int flags
, vec
<ce_s
> rhsc
,
3966 auto_vec
<ce_s
> lhsc
;
3968 get_constraint_for (lhs
, &lhsc
);
3969 /* If the store is to a global decl make sure to
3970 add proper escape constraints. */
3971 lhs
= get_base_address (lhs
);
3974 && is_global_var (lhs
))
3976 struct constraint_expr tmpc
;
3977 tmpc
.var
= escaped_id
;
3980 lhsc
.safe_push (tmpc
);
3983 /* If the call returns an argument unmodified override the rhs
3985 if (flags
& ERF_RETURNS_ARG
3986 && (flags
& ERF_RETURN_ARG_MASK
) < gimple_call_num_args (stmt
))
3990 arg
= gimple_call_arg (stmt
, flags
& ERF_RETURN_ARG_MASK
);
3991 get_constraint_for (arg
, &rhsc
);
3992 process_all_all_constraints (lhsc
, rhsc
);
3995 else if (flags
& ERF_NOALIAS
)
3998 struct constraint_expr tmpc
;
4000 vi
= make_heapvar ("HEAP");
4001 /* We are marking allocated storage local, we deal with it becoming
4002 global by escaping and setting of vars_contains_escaped_heap. */
4003 DECL_EXTERNAL (vi
->decl
) = 0;
4004 vi
->is_global_var
= 0;
4005 /* If this is not a real malloc call assume the memory was
4006 initialized and thus may point to global memory. All
4007 builtin functions with the malloc attribute behave in a sane way. */
4009 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
4010 make_constraint_from (vi
, nonlocal_id
);
4013 tmpc
.type
= ADDRESSOF
;
4014 rhsc
.safe_push (tmpc
);
4015 process_all_all_constraints (lhsc
, rhsc
);
4019 process_all_all_constraints (lhsc
, rhsc
);
4022 /* For non-IPA mode, generate constraints necessary for a call of a
4023 const function that returns a pointer in the statement STMT. */
4026 handle_const_call (gimple stmt
, vec
<ce_s
> *results
)
4028 struct constraint_expr rhsc
;
4031 /* Treat nested const functions the same as pure functions as far
4032 as the static chain is concerned. */
4033 if (gimple_call_chain (stmt
))
4035 varinfo_t uses
= get_call_use_vi (stmt
);
4036 make_transitive_closure_constraints (uses
);
4037 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4038 rhsc
.var
= uses
->id
;
4041 results
->safe_push (rhsc
);
4044 /* May return arguments. */
4045 for (k
= 0; k
< gimple_call_num_args (stmt
); ++k
)
4047 tree arg
= gimple_call_arg (stmt
, k
);
4048 auto_vec
<ce_s
> argc
;
4050 struct constraint_expr
*argp
;
4051 get_constraint_for_rhs (arg
, &argc
);
4052 FOR_EACH_VEC_ELT (argc
, i
, argp
)
4053 results
->safe_push (*argp
);
4056 /* May return addresses of globals. */
4057 rhsc
.var
= nonlocal_id
;
4059 rhsc
.type
= ADDRESSOF
;
4060 results
->safe_push (rhsc
);
4063 /* For non-IPA mode, generate constraints necessary for a call to a
4064 pure function in statement STMT. */
4067 handle_pure_call (gimple stmt
, vec
<ce_s
> *results
)
4069 struct constraint_expr rhsc
;
4071 varinfo_t uses
= NULL
;
4073 /* Memory reached from pointer arguments is call-used. */
4074 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
4076 tree arg
= gimple_call_arg (stmt
, i
);
4079 uses
= get_call_use_vi (stmt
);
4080 make_transitive_closure_constraints (uses
);
4082 make_constraint_to (uses
->id
, arg
);
4085 /* The static chain is used as well. */
4086 if (gimple_call_chain (stmt
))
4090 uses
= get_call_use_vi (stmt
);
4091 make_transitive_closure_constraints (uses
);
4093 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4096 /* Pure functions may return call-used and nonlocal memory. */
4099 rhsc
.var
= uses
->id
;
4102 results
->safe_push (rhsc
);
4104 rhsc
.var
= nonlocal_id
;
4107 results
->safe_push (rhsc
);
4111 /* Return the varinfo for the callee of CALL. */
4114 get_fi_for_callee (gimple call
)
4116 tree decl
, fn
= gimple_call_fn (call
);
4118 if (fn
&& TREE_CODE (fn
) == OBJ_TYPE_REF
)
4119 fn
= OBJ_TYPE_REF_EXPR (fn
);
4121 /* If we can directly resolve the function being called, do so.
4122 Otherwise, it must be some sort of indirect expression that
4123 we should still be able to handle. */
4124 decl
= gimple_call_addr_fndecl (fn
);
4126 return get_vi_for_tree (decl
);
4128 /* If the function is anything other than a SSA name pointer we have no
4129 clue and should be getting ANYFN (well, ANYTHING for now). */
4130 if (!fn
|| TREE_CODE (fn
) != SSA_NAME
)
4131 return get_varinfo (anything_id
);
4133 if (SSA_NAME_IS_DEFAULT_DEF (fn
)
4134 && (TREE_CODE (SSA_NAME_VAR (fn
)) == PARM_DECL
4135 || TREE_CODE (SSA_NAME_VAR (fn
)) == RESULT_DECL
))
4136 fn
= SSA_NAME_VAR (fn
);
4138 return get_vi_for_tree (fn
);
4141 /* Create constraints for the builtin call T. Return true if the call
4142 was handled, otherwise false. */
4145 find_func_aliases_for_builtin_call (struct function
*fn
, gimple t
)
4147 tree fndecl
= gimple_call_fndecl (t
);
4148 auto_vec
<ce_s
, 2> lhsc
;
4149 auto_vec
<ce_s
, 4> rhsc
;
4152 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
4153 /* ??? All builtins that are handled here need to be handled
4154 in the alias-oracle query functions explicitly! */
4155 switch (DECL_FUNCTION_CODE (fndecl
))
4157 /* All the following functions return a pointer to the same object
4158 as their first argument points to. The functions do not add
4159 to the ESCAPED solution. The functions make the first argument
4160 pointed to memory point to what the second argument pointed to
4161 memory points to. */
4162 case BUILT_IN_STRCPY
:
4163 case BUILT_IN_STRNCPY
:
4164 case BUILT_IN_BCOPY
:
4165 case BUILT_IN_MEMCPY
:
4166 case BUILT_IN_MEMMOVE
:
4167 case BUILT_IN_MEMPCPY
:
4168 case BUILT_IN_STPCPY
:
4169 case BUILT_IN_STPNCPY
:
4170 case BUILT_IN_STRCAT
:
4171 case BUILT_IN_STRNCAT
:
4172 case BUILT_IN_STRCPY_CHK
:
4173 case BUILT_IN_STRNCPY_CHK
:
4174 case BUILT_IN_MEMCPY_CHK
:
4175 case BUILT_IN_MEMMOVE_CHK
:
4176 case BUILT_IN_MEMPCPY_CHK
:
4177 case BUILT_IN_STPCPY_CHK
:
4178 case BUILT_IN_STPNCPY_CHK
:
4179 case BUILT_IN_STRCAT_CHK
:
4180 case BUILT_IN_STRNCAT_CHK
:
4181 case BUILT_IN_TM_MEMCPY
:
4182 case BUILT_IN_TM_MEMMOVE
:
4184 tree res
= gimple_call_lhs (t
);
4185 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4186 == BUILT_IN_BCOPY
? 1 : 0));
4187 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4188 == BUILT_IN_BCOPY
? 0 : 1));
4189 if (res
!= NULL_TREE
)
4191 get_constraint_for (res
, &lhsc
);
4192 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY
4193 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY
4194 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY
4195 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY_CHK
4196 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY_CHK
4197 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY_CHK
)
4198 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &rhsc
);
4200 get_constraint_for (dest
, &rhsc
);
4201 process_all_all_constraints (lhsc
, rhsc
);
4205 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4206 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4209 process_all_all_constraints (lhsc
, rhsc
);
4212 case BUILT_IN_MEMSET
:
4213 case BUILT_IN_MEMSET_CHK
:
4214 case BUILT_IN_TM_MEMSET
:
4216 tree res
= gimple_call_lhs (t
);
4217 tree dest
= gimple_call_arg (t
, 0);
4220 struct constraint_expr ac
;
4221 if (res
!= NULL_TREE
)
4223 get_constraint_for (res
, &lhsc
);
4224 get_constraint_for (dest
, &rhsc
);
4225 process_all_all_constraints (lhsc
, rhsc
);
4228 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4230 if (flag_delete_null_pointer_checks
4231 && integer_zerop (gimple_call_arg (t
, 1)))
4233 ac
.type
= ADDRESSOF
;
4234 ac
.var
= nothing_id
;
4239 ac
.var
= integer_id
;
4242 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4243 process_constraint (new_constraint (*lhsp
, ac
));
4246 case BUILT_IN_POSIX_MEMALIGN
:
4248 tree ptrptr
= gimple_call_arg (t
, 0);
4249 get_constraint_for (ptrptr
, &lhsc
);
4251 varinfo_t vi
= make_heapvar ("HEAP");
4252 /* We are marking allocated storage local, we deal with it becoming
4253 global by escaping and setting of vars_contains_escaped_heap. */
4254 DECL_EXTERNAL (vi
->decl
) = 0;
4255 vi
->is_global_var
= 0;
4256 struct constraint_expr tmpc
;
4259 tmpc
.type
= ADDRESSOF
;
4260 rhsc
.safe_push (tmpc
);
4261 process_all_all_constraints (lhsc
, rhsc
);
4264 case BUILT_IN_ASSUME_ALIGNED
:
4266 tree res
= gimple_call_lhs (t
);
4267 tree dest
= gimple_call_arg (t
, 0);
4268 if (res
!= NULL_TREE
)
4270 get_constraint_for (res
, &lhsc
);
4271 get_constraint_for (dest
, &rhsc
);
4272 process_all_all_constraints (lhsc
, rhsc
);
4276 /* All the following functions do not return pointers, do not
4277 modify the points-to sets of memory reachable from their
4278 arguments and do not add to the ESCAPED solution. */
4279 case BUILT_IN_SINCOS
:
4280 case BUILT_IN_SINCOSF
:
4281 case BUILT_IN_SINCOSL
:
4282 case BUILT_IN_FREXP
:
4283 case BUILT_IN_FREXPF
:
4284 case BUILT_IN_FREXPL
:
4285 case BUILT_IN_GAMMA_R
:
4286 case BUILT_IN_GAMMAF_R
:
4287 case BUILT_IN_GAMMAL_R
:
4288 case BUILT_IN_LGAMMA_R
:
4289 case BUILT_IN_LGAMMAF_R
:
4290 case BUILT_IN_LGAMMAL_R
:
4292 case BUILT_IN_MODFF
:
4293 case BUILT_IN_MODFL
:
4294 case BUILT_IN_REMQUO
:
4295 case BUILT_IN_REMQUOF
:
4296 case BUILT_IN_REMQUOL
:
4299 case BUILT_IN_STRDUP
:
4300 case BUILT_IN_STRNDUP
:
4301 case BUILT_IN_REALLOC
:
4302 if (gimple_call_lhs (t
))
4304 handle_lhs_call (t
, gimple_call_lhs (t
),
4305 gimple_call_return_flags (t
) | ERF_NOALIAS
,
4307 get_constraint_for_ptr_offset (gimple_call_lhs (t
),
4309 get_constraint_for_ptr_offset (gimple_call_arg (t
, 0),
4313 process_all_all_constraints (lhsc
, rhsc
);
4316 /* For realloc the resulting pointer can be equal to the
4317 argument as well. But only doing this wouldn't be
4318 correct because with ptr == 0 realloc behaves like malloc. */
4319 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_REALLOC
)
4321 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4322 get_constraint_for (gimple_call_arg (t
, 0), &rhsc
);
4323 process_all_all_constraints (lhsc
, rhsc
);
4328 /* String / character search functions return a pointer into the
4329 source string or NULL. */
4330 case BUILT_IN_INDEX
:
4331 case BUILT_IN_STRCHR
:
4332 case BUILT_IN_STRRCHR
:
4333 case BUILT_IN_MEMCHR
:
4334 case BUILT_IN_STRSTR
:
4335 case BUILT_IN_STRPBRK
:
4336 if (gimple_call_lhs (t
))
4338 tree src
= gimple_call_arg (t
, 0);
4339 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4340 constraint_expr nul
;
4341 nul
.var
= nothing_id
;
4343 nul
.type
= ADDRESSOF
;
4344 rhsc
.safe_push (nul
);
4345 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4346 process_all_all_constraints (lhsc
, rhsc
);
4349 /* Trampolines are special - they set up passing the static
4351 case BUILT_IN_INIT_TRAMPOLINE
:
4353 tree tramp
= gimple_call_arg (t
, 0);
4354 tree nfunc
= gimple_call_arg (t
, 1);
4355 tree frame
= gimple_call_arg (t
, 2);
4357 struct constraint_expr lhs
, *rhsp
;
4360 varinfo_t nfi
= NULL
;
4361 gcc_assert (TREE_CODE (nfunc
) == ADDR_EXPR
);
4362 nfi
= lookup_vi_for_tree (TREE_OPERAND (nfunc
, 0));
4365 lhs
= get_function_part_constraint (nfi
, fi_static_chain
);
4366 get_constraint_for (frame
, &rhsc
);
4367 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4368 process_constraint (new_constraint (lhs
, *rhsp
));
4371 /* Make the frame point to the function for
4372 the trampoline adjustment call. */
4373 get_constraint_for (tramp
, &lhsc
);
4375 get_constraint_for (nfunc
, &rhsc
);
4376 process_all_all_constraints (lhsc
, rhsc
);
4381 /* Else fallthru to generic handling which will let
4382 the frame escape. */
4385 case BUILT_IN_ADJUST_TRAMPOLINE
:
4387 tree tramp
= gimple_call_arg (t
, 0);
4388 tree res
= gimple_call_lhs (t
);
4389 if (in_ipa_mode
&& res
)
4391 get_constraint_for (res
, &lhsc
);
4392 get_constraint_for (tramp
, &rhsc
);
4394 process_all_all_constraints (lhsc
, rhsc
);
4398 CASE_BUILT_IN_TM_STORE (1):
4399 CASE_BUILT_IN_TM_STORE (2):
4400 CASE_BUILT_IN_TM_STORE (4):
4401 CASE_BUILT_IN_TM_STORE (8):
4402 CASE_BUILT_IN_TM_STORE (FLOAT
):
4403 CASE_BUILT_IN_TM_STORE (DOUBLE
):
4404 CASE_BUILT_IN_TM_STORE (LDOUBLE
):
4405 CASE_BUILT_IN_TM_STORE (M64
):
4406 CASE_BUILT_IN_TM_STORE (M128
):
4407 CASE_BUILT_IN_TM_STORE (M256
):
4409 tree addr
= gimple_call_arg (t
, 0);
4410 tree src
= gimple_call_arg (t
, 1);
4412 get_constraint_for (addr
, &lhsc
);
4414 get_constraint_for (src
, &rhsc
);
4415 process_all_all_constraints (lhsc
, rhsc
);
4418 CASE_BUILT_IN_TM_LOAD (1):
4419 CASE_BUILT_IN_TM_LOAD (2):
4420 CASE_BUILT_IN_TM_LOAD (4):
4421 CASE_BUILT_IN_TM_LOAD (8):
4422 CASE_BUILT_IN_TM_LOAD (FLOAT
):
4423 CASE_BUILT_IN_TM_LOAD (DOUBLE
):
4424 CASE_BUILT_IN_TM_LOAD (LDOUBLE
):
4425 CASE_BUILT_IN_TM_LOAD (M64
):
4426 CASE_BUILT_IN_TM_LOAD (M128
):
4427 CASE_BUILT_IN_TM_LOAD (M256
):
4429 tree dest
= gimple_call_lhs (t
);
4430 tree addr
= gimple_call_arg (t
, 0);
4432 get_constraint_for (dest
, &lhsc
);
4433 get_constraint_for (addr
, &rhsc
);
4435 process_all_all_constraints (lhsc
, rhsc
);
4438 /* Variadic argument handling needs to be handled in IPA
4440 case BUILT_IN_VA_START
:
4442 tree valist
= gimple_call_arg (t
, 0);
4443 struct constraint_expr rhs
, *lhsp
;
4445 get_constraint_for (valist
, &lhsc
);
4447 /* The va_list gets access to pointers in variadic
4448 arguments. Which we know in the case of IPA analysis
4449 and otherwise are just all nonlocal variables. */
4452 fi
= lookup_vi_for_tree (fn
->decl
);
4453 rhs
= get_function_part_constraint (fi
, ~0);
4454 rhs
.type
= ADDRESSOF
;
4458 rhs
.var
= nonlocal_id
;
4459 rhs
.type
= ADDRESSOF
;
4462 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4463 process_constraint (new_constraint (*lhsp
, rhs
));
4464 /* va_list is clobbered. */
4465 make_constraint_to (get_call_clobber_vi (t
)->id
, valist
);
4468 /* va_end doesn't have any effect that matters. */
4469 case BUILT_IN_VA_END
:
4471 /* Alternate return. Simply give up for now. */
4472 case BUILT_IN_RETURN
:
4476 || !(fi
= get_vi_for_tree (fn
->decl
)))
4477 make_constraint_from (get_varinfo (escaped_id
), anything_id
);
4478 else if (in_ipa_mode
4481 struct constraint_expr lhs
, rhs
;
4482 lhs
= get_function_part_constraint (fi
, fi_result
);
4483 rhs
.var
= anything_id
;
4486 process_constraint (new_constraint (lhs
, rhs
));
4490 /* printf-style functions may have hooks to set pointers to
4491 point to somewhere into the generated string. Leave them
4492 for a later exercise... */
4494 /* Fallthru to general call handling. */;
4500 /* Create constraints for the call T. */
4503 find_func_aliases_for_call (struct function
*fn
, gimple t
)
4505 tree fndecl
= gimple_call_fndecl (t
);
4508 if (fndecl
!= NULL_TREE
4509 && DECL_BUILT_IN (fndecl
)
4510 && find_func_aliases_for_builtin_call (fn
, t
))
4513 fi
= get_fi_for_callee (t
);
4515 || (fndecl
&& !fi
->is_fn_info
))
4517 auto_vec
<ce_s
, 16> rhsc
;
4518 int flags
= gimple_call_flags (t
);
4520 /* Const functions can return their arguments and addresses
4521 of global memory but not of escaped memory. */
4522 if (flags
& (ECF_CONST
|ECF_NOVOPS
))
4524 if (gimple_call_lhs (t
))
4525 handle_const_call (t
, &rhsc
);
4527 /* Pure functions can return addresses in and of memory
4528 reachable from their arguments, but they are not an escape
4529 point for reachable memory of their arguments. */
4530 else if (flags
& (ECF_PURE
|ECF_LOOPING_CONST_OR_PURE
))
4531 handle_pure_call (t
, &rhsc
);
4533 handle_rhs_call (t
, &rhsc
);
4534 if (gimple_call_lhs (t
))
4535 handle_lhs_call (t
, gimple_call_lhs (t
),
4536 gimple_call_return_flags (t
), rhsc
, fndecl
);
4540 auto_vec
<ce_s
, 2> rhsc
;
4544 /* Assign all the passed arguments to the appropriate incoming
4545 parameters of the function. */
4546 for (j
= 0; j
< gimple_call_num_args (t
); j
++)
4548 struct constraint_expr lhs
;
4549 struct constraint_expr
*rhsp
;
4550 tree arg
= gimple_call_arg (t
, j
);
4552 get_constraint_for_rhs (arg
, &rhsc
);
4553 lhs
= get_function_part_constraint (fi
, fi_parm_base
+ j
);
4554 while (rhsc
.length () != 0)
4556 rhsp
= &rhsc
.last ();
4557 process_constraint (new_constraint (lhs
, *rhsp
));
4562 /* If we are returning a value, assign it to the result. */
4563 lhsop
= gimple_call_lhs (t
);
4566 auto_vec
<ce_s
, 2> lhsc
;
4567 struct constraint_expr rhs
;
4568 struct constraint_expr
*lhsp
;
4570 get_constraint_for (lhsop
, &lhsc
);
4571 rhs
= get_function_part_constraint (fi
, fi_result
);
4573 && DECL_RESULT (fndecl
)
4574 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4576 auto_vec
<ce_s
, 2> tem
;
4577 tem
.quick_push (rhs
);
4579 gcc_checking_assert (tem
.length () == 1);
4582 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4583 process_constraint (new_constraint (*lhsp
, rhs
));
4586 /* If we pass the result decl by reference, honor that. */
4589 && DECL_RESULT (fndecl
)
4590 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4592 struct constraint_expr lhs
;
4593 struct constraint_expr
*rhsp
;
4595 get_constraint_for_address_of (lhsop
, &rhsc
);
4596 lhs
= get_function_part_constraint (fi
, fi_result
);
4597 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4598 process_constraint (new_constraint (lhs
, *rhsp
));
4602 /* If we use a static chain, pass it along. */
4603 if (gimple_call_chain (t
))
4605 struct constraint_expr lhs
;
4606 struct constraint_expr
*rhsp
;
4608 get_constraint_for (gimple_call_chain (t
), &rhsc
);
4609 lhs
= get_function_part_constraint (fi
, fi_static_chain
);
4610 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4611 process_constraint (new_constraint (lhs
, *rhsp
));
4616 /* Walk statement T setting up aliasing constraints according to the
4617 references found in T. This function is the main part of the
4618 constraint builder. AI points to auxiliary alias information used
4619 when building alias sets and computing alias grouping heuristics. */
4622 find_func_aliases (struct function
*fn
, gimple origt
)
4625 auto_vec
<ce_s
, 16> lhsc
;
4626 auto_vec
<ce_s
, 16> rhsc
;
4627 struct constraint_expr
*c
;
4630 /* Now build constraints expressions. */
4631 if (gimple_code (t
) == GIMPLE_PHI
)
4636 /* For a phi node, assign all the arguments to
4638 get_constraint_for (gimple_phi_result (t
), &lhsc
);
4639 for (i
= 0; i
< gimple_phi_num_args (t
); i
++)
4641 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
4643 STRIP_NOPS (strippedrhs
);
4644 get_constraint_for_rhs (gimple_phi_arg_def (t
, i
), &rhsc
);
4646 FOR_EACH_VEC_ELT (lhsc
, j
, c
)
4648 struct constraint_expr
*c2
;
4649 while (rhsc
.length () > 0)
4652 process_constraint (new_constraint (*c
, *c2
));
4658 /* In IPA mode, we need to generate constraints to pass call
4659 arguments through their calls. There are two cases,
4660 either a GIMPLE_CALL returning a value, or just a plain
4661 GIMPLE_CALL when we are not.
4663 In non-ipa mode, we need to generate constraints for each
4664 pointer passed by address. */
4665 else if (is_gimple_call (t
))
4666 find_func_aliases_for_call (fn
, t
);
4668 /* Otherwise, just a regular assignment statement. Only care about
4669 operations with pointer result, others are dealt with as escape
4670 points if they have pointer operands. */
4671 else if (is_gimple_assign (t
))
4673 /* Otherwise, just a regular assignment statement. */
4674 tree lhsop
= gimple_assign_lhs (t
);
4675 tree rhsop
= (gimple_num_ops (t
) == 2) ? gimple_assign_rhs1 (t
) : NULL
;
4677 if (rhsop
&& TREE_CLOBBER_P (rhsop
))
4678 /* Ignore clobbers, they don't actually store anything into
4681 else if (rhsop
&& AGGREGATE_TYPE_P (TREE_TYPE (lhsop
)))
4682 do_structure_copy (lhsop
, rhsop
);
4685 enum tree_code code
= gimple_assign_rhs_code (t
);
4687 get_constraint_for (lhsop
, &lhsc
);
4689 if (FLOAT_TYPE_P (TREE_TYPE (lhsop
)))
4690 /* If the operation produces a floating point result then
4691 assume the value is not produced to transfer a pointer. */
4693 else if (code
== POINTER_PLUS_EXPR
)
4694 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4695 gimple_assign_rhs2 (t
), &rhsc
);
4696 else if (code
== BIT_AND_EXPR
4697 && TREE_CODE (gimple_assign_rhs2 (t
)) == INTEGER_CST
)
4699 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4700 the pointer. Handle it by offsetting it by UNKNOWN. */
4701 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4704 else if ((CONVERT_EXPR_CODE_P (code
)
4705 && !(POINTER_TYPE_P (gimple_expr_type (t
))
4706 && !POINTER_TYPE_P (TREE_TYPE (rhsop
))))
4707 || gimple_assign_single_p (t
))
4708 get_constraint_for_rhs (rhsop
, &rhsc
);
4709 else if (code
== COND_EXPR
)
4711 /* The result is a merge of both COND_EXPR arms. */
4712 auto_vec
<ce_s
, 2> tmp
;
4713 struct constraint_expr
*rhsp
;
4715 get_constraint_for_rhs (gimple_assign_rhs2 (t
), &rhsc
);
4716 get_constraint_for_rhs (gimple_assign_rhs3 (t
), &tmp
);
4717 FOR_EACH_VEC_ELT (tmp
, i
, rhsp
)
4718 rhsc
.safe_push (*rhsp
);
4720 else if (truth_value_p (code
))
4721 /* Truth value results are not pointer (parts). Or at least
4722 very very unreasonable obfuscation of a part. */
4726 /* All other operations are merges. */
4727 auto_vec
<ce_s
, 4> tmp
;
4728 struct constraint_expr
*rhsp
;
4730 get_constraint_for_rhs (gimple_assign_rhs1 (t
), &rhsc
);
4731 for (i
= 2; i
< gimple_num_ops (t
); ++i
)
4733 get_constraint_for_rhs (gimple_op (t
, i
), &tmp
);
4734 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
4735 rhsc
.safe_push (*rhsp
);
4739 process_all_all_constraints (lhsc
, rhsc
);
4741 /* If there is a store to a global variable the rhs escapes. */
4742 if ((lhsop
= get_base_address (lhsop
)) != NULL_TREE
4744 && is_global_var (lhsop
)
4746 || DECL_EXTERNAL (lhsop
) || TREE_PUBLIC (lhsop
)))
4747 make_escape_constraint (rhsop
);
4749 /* Handle escapes through return. */
4750 else if (gimple_code (t
) == GIMPLE_RETURN
4751 && gimple_return_retval (t
) != NULL_TREE
)
4755 || !(fi
= get_vi_for_tree (fn
->decl
)))
4756 make_escape_constraint (gimple_return_retval (t
));
4757 else if (in_ipa_mode
4760 struct constraint_expr lhs
;
4761 struct constraint_expr
*rhsp
;
4764 lhs
= get_function_part_constraint (fi
, fi_result
);
4765 get_constraint_for_rhs (gimple_return_retval (t
), &rhsc
);
4766 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4767 process_constraint (new_constraint (lhs
, *rhsp
));
4770 /* Handle asms conservatively by adding escape constraints to everything. */
4771 else if (gimple_code (t
) == GIMPLE_ASM
)
4773 unsigned i
, noutputs
;
4774 const char **oconstraints
;
4775 const char *constraint
;
4776 bool allows_mem
, allows_reg
, is_inout
;
4778 noutputs
= gimple_asm_noutputs (t
);
4779 oconstraints
= XALLOCAVEC (const char *, noutputs
);
4781 for (i
= 0; i
< noutputs
; ++i
)
4783 tree link
= gimple_asm_output_op (t
, i
);
4784 tree op
= TREE_VALUE (link
);
4786 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4787 oconstraints
[i
] = constraint
;
4788 parse_output_constraint (&constraint
, i
, 0, 0, &allows_mem
,
4789 &allows_reg
, &is_inout
);
4791 /* A memory constraint makes the address of the operand escape. */
4792 if (!allows_reg
&& allows_mem
)
4793 make_escape_constraint (build_fold_addr_expr (op
));
4795 /* The asm may read global memory, so outputs may point to
4796 any global memory. */
4799 auto_vec
<ce_s
, 2> lhsc
;
4800 struct constraint_expr rhsc
, *lhsp
;
4802 get_constraint_for (op
, &lhsc
);
4803 rhsc
.var
= nonlocal_id
;
4806 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4807 process_constraint (new_constraint (*lhsp
, rhsc
));
4810 for (i
= 0; i
< gimple_asm_ninputs (t
); ++i
)
4812 tree link
= gimple_asm_input_op (t
, i
);
4813 tree op
= TREE_VALUE (link
);
4815 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4817 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0, oconstraints
,
4818 &allows_mem
, &allows_reg
);
4820 /* A memory constraint makes the address of the operand escape. */
4821 if (!allows_reg
&& allows_mem
)
4822 make_escape_constraint (build_fold_addr_expr (op
));
4823 /* Strictly we'd only need the constraint to ESCAPED if
4824 the asm clobbers memory, otherwise using something
4825 along the lines of per-call clobbers/uses would be enough. */
4827 make_escape_constraint (op
);
4833 /* Create a constraint adding to the clobber set of FI the memory
4834 pointed to by PTR. */
4837 process_ipa_clobber (varinfo_t fi
, tree ptr
)
4839 vec
<ce_s
> ptrc
= vNULL
;
4840 struct constraint_expr
*c
, lhs
;
4842 get_constraint_for_rhs (ptr
, &ptrc
);
4843 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4844 FOR_EACH_VEC_ELT (ptrc
, i
, c
)
4845 process_constraint (new_constraint (lhs
, *c
));
4849 /* Walk statement T setting up clobber and use constraints according to the
4850 references found in T. This function is a main part of the
4851 IPA constraint builder. */
4854 find_func_clobbers (struct function
*fn
, gimple origt
)
4857 auto_vec
<ce_s
, 16> lhsc
;
4858 auto_vec
<ce_s
, 16> rhsc
;
4861 /* Add constraints for clobbered/used in IPA mode.
4862 We are not interested in what automatic variables are clobbered
4863 or used as we only use the information in the caller to which
4864 they do not escape. */
4865 gcc_assert (in_ipa_mode
);
4867 /* If the stmt refers to memory in any way it better had a VUSE. */
4868 if (gimple_vuse (t
) == NULL_TREE
)
4871 /* We'd better have function information for the current function. */
4872 fi
= lookup_vi_for_tree (fn
->decl
);
4873 gcc_assert (fi
!= NULL
);
4875 /* Account for stores in assignments and calls. */
4876 if (gimple_vdef (t
) != NULL_TREE
4877 && gimple_has_lhs (t
))
4879 tree lhs
= gimple_get_lhs (t
);
4881 while (handled_component_p (tem
))
4882 tem
= TREE_OPERAND (tem
, 0);
4884 && !auto_var_in_fn_p (tem
, fn
->decl
))
4885 || INDIRECT_REF_P (tem
)
4886 || (TREE_CODE (tem
) == MEM_REF
4887 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
4889 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
4891 struct constraint_expr lhsc
, *rhsp
;
4893 lhsc
= get_function_part_constraint (fi
, fi_clobbers
);
4894 get_constraint_for_address_of (lhs
, &rhsc
);
4895 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4896 process_constraint (new_constraint (lhsc
, *rhsp
));
4901 /* Account for uses in assigments and returns. */
4902 if (gimple_assign_single_p (t
)
4903 || (gimple_code (t
) == GIMPLE_RETURN
4904 && gimple_return_retval (t
) != NULL_TREE
))
4906 tree rhs
= (gimple_assign_single_p (t
)
4907 ? gimple_assign_rhs1 (t
) : gimple_return_retval (t
));
4909 while (handled_component_p (tem
))
4910 tem
= TREE_OPERAND (tem
, 0);
4912 && !auto_var_in_fn_p (tem
, fn
->decl
))
4913 || INDIRECT_REF_P (tem
)
4914 || (TREE_CODE (tem
) == MEM_REF
4915 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
4917 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
4919 struct constraint_expr lhs
, *rhsp
;
4921 lhs
= get_function_part_constraint (fi
, fi_uses
);
4922 get_constraint_for_address_of (rhs
, &rhsc
);
4923 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4924 process_constraint (new_constraint (lhs
, *rhsp
));
4929 if (is_gimple_call (t
))
4931 varinfo_t cfi
= NULL
;
4932 tree decl
= gimple_call_fndecl (t
);
4933 struct constraint_expr lhs
, rhs
;
4936 /* For builtins we do not have separate function info. For those
4937 we do not generate escapes for we have to generate clobbers/uses. */
4938 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
4939 switch (DECL_FUNCTION_CODE (decl
))
4941 /* The following functions use and clobber memory pointed to
4942 by their arguments. */
4943 case BUILT_IN_STRCPY
:
4944 case BUILT_IN_STRNCPY
:
4945 case BUILT_IN_BCOPY
:
4946 case BUILT_IN_MEMCPY
:
4947 case BUILT_IN_MEMMOVE
:
4948 case BUILT_IN_MEMPCPY
:
4949 case BUILT_IN_STPCPY
:
4950 case BUILT_IN_STPNCPY
:
4951 case BUILT_IN_STRCAT
:
4952 case BUILT_IN_STRNCAT
:
4953 case BUILT_IN_STRCPY_CHK
:
4954 case BUILT_IN_STRNCPY_CHK
:
4955 case BUILT_IN_MEMCPY_CHK
:
4956 case BUILT_IN_MEMMOVE_CHK
:
4957 case BUILT_IN_MEMPCPY_CHK
:
4958 case BUILT_IN_STPCPY_CHK
:
4959 case BUILT_IN_STPNCPY_CHK
:
4960 case BUILT_IN_STRCAT_CHK
:
4961 case BUILT_IN_STRNCAT_CHK
:
4963 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
4964 == BUILT_IN_BCOPY
? 1 : 0));
4965 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
4966 == BUILT_IN_BCOPY
? 0 : 1));
4968 struct constraint_expr
*rhsp
, *lhsp
;
4969 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4970 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4971 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4972 process_constraint (new_constraint (lhs
, *lhsp
));
4973 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4974 lhs
= get_function_part_constraint (fi
, fi_uses
);
4975 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4976 process_constraint (new_constraint (lhs
, *rhsp
));
4979 /* The following function clobbers memory pointed to by
4981 case BUILT_IN_MEMSET
:
4982 case BUILT_IN_MEMSET_CHK
:
4983 case BUILT_IN_POSIX_MEMALIGN
:
4985 tree dest
= gimple_call_arg (t
, 0);
4988 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4989 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4990 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4991 process_constraint (new_constraint (lhs
, *lhsp
));
4994 /* The following functions clobber their second and third
4996 case BUILT_IN_SINCOS
:
4997 case BUILT_IN_SINCOSF
:
4998 case BUILT_IN_SINCOSL
:
5000 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5001 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5004 /* The following functions clobber their second argument. */
5005 case BUILT_IN_FREXP
:
5006 case BUILT_IN_FREXPF
:
5007 case BUILT_IN_FREXPL
:
5008 case BUILT_IN_LGAMMA_R
:
5009 case BUILT_IN_LGAMMAF_R
:
5010 case BUILT_IN_LGAMMAL_R
:
5011 case BUILT_IN_GAMMA_R
:
5012 case BUILT_IN_GAMMAF_R
:
5013 case BUILT_IN_GAMMAL_R
:
5015 case BUILT_IN_MODFF
:
5016 case BUILT_IN_MODFL
:
5018 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5021 /* The following functions clobber their third argument. */
5022 case BUILT_IN_REMQUO
:
5023 case BUILT_IN_REMQUOF
:
5024 case BUILT_IN_REMQUOL
:
5026 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5029 /* The following functions neither read nor clobber memory. */
5030 case BUILT_IN_ASSUME_ALIGNED
:
5033 /* Trampolines are of no interest to us. */
5034 case BUILT_IN_INIT_TRAMPOLINE
:
5035 case BUILT_IN_ADJUST_TRAMPOLINE
:
5037 case BUILT_IN_VA_START
:
5038 case BUILT_IN_VA_END
:
5040 /* printf-style functions may have hooks to set pointers to
5041 point to somewhere into the generated string. Leave them
5042 for a later exercise... */
5044 /* Fallthru to general call handling. */;
5047 /* Parameters passed by value are used. */
5048 lhs
= get_function_part_constraint (fi
, fi_uses
);
5049 for (i
= 0; i
< gimple_call_num_args (t
); i
++)
5051 struct constraint_expr
*rhsp
;
5052 tree arg
= gimple_call_arg (t
, i
);
5054 if (TREE_CODE (arg
) == SSA_NAME
5055 || is_gimple_min_invariant (arg
))
5058 get_constraint_for_address_of (arg
, &rhsc
);
5059 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5060 process_constraint (new_constraint (lhs
, *rhsp
));
5064 /* Build constraints for propagating clobbers/uses along the
5066 cfi
= get_fi_for_callee (t
);
5067 if (cfi
->id
== anything_id
)
5069 if (gimple_vdef (t
))
5070 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5072 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5077 /* For callees without function info (that's external functions),
5078 ESCAPED is clobbered and used. */
5079 if (gimple_call_fndecl (t
)
5080 && !cfi
->is_fn_info
)
5084 if (gimple_vdef (t
))
5085 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5087 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
), escaped_id
);
5089 /* Also honor the call statement use/clobber info. */
5090 if ((vi
= lookup_call_clobber_vi (t
)) != NULL
)
5091 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5093 if ((vi
= lookup_call_use_vi (t
)) != NULL
)
5094 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
),
5099 /* Otherwise the caller clobbers and uses what the callee does.
5100 ??? This should use a new complex constraint that filters
5101 local variables of the callee. */
5102 if (gimple_vdef (t
))
5104 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5105 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5106 process_constraint (new_constraint (lhs
, rhs
));
5108 lhs
= get_function_part_constraint (fi
, fi_uses
);
5109 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5110 process_constraint (new_constraint (lhs
, rhs
));
5112 else if (gimple_code (t
) == GIMPLE_ASM
)
5114 /* ??? Ick. We can do better. */
5115 if (gimple_vdef (t
))
5116 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5118 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5124 /* Find the first varinfo in the same variable as START that overlaps with
5125 OFFSET. Return NULL if we can't find one. */
5128 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
5130 /* If the offset is outside of the variable, bail out. */
5131 if (offset
>= start
->fullsize
)
5134 /* If we cannot reach offset from start, lookup the first field
5135 and start from there. */
5136 if (start
->offset
> offset
)
5137 start
= get_varinfo (start
->head
);
5141 /* We may not find a variable in the field list with the actual
5142 offset when when we have glommed a structure to a variable.
5143 In that case, however, offset should still be within the size
5145 if (offset
>= start
->offset
5146 && (offset
- start
->offset
) < start
->size
)
5149 start
= vi_next (start
);
5155 /* Find the first varinfo in the same variable as START that overlaps with
5156 OFFSET. If there is no such varinfo the varinfo directly preceding
5157 OFFSET is returned. */
5160 first_or_preceding_vi_for_offset (varinfo_t start
,
5161 unsigned HOST_WIDE_INT offset
)
5163 /* If we cannot reach offset from start, lookup the first field
5164 and start from there. */
5165 if (start
->offset
> offset
)
5166 start
= get_varinfo (start
->head
);
5168 /* We may not find a variable in the field list with the actual
5169 offset when when we have glommed a structure to a variable.
5170 In that case, however, offset should still be within the size
5172 If we got beyond the offset we look for return the field
5173 directly preceding offset which may be the last field. */
5175 && offset
>= start
->offset
5176 && !((offset
- start
->offset
) < start
->size
))
5177 start
= vi_next (start
);
5183 /* This structure is used during pushing fields onto the fieldstack
5184 to track the offset of the field, since bitpos_of_field gives it
5185 relative to its immediate containing type, and we want it relative
5186 to the ultimate containing object. */
5190 /* Offset from the base of the base containing object to this field. */
5191 HOST_WIDE_INT offset
;
5193 /* Size, in bits, of the field. */
5194 unsigned HOST_WIDE_INT size
;
5196 unsigned has_unknown_size
: 1;
5198 unsigned must_have_pointers
: 1;
5200 unsigned may_have_pointers
: 1;
5202 unsigned only_restrict_pointers
: 1;
5204 typedef struct fieldoff fieldoff_s
;
5207 /* qsort comparison function for two fieldoff's PA and PB */
5210 fieldoff_compare (const void *pa
, const void *pb
)
5212 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
5213 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
5214 unsigned HOST_WIDE_INT foasize
, fobsize
;
5216 if (foa
->offset
< fob
->offset
)
5218 else if (foa
->offset
> fob
->offset
)
5221 foasize
= foa
->size
;
5222 fobsize
= fob
->size
;
5223 if (foasize
< fobsize
)
5225 else if (foasize
> fobsize
)
5230 /* Sort a fieldstack according to the field offset and sizes. */
5232 sort_fieldstack (vec
<fieldoff_s
> fieldstack
)
5234 fieldstack
.qsort (fieldoff_compare
);
5237 /* Return true if T is a type that can have subvars. */
5240 type_can_have_subvars (const_tree t
)
5242 /* Aggregates without overlapping fields can have subvars. */
5243 return TREE_CODE (t
) == RECORD_TYPE
;
5246 /* Return true if V is a tree that we can have subvars for.
5247 Normally, this is any aggregate type. Also complex
5248 types which are not gimple registers can have subvars. */
5251 var_can_have_subvars (const_tree v
)
5253 /* Volatile variables should never have subvars. */
5254 if (TREE_THIS_VOLATILE (v
))
5257 /* Non decls or memory tags can never have subvars. */
5261 return type_can_have_subvars (TREE_TYPE (v
));
5264 /* Return true if T is a type that does contain pointers. */
5267 type_must_have_pointers (tree type
)
5269 if (POINTER_TYPE_P (type
))
5272 if (TREE_CODE (type
) == ARRAY_TYPE
)
5273 return type_must_have_pointers (TREE_TYPE (type
));
5275 /* A function or method can have pointers as arguments, so track
5276 those separately. */
5277 if (TREE_CODE (type
) == FUNCTION_TYPE
5278 || TREE_CODE (type
) == METHOD_TYPE
)
5285 field_must_have_pointers (tree t
)
5287 return type_must_have_pointers (TREE_TYPE (t
));
5290 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5291 the fields of TYPE onto fieldstack, recording their offsets along
5294 OFFSET is used to keep track of the offset in this entire
5295 structure, rather than just the immediately containing structure.
5296 Returns false if the caller is supposed to handle the field we
5300 push_fields_onto_fieldstack (tree type
, vec
<fieldoff_s
> *fieldstack
,
5301 HOST_WIDE_INT offset
)
5304 bool empty_p
= true;
5306 if (TREE_CODE (type
) != RECORD_TYPE
)
5309 /* If the vector of fields is growing too big, bail out early.
5310 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5312 if (fieldstack
->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5315 for (field
= TYPE_FIELDS (type
); field
; field
= DECL_CHAIN (field
))
5316 if (TREE_CODE (field
) == FIELD_DECL
)
5319 HOST_WIDE_INT foff
= bitpos_of_field (field
);
5321 if (!var_can_have_subvars (field
)
5322 || TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
5323 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
)
5325 else if (!push_fields_onto_fieldstack
5326 (TREE_TYPE (field
), fieldstack
, offset
+ foff
)
5327 && (DECL_SIZE (field
)
5328 && !integer_zerop (DECL_SIZE (field
))))
5329 /* Empty structures may have actual size, like in C++. So
5330 see if we didn't push any subfields and the size is
5331 nonzero, push the field onto the stack. */
5336 fieldoff_s
*pair
= NULL
;
5337 bool has_unknown_size
= false;
5338 bool must_have_pointers_p
;
5340 if (!fieldstack
->is_empty ())
5341 pair
= &fieldstack
->last ();
5343 /* If there isn't anything at offset zero, create sth. */
5345 && offset
+ foff
!= 0)
5347 fieldoff_s e
= {0, offset
+ foff
, false, false, false, false};
5348 pair
= fieldstack
->safe_push (e
);
5351 if (!DECL_SIZE (field
)
5352 || !tree_fits_uhwi_p (DECL_SIZE (field
)))
5353 has_unknown_size
= true;
5355 /* If adjacent fields do not contain pointers merge them. */
5356 must_have_pointers_p
= field_must_have_pointers (field
);
5358 && !has_unknown_size
5359 && !must_have_pointers_p
5360 && !pair
->must_have_pointers
5361 && !pair
->has_unknown_size
5362 && pair
->offset
+ (HOST_WIDE_INT
)pair
->size
== offset
+ foff
)
5364 pair
->size
+= tree_to_uhwi (DECL_SIZE (field
));
5369 e
.offset
= offset
+ foff
;
5370 e
.has_unknown_size
= has_unknown_size
;
5371 if (!has_unknown_size
)
5372 e
.size
= tree_to_uhwi (DECL_SIZE (field
));
5375 e
.must_have_pointers
= must_have_pointers_p
;
5376 e
.may_have_pointers
= true;
5377 e
.only_restrict_pointers
5378 = (!has_unknown_size
5379 && POINTER_TYPE_P (TREE_TYPE (field
))
5380 && TYPE_RESTRICT (TREE_TYPE (field
)));
5381 fieldstack
->safe_push (e
);
5391 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5392 if it is a varargs function. */
5395 count_num_arguments (tree decl
, bool *is_varargs
)
5397 unsigned int num
= 0;
5400 /* Capture named arguments for K&R functions. They do not
5401 have a prototype and thus no TYPE_ARG_TYPES. */
5402 for (t
= DECL_ARGUMENTS (decl
); t
; t
= DECL_CHAIN (t
))
5405 /* Check if the function has variadic arguments. */
5406 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
)); t
; t
= TREE_CHAIN (t
))
5407 if (TREE_VALUE (t
) == void_type_node
)
5415 /* Creation function node for DECL, using NAME, and return the index
5416 of the variable we've created for the function. */
5419 create_function_info_for (tree decl
, const char *name
)
5421 struct function
*fn
= DECL_STRUCT_FUNCTION (decl
);
5422 varinfo_t vi
, prev_vi
;
5425 bool is_varargs
= false;
5426 unsigned int num_args
= count_num_arguments (decl
, &is_varargs
);
5428 /* Create the variable info. */
5430 vi
= new_var_info (decl
, name
);
5433 vi
->fullsize
= fi_parm_base
+ num_args
;
5435 vi
->may_have_pointers
= false;
5438 insert_vi_for_tree (vi
->decl
, vi
);
5442 /* Create a variable for things the function clobbers and one for
5443 things the function uses. */
5445 varinfo_t clobbervi
, usevi
;
5446 const char *newname
;
5449 asprintf (&tempname
, "%s.clobber", name
);
5450 newname
= ggc_strdup (tempname
);
5453 clobbervi
= new_var_info (NULL
, newname
);
5454 clobbervi
->offset
= fi_clobbers
;
5455 clobbervi
->size
= 1;
5456 clobbervi
->fullsize
= vi
->fullsize
;
5457 clobbervi
->is_full_var
= true;
5458 clobbervi
->is_global_var
= false;
5459 gcc_assert (prev_vi
->offset
< clobbervi
->offset
);
5460 prev_vi
->next
= clobbervi
->id
;
5461 prev_vi
= clobbervi
;
5463 asprintf (&tempname
, "%s.use", name
);
5464 newname
= ggc_strdup (tempname
);
5467 usevi
= new_var_info (NULL
, newname
);
5468 usevi
->offset
= fi_uses
;
5470 usevi
->fullsize
= vi
->fullsize
;
5471 usevi
->is_full_var
= true;
5472 usevi
->is_global_var
= false;
5473 gcc_assert (prev_vi
->offset
< usevi
->offset
);
5474 prev_vi
->next
= usevi
->id
;
5478 /* And one for the static chain. */
5479 if (fn
->static_chain_decl
!= NULL_TREE
)
5482 const char *newname
;
5485 asprintf (&tempname
, "%s.chain", name
);
5486 newname
= ggc_strdup (tempname
);
5489 chainvi
= new_var_info (fn
->static_chain_decl
, newname
);
5490 chainvi
->offset
= fi_static_chain
;
5492 chainvi
->fullsize
= vi
->fullsize
;
5493 chainvi
->is_full_var
= true;
5494 chainvi
->is_global_var
= false;
5495 gcc_assert (prev_vi
->offset
< chainvi
->offset
);
5496 prev_vi
->next
= chainvi
->id
;
5498 insert_vi_for_tree (fn
->static_chain_decl
, chainvi
);
5501 /* Create a variable for the return var. */
5502 if (DECL_RESULT (decl
) != NULL
5503 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
5506 const char *newname
;
5508 tree resultdecl
= decl
;
5510 if (DECL_RESULT (decl
))
5511 resultdecl
= DECL_RESULT (decl
);
5513 asprintf (&tempname
, "%s.result", name
);
5514 newname
= ggc_strdup (tempname
);
5517 resultvi
= new_var_info (resultdecl
, newname
);
5518 resultvi
->offset
= fi_result
;
5520 resultvi
->fullsize
= vi
->fullsize
;
5521 resultvi
->is_full_var
= true;
5522 if (DECL_RESULT (decl
))
5523 resultvi
->may_have_pointers
= true;
5524 gcc_assert (prev_vi
->offset
< resultvi
->offset
);
5525 prev_vi
->next
= resultvi
->id
;
5527 if (DECL_RESULT (decl
))
5528 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
5531 /* Set up variables for each argument. */
5532 arg
= DECL_ARGUMENTS (decl
);
5533 for (i
= 0; i
< num_args
; i
++)
5536 const char *newname
;
5538 tree argdecl
= decl
;
5543 asprintf (&tempname
, "%s.arg%d", name
, i
);
5544 newname
= ggc_strdup (tempname
);
5547 argvi
= new_var_info (argdecl
, newname
);
5548 argvi
->offset
= fi_parm_base
+ i
;
5550 argvi
->is_full_var
= true;
5551 argvi
->fullsize
= vi
->fullsize
;
5553 argvi
->may_have_pointers
= true;
5554 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5555 prev_vi
->next
= argvi
->id
;
5559 insert_vi_for_tree (arg
, argvi
);
5560 arg
= DECL_CHAIN (arg
);
5564 /* Add one representative for all further args. */
5568 const char *newname
;
5572 asprintf (&tempname
, "%s.varargs", name
);
5573 newname
= ggc_strdup (tempname
);
5576 /* We need sth that can be pointed to for va_start. */
5577 decl
= build_fake_var_decl (ptr_type_node
);
5579 argvi
= new_var_info (decl
, newname
);
5580 argvi
->offset
= fi_parm_base
+ num_args
;
5582 argvi
->is_full_var
= true;
5583 argvi
->is_heap_var
= true;
5584 argvi
->fullsize
= vi
->fullsize
;
5585 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5586 prev_vi
->next
= argvi
->id
;
5594 /* Return true if FIELDSTACK contains fields that overlap.
5595 FIELDSTACK is assumed to be sorted by offset. */
5598 check_for_overlaps (vec
<fieldoff_s
> fieldstack
)
5600 fieldoff_s
*fo
= NULL
;
5602 HOST_WIDE_INT lastoffset
= -1;
5604 FOR_EACH_VEC_ELT (fieldstack
, i
, fo
)
5606 if (fo
->offset
== lastoffset
)
5608 lastoffset
= fo
->offset
;
5613 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5614 This will also create any varinfo structures necessary for fields
5618 create_variable_info_for_1 (tree decl
, const char *name
)
5620 varinfo_t vi
, newvi
;
5621 tree decl_type
= TREE_TYPE (decl
);
5622 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decl_type
);
5623 auto_vec
<fieldoff_s
> fieldstack
;
5626 varpool_node
*vnode
;
5629 || !tree_fits_uhwi_p (declsize
))
5631 vi
= new_var_info (decl
, name
);
5635 vi
->is_unknown_size_var
= true;
5636 vi
->is_full_var
= true;
5637 vi
->may_have_pointers
= true;
5641 /* Collect field information. */
5642 if (use_field_sensitive
5643 && var_can_have_subvars (decl
)
5644 /* ??? Force us to not use subfields for global initializers
5645 in IPA mode. Else we'd have to parse arbitrary initializers. */
5647 && is_global_var (decl
)
5648 && (vnode
= varpool_node::get (decl
))
5649 && vnode
->get_constructor ()))
5651 fieldoff_s
*fo
= NULL
;
5652 bool notokay
= false;
5655 push_fields_onto_fieldstack (decl_type
, &fieldstack
, 0);
5657 for (i
= 0; !notokay
&& fieldstack
.iterate (i
, &fo
); i
++)
5658 if (fo
->has_unknown_size
5665 /* We can't sort them if we have a field with a variable sized type,
5666 which will make notokay = true. In that case, we are going to return
5667 without creating varinfos for the fields anyway, so sorting them is a
5671 sort_fieldstack (fieldstack
);
5672 /* Due to some C++ FE issues, like PR 22488, we might end up
5673 what appear to be overlapping fields even though they,
5674 in reality, do not overlap. Until the C++ FE is fixed,
5675 we will simply disable field-sensitivity for these cases. */
5676 notokay
= check_for_overlaps (fieldstack
);
5680 fieldstack
.release ();
5683 /* If we didn't end up collecting sub-variables create a full
5684 variable for the decl. */
5685 if (fieldstack
.length () <= 1
5686 || fieldstack
.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5688 vi
= new_var_info (decl
, name
);
5690 vi
->may_have_pointers
= true;
5691 vi
->fullsize
= tree_to_uhwi (declsize
);
5692 vi
->size
= vi
->fullsize
;
5693 vi
->is_full_var
= true;
5694 fieldstack
.release ();
5698 vi
= new_var_info (decl
, name
);
5699 vi
->fullsize
= tree_to_uhwi (declsize
);
5700 for (i
= 0, newvi
= vi
;
5701 fieldstack
.iterate (i
, &fo
);
5702 ++i
, newvi
= vi_next (newvi
))
5704 const char *newname
= "NULL";
5709 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
5710 "+" HOST_WIDE_INT_PRINT_DEC
, name
, fo
->offset
, fo
->size
);
5711 newname
= ggc_strdup (tempname
);
5714 newvi
->name
= newname
;
5715 newvi
->offset
= fo
->offset
;
5716 newvi
->size
= fo
->size
;
5717 newvi
->fullsize
= vi
->fullsize
;
5718 newvi
->may_have_pointers
= fo
->may_have_pointers
;
5719 newvi
->only_restrict_pointers
= fo
->only_restrict_pointers
;
5720 if (i
+ 1 < fieldstack
.length ())
5722 varinfo_t tem
= new_var_info (decl
, name
);
5723 newvi
->next
= tem
->id
;
5732 create_variable_info_for (tree decl
, const char *name
)
5734 varinfo_t vi
= create_variable_info_for_1 (decl
, name
);
5735 unsigned int id
= vi
->id
;
5737 insert_vi_for_tree (decl
, vi
);
5739 if (TREE_CODE (decl
) != VAR_DECL
)
5742 /* Create initial constraints for globals. */
5743 for (; vi
; vi
= vi_next (vi
))
5745 if (!vi
->may_have_pointers
5746 || !vi
->is_global_var
)
5749 /* Mark global restrict qualified pointers. */
5750 if ((POINTER_TYPE_P (TREE_TYPE (decl
))
5751 && TYPE_RESTRICT (TREE_TYPE (decl
)))
5752 || vi
->only_restrict_pointers
)
5754 make_constraint_from_global_restrict (vi
, "GLOBAL_RESTRICT");
5758 /* In non-IPA mode the initializer from nonlocal is all we need. */
5760 || DECL_HARD_REGISTER (decl
))
5761 make_copy_constraint (vi
, nonlocal_id
);
5763 /* In IPA mode parse the initializer and generate proper constraints
5767 varpool_node
*vnode
= varpool_node::get (decl
);
5769 /* For escaped variables initialize them from nonlocal. */
5770 if (!vnode
->all_refs_explicit_p ())
5771 make_copy_constraint (vi
, nonlocal_id
);
5773 /* If this is a global variable with an initializer and we are in
5774 IPA mode generate constraints for it. */
5775 if (vnode
->get_constructor ()
5776 && vnode
->definition
)
5778 auto_vec
<ce_s
> rhsc
;
5779 struct constraint_expr lhs
, *rhsp
;
5781 get_constraint_for_rhs (vnode
->get_constructor (), &rhsc
);
5785 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5786 process_constraint (new_constraint (lhs
, *rhsp
));
5787 /* If this is a variable that escapes from the unit
5788 the initializer escapes as well. */
5789 if (!vnode
->all_refs_explicit_p ())
5791 lhs
.var
= escaped_id
;
5794 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5795 process_constraint (new_constraint (lhs
, *rhsp
));
5804 /* Print out the points-to solution for VAR to FILE. */
5807 dump_solution_for_var (FILE *file
, unsigned int var
)
5809 varinfo_t vi
= get_varinfo (var
);
5813 /* Dump the solution for unified vars anyway, this avoids difficulties
5814 in scanning dumps in the testsuite. */
5815 fprintf (file
, "%s = { ", vi
->name
);
5816 vi
= get_varinfo (find (var
));
5817 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
5818 fprintf (file
, "%s ", get_varinfo (i
)->name
);
5819 fprintf (file
, "}");
5821 /* But note when the variable was unified. */
5823 fprintf (file
, " same as %s", vi
->name
);
5825 fprintf (file
, "\n");
5828 /* Print the points-to solution for VAR to stderr. */
5831 debug_solution_for_var (unsigned int var
)
5833 dump_solution_for_var (stderr
, var
);
5836 /* Create varinfo structures for all of the variables in the
5837 function for intraprocedural mode. */
5840 intra_create_variable_infos (struct function
*fn
)
5844 /* For each incoming pointer argument arg, create the constraint ARG
5845 = NONLOCAL or a dummy variable if it is a restrict qualified
5846 passed-by-reference argument. */
5847 for (t
= DECL_ARGUMENTS (fn
->decl
); t
; t
= DECL_CHAIN (t
))
5849 varinfo_t p
= get_vi_for_tree (t
);
5851 /* For restrict qualified pointers to objects passed by
5852 reference build a real representative for the pointed-to object.
5853 Treat restrict qualified references the same. */
5854 if (TYPE_RESTRICT (TREE_TYPE (t
))
5855 && ((DECL_BY_REFERENCE (t
) && POINTER_TYPE_P (TREE_TYPE (t
)))
5856 || TREE_CODE (TREE_TYPE (t
)) == REFERENCE_TYPE
)
5857 && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t
))))
5859 struct constraint_expr lhsc
, rhsc
;
5861 tree heapvar
= build_fake_var_decl (TREE_TYPE (TREE_TYPE (t
)));
5862 DECL_EXTERNAL (heapvar
) = 1;
5863 vi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS");
5864 insert_vi_for_tree (heapvar
, vi
);
5869 rhsc
.type
= ADDRESSOF
;
5871 process_constraint (new_constraint (lhsc
, rhsc
));
5872 for (; vi
; vi
= vi_next (vi
))
5873 if (vi
->may_have_pointers
)
5875 if (vi
->only_restrict_pointers
)
5876 make_constraint_from_global_restrict (vi
, "GLOBAL_RESTRICT");
5878 make_copy_constraint (vi
, nonlocal_id
);
5883 if (POINTER_TYPE_P (TREE_TYPE (t
))
5884 && TYPE_RESTRICT (TREE_TYPE (t
)))
5885 make_constraint_from_global_restrict (p
, "PARM_RESTRICT");
5888 for (; p
; p
= vi_next (p
))
5890 if (p
->only_restrict_pointers
)
5891 make_constraint_from_global_restrict (p
, "PARM_RESTRICT");
5892 else if (p
->may_have_pointers
)
5893 make_constraint_from (p
, nonlocal_id
);
5898 /* Add a constraint for a result decl that is passed by reference. */
5899 if (DECL_RESULT (fn
->decl
)
5900 && DECL_BY_REFERENCE (DECL_RESULT (fn
->decl
)))
5902 varinfo_t p
, result_vi
= get_vi_for_tree (DECL_RESULT (fn
->decl
));
5904 for (p
= result_vi
; p
; p
= vi_next (p
))
5905 make_constraint_from (p
, nonlocal_id
);
5908 /* Add a constraint for the incoming static chain parameter. */
5909 if (fn
->static_chain_decl
!= NULL_TREE
)
5911 varinfo_t p
, chain_vi
= get_vi_for_tree (fn
->static_chain_decl
);
5913 for (p
= chain_vi
; p
; p
= vi_next (p
))
5914 make_constraint_from (p
, nonlocal_id
);
5918 /* Structure used to put solution bitmaps in a hashtable so they can
5919 be shared among variables with the same points-to set. */
5921 typedef struct shared_bitmap_info
5925 } *shared_bitmap_info_t
;
5926 typedef const struct shared_bitmap_info
*const_shared_bitmap_info_t
;
5928 /* Shared_bitmap hashtable helpers. */
5930 struct shared_bitmap_hasher
: typed_free_remove
<shared_bitmap_info
>
5932 typedef shared_bitmap_info value_type
;
5933 typedef shared_bitmap_info compare_type
;
5934 static inline hashval_t
hash (const value_type
*);
5935 static inline bool equal (const value_type
*, const compare_type
*);
5938 /* Hash function for a shared_bitmap_info_t */
5941 shared_bitmap_hasher::hash (const value_type
*bi
)
5943 return bi
->hashcode
;
5946 /* Equality function for two shared_bitmap_info_t's. */
5949 shared_bitmap_hasher::equal (const value_type
*sbi1
, const compare_type
*sbi2
)
5951 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
5954 /* Shared_bitmap hashtable. */
5956 static hash_table
<shared_bitmap_hasher
> *shared_bitmap_table
;
5958 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
5959 existing instance if there is one, NULL otherwise. */
5962 shared_bitmap_lookup (bitmap pt_vars
)
5964 shared_bitmap_info
**slot
;
5965 struct shared_bitmap_info sbi
;
5967 sbi
.pt_vars
= pt_vars
;
5968 sbi
.hashcode
= bitmap_hash (pt_vars
);
5970 slot
= shared_bitmap_table
->find_slot (&sbi
, NO_INSERT
);
5974 return (*slot
)->pt_vars
;
5978 /* Add a bitmap to the shared bitmap hashtable. */
5981 shared_bitmap_add (bitmap pt_vars
)
5983 shared_bitmap_info
**slot
;
5984 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
5986 sbi
->pt_vars
= pt_vars
;
5987 sbi
->hashcode
= bitmap_hash (pt_vars
);
5989 slot
= shared_bitmap_table
->find_slot (sbi
, INSERT
);
5990 gcc_assert (!*slot
);
5995 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
5998 set_uids_in_ptset (bitmap into
, bitmap from
, struct pt_solution
*pt
)
6002 varinfo_t escaped_vi
= get_varinfo (find (escaped_id
));
6003 bool everything_escaped
6004 = escaped_vi
->solution
&& bitmap_bit_p (escaped_vi
->solution
, anything_id
);
6006 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
6008 varinfo_t vi
= get_varinfo (i
);
6010 /* The only artificial variables that are allowed in a may-alias
6011 set are heap variables. */
6012 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
6015 if (everything_escaped
6016 || (escaped_vi
->solution
6017 && bitmap_bit_p (escaped_vi
->solution
, i
)))
6019 pt
->vars_contains_escaped
= true;
6020 pt
->vars_contains_escaped_heap
= vi
->is_heap_var
;
6023 if (TREE_CODE (vi
->decl
) == VAR_DECL
6024 || TREE_CODE (vi
->decl
) == PARM_DECL
6025 || TREE_CODE (vi
->decl
) == RESULT_DECL
)
6027 /* If we are in IPA mode we will not recompute points-to
6028 sets after inlining so make sure they stay valid. */
6030 && !DECL_PT_UID_SET_P (vi
->decl
))
6031 SET_DECL_PT_UID (vi
->decl
, DECL_UID (vi
->decl
));
6033 /* Add the decl to the points-to set. Note that the points-to
6034 set contains global variables. */
6035 bitmap_set_bit (into
, DECL_PT_UID (vi
->decl
));
6036 if (vi
->is_global_var
)
6037 pt
->vars_contains_nonlocal
= true;
6043 /* Compute the points-to solution *PT for the variable VI. */
6045 static struct pt_solution
6046 find_what_var_points_to (varinfo_t orig_vi
)
6050 bitmap finished_solution
;
6053 struct pt_solution
*pt
;
6055 /* This variable may have been collapsed, let's get the real
6057 vi
= get_varinfo (find (orig_vi
->id
));
6059 /* See if we have already computed the solution and return it. */
6060 pt_solution
**slot
= &final_solutions
->get_or_insert (vi
);
6064 *slot
= pt
= XOBNEW (&final_solutions_obstack
, struct pt_solution
);
6065 memset (pt
, 0, sizeof (struct pt_solution
));
6067 /* Translate artificial variables into SSA_NAME_PTR_INFO
6069 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6071 varinfo_t vi
= get_varinfo (i
);
6073 if (vi
->is_artificial_var
)
6075 if (vi
->id
== nothing_id
)
6077 else if (vi
->id
== escaped_id
)
6080 pt
->ipa_escaped
= 1;
6083 /* Expand some special vars of ESCAPED in-place here. */
6084 varinfo_t evi
= get_varinfo (find (escaped_id
));
6085 if (bitmap_bit_p (evi
->solution
, nonlocal_id
))
6088 else if (vi
->id
== nonlocal_id
)
6090 else if (vi
->is_heap_var
)
6091 /* We represent heapvars in the points-to set properly. */
6093 else if (vi
->id
== string_id
)
6094 /* Nobody cares - STRING_CSTs are read-only entities. */
6096 else if (vi
->id
== anything_id
6097 || vi
->id
== integer_id
)
6102 /* Instead of doing extra work, simply do not create
6103 elaborate points-to information for pt_anything pointers. */
6107 /* Share the final set of variables when possible. */
6108 finished_solution
= BITMAP_GGC_ALLOC ();
6109 stats
.points_to_sets_created
++;
6111 set_uids_in_ptset (finished_solution
, vi
->solution
, pt
);
6112 result
= shared_bitmap_lookup (finished_solution
);
6115 shared_bitmap_add (finished_solution
);
6116 pt
->vars
= finished_solution
;
6121 bitmap_clear (finished_solution
);
6127 /* Given a pointer variable P, fill in its points-to set. */
6130 find_what_p_points_to (tree p
)
6132 struct ptr_info_def
*pi
;
6136 /* For parameters, get at the points-to set for the actual parm
6138 if (TREE_CODE (p
) == SSA_NAME
6139 && SSA_NAME_IS_DEFAULT_DEF (p
)
6140 && (TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
6141 || TREE_CODE (SSA_NAME_VAR (p
)) == RESULT_DECL
))
6142 lookup_p
= SSA_NAME_VAR (p
);
6144 vi
= lookup_vi_for_tree (lookup_p
);
6148 pi
= get_ptr_info (p
);
6149 pi
->pt
= find_what_var_points_to (vi
);
6153 /* Query statistics for points-to solutions. */
6156 unsigned HOST_WIDE_INT pt_solution_includes_may_alias
;
6157 unsigned HOST_WIDE_INT pt_solution_includes_no_alias
;
6158 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias
;
6159 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias
;
6163 dump_pta_stats (FILE *s
)
6165 fprintf (s
, "\nPTA query stats:\n");
6166 fprintf (s
, " pt_solution_includes: "
6167 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6168 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6169 pta_stats
.pt_solution_includes_no_alias
,
6170 pta_stats
.pt_solution_includes_no_alias
6171 + pta_stats
.pt_solution_includes_may_alias
);
6172 fprintf (s
, " pt_solutions_intersect: "
6173 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6174 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6175 pta_stats
.pt_solutions_intersect_no_alias
,
6176 pta_stats
.pt_solutions_intersect_no_alias
6177 + pta_stats
.pt_solutions_intersect_may_alias
);
6181 /* Reset the points-to solution *PT to a conservative default
6182 (point to anything). */
6185 pt_solution_reset (struct pt_solution
*pt
)
6187 memset (pt
, 0, sizeof (struct pt_solution
));
6188 pt
->anything
= true;
6191 /* Set the points-to solution *PT to point only to the variables
6192 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6193 global variables and VARS_CONTAINS_RESTRICT specifies whether
6194 it contains restrict tag variables. */
6197 pt_solution_set (struct pt_solution
*pt
, bitmap vars
,
6198 bool vars_contains_nonlocal
)
6200 memset (pt
, 0, sizeof (struct pt_solution
));
6202 pt
->vars_contains_nonlocal
= vars_contains_nonlocal
;
6203 pt
->vars_contains_escaped
6204 = (cfun
->gimple_df
->escaped
.anything
6205 || bitmap_intersect_p (cfun
->gimple_df
->escaped
.vars
, vars
));
6208 /* Set the points-to solution *PT to point only to the variable VAR. */
6211 pt_solution_set_var (struct pt_solution
*pt
, tree var
)
6213 memset (pt
, 0, sizeof (struct pt_solution
));
6214 pt
->vars
= BITMAP_GGC_ALLOC ();
6215 bitmap_set_bit (pt
->vars
, DECL_PT_UID (var
));
6216 pt
->vars_contains_nonlocal
= is_global_var (var
);
6217 pt
->vars_contains_escaped
6218 = (cfun
->gimple_df
->escaped
.anything
6219 || bitmap_bit_p (cfun
->gimple_df
->escaped
.vars
, DECL_PT_UID (var
)));
6222 /* Computes the union of the points-to solutions *DEST and *SRC and
6223 stores the result in *DEST. This changes the points-to bitmap
6224 of *DEST and thus may not be used if that might be shared.
6225 The points-to bitmap of *SRC and *DEST will not be shared after
6226 this function if they were not before. */
6229 pt_solution_ior_into (struct pt_solution
*dest
, struct pt_solution
*src
)
6231 dest
->anything
|= src
->anything
;
6234 pt_solution_reset (dest
);
6238 dest
->nonlocal
|= src
->nonlocal
;
6239 dest
->escaped
|= src
->escaped
;
6240 dest
->ipa_escaped
|= src
->ipa_escaped
;
6241 dest
->null
|= src
->null
;
6242 dest
->vars_contains_nonlocal
|= src
->vars_contains_nonlocal
;
6243 dest
->vars_contains_escaped
|= src
->vars_contains_escaped
;
6244 dest
->vars_contains_escaped_heap
|= src
->vars_contains_escaped_heap
;
6249 dest
->vars
= BITMAP_GGC_ALLOC ();
6250 bitmap_ior_into (dest
->vars
, src
->vars
);
6253 /* Return true if the points-to solution *PT is empty. */
6256 pt_solution_empty_p (struct pt_solution
*pt
)
6263 && !bitmap_empty_p (pt
->vars
))
6266 /* If the solution includes ESCAPED, check if that is empty. */
6268 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
6271 /* If the solution includes ESCAPED, check if that is empty. */
6273 && !pt_solution_empty_p (&ipa_escaped_pt
))
6279 /* Return true if the points-to solution *PT only point to a single var, and
6280 return the var uid in *UID. */
6283 pt_solution_singleton_p (struct pt_solution
*pt
, unsigned *uid
)
6285 if (pt
->anything
|| pt
->nonlocal
|| pt
->escaped
|| pt
->ipa_escaped
6286 || pt
->null
|| pt
->vars
== NULL
6287 || !bitmap_single_bit_set_p (pt
->vars
))
6290 *uid
= bitmap_first_set_bit (pt
->vars
);
6294 /* Return true if the points-to solution *PT includes global memory. */
6297 pt_solution_includes_global (struct pt_solution
*pt
)
6301 || pt
->vars_contains_nonlocal
6302 /* The following is a hack to make the malloc escape hack work.
6303 In reality we'd need different sets for escaped-through-return
6304 and escaped-to-callees and passes would need to be updated. */
6305 || pt
->vars_contains_escaped_heap
)
6308 /* 'escaped' is also a placeholder so we have to look into it. */
6310 return pt_solution_includes_global (&cfun
->gimple_df
->escaped
);
6312 if (pt
->ipa_escaped
)
6313 return pt_solution_includes_global (&ipa_escaped_pt
);
6315 /* ??? This predicate is not correct for the IPA-PTA solution
6316 as we do not properly distinguish between unit escape points
6317 and global variables. */
6318 if (cfun
->gimple_df
->ipa_pta
)
6324 /* Return true if the points-to solution *PT includes the variable
6325 declaration DECL. */
6328 pt_solution_includes_1 (struct pt_solution
*pt
, const_tree decl
)
6334 && is_global_var (decl
))
6338 && bitmap_bit_p (pt
->vars
, DECL_PT_UID (decl
)))
6341 /* If the solution includes ESCAPED, check it. */
6343 && pt_solution_includes_1 (&cfun
->gimple_df
->escaped
, decl
))
6346 /* If the solution includes ESCAPED, check it. */
6348 && pt_solution_includes_1 (&ipa_escaped_pt
, decl
))
6355 pt_solution_includes (struct pt_solution
*pt
, const_tree decl
)
6357 bool res
= pt_solution_includes_1 (pt
, decl
);
6359 ++pta_stats
.pt_solution_includes_may_alias
;
6361 ++pta_stats
.pt_solution_includes_no_alias
;
6365 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6369 pt_solutions_intersect_1 (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6371 if (pt1
->anything
|| pt2
->anything
)
6374 /* If either points to unknown global memory and the other points to
6375 any global memory they alias. */
6378 || pt2
->vars_contains_nonlocal
))
6380 && pt1
->vars_contains_nonlocal
))
6383 /* If either points to all escaped memory and the other points to
6384 any escaped memory they alias. */
6387 || pt2
->vars_contains_escaped
))
6389 && pt1
->vars_contains_escaped
))
6392 /* Check the escaped solution if required.
6393 ??? Do we need to check the local against the IPA escaped sets? */
6394 if ((pt1
->ipa_escaped
|| pt2
->ipa_escaped
)
6395 && !pt_solution_empty_p (&ipa_escaped_pt
))
6397 /* If both point to escaped memory and that solution
6398 is not empty they alias. */
6399 if (pt1
->ipa_escaped
&& pt2
->ipa_escaped
)
6402 /* If either points to escaped memory see if the escaped solution
6403 intersects with the other. */
6404 if ((pt1
->ipa_escaped
6405 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt2
))
6406 || (pt2
->ipa_escaped
6407 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt1
)))
6411 /* Now both pointers alias if their points-to solution intersects. */
6414 && bitmap_intersect_p (pt1
->vars
, pt2
->vars
));
6418 pt_solutions_intersect (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6420 bool res
= pt_solutions_intersect_1 (pt1
, pt2
);
6422 ++pta_stats
.pt_solutions_intersect_may_alias
;
6424 ++pta_stats
.pt_solutions_intersect_no_alias
;
6429 /* Dump points-to information to OUTFILE. */
6432 dump_sa_points_to_info (FILE *outfile
)
6436 fprintf (outfile
, "\nPoints-to sets\n\n");
6438 if (dump_flags
& TDF_STATS
)
6440 fprintf (outfile
, "Stats:\n");
6441 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
6442 fprintf (outfile
, "Non-pointer vars: %d\n",
6443 stats
.nonpointer_vars
);
6444 fprintf (outfile
, "Statically unified vars: %d\n",
6445 stats
.unified_vars_static
);
6446 fprintf (outfile
, "Dynamically unified vars: %d\n",
6447 stats
.unified_vars_dynamic
);
6448 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
6449 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
6450 fprintf (outfile
, "Number of implicit edges: %d\n",
6451 stats
.num_implicit_edges
);
6454 for (i
= 1; i
< varmap
.length (); i
++)
6456 varinfo_t vi
= get_varinfo (i
);
6457 if (!vi
->may_have_pointers
)
6459 dump_solution_for_var (outfile
, i
);
6464 /* Debug points-to information to stderr. */
6467 debug_sa_points_to_info (void)
6469 dump_sa_points_to_info (stderr
);
6473 /* Initialize the always-existing constraint variables for NULL
6474 ANYTHING, READONLY, and INTEGER */
6477 init_base_vars (void)
6479 struct constraint_expr lhs
, rhs
;
6480 varinfo_t var_anything
;
6481 varinfo_t var_nothing
;
6482 varinfo_t var_string
;
6483 varinfo_t var_escaped
;
6484 varinfo_t var_nonlocal
;
6485 varinfo_t var_storedanything
;
6486 varinfo_t var_integer
;
6488 /* Variable ID zero is reserved and should be NULL. */
6489 varmap
.safe_push (NULL
);
6491 /* Create the NULL variable, used to represent that a variable points
6493 var_nothing
= new_var_info (NULL_TREE
, "NULL");
6494 gcc_assert (var_nothing
->id
== nothing_id
);
6495 var_nothing
->is_artificial_var
= 1;
6496 var_nothing
->offset
= 0;
6497 var_nothing
->size
= ~0;
6498 var_nothing
->fullsize
= ~0;
6499 var_nothing
->is_special_var
= 1;
6500 var_nothing
->may_have_pointers
= 0;
6501 var_nothing
->is_global_var
= 0;
6503 /* Create the ANYTHING variable, used to represent that a variable
6504 points to some unknown piece of memory. */
6505 var_anything
= new_var_info (NULL_TREE
, "ANYTHING");
6506 gcc_assert (var_anything
->id
== anything_id
);
6507 var_anything
->is_artificial_var
= 1;
6508 var_anything
->size
= ~0;
6509 var_anything
->offset
= 0;
6510 var_anything
->fullsize
= ~0;
6511 var_anything
->is_special_var
= 1;
6513 /* Anything points to anything. This makes deref constraints just
6514 work in the presence of linked list and other p = *p type loops,
6515 by saying that *ANYTHING = ANYTHING. */
6517 lhs
.var
= anything_id
;
6519 rhs
.type
= ADDRESSOF
;
6520 rhs
.var
= anything_id
;
6523 /* This specifically does not use process_constraint because
6524 process_constraint ignores all anything = anything constraints, since all
6525 but this one are redundant. */
6526 constraints
.safe_push (new_constraint (lhs
, rhs
));
6528 /* Create the STRING variable, used to represent that a variable
6529 points to a string literal. String literals don't contain
6530 pointers so STRING doesn't point to anything. */
6531 var_string
= new_var_info (NULL_TREE
, "STRING");
6532 gcc_assert (var_string
->id
== string_id
);
6533 var_string
->is_artificial_var
= 1;
6534 var_string
->offset
= 0;
6535 var_string
->size
= ~0;
6536 var_string
->fullsize
= ~0;
6537 var_string
->is_special_var
= 1;
6538 var_string
->may_have_pointers
= 0;
6540 /* Create the ESCAPED variable, used to represent the set of escaped
6542 var_escaped
= new_var_info (NULL_TREE
, "ESCAPED");
6543 gcc_assert (var_escaped
->id
== escaped_id
);
6544 var_escaped
->is_artificial_var
= 1;
6545 var_escaped
->offset
= 0;
6546 var_escaped
->size
= ~0;
6547 var_escaped
->fullsize
= ~0;
6548 var_escaped
->is_special_var
= 0;
6550 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6552 var_nonlocal
= new_var_info (NULL_TREE
, "NONLOCAL");
6553 gcc_assert (var_nonlocal
->id
== nonlocal_id
);
6554 var_nonlocal
->is_artificial_var
= 1;
6555 var_nonlocal
->offset
= 0;
6556 var_nonlocal
->size
= ~0;
6557 var_nonlocal
->fullsize
= ~0;
6558 var_nonlocal
->is_special_var
= 1;
6560 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6562 lhs
.var
= escaped_id
;
6565 rhs
.var
= escaped_id
;
6567 process_constraint (new_constraint (lhs
, rhs
));
6569 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6570 whole variable escapes. */
6572 lhs
.var
= escaped_id
;
6575 rhs
.var
= escaped_id
;
6576 rhs
.offset
= UNKNOWN_OFFSET
;
6577 process_constraint (new_constraint (lhs
, rhs
));
6579 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6580 everything pointed to by escaped points to what global memory can
6583 lhs
.var
= escaped_id
;
6586 rhs
.var
= nonlocal_id
;
6588 process_constraint (new_constraint (lhs
, rhs
));
6590 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6591 global memory may point to global memory and escaped memory. */
6593 lhs
.var
= nonlocal_id
;
6595 rhs
.type
= ADDRESSOF
;
6596 rhs
.var
= nonlocal_id
;
6598 process_constraint (new_constraint (lhs
, rhs
));
6599 rhs
.type
= ADDRESSOF
;
6600 rhs
.var
= escaped_id
;
6602 process_constraint (new_constraint (lhs
, rhs
));
6604 /* Create the STOREDANYTHING variable, used to represent the set of
6605 variables stored to *ANYTHING. */
6606 var_storedanything
= new_var_info (NULL_TREE
, "STOREDANYTHING");
6607 gcc_assert (var_storedanything
->id
== storedanything_id
);
6608 var_storedanything
->is_artificial_var
= 1;
6609 var_storedanything
->offset
= 0;
6610 var_storedanything
->size
= ~0;
6611 var_storedanything
->fullsize
= ~0;
6612 var_storedanything
->is_special_var
= 0;
6614 /* Create the INTEGER variable, used to represent that a variable points
6615 to what an INTEGER "points to". */
6616 var_integer
= new_var_info (NULL_TREE
, "INTEGER");
6617 gcc_assert (var_integer
->id
== integer_id
);
6618 var_integer
->is_artificial_var
= 1;
6619 var_integer
->size
= ~0;
6620 var_integer
->fullsize
= ~0;
6621 var_integer
->offset
= 0;
6622 var_integer
->is_special_var
= 1;
6624 /* INTEGER = ANYTHING, because we don't know where a dereference of
6625 a random integer will point to. */
6627 lhs
.var
= integer_id
;
6629 rhs
.type
= ADDRESSOF
;
6630 rhs
.var
= anything_id
;
6632 process_constraint (new_constraint (lhs
, rhs
));
6635 /* Initialize things necessary to perform PTA */
6638 init_alias_vars (void)
6640 use_field_sensitive
= (MAX_FIELDS_FOR_FIELD_SENSITIVE
> 1);
6642 bitmap_obstack_initialize (&pta_obstack
);
6643 bitmap_obstack_initialize (&oldpta_obstack
);
6644 bitmap_obstack_initialize (&predbitmap_obstack
);
6646 constraint_pool
= create_alloc_pool ("Constraint pool",
6647 sizeof (struct constraint
), 30);
6648 variable_info_pool
= create_alloc_pool ("Variable info pool",
6649 sizeof (struct variable_info
), 30);
6650 constraints
.create (8);
6652 vi_for_tree
= new hash_map
<tree
, varinfo_t
>;
6653 call_stmt_vars
= new hash_map
<gimple
, varinfo_t
>;
6655 memset (&stats
, 0, sizeof (stats
));
6656 shared_bitmap_table
= new hash_table
<shared_bitmap_hasher
> (511);
6659 gcc_obstack_init (&fake_var_decl_obstack
);
6661 final_solutions
= new hash_map
<varinfo_t
, pt_solution
*>;
6662 gcc_obstack_init (&final_solutions_obstack
);
6665 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6666 predecessor edges. */
6669 remove_preds_and_fake_succs (constraint_graph_t graph
)
6673 /* Clear the implicit ref and address nodes from the successor
6675 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
6677 if (graph
->succs
[i
])
6678 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
6679 FIRST_REF_NODE
* 2);
6682 /* Free the successor list for the non-ref nodes. */
6683 for (i
= FIRST_REF_NODE
+ 1; i
< graph
->size
; i
++)
6685 if (graph
->succs
[i
])
6686 BITMAP_FREE (graph
->succs
[i
]);
6689 /* Now reallocate the size of the successor list as, and blow away
6690 the predecessor bitmaps. */
6691 graph
->size
= varmap
.length ();
6692 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
6694 free (graph
->implicit_preds
);
6695 graph
->implicit_preds
= NULL
;
6696 free (graph
->preds
);
6697 graph
->preds
= NULL
;
6698 bitmap_obstack_release (&predbitmap_obstack
);
6701 /* Solve the constraint set. */
6704 solve_constraints (void)
6706 struct scc_info
*si
;
6710 "\nCollapsing static cycles and doing variable "
6713 init_graph (varmap
.length () * 2);
6716 fprintf (dump_file
, "Building predecessor graph\n");
6717 build_pred_graph ();
6720 fprintf (dump_file
, "Detecting pointer and location "
6722 si
= perform_var_substitution (graph
);
6725 fprintf (dump_file
, "Rewriting constraints and unifying "
6727 rewrite_constraints (graph
, si
);
6729 build_succ_graph ();
6731 free_var_substitution_info (si
);
6733 /* Attach complex constraints to graph nodes. */
6734 move_complex_constraints (graph
);
6737 fprintf (dump_file
, "Uniting pointer but not location equivalent "
6739 unite_pointer_equivalences (graph
);
6742 fprintf (dump_file
, "Finding indirect cycles\n");
6743 find_indirect_cycles (graph
);
6745 /* Implicit nodes and predecessors are no longer necessary at this
6747 remove_preds_and_fake_succs (graph
);
6749 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
6751 fprintf (dump_file
, "\n\n// The constraint graph before solve-graph "
6752 "in dot format:\n");
6753 dump_constraint_graph (dump_file
);
6754 fprintf (dump_file
, "\n\n");
6758 fprintf (dump_file
, "Solving graph\n");
6760 solve_graph (graph
);
6762 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
6764 fprintf (dump_file
, "\n\n// The constraint graph after solve-graph "
6765 "in dot format:\n");
6766 dump_constraint_graph (dump_file
);
6767 fprintf (dump_file
, "\n\n");
6771 dump_sa_points_to_info (dump_file
);
6774 /* Create points-to sets for the current function. See the comments
6775 at the start of the file for an algorithmic overview. */
6778 compute_points_to_sets (void)
6784 timevar_push (TV_TREE_PTA
);
6788 intra_create_variable_infos (cfun
);
6790 /* Now walk all statements and build the constraint set. */
6791 FOR_EACH_BB_FN (bb
, cfun
)
6793 gimple_stmt_iterator gsi
;
6795 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6797 gimple phi
= gsi_stmt (gsi
);
6799 if (! virtual_operand_p (gimple_phi_result (phi
)))
6800 find_func_aliases (cfun
, phi
);
6803 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6805 gimple stmt
= gsi_stmt (gsi
);
6807 find_func_aliases (cfun
, stmt
);
6813 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
6814 dump_constraints (dump_file
, 0);
6817 /* From the constraints compute the points-to sets. */
6818 solve_constraints ();
6820 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
6821 cfun
->gimple_df
->escaped
= find_what_var_points_to (get_varinfo (escaped_id
));
6823 /* Make sure the ESCAPED solution (which is used as placeholder in
6824 other solutions) does not reference itself. This simplifies
6825 points-to solution queries. */
6826 cfun
->gimple_df
->escaped
.escaped
= 0;
6828 /* Compute the points-to sets for pointer SSA_NAMEs. */
6829 for (i
= 0; i
< num_ssa_names
; ++i
)
6831 tree ptr
= ssa_name (i
);
6833 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
6834 find_what_p_points_to (ptr
);
6837 /* Compute the call-used/clobbered sets. */
6838 FOR_EACH_BB_FN (bb
, cfun
)
6840 gimple_stmt_iterator gsi
;
6842 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6844 gimple stmt
= gsi_stmt (gsi
);
6845 struct pt_solution
*pt
;
6846 if (!is_gimple_call (stmt
))
6849 pt
= gimple_call_use_set (stmt
);
6850 if (gimple_call_flags (stmt
) & ECF_CONST
)
6851 memset (pt
, 0, sizeof (struct pt_solution
));
6852 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
6854 *pt
= find_what_var_points_to (vi
);
6855 /* Escaped (and thus nonlocal) variables are always
6856 implicitly used by calls. */
6857 /* ??? ESCAPED can be empty even though NONLOCAL
6864 /* If there is nothing special about this call then
6865 we have made everything that is used also escape. */
6866 *pt
= cfun
->gimple_df
->escaped
;
6870 pt
= gimple_call_clobber_set (stmt
);
6871 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
6872 memset (pt
, 0, sizeof (struct pt_solution
));
6873 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
6875 *pt
= find_what_var_points_to (vi
);
6876 /* Escaped (and thus nonlocal) variables are always
6877 implicitly clobbered by calls. */
6878 /* ??? ESCAPED can be empty even though NONLOCAL
6885 /* If there is nothing special about this call then
6886 we have made everything that is used also escape. */
6887 *pt
= cfun
->gimple_df
->escaped
;
6893 timevar_pop (TV_TREE_PTA
);
6897 /* Delete created points-to sets. */
6900 delete_points_to_sets (void)
6904 delete shared_bitmap_table
;
6905 shared_bitmap_table
= NULL
;
6906 if (dump_file
&& (dump_flags
& TDF_STATS
))
6907 fprintf (dump_file
, "Points to sets created:%d\n",
6908 stats
.points_to_sets_created
);
6911 delete call_stmt_vars
;
6912 bitmap_obstack_release (&pta_obstack
);
6913 constraints
.release ();
6915 for (i
= 0; i
< graph
->size
; i
++)
6916 graph
->complex[i
].release ();
6917 free (graph
->complex);
6920 free (graph
->succs
);
6922 free (graph
->pe_rep
);
6923 free (graph
->indirect_cycles
);
6927 free_alloc_pool (variable_info_pool
);
6928 free_alloc_pool (constraint_pool
);
6930 obstack_free (&fake_var_decl_obstack
, NULL
);
6932 delete final_solutions
;
6933 obstack_free (&final_solutions_obstack
, NULL
);
6937 /* Compute points-to information for every SSA_NAME pointer in the
6938 current function and compute the transitive closure of escaped
6939 variables to re-initialize the call-clobber states of local variables. */
6942 compute_may_aliases (void)
6944 if (cfun
->gimple_df
->ipa_pta
)
6948 fprintf (dump_file
, "\nNot re-computing points-to information "
6949 "because IPA points-to information is available.\n\n");
6951 /* But still dump what we have remaining it. */
6952 dump_alias_info (dump_file
);
6958 /* For each pointer P_i, determine the sets of variables that P_i may
6959 point-to. Compute the reachability set of escaped and call-used
6961 compute_points_to_sets ();
6963 /* Debugging dumps. */
6965 dump_alias_info (dump_file
);
6967 /* Deallocate memory used by aliasing data structures and the internal
6968 points-to solution. */
6969 delete_points_to_sets ();
6971 gcc_assert (!need_ssa_update_p (cfun
));
6976 /* A dummy pass to cause points-to information to be computed via
6977 TODO_rebuild_alias. */
6981 const pass_data pass_data_build_alias
=
6983 GIMPLE_PASS
, /* type */
6985 OPTGROUP_NONE
, /* optinfo_flags */
6986 TV_NONE
, /* tv_id */
6987 ( PROP_cfg
| PROP_ssa
), /* properties_required */
6988 0, /* properties_provided */
6989 0, /* properties_destroyed */
6990 0, /* todo_flags_start */
6991 TODO_rebuild_alias
, /* todo_flags_finish */
6994 class pass_build_alias
: public gimple_opt_pass
6997 pass_build_alias (gcc::context
*ctxt
)
6998 : gimple_opt_pass (pass_data_build_alias
, ctxt
)
7001 /* opt_pass methods: */
7002 virtual bool gate (function
*) { return flag_tree_pta
; }
7004 }; // class pass_build_alias
7009 make_pass_build_alias (gcc::context
*ctxt
)
7011 return new pass_build_alias (ctxt
);
7014 /* A dummy pass to cause points-to information to be computed via
7015 TODO_rebuild_alias. */
7019 const pass_data pass_data_build_ealias
=
7021 GIMPLE_PASS
, /* type */
7022 "ealias", /* name */
7023 OPTGROUP_NONE
, /* optinfo_flags */
7024 TV_NONE
, /* tv_id */
7025 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7026 0, /* properties_provided */
7027 0, /* properties_destroyed */
7028 0, /* todo_flags_start */
7029 TODO_rebuild_alias
, /* todo_flags_finish */
7032 class pass_build_ealias
: public gimple_opt_pass
7035 pass_build_ealias (gcc::context
*ctxt
)
7036 : gimple_opt_pass (pass_data_build_ealias
, ctxt
)
7039 /* opt_pass methods: */
7040 virtual bool gate (function
*) { return flag_tree_pta
; }
7042 }; // class pass_build_ealias
7047 make_pass_build_ealias (gcc::context
*ctxt
)
7049 return new pass_build_ealias (ctxt
);
7053 /* IPA PTA solutions for ESCAPED. */
7054 struct pt_solution ipa_escaped_pt
7055 = { true, false, false, false, false, false, false, false, NULL
};
7057 /* Associate node with varinfo DATA. Worker for
7058 cgraph_for_node_and_aliases. */
7060 associate_varinfo_to_alias (struct cgraph_node
*node
, void *data
)
7062 if ((node
->alias
|| node
->thunk
.thunk_p
)
7064 insert_vi_for_tree (node
->decl
, (varinfo_t
)data
);
7068 /* Execute the driver for IPA PTA. */
7070 ipa_pta_execute (void)
7072 struct cgraph_node
*node
;
7080 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7082 symtab_node::dump_table (dump_file
);
7083 fprintf (dump_file
, "\n");
7086 /* Build the constraints. */
7087 FOR_EACH_DEFINED_FUNCTION (node
)
7090 /* Nodes without a body are not interesting. Especially do not
7091 visit clones at this point for now - we get duplicate decls
7092 there for inline clones at least. */
7093 if (!node
->has_gimple_body_p () || node
->clone_of
)
7097 gcc_assert (!node
->clone_of
);
7099 vi
= create_function_info_for (node
->decl
,
7100 alias_get_name (node
->decl
));
7101 node
->call_for_symbol_thunks_and_aliases
7102 (associate_varinfo_to_alias
, vi
, true);
7105 /* Create constraints for global variables and their initializers. */
7106 FOR_EACH_VARIABLE (var
)
7108 if (var
->alias
&& var
->analyzed
)
7111 get_vi_for_tree (var
->decl
);
7117 "Generating constraints for global initializers\n\n");
7118 dump_constraints (dump_file
, 0);
7119 fprintf (dump_file
, "\n");
7121 from
= constraints
.length ();
7123 FOR_EACH_DEFINED_FUNCTION (node
)
7125 struct function
*func
;
7128 /* Nodes without a body are not interesting. */
7129 if (!node
->has_gimple_body_p () || node
->clone_of
)
7135 "Generating constraints for %s", node
->name ());
7136 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
7137 fprintf (dump_file
, " (%s)",
7139 (DECL_ASSEMBLER_NAME (node
->decl
)));
7140 fprintf (dump_file
, "\n");
7143 func
= DECL_STRUCT_FUNCTION (node
->decl
);
7144 gcc_assert (cfun
== NULL
);
7146 /* For externally visible or attribute used annotated functions use
7147 local constraints for their arguments.
7148 For local functions we see all callers and thus do not need initial
7149 constraints for parameters. */
7150 if (node
->used_from_other_partition
7151 || node
->externally_visible
7152 || node
->force_output
)
7154 intra_create_variable_infos (func
);
7156 /* We also need to make function return values escape. Nothing
7157 escapes by returning from main though. */
7158 if (!MAIN_NAME_P (DECL_NAME (node
->decl
)))
7161 fi
= lookup_vi_for_tree (node
->decl
);
7162 rvi
= first_vi_for_offset (fi
, fi_result
);
7163 if (rvi
&& rvi
->offset
== fi_result
)
7165 struct constraint_expr includes
;
7166 struct constraint_expr var
;
7167 includes
.var
= escaped_id
;
7168 includes
.offset
= 0;
7169 includes
.type
= SCALAR
;
7173 process_constraint (new_constraint (includes
, var
));
7178 /* Build constriants for the function body. */
7179 FOR_EACH_BB_FN (bb
, func
)
7181 gimple_stmt_iterator gsi
;
7183 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7186 gimple phi
= gsi_stmt (gsi
);
7188 if (! virtual_operand_p (gimple_phi_result (phi
)))
7189 find_func_aliases (func
, phi
);
7192 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7194 gimple stmt
= gsi_stmt (gsi
);
7196 find_func_aliases (func
, stmt
);
7197 find_func_clobbers (func
, stmt
);
7203 fprintf (dump_file
, "\n");
7204 dump_constraints (dump_file
, from
);
7205 fprintf (dump_file
, "\n");
7207 from
= constraints
.length ();
7210 /* From the constraints compute the points-to sets. */
7211 solve_constraints ();
7213 /* Compute the global points-to sets for ESCAPED.
7214 ??? Note that the computed escape set is not correct
7215 for the whole unit as we fail to consider graph edges to
7216 externally visible functions. */
7217 ipa_escaped_pt
= find_what_var_points_to (get_varinfo (escaped_id
));
7219 /* Make sure the ESCAPED solution (which is used as placeholder in
7220 other solutions) does not reference itself. This simplifies
7221 points-to solution queries. */
7222 ipa_escaped_pt
.ipa_escaped
= 0;
7224 /* Assign the points-to sets to the SSA names in the unit. */
7225 FOR_EACH_DEFINED_FUNCTION (node
)
7228 struct function
*fn
;
7232 /* Nodes without a body are not interesting. */
7233 if (!node
->has_gimple_body_p () || node
->clone_of
)
7236 fn
= DECL_STRUCT_FUNCTION (node
->decl
);
7238 /* Compute the points-to sets for pointer SSA_NAMEs. */
7239 FOR_EACH_VEC_ELT (*fn
->gimple_df
->ssa_names
, i
, ptr
)
7242 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
7243 find_what_p_points_to (ptr
);
7246 /* Compute the call-use and call-clobber sets for indirect calls
7247 and calls to external functions. */
7248 FOR_EACH_BB_FN (bb
, fn
)
7250 gimple_stmt_iterator gsi
;
7252 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7254 gimple stmt
= gsi_stmt (gsi
);
7255 struct pt_solution
*pt
;
7259 if (!is_gimple_call (stmt
))
7262 /* Handle direct calls to functions with body. */
7263 decl
= gimple_call_fndecl (stmt
);
7265 && (fi
= lookup_vi_for_tree (decl
))
7268 *gimple_call_clobber_set (stmt
)
7269 = find_what_var_points_to
7270 (first_vi_for_offset (fi
, fi_clobbers
));
7271 *gimple_call_use_set (stmt
)
7272 = find_what_var_points_to
7273 (first_vi_for_offset (fi
, fi_uses
));
7275 /* Handle direct calls to external functions. */
7278 pt
= gimple_call_use_set (stmt
);
7279 if (gimple_call_flags (stmt
) & ECF_CONST
)
7280 memset (pt
, 0, sizeof (struct pt_solution
));
7281 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
7283 *pt
= find_what_var_points_to (vi
);
7284 /* Escaped (and thus nonlocal) variables are always
7285 implicitly used by calls. */
7286 /* ??? ESCAPED can be empty even though NONLOCAL
7289 pt
->ipa_escaped
= 1;
7293 /* If there is nothing special about this call then
7294 we have made everything that is used also escape. */
7295 *pt
= ipa_escaped_pt
;
7299 pt
= gimple_call_clobber_set (stmt
);
7300 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
7301 memset (pt
, 0, sizeof (struct pt_solution
));
7302 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
7304 *pt
= find_what_var_points_to (vi
);
7305 /* Escaped (and thus nonlocal) variables are always
7306 implicitly clobbered by calls. */
7307 /* ??? ESCAPED can be empty even though NONLOCAL
7310 pt
->ipa_escaped
= 1;
7314 /* If there is nothing special about this call then
7315 we have made everything that is used also escape. */
7316 *pt
= ipa_escaped_pt
;
7320 /* Handle indirect calls. */
7322 && (fi
= get_fi_for_callee (stmt
)))
7324 /* We need to accumulate all clobbers/uses of all possible
7326 fi
= get_varinfo (find (fi
->id
));
7327 /* If we cannot constrain the set of functions we'll end up
7328 calling we end up using/clobbering everything. */
7329 if (bitmap_bit_p (fi
->solution
, anything_id
)
7330 || bitmap_bit_p (fi
->solution
, nonlocal_id
)
7331 || bitmap_bit_p (fi
->solution
, escaped_id
))
7333 pt_solution_reset (gimple_call_clobber_set (stmt
));
7334 pt_solution_reset (gimple_call_use_set (stmt
));
7340 struct pt_solution
*uses
, *clobbers
;
7342 uses
= gimple_call_use_set (stmt
);
7343 clobbers
= gimple_call_clobber_set (stmt
);
7344 memset (uses
, 0, sizeof (struct pt_solution
));
7345 memset (clobbers
, 0, sizeof (struct pt_solution
));
7346 EXECUTE_IF_SET_IN_BITMAP (fi
->solution
, 0, i
, bi
)
7348 struct pt_solution sol
;
7350 vi
= get_varinfo (i
);
7351 if (!vi
->is_fn_info
)
7353 /* ??? We could be more precise here? */
7355 uses
->ipa_escaped
= 1;
7356 clobbers
->nonlocal
= 1;
7357 clobbers
->ipa_escaped
= 1;
7361 if (!uses
->anything
)
7363 sol
= find_what_var_points_to
7364 (first_vi_for_offset (vi
, fi_uses
));
7365 pt_solution_ior_into (uses
, &sol
);
7367 if (!clobbers
->anything
)
7369 sol
= find_what_var_points_to
7370 (first_vi_for_offset (vi
, fi_clobbers
));
7371 pt_solution_ior_into (clobbers
, &sol
);
7379 fn
->gimple_df
->ipa_pta
= true;
7382 delete_points_to_sets ();
7391 const pass_data pass_data_ipa_pta
=
7393 SIMPLE_IPA_PASS
, /* type */
7395 OPTGROUP_NONE
, /* optinfo_flags */
7396 TV_IPA_PTA
, /* tv_id */
7397 0, /* properties_required */
7398 0, /* properties_provided */
7399 0, /* properties_destroyed */
7400 0, /* todo_flags_start */
7401 0, /* todo_flags_finish */
7404 class pass_ipa_pta
: public simple_ipa_opt_pass
7407 pass_ipa_pta (gcc::context
*ctxt
)
7408 : simple_ipa_opt_pass (pass_data_ipa_pta
, ctxt
)
7411 /* opt_pass methods: */
7412 virtual bool gate (function
*)
7416 /* Don't bother doing anything if the program has errors. */
7420 virtual unsigned int execute (function
*) { return ipa_pta_execute (); }
7422 }; // class pass_ipa_pta
7426 simple_ipa_opt_pass
*
7427 make_pass_ipa_pta (gcc::context
*ctxt
)
7429 return new pass_ipa_pta (ctxt
);