1 /* Tree based points-to analysis
2 Copyright (C) 2005-2023 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"
28 #include "alloc-pool.h"
29 #include "tree-pass.h"
32 #include "tree-pretty-print.h"
33 #include "diagnostic-core.h"
34 #include "fold-const.h"
35 #include "stor-layout.h"
37 #include "gimple-iterator.h"
38 #include "tree-into-ssa.h"
40 #include "gimple-walk.h"
42 #include "stringpool.h"
46 #include "gimple-range.h"
47 #include "ipa-modref-tree.h"
48 #include "ipa-modref.h"
49 #include "attr-fnspec.h"
51 /* The idea behind this analyzer is to generate set constraints from the
52 program, then solve the resulting constraints in order to generate the
55 Set constraints are a way of modeling program analysis problems that
56 involve sets. They consist of an inclusion constraint language,
57 describing the variables (each variable is a set) and operations that
58 are involved on the variables, and a set of rules that derive facts
59 from these operations. To solve a system of set constraints, you derive
60 all possible facts under the rules, which gives you the correct sets
63 See "Efficient Field-sensitive pointer analysis for C" by "David
64 J. Pearce and Paul H. J. Kelly and Chris Hankin", at
65 http://citeseer.ist.psu.edu/pearce04efficient.html
67 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
68 of C Code in a Second" by "Nevin Heintze and Olivier Tardieu" at
69 http://citeseer.ist.psu.edu/heintze01ultrafast.html
71 There are three types of real constraint expressions, DEREF,
72 ADDRESSOF, and SCALAR. Each constraint expression consists
73 of a constraint type, a variable, and an offset.
75 SCALAR is a constraint expression type used to represent x, whether
76 it appears on the LHS or the RHS of a statement.
77 DEREF is a constraint expression type used to represent *x, whether
78 it appears on the LHS or the RHS of a statement.
79 ADDRESSOF is a constraint expression used to represent &x, whether
80 it appears on the LHS or the RHS of a statement.
82 Each pointer variable in the program is assigned an integer id, and
83 each field of a structure variable is assigned an integer id as well.
85 Structure variables are linked to their list of fields through a "next
86 field" in each variable that points to the next field in offset
88 Each variable for a structure field has
90 1. "size", that tells the size in bits of that field.
91 2. "fullsize", that tells the size in bits of the entire structure.
92 3. "offset", that tells the offset in bits from the beginning of the
93 structure to this field.
105 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
106 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
107 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
110 In order to solve the system of set constraints, the following is
113 1. Each constraint variable x has a solution set associated with it,
116 2. Constraints are separated into direct, copy, and complex.
117 Direct constraints are ADDRESSOF constraints that require no extra
118 processing, such as P = &Q
119 Copy constraints are those of the form P = Q.
120 Complex constraints are all the constraints involving dereferences
121 and offsets (including offsetted copies).
123 3. All direct constraints of the form P = &Q are processed, such
124 that Q is added to Sol(P)
126 4. All complex constraints for a given constraint variable are stored in a
127 linked list attached to that variable's node.
129 5. A directed graph is built out of the copy constraints. Each
130 constraint variable is a node in the graph, and an edge from
131 Q to P is added for each copy constraint of the form P = Q
133 6. The graph is then walked, and solution sets are
134 propagated along the copy edges, such that an edge from Q to P
135 causes Sol(P) <- Sol(P) union Sol(Q).
137 7. As we visit each node, all complex constraints associated with
138 that node are processed by adding appropriate copy edges to the graph, or the
139 appropriate variables to the solution set.
141 8. The process of walking the graph is iterated until no solution
144 Prior to walking the graph in steps 6 and 7, We perform static
145 cycle elimination on the constraint graph, as well
146 as off-line variable substitution.
148 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
149 on and turned into anything), but isn't. You can just see what offset
150 inside the pointed-to struct it's going to access.
152 TODO: Constant bounded arrays can be handled as if they were structs of the
153 same number of elements.
155 TODO: Modeling heap and incoming pointers becomes much better if we
156 add fields to them as we discover them, which we could do.
158 TODO: We could handle unions, but to be honest, it's probably not
159 worth the pain or slowdown. */
161 /* IPA-PTA optimizations possible.
163 When the indirect function called is ANYTHING we can add disambiguation
164 based on the function signatures (or simply the parameter count which
165 is the varinfo size). We also do not need to consider functions that
166 do not have their address taken.
168 The is_global_var bit which marks escape points is overly conservative
169 in IPA mode. Split it to is_escape_point and is_global_var - only
170 externally visible globals are escape points in IPA mode.
171 There is now is_ipa_escape_point but this is only used in a few
174 The way we introduce DECL_PT_UID to avoid fixing up all points-to
175 sets in the translation unit when we copy a DECL during inlining
176 pessimizes precision. The advantage is that the DECL_PT_UID keeps
177 compile-time and memory usage overhead low - the points-to sets
178 do not grow or get unshared as they would during a fixup phase.
179 An alternative solution is to delay IPA PTA until after all
180 inlining transformations have been applied.
182 The way we propagate clobber/use information isn't optimized.
183 It should use a new complex constraint that properly filters
184 out local variables of the callee (though that would make
185 the sets invalid after inlining). OTOH we might as well
186 admit defeat to WHOPR and simply do all the clobber/use analysis
187 and propagation after PTA finished but before we threw away
188 points-to information for memory variables. WHOPR and PTA
189 do not play along well anyway - the whole constraint solving
190 would need to be done in WPA phase and it will be very interesting
191 to apply the results to local SSA names during LTRANS phase.
193 We probably should compute a per-function unit-ESCAPE solution
194 propagating it simply like the clobber / uses solutions. The
195 solution can go alongside the non-IPA escaped solution and be
196 used to query which vars escape the unit through a function.
197 This is also required to make the escaped-HEAP trick work in IPA mode.
199 We never put function decls in points-to sets so we do not
200 keep the set of called functions for indirect calls.
202 And probably more. */
204 static bool use_field_sensitive
= true;
205 static int in_ipa_mode
= 0;
207 /* Used for predecessor bitmaps. */
208 static bitmap_obstack predbitmap_obstack
;
210 /* Used for points-to sets. */
211 static bitmap_obstack pta_obstack
;
213 /* Used for oldsolution members of variables. */
214 static bitmap_obstack oldpta_obstack
;
216 /* Used for per-solver-iteration bitmaps. */
217 static bitmap_obstack iteration_obstack
;
219 static unsigned int create_variable_info_for (tree
, const char *, bool);
220 typedef struct constraint_graph
*constraint_graph_t
;
221 static void unify_nodes (constraint_graph_t
, unsigned int, unsigned int, bool);
224 typedef struct constraint
*constraint_t
;
227 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
229 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
231 static struct constraint_stats
233 unsigned int total_vars
;
234 unsigned int nonpointer_vars
;
235 unsigned int unified_vars_static
;
236 unsigned int unified_vars_dynamic
;
237 unsigned int iterations
;
238 unsigned int num_edges
;
239 unsigned int num_implicit_edges
;
240 unsigned int num_avoided_edges
;
241 unsigned int points_to_sets_created
;
246 /* ID of this variable */
249 /* True if this is a variable created by the constraint analysis, such as
250 heap variables and constraints we had to break up. */
251 unsigned int is_artificial_var
: 1;
253 /* True if this is a special variable whose solution set should not be
255 unsigned int is_special_var
: 1;
257 /* True for variables whose size is not known or variable. */
258 unsigned int is_unknown_size_var
: 1;
260 /* True for (sub-)fields that represent a whole variable. */
261 unsigned int is_full_var
: 1;
263 /* True if this is a heap variable. */
264 unsigned int is_heap_var
: 1;
266 /* True if this is a register variable. */
267 unsigned int is_reg_var
: 1;
269 /* True if this field may contain pointers. */
270 unsigned int may_have_pointers
: 1;
272 /* True if this field has only restrict qualified pointers. */
273 unsigned int only_restrict_pointers
: 1;
275 /* True if this represents a heap var created for a restrict qualified
277 unsigned int is_restrict_var
: 1;
279 /* True if this represents a global variable. */
280 unsigned int is_global_var
: 1;
282 /* True if this represents a module escape point for IPA analysis. */
283 unsigned int is_ipa_escape_point
: 1;
285 /* True if this represents a IPA function info. */
286 unsigned int is_fn_info
: 1;
288 /* True if this appears as RHS in a ADDRESSOF constraint. */
289 unsigned int address_taken
: 1;
291 /* ??? Store somewhere better. */
294 /* The ID of the variable for the next field in this structure
295 or zero for the last field in this structure. */
298 /* The ID of the variable for the first field in this structure. */
301 /* Offset of this variable, in bits, from the base variable */
302 unsigned HOST_WIDE_INT offset
;
304 /* Size of the variable, in bits. */
305 unsigned HOST_WIDE_INT size
;
307 /* Full size of the base variable, in bits. */
308 unsigned HOST_WIDE_INT fullsize
;
310 /* In IPA mode the shadow UID in case the variable needs to be duplicated in
311 the final points-to solution because it reaches its containing
312 function recursively. Zero if none is needed. */
313 unsigned int shadow_var_uid
;
315 /* Name of this variable */
318 /* Tree that this variable is associated with. */
321 /* Points-to set for this variable. */
324 /* Old points-to set for this variable. */
327 typedef struct variable_info
*varinfo_t
;
329 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
330 static varinfo_t
first_or_preceding_vi_for_offset (varinfo_t
,
331 unsigned HOST_WIDE_INT
);
332 static varinfo_t
lookup_vi_for_tree (tree
);
333 static inline bool type_can_have_subvars (const_tree
);
334 static void make_param_constraints (varinfo_t
);
336 /* Pool of variable info structures. */
337 static object_allocator
<variable_info
> variable_info_pool
338 ("Variable info pool");
340 /* Map varinfo to final pt_solution. */
341 static hash_map
<varinfo_t
, pt_solution
*> *final_solutions
;
342 struct obstack final_solutions_obstack
;
344 /* Table of variable info structures for constraint variables.
345 Indexed directly by variable info id. */
346 static vec
<varinfo_t
> varmap
;
348 /* Return the varmap element N */
350 static inline varinfo_t
351 get_varinfo (unsigned int n
)
356 /* Return the next variable in the list of sub-variables of VI
357 or NULL if VI is the last sub-variable. */
359 static inline varinfo_t
360 vi_next (varinfo_t vi
)
362 return get_varinfo (vi
->next
);
365 /* Static IDs for the special variables. Variable ID zero is unused
366 and used as terminator for the sub-variable chain. */
367 enum { nothing_id
= 1, anything_id
= 2, string_id
= 3,
368 escaped_id
= 4, nonlocal_id
= 5,
369 storedanything_id
= 6, integer_id
= 7 };
371 /* Return a new variable info structure consisting for a variable
372 named NAME, and using constraint graph node NODE. Append it
373 to the vector of variable info structures. */
376 new_var_info (tree t
, const char *name
, bool add_id
)
378 unsigned index
= varmap
.length ();
379 varinfo_t ret
= variable_info_pool
.allocate ();
381 if (dump_file
&& add_id
)
383 char *tempname
= xasprintf ("%s(%d)", name
, index
);
384 name
= ggc_strdup (tempname
);
391 /* Vars without decl are artificial and do not have sub-variables. */
392 ret
->is_artificial_var
= (t
== NULL_TREE
);
393 ret
->is_special_var
= false;
394 ret
->is_unknown_size_var
= false;
395 ret
->is_full_var
= (t
== NULL_TREE
);
396 ret
->is_heap_var
= false;
397 ret
->may_have_pointers
= true;
398 ret
->only_restrict_pointers
= false;
399 ret
->is_restrict_var
= false;
401 ret
->is_global_var
= (t
== NULL_TREE
);
402 ret
->is_ipa_escape_point
= false;
403 ret
->is_fn_info
= false;
404 ret
->address_taken
= false;
406 ret
->is_global_var
= (is_global_var (t
)
407 /* We have to treat even local register variables
409 || (VAR_P (t
) && DECL_HARD_REGISTER (t
)));
410 ret
->is_reg_var
= (t
&& TREE_CODE (t
) == SSA_NAME
);
411 ret
->solution
= BITMAP_ALLOC (&pta_obstack
);
412 ret
->oldsolution
= NULL
;
414 ret
->shadow_var_uid
= 0;
419 varmap
.safe_push (ret
);
424 /* A map mapping call statements to per-stmt variables for uses
425 and clobbers specific to the call. */
426 static hash_map
<gimple
*, varinfo_t
> *call_stmt_vars
;
428 /* Lookup or create the variable for the call statement CALL. */
431 get_call_vi (gcall
*call
)
436 varinfo_t
*slot_p
= &call_stmt_vars
->get_or_insert (call
, &existed
);
440 vi
= new_var_info (NULL_TREE
, "CALLUSED", true);
444 vi
->is_full_var
= true;
445 vi
->is_reg_var
= true;
447 vi2
= new_var_info (NULL_TREE
, "CALLCLOBBERED", true);
451 vi2
->is_full_var
= true;
452 vi2
->is_reg_var
= true;
460 /* Lookup the variable for the call statement CALL representing
461 the uses. Returns NULL if there is nothing special about this call. */
464 lookup_call_use_vi (gcall
*call
)
466 varinfo_t
*slot_p
= call_stmt_vars
->get (call
);
473 /* Lookup the variable for the call statement CALL representing
474 the clobbers. Returns NULL if there is nothing special about this call. */
477 lookup_call_clobber_vi (gcall
*call
)
479 varinfo_t uses
= lookup_call_use_vi (call
);
483 return vi_next (uses
);
486 /* Lookup or create the variable for the call statement CALL representing
490 get_call_use_vi (gcall
*call
)
492 return get_call_vi (call
);
495 /* Lookup or create the variable for the call statement CALL representing
498 static varinfo_t ATTRIBUTE_UNUSED
499 get_call_clobber_vi (gcall
*call
)
501 return vi_next (get_call_vi (call
));
505 enum constraint_expr_type
{SCALAR
, DEREF
, ADDRESSOF
};
507 /* An expression that appears in a constraint. */
509 struct constraint_expr
511 /* Constraint type. */
512 constraint_expr_type type
;
514 /* Variable we are referring to in the constraint. */
517 /* Offset, in bits, of this constraint from the beginning of
518 variables it ends up referring to.
520 IOW, in a deref constraint, we would deref, get the result set,
521 then add OFFSET to each member. */
522 HOST_WIDE_INT offset
;
525 /* Use 0x8000... as special unknown offset. */
526 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
528 typedef struct constraint_expr ce_s
;
529 static void get_constraint_for_1 (tree
, vec
<ce_s
> *, bool, bool);
530 static void get_constraint_for (tree
, vec
<ce_s
> *);
531 static void get_constraint_for_rhs (tree
, vec
<ce_s
> *);
532 static void do_deref (vec
<ce_s
> *);
534 /* Our set constraints are made up of two constraint expressions, one
537 As described in the introduction, our set constraints each represent an
538 operation between set valued variables.
542 struct constraint_expr lhs
;
543 struct constraint_expr rhs
;
546 /* List of constraints that we use to build the constraint graph from. */
548 static vec
<constraint_t
> constraints
;
549 static object_allocator
<constraint
> constraint_pool ("Constraint pool");
551 /* The constraint graph is represented as an array of bitmaps
552 containing successor nodes. */
554 struct constraint_graph
556 /* Size of this graph, which may be different than the number of
557 nodes in the variable map. */
560 /* Explicit successors of each node. */
563 /* Implicit predecessors of each node (Used for variable
565 bitmap
*implicit_preds
;
567 /* Explicit predecessors of each node (Used for variable substitution). */
570 /* Indirect cycle representatives, or -1 if the node has no indirect
572 int *indirect_cycles
;
574 /* Representative node for a node. rep[a] == a unless the node has
578 /* Equivalence class representative for a label. This is used for
579 variable substitution. */
582 /* Pointer equivalence label for a node. All nodes with the same
583 pointer equivalence label can be unified together at some point
584 (either during constraint optimization or after the constraint
588 /* Pointer equivalence representative for a label. This is used to
589 handle nodes that are pointer equivalent but not location
590 equivalent. We can unite these once the addressof constraints
591 are transformed into initial points-to sets. */
594 /* Pointer equivalence label for each node, used during variable
596 unsigned int *pointer_label
;
598 /* Location equivalence label for each node, used during location
599 equivalence finding. */
600 unsigned int *loc_label
;
602 /* Pointed-by set for each node, used during location equivalence
603 finding. This is pointed-by rather than pointed-to, because it
604 is constructed using the predecessor graph. */
607 /* Points to sets for pointer equivalence. This is *not* the actual
608 points-to sets for nodes. */
611 /* Bitmap of nodes where the bit is set if the node is a direct
612 node. Used for variable substitution. */
613 sbitmap direct_nodes
;
615 /* Bitmap of nodes where the bit is set if the node is address
616 taken. Used for variable substitution. */
617 bitmap address_taken
;
619 /* Vector of complex constraints for each graph node. Complex
620 constraints are those involving dereferences or offsets that are
622 vec
<constraint_t
> *complex;
625 static constraint_graph_t graph
;
627 /* During variable substitution and the offline version of indirect
628 cycle finding, we create nodes to represent dereferences and
629 address taken constraints. These represent where these start and
631 #define FIRST_REF_NODE (varmap).length ()
632 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
634 /* Return the representative node for NODE, if NODE has been unioned
636 This function performs path compression along the way to finding
637 the representative. */
640 find (unsigned int node
)
642 gcc_checking_assert (node
< graph
->size
);
643 if (graph
->rep
[node
] != node
)
644 return graph
->rep
[node
] = find (graph
->rep
[node
]);
648 /* Union the TO and FROM nodes to the TO nodes.
649 Note that at some point in the future, we may want to do
650 union-by-rank, in which case we are going to have to return the
651 node we unified to. */
654 unite (unsigned int to
, unsigned int from
)
656 gcc_checking_assert (to
< graph
->size
&& from
< graph
->size
);
657 if (to
!= from
&& graph
->rep
[from
] != to
)
659 graph
->rep
[from
] = to
;
665 /* Create a new constraint consisting of LHS and RHS expressions. */
668 new_constraint (const struct constraint_expr lhs
,
669 const struct constraint_expr rhs
)
671 constraint_t ret
= constraint_pool
.allocate ();
677 /* Print out constraint C to FILE. */
680 dump_constraint (FILE *file
, constraint_t c
)
682 if (c
->lhs
.type
== ADDRESSOF
)
684 else if (c
->lhs
.type
== DEREF
)
687 fprintf (file
, "%s", get_varinfo (c
->lhs
.var
)->name
);
689 fprintf (file
, "V%d", c
->lhs
.var
);
690 if (c
->lhs
.offset
== UNKNOWN_OFFSET
)
691 fprintf (file
, " + UNKNOWN");
692 else if (c
->lhs
.offset
!= 0)
693 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
694 fprintf (file
, " = ");
695 if (c
->rhs
.type
== ADDRESSOF
)
697 else if (c
->rhs
.type
== DEREF
)
700 fprintf (file
, "%s", get_varinfo (c
->rhs
.var
)->name
);
702 fprintf (file
, "V%d", c
->rhs
.var
);
703 if (c
->rhs
.offset
== UNKNOWN_OFFSET
)
704 fprintf (file
, " + UNKNOWN");
705 else if (c
->rhs
.offset
!= 0)
706 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
710 void debug_constraint (constraint_t
);
711 void debug_constraints (void);
712 void debug_constraint_graph (void);
713 void debug_solution_for_var (unsigned int);
714 void debug_sa_points_to_info (void);
715 void debug_varinfo (varinfo_t
);
716 void debug_varmap (void);
718 /* Print out constraint C to stderr. */
721 debug_constraint (constraint_t c
)
723 dump_constraint (stderr
, c
);
724 fprintf (stderr
, "\n");
727 /* Print out all constraints to FILE */
730 dump_constraints (FILE *file
, int from
)
734 for (i
= from
; constraints
.iterate (i
, &c
); i
++)
737 dump_constraint (file
, c
);
738 fprintf (file
, "\n");
742 /* Print out all constraints to stderr. */
745 debug_constraints (void)
747 dump_constraints (stderr
, 0);
750 /* Print the constraint graph in dot format. */
753 dump_constraint_graph (FILE *file
)
757 /* Only print the graph if it has already been initialized: */
761 /* Prints the header of the dot file: */
762 fprintf (file
, "strict digraph {\n");
763 fprintf (file
, " node [\n shape = box\n ]\n");
764 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
765 fprintf (file
, "\n // List of nodes and complex constraints in "
766 "the constraint graph:\n");
768 /* The next lines print the nodes in the graph together with the
769 complex constraints attached to them. */
770 for (i
= 1; i
< graph
->size
; i
++)
772 if (i
== FIRST_REF_NODE
)
776 if (i
< FIRST_REF_NODE
)
777 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
779 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
780 if (graph
->complex[i
].exists ())
784 fprintf (file
, " [label=\"\\N\\n");
785 for (j
= 0; graph
->complex[i
].iterate (j
, &c
); ++j
)
787 dump_constraint (file
, c
);
788 fprintf (file
, "\\l");
790 fprintf (file
, "\"]");
792 fprintf (file
, ";\n");
795 /* Go over the edges. */
796 fprintf (file
, "\n // Edges in the constraint graph:\n");
797 for (i
= 1; i
< graph
->size
; i
++)
803 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
], 0, j
, bi
)
805 unsigned to
= find (j
);
808 if (i
< FIRST_REF_NODE
)
809 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
811 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
812 fprintf (file
, " -> ");
813 if (to
< FIRST_REF_NODE
)
814 fprintf (file
, "\"%s\"", get_varinfo (to
)->name
);
816 fprintf (file
, "\"*%s\"", get_varinfo (to
- FIRST_REF_NODE
)->name
);
817 fprintf (file
, ";\n");
821 /* Prints the tail of the dot file. */
822 fprintf (file
, "}\n");
825 /* Print out the constraint graph to stderr. */
828 debug_constraint_graph (void)
830 dump_constraint_graph (stderr
);
835 The solver is a simple worklist solver, that works on the following
838 sbitmap changed_nodes = all zeroes;
840 For each node that is not already collapsed:
842 set bit in changed nodes
844 while (changed_count > 0)
846 compute topological ordering for constraint graph
848 find and collapse cycles in the constraint graph (updating
849 changed if necessary)
851 for each node (n) in the graph in topological order:
854 Process each complex constraint associated with the node,
855 updating changed if necessary.
857 For each outgoing edge from n, propagate the solution from n to
858 the destination of the edge, updating changed as necessary.
862 /* Return true if two constraint expressions A and B are equal. */
865 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
867 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
870 /* Return true if constraint expression A is less than constraint expression
871 B. This is just arbitrary, but consistent, in order to give them an
875 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
877 if (a
.type
== b
.type
)
880 return a
.offset
< b
.offset
;
882 return a
.var
< b
.var
;
885 return a
.type
< b
.type
;
888 /* Return true if constraint A is less than constraint B. This is just
889 arbitrary, but consistent, in order to give them an ordering. */
892 constraint_less (const constraint_t
&a
, const constraint_t
&b
)
894 if (constraint_expr_less (a
->lhs
, b
->lhs
))
896 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
899 return constraint_expr_less (a
->rhs
, b
->rhs
);
902 /* Return true if two constraints A and B are equal. */
905 constraint_equal (struct constraint a
, struct constraint b
)
907 return constraint_expr_equal (a
.lhs
, b
.lhs
)
908 && constraint_expr_equal (a
.rhs
, b
.rhs
);
912 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
915 constraint_vec_find (vec
<constraint_t
> vec
,
916 struct constraint lookfor
)
924 place
= vec
.lower_bound (&lookfor
, constraint_less
);
925 if (place
>= vec
.length ())
928 if (!constraint_equal (*found
, lookfor
))
933 /* Union two constraint vectors, TO and FROM. Put the result in TO.
934 Returns true of TO set is changed. */
937 constraint_set_union (vec
<constraint_t
> *to
,
938 vec
<constraint_t
> *from
)
942 bool any_change
= false;
944 FOR_EACH_VEC_ELT (*from
, i
, c
)
946 if (constraint_vec_find (*to
, *c
) == NULL
)
948 unsigned int place
= to
->lower_bound (c
, constraint_less
);
949 to
->safe_insert (place
, c
);
956 /* Expands the solution in SET to all sub-fields of variables included. */
959 solution_set_expand (bitmap set
, bitmap
*expanded
)
967 *expanded
= BITMAP_ALLOC (&iteration_obstack
);
969 /* In a first pass expand variables, once for each head to avoid
970 quadratic behavior, to include all sub-fields. */
971 unsigned prev_head
= 0;
972 EXECUTE_IF_SET_IN_BITMAP (set
, 0, j
, bi
)
974 varinfo_t v
= get_varinfo (j
);
975 if (v
->is_artificial_var
978 if (v
->head
!= prev_head
)
980 varinfo_t head
= get_varinfo (v
->head
);
982 for (varinfo_t n
= vi_next (head
); n
!= NULL
; n
= vi_next (n
))
984 if (n
->id
!= head
->id
+ num
)
986 /* Usually sub variables are adjacent but since we
987 create pointed-to restrict representatives there
988 can be gaps as well. */
989 bitmap_set_range (*expanded
, head
->id
, num
);
997 bitmap_set_range (*expanded
, head
->id
, num
);
1002 /* And finally set the rest of the bits from SET in an efficient way. */
1003 bitmap_ior_into (*expanded
, set
);
1008 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
1012 set_union_with_increment (bitmap to
, bitmap delta
, HOST_WIDE_INT inc
,
1013 bitmap
*expanded_delta
)
1015 bool changed
= false;
1019 /* If the solution of DELTA contains anything it is good enough to transfer
1021 if (bitmap_bit_p (delta
, anything_id
))
1022 return bitmap_set_bit (to
, anything_id
);
1024 /* If the offset is unknown we have to expand the solution to
1026 if (inc
== UNKNOWN_OFFSET
)
1028 delta
= solution_set_expand (delta
, expanded_delta
);
1029 changed
|= bitmap_ior_into (to
, delta
);
1033 /* For non-zero offset union the offsetted solution into the destination. */
1034 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, i
, bi
)
1036 varinfo_t vi
= get_varinfo (i
);
1038 /* If this is a variable with just one field just set its bit
1040 if (vi
->is_artificial_var
1041 || vi
->is_unknown_size_var
1043 changed
|= bitmap_set_bit (to
, i
);
1046 HOST_WIDE_INT fieldoffset
= vi
->offset
+ inc
;
1047 unsigned HOST_WIDE_INT size
= vi
->size
;
1049 /* If the offset makes the pointer point to before the
1050 variable use offset zero for the field lookup. */
1051 if (fieldoffset
< 0)
1052 vi
= get_varinfo (vi
->head
);
1054 vi
= first_or_preceding_vi_for_offset (vi
, fieldoffset
);
1058 changed
|= bitmap_set_bit (to
, vi
->id
);
1063 /* We have to include all fields that overlap the current field
1067 while (vi
->offset
< fieldoffset
+ size
);
1074 /* Insert constraint C into the list of complex constraints for graph
1078 insert_into_complex (constraint_graph_t graph
,
1079 unsigned int var
, constraint_t c
)
1081 vec
<constraint_t
> complex = graph
->complex[var
];
1082 unsigned int place
= complex.lower_bound (c
, constraint_less
);
1084 /* Only insert constraints that do not already exist. */
1085 if (place
>= complex.length ()
1086 || !constraint_equal (*c
, *complex[place
]))
1087 graph
->complex[var
].safe_insert (place
, c
);
1091 /* Condense two variable nodes into a single variable node, by moving
1092 all associated info from FROM to TO. Returns true if TO node's
1093 constraint set changes after the merge. */
1096 merge_node_constraints (constraint_graph_t graph
, unsigned int to
,
1101 bool any_change
= false;
1103 gcc_checking_assert (find (from
) == to
);
1105 /* Move all complex constraints from src node into to node */
1106 FOR_EACH_VEC_ELT (graph
->complex[from
], i
, c
)
1108 /* In complex constraints for node FROM, we may have either
1109 a = *FROM, and *FROM = a, or an offseted constraint which are
1110 always added to the rhs node's constraints. */
1112 if (c
->rhs
.type
== DEREF
)
1114 else if (c
->lhs
.type
== DEREF
)
1120 any_change
= constraint_set_union (&graph
->complex[to
],
1121 &graph
->complex[from
]);
1122 graph
->complex[from
].release ();
1127 /* Remove edges involving NODE from GRAPH. */
1130 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
1132 if (graph
->succs
[node
])
1133 BITMAP_FREE (graph
->succs
[node
]);
1136 /* Merge GRAPH nodes FROM and TO into node TO. */
1139 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1142 if (graph
->indirect_cycles
[from
] != -1)
1144 /* If we have indirect cycles with the from node, and we have
1145 none on the to node, the to node has indirect cycles from the
1146 from node now that they are unified.
1147 If indirect cycles exist on both, unify the nodes that they
1148 are in a cycle with, since we know they are in a cycle with
1150 if (graph
->indirect_cycles
[to
] == -1)
1151 graph
->indirect_cycles
[to
] = graph
->indirect_cycles
[from
];
1154 /* Merge all the successor edges. */
1155 if (graph
->succs
[from
])
1157 if (!graph
->succs
[to
])
1158 graph
->succs
[to
] = BITMAP_ALLOC (&pta_obstack
);
1159 bitmap_ior_into (graph
->succs
[to
],
1160 graph
->succs
[from
]);
1163 clear_edges_for_node (graph
, from
);
1167 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1168 it doesn't exist in the graph already. */
1171 add_implicit_graph_edge (constraint_graph_t graph
, unsigned int to
,
1177 if (!graph
->implicit_preds
[to
])
1178 graph
->implicit_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1180 if (bitmap_set_bit (graph
->implicit_preds
[to
], from
))
1181 stats
.num_implicit_edges
++;
1184 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1185 it doesn't exist in the graph already.
1186 Return false if the edge already existed, true otherwise. */
1189 add_pred_graph_edge (constraint_graph_t graph
, unsigned int to
,
1192 if (!graph
->preds
[to
])
1193 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1194 bitmap_set_bit (graph
->preds
[to
], from
);
1197 /* Add a graph edge to GRAPH, going from FROM to TO if
1198 it doesn't exist in the graph already.
1199 Return false if the edge already existed, true otherwise. */
1202 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1213 if (!graph
->succs
[from
])
1214 graph
->succs
[from
] = BITMAP_ALLOC (&pta_obstack
);
1216 /* The graph solving process does not avoid "triangles", thus
1217 there can be multiple paths from a node to another involving
1218 intermediate other nodes. That causes extra copying which is
1219 most difficult to avoid when the intermediate node is ESCAPED
1220 because there are no edges added from ESCAPED. Avoid
1221 adding the direct edge FROM -> TO when we have FROM -> ESCAPED
1222 and TO contains ESCAPED.
1223 ??? Note this is only a heuristic, it does not prevent the
1224 situation from occuring. The heuristic helps PR38474 and
1225 PR99912 significantly. */
1226 if (to
< FIRST_REF_NODE
1227 && bitmap_bit_p (graph
->succs
[from
], find (escaped_id
))
1228 && bitmap_bit_p (get_varinfo (find (to
))->solution
, escaped_id
))
1230 stats
.num_avoided_edges
++;
1234 if (bitmap_set_bit (graph
->succs
[from
], to
))
1237 if (to
< FIRST_REF_NODE
&& from
< FIRST_REF_NODE
)
1245 /* Initialize the constraint graph structure to contain SIZE nodes. */
1248 init_graph (unsigned int size
)
1252 graph
= XCNEW (struct constraint_graph
);
1254 graph
->succs
= XCNEWVEC (bitmap
, graph
->size
);
1255 graph
->indirect_cycles
= XNEWVEC (int, graph
->size
);
1256 graph
->rep
= XNEWVEC (unsigned int, graph
->size
);
1257 /* ??? Macros do not support template types with multiple arguments,
1258 so we use a typedef to work around it. */
1259 typedef vec
<constraint_t
> vec_constraint_t_heap
;
1260 graph
->complex = XCNEWVEC (vec_constraint_t_heap
, size
);
1261 graph
->pe
= XCNEWVEC (unsigned int, graph
->size
);
1262 graph
->pe_rep
= XNEWVEC (int, graph
->size
);
1264 for (j
= 0; j
< graph
->size
; j
++)
1267 graph
->pe_rep
[j
] = -1;
1268 graph
->indirect_cycles
[j
] = -1;
1272 /* Build the constraint graph, adding only predecessor edges right now. */
1275 build_pred_graph (void)
1281 graph
->implicit_preds
= XCNEWVEC (bitmap
, graph
->size
);
1282 graph
->preds
= XCNEWVEC (bitmap
, graph
->size
);
1283 graph
->pointer_label
= XCNEWVEC (unsigned int, graph
->size
);
1284 graph
->loc_label
= XCNEWVEC (unsigned int, graph
->size
);
1285 graph
->pointed_by
= XCNEWVEC (bitmap
, graph
->size
);
1286 graph
->points_to
= XCNEWVEC (bitmap
, graph
->size
);
1287 graph
->eq_rep
= XNEWVEC (int, graph
->size
);
1288 graph
->direct_nodes
= sbitmap_alloc (graph
->size
);
1289 graph
->address_taken
= BITMAP_ALLOC (&predbitmap_obstack
);
1290 bitmap_clear (graph
->direct_nodes
);
1292 for (j
= 1; j
< FIRST_REF_NODE
; j
++)
1294 if (!get_varinfo (j
)->is_special_var
)
1295 bitmap_set_bit (graph
->direct_nodes
, j
);
1298 for (j
= 0; j
< graph
->size
; j
++)
1299 graph
->eq_rep
[j
] = -1;
1301 for (j
= 0; j
< varmap
.length (); j
++)
1302 graph
->indirect_cycles
[j
] = -1;
1304 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1306 struct constraint_expr lhs
= c
->lhs
;
1307 struct constraint_expr rhs
= c
->rhs
;
1308 unsigned int lhsvar
= lhs
.var
;
1309 unsigned int rhsvar
= rhs
.var
;
1311 if (lhs
.type
== DEREF
)
1314 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1315 add_pred_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1317 else if (rhs
.type
== DEREF
)
1320 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1321 add_pred_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1323 bitmap_clear_bit (graph
->direct_nodes
, lhsvar
);
1325 else if (rhs
.type
== ADDRESSOF
)
1330 if (graph
->points_to
[lhsvar
] == NULL
)
1331 graph
->points_to
[lhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1332 bitmap_set_bit (graph
->points_to
[lhsvar
], rhsvar
);
1334 if (graph
->pointed_by
[rhsvar
] == NULL
)
1335 graph
->pointed_by
[rhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1336 bitmap_set_bit (graph
->pointed_by
[rhsvar
], lhsvar
);
1338 /* Implicitly, *x = y */
1339 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1341 /* All related variables are no longer direct nodes. */
1342 bitmap_clear_bit (graph
->direct_nodes
, rhsvar
);
1343 v
= get_varinfo (rhsvar
);
1344 if (!v
->is_full_var
)
1346 v
= get_varinfo (v
->head
);
1349 bitmap_clear_bit (graph
->direct_nodes
, v
->id
);
1354 bitmap_set_bit (graph
->address_taken
, rhsvar
);
1356 else if (lhsvar
> anything_id
1357 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1360 add_pred_graph_edge (graph
, lhsvar
, rhsvar
);
1361 /* Implicitly, *x = *y */
1362 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
,
1363 FIRST_REF_NODE
+ rhsvar
);
1365 else if (lhs
.offset
!= 0 || rhs
.offset
!= 0)
1367 if (rhs
.offset
!= 0)
1368 bitmap_clear_bit (graph
->direct_nodes
, lhs
.var
);
1369 else if (lhs
.offset
!= 0)
1370 bitmap_clear_bit (graph
->direct_nodes
, rhs
.var
);
1375 /* Build the constraint graph, adding successor edges. */
1378 build_succ_graph (void)
1383 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1385 struct constraint_expr lhs
;
1386 struct constraint_expr rhs
;
1387 unsigned int lhsvar
;
1388 unsigned int rhsvar
;
1395 lhsvar
= find (lhs
.var
);
1396 rhsvar
= find (rhs
.var
);
1398 if (lhs
.type
== DEREF
)
1400 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1401 add_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1403 else if (rhs
.type
== DEREF
)
1405 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1406 add_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1408 else if (rhs
.type
== ADDRESSOF
)
1411 gcc_checking_assert (find (rhs
.var
) == rhs
.var
);
1412 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1414 else if (lhsvar
> anything_id
1415 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1417 add_graph_edge (graph
, lhsvar
, rhsvar
);
1421 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1422 receive pointers. */
1423 t
= find (storedanything_id
);
1424 for (i
= integer_id
+ 1; i
< FIRST_REF_NODE
; ++i
)
1426 if (!bitmap_bit_p (graph
->direct_nodes
, i
)
1427 && get_varinfo (i
)->may_have_pointers
)
1428 add_graph_edge (graph
, find (i
), t
);
1431 /* Everything stored to ANYTHING also potentially escapes. */
1432 add_graph_edge (graph
, find (escaped_id
), t
);
1436 /* Changed variables on the last iteration. */
1437 static bitmap changed
;
1439 /* Strongly Connected Component visitation info. */
1444 scc_info (size_t size
);
1447 auto_sbitmap visited
;
1448 auto_sbitmap deleted
;
1450 unsigned int *node_mapping
;
1452 auto_vec
<unsigned> scc_stack
;
1456 /* Recursive routine to find strongly connected components in GRAPH.
1457 SI is the SCC info to store the information in, and N is the id of current
1458 graph node we are processing.
1460 This is Tarjan's strongly connected component finding algorithm, as
1461 modified by Nuutila to keep only non-root nodes on the stack.
1462 The algorithm can be found in "On finding the strongly connected
1463 connected components in a directed graph" by Esko Nuutila and Eljas
1464 Soisalon-Soininen, in Information Processing Letters volume 49,
1465 number 1, pages 9-14. */
1468 scc_visit (constraint_graph_t graph
, class scc_info
*si
, unsigned int n
)
1472 unsigned int my_dfs
;
1474 bitmap_set_bit (si
->visited
, n
);
1475 si
->dfs
[n
] = si
->current_index
++;
1476 my_dfs
= si
->dfs
[n
];
1478 /* Visit all the successors. */
1479 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
1483 if (i
> LAST_REF_NODE
)
1487 if (bitmap_bit_p (si
->deleted
, w
))
1490 if (!bitmap_bit_p (si
->visited
, w
))
1491 scc_visit (graph
, si
, w
);
1493 unsigned int t
= find (w
);
1494 gcc_checking_assert (find (n
) == n
);
1495 if (si
->dfs
[t
] < si
->dfs
[n
])
1496 si
->dfs
[n
] = si
->dfs
[t
];
1499 /* See if any components have been identified. */
1500 if (si
->dfs
[n
] == my_dfs
)
1502 if (si
->scc_stack
.length () > 0
1503 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1505 bitmap scc
= BITMAP_ALLOC (NULL
);
1506 unsigned int lowest_node
;
1509 bitmap_set_bit (scc
, n
);
1511 while (si
->scc_stack
.length () != 0
1512 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1514 unsigned int w
= si
->scc_stack
.pop ();
1516 bitmap_set_bit (scc
, w
);
1519 lowest_node
= bitmap_first_set_bit (scc
);
1520 gcc_assert (lowest_node
< FIRST_REF_NODE
);
1522 /* Collapse the SCC nodes into a single node, and mark the
1524 EXECUTE_IF_SET_IN_BITMAP (scc
, 0, i
, bi
)
1526 if (i
< FIRST_REF_NODE
)
1528 if (unite (lowest_node
, i
))
1529 unify_nodes (graph
, lowest_node
, i
, false);
1533 unite (lowest_node
, i
);
1534 graph
->indirect_cycles
[i
- FIRST_REF_NODE
] = lowest_node
;
1538 bitmap_set_bit (si
->deleted
, n
);
1541 si
->scc_stack
.safe_push (n
);
1544 /* Unify node FROM into node TO, updating the changed count if
1545 necessary when UPDATE_CHANGED is true. */
1548 unify_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1549 bool update_changed
)
1551 gcc_checking_assert (to
!= from
&& find (to
) == to
);
1553 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1554 fprintf (dump_file
, "Unifying %s to %s\n",
1555 get_varinfo (from
)->name
,
1556 get_varinfo (to
)->name
);
1559 stats
.unified_vars_dynamic
++;
1561 stats
.unified_vars_static
++;
1563 merge_graph_nodes (graph
, to
, from
);
1564 if (merge_node_constraints (graph
, to
, from
))
1567 bitmap_set_bit (changed
, to
);
1570 /* Mark TO as changed if FROM was changed. If TO was already marked
1571 as changed, decrease the changed count. */
1574 && bitmap_clear_bit (changed
, from
))
1575 bitmap_set_bit (changed
, to
);
1576 varinfo_t fromvi
= get_varinfo (from
);
1577 if (fromvi
->solution
)
1579 /* If the solution changes because of the merging, we need to mark
1580 the variable as changed. */
1581 varinfo_t tovi
= get_varinfo (to
);
1582 if (bitmap_ior_into (tovi
->solution
, fromvi
->solution
))
1585 bitmap_set_bit (changed
, to
);
1588 BITMAP_FREE (fromvi
->solution
);
1589 if (fromvi
->oldsolution
)
1590 BITMAP_FREE (fromvi
->oldsolution
);
1592 if (stats
.iterations
> 0
1593 && tovi
->oldsolution
)
1594 BITMAP_FREE (tovi
->oldsolution
);
1596 if (graph
->succs
[to
])
1597 bitmap_clear_bit (graph
->succs
[to
], to
);
1600 /* Add a copy edge FROM -> TO, optimizing special cases. Returns TRUE
1601 if the solution of TO changed. */
1604 solve_add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1607 /* Adding edges from the special vars is pointless.
1608 They don't have sets that can change. */
1609 if (get_varinfo (from
)->is_special_var
)
1610 return bitmap_ior_into (get_varinfo (to
)->solution
,
1611 get_varinfo (from
)->solution
);
1612 /* Merging the solution from ESCAPED needlessly increases
1613 the set. Use ESCAPED as representative instead. */
1614 else if (from
== find (escaped_id
))
1615 return bitmap_set_bit (get_varinfo (to
)->solution
, escaped_id
);
1616 else if (get_varinfo (from
)->may_have_pointers
1617 && add_graph_edge (graph
, to
, from
))
1618 return bitmap_ior_into (get_varinfo (to
)->solution
,
1619 get_varinfo (from
)->solution
);
1623 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1624 starting solution for y. */
1627 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1628 bitmap delta
, bitmap
*expanded_delta
)
1630 unsigned int lhs
= c
->lhs
.var
;
1632 bitmap sol
= get_varinfo (lhs
)->solution
;
1635 HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1637 /* Our IL does not allow this. */
1638 gcc_checking_assert (c
->lhs
.offset
== 0);
1640 /* If the solution of Y contains anything it is good enough to transfer
1642 if (bitmap_bit_p (delta
, anything_id
))
1644 flag
|= bitmap_set_bit (sol
, anything_id
);
1648 /* If we do not know at with offset the rhs is dereferenced compute
1649 the reachability set of DELTA, conservatively assuming it is
1650 dereferenced at all valid offsets. */
1651 if (roffset
== UNKNOWN_OFFSET
)
1653 delta
= solution_set_expand (delta
, expanded_delta
);
1654 /* No further offset processing is necessary. */
1658 /* For each variable j in delta (Sol(y)), add
1659 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1660 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1662 varinfo_t v
= get_varinfo (j
);
1663 HOST_WIDE_INT fieldoffset
= v
->offset
+ roffset
;
1664 unsigned HOST_WIDE_INT size
= v
->size
;
1669 else if (roffset
!= 0)
1671 if (fieldoffset
< 0)
1672 v
= get_varinfo (v
->head
);
1674 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1677 /* We have to include all fields that overlap the current field
1678 shifted by roffset. */
1683 flag
|= solve_add_graph_edge (graph
, lhs
, t
);
1691 while (v
->offset
< fieldoffset
+ size
);
1695 /* If the LHS solution changed, mark the var as changed. */
1697 bitmap_set_bit (changed
, lhs
);
1700 /* Process a constraint C that represents *(x + off) = y using DELTA
1701 as the starting solution for x. */
1704 do_ds_constraint (constraint_t c
, bitmap delta
, bitmap
*expanded_delta
)
1706 unsigned int rhs
= c
->rhs
.var
;
1707 bitmap sol
= get_varinfo (rhs
)->solution
;
1710 HOST_WIDE_INT loff
= c
->lhs
.offset
;
1711 bool escaped_p
= false;
1713 /* Our IL does not allow this. */
1714 gcc_checking_assert (c
->rhs
.offset
== 0);
1716 /* If the solution of y contains ANYTHING simply use the ANYTHING
1717 solution. This avoids needlessly increasing the points-to sets. */
1718 if (bitmap_bit_p (sol
, anything_id
))
1719 sol
= get_varinfo (find (anything_id
))->solution
;
1721 /* If the solution for x contains ANYTHING we have to merge the
1722 solution of y into all pointer variables which we do via
1724 if (bitmap_bit_p (delta
, anything_id
))
1726 unsigned t
= find (storedanything_id
);
1727 if (solve_add_graph_edge (graph
, t
, rhs
))
1728 bitmap_set_bit (changed
, t
);
1732 /* If we do not know at with offset the rhs is dereferenced compute
1733 the reachability set of DELTA, conservatively assuming it is
1734 dereferenced at all valid offsets. */
1735 if (loff
== UNKNOWN_OFFSET
)
1737 delta
= solution_set_expand (delta
, expanded_delta
);
1741 /* For each member j of delta (Sol(x)), add an edge from y to j and
1742 union Sol(y) into Sol(j) */
1743 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1745 varinfo_t v
= get_varinfo (j
);
1747 HOST_WIDE_INT fieldoffset
= v
->offset
+ loff
;
1748 unsigned HOST_WIDE_INT size
= v
->size
;
1754 if (fieldoffset
< 0)
1755 v
= get_varinfo (v
->head
);
1757 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1760 /* We have to include all fields that overlap the current field
1764 if (v
->may_have_pointers
)
1766 /* If v is a global variable then this is an escape point. */
1767 if (v
->is_global_var
1770 t
= find (escaped_id
);
1771 if (add_graph_edge (graph
, t
, rhs
)
1772 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1773 bitmap_set_bit (changed
, t
);
1774 /* Enough to let rhs escape once. */
1778 if (v
->is_special_var
)
1783 if (solve_add_graph_edge (graph
, t
, rhs
))
1784 bitmap_set_bit (changed
, t
);
1793 while (v
->offset
< fieldoffset
+ size
);
1797 /* Handle a non-simple (simple meaning requires no iteration),
1798 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1801 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
,
1802 bitmap
*expanded_delta
)
1804 if (c
->lhs
.type
== DEREF
)
1806 if (c
->rhs
.type
== ADDRESSOF
)
1813 do_ds_constraint (c
, delta
, expanded_delta
);
1816 else if (c
->rhs
.type
== DEREF
)
1819 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1820 do_sd_constraint (graph
, c
, delta
, expanded_delta
);
1827 gcc_checking_assert (c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
1828 && c
->rhs
.offset
!= 0 && c
->lhs
.offset
== 0);
1829 tmp
= get_varinfo (c
->lhs
.var
)->solution
;
1831 flag
= set_union_with_increment (tmp
, delta
, c
->rhs
.offset
,
1835 bitmap_set_bit (changed
, c
->lhs
.var
);
1839 /* Initialize and return a new SCC info structure. */
1841 scc_info::scc_info (size_t size
) :
1842 visited (size
), deleted (size
), current_index (0), scc_stack (1)
1844 bitmap_clear (visited
);
1845 bitmap_clear (deleted
);
1846 node_mapping
= XNEWVEC (unsigned int, size
);
1847 dfs
= XCNEWVEC (unsigned int, size
);
1849 for (size_t i
= 0; i
< size
; i
++)
1850 node_mapping
[i
] = i
;
1853 /* Free an SCC info structure pointed to by SI */
1855 scc_info::~scc_info ()
1857 free (node_mapping
);
1862 /* Find indirect cycles in GRAPH that occur, using strongly connected
1863 components, and note them in the indirect cycles map.
1865 This technique comes from Ben Hardekopf and Calvin Lin,
1866 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1867 Lines of Code", submitted to PLDI 2007. */
1870 find_indirect_cycles (constraint_graph_t graph
)
1873 unsigned int size
= graph
->size
;
1876 for (i
= 0; i
< MIN (LAST_REF_NODE
, size
); i
++ )
1877 if (!bitmap_bit_p (si
.visited
, i
) && find (i
) == i
)
1878 scc_visit (graph
, &si
, i
);
1881 /* Visit the graph in topological order starting at node N, and store the
1882 order in TOPO_ORDER using VISITED to indicate visited nodes. */
1885 topo_visit (constraint_graph_t graph
, vec
<unsigned> &topo_order
,
1886 sbitmap visited
, unsigned int n
)
1891 bitmap_set_bit (visited
, n
);
1893 if (graph
->succs
[n
])
1894 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[n
], 0, j
, bi
)
1896 unsigned k
= find (j
);
1897 if (!bitmap_bit_p (visited
, k
))
1898 topo_visit (graph
, topo_order
, visited
, k
);
1901 topo_order
.quick_push (n
);
1904 /* Compute a topological ordering for GRAPH, and return the result. */
1906 static auto_vec
<unsigned>
1907 compute_topo_order (constraint_graph_t graph
)
1910 unsigned int size
= graph
->size
;
1912 auto_sbitmap
visited (size
);
1913 bitmap_clear (visited
);
1915 /* For the heuristic in add_graph_edge to work optimally make sure to
1916 first visit the connected component of the graph containing
1917 ESCAPED. Do this by extracting the connected component
1918 with ESCAPED and append that to all other components as solve_graph
1919 pops from the order. */
1920 auto_vec
<unsigned> tail (size
);
1921 topo_visit (graph
, tail
, visited
, find (escaped_id
));
1923 auto_vec
<unsigned> topo_order (size
);
1925 for (i
= 0; i
!= size
; ++i
)
1926 if (!bitmap_bit_p (visited
, i
) && find (i
) == i
)
1927 topo_visit (graph
, topo_order
, visited
, i
);
1929 topo_order
.splice (tail
);
1933 /* Structure used to for hash value numbering of pointer equivalence
1936 typedef struct equiv_class_label
1939 unsigned int equivalence_class
;
1941 } *equiv_class_label_t
;
1942 typedef const struct equiv_class_label
*const_equiv_class_label_t
;
1944 /* Equiv_class_label hashtable helpers. */
1946 struct equiv_class_hasher
: nofree_ptr_hash
<equiv_class_label
>
1948 static inline hashval_t
hash (const equiv_class_label
*);
1949 static inline bool equal (const equiv_class_label
*,
1950 const equiv_class_label
*);
1953 /* Hash function for a equiv_class_label_t */
1956 equiv_class_hasher::hash (const equiv_class_label
*ecl
)
1958 return ecl
->hashcode
;
1961 /* Equality function for two equiv_class_label_t's. */
1964 equiv_class_hasher::equal (const equiv_class_label
*eql1
,
1965 const equiv_class_label
*eql2
)
1967 return (eql1
->hashcode
== eql2
->hashcode
1968 && bitmap_equal_p (eql1
->labels
, eql2
->labels
));
1971 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1973 static hash_table
<equiv_class_hasher
> *pointer_equiv_class_table
;
1975 /* A hashtable for mapping a bitmap of labels->location equivalence
1977 static hash_table
<equiv_class_hasher
> *location_equiv_class_table
;
1979 struct obstack equiv_class_obstack
;
1981 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1982 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1983 is equivalent to. */
1985 static equiv_class_label
*
1986 equiv_class_lookup_or_add (hash_table
<equiv_class_hasher
> *table
,
1989 equiv_class_label
**slot
;
1990 equiv_class_label ecl
;
1992 ecl
.labels
= labels
;
1993 ecl
.hashcode
= bitmap_hash (labels
);
1994 slot
= table
->find_slot (&ecl
, INSERT
);
1997 *slot
= XOBNEW (&equiv_class_obstack
, struct equiv_class_label
);
1998 (*slot
)->labels
= labels
;
1999 (*slot
)->hashcode
= ecl
.hashcode
;
2000 (*slot
)->equivalence_class
= 0;
2006 /* Perform offline variable substitution.
2008 This is a worst case quadratic time way of identifying variables
2009 that must have equivalent points-to sets, including those caused by
2010 static cycles, and single entry subgraphs, in the constraint graph.
2012 The technique is described in "Exploiting Pointer and Location
2013 Equivalence to Optimize Pointer Analysis. In the 14th International
2014 Static Analysis Symposium (SAS), August 2007." It is known as the
2015 "HU" algorithm, and is equivalent to value numbering the collapsed
2016 constraint graph including evaluating unions.
2018 The general method of finding equivalence classes is as follows:
2019 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
2020 Initialize all non-REF nodes to be direct nodes.
2021 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
2023 For each constraint containing the dereference, we also do the same
2026 We then compute SCC's in the graph and unify nodes in the same SCC,
2029 For each non-collapsed node x:
2030 Visit all unvisited explicit incoming edges.
2031 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
2033 Lookup the equivalence class for pts(x).
2034 If we found one, equivalence_class(x) = found class.
2035 Otherwise, equivalence_class(x) = new class, and new_class is
2036 added to the lookup table.
2038 All direct nodes with the same equivalence class can be replaced
2039 with a single representative node.
2040 All unlabeled nodes (label == 0) are not pointers and all edges
2041 involving them can be eliminated.
2042 We perform these optimizations during rewrite_constraints
2044 In addition to pointer equivalence class finding, we also perform
2045 location equivalence class finding. This is the set of variables
2046 that always appear together in points-to sets. We use this to
2047 compress the size of the points-to sets. */
2049 /* Current maximum pointer equivalence class id. */
2050 static int pointer_equiv_class
;
2052 /* Current maximum location equivalence class id. */
2053 static int location_equiv_class
;
2055 /* Recursive routine to find strongly connected components in GRAPH,
2056 and label it's nodes with DFS numbers. */
2059 condense_visit (constraint_graph_t graph
, class scc_info
*si
, unsigned int n
)
2063 unsigned int my_dfs
;
2065 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2066 bitmap_set_bit (si
->visited
, n
);
2067 si
->dfs
[n
] = si
->current_index
++;
2068 my_dfs
= si
->dfs
[n
];
2070 /* Visit all the successors. */
2071 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2073 unsigned int w
= si
->node_mapping
[i
];
2075 if (bitmap_bit_p (si
->deleted
, w
))
2078 if (!bitmap_bit_p (si
->visited
, w
))
2079 condense_visit (graph
, si
, w
);
2081 unsigned int t
= si
->node_mapping
[w
];
2082 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2083 if (si
->dfs
[t
] < si
->dfs
[n
])
2084 si
->dfs
[n
] = si
->dfs
[t
];
2087 /* Visit all the implicit predecessors. */
2088 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->implicit_preds
[n
], 0, i
, bi
)
2090 unsigned int w
= si
->node_mapping
[i
];
2092 if (bitmap_bit_p (si
->deleted
, w
))
2095 if (!bitmap_bit_p (si
->visited
, w
))
2096 condense_visit (graph
, si
, w
);
2098 unsigned int t
= si
->node_mapping
[w
];
2099 gcc_assert (si
->node_mapping
[n
] == n
);
2100 if (si
->dfs
[t
] < si
->dfs
[n
])
2101 si
->dfs
[n
] = si
->dfs
[t
];
2104 /* See if any components have been identified. */
2105 if (si
->dfs
[n
] == my_dfs
)
2107 if (si
->scc_stack
.length () != 0
2108 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
2110 /* Find the first node of the SCC and do non-bitmap work. */
2111 bool direct_p
= true;
2112 unsigned first
= si
->scc_stack
.length ();
2116 unsigned int w
= si
->scc_stack
[first
];
2117 si
->node_mapping
[w
] = n
;
2118 if (!bitmap_bit_p (graph
->direct_nodes
, w
))
2122 && si
->dfs
[si
->scc_stack
[first
- 1]] >= my_dfs
);
2124 bitmap_clear_bit (graph
->direct_nodes
, n
);
2126 /* Want to reduce to node n, push that first. */
2127 si
->scc_stack
.reserve (1);
2128 si
->scc_stack
.quick_push (si
->scc_stack
[first
]);
2129 si
->scc_stack
[first
] = n
;
2131 unsigned scc_size
= si
->scc_stack
.length () - first
;
2132 unsigned split
= scc_size
/ 2;
2133 unsigned carry
= scc_size
- split
* 2;
2136 for (unsigned i
= 0; i
< split
; ++i
)
2138 unsigned a
= si
->scc_stack
[first
+ i
];
2139 unsigned b
= si
->scc_stack
[first
+ split
+ carry
+ i
];
2141 /* Unify our nodes. */
2142 if (graph
->preds
[b
])
2144 if (!graph
->preds
[a
])
2145 std::swap (graph
->preds
[a
], graph
->preds
[b
]);
2147 bitmap_ior_into_and_free (graph
->preds
[a
],
2150 if (graph
->implicit_preds
[b
])
2152 if (!graph
->implicit_preds
[a
])
2153 std::swap (graph
->implicit_preds
[a
],
2154 graph
->implicit_preds
[b
]);
2156 bitmap_ior_into_and_free (graph
->implicit_preds
[a
],
2157 &graph
->implicit_preds
[b
]);
2159 if (graph
->points_to
[b
])
2161 if (!graph
->points_to
[a
])
2162 std::swap (graph
->points_to
[a
], graph
->points_to
[b
]);
2164 bitmap_ior_into_and_free (graph
->points_to
[a
],
2165 &graph
->points_to
[b
]);
2168 unsigned remain
= split
+ carry
;
2170 carry
= remain
- split
* 2;
2172 /* Actually pop the SCC. */
2173 si
->scc_stack
.truncate (first
);
2175 bitmap_set_bit (si
->deleted
, n
);
2178 si
->scc_stack
.safe_push (n
);
2181 /* Label pointer equivalences.
2183 This performs a value numbering of the constraint graph to
2184 discover which variables will always have the same points-to sets
2185 under the current set of constraints.
2187 The way it value numbers is to store the set of points-to bits
2188 generated by the constraints and graph edges. This is just used as a
2189 hash and equality comparison. The *actual set of points-to bits* is
2190 completely irrelevant, in that we don't care about being able to
2193 The equality values (currently bitmaps) just have to satisfy a few
2194 constraints, the main ones being:
2195 1. The combining operation must be order independent.
2196 2. The end result of a given set of operations must be unique iff the
2197 combination of input values is unique
2201 label_visit (constraint_graph_t graph
, class scc_info
*si
, unsigned int n
)
2203 unsigned int i
, first_pred
;
2206 bitmap_set_bit (si
->visited
, n
);
2208 /* Label and union our incoming edges's points to sets. */
2210 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2212 unsigned int w
= si
->node_mapping
[i
];
2213 if (!bitmap_bit_p (si
->visited
, w
))
2214 label_visit (graph
, si
, w
);
2216 /* Skip unused edges */
2217 if (w
== n
|| graph
->pointer_label
[w
] == 0)
2220 if (graph
->points_to
[w
])
2222 if (!graph
->points_to
[n
])
2224 if (first_pred
== -1U)
2228 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2229 bitmap_ior (graph
->points_to
[n
],
2230 graph
->points_to
[first_pred
],
2231 graph
->points_to
[w
]);
2235 bitmap_ior_into (graph
->points_to
[n
], graph
->points_to
[w
]);
2239 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2240 if (!bitmap_bit_p (graph
->direct_nodes
, n
))
2242 if (!graph
->points_to
[n
])
2244 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2245 if (first_pred
!= -1U)
2246 bitmap_copy (graph
->points_to
[n
], graph
->points_to
[first_pred
]);
2248 bitmap_set_bit (graph
->points_to
[n
], FIRST_REF_NODE
+ n
);
2249 graph
->pointer_label
[n
] = pointer_equiv_class
++;
2250 equiv_class_label_t ecl
;
2251 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2252 graph
->points_to
[n
]);
2253 ecl
->equivalence_class
= graph
->pointer_label
[n
];
2257 /* If there was only a single non-empty predecessor the pointer equiv
2258 class is the same. */
2259 if (!graph
->points_to
[n
])
2261 if (first_pred
!= -1U)
2263 graph
->pointer_label
[n
] = graph
->pointer_label
[first_pred
];
2264 graph
->points_to
[n
] = graph
->points_to
[first_pred
];
2269 if (!bitmap_empty_p (graph
->points_to
[n
]))
2271 equiv_class_label_t ecl
;
2272 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2273 graph
->points_to
[n
]);
2274 if (ecl
->equivalence_class
== 0)
2275 ecl
->equivalence_class
= pointer_equiv_class
++;
2278 BITMAP_FREE (graph
->points_to
[n
]);
2279 graph
->points_to
[n
] = ecl
->labels
;
2281 graph
->pointer_label
[n
] = ecl
->equivalence_class
;
2285 /* Print the pred graph in dot format. */
2288 dump_pred_graph (class scc_info
*si
, FILE *file
)
2292 /* Only print the graph if it has already been initialized: */
2296 /* Prints the header of the dot file: */
2297 fprintf (file
, "strict digraph {\n");
2298 fprintf (file
, " node [\n shape = box\n ]\n");
2299 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
2300 fprintf (file
, "\n // List of nodes and complex constraints in "
2301 "the constraint graph:\n");
2303 /* The next lines print the nodes in the graph together with the
2304 complex constraints attached to them. */
2305 for (i
= 1; i
< graph
->size
; i
++)
2307 if (i
== FIRST_REF_NODE
)
2309 if (si
->node_mapping
[i
] != i
)
2311 if (i
< FIRST_REF_NODE
)
2312 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2314 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2315 if (graph
->points_to
[i
]
2316 && !bitmap_empty_p (graph
->points_to
[i
]))
2318 if (i
< FIRST_REF_NODE
)
2319 fprintf (file
, "[label=\"%s = {", get_varinfo (i
)->name
);
2321 fprintf (file
, "[label=\"*%s = {",
2322 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2325 EXECUTE_IF_SET_IN_BITMAP (graph
->points_to
[i
], 0, j
, bi
)
2326 fprintf (file
, " %d", j
);
2327 fprintf (file
, " }\"]");
2329 fprintf (file
, ";\n");
2332 /* Go over the edges. */
2333 fprintf (file
, "\n // Edges in the constraint graph:\n");
2334 for (i
= 1; i
< graph
->size
; i
++)
2338 if (si
->node_mapping
[i
] != i
)
2340 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[i
], 0, j
, bi
)
2342 unsigned from
= si
->node_mapping
[j
];
2343 if (from
< FIRST_REF_NODE
)
2344 fprintf (file
, "\"%s\"", get_varinfo (from
)->name
);
2346 fprintf (file
, "\"*%s\"", get_varinfo (from
- FIRST_REF_NODE
)->name
);
2347 fprintf (file
, " -> ");
2348 if (i
< FIRST_REF_NODE
)
2349 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2351 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2352 fprintf (file
, ";\n");
2356 /* Prints the tail of the dot file. */
2357 fprintf (file
, "}\n");
2360 /* Perform offline variable substitution, discovering equivalence
2361 classes, and eliminating non-pointer variables. */
2363 static class scc_info
*
2364 perform_var_substitution (constraint_graph_t graph
)
2367 unsigned int size
= graph
->size
;
2368 scc_info
*si
= new scc_info (size
);
2370 bitmap_obstack_initialize (&iteration_obstack
);
2371 gcc_obstack_init (&equiv_class_obstack
);
2372 pointer_equiv_class_table
= new hash_table
<equiv_class_hasher
> (511);
2373 location_equiv_class_table
2374 = new hash_table
<equiv_class_hasher
> (511);
2375 pointer_equiv_class
= 1;
2376 location_equiv_class
= 1;
2378 /* Condense the nodes, which means to find SCC's, count incoming
2379 predecessors, and unite nodes in SCC's. */
2380 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2381 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2382 condense_visit (graph
, si
, si
->node_mapping
[i
]);
2384 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
2386 fprintf (dump_file
, "\n\n// The constraint graph before var-substitution "
2387 "in dot format:\n");
2388 dump_pred_graph (si
, dump_file
);
2389 fprintf (dump_file
, "\n\n");
2392 bitmap_clear (si
->visited
);
2393 /* Actually the label the nodes for pointer equivalences */
2394 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2395 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2396 label_visit (graph
, si
, si
->node_mapping
[i
]);
2398 /* Calculate location equivalence labels. */
2399 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2405 if (!graph
->pointed_by
[i
])
2407 pointed_by
= BITMAP_ALLOC (&iteration_obstack
);
2409 /* Translate the pointed-by mapping for pointer equivalence
2411 EXECUTE_IF_SET_IN_BITMAP (graph
->pointed_by
[i
], 0, j
, bi
)
2413 bitmap_set_bit (pointed_by
,
2414 graph
->pointer_label
[si
->node_mapping
[j
]]);
2416 /* The original pointed_by is now dead. */
2417 BITMAP_FREE (graph
->pointed_by
[i
]);
2419 /* Look up the location equivalence label if one exists, or make
2421 equiv_class_label_t ecl
;
2422 ecl
= equiv_class_lookup_or_add (location_equiv_class_table
, pointed_by
);
2423 if (ecl
->equivalence_class
== 0)
2424 ecl
->equivalence_class
= location_equiv_class
++;
2427 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2428 fprintf (dump_file
, "Found location equivalence for node %s\n",
2429 get_varinfo (i
)->name
);
2430 BITMAP_FREE (pointed_by
);
2432 graph
->loc_label
[i
] = ecl
->equivalence_class
;
2436 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2437 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2439 unsigned j
= si
->node_mapping
[i
];
2442 fprintf (dump_file
, "%s node id %d ",
2443 bitmap_bit_p (graph
->direct_nodes
, i
)
2444 ? "Direct" : "Indirect", i
);
2445 if (i
< FIRST_REF_NODE
)
2446 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2448 fprintf (dump_file
, "\"*%s\"",
2449 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2450 fprintf (dump_file
, " mapped to SCC leader node id %d ", j
);
2451 if (j
< FIRST_REF_NODE
)
2452 fprintf (dump_file
, "\"%s\"\n", get_varinfo (j
)->name
);
2454 fprintf (dump_file
, "\"*%s\"\n",
2455 get_varinfo (j
- FIRST_REF_NODE
)->name
);
2460 "Equivalence classes for %s node id %d ",
2461 bitmap_bit_p (graph
->direct_nodes
, i
)
2462 ? "direct" : "indirect", i
);
2463 if (i
< FIRST_REF_NODE
)
2464 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2466 fprintf (dump_file
, "\"*%s\"",
2467 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2469 ": pointer %d, location %d\n",
2470 graph
->pointer_label
[i
], graph
->loc_label
[i
]);
2474 /* Quickly eliminate our non-pointer variables. */
2476 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2478 unsigned int node
= si
->node_mapping
[i
];
2480 if (graph
->pointer_label
[node
] == 0)
2482 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2484 "%s is a non-pointer variable, eliminating edges.\n",
2485 get_varinfo (node
)->name
);
2486 stats
.nonpointer_vars
++;
2487 clear_edges_for_node (graph
, node
);
2494 /* Free information that was only necessary for variable
2498 free_var_substitution_info (class scc_info
*si
)
2501 free (graph
->pointer_label
);
2502 free (graph
->loc_label
);
2503 free (graph
->pointed_by
);
2504 free (graph
->points_to
);
2505 free (graph
->eq_rep
);
2506 sbitmap_free (graph
->direct_nodes
);
2507 delete pointer_equiv_class_table
;
2508 pointer_equiv_class_table
= NULL
;
2509 delete location_equiv_class_table
;
2510 location_equiv_class_table
= NULL
;
2511 obstack_free (&equiv_class_obstack
, NULL
);
2512 bitmap_obstack_release (&iteration_obstack
);
2515 /* Return an existing node that is equivalent to NODE, which has
2516 equivalence class LABEL, if one exists. Return NODE otherwise. */
2519 find_equivalent_node (constraint_graph_t graph
,
2520 unsigned int node
, unsigned int label
)
2522 /* If the address version of this variable is unused, we can
2523 substitute it for anything else with the same label.
2524 Otherwise, we know the pointers are equivalent, but not the
2525 locations, and we can unite them later. */
2527 if (!bitmap_bit_p (graph
->address_taken
, node
))
2529 gcc_checking_assert (label
< graph
->size
);
2531 if (graph
->eq_rep
[label
] != -1)
2533 /* Unify the two variables since we know they are equivalent. */
2534 if (unite (graph
->eq_rep
[label
], node
))
2535 unify_nodes (graph
, graph
->eq_rep
[label
], node
, false);
2536 return graph
->eq_rep
[label
];
2540 graph
->eq_rep
[label
] = node
;
2541 graph
->pe_rep
[label
] = node
;
2546 gcc_checking_assert (label
< graph
->size
);
2547 graph
->pe
[node
] = label
;
2548 if (graph
->pe_rep
[label
] == -1)
2549 graph
->pe_rep
[label
] = node
;
2555 /* Unite pointer equivalent but not location equivalent nodes in
2556 GRAPH. This may only be performed once variable substitution is
2560 unite_pointer_equivalences (constraint_graph_t graph
)
2564 /* Go through the pointer equivalences and unite them to their
2565 representative, if they aren't already. */
2566 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2568 unsigned int label
= graph
->pe
[i
];
2571 int label_rep
= graph
->pe_rep
[label
];
2573 if (label_rep
== -1)
2576 label_rep
= find (label_rep
);
2577 if (label_rep
>= 0 && unite (label_rep
, find (i
)))
2578 unify_nodes (graph
, label_rep
, i
, false);
2583 /* Move complex constraints to the GRAPH nodes they belong to. */
2586 move_complex_constraints (constraint_graph_t graph
)
2591 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2595 struct constraint_expr lhs
= c
->lhs
;
2596 struct constraint_expr rhs
= c
->rhs
;
2598 if (lhs
.type
== DEREF
)
2600 insert_into_complex (graph
, lhs
.var
, c
);
2602 else if (rhs
.type
== DEREF
)
2604 if (!(get_varinfo (lhs
.var
)->is_special_var
))
2605 insert_into_complex (graph
, rhs
.var
, c
);
2607 else if (rhs
.type
!= ADDRESSOF
&& lhs
.var
> anything_id
2608 && (lhs
.offset
!= 0 || rhs
.offset
!= 0))
2610 insert_into_complex (graph
, rhs
.var
, c
);
2617 /* Optimize and rewrite complex constraints while performing
2618 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2619 result of perform_variable_substitution. */
2622 rewrite_constraints (constraint_graph_t graph
,
2630 for (unsigned int j
= 0; j
< graph
->size
; j
++)
2631 gcc_assert (find (j
) == j
);
2634 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2636 struct constraint_expr lhs
= c
->lhs
;
2637 struct constraint_expr rhs
= c
->rhs
;
2638 unsigned int lhsvar
= find (lhs
.var
);
2639 unsigned int rhsvar
= find (rhs
.var
);
2640 unsigned int lhsnode
, rhsnode
;
2641 unsigned int lhslabel
, rhslabel
;
2643 lhsnode
= si
->node_mapping
[lhsvar
];
2644 rhsnode
= si
->node_mapping
[rhsvar
];
2645 lhslabel
= graph
->pointer_label
[lhsnode
];
2646 rhslabel
= graph
->pointer_label
[rhsnode
];
2648 /* See if it is really a non-pointer variable, and if so, ignore
2652 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2655 fprintf (dump_file
, "%s is a non-pointer variable, "
2656 "ignoring constraint:",
2657 get_varinfo (lhs
.var
)->name
);
2658 dump_constraint (dump_file
, c
);
2659 fprintf (dump_file
, "\n");
2661 constraints
[i
] = NULL
;
2667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2670 fprintf (dump_file
, "%s is a non-pointer variable, "
2671 "ignoring constraint:",
2672 get_varinfo (rhs
.var
)->name
);
2673 dump_constraint (dump_file
, c
);
2674 fprintf (dump_file
, "\n");
2676 constraints
[i
] = NULL
;
2680 lhsvar
= find_equivalent_node (graph
, lhsvar
, lhslabel
);
2681 rhsvar
= find_equivalent_node (graph
, rhsvar
, rhslabel
);
2682 c
->lhs
.var
= lhsvar
;
2683 c
->rhs
.var
= rhsvar
;
2687 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2688 part of an SCC, false otherwise. */
2691 eliminate_indirect_cycles (unsigned int node
)
2693 if (graph
->indirect_cycles
[node
] != -1
2694 && !bitmap_empty_p (get_varinfo (node
)->solution
))
2697 auto_vec
<unsigned> queue
;
2699 unsigned int to
= find (graph
->indirect_cycles
[node
]);
2702 /* We can't touch the solution set and call unify_nodes
2703 at the same time, because unify_nodes is going to do
2704 bitmap unions into it. */
2706 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node
)->solution
, 0, i
, bi
)
2708 if (find (i
) == i
&& i
!= to
)
2711 queue
.safe_push (i
);
2716 queue
.iterate (queuepos
, &i
);
2719 unify_nodes (graph
, to
, i
, true);
2726 /* Solve the constraint graph GRAPH using our worklist solver.
2727 This is based on the PW* family of solvers from the "Efficient Field
2728 Sensitive Pointer Analysis for C" paper.
2729 It works by iterating over all the graph nodes, processing the complex
2730 constraints and propagating the copy constraints, until everything stops
2731 changed. This corresponds to steps 6-8 in the solving list given above. */
2734 solve_graph (constraint_graph_t graph
)
2736 unsigned int size
= graph
->size
;
2740 changed
= BITMAP_ALLOC (NULL
);
2742 /* Mark all initial non-collapsed nodes as changed. */
2743 for (i
= 1; i
< size
; i
++)
2745 varinfo_t ivi
= get_varinfo (i
);
2746 if (find (i
) == i
&& !bitmap_empty_p (ivi
->solution
)
2747 && ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
2748 || graph
->complex[i
].length () > 0))
2749 bitmap_set_bit (changed
, i
);
2752 /* Allocate a bitmap to be used to store the changed bits. */
2753 pts
= BITMAP_ALLOC (&pta_obstack
);
2755 while (!bitmap_empty_p (changed
))
2760 bitmap_obstack_initialize (&iteration_obstack
);
2762 auto_vec
<unsigned> topo_order
= compute_topo_order (graph
);
2763 while (topo_order
.length () != 0)
2765 i
= topo_order
.pop ();
2767 /* If this variable is not a representative, skip it. */
2771 /* In certain indirect cycle cases, we may merge this
2772 variable to another. */
2773 if (eliminate_indirect_cycles (i
) && find (i
) != i
)
2776 /* If the node has changed, we need to process the
2777 complex constraints and outgoing edges again. For complex
2778 constraints that modify i itself, like the common group of
2779 callarg = callarg + UNKNOWN;
2780 callarg = *callarg + UNKNOWN;
2781 *callarg = callescape;
2782 make sure to iterate immediately because that maximizes
2783 cache reuse and expands the graph quickest, leading to
2784 better visitation order in the next iteration. */
2785 while (bitmap_clear_bit (changed
, i
))
2790 vec
<constraint_t
> complex = graph
->complex[i
];
2791 varinfo_t vi
= get_varinfo (i
);
2792 bool solution_empty
;
2794 /* Compute the changed set of solution bits. If anything
2795 is in the solution just propagate that. */
2796 if (bitmap_bit_p (vi
->solution
, anything_id
))
2798 /* If anything is also in the old solution there is
2800 ??? But we shouldn't ended up with "changed" set ... */
2802 && bitmap_bit_p (vi
->oldsolution
, anything_id
))
2804 bitmap_copy (pts
, get_varinfo (find (anything_id
))->solution
);
2806 else if (vi
->oldsolution
)
2807 bitmap_and_compl (pts
, vi
->solution
, vi
->oldsolution
);
2809 bitmap_copy (pts
, vi
->solution
);
2811 if (bitmap_empty_p (pts
))
2814 if (vi
->oldsolution
)
2815 bitmap_ior_into (vi
->oldsolution
, pts
);
2818 vi
->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
2819 bitmap_copy (vi
->oldsolution
, pts
);
2822 solution
= vi
->solution
;
2823 solution_empty
= bitmap_empty_p (solution
);
2825 /* Process the complex constraints */
2826 bitmap expanded_pts
= NULL
;
2827 FOR_EACH_VEC_ELT (complex, j
, c
)
2829 /* XXX: This is going to unsort the constraints in
2830 some cases, which will occasionally add duplicate
2831 constraints during unification. This does not
2832 affect correctness. */
2833 c
->lhs
.var
= find (c
->lhs
.var
);
2834 c
->rhs
.var
= find (c
->rhs
.var
);
2836 /* The only complex constraint that can change our
2837 solution to non-empty, given an empty solution,
2838 is a constraint where the lhs side is receiving
2839 some set from elsewhere. */
2840 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2841 do_complex_constraint (graph
, c
, pts
, &expanded_pts
);
2843 BITMAP_FREE (expanded_pts
);
2845 solution_empty
= bitmap_empty_p (solution
);
2847 if (!solution_empty
)
2850 unsigned eff_escaped_id
= find (escaped_id
);
2852 /* Propagate solution to all successors. */
2853 unsigned to_remove
= ~0U;
2854 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
2857 if (to_remove
!= ~0U)
2859 bitmap_clear_bit (graph
->succs
[i
], to_remove
);
2862 unsigned int to
= find (j
);
2865 /* Update the succ graph, avoiding duplicate
2868 if (! bitmap_set_bit (graph
->succs
[i
], to
))
2870 /* We eventually end up processing 'to' twice
2871 as it is undefined whether bitmap iteration
2872 iterates over bits set during iteration.
2873 Play safe instead of doing tricks. */
2875 /* Don't try to propagate to ourselves. */
2881 /* Early node unification can lead to edges from
2882 escaped - remove them. */
2883 if (i
== eff_escaped_id
)
2886 if (bitmap_set_bit (get_varinfo (to
)->solution
,
2888 bitmap_set_bit (changed
, to
);
2892 if (bitmap_ior_into (get_varinfo (to
)->solution
, pts
))
2893 bitmap_set_bit (changed
, to
);
2895 if (to_remove
!= ~0U)
2896 bitmap_clear_bit (graph
->succs
[i
], to_remove
);
2900 bitmap_obstack_release (&iteration_obstack
);
2904 BITMAP_FREE (changed
);
2905 bitmap_obstack_release (&oldpta_obstack
);
2908 /* Map from trees to variable infos. */
2909 static hash_map
<tree
, varinfo_t
> *vi_for_tree
;
2912 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2915 insert_vi_for_tree (tree t
, varinfo_t vi
)
2918 gcc_assert (!vi_for_tree
->put (t
, vi
));
2921 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2922 exist in the map, return NULL, otherwise, return the varinfo we found. */
2925 lookup_vi_for_tree (tree t
)
2927 varinfo_t
*slot
= vi_for_tree
->get (t
);
2934 /* Return a printable name for DECL */
2937 alias_get_name (tree decl
)
2939 const char *res
= "NULL";
2943 if (TREE_CODE (decl
) == SSA_NAME
)
2945 res
= get_name (decl
);
2946 temp
= xasprintf ("%s_%u", res
? res
: "", SSA_NAME_VERSION (decl
));
2948 else if (HAS_DECL_ASSEMBLER_NAME_P (decl
)
2949 && DECL_ASSEMBLER_NAME_SET_P (decl
))
2950 res
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME_RAW (decl
));
2951 else if (DECL_P (decl
))
2953 res
= get_name (decl
);
2955 temp
= xasprintf ("D.%u", DECL_UID (decl
));
2960 res
= ggc_strdup (temp
);
2968 /* Find the variable id for tree T in the map.
2969 If T doesn't exist in the map, create an entry for it and return it. */
2972 get_vi_for_tree (tree t
)
2974 varinfo_t
*slot
= vi_for_tree
->get (t
);
2977 unsigned int id
= create_variable_info_for (t
, alias_get_name (t
), false);
2978 return get_varinfo (id
);
2984 /* Get a scalar constraint expression for a new temporary variable. */
2986 static struct constraint_expr
2987 new_scalar_tmp_constraint_exp (const char *name
, bool add_id
)
2989 struct constraint_expr tmp
;
2992 vi
= new_var_info (NULL_TREE
, name
, add_id
);
2996 vi
->is_full_var
= 1;
3006 /* Get a constraint expression vector from an SSA_VAR_P node.
3007 If address_p is true, the result will be taken its address of. */
3010 get_constraint_for_ssa_var (tree t
, vec
<ce_s
> *results
, bool address_p
)
3012 struct constraint_expr cexpr
;
3015 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
3016 gcc_assert (TREE_CODE (t
) == SSA_NAME
|| DECL_P (t
));
3018 if (TREE_CODE (t
) == SSA_NAME
3019 && SSA_NAME_IS_DEFAULT_DEF (t
))
3021 /* For parameters, get at the points-to set for the actual parm
3023 if (TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
3024 || TREE_CODE (SSA_NAME_VAR (t
)) == RESULT_DECL
)
3026 get_constraint_for_ssa_var (SSA_NAME_VAR (t
), results
, address_p
);
3029 /* For undefined SSA names return nothing. */
3030 else if (!ssa_defined_default_def_p (t
))
3032 cexpr
.var
= nothing_id
;
3033 cexpr
.type
= SCALAR
;
3035 results
->safe_push (cexpr
);
3040 /* For global variables resort to the alias target. */
3041 if (VAR_P (t
) && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
3043 varpool_node
*node
= varpool_node::get (t
);
3044 if (node
&& node
->alias
&& node
->analyzed
)
3046 node
= node
->ultimate_alias_target ();
3047 /* Canonicalize the PT uid of all aliases to the ultimate target.
3048 ??? Hopefully the set of aliases can't change in a way that
3049 changes the ultimate alias target. */
3050 gcc_assert ((! DECL_PT_UID_SET_P (node
->decl
)
3051 || DECL_PT_UID (node
->decl
) == DECL_UID (node
->decl
))
3052 && (! DECL_PT_UID_SET_P (t
)
3053 || DECL_PT_UID (t
) == DECL_UID (node
->decl
)));
3054 DECL_PT_UID (t
) = DECL_UID (node
->decl
);
3058 /* If this is decl may bind to NULL note that. */
3060 && (! node
|| ! node
->nonzero_address ()))
3062 cexpr
.var
= nothing_id
;
3063 cexpr
.type
= SCALAR
;
3065 results
->safe_push (cexpr
);
3069 vi
= get_vi_for_tree (t
);
3071 cexpr
.type
= SCALAR
;
3074 /* If we are not taking the address of the constraint expr, add all
3075 sub-fiels of the variable as well. */
3077 && !vi
->is_full_var
)
3079 for (; vi
; vi
= vi_next (vi
))
3082 results
->safe_push (cexpr
);
3087 results
->safe_push (cexpr
);
3090 /* Process constraint T, performing various simplifications and then
3091 adding it to our list of overall constraints. */
3094 process_constraint (constraint_t t
)
3096 struct constraint_expr rhs
= t
->rhs
;
3097 struct constraint_expr lhs
= t
->lhs
;
3099 gcc_assert (rhs
.var
< varmap
.length ());
3100 gcc_assert (lhs
.var
< varmap
.length ());
3102 /* If we didn't get any useful constraint from the lhs we get
3103 &ANYTHING as fallback from get_constraint_for. Deal with
3104 it here by turning it into *ANYTHING. */
3105 if (lhs
.type
== ADDRESSOF
3106 && lhs
.var
== anything_id
)
3109 /* ADDRESSOF on the lhs is invalid. */
3110 gcc_assert (lhs
.type
!= ADDRESSOF
);
3112 /* We shouldn't add constraints from things that cannot have pointers.
3113 It's not completely trivial to avoid in the callers, so do it here. */
3114 if (rhs
.type
!= ADDRESSOF
3115 && !get_varinfo (rhs
.var
)->may_have_pointers
)
3118 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3119 if (!get_varinfo (lhs
.var
)->may_have_pointers
)
3122 /* This can happen in our IR with things like n->a = *p */
3123 if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
3125 /* Split into tmp = *rhs, *lhs = tmp */
3126 struct constraint_expr tmplhs
;
3127 tmplhs
= new_scalar_tmp_constraint_exp ("doubledereftmp", true);
3128 process_constraint (new_constraint (tmplhs
, rhs
));
3129 process_constraint (new_constraint (lhs
, tmplhs
));
3131 else if ((rhs
.type
!= SCALAR
|| rhs
.offset
!= 0) && lhs
.type
== DEREF
)
3133 /* Split into tmp = &rhs, *lhs = tmp */
3134 struct constraint_expr tmplhs
;
3135 tmplhs
= new_scalar_tmp_constraint_exp ("derefaddrtmp", true);
3136 process_constraint (new_constraint (tmplhs
, rhs
));
3137 process_constraint (new_constraint (lhs
, tmplhs
));
3141 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
3142 if (rhs
.type
== ADDRESSOF
)
3143 get_varinfo (get_varinfo (rhs
.var
)->head
)->address_taken
= true;
3144 constraints
.safe_push (t
);
3149 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3152 static HOST_WIDE_INT
3153 bitpos_of_field (const tree fdecl
)
3155 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl
))
3156 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl
)))
3159 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl
)) * BITS_PER_UNIT
3160 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl
)));
3164 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3165 resulting constraint expressions in *RESULTS. */
3168 get_constraint_for_ptr_offset (tree ptr
, tree offset
,
3171 struct constraint_expr c
;
3173 HOST_WIDE_INT rhsoffset
;
3175 /* If we do not do field-sensitive PTA adding offsets to pointers
3176 does not change the points-to solution. */
3177 if (!use_field_sensitive
)
3179 get_constraint_for_rhs (ptr
, results
);
3183 /* If the offset is not a non-negative integer constant that fits
3184 in a HOST_WIDE_INT, we have to fall back to a conservative
3185 solution which includes all sub-fields of all pointed-to
3186 variables of ptr. */
3187 if (offset
== NULL_TREE
3188 || TREE_CODE (offset
) != INTEGER_CST
)
3189 rhsoffset
= UNKNOWN_OFFSET
;
3192 /* Sign-extend the offset. */
3193 offset_int soffset
= offset_int::from (wi::to_wide (offset
), SIGNED
);
3194 if (!wi::fits_shwi_p (soffset
))
3195 rhsoffset
= UNKNOWN_OFFSET
;
3198 /* Make sure the bit-offset also fits. */
3199 HOST_WIDE_INT rhsunitoffset
= soffset
.to_shwi ();
3200 rhsoffset
= rhsunitoffset
* (unsigned HOST_WIDE_INT
) BITS_PER_UNIT
;
3201 if (rhsunitoffset
!= rhsoffset
/ BITS_PER_UNIT
)
3202 rhsoffset
= UNKNOWN_OFFSET
;
3206 get_constraint_for_rhs (ptr
, results
);
3210 /* As we are eventually appending to the solution do not use
3211 vec::iterate here. */
3212 n
= results
->length ();
3213 for (j
= 0; j
< n
; j
++)
3217 curr
= get_varinfo (c
.var
);
3219 if (c
.type
== ADDRESSOF
3220 /* If this varinfo represents a full variable just use it. */
3221 && curr
->is_full_var
)
3223 else if (c
.type
== ADDRESSOF
3224 /* If we do not know the offset add all subfields. */
3225 && rhsoffset
== UNKNOWN_OFFSET
)
3227 varinfo_t temp
= get_varinfo (curr
->head
);
3230 struct constraint_expr c2
;
3232 c2
.type
= ADDRESSOF
;
3234 if (c2
.var
!= c
.var
)
3235 results
->safe_push (c2
);
3236 temp
= vi_next (temp
);
3240 else if (c
.type
== ADDRESSOF
)
3243 unsigned HOST_WIDE_INT offset
= curr
->offset
+ rhsoffset
;
3245 /* If curr->offset + rhsoffset is less than zero adjust it. */
3247 && curr
->offset
< offset
)
3250 /* We have to include all fields that overlap the current
3251 field shifted by rhsoffset. And we include at least
3252 the last or the first field of the variable to represent
3253 reachability of off-bound addresses, in particular &object + 1,
3254 conservatively correct. */
3255 temp
= first_or_preceding_vi_for_offset (curr
, offset
);
3258 temp
= vi_next (temp
);
3260 && temp
->offset
< offset
+ curr
->size
)
3262 struct constraint_expr c2
;
3264 c2
.type
= ADDRESSOF
;
3266 results
->safe_push (c2
);
3267 temp
= vi_next (temp
);
3270 else if (c
.type
== SCALAR
)
3272 gcc_assert (c
.offset
== 0);
3273 c
.offset
= rhsoffset
;
3276 /* We shouldn't get any DEREFs here. */
3284 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3285 If address_p is true the result will be taken its address of.
3286 If lhs_p is true then the constraint expression is assumed to be used
3290 get_constraint_for_component_ref (tree t
, vec
<ce_s
> *results
,
3291 bool address_p
, bool lhs_p
)
3294 poly_int64 bitsize
= -1;
3295 poly_int64 bitmaxsize
= -1;
3300 /* Some people like to do cute things like take the address of
3303 while (handled_component_p (forzero
)
3304 || INDIRECT_REF_P (forzero
)
3305 || TREE_CODE (forzero
) == MEM_REF
)
3306 forzero
= TREE_OPERAND (forzero
, 0);
3308 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
3310 struct constraint_expr temp
;
3313 temp
.var
= integer_id
;
3315 results
->safe_push (temp
);
3319 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
, &reverse
);
3321 /* We can end up here for component references on a
3322 VIEW_CONVERT_EXPR <>(&foobar) or things like a
3323 BIT_FIELD_REF <&MEM[(void *)&b + 4B], ...>. So for
3324 symbolic constants simply give up. */
3325 if (TREE_CODE (t
) == ADDR_EXPR
)
3327 constraint_expr result
;
3328 result
.type
= SCALAR
;
3329 result
.var
= anything_id
;
3331 results
->safe_push (result
);
3335 /* Avoid creating pointer-offset constraints, so handle MEM_REF
3336 offsets directly. Pretend to take the address of the base,
3337 we'll take care of adding the required subset of sub-fields below. */
3338 if (TREE_CODE (t
) == MEM_REF
3339 && !integer_zerop (TREE_OPERAND (t
, 0)))
3341 poly_offset_int off
= mem_ref_offset (t
);
3342 off
<<= LOG2_BITS_PER_UNIT
;
3345 if (off
.to_shwi (&off_hwi
))
3352 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, false, lhs_p
);
3356 get_constraint_for_1 (t
, results
, true, lhs_p
);
3358 /* Strip off nothing_id. */
3359 if (results
->length () == 2)
3361 gcc_assert ((*results
)[0].var
== nothing_id
);
3362 results
->unordered_remove (0);
3364 gcc_assert (results
->length () == 1);
3365 struct constraint_expr
&result
= results
->last ();
3367 if (result
.type
== SCALAR
3368 && get_varinfo (result
.var
)->is_full_var
)
3369 /* For single-field vars do not bother about the offset. */
3371 else if (result
.type
== SCALAR
)
3373 /* In languages like C, you can access one past the end of an
3374 array. You aren't allowed to dereference it, so we can
3375 ignore this constraint. When we handle pointer subtraction,
3376 we may have to do something cute here. */
3378 if (maybe_lt (poly_uint64 (bitpos
), get_varinfo (result
.var
)->fullsize
)
3379 && maybe_ne (bitmaxsize
, 0))
3381 /* It's also not true that the constraint will actually start at the
3382 right offset, it may start in some padding. We only care about
3383 setting the constraint to the first actual field it touches, so
3385 struct constraint_expr cexpr
= result
;
3389 for (curr
= get_varinfo (cexpr
.var
); curr
; curr
= vi_next (curr
))
3391 if (ranges_maybe_overlap_p (poly_int64 (curr
->offset
),
3392 curr
->size
, bitpos
, bitmaxsize
))
3394 cexpr
.var
= curr
->id
;
3395 results
->safe_push (cexpr
);
3400 /* If we are going to take the address of this field then
3401 to be able to compute reachability correctly add at least
3402 the last field of the variable. */
3403 if (address_p
&& results
->length () == 0)
3405 curr
= get_varinfo (cexpr
.var
);
3406 while (curr
->next
!= 0)
3407 curr
= vi_next (curr
);
3408 cexpr
.var
= curr
->id
;
3409 results
->safe_push (cexpr
);
3411 else if (results
->length () == 0)
3412 /* Assert that we found *some* field there. The user couldn't be
3413 accessing *only* padding. */
3414 /* Still the user could access one past the end of an array
3415 embedded in a struct resulting in accessing *only* padding. */
3416 /* Or accessing only padding via type-punning to a type
3417 that has a filed just in padding space. */
3419 cexpr
.type
= SCALAR
;
3420 cexpr
.var
= anything_id
;
3422 results
->safe_push (cexpr
);
3425 else if (known_eq (bitmaxsize
, 0))
3427 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3428 fprintf (dump_file
, "Access to zero-sized part of variable, "
3432 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3433 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
3435 else if (result
.type
== DEREF
)
3437 /* If we do not know exactly where the access goes say so. Note
3438 that only for non-structure accesses we know that we access
3439 at most one subfiled of any variable. */
3440 HOST_WIDE_INT const_bitpos
;
3441 if (!bitpos
.is_constant (&const_bitpos
)
3442 || const_bitpos
== -1
3443 || maybe_ne (bitsize
, bitmaxsize
)
3444 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t
))
3445 || result
.offset
== UNKNOWN_OFFSET
)
3446 result
.offset
= UNKNOWN_OFFSET
;
3448 result
.offset
+= const_bitpos
;
3450 else if (result
.type
== ADDRESSOF
)
3452 /* We can end up here for component references on constants like
3453 VIEW_CONVERT_EXPR <>({ 0, 1, 2, 3 })[i]. */
3454 result
.type
= SCALAR
;
3455 result
.var
= anything_id
;
3463 /* Dereference the constraint expression CONS, and return the result.
3464 DEREF (ADDRESSOF) = SCALAR
3465 DEREF (SCALAR) = DEREF
3466 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3467 This is needed so that we can handle dereferencing DEREF constraints. */
3470 do_deref (vec
<ce_s
> *constraints
)
3472 struct constraint_expr
*c
;
3475 FOR_EACH_VEC_ELT (*constraints
, i
, c
)
3477 if (c
->type
== SCALAR
)
3479 else if (c
->type
== ADDRESSOF
)
3481 else if (c
->type
== DEREF
)
3483 struct constraint_expr tmplhs
;
3484 tmplhs
= new_scalar_tmp_constraint_exp ("dereftmp", true);
3485 process_constraint (new_constraint (tmplhs
, *c
));
3486 c
->var
= tmplhs
.var
;
3493 /* Given a tree T, return the constraint expression for taking the
3497 get_constraint_for_address_of (tree t
, vec
<ce_s
> *results
)
3499 struct constraint_expr
*c
;
3502 get_constraint_for_1 (t
, results
, true, true);
3504 FOR_EACH_VEC_ELT (*results
, i
, c
)
3506 if (c
->type
== DEREF
)
3509 c
->type
= ADDRESSOF
;
3513 /* Given a tree T, return the constraint expression for it. */
3516 get_constraint_for_1 (tree t
, vec
<ce_s
> *results
, bool address_p
,
3519 struct constraint_expr temp
;
3521 /* x = integer is all glommed to a single variable, which doesn't
3522 point to anything by itself. That is, of course, unless it is an
3523 integer constant being treated as a pointer, in which case, we
3524 will return that this is really the addressof anything. This
3525 happens below, since it will fall into the default case. The only
3526 case we know something about an integer treated like a pointer is
3527 when it is the NULL pointer, and then we just say it points to
3530 Do not do that if -fno-delete-null-pointer-checks though, because
3531 in that case *NULL does not fail, so it _should_ alias *anything.
3532 It is not worth adding a new option or renaming the existing one,
3533 since this case is relatively obscure. */
3534 if ((TREE_CODE (t
) == INTEGER_CST
3535 && integer_zerop (t
))
3536 /* The only valid CONSTRUCTORs in gimple with pointer typed
3537 elements are zero-initializer. But in IPA mode we also
3538 process global initializers, so verify at least. */
3539 || (TREE_CODE (t
) == CONSTRUCTOR
3540 && CONSTRUCTOR_NELTS (t
) == 0))
3542 if (flag_delete_null_pointer_checks
)
3543 temp
.var
= nothing_id
;
3545 temp
.var
= nonlocal_id
;
3546 temp
.type
= ADDRESSOF
;
3548 results
->safe_push (temp
);
3552 /* String constants are read-only, ideally we'd have a CONST_DECL
3554 if (TREE_CODE (t
) == STRING_CST
)
3556 temp
.var
= string_id
;
3559 results
->safe_push (temp
);
3563 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
3565 case tcc_expression
:
3567 switch (TREE_CODE (t
))
3570 get_constraint_for_address_of (TREE_OPERAND (t
, 0), results
);
3578 switch (TREE_CODE (t
))
3582 struct constraint_expr cs
;
3584 get_constraint_for_ptr_offset (TREE_OPERAND (t
, 0),
3585 TREE_OPERAND (t
, 1), results
);
3588 /* If we are not taking the address then make sure to process
3589 all subvariables we might access. */
3593 cs
= results
->last ();
3594 if (cs
.type
== DEREF
3595 && type_can_have_subvars (TREE_TYPE (t
)))
3597 /* For dereferences this means we have to defer it
3599 results
->last ().offset
= UNKNOWN_OFFSET
;
3602 if (cs
.type
!= SCALAR
)
3605 vi
= get_varinfo (cs
.var
);
3606 curr
= vi_next (vi
);
3607 if (!vi
->is_full_var
3610 unsigned HOST_WIDE_INT size
;
3611 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t
))))
3612 size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t
)));
3615 for (; curr
; curr
= vi_next (curr
))
3617 if (curr
->offset
- vi
->offset
< size
)
3620 results
->safe_push (cs
);
3629 case ARRAY_RANGE_REF
:
3634 get_constraint_for_component_ref (t
, results
, address_p
, lhs_p
);
3636 case VIEW_CONVERT_EXPR
:
3637 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, address_p
,
3640 /* We are missing handling for TARGET_MEM_REF here. */
3645 case tcc_exceptional
:
3647 switch (TREE_CODE (t
))
3651 get_constraint_for_ssa_var (t
, results
, address_p
);
3659 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t
), i
, val
)
3661 struct constraint_expr
*rhsp
;
3663 get_constraint_for_1 (val
, &tmp
, address_p
, lhs_p
);
3664 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
3665 results
->safe_push (*rhsp
);
3668 /* We do not know whether the constructor was complete,
3669 so technically we have to add &NOTHING or &ANYTHING
3670 like we do for an empty constructor as well. */
3677 case tcc_declaration
:
3679 get_constraint_for_ssa_var (t
, results
, address_p
);
3684 /* We cannot refer to automatic variables through constants. */
3685 temp
.type
= ADDRESSOF
;
3686 temp
.var
= nonlocal_id
;
3688 results
->safe_push (temp
);
3694 /* The default fallback is a constraint from anything. */
3695 temp
.type
= ADDRESSOF
;
3696 temp
.var
= anything_id
;
3698 results
->safe_push (temp
);
3701 /* Given a gimple tree T, return the constraint expression vector for it. */
3704 get_constraint_for (tree t
, vec
<ce_s
> *results
)
3706 gcc_assert (results
->length () == 0);
3708 get_constraint_for_1 (t
, results
, false, true);
3711 /* Given a gimple tree T, return the constraint expression vector for it
3712 to be used as the rhs of a constraint. */
3715 get_constraint_for_rhs (tree t
, vec
<ce_s
> *results
)
3717 gcc_assert (results
->length () == 0);
3719 get_constraint_for_1 (t
, results
, false, false);
3723 /* Efficiently generates constraints from all entries in *RHSC to all
3724 entries in *LHSC. */
3727 process_all_all_constraints (const vec
<ce_s
> &lhsc
,
3728 const vec
<ce_s
> &rhsc
)
3730 struct constraint_expr
*lhsp
, *rhsp
;
3733 if (lhsc
.length () <= 1 || rhsc
.length () <= 1)
3735 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3736 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
3737 process_constraint (new_constraint (*lhsp
, *rhsp
));
3741 struct constraint_expr tmp
;
3742 tmp
= new_scalar_tmp_constraint_exp ("allalltmp", true);
3743 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
3744 process_constraint (new_constraint (tmp
, *rhsp
));
3745 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3746 process_constraint (new_constraint (*lhsp
, tmp
));
3750 /* Handle aggregate copies by expanding into copies of the respective
3751 fields of the structures. */
3754 do_structure_copy (tree lhsop
, tree rhsop
)
3756 struct constraint_expr
*lhsp
, *rhsp
;
3757 auto_vec
<ce_s
> lhsc
;
3758 auto_vec
<ce_s
> rhsc
;
3761 get_constraint_for (lhsop
, &lhsc
);
3762 get_constraint_for_rhs (rhsop
, &rhsc
);
3765 if (lhsp
->type
== DEREF
3766 || (lhsp
->type
== ADDRESSOF
&& lhsp
->var
== anything_id
)
3767 || rhsp
->type
== DEREF
)
3769 if (lhsp
->type
== DEREF
)
3771 gcc_assert (lhsc
.length () == 1);
3772 lhsp
->offset
= UNKNOWN_OFFSET
;
3774 if (rhsp
->type
== DEREF
)
3776 gcc_assert (rhsc
.length () == 1);
3777 rhsp
->offset
= UNKNOWN_OFFSET
;
3779 process_all_all_constraints (lhsc
, rhsc
);
3781 else if (lhsp
->type
== SCALAR
3782 && (rhsp
->type
== SCALAR
3783 || rhsp
->type
== ADDRESSOF
))
3785 HOST_WIDE_INT lhssize
, lhsoffset
;
3786 HOST_WIDE_INT rhssize
, rhsoffset
;
3789 if (!get_ref_base_and_extent_hwi (lhsop
, &lhsoffset
, &lhssize
, &reverse
)
3790 || !get_ref_base_and_extent_hwi (rhsop
, &rhsoffset
, &rhssize
,
3793 process_all_all_constraints (lhsc
, rhsc
);
3796 for (j
= 0; lhsc
.iterate (j
, &lhsp
);)
3798 varinfo_t lhsv
, rhsv
;
3800 lhsv
= get_varinfo (lhsp
->var
);
3801 rhsv
= get_varinfo (rhsp
->var
);
3802 if (lhsv
->may_have_pointers
3803 && (lhsv
->is_full_var
3804 || rhsv
->is_full_var
3805 || ranges_overlap_p (lhsv
->offset
+ rhsoffset
, lhsv
->size
,
3806 rhsv
->offset
+ lhsoffset
, rhsv
->size
)))
3807 process_constraint (new_constraint (*lhsp
, *rhsp
));
3808 if (!rhsv
->is_full_var
3809 && (lhsv
->is_full_var
3810 || (lhsv
->offset
+ rhsoffset
+ lhsv
->size
3811 > rhsv
->offset
+ lhsoffset
+ rhsv
->size
)))
3814 if (k
>= rhsc
.length ())
3825 /* Create constraints ID = { rhsc }. */
3828 make_constraints_to (unsigned id
, const vec
<ce_s
> &rhsc
)
3830 struct constraint_expr
*c
;
3831 struct constraint_expr includes
;
3835 includes
.offset
= 0;
3836 includes
.type
= SCALAR
;
3838 FOR_EACH_VEC_ELT (rhsc
, j
, c
)
3839 process_constraint (new_constraint (includes
, *c
));
3842 /* Create a constraint ID = OP. */
3845 make_constraint_to (unsigned id
, tree op
)
3847 auto_vec
<ce_s
> rhsc
;
3848 get_constraint_for_rhs (op
, &rhsc
);
3849 make_constraints_to (id
, rhsc
);
3852 /* Create a constraint ID = &FROM. */
3855 make_constraint_from (varinfo_t vi
, int from
)
3857 struct constraint_expr lhs
, rhs
;
3865 rhs
.type
= ADDRESSOF
;
3866 process_constraint (new_constraint (lhs
, rhs
));
3869 /* Create a constraint ID = FROM. */
3872 make_copy_constraint (varinfo_t vi
, int from
)
3874 struct constraint_expr lhs
, rhs
;
3883 process_constraint (new_constraint (lhs
, rhs
));
3886 /* Make constraints necessary to make OP escape. */
3889 make_escape_constraint (tree op
)
3891 make_constraint_to (escaped_id
, op
);
3894 /* Make constraint necessary to make all indirect references
3898 make_indirect_escape_constraint (varinfo_t vi
)
3900 struct constraint_expr lhs
, rhs
;
3901 /* escaped = *(VAR + UNKNOWN); */
3903 lhs
.var
= escaped_id
;
3907 rhs
.offset
= UNKNOWN_OFFSET
;
3908 process_constraint (new_constraint (lhs
, rhs
));
3911 /* Add constraints to that the solution of VI is transitively closed. */
3914 make_transitive_closure_constraints (varinfo_t vi
)
3916 struct constraint_expr lhs
, rhs
;
3918 /* VAR = *(VAR + UNKNOWN); */
3924 rhs
.offset
= UNKNOWN_OFFSET
;
3925 process_constraint (new_constraint (lhs
, rhs
));
3928 /* Add constraints to that the solution of VI has all subvariables added. */
3931 make_any_offset_constraints (varinfo_t vi
)
3933 struct constraint_expr lhs
, rhs
;
3935 /* VAR = VAR + UNKNOWN; */
3941 rhs
.offset
= UNKNOWN_OFFSET
;
3942 process_constraint (new_constraint (lhs
, rhs
));
3945 /* Temporary storage for fake var decls. */
3946 struct obstack fake_var_decl_obstack
;
3948 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3951 build_fake_var_decl (tree type
)
3953 tree decl
= (tree
) XOBNEW (&fake_var_decl_obstack
, struct tree_var_decl
);
3954 memset (decl
, 0, sizeof (struct tree_var_decl
));
3955 TREE_SET_CODE (decl
, VAR_DECL
);
3956 TREE_TYPE (decl
) = type
;
3957 DECL_UID (decl
) = allocate_decl_uid ();
3958 SET_DECL_PT_UID (decl
, -1);
3959 layout_decl (decl
, 0);
3963 /* Create a new artificial heap variable with NAME.
3964 Return the created variable. */
3967 make_heapvar (const char *name
, bool add_id
)
3972 heapvar
= build_fake_var_decl (ptr_type_node
);
3973 DECL_EXTERNAL (heapvar
) = 1;
3975 vi
= new_var_info (heapvar
, name
, add_id
);
3976 vi
->is_heap_var
= true;
3977 vi
->is_unknown_size_var
= true;
3981 vi
->is_full_var
= true;
3982 insert_vi_for_tree (heapvar
, vi
);
3987 /* Create a new artificial heap variable with NAME and make a
3988 constraint from it to LHS. Set flags according to a tag used
3989 for tracking restrict pointers. */
3992 make_constraint_from_restrict (varinfo_t lhs
, const char *name
, bool add_id
)
3994 varinfo_t vi
= make_heapvar (name
, add_id
);
3995 vi
->is_restrict_var
= 1;
3996 vi
->is_global_var
= 1;
3997 vi
->may_have_pointers
= 1;
3998 make_constraint_from (lhs
, vi
->id
);
4002 /* Create a new artificial heap variable with NAME and make a
4003 constraint from it to LHS. Set flags according to a tag used
4004 for tracking restrict pointers and make the artificial heap
4005 point to global memory. */
4008 make_constraint_from_global_restrict (varinfo_t lhs
, const char *name
,
4011 varinfo_t vi
= make_constraint_from_restrict (lhs
, name
, add_id
);
4012 make_copy_constraint (vi
, nonlocal_id
);
4016 /* In IPA mode there are varinfos for different aspects of reach
4017 function designator. One for the points-to set of the return
4018 value, one for the variables that are clobbered by the function,
4019 one for its uses and one for each parameter (including a single
4020 glob for remaining variadic arguments). */
4022 enum { fi_clobbers
= 1, fi_uses
= 2,
4023 fi_static_chain
= 3, fi_result
= 4, fi_parm_base
= 5 };
4025 /* Get a constraint for the requested part of a function designator FI
4026 when operating in IPA mode. */
4028 static struct constraint_expr
4029 get_function_part_constraint (varinfo_t fi
, unsigned part
)
4031 struct constraint_expr c
;
4033 gcc_assert (in_ipa_mode
);
4035 if (fi
->id
== anything_id
)
4037 /* ??? We probably should have a ANYFN special variable. */
4038 c
.var
= anything_id
;
4042 else if (fi
->decl
&& TREE_CODE (fi
->decl
) == FUNCTION_DECL
)
4044 varinfo_t ai
= first_vi_for_offset (fi
, part
);
4048 c
.var
= anything_id
;
4062 /* Produce constraints for argument ARG of call STMT with eaf flags
4063 FLAGS. RESULTS is array holding constraints for return value.
4064 CALLESCAPE_ID is variable where call loocal escapes are added.
4065 WRITES_GLOVEL_MEMORY is true if callee may write global memory. */
4068 handle_call_arg (gcall
*stmt
, tree arg
, vec
<ce_s
> *results
, int flags
,
4069 int callescape_id
, bool writes_global_memory
)
4071 int relevant_indirect_flags
= EAF_NO_INDIRECT_CLOBBER
| EAF_NO_INDIRECT_READ
4072 | EAF_NO_INDIRECT_ESCAPE
;
4073 int relevant_flags
= relevant_indirect_flags
4074 | EAF_NO_DIRECT_CLOBBER
4075 | EAF_NO_DIRECT_READ
4076 | EAF_NO_DIRECT_ESCAPE
;
4077 if (gimple_call_lhs (stmt
))
4079 relevant_flags
|= EAF_NOT_RETURNED_DIRECTLY
| EAF_NOT_RETURNED_INDIRECTLY
;
4080 relevant_indirect_flags
|= EAF_NOT_RETURNED_INDIRECTLY
;
4082 /* If value is never read from it can not be returned indirectly
4083 (except through the escape solution).
4084 For all flags we get these implications right except for
4085 not_returned because we miss return functions in ipa-prop. */
4087 if (flags
& EAF_NO_DIRECT_READ
)
4088 flags
|= EAF_NOT_RETURNED_INDIRECTLY
;
4091 /* If the argument is not used we can ignore it.
4092 Similarly argument is invisile for us if it not clobbered, does not
4093 escape, is not read and can not be returned. */
4094 if ((flags
& EAF_UNUSED
) || ((flags
& relevant_flags
) == relevant_flags
))
4097 /* Produce varinfo for direct accesses to ARG. */
4098 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg", true);
4099 tem
->is_reg_var
= true;
4100 make_constraint_to (tem
->id
, arg
);
4101 make_any_offset_constraints (tem
);
4103 bool callarg_transitive
= false;
4105 /* As an compile time optimization if we make no difference between
4106 direct and indirect accesses make arg transitively closed.
4107 This avoids the need to build indir arg and do everything twice. */
4108 if (((flags
& EAF_NO_INDIRECT_CLOBBER
) != 0)
4109 == ((flags
& EAF_NO_DIRECT_CLOBBER
) != 0)
4110 && (((flags
& EAF_NO_INDIRECT_READ
) != 0)
4111 == ((flags
& EAF_NO_DIRECT_READ
) != 0))
4112 && (((flags
& EAF_NO_INDIRECT_ESCAPE
) != 0)
4113 == ((flags
& EAF_NO_DIRECT_ESCAPE
) != 0))
4114 && (((flags
& EAF_NOT_RETURNED_INDIRECTLY
) != 0)
4115 == ((flags
& EAF_NOT_RETURNED_DIRECTLY
) != 0)))
4117 make_transitive_closure_constraints (tem
);
4118 callarg_transitive
= true;
4119 gcc_checking_assert (!(flags
& EAF_NO_DIRECT_READ
));
4122 /* If necessary, produce varinfo for indirect accesses to ARG. */
4123 varinfo_t indir_tem
= NULL
;
4124 if (!callarg_transitive
4125 && (flags
& relevant_indirect_flags
) != relevant_indirect_flags
)
4127 struct constraint_expr lhs
, rhs
;
4128 indir_tem
= new_var_info (NULL_TREE
, "indircallarg", true);
4129 indir_tem
->is_reg_var
= true;
4131 /* indir_term = *tem. */
4133 lhs
.var
= indir_tem
->id
;
4138 rhs
.offset
= UNKNOWN_OFFSET
;
4139 process_constraint (new_constraint (lhs
, rhs
));
4141 make_any_offset_constraints (indir_tem
);
4143 /* If we do not read indirectly there is no need for transitive closure.
4144 We know there is only one level of indirection. */
4145 if (!(flags
& EAF_NO_INDIRECT_READ
))
4146 make_transitive_closure_constraints (indir_tem
);
4147 gcc_checking_assert (!(flags
& EAF_NO_DIRECT_READ
));
4150 if (gimple_call_lhs (stmt
))
4152 if (!(flags
& EAF_NOT_RETURNED_DIRECTLY
))
4154 struct constraint_expr cexpr
;
4155 cexpr
.var
= tem
->id
;
4156 cexpr
.type
= SCALAR
;
4158 results
->safe_push (cexpr
);
4160 if (!callarg_transitive
& !(flags
& EAF_NOT_RETURNED_INDIRECTLY
))
4162 struct constraint_expr cexpr
;
4163 cexpr
.var
= indir_tem
->id
;
4164 cexpr
.type
= SCALAR
;
4166 results
->safe_push (cexpr
);
4170 if (!(flags
& EAF_NO_DIRECT_READ
))
4172 varinfo_t uses
= get_call_use_vi (stmt
);
4173 make_copy_constraint (uses
, tem
->id
);
4174 if (!callarg_transitive
& !(flags
& EAF_NO_INDIRECT_READ
))
4175 make_copy_constraint (uses
, indir_tem
->id
);
4178 /* To read indirectly we need to read directly. */
4179 gcc_checking_assert (flags
& EAF_NO_INDIRECT_READ
);
4181 if (!(flags
& EAF_NO_DIRECT_CLOBBER
))
4183 struct constraint_expr lhs
, rhs
;
4185 /* *arg = callescape. */
4191 rhs
.var
= callescape_id
;
4193 process_constraint (new_constraint (lhs
, rhs
));
4195 /* callclobbered = arg. */
4196 make_copy_constraint (get_call_clobber_vi (stmt
), tem
->id
);
4198 if (!callarg_transitive
& !(flags
& EAF_NO_INDIRECT_CLOBBER
))
4200 struct constraint_expr lhs
, rhs
;
4202 /* *indir_arg = callescape. */
4204 lhs
.var
= indir_tem
->id
;
4208 rhs
.var
= callescape_id
;
4210 process_constraint (new_constraint (lhs
, rhs
));
4212 /* callclobbered = indir_arg. */
4213 make_copy_constraint (get_call_clobber_vi (stmt
), indir_tem
->id
);
4216 if (!(flags
& (EAF_NO_DIRECT_ESCAPE
| EAF_NO_INDIRECT_ESCAPE
)))
4218 struct constraint_expr lhs
, rhs
;
4220 /* callescape = arg; */
4221 lhs
.var
= callescape_id
;
4228 process_constraint (new_constraint (lhs
, rhs
));
4230 if (writes_global_memory
)
4231 make_escape_constraint (arg
);
4233 else if (!callarg_transitive
& !(flags
& EAF_NO_INDIRECT_ESCAPE
))
4235 struct constraint_expr lhs
, rhs
;
4237 /* callescape = *(indir_arg + UNKNOWN); */
4238 lhs
.var
= callescape_id
;
4242 rhs
.var
= indir_tem
->id
;
4245 process_constraint (new_constraint (lhs
, rhs
));
4247 if (writes_global_memory
)
4248 make_indirect_escape_constraint (tem
);
4252 /* Determine global memory access of call STMT and update
4253 WRITES_GLOBAL_MEMORY, READS_GLOBAL_MEMORY and USES_GLOBAL_MEMORY. */
4256 determine_global_memory_access (gcall
*stmt
,
4257 bool *writes_global_memory
,
4258 bool *reads_global_memory
,
4259 bool *uses_global_memory
)
4263 modref_summary
*summary
;
4265 /* We need to detrmine reads to set uses. */
4266 gcc_assert (!uses_global_memory
|| reads_global_memory
);
4268 if ((callee
= gimple_call_fndecl (stmt
)) != NULL_TREE
4269 && (node
= cgraph_node::get (callee
)) != NULL
4270 && (summary
= get_modref_function_summary (node
)))
4272 if (writes_global_memory
&& *writes_global_memory
)
4273 *writes_global_memory
= summary
->global_memory_written
;
4274 if (reads_global_memory
&& *reads_global_memory
)
4275 *reads_global_memory
= summary
->global_memory_read
;
4276 if (reads_global_memory
&& uses_global_memory
4277 && !summary
->calls_interposable
4278 && !*reads_global_memory
&& node
->binds_to_current_def_p ())
4279 *uses_global_memory
= false;
4281 if ((writes_global_memory
&& *writes_global_memory
)
4282 || (uses_global_memory
&& *uses_global_memory
)
4283 || (reads_global_memory
&& *reads_global_memory
))
4285 attr_fnspec fnspec
= gimple_call_fnspec (stmt
);
4286 if (fnspec
.known_p ())
4288 if (writes_global_memory
4289 && !fnspec
.global_memory_written_p ())
4290 *writes_global_memory
= false;
4291 if (reads_global_memory
&& !fnspec
.global_memory_read_p ())
4293 *reads_global_memory
= false;
4294 if (uses_global_memory
)
4295 *uses_global_memory
= false;
4301 /* For non-IPA mode, generate constraints necessary for a call on the
4302 RHS and collect return value constraint to RESULTS to be used later in
4305 IMPLICIT_EAF_FLAGS are added to each function argument. If
4306 WRITES_GLOBAL_MEMORY is true function is assumed to possibly write to global
4307 memory. Similar for READS_GLOBAL_MEMORY. */
4310 handle_rhs_call (gcall
*stmt
, vec
<ce_s
> *results
,
4311 int implicit_eaf_flags
,
4312 bool writes_global_memory
,
4313 bool reads_global_memory
)
4315 determine_global_memory_access (stmt
, &writes_global_memory
,
4316 &reads_global_memory
,
4319 varinfo_t callescape
= new_var_info (NULL_TREE
, "callescape", true);
4321 /* If function can use global memory, add it to callescape
4322 and to possible return values. If not we can still use/return addresses
4323 of global symbols. */
4324 struct constraint_expr lhs
, rhs
;
4327 lhs
.var
= callescape
->id
;
4330 rhs
.type
= reads_global_memory
? SCALAR
: ADDRESSOF
;
4331 rhs
.var
= nonlocal_id
;
4334 process_constraint (new_constraint (lhs
, rhs
));
4335 results
->safe_push (rhs
);
4337 varinfo_t uses
= get_call_use_vi (stmt
);
4338 make_copy_constraint (uses
, callescape
->id
);
4340 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
4342 tree arg
= gimple_call_arg (stmt
, i
);
4343 int flags
= gimple_call_arg_flags (stmt
, i
);
4344 handle_call_arg (stmt
, arg
, results
,
4345 flags
| implicit_eaf_flags
,
4346 callescape
->id
, writes_global_memory
);
4349 /* The static chain escapes as well. */
4350 if (gimple_call_chain (stmt
))
4351 handle_call_arg (stmt
, gimple_call_chain (stmt
), results
,
4353 | gimple_call_static_chain_flags (stmt
),
4354 callescape
->id
, writes_global_memory
);
4356 /* And if we applied NRV the address of the return slot escapes as well. */
4357 if (gimple_call_return_slot_opt_p (stmt
)
4358 && gimple_call_lhs (stmt
) != NULL_TREE
4359 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
4361 int flags
= gimple_call_retslot_flags (stmt
);
4362 const int relevant_flags
= EAF_NO_DIRECT_ESCAPE
4363 | EAF_NOT_RETURNED_DIRECTLY
;
4365 if (!(flags
& EAF_UNUSED
) && (flags
& relevant_flags
) != relevant_flags
)
4367 auto_vec
<ce_s
> tmpc
;
4369 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
4371 if (!(flags
& EAF_NO_DIRECT_ESCAPE
))
4373 make_constraints_to (callescape
->id
, tmpc
);
4374 if (writes_global_memory
)
4375 make_constraints_to (escaped_id
, tmpc
);
4377 if (!(flags
& EAF_NOT_RETURNED_DIRECTLY
))
4379 struct constraint_expr
*c
;
4381 FOR_EACH_VEC_ELT (tmpc
, i
, c
)
4382 results
->safe_push (*c
);
4388 /* For non-IPA mode, generate constraints necessary for a call
4389 that returns a pointer and assigns it to LHS. This simply makes
4390 the LHS point to global and escaped variables. */
4393 handle_lhs_call (gcall
*stmt
, tree lhs
, int flags
, vec
<ce_s
> &rhsc
,
4396 auto_vec
<ce_s
> lhsc
;
4398 get_constraint_for (lhs
, &lhsc
);
4399 /* If the store is to a global decl make sure to
4400 add proper escape constraints. */
4401 lhs
= get_base_address (lhs
);
4404 && is_global_var (lhs
))
4406 struct constraint_expr tmpc
;
4407 tmpc
.var
= escaped_id
;
4410 lhsc
.safe_push (tmpc
);
4413 /* If the call returns an argument unmodified override the rhs
4415 if (flags
& ERF_RETURNS_ARG
4416 && (flags
& ERF_RETURN_ARG_MASK
) < gimple_call_num_args (stmt
))
4420 arg
= gimple_call_arg (stmt
, flags
& ERF_RETURN_ARG_MASK
);
4421 get_constraint_for (arg
, &rhsc
);
4422 process_all_all_constraints (lhsc
, rhsc
);
4425 else if (flags
& ERF_NOALIAS
)
4428 struct constraint_expr tmpc
;
4430 vi
= make_heapvar ("HEAP", true);
4431 /* We are marking allocated storage local, we deal with it becoming
4432 global by escaping and setting of vars_contains_escaped_heap. */
4433 DECL_EXTERNAL (vi
->decl
) = 0;
4434 vi
->is_global_var
= 0;
4435 /* If this is not a real malloc call assume the memory was
4436 initialized and thus may point to global memory. All
4437 builtin functions with the malloc attribute behave in a sane way. */
4439 || !fndecl_built_in_p (fndecl
, BUILT_IN_NORMAL
))
4440 make_constraint_from (vi
, nonlocal_id
);
4443 tmpc
.type
= ADDRESSOF
;
4444 rhsc
.safe_push (tmpc
);
4445 process_all_all_constraints (lhsc
, rhsc
);
4449 process_all_all_constraints (lhsc
, rhsc
);
4453 /* Return the varinfo for the callee of CALL. */
4456 get_fi_for_callee (gcall
*call
)
4458 tree decl
, fn
= gimple_call_fn (call
);
4460 if (fn
&& TREE_CODE (fn
) == OBJ_TYPE_REF
)
4461 fn
= OBJ_TYPE_REF_EXPR (fn
);
4463 /* If we can directly resolve the function being called, do so.
4464 Otherwise, it must be some sort of indirect expression that
4465 we should still be able to handle. */
4466 decl
= gimple_call_addr_fndecl (fn
);
4468 return get_vi_for_tree (decl
);
4470 /* If the function is anything other than a SSA name pointer we have no
4471 clue and should be getting ANYFN (well, ANYTHING for now). */
4472 if (!fn
|| TREE_CODE (fn
) != SSA_NAME
)
4473 return get_varinfo (anything_id
);
4475 if (SSA_NAME_IS_DEFAULT_DEF (fn
)
4476 && (TREE_CODE (SSA_NAME_VAR (fn
)) == PARM_DECL
4477 || TREE_CODE (SSA_NAME_VAR (fn
)) == RESULT_DECL
))
4478 fn
= SSA_NAME_VAR (fn
);
4480 return get_vi_for_tree (fn
);
4483 /* Create constraints for assigning call argument ARG to the incoming parameter
4484 INDEX of function FI. */
4487 find_func_aliases_for_call_arg (varinfo_t fi
, unsigned index
, tree arg
)
4489 struct constraint_expr lhs
;
4490 lhs
= get_function_part_constraint (fi
, fi_parm_base
+ index
);
4492 auto_vec
<ce_s
, 2> rhsc
;
4493 get_constraint_for_rhs (arg
, &rhsc
);
4496 struct constraint_expr
*rhsp
;
4497 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4498 process_constraint (new_constraint (lhs
, *rhsp
));
4501 /* Return true if FNDECL may be part of another lto partition. */
4504 fndecl_maybe_in_other_partition (tree fndecl
)
4506 cgraph_node
*fn_node
= cgraph_node::get (fndecl
);
4507 if (fn_node
== NULL
)
4510 return fn_node
->in_other_partition
;
4513 /* Create constraints for the builtin call T. Return true if the call
4514 was handled, otherwise false. */
4517 find_func_aliases_for_builtin_call (struct function
*fn
, gcall
*t
)
4519 tree fndecl
= gimple_call_fndecl (t
);
4520 auto_vec
<ce_s
, 2> lhsc
;
4521 auto_vec
<ce_s
, 4> rhsc
;
4524 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
4525 /* ??? All builtins that are handled here need to be handled
4526 in the alias-oracle query functions explicitly! */
4527 switch (DECL_FUNCTION_CODE (fndecl
))
4529 /* All the following functions return a pointer to the same object
4530 as their first argument points to. The functions do not add
4531 to the ESCAPED solution. The functions make the first argument
4532 pointed to memory point to what the second argument pointed to
4533 memory points to. */
4534 case BUILT_IN_STRCPY
:
4535 case BUILT_IN_STRNCPY
:
4536 case BUILT_IN_BCOPY
:
4537 case BUILT_IN_MEMCPY
:
4538 case BUILT_IN_MEMMOVE
:
4539 case BUILT_IN_MEMPCPY
:
4540 case BUILT_IN_STPCPY
:
4541 case BUILT_IN_STPNCPY
:
4542 case BUILT_IN_STRCAT
:
4543 case BUILT_IN_STRNCAT
:
4544 case BUILT_IN_STRCPY_CHK
:
4545 case BUILT_IN_STRNCPY_CHK
:
4546 case BUILT_IN_MEMCPY_CHK
:
4547 case BUILT_IN_MEMMOVE_CHK
:
4548 case BUILT_IN_MEMPCPY_CHK
:
4549 case BUILT_IN_STPCPY_CHK
:
4550 case BUILT_IN_STPNCPY_CHK
:
4551 case BUILT_IN_STRCAT_CHK
:
4552 case BUILT_IN_STRNCAT_CHK
:
4553 case BUILT_IN_TM_MEMCPY
:
4554 case BUILT_IN_TM_MEMMOVE
:
4556 tree res
= gimple_call_lhs (t
);
4557 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4558 == BUILT_IN_BCOPY
? 1 : 0));
4559 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4560 == BUILT_IN_BCOPY
? 0 : 1));
4561 if (res
!= NULL_TREE
)
4563 get_constraint_for (res
, &lhsc
);
4564 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY
4565 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY
4566 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY
4567 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY_CHK
4568 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY_CHK
4569 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY_CHK
)
4570 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &rhsc
);
4572 get_constraint_for (dest
, &rhsc
);
4573 process_all_all_constraints (lhsc
, rhsc
);
4577 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4578 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4581 process_all_all_constraints (lhsc
, rhsc
);
4584 case BUILT_IN_MEMSET
:
4585 case BUILT_IN_MEMSET_CHK
:
4586 case BUILT_IN_TM_MEMSET
:
4588 tree res
= gimple_call_lhs (t
);
4589 tree dest
= gimple_call_arg (t
, 0);
4592 struct constraint_expr ac
;
4593 if (res
!= NULL_TREE
)
4595 get_constraint_for (res
, &lhsc
);
4596 get_constraint_for (dest
, &rhsc
);
4597 process_all_all_constraints (lhsc
, rhsc
);
4600 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4602 if (flag_delete_null_pointer_checks
4603 && integer_zerop (gimple_call_arg (t
, 1)))
4605 ac
.type
= ADDRESSOF
;
4606 ac
.var
= nothing_id
;
4611 ac
.var
= integer_id
;
4614 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4615 process_constraint (new_constraint (*lhsp
, ac
));
4618 case BUILT_IN_STACK_SAVE
:
4619 case BUILT_IN_STACK_RESTORE
:
4620 /* Nothing interesting happens. */
4622 case BUILT_IN_ALLOCA
:
4623 case BUILT_IN_ALLOCA_WITH_ALIGN
:
4624 case BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX
:
4626 tree ptr
= gimple_call_lhs (t
);
4627 if (ptr
== NULL_TREE
)
4629 get_constraint_for (ptr
, &lhsc
);
4630 varinfo_t vi
= make_heapvar ("HEAP", true);
4631 /* Alloca storage is never global. To exempt it from escaped
4632 handling make it a non-heap var. */
4633 DECL_EXTERNAL (vi
->decl
) = 0;
4634 vi
->is_global_var
= 0;
4635 vi
->is_heap_var
= 0;
4636 struct constraint_expr tmpc
;
4639 tmpc
.type
= ADDRESSOF
;
4640 rhsc
.safe_push (tmpc
);
4641 process_all_all_constraints (lhsc
, rhsc
);
4644 case BUILT_IN_POSIX_MEMALIGN
:
4646 tree ptrptr
= gimple_call_arg (t
, 0);
4647 get_constraint_for (ptrptr
, &lhsc
);
4649 varinfo_t vi
= make_heapvar ("HEAP", true);
4650 /* We are marking allocated storage local, we deal with it becoming
4651 global by escaping and setting of vars_contains_escaped_heap. */
4652 DECL_EXTERNAL (vi
->decl
) = 0;
4653 vi
->is_global_var
= 0;
4654 struct constraint_expr tmpc
;
4657 tmpc
.type
= ADDRESSOF
;
4658 rhsc
.safe_push (tmpc
);
4659 process_all_all_constraints (lhsc
, rhsc
);
4662 case BUILT_IN_ASSUME_ALIGNED
:
4664 tree res
= gimple_call_lhs (t
);
4665 tree dest
= gimple_call_arg (t
, 0);
4666 if (res
!= NULL_TREE
)
4668 get_constraint_for (res
, &lhsc
);
4669 get_constraint_for (dest
, &rhsc
);
4670 process_all_all_constraints (lhsc
, rhsc
);
4674 /* All the following functions do not return pointers, do not
4675 modify the points-to sets of memory reachable from their
4676 arguments and do not add to the ESCAPED solution. */
4677 case BUILT_IN_SINCOS
:
4678 case BUILT_IN_SINCOSF
:
4679 case BUILT_IN_SINCOSL
:
4680 case BUILT_IN_FREXP
:
4681 case BUILT_IN_FREXPF
:
4682 case BUILT_IN_FREXPL
:
4683 case BUILT_IN_GAMMA_R
:
4684 case BUILT_IN_GAMMAF_R
:
4685 case BUILT_IN_GAMMAL_R
:
4686 case BUILT_IN_LGAMMA_R
:
4687 case BUILT_IN_LGAMMAF_R
:
4688 case BUILT_IN_LGAMMAL_R
:
4690 case BUILT_IN_MODFF
:
4691 case BUILT_IN_MODFL
:
4692 case BUILT_IN_REMQUO
:
4693 case BUILT_IN_REMQUOF
:
4694 case BUILT_IN_REMQUOL
:
4697 case BUILT_IN_STRDUP
:
4698 case BUILT_IN_STRNDUP
:
4699 case BUILT_IN_REALLOC
:
4700 if (gimple_call_lhs (t
))
4702 auto_vec
<ce_s
> rhsc
;
4703 handle_lhs_call (t
, gimple_call_lhs (t
),
4704 gimple_call_return_flags (t
) | ERF_NOALIAS
,
4706 get_constraint_for_ptr_offset (gimple_call_lhs (t
),
4708 get_constraint_for_ptr_offset (gimple_call_arg (t
, 0),
4712 process_all_all_constraints (lhsc
, rhsc
);
4715 /* For realloc the resulting pointer can be equal to the
4716 argument as well. But only doing this wouldn't be
4717 correct because with ptr == 0 realloc behaves like malloc. */
4718 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_REALLOC
)
4720 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4721 get_constraint_for (gimple_call_arg (t
, 0), &rhsc
);
4722 process_all_all_constraints (lhsc
, rhsc
);
4727 /* String / character search functions return a pointer into the
4728 source string or NULL. */
4729 case BUILT_IN_INDEX
:
4730 case BUILT_IN_STRCHR
:
4731 case BUILT_IN_STRRCHR
:
4732 case BUILT_IN_MEMCHR
:
4733 case BUILT_IN_STRSTR
:
4734 case BUILT_IN_STRPBRK
:
4735 if (gimple_call_lhs (t
))
4737 tree src
= gimple_call_arg (t
, 0);
4738 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4739 constraint_expr nul
;
4740 nul
.var
= nothing_id
;
4742 nul
.type
= ADDRESSOF
;
4743 rhsc
.safe_push (nul
);
4744 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4745 process_all_all_constraints (lhsc
, rhsc
);
4748 /* Pure functions that return something not based on any object and
4749 that use the memory pointed to by their arguments (but not
4751 case BUILT_IN_STRCMP
:
4752 case BUILT_IN_STRCMP_EQ
:
4753 case BUILT_IN_STRNCMP
:
4754 case BUILT_IN_STRNCMP_EQ
:
4755 case BUILT_IN_STRCASECMP
:
4756 case BUILT_IN_STRNCASECMP
:
4757 case BUILT_IN_MEMCMP
:
4759 case BUILT_IN_STRSPN
:
4760 case BUILT_IN_STRCSPN
:
4762 varinfo_t uses
= get_call_use_vi (t
);
4763 make_any_offset_constraints (uses
);
4764 make_constraint_to (uses
->id
, gimple_call_arg (t
, 0));
4765 make_constraint_to (uses
->id
, gimple_call_arg (t
, 1));
4766 /* No constraints are necessary for the return value. */
4769 case BUILT_IN_STRLEN
:
4771 varinfo_t uses
= get_call_use_vi (t
);
4772 make_any_offset_constraints (uses
);
4773 make_constraint_to (uses
->id
, gimple_call_arg (t
, 0));
4774 /* No constraints are necessary for the return value. */
4777 case BUILT_IN_OBJECT_SIZE
:
4778 case BUILT_IN_CONSTANT_P
:
4780 /* No constraints are necessary for the return value or the
4784 /* Trampolines are special - they set up passing the static
4786 case BUILT_IN_INIT_TRAMPOLINE
:
4788 tree tramp
= gimple_call_arg (t
, 0);
4789 tree nfunc
= gimple_call_arg (t
, 1);
4790 tree frame
= gimple_call_arg (t
, 2);
4792 struct constraint_expr lhs
, *rhsp
;
4795 varinfo_t nfi
= NULL
;
4796 gcc_assert (TREE_CODE (nfunc
) == ADDR_EXPR
);
4797 nfi
= lookup_vi_for_tree (TREE_OPERAND (nfunc
, 0));
4800 lhs
= get_function_part_constraint (nfi
, fi_static_chain
);
4801 get_constraint_for (frame
, &rhsc
);
4802 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4803 process_constraint (new_constraint (lhs
, *rhsp
));
4806 /* Make the frame point to the function for
4807 the trampoline adjustment call. */
4808 get_constraint_for (tramp
, &lhsc
);
4810 get_constraint_for (nfunc
, &rhsc
);
4811 process_all_all_constraints (lhsc
, rhsc
);
4816 /* Else fallthru to generic handling which will let
4817 the frame escape. */
4820 case BUILT_IN_ADJUST_TRAMPOLINE
:
4822 tree tramp
= gimple_call_arg (t
, 0);
4823 tree res
= gimple_call_lhs (t
);
4824 if (in_ipa_mode
&& res
)
4826 get_constraint_for (res
, &lhsc
);
4827 get_constraint_for (tramp
, &rhsc
);
4829 process_all_all_constraints (lhsc
, rhsc
);
4833 CASE_BUILT_IN_TM_STORE (1):
4834 CASE_BUILT_IN_TM_STORE (2):
4835 CASE_BUILT_IN_TM_STORE (4):
4836 CASE_BUILT_IN_TM_STORE (8):
4837 CASE_BUILT_IN_TM_STORE (FLOAT
):
4838 CASE_BUILT_IN_TM_STORE (DOUBLE
):
4839 CASE_BUILT_IN_TM_STORE (LDOUBLE
):
4840 CASE_BUILT_IN_TM_STORE (M64
):
4841 CASE_BUILT_IN_TM_STORE (M128
):
4842 CASE_BUILT_IN_TM_STORE (M256
):
4844 tree addr
= gimple_call_arg (t
, 0);
4845 tree src
= gimple_call_arg (t
, 1);
4847 get_constraint_for (addr
, &lhsc
);
4849 get_constraint_for (src
, &rhsc
);
4850 process_all_all_constraints (lhsc
, rhsc
);
4853 CASE_BUILT_IN_TM_LOAD (1):
4854 CASE_BUILT_IN_TM_LOAD (2):
4855 CASE_BUILT_IN_TM_LOAD (4):
4856 CASE_BUILT_IN_TM_LOAD (8):
4857 CASE_BUILT_IN_TM_LOAD (FLOAT
):
4858 CASE_BUILT_IN_TM_LOAD (DOUBLE
):
4859 CASE_BUILT_IN_TM_LOAD (LDOUBLE
):
4860 CASE_BUILT_IN_TM_LOAD (M64
):
4861 CASE_BUILT_IN_TM_LOAD (M128
):
4862 CASE_BUILT_IN_TM_LOAD (M256
):
4864 tree dest
= gimple_call_lhs (t
);
4865 tree addr
= gimple_call_arg (t
, 0);
4867 get_constraint_for (dest
, &lhsc
);
4868 get_constraint_for (addr
, &rhsc
);
4870 process_all_all_constraints (lhsc
, rhsc
);
4873 /* Variadic argument handling needs to be handled in IPA
4875 case BUILT_IN_VA_START
:
4877 tree valist
= gimple_call_arg (t
, 0);
4878 struct constraint_expr rhs
, *lhsp
;
4880 get_constraint_for_ptr_offset (valist
, NULL_TREE
, &lhsc
);
4882 /* The va_list gets access to pointers in variadic
4883 arguments. Which we know in the case of IPA analysis
4884 and otherwise are just all nonlocal variables. */
4887 fi
= lookup_vi_for_tree (fn
->decl
);
4888 rhs
= get_function_part_constraint (fi
, ~0);
4889 rhs
.type
= ADDRESSOF
;
4893 rhs
.var
= nonlocal_id
;
4894 rhs
.type
= ADDRESSOF
;
4897 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4898 process_constraint (new_constraint (*lhsp
, rhs
));
4899 /* va_list is clobbered. */
4900 make_constraint_to (get_call_clobber_vi (t
)->id
, valist
);
4903 /* va_end doesn't have any effect that matters. */
4904 case BUILT_IN_VA_END
:
4906 /* Alternate return. Simply give up for now. */
4907 case BUILT_IN_RETURN
:
4911 || !(fi
= get_vi_for_tree (fn
->decl
)))
4912 make_constraint_from (get_varinfo (escaped_id
), anything_id
);
4913 else if (in_ipa_mode
4916 struct constraint_expr lhs
, rhs
;
4917 lhs
= get_function_part_constraint (fi
, fi_result
);
4918 rhs
.var
= anything_id
;
4921 process_constraint (new_constraint (lhs
, rhs
));
4925 case BUILT_IN_GOMP_PARALLEL
:
4926 case BUILT_IN_GOACC_PARALLEL
:
4930 unsigned int fnpos
, argpos
;
4931 switch (DECL_FUNCTION_CODE (fndecl
))
4933 case BUILT_IN_GOMP_PARALLEL
:
4934 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
4938 case BUILT_IN_GOACC_PARALLEL
:
4939 /* __builtin_GOACC_parallel (flags_m, fn, mapnum, hostaddrs,
4940 sizes, kinds, ...). */
4948 tree fnarg
= gimple_call_arg (t
, fnpos
);
4949 gcc_assert (TREE_CODE (fnarg
) == ADDR_EXPR
);
4950 tree fndecl
= TREE_OPERAND (fnarg
, 0);
4951 if (fndecl_maybe_in_other_partition (fndecl
))
4952 /* Fallthru to general call handling. */
4955 tree arg
= gimple_call_arg (t
, argpos
);
4957 varinfo_t fi
= get_vi_for_tree (fndecl
);
4958 find_func_aliases_for_call_arg (fi
, 0, arg
);
4961 /* Else fallthru to generic call handling. */
4964 /* printf-style functions may have hooks to set pointers to
4965 point to somewhere into the generated string. Leave them
4966 for a later exercise... */
4968 /* Fallthru to general call handling. */;
4974 /* Create constraints for the call T. */
4977 find_func_aliases_for_call (struct function
*fn
, gcall
*t
)
4979 tree fndecl
= gimple_call_fndecl (t
);
4982 if (fndecl
!= NULL_TREE
4983 && fndecl_built_in_p (fndecl
)
4984 && find_func_aliases_for_builtin_call (fn
, t
))
4987 if (gimple_call_internal_p (t
, IFN_DEFERRED_INIT
))
4990 fi
= get_fi_for_callee (t
);
4992 || (fi
->decl
&& fndecl
&& !fi
->is_fn_info
))
4994 auto_vec
<ce_s
, 16> rhsc
;
4995 int flags
= gimple_call_flags (t
);
4997 /* Const functions can return their arguments and addresses
4998 of global memory but not of escaped memory. */
4999 if (flags
& (ECF_CONST
|ECF_NOVOPS
))
5001 if (gimple_call_lhs (t
))
5002 handle_rhs_call (t
, &rhsc
, implicit_const_eaf_flags
, false, false);
5004 /* Pure functions can return addresses in and of memory
5005 reachable from their arguments, but they are not an escape
5006 point for reachable memory of their arguments. */
5007 else if (flags
& (ECF_PURE
|ECF_LOOPING_CONST_OR_PURE
))
5008 handle_rhs_call (t
, &rhsc
, implicit_pure_eaf_flags
, false, true);
5009 /* If the call is to a replaceable operator delete and results
5010 from a delete expression as opposed to a direct call to
5011 such operator, then the effects for PTA (in particular
5012 the escaping of the pointer) can be ignored. */
5014 && DECL_IS_OPERATOR_DELETE_P (fndecl
)
5015 && gimple_call_from_new_or_delete (t
))
5018 handle_rhs_call (t
, &rhsc
, 0, true, true);
5019 if (gimple_call_lhs (t
))
5020 handle_lhs_call (t
, gimple_call_lhs (t
),
5021 gimple_call_return_flags (t
), rhsc
, fndecl
);
5025 auto_vec
<ce_s
, 2> rhsc
;
5029 /* Assign all the passed arguments to the appropriate incoming
5030 parameters of the function. */
5031 for (j
= 0; j
< gimple_call_num_args (t
); j
++)
5033 tree arg
= gimple_call_arg (t
, j
);
5034 find_func_aliases_for_call_arg (fi
, j
, arg
);
5037 /* If we are returning a value, assign it to the result. */
5038 lhsop
= gimple_call_lhs (t
);
5041 auto_vec
<ce_s
, 2> lhsc
;
5042 struct constraint_expr rhs
;
5043 struct constraint_expr
*lhsp
;
5044 bool aggr_p
= aggregate_value_p (lhsop
, gimple_call_fntype (t
));
5046 get_constraint_for (lhsop
, &lhsc
);
5047 rhs
= get_function_part_constraint (fi
, fi_result
);
5050 auto_vec
<ce_s
, 2> tem
;
5051 tem
.quick_push (rhs
);
5053 gcc_checking_assert (tem
.length () == 1);
5056 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
5057 process_constraint (new_constraint (*lhsp
, rhs
));
5059 /* If we pass the result decl by reference, honor that. */
5062 struct constraint_expr lhs
;
5063 struct constraint_expr
*rhsp
;
5065 get_constraint_for_address_of (lhsop
, &rhsc
);
5066 lhs
= get_function_part_constraint (fi
, fi_result
);
5067 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5068 process_constraint (new_constraint (lhs
, *rhsp
));
5073 /* If we use a static chain, pass it along. */
5074 if (gimple_call_chain (t
))
5076 struct constraint_expr lhs
;
5077 struct constraint_expr
*rhsp
;
5079 get_constraint_for (gimple_call_chain (t
), &rhsc
);
5080 lhs
= get_function_part_constraint (fi
, fi_static_chain
);
5081 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5082 process_constraint (new_constraint (lhs
, *rhsp
));
5087 /* Walk statement T setting up aliasing constraints according to the
5088 references found in T. This function is the main part of the
5089 constraint builder. AI points to auxiliary alias information used
5090 when building alias sets and computing alias grouping heuristics. */
5093 find_func_aliases (struct function
*fn
, gimple
*origt
)
5096 auto_vec
<ce_s
, 16> lhsc
;
5097 auto_vec
<ce_s
, 16> rhsc
;
5100 /* Now build constraints expressions. */
5101 if (gimple_code (t
) == GIMPLE_PHI
)
5103 /* For a phi node, assign all the arguments to
5105 get_constraint_for (gimple_phi_result (t
), &lhsc
);
5106 for (unsigned i
= 0; i
< gimple_phi_num_args (t
); i
++)
5108 get_constraint_for_rhs (gimple_phi_arg_def (t
, i
), &rhsc
);
5109 process_all_all_constraints (lhsc
, rhsc
);
5113 /* In IPA mode, we need to generate constraints to pass call
5114 arguments through their calls. There are two cases,
5115 either a GIMPLE_CALL returning a value, or just a plain
5116 GIMPLE_CALL when we are not.
5118 In non-ipa mode, we need to generate constraints for each
5119 pointer passed by address. */
5120 else if (is_gimple_call (t
))
5121 find_func_aliases_for_call (fn
, as_a
<gcall
*> (t
));
5123 /* Otherwise, just a regular assignment statement. Only care about
5124 operations with pointer result, others are dealt with as escape
5125 points if they have pointer operands. */
5126 else if (is_gimple_assign (t
))
5128 /* Otherwise, just a regular assignment statement. */
5129 tree lhsop
= gimple_assign_lhs (t
);
5130 tree rhsop
= (gimple_num_ops (t
) == 2) ? gimple_assign_rhs1 (t
) : NULL
;
5132 if (rhsop
&& TREE_CLOBBER_P (rhsop
))
5133 /* Ignore clobbers, they don't actually store anything into
5136 else if (rhsop
&& AGGREGATE_TYPE_P (TREE_TYPE (lhsop
)))
5137 do_structure_copy (lhsop
, rhsop
);
5140 enum tree_code code
= gimple_assign_rhs_code (t
);
5142 get_constraint_for (lhsop
, &lhsc
);
5144 if (code
== POINTER_PLUS_EXPR
)
5145 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
5146 gimple_assign_rhs2 (t
), &rhsc
);
5147 else if (code
== POINTER_DIFF_EXPR
)
5148 /* The result is not a pointer (part). */
5150 else if (code
== BIT_AND_EXPR
5151 && TREE_CODE (gimple_assign_rhs2 (t
)) == INTEGER_CST
)
5153 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
5154 the pointer. Handle it by offsetting it by UNKNOWN. */
5155 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
5158 else if (code
== TRUNC_DIV_EXPR
5159 || code
== CEIL_DIV_EXPR
5160 || code
== FLOOR_DIV_EXPR
5161 || code
== ROUND_DIV_EXPR
5162 || code
== EXACT_DIV_EXPR
5163 || code
== TRUNC_MOD_EXPR
5164 || code
== CEIL_MOD_EXPR
5165 || code
== FLOOR_MOD_EXPR
5166 || code
== ROUND_MOD_EXPR
)
5167 /* Division and modulo transfer the pointer from the LHS. */
5168 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
5170 else if (CONVERT_EXPR_CODE_P (code
)
5171 || gimple_assign_single_p (t
))
5172 /* See through conversions, single RHS are handled by
5173 get_constraint_for_rhs. */
5174 get_constraint_for_rhs (rhsop
, &rhsc
);
5175 else if (code
== COND_EXPR
)
5177 /* The result is a merge of both COND_EXPR arms. */
5178 auto_vec
<ce_s
, 2> tmp
;
5179 struct constraint_expr
*rhsp
;
5181 get_constraint_for_rhs (gimple_assign_rhs2 (t
), &rhsc
);
5182 get_constraint_for_rhs (gimple_assign_rhs3 (t
), &tmp
);
5183 FOR_EACH_VEC_ELT (tmp
, i
, rhsp
)
5184 rhsc
.safe_push (*rhsp
);
5186 else if (truth_value_p (code
))
5187 /* Truth value results are not pointer (parts). Or at least
5188 very unreasonable obfuscation of a part. */
5192 /* All other operations are possibly offsetting merges. */
5193 auto_vec
<ce_s
, 4> tmp
;
5194 struct constraint_expr
*rhsp
;
5196 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
5198 for (i
= 2; i
< gimple_num_ops (t
); ++i
)
5200 get_constraint_for_ptr_offset (gimple_op (t
, i
),
5202 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
5203 rhsc
.safe_push (*rhsp
);
5207 process_all_all_constraints (lhsc
, rhsc
);
5209 /* If there is a store to a global variable the rhs escapes. */
5210 if ((lhsop
= get_base_address (lhsop
)) != NULL_TREE
5213 varinfo_t vi
= get_vi_for_tree (lhsop
);
5214 if ((! in_ipa_mode
&& vi
->is_global_var
)
5215 || vi
->is_ipa_escape_point
)
5216 make_escape_constraint (rhsop
);
5219 /* Handle escapes through return. */
5220 else if (gimple_code (t
) == GIMPLE_RETURN
5221 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
)
5223 greturn
*return_stmt
= as_a
<greturn
*> (t
);
5226 && SSA_VAR_P (gimple_return_retval (return_stmt
)))
5228 /* We handle simple returns by post-processing the solutions. */
5231 if (!(fi
= get_vi_for_tree (fn
->decl
)))
5232 make_escape_constraint (gimple_return_retval (return_stmt
));
5233 else if (in_ipa_mode
)
5235 struct constraint_expr lhs
;
5236 struct constraint_expr
*rhsp
;
5239 lhs
= get_function_part_constraint (fi
, fi_result
);
5240 get_constraint_for_rhs (gimple_return_retval (return_stmt
), &rhsc
);
5241 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5242 process_constraint (new_constraint (lhs
, *rhsp
));
5245 /* Handle asms conservatively by adding escape constraints to everything. */
5246 else if (gasm
*asm_stmt
= dyn_cast
<gasm
*> (t
))
5248 unsigned i
, noutputs
;
5249 const char **oconstraints
;
5250 const char *constraint
;
5251 bool allows_mem
, allows_reg
, is_inout
;
5253 noutputs
= gimple_asm_noutputs (asm_stmt
);
5254 oconstraints
= XALLOCAVEC (const char *, noutputs
);
5256 for (i
= 0; i
< noutputs
; ++i
)
5258 tree link
= gimple_asm_output_op (asm_stmt
, i
);
5259 tree op
= TREE_VALUE (link
);
5261 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
5262 oconstraints
[i
] = constraint
;
5263 parse_output_constraint (&constraint
, i
, 0, 0, &allows_mem
,
5264 &allows_reg
, &is_inout
);
5266 /* A memory constraint makes the address of the operand escape. */
5267 if (!allows_reg
&& allows_mem
)
5268 make_escape_constraint (build_fold_addr_expr (op
));
5270 /* The asm may read global memory, so outputs may point to
5271 any global memory. */
5274 auto_vec
<ce_s
, 2> lhsc
;
5275 struct constraint_expr rhsc
, *lhsp
;
5277 get_constraint_for (op
, &lhsc
);
5278 rhsc
.var
= nonlocal_id
;
5281 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
5282 process_constraint (new_constraint (*lhsp
, rhsc
));
5285 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); ++i
)
5287 tree link
= gimple_asm_input_op (asm_stmt
, i
);
5288 tree op
= TREE_VALUE (link
);
5290 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
5292 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0, oconstraints
,
5293 &allows_mem
, &allows_reg
);
5295 /* A memory constraint makes the address of the operand escape. */
5296 if (!allows_reg
&& allows_mem
)
5297 make_escape_constraint (build_fold_addr_expr (op
));
5298 /* Strictly we'd only need the constraint to ESCAPED if
5299 the asm clobbers memory, otherwise using something
5300 along the lines of per-call clobbers/uses would be enough. */
5302 make_escape_constraint (op
);
5308 /* Create a constraint adding to the clobber set of FI the memory
5309 pointed to by PTR. */
5312 process_ipa_clobber (varinfo_t fi
, tree ptr
)
5314 vec
<ce_s
> ptrc
= vNULL
;
5315 struct constraint_expr
*c
, lhs
;
5317 get_constraint_for_rhs (ptr
, &ptrc
);
5318 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5319 FOR_EACH_VEC_ELT (ptrc
, i
, c
)
5320 process_constraint (new_constraint (lhs
, *c
));
5324 /* Walk statement T setting up clobber and use constraints according to the
5325 references found in T. This function is a main part of the
5326 IPA constraint builder. */
5329 find_func_clobbers (struct function
*fn
, gimple
*origt
)
5332 auto_vec
<ce_s
, 16> lhsc
;
5333 auto_vec
<ce_s
, 16> rhsc
;
5336 /* Add constraints for clobbered/used in IPA mode.
5337 We are not interested in what automatic variables are clobbered
5338 or used as we only use the information in the caller to which
5339 they do not escape. */
5340 gcc_assert (in_ipa_mode
);
5342 /* If the stmt refers to memory in any way it better had a VUSE. */
5343 if (gimple_vuse (t
) == NULL_TREE
)
5346 /* We'd better have function information for the current function. */
5347 fi
= lookup_vi_for_tree (fn
->decl
);
5348 gcc_assert (fi
!= NULL
);
5350 /* Account for stores in assignments and calls. */
5351 if (gimple_vdef (t
) != NULL_TREE
5352 && gimple_has_lhs (t
))
5354 tree lhs
= gimple_get_lhs (t
);
5356 while (handled_component_p (tem
))
5357 tem
= TREE_OPERAND (tem
, 0);
5359 && !auto_var_in_fn_p (tem
, fn
->decl
))
5360 || INDIRECT_REF_P (tem
)
5361 || (TREE_CODE (tem
) == MEM_REF
5362 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
5364 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
5366 struct constraint_expr lhsc
, *rhsp
;
5368 lhsc
= get_function_part_constraint (fi
, fi_clobbers
);
5369 get_constraint_for_address_of (lhs
, &rhsc
);
5370 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5371 process_constraint (new_constraint (lhsc
, *rhsp
));
5376 /* Account for uses in assigments and returns. */
5377 if (gimple_assign_single_p (t
)
5378 || (gimple_code (t
) == GIMPLE_RETURN
5379 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
))
5381 tree rhs
= (gimple_assign_single_p (t
)
5382 ? gimple_assign_rhs1 (t
)
5383 : gimple_return_retval (as_a
<greturn
*> (t
)));
5385 while (handled_component_p (tem
))
5386 tem
= TREE_OPERAND (tem
, 0);
5388 && !auto_var_in_fn_p (tem
, fn
->decl
))
5389 || INDIRECT_REF_P (tem
)
5390 || (TREE_CODE (tem
) == MEM_REF
5391 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
5393 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
5395 struct constraint_expr lhs
, *rhsp
;
5397 lhs
= get_function_part_constraint (fi
, fi_uses
);
5398 get_constraint_for_address_of (rhs
, &rhsc
);
5399 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5400 process_constraint (new_constraint (lhs
, *rhsp
));
5405 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (t
))
5407 varinfo_t cfi
= NULL
;
5408 tree decl
= gimple_call_fndecl (t
);
5409 struct constraint_expr lhs
, rhs
;
5412 /* For builtins we do not have separate function info. For those
5413 we do not generate escapes for we have to generate clobbers/uses. */
5414 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
5415 switch (DECL_FUNCTION_CODE (decl
))
5417 /* The following functions use and clobber memory pointed to
5418 by their arguments. */
5419 case BUILT_IN_STRCPY
:
5420 case BUILT_IN_STRNCPY
:
5421 case BUILT_IN_BCOPY
:
5422 case BUILT_IN_MEMCPY
:
5423 case BUILT_IN_MEMMOVE
:
5424 case BUILT_IN_MEMPCPY
:
5425 case BUILT_IN_STPCPY
:
5426 case BUILT_IN_STPNCPY
:
5427 case BUILT_IN_STRCAT
:
5428 case BUILT_IN_STRNCAT
:
5429 case BUILT_IN_STRCPY_CHK
:
5430 case BUILT_IN_STRNCPY_CHK
:
5431 case BUILT_IN_MEMCPY_CHK
:
5432 case BUILT_IN_MEMMOVE_CHK
:
5433 case BUILT_IN_MEMPCPY_CHK
:
5434 case BUILT_IN_STPCPY_CHK
:
5435 case BUILT_IN_STPNCPY_CHK
:
5436 case BUILT_IN_STRCAT_CHK
:
5437 case BUILT_IN_STRNCAT_CHK
:
5439 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
5440 == BUILT_IN_BCOPY
? 1 : 0));
5441 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
5442 == BUILT_IN_BCOPY
? 0 : 1));
5444 struct constraint_expr
*rhsp
, *lhsp
;
5445 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5446 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5447 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5448 process_constraint (new_constraint (lhs
, *lhsp
));
5449 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
5450 lhs
= get_function_part_constraint (fi
, fi_uses
);
5451 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5452 process_constraint (new_constraint (lhs
, *rhsp
));
5455 /* The following function clobbers memory pointed to by
5457 case BUILT_IN_MEMSET
:
5458 case BUILT_IN_MEMSET_CHK
:
5459 case BUILT_IN_POSIX_MEMALIGN
:
5461 tree dest
= gimple_call_arg (t
, 0);
5464 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5465 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5466 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5467 process_constraint (new_constraint (lhs
, *lhsp
));
5470 /* The following functions clobber their second and third
5472 case BUILT_IN_SINCOS
:
5473 case BUILT_IN_SINCOSF
:
5474 case BUILT_IN_SINCOSL
:
5476 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5477 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5480 /* The following functions clobber their second argument. */
5481 case BUILT_IN_FREXP
:
5482 case BUILT_IN_FREXPF
:
5483 case BUILT_IN_FREXPL
:
5484 case BUILT_IN_LGAMMA_R
:
5485 case BUILT_IN_LGAMMAF_R
:
5486 case BUILT_IN_LGAMMAL_R
:
5487 case BUILT_IN_GAMMA_R
:
5488 case BUILT_IN_GAMMAF_R
:
5489 case BUILT_IN_GAMMAL_R
:
5491 case BUILT_IN_MODFF
:
5492 case BUILT_IN_MODFL
:
5494 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5497 /* The following functions clobber their third argument. */
5498 case BUILT_IN_REMQUO
:
5499 case BUILT_IN_REMQUOF
:
5500 case BUILT_IN_REMQUOL
:
5502 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5505 /* The following functions neither read nor clobber memory. */
5506 case BUILT_IN_ASSUME_ALIGNED
:
5509 /* Trampolines are of no interest to us. */
5510 case BUILT_IN_INIT_TRAMPOLINE
:
5511 case BUILT_IN_ADJUST_TRAMPOLINE
:
5513 case BUILT_IN_VA_START
:
5514 case BUILT_IN_VA_END
:
5516 case BUILT_IN_GOMP_PARALLEL
:
5517 case BUILT_IN_GOACC_PARALLEL
:
5519 unsigned int fnpos
, argpos
;
5520 unsigned int implicit_use_args
[2];
5521 unsigned int num_implicit_use_args
= 0;
5522 switch (DECL_FUNCTION_CODE (decl
))
5524 case BUILT_IN_GOMP_PARALLEL
:
5525 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
5529 case BUILT_IN_GOACC_PARALLEL
:
5530 /* __builtin_GOACC_parallel (flags_m, fn, mapnum, hostaddrs,
5531 sizes, kinds, ...). */
5534 implicit_use_args
[num_implicit_use_args
++] = 4;
5535 implicit_use_args
[num_implicit_use_args
++] = 5;
5541 tree fnarg
= gimple_call_arg (t
, fnpos
);
5542 gcc_assert (TREE_CODE (fnarg
) == ADDR_EXPR
);
5543 tree fndecl
= TREE_OPERAND (fnarg
, 0);
5544 if (fndecl_maybe_in_other_partition (fndecl
))
5545 /* Fallthru to general call handling. */
5548 varinfo_t cfi
= get_vi_for_tree (fndecl
);
5550 tree arg
= gimple_call_arg (t
, argpos
);
5552 /* Parameter passed by value is used. */
5553 lhs
= get_function_part_constraint (fi
, fi_uses
);
5554 struct constraint_expr
*rhsp
;
5555 get_constraint_for (arg
, &rhsc
);
5556 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5557 process_constraint (new_constraint (lhs
, *rhsp
));
5560 /* Handle parameters used by the call, but not used in cfi, as
5561 implicitly used by cfi. */
5562 lhs
= get_function_part_constraint (cfi
, fi_uses
);
5563 for (unsigned i
= 0; i
< num_implicit_use_args
; ++i
)
5565 tree arg
= gimple_call_arg (t
, implicit_use_args
[i
]);
5566 get_constraint_for (arg
, &rhsc
);
5567 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5568 process_constraint (new_constraint (lhs
, *rhsp
));
5572 /* The caller clobbers what the callee does. */
5573 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5574 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5575 process_constraint (new_constraint (lhs
, rhs
));
5577 /* The caller uses what the callee does. */
5578 lhs
= get_function_part_constraint (fi
, fi_uses
);
5579 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5580 process_constraint (new_constraint (lhs
, rhs
));
5584 /* printf-style functions may have hooks to set pointers to
5585 point to somewhere into the generated string. Leave them
5586 for a later exercise... */
5588 /* Fallthru to general call handling. */;
5591 /* Parameters passed by value are used. */
5592 lhs
= get_function_part_constraint (fi
, fi_uses
);
5593 for (i
= 0; i
< gimple_call_num_args (t
); i
++)
5595 struct constraint_expr
*rhsp
;
5596 tree arg
= gimple_call_arg (t
, i
);
5598 if (TREE_CODE (arg
) == SSA_NAME
5599 || is_gimple_min_invariant (arg
))
5602 get_constraint_for_address_of (arg
, &rhsc
);
5603 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5604 process_constraint (new_constraint (lhs
, *rhsp
));
5608 /* Build constraints for propagating clobbers/uses along the
5610 cfi
= get_fi_for_callee (call_stmt
);
5611 if (cfi
->id
== anything_id
)
5613 if (gimple_vdef (t
))
5614 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5616 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5621 /* For callees without function info (that's external functions),
5622 ESCAPED is clobbered and used. */
5624 && TREE_CODE (cfi
->decl
) == FUNCTION_DECL
5625 && !cfi
->is_fn_info
)
5629 if (gimple_vdef (t
))
5630 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5632 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
), escaped_id
);
5634 /* Also honor the call statement use/clobber info. */
5635 if ((vi
= lookup_call_clobber_vi (call_stmt
)) != NULL
)
5636 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5638 if ((vi
= lookup_call_use_vi (call_stmt
)) != NULL
)
5639 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
),
5644 /* Otherwise the caller clobbers and uses what the callee does.
5645 ??? This should use a new complex constraint that filters
5646 local variables of the callee. */
5647 if (gimple_vdef (t
))
5649 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5650 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5651 process_constraint (new_constraint (lhs
, rhs
));
5653 lhs
= get_function_part_constraint (fi
, fi_uses
);
5654 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5655 process_constraint (new_constraint (lhs
, rhs
));
5657 else if (gimple_code (t
) == GIMPLE_ASM
)
5659 /* ??? Ick. We can do better. */
5660 if (gimple_vdef (t
))
5661 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5663 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5669 /* Find the first varinfo in the same variable as START that overlaps with
5670 OFFSET. Return NULL if we can't find one. */
5673 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
5675 /* If the offset is outside of the variable, bail out. */
5676 if (offset
>= start
->fullsize
)
5679 /* If we cannot reach offset from start, lookup the first field
5680 and start from there. */
5681 if (start
->offset
> offset
)
5682 start
= get_varinfo (start
->head
);
5686 /* We may not find a variable in the field list with the actual
5687 offset when we have glommed a structure to a variable.
5688 In that case, however, offset should still be within the size
5690 if (offset
>= start
->offset
5691 && (offset
- start
->offset
) < start
->size
)
5694 start
= vi_next (start
);
5700 /* Find the first varinfo in the same variable as START that overlaps with
5701 OFFSET. If there is no such varinfo the varinfo directly preceding
5702 OFFSET is returned. */
5705 first_or_preceding_vi_for_offset (varinfo_t start
,
5706 unsigned HOST_WIDE_INT offset
)
5708 /* If we cannot reach offset from start, lookup the first field
5709 and start from there. */
5710 if (start
->offset
> offset
)
5711 start
= get_varinfo (start
->head
);
5713 /* We may not find a variable in the field list with the actual
5714 offset when we have glommed a structure to a variable.
5715 In that case, however, offset should still be within the size
5717 If we got beyond the offset we look for return the field
5718 directly preceding offset which may be the last field. */
5720 && offset
>= start
->offset
5721 && !((offset
- start
->offset
) < start
->size
))
5722 start
= vi_next (start
);
5728 /* This structure is used during pushing fields onto the fieldstack
5729 to track the offset of the field, since bitpos_of_field gives it
5730 relative to its immediate containing type, and we want it relative
5731 to the ultimate containing object. */
5735 /* Offset from the base of the base containing object to this field. */
5736 HOST_WIDE_INT offset
;
5738 /* Size, in bits, of the field. */
5739 unsigned HOST_WIDE_INT size
;
5741 unsigned has_unknown_size
: 1;
5743 unsigned must_have_pointers
: 1;
5745 unsigned may_have_pointers
: 1;
5747 unsigned only_restrict_pointers
: 1;
5749 tree restrict_pointed_type
;
5751 typedef struct fieldoff fieldoff_s
;
5754 /* qsort comparison function for two fieldoff's PA and PB */
5757 fieldoff_compare (const void *pa
, const void *pb
)
5759 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
5760 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
5761 unsigned HOST_WIDE_INT foasize
, fobsize
;
5763 if (foa
->offset
< fob
->offset
)
5765 else if (foa
->offset
> fob
->offset
)
5768 foasize
= foa
->size
;
5769 fobsize
= fob
->size
;
5770 if (foasize
< fobsize
)
5772 else if (foasize
> fobsize
)
5777 /* Sort a fieldstack according to the field offset and sizes. */
5779 sort_fieldstack (vec
<fieldoff_s
> &fieldstack
)
5781 fieldstack
.qsort (fieldoff_compare
);
5784 /* Return true if T is a type that can have subvars. */
5787 type_can_have_subvars (const_tree t
)
5789 /* Aggregates without overlapping fields can have subvars. */
5790 return TREE_CODE (t
) == RECORD_TYPE
;
5793 /* Return true if V is a tree that we can have subvars for.
5794 Normally, this is any aggregate type. Also complex
5795 types which are not gimple registers can have subvars. */
5798 var_can_have_subvars (const_tree v
)
5800 /* Volatile variables should never have subvars. */
5801 if (TREE_THIS_VOLATILE (v
))
5804 /* Non decls or memory tags can never have subvars. */
5808 return type_can_have_subvars (TREE_TYPE (v
));
5811 /* Return true if T is a type that does contain pointers. */
5814 type_must_have_pointers (tree type
)
5816 if (POINTER_TYPE_P (type
))
5819 if (TREE_CODE (type
) == ARRAY_TYPE
)
5820 return type_must_have_pointers (TREE_TYPE (type
));
5822 /* A function or method can have pointers as arguments, so track
5823 those separately. */
5824 if (FUNC_OR_METHOD_TYPE_P (type
))
5831 field_must_have_pointers (tree t
)
5833 return type_must_have_pointers (TREE_TYPE (t
));
5836 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5837 the fields of TYPE onto fieldstack, recording their offsets along
5840 OFFSET is used to keep track of the offset in this entire
5841 structure, rather than just the immediately containing structure.
5842 Returns false if the caller is supposed to handle the field we
5846 push_fields_onto_fieldstack (tree type
, vec
<fieldoff_s
> *fieldstack
,
5847 HOST_WIDE_INT offset
)
5850 bool empty_p
= true;
5852 if (TREE_CODE (type
) != RECORD_TYPE
)
5855 /* If the vector of fields is growing too big, bail out early.
5856 Callers check for vec::length <= param_max_fields_for_field_sensitive, make
5858 if (fieldstack
->length () > (unsigned)param_max_fields_for_field_sensitive
)
5861 for (field
= TYPE_FIELDS (type
); field
; field
= DECL_CHAIN (field
))
5862 if (TREE_CODE (field
) == FIELD_DECL
)
5865 HOST_WIDE_INT foff
= bitpos_of_field (field
);
5866 tree field_type
= TREE_TYPE (field
);
5868 if (!var_can_have_subvars (field
)
5869 || TREE_CODE (field_type
) == QUAL_UNION_TYPE
5870 || TREE_CODE (field_type
) == UNION_TYPE
)
5872 else if (!push_fields_onto_fieldstack
5873 (field_type
, fieldstack
, offset
+ foff
)
5874 && (DECL_SIZE (field
)
5875 && !integer_zerop (DECL_SIZE (field
))))
5876 /* Empty structures may have actual size, like in C++. So
5877 see if we didn't push any subfields and the size is
5878 nonzero, push the field onto the stack. */
5883 fieldoff_s
*pair
= NULL
;
5884 bool has_unknown_size
= false;
5885 bool must_have_pointers_p
;
5887 if (!fieldstack
->is_empty ())
5888 pair
= &fieldstack
->last ();
5890 /* If there isn't anything at offset zero, create sth. */
5892 && offset
+ foff
!= 0)
5895 = {0, offset
+ foff
, false, false, true, false, NULL_TREE
};
5896 pair
= fieldstack
->safe_push (e
);
5899 if (!DECL_SIZE (field
)
5900 || !tree_fits_uhwi_p (DECL_SIZE (field
)))
5901 has_unknown_size
= true;
5903 /* If adjacent fields do not contain pointers merge them. */
5904 must_have_pointers_p
= field_must_have_pointers (field
);
5906 && !has_unknown_size
5907 && !must_have_pointers_p
5908 && !pair
->must_have_pointers
5909 && !pair
->has_unknown_size
5910 && pair
->offset
+ (HOST_WIDE_INT
)pair
->size
== offset
+ foff
)
5912 pair
->size
+= tree_to_uhwi (DECL_SIZE (field
));
5917 e
.offset
= offset
+ foff
;
5918 e
.has_unknown_size
= has_unknown_size
;
5919 if (!has_unknown_size
)
5920 e
.size
= tree_to_uhwi (DECL_SIZE (field
));
5923 e
.must_have_pointers
= must_have_pointers_p
;
5924 e
.may_have_pointers
= true;
5925 e
.only_restrict_pointers
5926 = (!has_unknown_size
5927 && POINTER_TYPE_P (field_type
)
5928 && TYPE_RESTRICT (field_type
));
5929 if (e
.only_restrict_pointers
)
5930 e
.restrict_pointed_type
= TREE_TYPE (field_type
);
5931 fieldstack
->safe_push (e
);
5941 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5942 if it is a varargs function. */
5945 count_num_arguments (tree decl
, bool *is_varargs
)
5947 unsigned int num
= 0;
5950 /* Capture named arguments for K&R functions. They do not
5951 have a prototype and thus no TYPE_ARG_TYPES. */
5952 for (t
= DECL_ARGUMENTS (decl
); t
; t
= DECL_CHAIN (t
))
5955 /* Check if the function has variadic arguments. */
5956 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
)); t
; t
= TREE_CHAIN (t
))
5957 if (TREE_VALUE (t
) == void_type_node
)
5965 /* Creation function node for DECL, using NAME, and return the index
5966 of the variable we've created for the function. If NONLOCAL_p, create
5967 initial constraints. */
5970 create_function_info_for (tree decl
, const char *name
, bool add_id
,
5973 struct function
*fn
= DECL_STRUCT_FUNCTION (decl
);
5974 varinfo_t vi
, prev_vi
;
5977 bool is_varargs
= false;
5978 unsigned int num_args
= count_num_arguments (decl
, &is_varargs
);
5980 /* Create the variable info. */
5982 vi
= new_var_info (decl
, name
, add_id
);
5985 vi
->fullsize
= fi_parm_base
+ num_args
;
5987 vi
->may_have_pointers
= false;
5990 insert_vi_for_tree (vi
->decl
, vi
);
5994 /* Create a variable for things the function clobbers and one for
5995 things the function uses. */
5997 varinfo_t clobbervi
, usevi
;
5998 const char *newname
;
6001 tempname
= xasprintf ("%s.clobber", name
);
6002 newname
= ggc_strdup (tempname
);
6005 clobbervi
= new_var_info (NULL
, newname
, false);
6006 clobbervi
->offset
= fi_clobbers
;
6007 clobbervi
->size
= 1;
6008 clobbervi
->fullsize
= vi
->fullsize
;
6009 clobbervi
->is_full_var
= true;
6010 clobbervi
->is_global_var
= false;
6011 clobbervi
->is_reg_var
= true;
6013 gcc_assert (prev_vi
->offset
< clobbervi
->offset
);
6014 prev_vi
->next
= clobbervi
->id
;
6015 prev_vi
= clobbervi
;
6017 tempname
= xasprintf ("%s.use", name
);
6018 newname
= ggc_strdup (tempname
);
6021 usevi
= new_var_info (NULL
, newname
, false);
6022 usevi
->offset
= fi_uses
;
6024 usevi
->fullsize
= vi
->fullsize
;
6025 usevi
->is_full_var
= true;
6026 usevi
->is_global_var
= false;
6027 usevi
->is_reg_var
= true;
6029 gcc_assert (prev_vi
->offset
< usevi
->offset
);
6030 prev_vi
->next
= usevi
->id
;
6034 /* And one for the static chain. */
6035 if (fn
->static_chain_decl
!= NULL_TREE
)
6038 const char *newname
;
6041 tempname
= xasprintf ("%s.chain", name
);
6042 newname
= ggc_strdup (tempname
);
6045 chainvi
= new_var_info (fn
->static_chain_decl
, newname
, false);
6046 chainvi
->offset
= fi_static_chain
;
6048 chainvi
->fullsize
= vi
->fullsize
;
6049 chainvi
->is_full_var
= true;
6050 chainvi
->is_global_var
= false;
6052 insert_vi_for_tree (fn
->static_chain_decl
, chainvi
);
6055 && chainvi
->may_have_pointers
)
6056 make_constraint_from (chainvi
, nonlocal_id
);
6058 gcc_assert (prev_vi
->offset
< chainvi
->offset
);
6059 prev_vi
->next
= chainvi
->id
;
6063 /* Create a variable for the return var. */
6064 if (DECL_RESULT (decl
) != NULL
6065 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
6068 const char *newname
;
6070 tree resultdecl
= decl
;
6072 if (DECL_RESULT (decl
))
6073 resultdecl
= DECL_RESULT (decl
);
6075 tempname
= xasprintf ("%s.result", name
);
6076 newname
= ggc_strdup (tempname
);
6079 resultvi
= new_var_info (resultdecl
, newname
, false);
6080 resultvi
->offset
= fi_result
;
6082 resultvi
->fullsize
= vi
->fullsize
;
6083 resultvi
->is_full_var
= true;
6084 if (DECL_RESULT (decl
))
6085 resultvi
->may_have_pointers
= true;
6087 if (DECL_RESULT (decl
))
6088 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
6091 && DECL_RESULT (decl
)
6092 && DECL_BY_REFERENCE (DECL_RESULT (decl
)))
6093 make_constraint_from (resultvi
, nonlocal_id
);
6095 gcc_assert (prev_vi
->offset
< resultvi
->offset
);
6096 prev_vi
->next
= resultvi
->id
;
6100 /* We also need to make function return values escape. Nothing
6101 escapes by returning from main though. */
6103 && !MAIN_NAME_P (DECL_NAME (decl
)))
6106 fi
= lookup_vi_for_tree (decl
);
6107 rvi
= first_vi_for_offset (fi
, fi_result
);
6108 if (rvi
&& rvi
->offset
== fi_result
)
6109 make_copy_constraint (get_varinfo (escaped_id
), rvi
->id
);
6112 /* Set up variables for each argument. */
6113 arg
= DECL_ARGUMENTS (decl
);
6114 for (i
= 0; i
< num_args
; i
++)
6117 const char *newname
;
6119 tree argdecl
= decl
;
6124 tempname
= xasprintf ("%s.arg%d", name
, i
);
6125 newname
= ggc_strdup (tempname
);
6128 argvi
= new_var_info (argdecl
, newname
, false);
6129 argvi
->offset
= fi_parm_base
+ i
;
6131 argvi
->is_full_var
= true;
6132 argvi
->fullsize
= vi
->fullsize
;
6134 argvi
->may_have_pointers
= true;
6137 insert_vi_for_tree (arg
, argvi
);
6140 && argvi
->may_have_pointers
)
6141 make_constraint_from (argvi
, nonlocal_id
);
6143 gcc_assert (prev_vi
->offset
< argvi
->offset
);
6144 prev_vi
->next
= argvi
->id
;
6147 arg
= DECL_CHAIN (arg
);
6150 /* Add one representative for all further args. */
6154 const char *newname
;
6158 tempname
= xasprintf ("%s.varargs", name
);
6159 newname
= ggc_strdup (tempname
);
6162 /* We need sth that can be pointed to for va_start. */
6163 decl
= build_fake_var_decl (ptr_type_node
);
6165 argvi
= new_var_info (decl
, newname
, false);
6166 argvi
->offset
= fi_parm_base
+ num_args
;
6168 argvi
->is_full_var
= true;
6169 argvi
->is_heap_var
= true;
6170 argvi
->fullsize
= vi
->fullsize
;
6173 && argvi
->may_have_pointers
)
6174 make_constraint_from (argvi
, nonlocal_id
);
6176 gcc_assert (prev_vi
->offset
< argvi
->offset
);
6177 prev_vi
->next
= argvi
->id
;
6184 /* Return true if FIELDSTACK contains fields that overlap.
6185 FIELDSTACK is assumed to be sorted by offset. */
6188 check_for_overlaps (const vec
<fieldoff_s
> &fieldstack
)
6190 fieldoff_s
*fo
= NULL
;
6192 HOST_WIDE_INT lastoffset
= -1;
6194 FOR_EACH_VEC_ELT (fieldstack
, i
, fo
)
6196 if (fo
->offset
== lastoffset
)
6198 lastoffset
= fo
->offset
;
6203 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
6204 This will also create any varinfo structures necessary for fields
6205 of DECL. DECL is a function parameter if HANDLE_PARAM is set.
6206 HANDLED_STRUCT_TYPE is used to register struct types reached by following
6207 restrict pointers. This is needed to prevent infinite recursion.
6208 If ADD_RESTRICT, pretend that the pointer NAME is restrict even if DECL
6209 does not advertise it. */
6212 create_variable_info_for_1 (tree decl
, const char *name
, bool add_id
,
6213 bool handle_param
, bitmap handled_struct_type
,
6214 bool add_restrict
= false)
6216 varinfo_t vi
, newvi
;
6217 tree decl_type
= TREE_TYPE (decl
);
6218 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decl_type
);
6219 auto_vec
<fieldoff_s
> fieldstack
;
6224 || !tree_fits_uhwi_p (declsize
))
6226 vi
= new_var_info (decl
, name
, add_id
);
6230 vi
->is_unknown_size_var
= true;
6231 vi
->is_full_var
= true;
6232 vi
->may_have_pointers
= true;
6236 /* Collect field information. */
6237 if (use_field_sensitive
6238 && var_can_have_subvars (decl
)
6239 /* ??? Force us to not use subfields for globals in IPA mode.
6240 Else we'd have to parse arbitrary initializers. */
6242 && is_global_var (decl
)))
6244 fieldoff_s
*fo
= NULL
;
6245 bool notokay
= false;
6248 push_fields_onto_fieldstack (decl_type
, &fieldstack
, 0);
6250 for (i
= 0; !notokay
&& fieldstack
.iterate (i
, &fo
); i
++)
6251 if (fo
->has_unknown_size
6258 /* We can't sort them if we have a field with a variable sized type,
6259 which will make notokay = true. In that case, we are going to return
6260 without creating varinfos for the fields anyway, so sorting them is a
6264 sort_fieldstack (fieldstack
);
6265 /* Due to some C++ FE issues, like PR 22488, we might end up
6266 what appear to be overlapping fields even though they,
6267 in reality, do not overlap. Until the C++ FE is fixed,
6268 we will simply disable field-sensitivity for these cases. */
6269 notokay
= check_for_overlaps (fieldstack
);
6273 fieldstack
.release ();
6276 /* If we didn't end up collecting sub-variables create a full
6277 variable for the decl. */
6278 if (fieldstack
.length () == 0
6279 || fieldstack
.length () > (unsigned)param_max_fields_for_field_sensitive
)
6281 vi
= new_var_info (decl
, name
, add_id
);
6283 vi
->may_have_pointers
= true;
6284 vi
->fullsize
= tree_to_uhwi (declsize
);
6285 vi
->size
= vi
->fullsize
;
6286 vi
->is_full_var
= true;
6287 if (POINTER_TYPE_P (decl_type
)
6288 && (TYPE_RESTRICT (decl_type
) || add_restrict
))
6289 vi
->only_restrict_pointers
= 1;
6290 if (vi
->only_restrict_pointers
6291 && !type_contains_placeholder_p (TREE_TYPE (decl_type
))
6293 && !bitmap_bit_p (handled_struct_type
,
6294 TYPE_UID (TREE_TYPE (decl_type
))))
6297 tree heapvar
= build_fake_var_decl (TREE_TYPE (decl_type
));
6298 DECL_EXTERNAL (heapvar
) = 1;
6299 if (var_can_have_subvars (heapvar
))
6300 bitmap_set_bit (handled_struct_type
,
6301 TYPE_UID (TREE_TYPE (decl_type
)));
6302 rvi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS", true,
6303 true, handled_struct_type
);
6304 if (var_can_have_subvars (heapvar
))
6305 bitmap_clear_bit (handled_struct_type
,
6306 TYPE_UID (TREE_TYPE (decl_type
)));
6307 rvi
->is_restrict_var
= 1;
6308 insert_vi_for_tree (heapvar
, rvi
);
6309 make_constraint_from (vi
, rvi
->id
);
6310 make_param_constraints (rvi
);
6312 fieldstack
.release ();
6316 vi
= new_var_info (decl
, name
, add_id
);
6317 vi
->fullsize
= tree_to_uhwi (declsize
);
6318 if (fieldstack
.length () == 1)
6319 vi
->is_full_var
= true;
6320 for (i
= 0, newvi
= vi
;
6321 fieldstack
.iterate (i
, &fo
);
6322 ++i
, newvi
= vi_next (newvi
))
6324 const char *newname
= NULL
;
6329 if (fieldstack
.length () != 1)
6332 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC
6333 "+" HOST_WIDE_INT_PRINT_DEC
, name
,
6334 fo
->offset
, fo
->size
);
6335 newname
= ggc_strdup (tempname
);
6343 newvi
->name
= newname
;
6344 newvi
->offset
= fo
->offset
;
6345 newvi
->size
= fo
->size
;
6346 newvi
->fullsize
= vi
->fullsize
;
6347 newvi
->may_have_pointers
= fo
->may_have_pointers
;
6348 newvi
->only_restrict_pointers
= fo
->only_restrict_pointers
;
6350 && newvi
->only_restrict_pointers
6351 && !type_contains_placeholder_p (fo
->restrict_pointed_type
)
6352 && !bitmap_bit_p (handled_struct_type
,
6353 TYPE_UID (fo
->restrict_pointed_type
)))
6356 tree heapvar
= build_fake_var_decl (fo
->restrict_pointed_type
);
6357 DECL_EXTERNAL (heapvar
) = 1;
6358 if (var_can_have_subvars (heapvar
))
6359 bitmap_set_bit (handled_struct_type
,
6360 TYPE_UID (fo
->restrict_pointed_type
));
6361 rvi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS", true,
6362 true, handled_struct_type
);
6363 if (var_can_have_subvars (heapvar
))
6364 bitmap_clear_bit (handled_struct_type
,
6365 TYPE_UID (fo
->restrict_pointed_type
));
6366 rvi
->is_restrict_var
= 1;
6367 insert_vi_for_tree (heapvar
, rvi
);
6368 make_constraint_from (newvi
, rvi
->id
);
6369 make_param_constraints (rvi
);
6371 if (i
+ 1 < fieldstack
.length ())
6373 varinfo_t tem
= new_var_info (decl
, name
, false);
6374 newvi
->next
= tem
->id
;
6383 create_variable_info_for (tree decl
, const char *name
, bool add_id
)
6385 /* First see if we are dealing with an ifunc resolver call and
6386 assiociate that with a call to the resolver function result. */
6389 && TREE_CODE (decl
) == FUNCTION_DECL
6390 && (node
= cgraph_node::get (decl
))
6391 && node
->ifunc_resolver
)
6393 varinfo_t fi
= get_vi_for_tree (node
->get_alias_target ()->decl
);
6395 = get_function_part_constraint (fi
, fi_result
);
6396 fi
= new_var_info (NULL_TREE
, "ifuncres", true);
6397 fi
->is_reg_var
= true;
6398 constraint_expr lhs
;
6402 process_constraint (new_constraint (lhs
, rhs
));
6403 insert_vi_for_tree (decl
, fi
);
6407 varinfo_t vi
= create_variable_info_for_1 (decl
, name
, add_id
, false, NULL
);
6408 unsigned int id
= vi
->id
;
6410 insert_vi_for_tree (decl
, vi
);
6415 /* Create initial constraints for globals. */
6416 for (; vi
; vi
= vi_next (vi
))
6418 if (!vi
->may_have_pointers
6419 || !vi
->is_global_var
)
6422 /* Mark global restrict qualified pointers. */
6423 if ((POINTER_TYPE_P (TREE_TYPE (decl
))
6424 && TYPE_RESTRICT (TREE_TYPE (decl
)))
6425 || vi
->only_restrict_pointers
)
6428 = make_constraint_from_global_restrict (vi
, "GLOBAL_RESTRICT",
6430 /* ??? For now exclude reads from globals as restrict sources
6431 if those are not (indirectly) from incoming parameters. */
6432 rvi
->is_restrict_var
= false;
6436 /* In non-IPA mode the initializer from nonlocal is all we need. */
6438 || DECL_HARD_REGISTER (decl
))
6439 make_copy_constraint (vi
, nonlocal_id
);
6441 /* In IPA mode parse the initializer and generate proper constraints
6445 varpool_node
*vnode
= varpool_node::get (decl
);
6447 /* For escaped variables initialize them from nonlocal. */
6448 if (!vnode
->all_refs_explicit_p ())
6449 make_copy_constraint (vi
, nonlocal_id
);
6451 /* If this is a global variable with an initializer and we are in
6452 IPA mode generate constraints for it. */
6454 for (unsigned idx
= 0; vnode
->iterate_reference (idx
, ref
); ++idx
)
6456 auto_vec
<ce_s
> rhsc
;
6457 struct constraint_expr lhs
, *rhsp
;
6459 get_constraint_for_address_of (ref
->referred
->decl
, &rhsc
);
6463 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
6464 process_constraint (new_constraint (lhs
, *rhsp
));
6465 /* If this is a variable that escapes from the unit
6466 the initializer escapes as well. */
6467 if (!vnode
->all_refs_explicit_p ())
6469 lhs
.var
= escaped_id
;
6472 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
6473 process_constraint (new_constraint (lhs
, *rhsp
));
6482 /* Print out the points-to solution for VAR to FILE. */
6485 dump_solution_for_var (FILE *file
, unsigned int var
)
6487 varinfo_t vi
= get_varinfo (var
);
6491 /* Dump the solution for unified vars anyway, this avoids difficulties
6492 in scanning dumps in the testsuite. */
6493 fprintf (file
, "%s = { ", vi
->name
);
6494 vi
= get_varinfo (find (var
));
6495 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6496 fprintf (file
, "%s ", get_varinfo (i
)->name
);
6497 fprintf (file
, "}");
6499 /* But note when the variable was unified. */
6501 fprintf (file
, " same as %s", vi
->name
);
6503 fprintf (file
, "\n");
6506 /* Print the points-to solution for VAR to stderr. */
6509 debug_solution_for_var (unsigned int var
)
6511 dump_solution_for_var (stderr
, var
);
6514 /* Register the constraints for function parameter related VI. */
6517 make_param_constraints (varinfo_t vi
)
6519 for (; vi
; vi
= vi_next (vi
))
6521 if (vi
->only_restrict_pointers
)
6523 else if (vi
->may_have_pointers
)
6524 make_constraint_from (vi
, nonlocal_id
);
6526 if (vi
->is_full_var
)
6531 /* Create varinfo structures for all of the variables in the
6532 function for intraprocedural mode. */
6535 intra_create_variable_infos (struct function
*fn
)
6538 bitmap handled_struct_type
= NULL
;
6539 bool this_parm_in_ctor
= DECL_CXX_CONSTRUCTOR_P (fn
->decl
);
6541 /* For each incoming pointer argument arg, create the constraint ARG
6542 = NONLOCAL or a dummy variable if it is a restrict qualified
6543 passed-by-reference argument. */
6544 for (t
= DECL_ARGUMENTS (fn
->decl
); t
; t
= DECL_CHAIN (t
))
6546 if (handled_struct_type
== NULL
)
6547 handled_struct_type
= BITMAP_ALLOC (NULL
);
6550 = create_variable_info_for_1 (t
, alias_get_name (t
), false, true,
6551 handled_struct_type
, this_parm_in_ctor
);
6552 insert_vi_for_tree (t
, p
);
6554 make_param_constraints (p
);
6556 this_parm_in_ctor
= false;
6559 if (handled_struct_type
!= NULL
)
6560 BITMAP_FREE (handled_struct_type
);
6562 /* Add a constraint for a result decl that is passed by reference. */
6563 if (DECL_RESULT (fn
->decl
)
6564 && DECL_BY_REFERENCE (DECL_RESULT (fn
->decl
)))
6566 varinfo_t p
, result_vi
= get_vi_for_tree (DECL_RESULT (fn
->decl
));
6568 for (p
= result_vi
; p
; p
= vi_next (p
))
6569 make_constraint_from (p
, nonlocal_id
);
6572 /* Add a constraint for the incoming static chain parameter. */
6573 if (fn
->static_chain_decl
!= NULL_TREE
)
6575 varinfo_t p
, chain_vi
= get_vi_for_tree (fn
->static_chain_decl
);
6577 for (p
= chain_vi
; p
; p
= vi_next (p
))
6578 make_constraint_from (p
, nonlocal_id
);
6582 /* Structure used to put solution bitmaps in a hashtable so they can
6583 be shared among variables with the same points-to set. */
6585 typedef struct shared_bitmap_info
6589 } *shared_bitmap_info_t
;
6590 typedef const struct shared_bitmap_info
*const_shared_bitmap_info_t
;
6592 /* Shared_bitmap hashtable helpers. */
6594 struct shared_bitmap_hasher
: free_ptr_hash
<shared_bitmap_info
>
6596 static inline hashval_t
hash (const shared_bitmap_info
*);
6597 static inline bool equal (const shared_bitmap_info
*,
6598 const shared_bitmap_info
*);
6601 /* Hash function for a shared_bitmap_info_t */
6604 shared_bitmap_hasher::hash (const shared_bitmap_info
*bi
)
6606 return bi
->hashcode
;
6609 /* Equality function for two shared_bitmap_info_t's. */
6612 shared_bitmap_hasher::equal (const shared_bitmap_info
*sbi1
,
6613 const shared_bitmap_info
*sbi2
)
6615 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
6618 /* Shared_bitmap hashtable. */
6620 static hash_table
<shared_bitmap_hasher
> *shared_bitmap_table
;
6622 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
6623 existing instance if there is one, NULL otherwise. */
6626 shared_bitmap_lookup (bitmap pt_vars
)
6628 shared_bitmap_info
**slot
;
6629 struct shared_bitmap_info sbi
;
6631 sbi
.pt_vars
= pt_vars
;
6632 sbi
.hashcode
= bitmap_hash (pt_vars
);
6634 slot
= shared_bitmap_table
->find_slot (&sbi
, NO_INSERT
);
6638 return (*slot
)->pt_vars
;
6642 /* Add a bitmap to the shared bitmap hashtable. */
6645 shared_bitmap_add (bitmap pt_vars
)
6647 shared_bitmap_info
**slot
;
6648 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
6650 sbi
->pt_vars
= pt_vars
;
6651 sbi
->hashcode
= bitmap_hash (pt_vars
);
6653 slot
= shared_bitmap_table
->find_slot (sbi
, INSERT
);
6654 gcc_assert (!*slot
);
6659 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
6662 set_uids_in_ptset (bitmap into
, bitmap from
, struct pt_solution
*pt
,
6667 varinfo_t escaped_vi
= get_varinfo (find (escaped_id
));
6668 bool everything_escaped
6669 = escaped_vi
->solution
&& bitmap_bit_p (escaped_vi
->solution
, anything_id
);
6671 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
6673 varinfo_t vi
= get_varinfo (i
);
6675 if (vi
->is_artificial_var
)
6678 if (everything_escaped
6679 || (escaped_vi
->solution
6680 && bitmap_bit_p (escaped_vi
->solution
, i
)))
6682 pt
->vars_contains_escaped
= true;
6683 pt
->vars_contains_escaped_heap
|= vi
->is_heap_var
;
6686 if (vi
->is_restrict_var
)
6687 pt
->vars_contains_restrict
= true;
6689 if (VAR_P (vi
->decl
)
6690 || TREE_CODE (vi
->decl
) == PARM_DECL
6691 || TREE_CODE (vi
->decl
) == RESULT_DECL
)
6693 /* If we are in IPA mode we will not recompute points-to
6694 sets after inlining so make sure they stay valid. */
6696 && !DECL_PT_UID_SET_P (vi
->decl
))
6697 SET_DECL_PT_UID (vi
->decl
, DECL_UID (vi
->decl
));
6699 /* Add the decl to the points-to set. Note that the points-to
6700 set contains global variables. */
6701 bitmap_set_bit (into
, DECL_PT_UID (vi
->decl
));
6702 if (vi
->is_global_var
6703 /* In IPA mode the escaped_heap trick doesn't work as
6704 ESCAPED is escaped from the unit but
6705 pt_solution_includes_global needs to answer true for
6706 all variables not automatic within a function.
6707 For the same reason is_global_var is not the
6708 correct flag to track - local variables from other
6709 functions also need to be considered global.
6710 Conveniently all HEAP vars are not put in function
6714 && ! auto_var_in_fn_p (vi
->decl
, fndecl
)))
6715 pt
->vars_contains_nonlocal
= true;
6717 /* If we have a variable that is interposable record that fact
6718 for pointer comparison simplification. */
6719 if (VAR_P (vi
->decl
)
6720 && (TREE_STATIC (vi
->decl
) || DECL_EXTERNAL (vi
->decl
))
6721 && ! decl_binds_to_current_def_p (vi
->decl
))
6722 pt
->vars_contains_interposable
= true;
6724 /* If this is a local variable we can have overlapping lifetime
6725 of different function invocations through recursion duplicate
6726 it with its shadow variable. */
6728 && vi
->shadow_var_uid
!= 0)
6730 bitmap_set_bit (into
, vi
->shadow_var_uid
);
6731 pt
->vars_contains_nonlocal
= true;
6735 else if (TREE_CODE (vi
->decl
) == FUNCTION_DECL
6736 || TREE_CODE (vi
->decl
) == LABEL_DECL
)
6738 /* Nothing should read/write from/to code so we can
6739 save bits by not including them in the points-to bitmaps.
6740 Still mark the points-to set as containing global memory
6741 to make code-patching possible - see PR70128. */
6742 pt
->vars_contains_nonlocal
= true;
6748 /* Compute the points-to solution *PT for the variable VI. */
6750 static struct pt_solution
6751 find_what_var_points_to (tree fndecl
, varinfo_t orig_vi
)
6755 bitmap finished_solution
;
6758 struct pt_solution
*pt
;
6760 /* This variable may have been collapsed, let's get the real
6762 vi
= get_varinfo (find (orig_vi
->id
));
6764 /* See if we have already computed the solution and return it. */
6765 pt_solution
**slot
= &final_solutions
->get_or_insert (vi
);
6769 *slot
= pt
= XOBNEW (&final_solutions_obstack
, struct pt_solution
);
6770 memset (pt
, 0, sizeof (struct pt_solution
));
6772 /* Translate artificial variables into SSA_NAME_PTR_INFO
6774 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6776 varinfo_t vi
= get_varinfo (i
);
6778 if (vi
->is_artificial_var
)
6780 if (vi
->id
== nothing_id
)
6782 else if (vi
->id
== escaped_id
)
6785 pt
->ipa_escaped
= 1;
6788 /* Expand some special vars of ESCAPED in-place here. */
6789 varinfo_t evi
= get_varinfo (find (escaped_id
));
6790 if (bitmap_bit_p (evi
->solution
, nonlocal_id
))
6793 else if (vi
->id
== nonlocal_id
)
6795 else if (vi
->id
== string_id
)
6796 /* Nobody cares - STRING_CSTs are read-only entities. */
6798 else if (vi
->id
== anything_id
6799 || vi
->id
== integer_id
)
6804 /* Instead of doing extra work, simply do not create
6805 elaborate points-to information for pt_anything pointers. */
6809 /* Share the final set of variables when possible. */
6810 finished_solution
= BITMAP_GGC_ALLOC ();
6811 stats
.points_to_sets_created
++;
6813 set_uids_in_ptset (finished_solution
, vi
->solution
, pt
, fndecl
);
6814 result
= shared_bitmap_lookup (finished_solution
);
6817 shared_bitmap_add (finished_solution
);
6818 pt
->vars
= finished_solution
;
6823 bitmap_clear (finished_solution
);
6829 /* Given a pointer variable P, fill in its points-to set. */
6832 find_what_p_points_to (tree fndecl
, tree p
)
6834 struct ptr_info_def
*pi
;
6838 get_range_query (DECL_STRUCT_FUNCTION (fndecl
))->range_of_expr (vr
, p
);
6839 bool nonnull
= vr
.nonzero_p ();
6841 /* For parameters, get at the points-to set for the actual parm
6843 if (TREE_CODE (p
) == SSA_NAME
6844 && SSA_NAME_IS_DEFAULT_DEF (p
)
6845 && (TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
6846 || TREE_CODE (SSA_NAME_VAR (p
)) == RESULT_DECL
))
6847 lookup_p
= SSA_NAME_VAR (p
);
6849 vi
= lookup_vi_for_tree (lookup_p
);
6853 pi
= get_ptr_info (p
);
6854 pi
->pt
= find_what_var_points_to (fndecl
, vi
);
6855 /* Conservatively set to NULL from PTA (to true). */
6857 /* Preserve pointer nonnull globally computed. */
6859 set_ptr_nonnull (p
);
6863 /* Query statistics for points-to solutions. */
6866 unsigned HOST_WIDE_INT pt_solution_includes_may_alias
;
6867 unsigned HOST_WIDE_INT pt_solution_includes_no_alias
;
6868 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias
;
6869 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias
;
6873 dump_pta_stats (FILE *s
)
6875 fprintf (s
, "\nPTA query stats:\n");
6876 fprintf (s
, " pt_solution_includes: "
6877 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6878 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6879 pta_stats
.pt_solution_includes_no_alias
,
6880 pta_stats
.pt_solution_includes_no_alias
6881 + pta_stats
.pt_solution_includes_may_alias
);
6882 fprintf (s
, " pt_solutions_intersect: "
6883 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6884 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6885 pta_stats
.pt_solutions_intersect_no_alias
,
6886 pta_stats
.pt_solutions_intersect_no_alias
6887 + pta_stats
.pt_solutions_intersect_may_alias
);
6891 /* Reset the points-to solution *PT to a conservative default
6892 (point to anything). */
6895 pt_solution_reset (struct pt_solution
*pt
)
6897 memset (pt
, 0, sizeof (struct pt_solution
));
6898 pt
->anything
= true;
6902 /* Set the points-to solution *PT to point only to the variables
6903 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6904 global variables and VARS_CONTAINS_RESTRICT specifies whether
6905 it contains restrict tag variables. */
6908 pt_solution_set (struct pt_solution
*pt
, bitmap vars
,
6909 bool vars_contains_nonlocal
)
6911 memset (pt
, 0, sizeof (struct pt_solution
));
6913 pt
->vars_contains_nonlocal
= vars_contains_nonlocal
;
6914 pt
->vars_contains_escaped
6915 = (cfun
->gimple_df
->escaped
.anything
6916 || bitmap_intersect_p (cfun
->gimple_df
->escaped
.vars
, vars
));
6919 /* Set the points-to solution *PT to point only to the variable VAR. */
6922 pt_solution_set_var (struct pt_solution
*pt
, tree var
)
6924 memset (pt
, 0, sizeof (struct pt_solution
));
6925 pt
->vars
= BITMAP_GGC_ALLOC ();
6926 bitmap_set_bit (pt
->vars
, DECL_PT_UID (var
));
6927 pt
->vars_contains_nonlocal
= is_global_var (var
);
6928 pt
->vars_contains_escaped
6929 = (cfun
->gimple_df
->escaped
.anything
6930 || bitmap_bit_p (cfun
->gimple_df
->escaped
.vars
, DECL_PT_UID (var
)));
6933 /* Computes the union of the points-to solutions *DEST and *SRC and
6934 stores the result in *DEST. This changes the points-to bitmap
6935 of *DEST and thus may not be used if that might be shared.
6936 The points-to bitmap of *SRC and *DEST will not be shared after
6937 this function if they were not before. */
6940 pt_solution_ior_into (struct pt_solution
*dest
, struct pt_solution
*src
)
6942 dest
->anything
|= src
->anything
;
6945 pt_solution_reset (dest
);
6949 dest
->nonlocal
|= src
->nonlocal
;
6950 dest
->escaped
|= src
->escaped
;
6951 dest
->ipa_escaped
|= src
->ipa_escaped
;
6952 dest
->null
|= src
->null
;
6953 dest
->vars_contains_nonlocal
|= src
->vars_contains_nonlocal
;
6954 dest
->vars_contains_escaped
|= src
->vars_contains_escaped
;
6955 dest
->vars_contains_escaped_heap
|= src
->vars_contains_escaped_heap
;
6960 dest
->vars
= BITMAP_GGC_ALLOC ();
6961 bitmap_ior_into (dest
->vars
, src
->vars
);
6964 /* Return true if the points-to solution *PT is empty. */
6967 pt_solution_empty_p (const pt_solution
*pt
)
6974 && !bitmap_empty_p (pt
->vars
))
6977 /* If the solution includes ESCAPED, check if that is empty. */
6979 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
6982 /* If the solution includes ESCAPED, check if that is empty. */
6984 && !pt_solution_empty_p (&ipa_escaped_pt
))
6990 /* Return true if the points-to solution *PT only point to a single var, and
6991 return the var uid in *UID. */
6994 pt_solution_singleton_or_null_p (struct pt_solution
*pt
, unsigned *uid
)
6996 if (pt
->anything
|| pt
->nonlocal
|| pt
->escaped
|| pt
->ipa_escaped
6998 || !bitmap_single_bit_set_p (pt
->vars
))
7001 *uid
= bitmap_first_set_bit (pt
->vars
);
7005 /* Return true if the points-to solution *PT includes global memory.
7006 If ESCAPED_LOCAL_P is true then escaped local variables are also
7007 considered global. */
7010 pt_solution_includes_global (struct pt_solution
*pt
, bool escaped_local_p
)
7014 || pt
->vars_contains_nonlocal
7015 /* The following is a hack to make the malloc escape hack work.
7016 In reality we'd need different sets for escaped-through-return
7017 and escaped-to-callees and passes would need to be updated. */
7018 || pt
->vars_contains_escaped_heap
)
7021 if (escaped_local_p
&& pt
->vars_contains_escaped
)
7024 /* 'escaped' is also a placeholder so we have to look into it. */
7026 return pt_solution_includes_global (&cfun
->gimple_df
->escaped
,
7029 if (pt
->ipa_escaped
)
7030 return pt_solution_includes_global (&ipa_escaped_pt
,
7036 /* Return true if the points-to solution *PT includes the variable
7037 declaration DECL. */
7040 pt_solution_includes_1 (struct pt_solution
*pt
, const_tree decl
)
7046 && is_global_var (decl
))
7050 && bitmap_bit_p (pt
->vars
, DECL_PT_UID (decl
)))
7053 /* If the solution includes ESCAPED, check it. */
7055 && pt_solution_includes_1 (&cfun
->gimple_df
->escaped
, decl
))
7058 /* If the solution includes ESCAPED, check it. */
7060 && pt_solution_includes_1 (&ipa_escaped_pt
, decl
))
7067 pt_solution_includes (struct pt_solution
*pt
, const_tree decl
)
7069 bool res
= pt_solution_includes_1 (pt
, decl
);
7071 ++pta_stats
.pt_solution_includes_may_alias
;
7073 ++pta_stats
.pt_solution_includes_no_alias
;
7077 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
7081 pt_solutions_intersect_1 (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
7083 if (pt1
->anything
|| pt2
->anything
)
7086 /* If either points to unknown global memory and the other points to
7087 any global memory they alias. */
7090 || pt2
->vars_contains_nonlocal
))
7092 && pt1
->vars_contains_nonlocal
))
7095 /* If either points to all escaped memory and the other points to
7096 any escaped memory they alias. */
7099 || pt2
->vars_contains_escaped
))
7101 && pt1
->vars_contains_escaped
))
7104 /* Check the escaped solution if required.
7105 ??? Do we need to check the local against the IPA escaped sets? */
7106 if ((pt1
->ipa_escaped
|| pt2
->ipa_escaped
)
7107 && !pt_solution_empty_p (&ipa_escaped_pt
))
7109 /* If both point to escaped memory and that solution
7110 is not empty they alias. */
7111 if (pt1
->ipa_escaped
&& pt2
->ipa_escaped
)
7114 /* If either points to escaped memory see if the escaped solution
7115 intersects with the other. */
7116 if ((pt1
->ipa_escaped
7117 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt2
))
7118 || (pt2
->ipa_escaped
7119 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt1
)))
7123 /* Now both pointers alias if their points-to solution intersects. */
7126 && bitmap_intersect_p (pt1
->vars
, pt2
->vars
));
7130 pt_solutions_intersect (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
7132 bool res
= pt_solutions_intersect_1 (pt1
, pt2
);
7134 ++pta_stats
.pt_solutions_intersect_may_alias
;
7136 ++pta_stats
.pt_solutions_intersect_no_alias
;
7140 /* Dump stats information to OUTFILE. */
7143 dump_sa_stats (FILE *outfile
)
7145 fprintf (outfile
, "Points-to Stats:\n");
7146 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
7147 fprintf (outfile
, "Non-pointer vars: %d\n",
7148 stats
.nonpointer_vars
);
7149 fprintf (outfile
, "Statically unified vars: %d\n",
7150 stats
.unified_vars_static
);
7151 fprintf (outfile
, "Dynamically unified vars: %d\n",
7152 stats
.unified_vars_dynamic
);
7153 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
7154 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
7155 fprintf (outfile
, "Number of implicit edges: %d\n",
7156 stats
.num_implicit_edges
);
7157 fprintf (outfile
, "Number of avoided edges: %d\n",
7158 stats
.num_avoided_edges
);
7161 /* Dump points-to information to OUTFILE. */
7164 dump_sa_points_to_info (FILE *outfile
)
7166 fprintf (outfile
, "\nPoints-to sets\n\n");
7168 for (unsigned i
= 1; i
< varmap
.length (); i
++)
7170 varinfo_t vi
= get_varinfo (i
);
7171 if (!vi
->may_have_pointers
)
7173 dump_solution_for_var (outfile
, i
);
7178 /* Debug points-to information to stderr. */
7181 debug_sa_points_to_info (void)
7183 dump_sa_points_to_info (stderr
);
7187 /* Initialize the always-existing constraint variables for NULL
7188 ANYTHING, READONLY, and INTEGER */
7191 init_base_vars (void)
7193 struct constraint_expr lhs
, rhs
;
7194 varinfo_t var_anything
;
7195 varinfo_t var_nothing
;
7196 varinfo_t var_string
;
7197 varinfo_t var_escaped
;
7198 varinfo_t var_nonlocal
;
7199 varinfo_t var_storedanything
;
7200 varinfo_t var_integer
;
7202 /* Variable ID zero is reserved and should be NULL. */
7203 varmap
.safe_push (NULL
);
7205 /* Create the NULL variable, used to represent that a variable points
7207 var_nothing
= new_var_info (NULL_TREE
, "NULL", false);
7208 gcc_assert (var_nothing
->id
== nothing_id
);
7209 var_nothing
->is_artificial_var
= 1;
7210 var_nothing
->offset
= 0;
7211 var_nothing
->size
= ~0;
7212 var_nothing
->fullsize
= ~0;
7213 var_nothing
->is_special_var
= 1;
7214 var_nothing
->may_have_pointers
= 0;
7215 var_nothing
->is_global_var
= 0;
7217 /* Create the ANYTHING variable, used to represent that a variable
7218 points to some unknown piece of memory. */
7219 var_anything
= new_var_info (NULL_TREE
, "ANYTHING", false);
7220 gcc_assert (var_anything
->id
== anything_id
);
7221 var_anything
->is_artificial_var
= 1;
7222 var_anything
->size
= ~0;
7223 var_anything
->offset
= 0;
7224 var_anything
->fullsize
= ~0;
7225 var_anything
->is_special_var
= 1;
7227 /* Anything points to anything. This makes deref constraints just
7228 work in the presence of linked list and other p = *p type loops,
7229 by saying that *ANYTHING = ANYTHING. */
7231 lhs
.var
= anything_id
;
7233 rhs
.type
= ADDRESSOF
;
7234 rhs
.var
= anything_id
;
7237 /* This specifically does not use process_constraint because
7238 process_constraint ignores all anything = anything constraints, since all
7239 but this one are redundant. */
7240 constraints
.safe_push (new_constraint (lhs
, rhs
));
7242 /* Create the STRING variable, used to represent that a variable
7243 points to a string literal. String literals don't contain
7244 pointers so STRING doesn't point to anything. */
7245 var_string
= new_var_info (NULL_TREE
, "STRING", false);
7246 gcc_assert (var_string
->id
== string_id
);
7247 var_string
->is_artificial_var
= 1;
7248 var_string
->offset
= 0;
7249 var_string
->size
= ~0;
7250 var_string
->fullsize
= ~0;
7251 var_string
->is_special_var
= 1;
7252 var_string
->may_have_pointers
= 0;
7254 /* Create the ESCAPED variable, used to represent the set of escaped
7256 var_escaped
= new_var_info (NULL_TREE
, "ESCAPED", false);
7257 gcc_assert (var_escaped
->id
== escaped_id
);
7258 var_escaped
->is_artificial_var
= 1;
7259 var_escaped
->offset
= 0;
7260 var_escaped
->size
= ~0;
7261 var_escaped
->fullsize
= ~0;
7262 var_escaped
->is_special_var
= 0;
7264 /* Create the NONLOCAL variable, used to represent the set of nonlocal
7266 var_nonlocal
= new_var_info (NULL_TREE
, "NONLOCAL", false);
7267 gcc_assert (var_nonlocal
->id
== nonlocal_id
);
7268 var_nonlocal
->is_artificial_var
= 1;
7269 var_nonlocal
->offset
= 0;
7270 var_nonlocal
->size
= ~0;
7271 var_nonlocal
->fullsize
= ~0;
7272 var_nonlocal
->is_special_var
= 1;
7274 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
7276 lhs
.var
= escaped_id
;
7279 rhs
.var
= escaped_id
;
7281 process_constraint (new_constraint (lhs
, rhs
));
7283 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
7284 whole variable escapes. */
7286 lhs
.var
= escaped_id
;
7289 rhs
.var
= escaped_id
;
7290 rhs
.offset
= UNKNOWN_OFFSET
;
7291 process_constraint (new_constraint (lhs
, rhs
));
7293 /* *ESCAPED = NONLOCAL. This is true because we have to assume
7294 everything pointed to by escaped points to what global memory can
7297 lhs
.var
= escaped_id
;
7300 rhs
.var
= nonlocal_id
;
7302 process_constraint (new_constraint (lhs
, rhs
));
7304 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
7305 global memory may point to global memory and escaped memory. */
7307 lhs
.var
= nonlocal_id
;
7309 rhs
.type
= ADDRESSOF
;
7310 rhs
.var
= nonlocal_id
;
7312 process_constraint (new_constraint (lhs
, rhs
));
7313 rhs
.type
= ADDRESSOF
;
7314 rhs
.var
= escaped_id
;
7316 process_constraint (new_constraint (lhs
, rhs
));
7318 /* Create the STOREDANYTHING variable, used to represent the set of
7319 variables stored to *ANYTHING. */
7320 var_storedanything
= new_var_info (NULL_TREE
, "STOREDANYTHING", false);
7321 gcc_assert (var_storedanything
->id
== storedanything_id
);
7322 var_storedanything
->is_artificial_var
= 1;
7323 var_storedanything
->offset
= 0;
7324 var_storedanything
->size
= ~0;
7325 var_storedanything
->fullsize
= ~0;
7326 var_storedanything
->is_special_var
= 0;
7328 /* Create the INTEGER variable, used to represent that a variable points
7329 to what an INTEGER "points to". */
7330 var_integer
= new_var_info (NULL_TREE
, "INTEGER", false);
7331 gcc_assert (var_integer
->id
== integer_id
);
7332 var_integer
->is_artificial_var
= 1;
7333 var_integer
->size
= ~0;
7334 var_integer
->fullsize
= ~0;
7335 var_integer
->offset
= 0;
7336 var_integer
->is_special_var
= 1;
7338 /* INTEGER = ANYTHING, because we don't know where a dereference of
7339 a random integer will point to. */
7341 lhs
.var
= integer_id
;
7343 rhs
.type
= ADDRESSOF
;
7344 rhs
.var
= anything_id
;
7346 process_constraint (new_constraint (lhs
, rhs
));
7349 /* Initialize things necessary to perform PTA */
7352 init_alias_vars (void)
7354 use_field_sensitive
= (param_max_fields_for_field_sensitive
> 1);
7356 bitmap_obstack_initialize (&pta_obstack
);
7357 bitmap_obstack_initialize (&oldpta_obstack
);
7358 bitmap_obstack_initialize (&predbitmap_obstack
);
7360 constraints
.create (8);
7362 vi_for_tree
= new hash_map
<tree
, varinfo_t
>;
7363 call_stmt_vars
= new hash_map
<gimple
*, varinfo_t
>;
7365 memset (&stats
, 0, sizeof (stats
));
7366 shared_bitmap_table
= new hash_table
<shared_bitmap_hasher
> (511);
7369 gcc_obstack_init (&fake_var_decl_obstack
);
7371 final_solutions
= new hash_map
<varinfo_t
, pt_solution
*>;
7372 gcc_obstack_init (&final_solutions_obstack
);
7375 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
7376 predecessor edges. */
7379 remove_preds_and_fake_succs (constraint_graph_t graph
)
7383 /* Clear the implicit ref and address nodes from the successor
7385 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
7387 if (graph
->succs
[i
])
7388 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
7389 FIRST_REF_NODE
* 2);
7392 /* Free the successor list for the non-ref nodes. */
7393 for (i
= FIRST_REF_NODE
+ 1; i
< graph
->size
; i
++)
7395 if (graph
->succs
[i
])
7396 BITMAP_FREE (graph
->succs
[i
]);
7399 /* Now reallocate the size of the successor list as, and blow away
7400 the predecessor bitmaps. */
7401 graph
->size
= varmap
.length ();
7402 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
7404 free (graph
->implicit_preds
);
7405 graph
->implicit_preds
= NULL
;
7406 free (graph
->preds
);
7407 graph
->preds
= NULL
;
7408 bitmap_obstack_release (&predbitmap_obstack
);
7411 /* Solve the constraint set. */
7414 solve_constraints (void)
7418 /* Sort varinfos so that ones that cannot be pointed to are last.
7419 This makes bitmaps more efficient. */
7420 unsigned int *map
= XNEWVEC (unsigned int, varmap
.length ());
7421 for (unsigned i
= 0; i
< integer_id
+ 1; ++i
)
7423 /* Start with address-taken vars, followed by not address-taken vars
7424 to move vars never appearing in the points-to solution bitmaps last. */
7425 unsigned j
= integer_id
+ 1;
7426 for (unsigned i
= integer_id
+ 1; i
< varmap
.length (); ++i
)
7427 if (varmap
[varmap
[i
]->head
]->address_taken
)
7429 for (unsigned i
= integer_id
+ 1; i
< varmap
.length (); ++i
)
7430 if (! varmap
[varmap
[i
]->head
]->address_taken
)
7432 /* Shuffle varmap according to map. */
7433 for (unsigned i
= integer_id
+ 1; i
< varmap
.length (); ++i
)
7435 while (map
[varmap
[i
]->id
] != i
)
7436 std::swap (varmap
[i
], varmap
[map
[varmap
[i
]->id
]]);
7437 gcc_assert (bitmap_empty_p (varmap
[i
]->solution
));
7439 varmap
[i
]->next
= map
[varmap
[i
]->next
];
7440 varmap
[i
]->head
= map
[varmap
[i
]->head
];
7442 /* Finally rewrite constraints. */
7443 for (unsigned i
= 0; i
< constraints
.length (); ++i
)
7445 constraints
[i
]->lhs
.var
= map
[constraints
[i
]->lhs
.var
];
7446 constraints
[i
]->rhs
.var
= map
[constraints
[i
]->rhs
.var
];
7452 "\nCollapsing static cycles and doing variable "
7455 init_graph (varmap
.length () * 2);
7458 fprintf (dump_file
, "Building predecessor graph\n");
7459 build_pred_graph ();
7462 fprintf (dump_file
, "Detecting pointer and location "
7464 si
= perform_var_substitution (graph
);
7467 fprintf (dump_file
, "Rewriting constraints and unifying "
7469 rewrite_constraints (graph
, si
);
7471 build_succ_graph ();
7473 free_var_substitution_info (si
);
7475 /* Attach complex constraints to graph nodes. */
7476 move_complex_constraints (graph
);
7479 fprintf (dump_file
, "Uniting pointer but not location equivalent "
7481 unite_pointer_equivalences (graph
);
7484 fprintf (dump_file
, "Finding indirect cycles\n");
7485 find_indirect_cycles (graph
);
7487 /* Implicit nodes and predecessors are no longer necessary at this
7489 remove_preds_and_fake_succs (graph
);
7491 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
7493 fprintf (dump_file
, "\n\n// The constraint graph before solve-graph "
7494 "in dot format:\n");
7495 dump_constraint_graph (dump_file
);
7496 fprintf (dump_file
, "\n\n");
7500 fprintf (dump_file
, "Solving graph\n");
7502 solve_graph (graph
);
7504 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
7506 fprintf (dump_file
, "\n\n// The constraint graph after solve-graph "
7507 "in dot format:\n");
7508 dump_constraint_graph (dump_file
);
7509 fprintf (dump_file
, "\n\n");
7513 /* Create points-to sets for the current function. See the comments
7514 at the start of the file for an algorithmic overview. */
7517 compute_points_to_sets (void)
7522 timevar_push (TV_TREE_PTA
);
7526 intra_create_variable_infos (cfun
);
7528 /* Now walk all statements and build the constraint set. */
7529 FOR_EACH_BB_FN (bb
, cfun
)
7531 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7534 gphi
*phi
= gsi
.phi ();
7536 if (! virtual_operand_p (gimple_phi_result (phi
)))
7537 find_func_aliases (cfun
, phi
);
7540 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
7543 gimple
*stmt
= gsi_stmt (gsi
);
7545 find_func_aliases (cfun
, stmt
);
7549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7551 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
7552 dump_constraints (dump_file
, 0);
7555 /* From the constraints compute the points-to sets. */
7556 solve_constraints ();
7558 /* Post-process solutions for escapes through returns. */
7561 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
7562 if (greturn
*ret
= safe_dyn_cast
<greturn
*> (*gsi_last_bb (e
->src
)))
7564 tree val
= gimple_return_retval (ret
);
7565 /* ??? Easy to handle simple indirections with some work.
7566 Arbitrary references like foo.bar.baz are more difficult
7567 (but conservatively easy enough with just looking at the base).
7568 Mind to fixup find_func_aliases as well. */
7569 if (!val
|| !SSA_VAR_P (val
))
7571 /* returns happen last in non-IPA so they only influence
7572 the ESCAPED solution and we can filter local variables. */
7573 varinfo_t escaped_vi
= get_varinfo (find (escaped_id
));
7574 varinfo_t vi
= lookup_vi_for_tree (val
);
7575 bitmap delta
= BITMAP_ALLOC (&pta_obstack
);
7578 for (; vi
; vi
= vi_next (vi
))
7580 varinfo_t part_vi
= get_varinfo (find (vi
->id
));
7581 EXECUTE_IF_AND_COMPL_IN_BITMAP (part_vi
->solution
,
7582 escaped_vi
->solution
, 0, i
, bi
)
7584 varinfo_t pointed_to_vi
= get_varinfo (i
);
7585 if (pointed_to_vi
->is_global_var
7586 /* We delay marking of heap memory as global. */
7587 || pointed_to_vi
->is_heap_var
)
7588 bitmap_set_bit (delta
, i
);
7592 /* Now compute the transitive closure. */
7593 bitmap_ior_into (escaped_vi
->solution
, delta
);
7594 bitmap new_delta
= BITMAP_ALLOC (&pta_obstack
);
7595 while (!bitmap_empty_p (delta
))
7597 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, i
, bi
)
7599 varinfo_t pointed_to_vi
= get_varinfo (i
);
7600 pointed_to_vi
= get_varinfo (find (pointed_to_vi
->id
));
7602 bitmap_iterator bi2
;
7603 EXECUTE_IF_AND_COMPL_IN_BITMAP (pointed_to_vi
->solution
,
7604 escaped_vi
->solution
,
7607 varinfo_t pointed_to_vi2
= get_varinfo (j
);
7608 if (pointed_to_vi2
->is_global_var
7609 /* We delay marking of heap memory as global. */
7610 || pointed_to_vi2
->is_heap_var
)
7611 bitmap_set_bit (new_delta
, j
);
7614 bitmap_ior_into (escaped_vi
->solution
, new_delta
);
7615 bitmap_clear (delta
);
7616 std::swap (delta
, new_delta
);
7618 BITMAP_FREE (delta
);
7619 BITMAP_FREE (new_delta
);
7622 if (dump_file
&& (dump_flags
& TDF_STATS
))
7623 dump_sa_stats (dump_file
);
7625 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7626 dump_sa_points_to_info (dump_file
);
7628 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
7629 cfun
->gimple_df
->escaped
= find_what_var_points_to (cfun
->decl
,
7630 get_varinfo (escaped_id
));
7632 /* Make sure the ESCAPED solution (which is used as placeholder in
7633 other solutions) does not reference itself. This simplifies
7634 points-to solution queries. */
7635 cfun
->gimple_df
->escaped
.escaped
= 0;
7637 /* Compute the points-to sets for pointer SSA_NAMEs. */
7641 FOR_EACH_SSA_NAME (i
, ptr
, cfun
)
7643 if (POINTER_TYPE_P (TREE_TYPE (ptr
)))
7644 find_what_p_points_to (cfun
->decl
, ptr
);
7647 /* Compute the call-used/clobbered sets. */
7648 FOR_EACH_BB_FN (bb
, cfun
)
7650 gimple_stmt_iterator gsi
;
7652 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7655 struct pt_solution
*pt
;
7657 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
7661 pt
= gimple_call_use_set (stmt
);
7662 if (gimple_call_flags (stmt
) & ECF_CONST
)
7663 memset (pt
, 0, sizeof (struct pt_solution
));
7666 bool uses_global_memory
= true;
7667 bool reads_global_memory
= true;
7669 determine_global_memory_access (stmt
, NULL
,
7670 &reads_global_memory
,
7671 &uses_global_memory
);
7672 if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
7674 *pt
= find_what_var_points_to (cfun
->decl
, vi
);
7675 /* Escaped (and thus nonlocal) variables are always
7676 implicitly used by calls. */
7677 /* ??? ESCAPED can be empty even though NONLOCAL
7679 if (uses_global_memory
)
7685 else if (uses_global_memory
)
7687 /* If there is nothing special about this call then
7688 we have made everything that is used also escape. */
7689 *pt
= cfun
->gimple_df
->escaped
;
7693 memset (pt
, 0, sizeof (struct pt_solution
));
7696 pt
= gimple_call_clobber_set (stmt
);
7697 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
7698 memset (pt
, 0, sizeof (struct pt_solution
));
7701 bool writes_global_memory
= true;
7703 determine_global_memory_access (stmt
, &writes_global_memory
,
7706 if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
7708 *pt
= find_what_var_points_to (cfun
->decl
, vi
);
7709 /* Escaped (and thus nonlocal) variables are always
7710 implicitly clobbered by calls. */
7711 /* ??? ESCAPED can be empty even though NONLOCAL
7713 if (writes_global_memory
)
7719 else if (writes_global_memory
)
7721 /* If there is nothing special about this call then
7722 we have made everything that is used also escape. */
7723 *pt
= cfun
->gimple_df
->escaped
;
7727 memset (pt
, 0, sizeof (struct pt_solution
));
7732 timevar_pop (TV_TREE_PTA
);
7736 /* Delete created points-to sets. */
7739 delete_points_to_sets (void)
7743 delete shared_bitmap_table
;
7744 shared_bitmap_table
= NULL
;
7745 if (dump_file
&& (dump_flags
& TDF_STATS
))
7746 fprintf (dump_file
, "Points to sets created:%d\n",
7747 stats
.points_to_sets_created
);
7750 delete call_stmt_vars
;
7751 bitmap_obstack_release (&pta_obstack
);
7752 constraints
.release ();
7754 for (i
= 0; i
< graph
->size
; i
++)
7755 graph
->complex[i
].release ();
7756 free (graph
->complex);
7759 free (graph
->succs
);
7761 free (graph
->pe_rep
);
7762 free (graph
->indirect_cycles
);
7766 variable_info_pool
.release ();
7767 constraint_pool
.release ();
7769 obstack_free (&fake_var_decl_obstack
, NULL
);
7771 delete final_solutions
;
7772 obstack_free (&final_solutions_obstack
, NULL
);
7777 unsigned short clique
;
7782 /* Mark "other" loads and stores as belonging to CLIQUE and with
7786 visit_loadstore (gimple
*, tree base
, tree ref
, void *data
)
7788 unsigned short clique
= ((vls_data
*) data
)->clique
;
7789 bitmap rvars
= ((vls_data
*) data
)->rvars
;
7790 bool escaped_p
= ((vls_data
*) data
)->escaped_p
;
7791 if (TREE_CODE (base
) == MEM_REF
7792 || TREE_CODE (base
) == TARGET_MEM_REF
)
7794 tree ptr
= TREE_OPERAND (base
, 0);
7795 if (TREE_CODE (ptr
) == SSA_NAME
)
7797 /* For parameters, get at the points-to set for the actual parm
7799 if (SSA_NAME_IS_DEFAULT_DEF (ptr
)
7800 && (TREE_CODE (SSA_NAME_VAR (ptr
)) == PARM_DECL
7801 || TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
))
7802 ptr
= SSA_NAME_VAR (ptr
);
7804 /* We need to make sure 'ptr' doesn't include any of
7805 the restrict tags we added bases for in its points-to set. */
7806 varinfo_t vi
= lookup_vi_for_tree (ptr
);
7810 vi
= get_varinfo (find (vi
->id
));
7811 if (bitmap_intersect_p (rvars
, vi
->solution
)
7812 || (escaped_p
&& bitmap_bit_p (vi
->solution
, escaped_id
)))
7816 /* Do not overwrite existing cliques (that includes clique, base
7817 pairs we just set). */
7818 if (MR_DEPENDENCE_CLIQUE (base
) == 0)
7820 MR_DEPENDENCE_CLIQUE (base
) = clique
;
7821 MR_DEPENDENCE_BASE (base
) = 0;
7825 /* For plain decl accesses see whether they are accesses to globals
7826 and rewrite them to MEM_REFs with { clique, 0 }. */
7828 && is_global_var (base
)
7829 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
7834 while (handled_component_p (*basep
))
7835 basep
= &TREE_OPERAND (*basep
, 0);
7836 gcc_assert (VAR_P (*basep
));
7837 tree ptr
= build_fold_addr_expr (*basep
);
7838 tree zero
= build_int_cst (TREE_TYPE (ptr
), 0);
7839 *basep
= build2 (MEM_REF
, TREE_TYPE (*basep
), ptr
, zero
);
7840 MR_DEPENDENCE_CLIQUE (*basep
) = clique
;
7841 MR_DEPENDENCE_BASE (*basep
) = 0;
7849 unsigned short *clique
;
7850 unsigned short *last_ruid
;
7851 varinfo_t restrict_var
;
7854 /* If BASE is a MEM_REF then assign a clique, base pair to it, updating
7855 CLIQUE, *RESTRICT_VAR and LAST_RUID as passed via DATA.
7856 Return whether dependence info was assigned to BASE. */
7859 maybe_set_dependence_info (gimple
*, tree base
, tree
, void *data
)
7861 tree ptr
= ((msdi_data
*)data
)->ptr
;
7862 unsigned short &clique
= *((msdi_data
*)data
)->clique
;
7863 unsigned short &last_ruid
= *((msdi_data
*)data
)->last_ruid
;
7864 varinfo_t restrict_var
= ((msdi_data
*)data
)->restrict_var
;
7865 if ((TREE_CODE (base
) == MEM_REF
7866 || TREE_CODE (base
) == TARGET_MEM_REF
)
7867 && TREE_OPERAND (base
, 0) == ptr
)
7869 /* Do not overwrite existing cliques. This avoids overwriting dependence
7870 info inlined from a function with restrict parameters inlined
7871 into a function with restrict parameters. This usually means we
7872 prefer to be precise in innermost loops. */
7873 if (MR_DEPENDENCE_CLIQUE (base
) == 0)
7877 if (cfun
->last_clique
== 0)
7878 cfun
->last_clique
= 1;
7881 if (restrict_var
->ruid
== 0)
7882 restrict_var
->ruid
= ++last_ruid
;
7883 MR_DEPENDENCE_CLIQUE (base
) = clique
;
7884 MR_DEPENDENCE_BASE (base
) = restrict_var
->ruid
;
7891 /* Clear dependence info for the clique DATA. */
7894 clear_dependence_clique (gimple
*, tree base
, tree
, void *data
)
7896 unsigned short clique
= (uintptr_t)data
;
7897 if ((TREE_CODE (base
) == MEM_REF
7898 || TREE_CODE (base
) == TARGET_MEM_REF
)
7899 && MR_DEPENDENCE_CLIQUE (base
) == clique
)
7901 MR_DEPENDENCE_CLIQUE (base
) = 0;
7902 MR_DEPENDENCE_BASE (base
) = 0;
7908 /* Compute the set of independend memory references based on restrict
7909 tags and their conservative propagation to the points-to sets. */
7912 compute_dependence_clique (void)
7914 /* First clear the special "local" clique. */
7916 if (cfun
->last_clique
!= 0)
7917 FOR_EACH_BB_FN (bb
, cfun
)
7918 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
7919 !gsi_end_p (gsi
); gsi_next (&gsi
))
7921 gimple
*stmt
= gsi_stmt (gsi
);
7922 walk_stmt_load_store_ops (stmt
, (void *)(uintptr_t) 1,
7923 clear_dependence_clique
,
7924 clear_dependence_clique
);
7927 unsigned short clique
= 0;
7928 unsigned short last_ruid
= 0;
7929 bitmap rvars
= BITMAP_ALLOC (NULL
);
7930 bool escaped_p
= false;
7931 for (unsigned i
= 0; i
< num_ssa_names
; ++i
)
7933 tree ptr
= ssa_name (i
);
7934 if (!ptr
|| !POINTER_TYPE_P (TREE_TYPE (ptr
)))
7937 /* Avoid all this when ptr is not dereferenced? */
7939 if (SSA_NAME_IS_DEFAULT_DEF (ptr
)
7940 && (TREE_CODE (SSA_NAME_VAR (ptr
)) == PARM_DECL
7941 || TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
))
7942 p
= SSA_NAME_VAR (ptr
);
7943 varinfo_t vi
= lookup_vi_for_tree (p
);
7946 vi
= get_varinfo (find (vi
->id
));
7949 varinfo_t restrict_var
= NULL
;
7950 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, j
, bi
)
7952 varinfo_t oi
= get_varinfo (j
);
7954 oi
= get_varinfo (oi
->head
);
7955 if (oi
->is_restrict_var
)
7958 && restrict_var
!= oi
)
7960 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7962 fprintf (dump_file
, "found restrict pointed-to "
7964 print_generic_expr (dump_file
, ptr
);
7965 fprintf (dump_file
, " but not exclusively\n");
7967 restrict_var
= NULL
;
7972 /* NULL is the only other valid points-to entry. */
7973 else if (oi
->id
!= nothing_id
)
7975 restrict_var
= NULL
;
7979 /* Ok, found that ptr must(!) point to a single(!) restrict
7981 /* ??? PTA isn't really a proper propagation engine to compute
7983 ??? We could handle merging of two restricts by unifying them. */
7986 /* Now look at possible dereferences of ptr. */
7987 imm_use_iterator ui
;
7990 msdi_data data
= { ptr
, &clique
, &last_ruid
, restrict_var
};
7991 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, ptr
)
7992 used
|= walk_stmt_load_store_ops (use_stmt
, &data
,
7993 maybe_set_dependence_info
,
7994 maybe_set_dependence_info
);
7997 /* Add all subvars to the set of restrict pointed-to set. */
7998 for (unsigned sv
= restrict_var
->head
; sv
!= 0;
7999 sv
= get_varinfo (sv
)->next
)
8000 bitmap_set_bit (rvars
, sv
);
8001 varinfo_t escaped
= get_varinfo (find (escaped_id
));
8002 if (bitmap_bit_p (escaped
->solution
, restrict_var
->id
))
8010 /* Assign the BASE id zero to all accesses not based on a restrict
8011 pointer. That way they get disambiguated against restrict
8012 accesses but not against each other. */
8013 /* ??? For restricts derived from globals (thus not incoming
8014 parameters) we can't restrict scoping properly thus the following
8015 is too aggressive there. For now we have excluded those globals from
8016 getting into the MR_DEPENDENCE machinery. */
8017 vls_data data
= { clique
, escaped_p
, rvars
};
8019 FOR_EACH_BB_FN (bb
, cfun
)
8020 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
8021 !gsi_end_p (gsi
); gsi_next (&gsi
))
8023 gimple
*stmt
= gsi_stmt (gsi
);
8024 walk_stmt_load_store_ops (stmt
, &data
,
8025 visit_loadstore
, visit_loadstore
);
8029 BITMAP_FREE (rvars
);
8032 /* Compute points-to information for every SSA_NAME pointer in the
8033 current function and compute the transitive closure of escaped
8034 variables to re-initialize the call-clobber states of local variables. */
8037 compute_may_aliases (void)
8039 if (cfun
->gimple_df
->ipa_pta
)
8043 fprintf (dump_file
, "\nNot re-computing points-to information "
8044 "because IPA points-to information is available.\n\n");
8046 /* But still dump what we have remaining it. */
8047 if (dump_flags
& (TDF_DETAILS
|TDF_ALIAS
))
8048 dump_alias_info (dump_file
);
8054 /* For each pointer P_i, determine the sets of variables that P_i may
8055 point-to. Compute the reachability set of escaped and call-used
8057 compute_points_to_sets ();
8059 /* Debugging dumps. */
8060 if (dump_file
&& (dump_flags
& (TDF_DETAILS
|TDF_ALIAS
)))
8061 dump_alias_info (dump_file
);
8063 /* Compute restrict-based memory disambiguations. */
8064 compute_dependence_clique ();
8066 /* Deallocate memory used by aliasing data structures and the internal
8067 points-to solution. */
8068 delete_points_to_sets ();
8070 gcc_assert (!need_ssa_update_p (cfun
));
8075 /* A dummy pass to cause points-to information to be computed via
8076 TODO_rebuild_alias. */
8080 const pass_data pass_data_build_alias
=
8082 GIMPLE_PASS
, /* type */
8084 OPTGROUP_NONE
, /* optinfo_flags */
8085 TV_NONE
, /* tv_id */
8086 ( PROP_cfg
| PROP_ssa
), /* properties_required */
8087 0, /* properties_provided */
8088 0, /* properties_destroyed */
8089 0, /* todo_flags_start */
8090 TODO_rebuild_alias
, /* todo_flags_finish */
8093 class pass_build_alias
: public gimple_opt_pass
8096 pass_build_alias (gcc::context
*ctxt
)
8097 : gimple_opt_pass (pass_data_build_alias
, ctxt
)
8100 /* opt_pass methods: */
8101 bool gate (function
*) final override
{ return flag_tree_pta
; }
8103 }; // class pass_build_alias
8108 make_pass_build_alias (gcc::context
*ctxt
)
8110 return new pass_build_alias (ctxt
);
8113 /* A dummy pass to cause points-to information to be computed via
8114 TODO_rebuild_alias. */
8118 const pass_data pass_data_build_ealias
=
8120 GIMPLE_PASS
, /* type */
8121 "ealias", /* name */
8122 OPTGROUP_NONE
, /* optinfo_flags */
8123 TV_NONE
, /* tv_id */
8124 ( PROP_cfg
| PROP_ssa
), /* properties_required */
8125 0, /* properties_provided */
8126 0, /* properties_destroyed */
8127 0, /* todo_flags_start */
8128 TODO_rebuild_alias
, /* todo_flags_finish */
8131 class pass_build_ealias
: public gimple_opt_pass
8134 pass_build_ealias (gcc::context
*ctxt
)
8135 : gimple_opt_pass (pass_data_build_ealias
, ctxt
)
8138 /* opt_pass methods: */
8139 bool gate (function
*) final override
{ return flag_tree_pta
; }
8141 }; // class pass_build_ealias
8146 make_pass_build_ealias (gcc::context
*ctxt
)
8148 return new pass_build_ealias (ctxt
);
8152 /* IPA PTA solutions for ESCAPED. */
8153 struct pt_solution ipa_escaped_pt
8154 = { true, false, false, false, false,
8155 false, false, false, false, false, NULL
};
8157 /* Associate node with varinfo DATA. Worker for
8158 cgraph_for_symbol_thunks_and_aliases. */
8160 associate_varinfo_to_alias (struct cgraph_node
*node
, void *data
)
8164 && ! node
->inlined_to
))
8166 && !node
->ifunc_resolver
)
8167 insert_vi_for_tree (node
->decl
, (varinfo_t
)data
);
8171 /* Dump varinfo VI to FILE. */
8174 dump_varinfo (FILE *file
, varinfo_t vi
)
8179 fprintf (file
, "%u: %s\n", vi
->id
, vi
->name
);
8181 const char *sep
= " ";
8182 if (vi
->is_artificial_var
)
8183 fprintf (file
, "%sartificial", sep
);
8184 if (vi
->is_special_var
)
8185 fprintf (file
, "%sspecial", sep
);
8186 if (vi
->is_unknown_size_var
)
8187 fprintf (file
, "%sunknown-size", sep
);
8188 if (vi
->is_full_var
)
8189 fprintf (file
, "%sfull", sep
);
8190 if (vi
->is_heap_var
)
8191 fprintf (file
, "%sheap", sep
);
8192 if (vi
->may_have_pointers
)
8193 fprintf (file
, "%smay-have-pointers", sep
);
8194 if (vi
->only_restrict_pointers
)
8195 fprintf (file
, "%sonly-restrict-pointers", sep
);
8196 if (vi
->is_restrict_var
)
8197 fprintf (file
, "%sis-restrict-var", sep
);
8198 if (vi
->is_global_var
)
8199 fprintf (file
, "%sglobal", sep
);
8200 if (vi
->is_ipa_escape_point
)
8201 fprintf (file
, "%sipa-escape-point", sep
);
8203 fprintf (file
, "%sfn-info", sep
);
8205 fprintf (file
, "%srestrict-uid:%u", sep
, vi
->ruid
);
8207 fprintf (file
, "%snext:%u", sep
, vi
->next
);
8208 if (vi
->head
!= vi
->id
)
8209 fprintf (file
, "%shead:%u", sep
, vi
->head
);
8211 fprintf (file
, "%soffset:" HOST_WIDE_INT_PRINT_DEC
, sep
, vi
->offset
);
8212 if (vi
->size
!= ~(unsigned HOST_WIDE_INT
)0)
8213 fprintf (file
, "%ssize:" HOST_WIDE_INT_PRINT_DEC
, sep
, vi
->size
);
8214 if (vi
->fullsize
!= ~(unsigned HOST_WIDE_INT
)0
8215 && vi
->fullsize
!= vi
->size
)
8216 fprintf (file
, "%sfullsize:" HOST_WIDE_INT_PRINT_DEC
, sep
,
8218 fprintf (file
, "\n");
8220 if (vi
->solution
&& !bitmap_empty_p (vi
->solution
))
8224 fprintf (file
, " solution: {");
8225 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
8226 fprintf (file
, " %u", i
);
8227 fprintf (file
, " }\n");
8230 if (vi
->oldsolution
&& !bitmap_empty_p (vi
->oldsolution
)
8231 && !bitmap_equal_p (vi
->solution
, vi
->oldsolution
))
8235 fprintf (file
, " oldsolution: {");
8236 EXECUTE_IF_SET_IN_BITMAP (vi
->oldsolution
, 0, i
, bi
)
8237 fprintf (file
, " %u", i
);
8238 fprintf (file
, " }\n");
8242 /* Dump varinfo VI to stderr. */
8245 debug_varinfo (varinfo_t vi
)
8247 dump_varinfo (stderr
, vi
);
8250 /* Dump varmap to FILE. */
8253 dump_varmap (FILE *file
)
8255 if (varmap
.length () == 0)
8258 fprintf (file
, "variables:\n");
8260 for (unsigned int i
= 0; i
< varmap
.length (); ++i
)
8262 varinfo_t vi
= get_varinfo (i
);
8263 dump_varinfo (file
, vi
);
8266 fprintf (file
, "\n");
8269 /* Dump varmap to stderr. */
8274 dump_varmap (stderr
);
8277 /* Compute whether node is refered to non-locally. Worker for
8278 cgraph_for_symbol_thunks_and_aliases. */
8280 refered_from_nonlocal_fn (struct cgraph_node
*node
, void *data
)
8282 bool *nonlocal_p
= (bool *)data
;
8283 *nonlocal_p
|= (node
->used_from_other_partition
8284 || DECL_EXTERNAL (node
->decl
)
8285 || TREE_PUBLIC (node
->decl
)
8286 || node
->force_output
8287 || lookup_attribute ("noipa", DECL_ATTRIBUTES (node
->decl
)));
8291 /* Same for varpool nodes. */
8293 refered_from_nonlocal_var (struct varpool_node
*node
, void *data
)
8295 bool *nonlocal_p
= (bool *)data
;
8296 *nonlocal_p
|= (node
->used_from_other_partition
8297 || DECL_EXTERNAL (node
->decl
)
8298 || TREE_PUBLIC (node
->decl
)
8299 || node
->force_output
);
8303 /* Execute the driver for IPA PTA. */
8305 ipa_pta_execute (void)
8307 struct cgraph_node
*node
;
8309 unsigned int from
= 0;
8315 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
8317 symtab
->dump (dump_file
);
8318 fprintf (dump_file
, "\n");
8321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
8323 fprintf (dump_file
, "Generating generic constraints\n\n");
8324 dump_constraints (dump_file
, from
);
8325 fprintf (dump_file
, "\n");
8326 from
= constraints
.length ();
8329 /* Build the constraints. */
8330 FOR_EACH_DEFINED_FUNCTION (node
)
8333 /* Nodes without a body in this partition are not interesting.
8334 Especially do not visit clones at this point for now - we
8335 get duplicate decls there for inline clones at least. */
8336 if (!node
->has_gimple_body_p ()
8337 || node
->in_other_partition
8338 || node
->inlined_to
)
8342 gcc_assert (!node
->clone_of
);
8344 /* For externally visible or attribute used annotated functions use
8345 local constraints for their arguments.
8346 For local functions we see all callers and thus do not need initial
8347 constraints for parameters. */
8348 bool nonlocal_p
= (node
->used_from_other_partition
8349 || DECL_EXTERNAL (node
->decl
)
8350 || TREE_PUBLIC (node
->decl
)
8351 || node
->force_output
8352 || lookup_attribute ("noipa",
8353 DECL_ATTRIBUTES (node
->decl
)));
8354 node
->call_for_symbol_thunks_and_aliases (refered_from_nonlocal_fn
,
8357 vi
= create_function_info_for (node
->decl
,
8358 alias_get_name (node
->decl
), false,
8360 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
8361 && from
!= constraints
.length ())
8364 "Generating initial constraints for %s",
8365 node
->dump_name ());
8366 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
8367 fprintf (dump_file
, " (%s)",
8369 (DECL_ASSEMBLER_NAME (node
->decl
)));
8370 fprintf (dump_file
, "\n\n");
8371 dump_constraints (dump_file
, from
);
8372 fprintf (dump_file
, "\n");
8374 from
= constraints
.length ();
8377 node
->call_for_symbol_thunks_and_aliases
8378 (associate_varinfo_to_alias
, vi
, true);
8381 /* Create constraints for global variables and their initializers. */
8382 FOR_EACH_VARIABLE (var
)
8384 if (var
->alias
&& var
->analyzed
)
8387 varinfo_t vi
= get_vi_for_tree (var
->decl
);
8389 /* For the purpose of IPA PTA unit-local globals are not
8391 bool nonlocal_p
= (DECL_EXTERNAL (var
->decl
)
8392 || TREE_PUBLIC (var
->decl
)
8393 || var
->used_from_other_partition
8394 || var
->force_output
);
8395 var
->call_for_symbol_and_aliases (refered_from_nonlocal_var
,
8398 vi
->is_ipa_escape_point
= true;
8401 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
8402 && from
!= constraints
.length ())
8405 "Generating constraints for global initializers\n\n");
8406 dump_constraints (dump_file
, from
);
8407 fprintf (dump_file
, "\n");
8408 from
= constraints
.length ();
8411 FOR_EACH_DEFINED_FUNCTION (node
)
8413 struct function
*func
;
8416 /* Nodes without a body in this partition are not interesting. */
8417 if (!node
->has_gimple_body_p ()
8418 || node
->in_other_partition
8422 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
8425 "Generating constraints for %s", node
->dump_name ());
8426 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
8427 fprintf (dump_file
, " (%s)",
8429 (DECL_ASSEMBLER_NAME (node
->decl
)));
8430 fprintf (dump_file
, "\n");
8433 func
= DECL_STRUCT_FUNCTION (node
->decl
);
8434 gcc_assert (cfun
== NULL
);
8436 /* Build constriants for the function body. */
8437 FOR_EACH_BB_FN (bb
, func
)
8439 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
8442 gphi
*phi
= gsi
.phi ();
8444 if (! virtual_operand_p (gimple_phi_result (phi
)))
8445 find_func_aliases (func
, phi
);
8448 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
8451 gimple
*stmt
= gsi_stmt (gsi
);
8453 find_func_aliases (func
, stmt
);
8454 find_func_clobbers (func
, stmt
);
8458 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
8460 fprintf (dump_file
, "\n");
8461 dump_constraints (dump_file
, from
);
8462 fprintf (dump_file
, "\n");
8463 from
= constraints
.length ();
8467 /* From the constraints compute the points-to sets. */
8468 solve_constraints ();
8470 if (dump_file
&& (dump_flags
& TDF_STATS
))
8471 dump_sa_stats (dump_file
);
8473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
8474 dump_sa_points_to_info (dump_file
);
8476 /* Now post-process solutions to handle locals from different
8477 runtime instantiations coming in through recursive invocations. */
8478 unsigned shadow_var_cnt
= 0;
8479 for (unsigned i
= 1; i
< varmap
.length (); ++i
)
8481 varinfo_t fi
= get_varinfo (i
);
8484 /* Automatic variables pointed to by their containing functions
8485 parameters need this treatment. */
8486 for (varinfo_t ai
= first_vi_for_offset (fi
, fi_parm_base
);
8487 ai
; ai
= vi_next (ai
))
8489 varinfo_t vi
= get_varinfo (find (ai
->id
));
8492 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, j
, bi
)
8494 varinfo_t pt
= get_varinfo (j
);
8495 if (pt
->shadow_var_uid
== 0
8497 && auto_var_in_fn_p (pt
->decl
, fi
->decl
))
8499 pt
->shadow_var_uid
= allocate_decl_uid ();
8504 /* As well as global variables which are another way of passing
8505 arguments to recursive invocations. */
8506 else if (fi
->is_global_var
)
8508 for (varinfo_t ai
= fi
; ai
; ai
= vi_next (ai
))
8510 varinfo_t vi
= get_varinfo (find (ai
->id
));
8513 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, j
, bi
)
8515 varinfo_t pt
= get_varinfo (j
);
8516 if (pt
->shadow_var_uid
== 0
8518 && auto_var_p (pt
->decl
))
8520 pt
->shadow_var_uid
= allocate_decl_uid ();
8527 if (shadow_var_cnt
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
8528 fprintf (dump_file
, "Allocated %u shadow variables for locals "
8529 "maybe leaking into recursive invocations of their containing "
8530 "functions\n", shadow_var_cnt
);
8532 /* Compute the global points-to sets for ESCAPED.
8533 ??? Note that the computed escape set is not correct
8534 for the whole unit as we fail to consider graph edges to
8535 externally visible functions. */
8536 ipa_escaped_pt
= find_what_var_points_to (NULL
, get_varinfo (escaped_id
));
8538 /* Make sure the ESCAPED solution (which is used as placeholder in
8539 other solutions) does not reference itself. This simplifies
8540 points-to solution queries. */
8541 ipa_escaped_pt
.ipa_escaped
= 0;
8543 /* Assign the points-to sets to the SSA names in the unit. */
8544 FOR_EACH_DEFINED_FUNCTION (node
)
8547 struct function
*fn
;
8551 /* Nodes without a body in this partition are not interesting. */
8552 if (!node
->has_gimple_body_p ()
8553 || node
->in_other_partition
8557 fn
= DECL_STRUCT_FUNCTION (node
->decl
);
8559 /* Compute the points-to sets for pointer SSA_NAMEs. */
8560 FOR_EACH_VEC_ELT (*fn
->gimple_df
->ssa_names
, i
, ptr
)
8563 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
8564 find_what_p_points_to (node
->decl
, ptr
);
8567 /* Compute the call-use and call-clobber sets for indirect calls
8568 and calls to external functions. */
8569 FOR_EACH_BB_FN (bb
, fn
)
8571 gimple_stmt_iterator gsi
;
8573 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
8576 struct pt_solution
*pt
;
8580 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
8584 /* Handle direct calls to functions with body. */
8585 decl
= gimple_call_fndecl (stmt
);
8588 tree called_decl
= NULL_TREE
;
8589 if (gimple_call_builtin_p (stmt
, BUILT_IN_GOMP_PARALLEL
))
8590 called_decl
= TREE_OPERAND (gimple_call_arg (stmt
, 0), 0);
8591 else if (gimple_call_builtin_p (stmt
, BUILT_IN_GOACC_PARALLEL
))
8592 called_decl
= TREE_OPERAND (gimple_call_arg (stmt
, 1), 0);
8594 if (called_decl
!= NULL_TREE
8595 && !fndecl_maybe_in_other_partition (called_decl
))
8600 && (fi
= lookup_vi_for_tree (decl
))
8603 *gimple_call_clobber_set (stmt
)
8604 = find_what_var_points_to
8605 (node
->decl
, first_vi_for_offset (fi
, fi_clobbers
));
8606 *gimple_call_use_set (stmt
)
8607 = find_what_var_points_to
8608 (node
->decl
, first_vi_for_offset (fi
, fi_uses
));
8610 /* Handle direct calls to external functions. */
8611 else if (decl
&& (!fi
|| fi
->decl
))
8613 pt
= gimple_call_use_set (stmt
);
8614 if (gimple_call_flags (stmt
) & ECF_CONST
)
8615 memset (pt
, 0, sizeof (struct pt_solution
));
8616 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
8618 *pt
= find_what_var_points_to (node
->decl
, vi
);
8619 /* Escaped (and thus nonlocal) variables are always
8620 implicitly used by calls. */
8621 /* ??? ESCAPED can be empty even though NONLOCAL
8624 pt
->ipa_escaped
= 1;
8628 /* If there is nothing special about this call then
8629 we have made everything that is used also escape. */
8630 *pt
= ipa_escaped_pt
;
8634 pt
= gimple_call_clobber_set (stmt
);
8635 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
8636 memset (pt
, 0, sizeof (struct pt_solution
));
8637 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
8639 *pt
= find_what_var_points_to (node
->decl
, vi
);
8640 /* Escaped (and thus nonlocal) variables are always
8641 implicitly clobbered by calls. */
8642 /* ??? ESCAPED can be empty even though NONLOCAL
8645 pt
->ipa_escaped
= 1;
8649 /* If there is nothing special about this call then
8650 we have made everything that is used also escape. */
8651 *pt
= ipa_escaped_pt
;
8655 /* Handle indirect calls. */
8656 else if ((fi
= get_fi_for_callee (stmt
)))
8658 /* We need to accumulate all clobbers/uses of all possible
8660 fi
= get_varinfo (find (fi
->id
));
8661 /* If we cannot constrain the set of functions we'll end up
8662 calling we end up using/clobbering everything. */
8663 if (bitmap_bit_p (fi
->solution
, anything_id
)
8664 || bitmap_bit_p (fi
->solution
, nonlocal_id
)
8665 || bitmap_bit_p (fi
->solution
, escaped_id
))
8667 pt_solution_reset (gimple_call_clobber_set (stmt
));
8668 pt_solution_reset (gimple_call_use_set (stmt
));
8674 struct pt_solution
*uses
, *clobbers
;
8676 uses
= gimple_call_use_set (stmt
);
8677 clobbers
= gimple_call_clobber_set (stmt
);
8678 memset (uses
, 0, sizeof (struct pt_solution
));
8679 memset (clobbers
, 0, sizeof (struct pt_solution
));
8680 EXECUTE_IF_SET_IN_BITMAP (fi
->solution
, 0, i
, bi
)
8682 struct pt_solution sol
;
8684 vi
= get_varinfo (i
);
8685 if (!vi
->is_fn_info
)
8687 /* ??? We could be more precise here? */
8689 uses
->ipa_escaped
= 1;
8690 clobbers
->nonlocal
= 1;
8691 clobbers
->ipa_escaped
= 1;
8695 if (!uses
->anything
)
8697 sol
= find_what_var_points_to
8699 first_vi_for_offset (vi
, fi_uses
));
8700 pt_solution_ior_into (uses
, &sol
);
8702 if (!clobbers
->anything
)
8704 sol
= find_what_var_points_to
8706 first_vi_for_offset (vi
, fi_clobbers
));
8707 pt_solution_ior_into (clobbers
, &sol
);
8717 fn
->gimple_df
->ipa_pta
= true;
8719 /* We have to re-set the final-solution cache after each function
8720 because what is a "global" is dependent on function context. */
8721 final_solutions
->empty ();
8722 obstack_free (&final_solutions_obstack
, NULL
);
8723 gcc_obstack_init (&final_solutions_obstack
);
8726 delete_points_to_sets ();
8735 const pass_data pass_data_ipa_pta
=
8737 SIMPLE_IPA_PASS
, /* type */
8739 OPTGROUP_NONE
, /* optinfo_flags */
8740 TV_IPA_PTA
, /* tv_id */
8741 0, /* properties_required */
8742 0, /* properties_provided */
8743 0, /* properties_destroyed */
8744 0, /* todo_flags_start */
8745 0, /* todo_flags_finish */
8748 class pass_ipa_pta
: public simple_ipa_opt_pass
8751 pass_ipa_pta (gcc::context
*ctxt
)
8752 : simple_ipa_opt_pass (pass_data_ipa_pta
, ctxt
)
8755 /* opt_pass methods: */
8756 bool gate (function
*) final override
8760 /* Don't bother doing anything if the program has errors. */
8764 opt_pass
* clone () final override
{ return new pass_ipa_pta (m_ctxt
); }
8766 unsigned int execute (function
*) final override
8768 return ipa_pta_execute ();
8771 }; // class pass_ipa_pta
8775 simple_ipa_opt_pass
*
8776 make_pass_ipa_pta (gcc::context
*ctxt
)
8778 return new pass_ipa_pta (ctxt
);