1 /* Tree based points-to analysis
2 Copyright (C) 2005-2017 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"
41 #include "gimple-walk.h"
45 /* The idea behind this analyzer is to generate set constraints from the
46 program, then solve the resulting constraints in order to generate the
49 Set constraints are a way of modeling program analysis problems that
50 involve sets. They consist of an inclusion constraint language,
51 describing the variables (each variable is a set) and operations that
52 are involved on the variables, and a set of rules that derive facts
53 from these operations. To solve a system of set constraints, you derive
54 all possible facts under the rules, which gives you the correct sets
57 See "Efficient Field-sensitive pointer analysis for C" by "David
58 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
59 http://citeseer.ist.psu.edu/pearce04efficient.html
61 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
62 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
63 http://citeseer.ist.psu.edu/heintze01ultrafast.html
65 There are three types of real constraint expressions, DEREF,
66 ADDRESSOF, and SCALAR. Each constraint expression consists
67 of a constraint type, a variable, and an offset.
69 SCALAR is a constraint expression type used to represent x, whether
70 it appears on the LHS or the RHS of a statement.
71 DEREF is a constraint expression type used to represent *x, whether
72 it appears on the LHS or the RHS of a statement.
73 ADDRESSOF is a constraint expression used to represent &x, whether
74 it appears on the LHS or the RHS of a statement.
76 Each pointer variable in the program is assigned an integer id, and
77 each field of a structure variable is assigned an integer id as well.
79 Structure variables are linked to their list of fields through a "next
80 field" in each variable that points to the next field in offset
82 Each variable for a structure field has
84 1. "size", that tells the size in bits of that field.
85 2. "fullsize, that tells the size in bits of the entire structure.
86 3. "offset", that tells the offset in bits from the beginning of the
87 structure to this field.
99 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
100 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
101 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
104 In order to solve the system of set constraints, the following is
107 1. Each constraint variable x has a solution set associated with it,
110 2. Constraints are separated into direct, copy, and complex.
111 Direct constraints are ADDRESSOF constraints that require no extra
112 processing, such as P = &Q
113 Copy constraints are those of the form P = Q.
114 Complex constraints are all the constraints involving dereferences
115 and offsets (including offsetted copies).
117 3. All direct constraints of the form P = &Q are processed, such
118 that Q is added to Sol(P)
120 4. All complex constraints for a given constraint variable are stored in a
121 linked list attached to that variable's node.
123 5. A directed graph is built out of the copy constraints. Each
124 constraint variable is a node in the graph, and an edge from
125 Q to P is added for each copy constraint of the form P = Q
127 6. The graph is then walked, and solution sets are
128 propagated along the copy edges, such that an edge from Q to P
129 causes Sol(P) <- Sol(P) union Sol(Q).
131 7. As we visit each node, all complex constraints associated with
132 that node are processed by adding appropriate copy edges to the graph, or the
133 appropriate variables to the solution set.
135 8. The process of walking the graph is iterated until no solution
138 Prior to walking the graph in steps 6 and 7, We perform static
139 cycle elimination on the constraint graph, as well
140 as off-line variable substitution.
142 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
143 on and turned into anything), but isn't. You can just see what offset
144 inside the pointed-to struct it's going to access.
146 TODO: Constant bounded arrays can be handled as if they were structs of the
147 same number of elements.
149 TODO: Modeling heap and incoming pointers becomes much better if we
150 add fields to them as we discover them, which we could do.
152 TODO: We could handle unions, but to be honest, it's probably not
153 worth the pain or slowdown. */
155 /* IPA-PTA optimizations possible.
157 When the indirect function called is ANYTHING we can add disambiguation
158 based on the function signatures (or simply the parameter count which
159 is the varinfo size). We also do not need to consider functions that
160 do not have their address taken.
162 The is_global_var bit which marks escape points is overly conservative
163 in IPA mode. Split it to is_escape_point and is_global_var - only
164 externally visible globals are escape points in IPA mode.
165 There is now is_ipa_escape_point but this is only used in a few
168 The way we introduce DECL_PT_UID to avoid fixing up all points-to
169 sets in the translation unit when we copy a DECL during inlining
170 pessimizes precision. The advantage is that the DECL_PT_UID keeps
171 compile-time and memory usage overhead low - the points-to sets
172 do not grow or get unshared as they would during a fixup phase.
173 An alternative solution is to delay IPA PTA until after all
174 inlining transformations have been applied.
176 The way we propagate clobber/use information isn't optimized.
177 It should use a new complex constraint that properly filters
178 out local variables of the callee (though that would make
179 the sets invalid after inlining). OTOH we might as well
180 admit defeat to WHOPR and simply do all the clobber/use analysis
181 and propagation after PTA finished but before we threw away
182 points-to information for memory variables. WHOPR and PTA
183 do not play along well anyway - the whole constraint solving
184 would need to be done in WPA phase and it will be very interesting
185 to apply the results to local SSA names during LTRANS phase.
187 We probably should compute a per-function unit-ESCAPE solution
188 propagating it simply like the clobber / uses solutions. The
189 solution can go alongside the non-IPA espaced solution and be
190 used to query which vars escape the unit through a function.
191 This is also required to make the escaped-HEAP trick work in IPA mode.
193 We never put function decls in points-to sets so we do not
194 keep the set of called functions for indirect calls.
196 And probably more. */
198 static bool use_field_sensitive
= true;
199 static int in_ipa_mode
= 0;
201 /* Used for predecessor bitmaps. */
202 static bitmap_obstack predbitmap_obstack
;
204 /* Used for points-to sets. */
205 static bitmap_obstack pta_obstack
;
207 /* Used for oldsolution members of variables. */
208 static bitmap_obstack oldpta_obstack
;
210 /* Used for per-solver-iteration bitmaps. */
211 static bitmap_obstack iteration_obstack
;
213 static unsigned int create_variable_info_for (tree
, const char *, bool);
214 typedef struct constraint_graph
*constraint_graph_t
;
215 static void unify_nodes (constraint_graph_t
, unsigned int, unsigned int, bool);
218 typedef struct constraint
*constraint_t
;
221 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
223 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
225 static struct constraint_stats
227 unsigned int total_vars
;
228 unsigned int nonpointer_vars
;
229 unsigned int unified_vars_static
;
230 unsigned int unified_vars_dynamic
;
231 unsigned int iterations
;
232 unsigned int num_edges
;
233 unsigned int num_implicit_edges
;
234 unsigned int points_to_sets_created
;
239 /* ID of this variable */
242 /* True if this is a variable created by the constraint analysis, such as
243 heap variables and constraints we had to break up. */
244 unsigned int is_artificial_var
: 1;
246 /* True if this is a special variable whose solution set should not be
248 unsigned int is_special_var
: 1;
250 /* True for variables whose size is not known or variable. */
251 unsigned int is_unknown_size_var
: 1;
253 /* True for (sub-)fields that represent a whole variable. */
254 unsigned int is_full_var
: 1;
256 /* True if this is a heap variable. */
257 unsigned int is_heap_var
: 1;
259 /* True if this field may contain pointers. */
260 unsigned int may_have_pointers
: 1;
262 /* True if this field has only restrict qualified pointers. */
263 unsigned int only_restrict_pointers
: 1;
265 /* True if this represents a heap var created for a restrict qualified
267 unsigned int is_restrict_var
: 1;
269 /* True if this represents a global variable. */
270 unsigned int is_global_var
: 1;
272 /* True if this represents a module escape point for IPA analysis. */
273 unsigned int is_ipa_escape_point
: 1;
275 /* True if this represents a IPA function info. */
276 unsigned int is_fn_info
: 1;
278 /* ??? Store somewhere better. */
281 /* The ID of the variable for the next field in this structure
282 or zero for the last field in this structure. */
285 /* The ID of the variable for the first field in this structure. */
288 /* Offset of this variable, in bits, from the base variable */
289 unsigned HOST_WIDE_INT offset
;
291 /* Size of the variable, in bits. */
292 unsigned HOST_WIDE_INT size
;
294 /* Full size of the base variable, in bits. */
295 unsigned HOST_WIDE_INT fullsize
;
297 /* Name of this variable */
300 /* Tree that this variable is associated with. */
303 /* Points-to set for this variable. */
306 /* Old points-to set for this variable. */
309 typedef struct variable_info
*varinfo_t
;
311 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
312 static varinfo_t
first_or_preceding_vi_for_offset (varinfo_t
,
313 unsigned HOST_WIDE_INT
);
314 static varinfo_t
lookup_vi_for_tree (tree
);
315 static inline bool type_can_have_subvars (const_tree
);
316 static void make_param_constraints (varinfo_t
);
318 /* Pool of variable info structures. */
319 static object_allocator
<variable_info
> variable_info_pool
320 ("Variable info pool");
322 /* Map varinfo to final pt_solution. */
323 static hash_map
<varinfo_t
, pt_solution
*> *final_solutions
;
324 struct obstack final_solutions_obstack
;
326 /* Table of variable info structures for constraint variables.
327 Indexed directly by variable info id. */
328 static vec
<varinfo_t
> varmap
;
330 /* Return the varmap element N */
332 static inline varinfo_t
333 get_varinfo (unsigned int n
)
338 /* Return the next variable in the list of sub-variables of VI
339 or NULL if VI is the last sub-variable. */
341 static inline varinfo_t
342 vi_next (varinfo_t vi
)
344 return get_varinfo (vi
->next
);
347 /* Static IDs for the special variables. Variable ID zero is unused
348 and used as terminator for the sub-variable chain. */
349 enum { nothing_id
= 1, anything_id
= 2, string_id
= 3,
350 escaped_id
= 4, nonlocal_id
= 5,
351 storedanything_id
= 6, integer_id
= 7 };
353 /* Return a new variable info structure consisting for a variable
354 named NAME, and using constraint graph node NODE. Append it
355 to the vector of variable info structures. */
358 new_var_info (tree t
, const char *name
, bool add_id
)
360 unsigned index
= varmap
.length ();
361 varinfo_t ret
= variable_info_pool
.allocate ();
363 if (dump_file
&& add_id
)
365 char *tempname
= xasprintf ("%s(%d)", name
, index
);
366 name
= ggc_strdup (tempname
);
373 /* Vars without decl are artificial and do not have sub-variables. */
374 ret
->is_artificial_var
= (t
== NULL_TREE
);
375 ret
->is_special_var
= false;
376 ret
->is_unknown_size_var
= false;
377 ret
->is_full_var
= (t
== NULL_TREE
);
378 ret
->is_heap_var
= false;
379 ret
->may_have_pointers
= true;
380 ret
->only_restrict_pointers
= false;
381 ret
->is_restrict_var
= false;
383 ret
->is_global_var
= (t
== NULL_TREE
);
384 ret
->is_ipa_escape_point
= false;
385 ret
->is_fn_info
= false;
387 ret
->is_global_var
= (is_global_var (t
)
388 /* We have to treat even local register variables
390 || (VAR_P (t
) && DECL_HARD_REGISTER (t
)));
391 ret
->solution
= BITMAP_ALLOC (&pta_obstack
);
392 ret
->oldsolution
= NULL
;
398 varmap
.safe_push (ret
);
403 /* A map mapping call statements to per-stmt variables for uses
404 and clobbers specific to the call. */
405 static hash_map
<gimple
*, varinfo_t
> *call_stmt_vars
;
407 /* Lookup or create the variable for the call statement CALL. */
410 get_call_vi (gcall
*call
)
415 varinfo_t
*slot_p
= &call_stmt_vars
->get_or_insert (call
, &existed
);
419 vi
= new_var_info (NULL_TREE
, "CALLUSED", true);
423 vi
->is_full_var
= true;
425 vi2
= new_var_info (NULL_TREE
, "CALLCLOBBERED", true);
429 vi2
->is_full_var
= true;
437 /* Lookup the variable for the call statement CALL representing
438 the uses. Returns NULL if there is nothing special about this call. */
441 lookup_call_use_vi (gcall
*call
)
443 varinfo_t
*slot_p
= call_stmt_vars
->get (call
);
450 /* Lookup the variable for the call statement CALL representing
451 the clobbers. Returns NULL if there is nothing special about this call. */
454 lookup_call_clobber_vi (gcall
*call
)
456 varinfo_t uses
= lookup_call_use_vi (call
);
460 return vi_next (uses
);
463 /* Lookup or create the variable for the call statement CALL representing
467 get_call_use_vi (gcall
*call
)
469 return get_call_vi (call
);
472 /* Lookup or create the variable for the call statement CALL representing
475 static varinfo_t ATTRIBUTE_UNUSED
476 get_call_clobber_vi (gcall
*call
)
478 return vi_next (get_call_vi (call
));
482 enum constraint_expr_type
{SCALAR
, DEREF
, ADDRESSOF
};
484 /* An expression that appears in a constraint. */
486 struct constraint_expr
488 /* Constraint type. */
489 constraint_expr_type type
;
491 /* Variable we are referring to in the constraint. */
494 /* Offset, in bits, of this constraint from the beginning of
495 variables it ends up referring to.
497 IOW, in a deref constraint, we would deref, get the result set,
498 then add OFFSET to each member. */
499 HOST_WIDE_INT offset
;
502 /* Use 0x8000... as special unknown offset. */
503 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
505 typedef struct constraint_expr ce_s
;
506 static void get_constraint_for_1 (tree
, vec
<ce_s
> *, bool, bool);
507 static void get_constraint_for (tree
, vec
<ce_s
> *);
508 static void get_constraint_for_rhs (tree
, vec
<ce_s
> *);
509 static void do_deref (vec
<ce_s
> *);
511 /* Our set constraints are made up of two constraint expressions, one
514 As described in the introduction, our set constraints each represent an
515 operation between set valued variables.
519 struct constraint_expr lhs
;
520 struct constraint_expr rhs
;
523 /* List of constraints that we use to build the constraint graph from. */
525 static vec
<constraint_t
> constraints
;
526 static object_allocator
<constraint
> constraint_pool ("Constraint pool");
528 /* The constraint graph is represented as an array of bitmaps
529 containing successor nodes. */
531 struct constraint_graph
533 /* Size of this graph, which may be different than the number of
534 nodes in the variable map. */
537 /* Explicit successors of each node. */
540 /* Implicit predecessors of each node (Used for variable
542 bitmap
*implicit_preds
;
544 /* Explicit predecessors of each node (Used for variable substitution). */
547 /* Indirect cycle representatives, or -1 if the node has no indirect
549 int *indirect_cycles
;
551 /* Representative node for a node. rep[a] == a unless the node has
555 /* Equivalence class representative for a label. This is used for
556 variable substitution. */
559 /* Pointer equivalence label for a node. All nodes with the same
560 pointer equivalence label can be unified together at some point
561 (either during constraint optimization or after the constraint
565 /* Pointer equivalence representative for a label. This is used to
566 handle nodes that are pointer equivalent but not location
567 equivalent. We can unite these once the addressof constraints
568 are transformed into initial points-to sets. */
571 /* Pointer equivalence label for each node, used during variable
573 unsigned int *pointer_label
;
575 /* Location equivalence label for each node, used during location
576 equivalence finding. */
577 unsigned int *loc_label
;
579 /* Pointed-by set for each node, used during location equivalence
580 finding. This is pointed-by rather than pointed-to, because it
581 is constructed using the predecessor graph. */
584 /* Points to sets for pointer equivalence. This is *not* the actual
585 points-to sets for nodes. */
588 /* Bitmap of nodes where the bit is set if the node is a direct
589 node. Used for variable substitution. */
590 sbitmap direct_nodes
;
592 /* Bitmap of nodes where the bit is set if the node is address
593 taken. Used for variable substitution. */
594 bitmap address_taken
;
596 /* Vector of complex constraints for each graph node. Complex
597 constraints are those involving dereferences or offsets that are
599 vec
<constraint_t
> *complex;
602 static constraint_graph_t graph
;
604 /* During variable substitution and the offline version of indirect
605 cycle finding, we create nodes to represent dereferences and
606 address taken constraints. These represent where these start and
608 #define FIRST_REF_NODE (varmap).length ()
609 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
611 /* Return the representative node for NODE, if NODE has been unioned
613 This function performs path compression along the way to finding
614 the representative. */
617 find (unsigned int node
)
619 gcc_checking_assert (node
< graph
->size
);
620 if (graph
->rep
[node
] != node
)
621 return graph
->rep
[node
] = find (graph
->rep
[node
]);
625 /* Union the TO and FROM nodes to the TO nodes.
626 Note that at some point in the future, we may want to do
627 union-by-rank, in which case we are going to have to return the
628 node we unified to. */
631 unite (unsigned int to
, unsigned int from
)
633 gcc_checking_assert (to
< graph
->size
&& from
< graph
->size
);
634 if (to
!= from
&& graph
->rep
[from
] != to
)
636 graph
->rep
[from
] = to
;
642 /* Create a new constraint consisting of LHS and RHS expressions. */
645 new_constraint (const struct constraint_expr lhs
,
646 const struct constraint_expr rhs
)
648 constraint_t ret
= constraint_pool
.allocate ();
654 /* Print out constraint C to FILE. */
657 dump_constraint (FILE *file
, constraint_t c
)
659 if (c
->lhs
.type
== ADDRESSOF
)
661 else if (c
->lhs
.type
== DEREF
)
663 fprintf (file
, "%s", get_varinfo (c
->lhs
.var
)->name
);
664 if (c
->lhs
.offset
== UNKNOWN_OFFSET
)
665 fprintf (file
, " + UNKNOWN");
666 else if (c
->lhs
.offset
!= 0)
667 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
668 fprintf (file
, " = ");
669 if (c
->rhs
.type
== ADDRESSOF
)
671 else if (c
->rhs
.type
== DEREF
)
673 fprintf (file
, "%s", get_varinfo (c
->rhs
.var
)->name
);
674 if (c
->rhs
.offset
== UNKNOWN_OFFSET
)
675 fprintf (file
, " + UNKNOWN");
676 else if (c
->rhs
.offset
!= 0)
677 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
681 void debug_constraint (constraint_t
);
682 void debug_constraints (void);
683 void debug_constraint_graph (void);
684 void debug_solution_for_var (unsigned int);
685 void debug_sa_points_to_info (void);
686 void debug_varinfo (varinfo_t
);
687 void debug_varmap (void);
689 /* Print out constraint C to stderr. */
692 debug_constraint (constraint_t c
)
694 dump_constraint (stderr
, c
);
695 fprintf (stderr
, "\n");
698 /* Print out all constraints to FILE */
701 dump_constraints (FILE *file
, int from
)
705 for (i
= from
; constraints
.iterate (i
, &c
); i
++)
708 dump_constraint (file
, c
);
709 fprintf (file
, "\n");
713 /* Print out all constraints to stderr. */
716 debug_constraints (void)
718 dump_constraints (stderr
, 0);
721 /* Print the constraint graph in dot format. */
724 dump_constraint_graph (FILE *file
)
728 /* Only print the graph if it has already been initialized: */
732 /* Prints the header of the dot file: */
733 fprintf (file
, "strict digraph {\n");
734 fprintf (file
, " node [\n shape = box\n ]\n");
735 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
736 fprintf (file
, "\n // List of nodes and complex constraints in "
737 "the constraint graph:\n");
739 /* The next lines print the nodes in the graph together with the
740 complex constraints attached to them. */
741 for (i
= 1; i
< graph
->size
; i
++)
743 if (i
== FIRST_REF_NODE
)
747 if (i
< FIRST_REF_NODE
)
748 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
750 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
751 if (graph
->complex[i
].exists ())
755 fprintf (file
, " [label=\"\\N\\n");
756 for (j
= 0; graph
->complex[i
].iterate (j
, &c
); ++j
)
758 dump_constraint (file
, c
);
759 fprintf (file
, "\\l");
761 fprintf (file
, "\"]");
763 fprintf (file
, ";\n");
766 /* Go over the edges. */
767 fprintf (file
, "\n // Edges in the constraint graph:\n");
768 for (i
= 1; i
< graph
->size
; i
++)
774 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
], 0, j
, bi
)
776 unsigned to
= find (j
);
779 if (i
< FIRST_REF_NODE
)
780 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
782 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
783 fprintf (file
, " -> ");
784 if (to
< FIRST_REF_NODE
)
785 fprintf (file
, "\"%s\"", get_varinfo (to
)->name
);
787 fprintf (file
, "\"*%s\"", get_varinfo (to
- FIRST_REF_NODE
)->name
);
788 fprintf (file
, ";\n");
792 /* Prints the tail of the dot file. */
793 fprintf (file
, "}\n");
796 /* Print out the constraint graph to stderr. */
799 debug_constraint_graph (void)
801 dump_constraint_graph (stderr
);
806 The solver is a simple worklist solver, that works on the following
809 sbitmap changed_nodes = all zeroes;
811 For each node that is not already collapsed:
813 set bit in changed nodes
815 while (changed_count > 0)
817 compute topological ordering for constraint graph
819 find and collapse cycles in the constraint graph (updating
820 changed if necessary)
822 for each node (n) in the graph in topological order:
825 Process each complex constraint associated with the node,
826 updating changed if necessary.
828 For each outgoing edge from n, propagate the solution from n to
829 the destination of the edge, updating changed as necessary.
833 /* Return true if two constraint expressions A and B are equal. */
836 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
838 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
841 /* Return true if constraint expression A is less than constraint expression
842 B. This is just arbitrary, but consistent, in order to give them an
846 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
848 if (a
.type
== b
.type
)
851 return a
.offset
< b
.offset
;
853 return a
.var
< b
.var
;
856 return a
.type
< b
.type
;
859 /* Return true if constraint A is less than constraint B. This is just
860 arbitrary, but consistent, in order to give them an ordering. */
863 constraint_less (const constraint_t
&a
, const constraint_t
&b
)
865 if (constraint_expr_less (a
->lhs
, b
->lhs
))
867 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
870 return constraint_expr_less (a
->rhs
, b
->rhs
);
873 /* Return true if two constraints A and B are equal. */
876 constraint_equal (struct constraint a
, struct constraint b
)
878 return constraint_expr_equal (a
.lhs
, b
.lhs
)
879 && constraint_expr_equal (a
.rhs
, b
.rhs
);
883 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
886 constraint_vec_find (vec
<constraint_t
> vec
,
887 struct constraint lookfor
)
895 place
= vec
.lower_bound (&lookfor
, constraint_less
);
896 if (place
>= vec
.length ())
899 if (!constraint_equal (*found
, lookfor
))
904 /* Union two constraint vectors, TO and FROM. Put the result in TO.
905 Returns true of TO set is changed. */
908 constraint_set_union (vec
<constraint_t
> *to
,
909 vec
<constraint_t
> *from
)
913 bool any_change
= false;
915 FOR_EACH_VEC_ELT (*from
, i
, c
)
917 if (constraint_vec_find (*to
, *c
) == NULL
)
919 unsigned int place
= to
->lower_bound (c
, constraint_less
);
920 to
->safe_insert (place
, c
);
927 /* Expands the solution in SET to all sub-fields of variables included. */
930 solution_set_expand (bitmap set
, bitmap
*expanded
)
938 *expanded
= BITMAP_ALLOC (&iteration_obstack
);
940 /* In a first pass expand to the head of the variables we need to
941 add all sub-fields off. This avoids quadratic behavior. */
942 EXECUTE_IF_SET_IN_BITMAP (set
, 0, j
, bi
)
944 varinfo_t v
= get_varinfo (j
);
945 if (v
->is_artificial_var
948 bitmap_set_bit (*expanded
, v
->head
);
951 /* In the second pass now expand all head variables with subfields. */
952 EXECUTE_IF_SET_IN_BITMAP (*expanded
, 0, j
, bi
)
954 varinfo_t v
= get_varinfo (j
);
957 for (v
= vi_next (v
); v
!= NULL
; v
= vi_next (v
))
958 bitmap_set_bit (*expanded
, v
->id
);
961 /* And finally set the rest of the bits from SET. */
962 bitmap_ior_into (*expanded
, set
);
967 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
971 set_union_with_increment (bitmap to
, bitmap delta
, HOST_WIDE_INT inc
,
972 bitmap
*expanded_delta
)
974 bool changed
= false;
978 /* If the solution of DELTA contains anything it is good enough to transfer
980 if (bitmap_bit_p (delta
, anything_id
))
981 return bitmap_set_bit (to
, anything_id
);
983 /* If the offset is unknown we have to expand the solution to
985 if (inc
== UNKNOWN_OFFSET
)
987 delta
= solution_set_expand (delta
, expanded_delta
);
988 changed
|= bitmap_ior_into (to
, delta
);
992 /* For non-zero offset union the offsetted solution into the destination. */
993 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, i
, bi
)
995 varinfo_t vi
= get_varinfo (i
);
997 /* If this is a variable with just one field just set its bit
999 if (vi
->is_artificial_var
1000 || vi
->is_unknown_size_var
1002 changed
|= bitmap_set_bit (to
, i
);
1005 HOST_WIDE_INT fieldoffset
= vi
->offset
+ inc
;
1006 unsigned HOST_WIDE_INT size
= vi
->size
;
1008 /* If the offset makes the pointer point to before the
1009 variable use offset zero for the field lookup. */
1010 if (fieldoffset
< 0)
1011 vi
= get_varinfo (vi
->head
);
1013 vi
= first_or_preceding_vi_for_offset (vi
, fieldoffset
);
1017 changed
|= bitmap_set_bit (to
, vi
->id
);
1022 /* We have to include all fields that overlap the current field
1026 while (vi
->offset
< fieldoffset
+ size
);
1033 /* Insert constraint C into the list of complex constraints for graph
1037 insert_into_complex (constraint_graph_t graph
,
1038 unsigned int var
, constraint_t c
)
1040 vec
<constraint_t
> complex = graph
->complex[var
];
1041 unsigned int place
= complex.lower_bound (c
, constraint_less
);
1043 /* Only insert constraints that do not already exist. */
1044 if (place
>= complex.length ()
1045 || !constraint_equal (*c
, *complex[place
]))
1046 graph
->complex[var
].safe_insert (place
, c
);
1050 /* Condense two variable nodes into a single variable node, by moving
1051 all associated info from FROM to TO. Returns true if TO node's
1052 constraint set changes after the merge. */
1055 merge_node_constraints (constraint_graph_t graph
, unsigned int to
,
1060 bool any_change
= false;
1062 gcc_checking_assert (find (from
) == to
);
1064 /* Move all complex constraints from src node into to node */
1065 FOR_EACH_VEC_ELT (graph
->complex[from
], i
, c
)
1067 /* In complex constraints for node FROM, we may have either
1068 a = *FROM, and *FROM = a, or an offseted constraint which are
1069 always added to the rhs node's constraints. */
1071 if (c
->rhs
.type
== DEREF
)
1073 else if (c
->lhs
.type
== DEREF
)
1079 any_change
= constraint_set_union (&graph
->complex[to
],
1080 &graph
->complex[from
]);
1081 graph
->complex[from
].release ();
1086 /* Remove edges involving NODE from GRAPH. */
1089 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
1091 if (graph
->succs
[node
])
1092 BITMAP_FREE (graph
->succs
[node
]);
1095 /* Merge GRAPH nodes FROM and TO into node TO. */
1098 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1101 if (graph
->indirect_cycles
[from
] != -1)
1103 /* If we have indirect cycles with the from node, and we have
1104 none on the to node, the to node has indirect cycles from the
1105 from node now that they are unified.
1106 If indirect cycles exist on both, unify the nodes that they
1107 are in a cycle with, since we know they are in a cycle with
1109 if (graph
->indirect_cycles
[to
] == -1)
1110 graph
->indirect_cycles
[to
] = graph
->indirect_cycles
[from
];
1113 /* Merge all the successor edges. */
1114 if (graph
->succs
[from
])
1116 if (!graph
->succs
[to
])
1117 graph
->succs
[to
] = BITMAP_ALLOC (&pta_obstack
);
1118 bitmap_ior_into (graph
->succs
[to
],
1119 graph
->succs
[from
]);
1122 clear_edges_for_node (graph
, from
);
1126 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1127 it doesn't exist in the graph already. */
1130 add_implicit_graph_edge (constraint_graph_t graph
, unsigned int to
,
1136 if (!graph
->implicit_preds
[to
])
1137 graph
->implicit_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1139 if (bitmap_set_bit (graph
->implicit_preds
[to
], from
))
1140 stats
.num_implicit_edges
++;
1143 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1144 it doesn't exist in the graph already.
1145 Return false if the edge already existed, true otherwise. */
1148 add_pred_graph_edge (constraint_graph_t graph
, unsigned int to
,
1151 if (!graph
->preds
[to
])
1152 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1153 bitmap_set_bit (graph
->preds
[to
], from
);
1156 /* Add a graph edge to GRAPH, going from FROM to TO if
1157 it doesn't exist in the graph already.
1158 Return false if the edge already existed, true otherwise. */
1161 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1172 if (!graph
->succs
[from
])
1173 graph
->succs
[from
] = BITMAP_ALLOC (&pta_obstack
);
1174 if (bitmap_set_bit (graph
->succs
[from
], to
))
1177 if (to
< FIRST_REF_NODE
&& from
< FIRST_REF_NODE
)
1185 /* Initialize the constraint graph structure to contain SIZE nodes. */
1188 init_graph (unsigned int size
)
1192 graph
= XCNEW (struct constraint_graph
);
1194 graph
->succs
= XCNEWVEC (bitmap
, graph
->size
);
1195 graph
->indirect_cycles
= XNEWVEC (int, graph
->size
);
1196 graph
->rep
= XNEWVEC (unsigned int, graph
->size
);
1197 /* ??? Macros do not support template types with multiple arguments,
1198 so we use a typedef to work around it. */
1199 typedef vec
<constraint_t
> vec_constraint_t_heap
;
1200 graph
->complex = XCNEWVEC (vec_constraint_t_heap
, size
);
1201 graph
->pe
= XCNEWVEC (unsigned int, graph
->size
);
1202 graph
->pe_rep
= XNEWVEC (int, graph
->size
);
1204 for (j
= 0; j
< graph
->size
; j
++)
1207 graph
->pe_rep
[j
] = -1;
1208 graph
->indirect_cycles
[j
] = -1;
1212 /* Build the constraint graph, adding only predecessor edges right now. */
1215 build_pred_graph (void)
1221 graph
->implicit_preds
= XCNEWVEC (bitmap
, graph
->size
);
1222 graph
->preds
= XCNEWVEC (bitmap
, graph
->size
);
1223 graph
->pointer_label
= XCNEWVEC (unsigned int, graph
->size
);
1224 graph
->loc_label
= XCNEWVEC (unsigned int, graph
->size
);
1225 graph
->pointed_by
= XCNEWVEC (bitmap
, graph
->size
);
1226 graph
->points_to
= XCNEWVEC (bitmap
, graph
->size
);
1227 graph
->eq_rep
= XNEWVEC (int, graph
->size
);
1228 graph
->direct_nodes
= sbitmap_alloc (graph
->size
);
1229 graph
->address_taken
= BITMAP_ALLOC (&predbitmap_obstack
);
1230 bitmap_clear (graph
->direct_nodes
);
1232 for (j
= 1; j
< FIRST_REF_NODE
; j
++)
1234 if (!get_varinfo (j
)->is_special_var
)
1235 bitmap_set_bit (graph
->direct_nodes
, j
);
1238 for (j
= 0; j
< graph
->size
; j
++)
1239 graph
->eq_rep
[j
] = -1;
1241 for (j
= 0; j
< varmap
.length (); j
++)
1242 graph
->indirect_cycles
[j
] = -1;
1244 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1246 struct constraint_expr lhs
= c
->lhs
;
1247 struct constraint_expr rhs
= c
->rhs
;
1248 unsigned int lhsvar
= lhs
.var
;
1249 unsigned int rhsvar
= rhs
.var
;
1251 if (lhs
.type
== DEREF
)
1254 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1255 add_pred_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1257 else if (rhs
.type
== DEREF
)
1260 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1261 add_pred_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1263 bitmap_clear_bit (graph
->direct_nodes
, lhsvar
);
1265 else if (rhs
.type
== ADDRESSOF
)
1270 if (graph
->points_to
[lhsvar
] == NULL
)
1271 graph
->points_to
[lhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1272 bitmap_set_bit (graph
->points_to
[lhsvar
], rhsvar
);
1274 if (graph
->pointed_by
[rhsvar
] == NULL
)
1275 graph
->pointed_by
[rhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1276 bitmap_set_bit (graph
->pointed_by
[rhsvar
], lhsvar
);
1278 /* Implicitly, *x = y */
1279 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1281 /* All related variables are no longer direct nodes. */
1282 bitmap_clear_bit (graph
->direct_nodes
, rhsvar
);
1283 v
= get_varinfo (rhsvar
);
1284 if (!v
->is_full_var
)
1286 v
= get_varinfo (v
->head
);
1289 bitmap_clear_bit (graph
->direct_nodes
, v
->id
);
1294 bitmap_set_bit (graph
->address_taken
, rhsvar
);
1296 else if (lhsvar
> anything_id
1297 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1300 add_pred_graph_edge (graph
, lhsvar
, rhsvar
);
1301 /* Implicitly, *x = *y */
1302 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
,
1303 FIRST_REF_NODE
+ rhsvar
);
1305 else if (lhs
.offset
!= 0 || rhs
.offset
!= 0)
1307 if (rhs
.offset
!= 0)
1308 bitmap_clear_bit (graph
->direct_nodes
, lhs
.var
);
1309 else if (lhs
.offset
!= 0)
1310 bitmap_clear_bit (graph
->direct_nodes
, rhs
.var
);
1315 /* Build the constraint graph, adding successor edges. */
1318 build_succ_graph (void)
1323 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1325 struct constraint_expr lhs
;
1326 struct constraint_expr rhs
;
1327 unsigned int lhsvar
;
1328 unsigned int rhsvar
;
1335 lhsvar
= find (lhs
.var
);
1336 rhsvar
= find (rhs
.var
);
1338 if (lhs
.type
== DEREF
)
1340 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1341 add_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1343 else if (rhs
.type
== DEREF
)
1345 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1346 add_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1348 else if (rhs
.type
== ADDRESSOF
)
1351 gcc_checking_assert (find (rhs
.var
) == rhs
.var
);
1352 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1354 else if (lhsvar
> anything_id
1355 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1357 add_graph_edge (graph
, lhsvar
, rhsvar
);
1361 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1362 receive pointers. */
1363 t
= find (storedanything_id
);
1364 for (i
= integer_id
+ 1; i
< FIRST_REF_NODE
; ++i
)
1366 if (!bitmap_bit_p (graph
->direct_nodes
, i
)
1367 && get_varinfo (i
)->may_have_pointers
)
1368 add_graph_edge (graph
, find (i
), t
);
1371 /* Everything stored to ANYTHING also potentially escapes. */
1372 add_graph_edge (graph
, find (escaped_id
), t
);
1376 /* Changed variables on the last iteration. */
1377 static bitmap changed
;
1379 /* Strongly Connected Component visitation info. */
1383 scc_info (size_t size
);
1386 auto_sbitmap visited
;
1387 auto_sbitmap deleted
;
1389 unsigned int *node_mapping
;
1391 auto_vec
<unsigned> scc_stack
;
1395 /* Recursive routine to find strongly connected components in GRAPH.
1396 SI is the SCC info to store the information in, and N is the id of current
1397 graph node we are processing.
1399 This is Tarjan's strongly connected component finding algorithm, as
1400 modified by Nuutila to keep only non-root nodes on the stack.
1401 The algorithm can be found in "On finding the strongly connected
1402 connected components in a directed graph" by Esko Nuutila and Eljas
1403 Soisalon-Soininen, in Information Processing Letters volume 49,
1404 number 1, pages 9-14. */
1407 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1411 unsigned int my_dfs
;
1413 bitmap_set_bit (si
->visited
, n
);
1414 si
->dfs
[n
] = si
->current_index
++;
1415 my_dfs
= si
->dfs
[n
];
1417 /* Visit all the successors. */
1418 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
1422 if (i
> LAST_REF_NODE
)
1426 if (bitmap_bit_p (si
->deleted
, w
))
1429 if (!bitmap_bit_p (si
->visited
, w
))
1430 scc_visit (graph
, si
, w
);
1432 unsigned int t
= find (w
);
1433 gcc_checking_assert (find (n
) == n
);
1434 if (si
->dfs
[t
] < si
->dfs
[n
])
1435 si
->dfs
[n
] = si
->dfs
[t
];
1438 /* See if any components have been identified. */
1439 if (si
->dfs
[n
] == my_dfs
)
1441 if (si
->scc_stack
.length () > 0
1442 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1444 bitmap scc
= BITMAP_ALLOC (NULL
);
1445 unsigned int lowest_node
;
1448 bitmap_set_bit (scc
, n
);
1450 while (si
->scc_stack
.length () != 0
1451 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1453 unsigned int w
= si
->scc_stack
.pop ();
1455 bitmap_set_bit (scc
, w
);
1458 lowest_node
= bitmap_first_set_bit (scc
);
1459 gcc_assert (lowest_node
< FIRST_REF_NODE
);
1461 /* Collapse the SCC nodes into a single node, and mark the
1463 EXECUTE_IF_SET_IN_BITMAP (scc
, 0, i
, bi
)
1465 if (i
< FIRST_REF_NODE
)
1467 if (unite (lowest_node
, i
))
1468 unify_nodes (graph
, lowest_node
, i
, false);
1472 unite (lowest_node
, i
);
1473 graph
->indirect_cycles
[i
- FIRST_REF_NODE
] = lowest_node
;
1477 bitmap_set_bit (si
->deleted
, n
);
1480 si
->scc_stack
.safe_push (n
);
1483 /* Unify node FROM into node TO, updating the changed count if
1484 necessary when UPDATE_CHANGED is true. */
1487 unify_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1488 bool update_changed
)
1490 gcc_checking_assert (to
!= from
&& find (to
) == to
);
1492 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1493 fprintf (dump_file
, "Unifying %s to %s\n",
1494 get_varinfo (from
)->name
,
1495 get_varinfo (to
)->name
);
1498 stats
.unified_vars_dynamic
++;
1500 stats
.unified_vars_static
++;
1502 merge_graph_nodes (graph
, to
, from
);
1503 if (merge_node_constraints (graph
, to
, from
))
1506 bitmap_set_bit (changed
, to
);
1509 /* Mark TO as changed if FROM was changed. If TO was already marked
1510 as changed, decrease the changed count. */
1513 && bitmap_clear_bit (changed
, from
))
1514 bitmap_set_bit (changed
, to
);
1515 varinfo_t fromvi
= get_varinfo (from
);
1516 if (fromvi
->solution
)
1518 /* If the solution changes because of the merging, we need to mark
1519 the variable as changed. */
1520 varinfo_t tovi
= get_varinfo (to
);
1521 if (bitmap_ior_into (tovi
->solution
, fromvi
->solution
))
1524 bitmap_set_bit (changed
, to
);
1527 BITMAP_FREE (fromvi
->solution
);
1528 if (fromvi
->oldsolution
)
1529 BITMAP_FREE (fromvi
->oldsolution
);
1531 if (stats
.iterations
> 0
1532 && tovi
->oldsolution
)
1533 BITMAP_FREE (tovi
->oldsolution
);
1535 if (graph
->succs
[to
])
1536 bitmap_clear_bit (graph
->succs
[to
], to
);
1539 /* Information needed to compute the topological ordering of a graph. */
1543 /* sbitmap of visited nodes. */
1545 /* Array that stores the topological order of the graph, *in
1547 vec
<unsigned> topo_order
;
1551 /* Initialize and return a topological info structure. */
1553 static struct topo_info
*
1554 init_topo_info (void)
1556 size_t size
= graph
->size
;
1557 struct topo_info
*ti
= XNEW (struct topo_info
);
1558 ti
->visited
= sbitmap_alloc (size
);
1559 bitmap_clear (ti
->visited
);
1560 ti
->topo_order
.create (1);
1565 /* Free the topological sort info pointed to by TI. */
1568 free_topo_info (struct topo_info
*ti
)
1570 sbitmap_free (ti
->visited
);
1571 ti
->topo_order
.release ();
1575 /* Visit the graph in topological order, and store the order in the
1576 topo_info structure. */
1579 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1585 bitmap_set_bit (ti
->visited
, n
);
1587 if (graph
->succs
[n
])
1588 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[n
], 0, j
, bi
)
1590 if (!bitmap_bit_p (ti
->visited
, j
))
1591 topo_visit (graph
, ti
, j
);
1594 ti
->topo_order
.safe_push (n
);
1597 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1598 starting solution for y. */
1601 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1602 bitmap delta
, bitmap
*expanded_delta
)
1604 unsigned int lhs
= c
->lhs
.var
;
1606 bitmap sol
= get_varinfo (lhs
)->solution
;
1609 HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1611 /* Our IL does not allow this. */
1612 gcc_checking_assert (c
->lhs
.offset
== 0);
1614 /* If the solution of Y contains anything it is good enough to transfer
1616 if (bitmap_bit_p (delta
, anything_id
))
1618 flag
|= bitmap_set_bit (sol
, anything_id
);
1622 /* If we do not know at with offset the rhs is dereferenced compute
1623 the reachability set of DELTA, conservatively assuming it is
1624 dereferenced at all valid offsets. */
1625 if (roffset
== UNKNOWN_OFFSET
)
1627 delta
= solution_set_expand (delta
, expanded_delta
);
1628 /* No further offset processing is necessary. */
1632 /* For each variable j in delta (Sol(y)), add
1633 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1634 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1636 varinfo_t v
= get_varinfo (j
);
1637 HOST_WIDE_INT fieldoffset
= v
->offset
+ roffset
;
1638 unsigned HOST_WIDE_INT size
= v
->size
;
1643 else if (roffset
!= 0)
1645 if (fieldoffset
< 0)
1646 v
= get_varinfo (v
->head
);
1648 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1651 /* We have to include all fields that overlap the current field
1652 shifted by roffset. */
1657 /* Adding edges from the special vars is pointless.
1658 They don't have sets that can change. */
1659 if (get_varinfo (t
)->is_special_var
)
1660 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1661 /* Merging the solution from ESCAPED needlessly increases
1662 the set. Use ESCAPED as representative instead. */
1663 else if (v
->id
== escaped_id
)
1664 flag
|= bitmap_set_bit (sol
, escaped_id
);
1665 else if (v
->may_have_pointers
1666 && add_graph_edge (graph
, lhs
, t
))
1667 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1675 while (v
->offset
< fieldoffset
+ size
);
1679 /* If the LHS solution changed, mark the var as changed. */
1682 get_varinfo (lhs
)->solution
= sol
;
1683 bitmap_set_bit (changed
, lhs
);
1687 /* Process a constraint C that represents *(x + off) = y using DELTA
1688 as the starting solution for x. */
1691 do_ds_constraint (constraint_t c
, bitmap delta
, bitmap
*expanded_delta
)
1693 unsigned int rhs
= c
->rhs
.var
;
1694 bitmap sol
= get_varinfo (rhs
)->solution
;
1697 HOST_WIDE_INT loff
= c
->lhs
.offset
;
1698 bool escaped_p
= false;
1700 /* Our IL does not allow this. */
1701 gcc_checking_assert (c
->rhs
.offset
== 0);
1703 /* If the solution of y contains ANYTHING simply use the ANYTHING
1704 solution. This avoids needlessly increasing the points-to sets. */
1705 if (bitmap_bit_p (sol
, anything_id
))
1706 sol
= get_varinfo (find (anything_id
))->solution
;
1708 /* If the solution for x contains ANYTHING we have to merge the
1709 solution of y into all pointer variables which we do via
1711 if (bitmap_bit_p (delta
, anything_id
))
1713 unsigned t
= find (storedanything_id
);
1714 if (add_graph_edge (graph
, t
, rhs
))
1716 if (bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1717 bitmap_set_bit (changed
, t
);
1722 /* If we do not know at with offset the rhs is dereferenced compute
1723 the reachability set of DELTA, conservatively assuming it is
1724 dereferenced at all valid offsets. */
1725 if (loff
== UNKNOWN_OFFSET
)
1727 delta
= solution_set_expand (delta
, expanded_delta
);
1731 /* For each member j of delta (Sol(x)), add an edge from y to j and
1732 union Sol(y) into Sol(j) */
1733 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1735 varinfo_t v
= get_varinfo (j
);
1737 HOST_WIDE_INT fieldoffset
= v
->offset
+ loff
;
1738 unsigned HOST_WIDE_INT size
= v
->size
;
1744 if (fieldoffset
< 0)
1745 v
= get_varinfo (v
->head
);
1747 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1750 /* We have to include all fields that overlap the current field
1754 if (v
->may_have_pointers
)
1756 /* If v is a global variable then this is an escape point. */
1757 if (v
->is_global_var
1760 t
= find (escaped_id
);
1761 if (add_graph_edge (graph
, t
, rhs
)
1762 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1763 bitmap_set_bit (changed
, t
);
1764 /* Enough to let rhs escape once. */
1768 if (v
->is_special_var
)
1772 if (add_graph_edge (graph
, t
, rhs
)
1773 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1774 bitmap_set_bit (changed
, t
);
1783 while (v
->offset
< fieldoffset
+ size
);
1787 /* Handle a non-simple (simple meaning requires no iteration),
1788 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1791 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
,
1792 bitmap
*expanded_delta
)
1794 if (c
->lhs
.type
== DEREF
)
1796 if (c
->rhs
.type
== ADDRESSOF
)
1803 do_ds_constraint (c
, delta
, expanded_delta
);
1806 else if (c
->rhs
.type
== DEREF
)
1809 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1810 do_sd_constraint (graph
, c
, delta
, expanded_delta
);
1817 gcc_checking_assert (c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
1818 && c
->rhs
.offset
!= 0 && c
->lhs
.offset
== 0);
1819 tmp
= get_varinfo (c
->lhs
.var
)->solution
;
1821 flag
= set_union_with_increment (tmp
, delta
, c
->rhs
.offset
,
1825 bitmap_set_bit (changed
, c
->lhs
.var
);
1829 /* Initialize and return a new SCC info structure. */
1831 scc_info::scc_info (size_t size
) :
1832 visited (size
), deleted (size
), current_index (0), scc_stack (1)
1834 bitmap_clear (visited
);
1835 bitmap_clear (deleted
);
1836 node_mapping
= XNEWVEC (unsigned int, size
);
1837 dfs
= XCNEWVEC (unsigned int, size
);
1839 for (size_t i
= 0; i
< size
; i
++)
1840 node_mapping
[i
] = i
;
1843 /* Free an SCC info structure pointed to by SI */
1845 scc_info::~scc_info ()
1847 free (node_mapping
);
1852 /* Find indirect cycles in GRAPH that occur, using strongly connected
1853 components, and note them in the indirect cycles map.
1855 This technique comes from Ben Hardekopf and Calvin Lin,
1856 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1857 Lines of Code", submitted to PLDI 2007. */
1860 find_indirect_cycles (constraint_graph_t graph
)
1863 unsigned int size
= graph
->size
;
1866 for (i
= 0; i
< MIN (LAST_REF_NODE
, size
); i
++ )
1867 if (!bitmap_bit_p (si
.visited
, i
) && find (i
) == i
)
1868 scc_visit (graph
, &si
, i
);
1871 /* Compute a topological ordering for GRAPH, and store the result in the
1872 topo_info structure TI. */
1875 compute_topo_order (constraint_graph_t graph
,
1876 struct topo_info
*ti
)
1879 unsigned int size
= graph
->size
;
1881 for (i
= 0; i
!= size
; ++i
)
1882 if (!bitmap_bit_p (ti
->visited
, i
) && find (i
) == i
)
1883 topo_visit (graph
, ti
, i
);
1886 /* Structure used to for hash value numbering of pointer equivalence
1889 typedef struct equiv_class_label
1892 unsigned int equivalence_class
;
1894 } *equiv_class_label_t
;
1895 typedef const struct equiv_class_label
*const_equiv_class_label_t
;
1897 /* Equiv_class_label hashtable helpers. */
1899 struct equiv_class_hasher
: free_ptr_hash
<equiv_class_label
>
1901 static inline hashval_t
hash (const equiv_class_label
*);
1902 static inline bool equal (const equiv_class_label
*,
1903 const equiv_class_label
*);
1906 /* Hash function for a equiv_class_label_t */
1909 equiv_class_hasher::hash (const equiv_class_label
*ecl
)
1911 return ecl
->hashcode
;
1914 /* Equality function for two equiv_class_label_t's. */
1917 equiv_class_hasher::equal (const equiv_class_label
*eql1
,
1918 const equiv_class_label
*eql2
)
1920 return (eql1
->hashcode
== eql2
->hashcode
1921 && bitmap_equal_p (eql1
->labels
, eql2
->labels
));
1924 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1926 static hash_table
<equiv_class_hasher
> *pointer_equiv_class_table
;
1928 /* A hashtable for mapping a bitmap of labels->location equivalence
1930 static hash_table
<equiv_class_hasher
> *location_equiv_class_table
;
1932 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1933 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1934 is equivalent to. */
1936 static equiv_class_label
*
1937 equiv_class_lookup_or_add (hash_table
<equiv_class_hasher
> *table
,
1940 equiv_class_label
**slot
;
1941 equiv_class_label ecl
;
1943 ecl
.labels
= labels
;
1944 ecl
.hashcode
= bitmap_hash (labels
);
1945 slot
= table
->find_slot (&ecl
, INSERT
);
1948 *slot
= XNEW (struct equiv_class_label
);
1949 (*slot
)->labels
= labels
;
1950 (*slot
)->hashcode
= ecl
.hashcode
;
1951 (*slot
)->equivalence_class
= 0;
1957 /* Perform offline variable substitution.
1959 This is a worst case quadratic time way of identifying variables
1960 that must have equivalent points-to sets, including those caused by
1961 static cycles, and single entry subgraphs, in the constraint graph.
1963 The technique is described in "Exploiting Pointer and Location
1964 Equivalence to Optimize Pointer Analysis. In the 14th International
1965 Static Analysis Symposium (SAS), August 2007." It is known as the
1966 "HU" algorithm, and is equivalent to value numbering the collapsed
1967 constraint graph including evaluating unions.
1969 The general method of finding equivalence classes is as follows:
1970 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1971 Initialize all non-REF nodes to be direct nodes.
1972 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1974 For each constraint containing the dereference, we also do the same
1977 We then compute SCC's in the graph and unify nodes in the same SCC,
1980 For each non-collapsed node x:
1981 Visit all unvisited explicit incoming edges.
1982 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1984 Lookup the equivalence class for pts(x).
1985 If we found one, equivalence_class(x) = found class.
1986 Otherwise, equivalence_class(x) = new class, and new_class is
1987 added to the lookup table.
1989 All direct nodes with the same equivalence class can be replaced
1990 with a single representative node.
1991 All unlabeled nodes (label == 0) are not pointers and all edges
1992 involving them can be eliminated.
1993 We perform these optimizations during rewrite_constraints
1995 In addition to pointer equivalence class finding, we also perform
1996 location equivalence class finding. This is the set of variables
1997 that always appear together in points-to sets. We use this to
1998 compress the size of the points-to sets. */
2000 /* Current maximum pointer equivalence class id. */
2001 static int pointer_equiv_class
;
2003 /* Current maximum location equivalence class id. */
2004 static int location_equiv_class
;
2006 /* Recursive routine to find strongly connected components in GRAPH,
2007 and label it's nodes with DFS numbers. */
2010 condense_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2014 unsigned int my_dfs
;
2016 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2017 bitmap_set_bit (si
->visited
, n
);
2018 si
->dfs
[n
] = si
->current_index
++;
2019 my_dfs
= si
->dfs
[n
];
2021 /* Visit all the successors. */
2022 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2024 unsigned int w
= si
->node_mapping
[i
];
2026 if (bitmap_bit_p (si
->deleted
, w
))
2029 if (!bitmap_bit_p (si
->visited
, w
))
2030 condense_visit (graph
, si
, w
);
2032 unsigned int t
= si
->node_mapping
[w
];
2033 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2034 if (si
->dfs
[t
] < si
->dfs
[n
])
2035 si
->dfs
[n
] = si
->dfs
[t
];
2038 /* Visit all the implicit predecessors. */
2039 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->implicit_preds
[n
], 0, i
, bi
)
2041 unsigned int w
= si
->node_mapping
[i
];
2043 if (bitmap_bit_p (si
->deleted
, w
))
2046 if (!bitmap_bit_p (si
->visited
, w
))
2047 condense_visit (graph
, si
, w
);
2049 unsigned int t
= si
->node_mapping
[w
];
2050 gcc_assert (si
->node_mapping
[n
] == n
);
2051 if (si
->dfs
[t
] < si
->dfs
[n
])
2052 si
->dfs
[n
] = si
->dfs
[t
];
2055 /* See if any components have been identified. */
2056 if (si
->dfs
[n
] == my_dfs
)
2058 while (si
->scc_stack
.length () != 0
2059 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
2061 unsigned int w
= si
->scc_stack
.pop ();
2062 si
->node_mapping
[w
] = n
;
2064 if (!bitmap_bit_p (graph
->direct_nodes
, w
))
2065 bitmap_clear_bit (graph
->direct_nodes
, n
);
2067 /* Unify our nodes. */
2068 if (graph
->preds
[w
])
2070 if (!graph
->preds
[n
])
2071 graph
->preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2072 bitmap_ior_into (graph
->preds
[n
], graph
->preds
[w
]);
2074 if (graph
->implicit_preds
[w
])
2076 if (!graph
->implicit_preds
[n
])
2077 graph
->implicit_preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2078 bitmap_ior_into (graph
->implicit_preds
[n
],
2079 graph
->implicit_preds
[w
]);
2081 if (graph
->points_to
[w
])
2083 if (!graph
->points_to
[n
])
2084 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2085 bitmap_ior_into (graph
->points_to
[n
],
2086 graph
->points_to
[w
]);
2089 bitmap_set_bit (si
->deleted
, n
);
2092 si
->scc_stack
.safe_push (n
);
2095 /* Label pointer equivalences.
2097 This performs a value numbering of the constraint graph to
2098 discover which variables will always have the same points-to sets
2099 under the current set of constraints.
2101 The way it value numbers is to store the set of points-to bits
2102 generated by the constraints and graph edges. This is just used as a
2103 hash and equality comparison. The *actual set of points-to bits* is
2104 completely irrelevant, in that we don't care about being able to
2107 The equality values (currently bitmaps) just have to satisfy a few
2108 constraints, the main ones being:
2109 1. The combining operation must be order independent.
2110 2. The end result of a given set of operations must be unique iff the
2111 combination of input values is unique
2115 label_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2117 unsigned int i
, first_pred
;
2120 bitmap_set_bit (si
->visited
, n
);
2122 /* Label and union our incoming edges's points to sets. */
2124 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2126 unsigned int w
= si
->node_mapping
[i
];
2127 if (!bitmap_bit_p (si
->visited
, w
))
2128 label_visit (graph
, si
, w
);
2130 /* Skip unused edges */
2131 if (w
== n
|| graph
->pointer_label
[w
] == 0)
2134 if (graph
->points_to
[w
])
2136 if (!graph
->points_to
[n
])
2138 if (first_pred
== -1U)
2142 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2143 bitmap_ior (graph
->points_to
[n
],
2144 graph
->points_to
[first_pred
],
2145 graph
->points_to
[w
]);
2149 bitmap_ior_into (graph
->points_to
[n
], graph
->points_to
[w
]);
2153 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2154 if (!bitmap_bit_p (graph
->direct_nodes
, n
))
2156 if (!graph
->points_to
[n
])
2158 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2159 if (first_pred
!= -1U)
2160 bitmap_copy (graph
->points_to
[n
], graph
->points_to
[first_pred
]);
2162 bitmap_set_bit (graph
->points_to
[n
], FIRST_REF_NODE
+ n
);
2163 graph
->pointer_label
[n
] = pointer_equiv_class
++;
2164 equiv_class_label_t ecl
;
2165 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2166 graph
->points_to
[n
]);
2167 ecl
->equivalence_class
= graph
->pointer_label
[n
];
2171 /* If there was only a single non-empty predecessor the pointer equiv
2172 class is the same. */
2173 if (!graph
->points_to
[n
])
2175 if (first_pred
!= -1U)
2177 graph
->pointer_label
[n
] = graph
->pointer_label
[first_pred
];
2178 graph
->points_to
[n
] = graph
->points_to
[first_pred
];
2183 if (!bitmap_empty_p (graph
->points_to
[n
]))
2185 equiv_class_label_t ecl
;
2186 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2187 graph
->points_to
[n
]);
2188 if (ecl
->equivalence_class
== 0)
2189 ecl
->equivalence_class
= pointer_equiv_class
++;
2192 BITMAP_FREE (graph
->points_to
[n
]);
2193 graph
->points_to
[n
] = ecl
->labels
;
2195 graph
->pointer_label
[n
] = ecl
->equivalence_class
;
2199 /* Print the pred graph in dot format. */
2202 dump_pred_graph (struct scc_info
*si
, FILE *file
)
2206 /* Only print the graph if it has already been initialized: */
2210 /* Prints the header of the dot file: */
2211 fprintf (file
, "strict digraph {\n");
2212 fprintf (file
, " node [\n shape = box\n ]\n");
2213 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
2214 fprintf (file
, "\n // List of nodes and complex constraints in "
2215 "the constraint graph:\n");
2217 /* The next lines print the nodes in the graph together with the
2218 complex constraints attached to them. */
2219 for (i
= 1; i
< graph
->size
; i
++)
2221 if (i
== FIRST_REF_NODE
)
2223 if (si
->node_mapping
[i
] != i
)
2225 if (i
< FIRST_REF_NODE
)
2226 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2228 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2229 if (graph
->points_to
[i
]
2230 && !bitmap_empty_p (graph
->points_to
[i
]))
2232 if (i
< FIRST_REF_NODE
)
2233 fprintf (file
, "[label=\"%s = {", get_varinfo (i
)->name
);
2235 fprintf (file
, "[label=\"*%s = {",
2236 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2239 EXECUTE_IF_SET_IN_BITMAP (graph
->points_to
[i
], 0, j
, bi
)
2240 fprintf (file
, " %d", j
);
2241 fprintf (file
, " }\"]");
2243 fprintf (file
, ";\n");
2246 /* Go over the edges. */
2247 fprintf (file
, "\n // Edges in the constraint graph:\n");
2248 for (i
= 1; i
< graph
->size
; i
++)
2252 if (si
->node_mapping
[i
] != i
)
2254 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[i
], 0, j
, bi
)
2256 unsigned from
= si
->node_mapping
[j
];
2257 if (from
< FIRST_REF_NODE
)
2258 fprintf (file
, "\"%s\"", get_varinfo (from
)->name
);
2260 fprintf (file
, "\"*%s\"", get_varinfo (from
- FIRST_REF_NODE
)->name
);
2261 fprintf (file
, " -> ");
2262 if (i
< FIRST_REF_NODE
)
2263 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2265 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2266 fprintf (file
, ";\n");
2270 /* Prints the tail of the dot file. */
2271 fprintf (file
, "}\n");
2274 /* Perform offline variable substitution, discovering equivalence
2275 classes, and eliminating non-pointer variables. */
2277 static struct scc_info
*
2278 perform_var_substitution (constraint_graph_t graph
)
2281 unsigned int size
= graph
->size
;
2282 scc_info
*si
= new scc_info (size
);
2284 bitmap_obstack_initialize (&iteration_obstack
);
2285 pointer_equiv_class_table
= new hash_table
<equiv_class_hasher
> (511);
2286 location_equiv_class_table
2287 = new hash_table
<equiv_class_hasher
> (511);
2288 pointer_equiv_class
= 1;
2289 location_equiv_class
= 1;
2291 /* Condense the nodes, which means to find SCC's, count incoming
2292 predecessors, and unite nodes in SCC's. */
2293 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2294 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2295 condense_visit (graph
, si
, si
->node_mapping
[i
]);
2297 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
2299 fprintf (dump_file
, "\n\n// The constraint graph before var-substitution "
2300 "in dot format:\n");
2301 dump_pred_graph (si
, dump_file
);
2302 fprintf (dump_file
, "\n\n");
2305 bitmap_clear (si
->visited
);
2306 /* Actually the label the nodes for pointer equivalences */
2307 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2308 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2309 label_visit (graph
, si
, si
->node_mapping
[i
]);
2311 /* Calculate location equivalence labels. */
2312 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2318 if (!graph
->pointed_by
[i
])
2320 pointed_by
= BITMAP_ALLOC (&iteration_obstack
);
2322 /* Translate the pointed-by mapping for pointer equivalence
2324 EXECUTE_IF_SET_IN_BITMAP (graph
->pointed_by
[i
], 0, j
, bi
)
2326 bitmap_set_bit (pointed_by
,
2327 graph
->pointer_label
[si
->node_mapping
[j
]]);
2329 /* The original pointed_by is now dead. */
2330 BITMAP_FREE (graph
->pointed_by
[i
]);
2332 /* Look up the location equivalence label if one exists, or make
2334 equiv_class_label_t ecl
;
2335 ecl
= equiv_class_lookup_or_add (location_equiv_class_table
, pointed_by
);
2336 if (ecl
->equivalence_class
== 0)
2337 ecl
->equivalence_class
= location_equiv_class
++;
2340 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2341 fprintf (dump_file
, "Found location equivalence for node %s\n",
2342 get_varinfo (i
)->name
);
2343 BITMAP_FREE (pointed_by
);
2345 graph
->loc_label
[i
] = ecl
->equivalence_class
;
2349 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2350 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2352 unsigned j
= si
->node_mapping
[i
];
2355 fprintf (dump_file
, "%s node id %d ",
2356 bitmap_bit_p (graph
->direct_nodes
, i
)
2357 ? "Direct" : "Indirect", i
);
2358 if (i
< FIRST_REF_NODE
)
2359 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2361 fprintf (dump_file
, "\"*%s\"",
2362 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2363 fprintf (dump_file
, " mapped to SCC leader node id %d ", j
);
2364 if (j
< FIRST_REF_NODE
)
2365 fprintf (dump_file
, "\"%s\"\n", get_varinfo (j
)->name
);
2367 fprintf (dump_file
, "\"*%s\"\n",
2368 get_varinfo (j
- FIRST_REF_NODE
)->name
);
2373 "Equivalence classes for %s node id %d ",
2374 bitmap_bit_p (graph
->direct_nodes
, i
)
2375 ? "direct" : "indirect", i
);
2376 if (i
< FIRST_REF_NODE
)
2377 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2379 fprintf (dump_file
, "\"*%s\"",
2380 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2382 ": pointer %d, location %d\n",
2383 graph
->pointer_label
[i
], graph
->loc_label
[i
]);
2387 /* Quickly eliminate our non-pointer variables. */
2389 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2391 unsigned int node
= si
->node_mapping
[i
];
2393 if (graph
->pointer_label
[node
] == 0)
2395 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2397 "%s is a non-pointer variable, eliminating edges.\n",
2398 get_varinfo (node
)->name
);
2399 stats
.nonpointer_vars
++;
2400 clear_edges_for_node (graph
, node
);
2407 /* Free information that was only necessary for variable
2411 free_var_substitution_info (struct scc_info
*si
)
2414 free (graph
->pointer_label
);
2415 free (graph
->loc_label
);
2416 free (graph
->pointed_by
);
2417 free (graph
->points_to
);
2418 free (graph
->eq_rep
);
2419 sbitmap_free (graph
->direct_nodes
);
2420 delete pointer_equiv_class_table
;
2421 pointer_equiv_class_table
= NULL
;
2422 delete location_equiv_class_table
;
2423 location_equiv_class_table
= NULL
;
2424 bitmap_obstack_release (&iteration_obstack
);
2427 /* Return an existing node that is equivalent to NODE, which has
2428 equivalence class LABEL, if one exists. Return NODE otherwise. */
2431 find_equivalent_node (constraint_graph_t graph
,
2432 unsigned int node
, unsigned int label
)
2434 /* If the address version of this variable is unused, we can
2435 substitute it for anything else with the same label.
2436 Otherwise, we know the pointers are equivalent, but not the
2437 locations, and we can unite them later. */
2439 if (!bitmap_bit_p (graph
->address_taken
, node
))
2441 gcc_checking_assert (label
< graph
->size
);
2443 if (graph
->eq_rep
[label
] != -1)
2445 /* Unify the two variables since we know they are equivalent. */
2446 if (unite (graph
->eq_rep
[label
], node
))
2447 unify_nodes (graph
, graph
->eq_rep
[label
], node
, false);
2448 return graph
->eq_rep
[label
];
2452 graph
->eq_rep
[label
] = node
;
2453 graph
->pe_rep
[label
] = node
;
2458 gcc_checking_assert (label
< graph
->size
);
2459 graph
->pe
[node
] = label
;
2460 if (graph
->pe_rep
[label
] == -1)
2461 graph
->pe_rep
[label
] = node
;
2467 /* Unite pointer equivalent but not location equivalent nodes in
2468 GRAPH. This may only be performed once variable substitution is
2472 unite_pointer_equivalences (constraint_graph_t graph
)
2476 /* Go through the pointer equivalences and unite them to their
2477 representative, if they aren't already. */
2478 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2480 unsigned int label
= graph
->pe
[i
];
2483 int label_rep
= graph
->pe_rep
[label
];
2485 if (label_rep
== -1)
2488 label_rep
= find (label_rep
);
2489 if (label_rep
>= 0 && unite (label_rep
, find (i
)))
2490 unify_nodes (graph
, label_rep
, i
, false);
2495 /* Move complex constraints to the GRAPH nodes they belong to. */
2498 move_complex_constraints (constraint_graph_t graph
)
2503 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2507 struct constraint_expr lhs
= c
->lhs
;
2508 struct constraint_expr rhs
= c
->rhs
;
2510 if (lhs
.type
== DEREF
)
2512 insert_into_complex (graph
, lhs
.var
, c
);
2514 else if (rhs
.type
== DEREF
)
2516 if (!(get_varinfo (lhs
.var
)->is_special_var
))
2517 insert_into_complex (graph
, rhs
.var
, c
);
2519 else if (rhs
.type
!= ADDRESSOF
&& lhs
.var
> anything_id
2520 && (lhs
.offset
!= 0 || rhs
.offset
!= 0))
2522 insert_into_complex (graph
, rhs
.var
, c
);
2529 /* Optimize and rewrite complex constraints while performing
2530 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2531 result of perform_variable_substitution. */
2534 rewrite_constraints (constraint_graph_t graph
,
2535 struct scc_info
*si
)
2542 for (unsigned int j
= 0; j
< graph
->size
; j
++)
2543 gcc_assert (find (j
) == j
);
2546 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2548 struct constraint_expr lhs
= c
->lhs
;
2549 struct constraint_expr rhs
= c
->rhs
;
2550 unsigned int lhsvar
= find (lhs
.var
);
2551 unsigned int rhsvar
= find (rhs
.var
);
2552 unsigned int lhsnode
, rhsnode
;
2553 unsigned int lhslabel
, rhslabel
;
2555 lhsnode
= si
->node_mapping
[lhsvar
];
2556 rhsnode
= si
->node_mapping
[rhsvar
];
2557 lhslabel
= graph
->pointer_label
[lhsnode
];
2558 rhslabel
= graph
->pointer_label
[rhsnode
];
2560 /* See if it is really a non-pointer variable, and if so, ignore
2564 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2567 fprintf (dump_file
, "%s is a non-pointer variable, "
2568 "ignoring constraint:",
2569 get_varinfo (lhs
.var
)->name
);
2570 dump_constraint (dump_file
, c
);
2571 fprintf (dump_file
, "\n");
2573 constraints
[i
] = NULL
;
2579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2582 fprintf (dump_file
, "%s is a non-pointer variable, "
2583 "ignoring constraint:",
2584 get_varinfo (rhs
.var
)->name
);
2585 dump_constraint (dump_file
, c
);
2586 fprintf (dump_file
, "\n");
2588 constraints
[i
] = NULL
;
2592 lhsvar
= find_equivalent_node (graph
, lhsvar
, lhslabel
);
2593 rhsvar
= find_equivalent_node (graph
, rhsvar
, rhslabel
);
2594 c
->lhs
.var
= lhsvar
;
2595 c
->rhs
.var
= rhsvar
;
2599 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2600 part of an SCC, false otherwise. */
2603 eliminate_indirect_cycles (unsigned int node
)
2605 if (graph
->indirect_cycles
[node
] != -1
2606 && !bitmap_empty_p (get_varinfo (node
)->solution
))
2609 auto_vec
<unsigned> queue
;
2611 unsigned int to
= find (graph
->indirect_cycles
[node
]);
2614 /* We can't touch the solution set and call unify_nodes
2615 at the same time, because unify_nodes is going to do
2616 bitmap unions into it. */
2618 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node
)->solution
, 0, i
, bi
)
2620 if (find (i
) == i
&& i
!= to
)
2623 queue
.safe_push (i
);
2628 queue
.iterate (queuepos
, &i
);
2631 unify_nodes (graph
, to
, i
, true);
2638 /* Solve the constraint graph GRAPH using our worklist solver.
2639 This is based on the PW* family of solvers from the "Efficient Field
2640 Sensitive Pointer Analysis for C" paper.
2641 It works by iterating over all the graph nodes, processing the complex
2642 constraints and propagating the copy constraints, until everything stops
2643 changed. This corresponds to steps 6-8 in the solving list given above. */
2646 solve_graph (constraint_graph_t graph
)
2648 unsigned int size
= graph
->size
;
2652 changed
= BITMAP_ALLOC (NULL
);
2654 /* Mark all initial non-collapsed nodes as changed. */
2655 for (i
= 1; i
< size
; i
++)
2657 varinfo_t ivi
= get_varinfo (i
);
2658 if (find (i
) == i
&& !bitmap_empty_p (ivi
->solution
)
2659 && ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
2660 || graph
->complex[i
].length () > 0))
2661 bitmap_set_bit (changed
, i
);
2664 /* Allocate a bitmap to be used to store the changed bits. */
2665 pts
= BITMAP_ALLOC (&pta_obstack
);
2667 while (!bitmap_empty_p (changed
))
2670 struct topo_info
*ti
= init_topo_info ();
2673 bitmap_obstack_initialize (&iteration_obstack
);
2675 compute_topo_order (graph
, ti
);
2677 while (ti
->topo_order
.length () != 0)
2680 i
= ti
->topo_order
.pop ();
2682 /* If this variable is not a representative, skip it. */
2686 /* In certain indirect cycle cases, we may merge this
2687 variable to another. */
2688 if (eliminate_indirect_cycles (i
) && find (i
) != i
)
2691 /* If the node has changed, we need to process the
2692 complex constraints and outgoing edges again. */
2693 if (bitmap_clear_bit (changed
, i
))
2698 vec
<constraint_t
> complex = graph
->complex[i
];
2699 varinfo_t vi
= get_varinfo (i
);
2700 bool solution_empty
;
2702 /* Compute the changed set of solution bits. If anything
2703 is in the solution just propagate that. */
2704 if (bitmap_bit_p (vi
->solution
, anything_id
))
2706 /* If anything is also in the old solution there is
2708 ??? But we shouldn't ended up with "changed" set ... */
2710 && bitmap_bit_p (vi
->oldsolution
, anything_id
))
2712 bitmap_copy (pts
, get_varinfo (find (anything_id
))->solution
);
2714 else if (vi
->oldsolution
)
2715 bitmap_and_compl (pts
, vi
->solution
, vi
->oldsolution
);
2717 bitmap_copy (pts
, vi
->solution
);
2719 if (bitmap_empty_p (pts
))
2722 if (vi
->oldsolution
)
2723 bitmap_ior_into (vi
->oldsolution
, pts
);
2726 vi
->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
2727 bitmap_copy (vi
->oldsolution
, pts
);
2730 solution
= vi
->solution
;
2731 solution_empty
= bitmap_empty_p (solution
);
2733 /* Process the complex constraints */
2734 bitmap expanded_pts
= NULL
;
2735 FOR_EACH_VEC_ELT (complex, j
, c
)
2737 /* XXX: This is going to unsort the constraints in
2738 some cases, which will occasionally add duplicate
2739 constraints during unification. This does not
2740 affect correctness. */
2741 c
->lhs
.var
= find (c
->lhs
.var
);
2742 c
->rhs
.var
= find (c
->rhs
.var
);
2744 /* The only complex constraint that can change our
2745 solution to non-empty, given an empty solution,
2746 is a constraint where the lhs side is receiving
2747 some set from elsewhere. */
2748 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2749 do_complex_constraint (graph
, c
, pts
, &expanded_pts
);
2751 BITMAP_FREE (expanded_pts
);
2753 solution_empty
= bitmap_empty_p (solution
);
2755 if (!solution_empty
)
2758 unsigned eff_escaped_id
= find (escaped_id
);
2760 /* Propagate solution to all successors. */
2761 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
2767 unsigned int to
= find (j
);
2768 tmp
= get_varinfo (to
)->solution
;
2771 /* Don't try to propagate to ourselves. */
2775 /* If we propagate from ESCAPED use ESCAPED as
2777 if (i
== eff_escaped_id
)
2778 flag
= bitmap_set_bit (tmp
, escaped_id
);
2780 flag
= bitmap_ior_into (tmp
, pts
);
2783 bitmap_set_bit (changed
, to
);
2788 free_topo_info (ti
);
2789 bitmap_obstack_release (&iteration_obstack
);
2793 BITMAP_FREE (changed
);
2794 bitmap_obstack_release (&oldpta_obstack
);
2797 /* Map from trees to variable infos. */
2798 static hash_map
<tree
, varinfo_t
> *vi_for_tree
;
2801 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2804 insert_vi_for_tree (tree t
, varinfo_t vi
)
2807 gcc_assert (!vi_for_tree
->put (t
, vi
));
2810 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2811 exist in the map, return NULL, otherwise, return the varinfo we found. */
2814 lookup_vi_for_tree (tree t
)
2816 varinfo_t
*slot
= vi_for_tree
->get (t
);
2823 /* Return a printable name for DECL */
2826 alias_get_name (tree decl
)
2828 const char *res
= NULL
;
2830 int num_printed
= 0;
2835 if (TREE_CODE (decl
) == SSA_NAME
)
2837 res
= get_name (decl
);
2839 num_printed
= asprintf (&temp
, "%s_%u", res
, SSA_NAME_VERSION (decl
));
2841 num_printed
= asprintf (&temp
, "_%u", SSA_NAME_VERSION (decl
));
2842 if (num_printed
> 0)
2844 res
= ggc_strdup (temp
);
2848 else if (DECL_P (decl
))
2850 if (DECL_ASSEMBLER_NAME_SET_P (decl
))
2851 res
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
2854 res
= get_name (decl
);
2857 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2858 if (num_printed
> 0)
2860 res
= ggc_strdup (temp
);
2872 /* Find the variable id for tree T in the map.
2873 If T doesn't exist in the map, create an entry for it and return it. */
2876 get_vi_for_tree (tree t
)
2878 varinfo_t
*slot
= vi_for_tree
->get (t
);
2881 unsigned int id
= create_variable_info_for (t
, alias_get_name (t
), false);
2882 return get_varinfo (id
);
2888 /* Get a scalar constraint expression for a new temporary variable. */
2890 static struct constraint_expr
2891 new_scalar_tmp_constraint_exp (const char *name
, bool add_id
)
2893 struct constraint_expr tmp
;
2896 vi
= new_var_info (NULL_TREE
, name
, add_id
);
2900 vi
->is_full_var
= 1;
2909 /* Get a constraint expression vector from an SSA_VAR_P node.
2910 If address_p is true, the result will be taken its address of. */
2913 get_constraint_for_ssa_var (tree t
, vec
<ce_s
> *results
, bool address_p
)
2915 struct constraint_expr cexpr
;
2918 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2919 gcc_assert (TREE_CODE (t
) == SSA_NAME
|| DECL_P (t
));
2921 /* For parameters, get at the points-to set for the actual parm
2923 if (TREE_CODE (t
) == SSA_NAME
2924 && SSA_NAME_IS_DEFAULT_DEF (t
)
2925 && (TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2926 || TREE_CODE (SSA_NAME_VAR (t
)) == RESULT_DECL
))
2928 get_constraint_for_ssa_var (SSA_NAME_VAR (t
), results
, address_p
);
2932 /* For global variables resort to the alias target. */
2933 if (VAR_P (t
) && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
2935 varpool_node
*node
= varpool_node::get (t
);
2936 if (node
&& node
->alias
&& node
->analyzed
)
2938 node
= node
->ultimate_alias_target ();
2939 /* Canonicalize the PT uid of all aliases to the ultimate target.
2940 ??? Hopefully the set of aliases can't change in a way that
2941 changes the ultimate alias target. */
2942 gcc_assert ((! DECL_PT_UID_SET_P (node
->decl
)
2943 || DECL_PT_UID (node
->decl
) == DECL_UID (node
->decl
))
2944 && (! DECL_PT_UID_SET_P (t
)
2945 || DECL_PT_UID (t
) == DECL_UID (node
->decl
)));
2946 DECL_PT_UID (t
) = DECL_UID (node
->decl
);
2950 /* If this is decl may bind to NULL note that. */
2952 && (! node
|| ! node
->nonzero_address ()))
2954 cexpr
.var
= nothing_id
;
2955 cexpr
.type
= SCALAR
;
2957 results
->safe_push (cexpr
);
2961 vi
= get_vi_for_tree (t
);
2963 cexpr
.type
= SCALAR
;
2966 /* If we are not taking the address of the constraint expr, add all
2967 sub-fiels of the variable as well. */
2969 && !vi
->is_full_var
)
2971 for (; vi
; vi
= vi_next (vi
))
2974 results
->safe_push (cexpr
);
2979 results
->safe_push (cexpr
);
2982 /* Process constraint T, performing various simplifications and then
2983 adding it to our list of overall constraints. */
2986 process_constraint (constraint_t t
)
2988 struct constraint_expr rhs
= t
->rhs
;
2989 struct constraint_expr lhs
= t
->lhs
;
2991 gcc_assert (rhs
.var
< varmap
.length ());
2992 gcc_assert (lhs
.var
< varmap
.length ());
2994 /* If we didn't get any useful constraint from the lhs we get
2995 &ANYTHING as fallback from get_constraint_for. Deal with
2996 it here by turning it into *ANYTHING. */
2997 if (lhs
.type
== ADDRESSOF
2998 && lhs
.var
== anything_id
)
3001 /* ADDRESSOF on the lhs is invalid. */
3002 gcc_assert (lhs
.type
!= ADDRESSOF
);
3004 /* We shouldn't add constraints from things that cannot have pointers.
3005 It's not completely trivial to avoid in the callers, so do it here. */
3006 if (rhs
.type
!= ADDRESSOF
3007 && !get_varinfo (rhs
.var
)->may_have_pointers
)
3010 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3011 if (!get_varinfo (lhs
.var
)->may_have_pointers
)
3014 /* This can happen in our IR with things like n->a = *p */
3015 if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
3017 /* Split into tmp = *rhs, *lhs = tmp */
3018 struct constraint_expr tmplhs
;
3019 tmplhs
= new_scalar_tmp_constraint_exp ("doubledereftmp", true);
3020 process_constraint (new_constraint (tmplhs
, rhs
));
3021 process_constraint (new_constraint (lhs
, tmplhs
));
3023 else if ((rhs
.type
!= SCALAR
|| rhs
.offset
!= 0) && lhs
.type
== DEREF
)
3025 /* Split into tmp = &rhs, *lhs = tmp */
3026 struct constraint_expr tmplhs
;
3027 tmplhs
= new_scalar_tmp_constraint_exp ("derefaddrtmp", true);
3028 process_constraint (new_constraint (tmplhs
, rhs
));
3029 process_constraint (new_constraint (lhs
, tmplhs
));
3033 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
3034 constraints
.safe_push (t
);
3039 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3042 static HOST_WIDE_INT
3043 bitpos_of_field (const tree fdecl
)
3045 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl
))
3046 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl
)))
3049 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl
)) * BITS_PER_UNIT
3050 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl
)));
3054 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3055 resulting constraint expressions in *RESULTS. */
3058 get_constraint_for_ptr_offset (tree ptr
, tree offset
,
3061 struct constraint_expr c
;
3063 HOST_WIDE_INT rhsoffset
;
3065 /* If we do not do field-sensitive PTA adding offsets to pointers
3066 does not change the points-to solution. */
3067 if (!use_field_sensitive
)
3069 get_constraint_for_rhs (ptr
, results
);
3073 /* If the offset is not a non-negative integer constant that fits
3074 in a HOST_WIDE_INT, we have to fall back to a conservative
3075 solution which includes all sub-fields of all pointed-to
3076 variables of ptr. */
3077 if (offset
== NULL_TREE
3078 || TREE_CODE (offset
) != INTEGER_CST
)
3079 rhsoffset
= UNKNOWN_OFFSET
;
3082 /* Sign-extend the offset. */
3083 offset_int soffset
= offset_int::from (offset
, SIGNED
);
3084 if (!wi::fits_shwi_p (soffset
))
3085 rhsoffset
= UNKNOWN_OFFSET
;
3088 /* Make sure the bit-offset also fits. */
3089 HOST_WIDE_INT rhsunitoffset
= soffset
.to_shwi ();
3090 rhsoffset
= rhsunitoffset
* BITS_PER_UNIT
;
3091 if (rhsunitoffset
!= rhsoffset
/ BITS_PER_UNIT
)
3092 rhsoffset
= UNKNOWN_OFFSET
;
3096 get_constraint_for_rhs (ptr
, results
);
3100 /* As we are eventually appending to the solution do not use
3101 vec::iterate here. */
3102 n
= results
->length ();
3103 for (j
= 0; j
< n
; j
++)
3107 curr
= get_varinfo (c
.var
);
3109 if (c
.type
== ADDRESSOF
3110 /* If this varinfo represents a full variable just use it. */
3111 && curr
->is_full_var
)
3113 else if (c
.type
== ADDRESSOF
3114 /* If we do not know the offset add all subfields. */
3115 && rhsoffset
== UNKNOWN_OFFSET
)
3117 varinfo_t temp
= get_varinfo (curr
->head
);
3120 struct constraint_expr c2
;
3122 c2
.type
= ADDRESSOF
;
3124 if (c2
.var
!= c
.var
)
3125 results
->safe_push (c2
);
3126 temp
= vi_next (temp
);
3130 else if (c
.type
== ADDRESSOF
)
3133 unsigned HOST_WIDE_INT offset
= curr
->offset
+ rhsoffset
;
3135 /* If curr->offset + rhsoffset is less than zero adjust it. */
3137 && curr
->offset
< offset
)
3140 /* We have to include all fields that overlap the current
3141 field shifted by rhsoffset. And we include at least
3142 the last or the first field of the variable to represent
3143 reachability of off-bound addresses, in particular &object + 1,
3144 conservatively correct. */
3145 temp
= first_or_preceding_vi_for_offset (curr
, offset
);
3148 temp
= vi_next (temp
);
3150 && temp
->offset
< offset
+ curr
->size
)
3152 struct constraint_expr c2
;
3154 c2
.type
= ADDRESSOF
;
3156 results
->safe_push (c2
);
3157 temp
= vi_next (temp
);
3160 else if (c
.type
== SCALAR
)
3162 gcc_assert (c
.offset
== 0);
3163 c
.offset
= rhsoffset
;
3166 /* We shouldn't get any DEREFs here. */
3174 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3175 If address_p is true the result will be taken its address of.
3176 If lhs_p is true then the constraint expression is assumed to be used
3180 get_constraint_for_component_ref (tree t
, vec
<ce_s
> *results
,
3181 bool address_p
, bool lhs_p
)
3184 HOST_WIDE_INT bitsize
= -1;
3185 HOST_WIDE_INT bitmaxsize
= -1;
3186 HOST_WIDE_INT bitpos
;
3190 /* Some people like to do cute things like take the address of
3193 while (handled_component_p (forzero
)
3194 || INDIRECT_REF_P (forzero
)
3195 || TREE_CODE (forzero
) == MEM_REF
)
3196 forzero
= TREE_OPERAND (forzero
, 0);
3198 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
3200 struct constraint_expr temp
;
3203 temp
.var
= integer_id
;
3205 results
->safe_push (temp
);
3209 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
, &reverse
);
3211 /* We can end up here for component references on a
3212 VIEW_CONVERT_EXPR <>(&foobar) or things like a
3213 BIT_FIELD_REF <&MEM[(void *)&b + 4B], ...>. So for
3214 symbolic constants simply give up. */
3215 if (TREE_CODE (t
) == ADDR_EXPR
)
3217 constraint_expr result
;
3218 result
.type
= SCALAR
;
3219 result
.var
= anything_id
;
3221 results
->safe_push (result
);
3225 /* Pretend to take the address of the base, we'll take care of
3226 adding the required subset of sub-fields below. */
3227 get_constraint_for_1 (t
, results
, true, lhs_p
);
3228 /* Strip off nothing_id. */
3229 if (results
->length () == 2)
3231 gcc_assert ((*results
)[0].var
== nothing_id
);
3232 results
->unordered_remove (0);
3234 gcc_assert (results
->length () == 1);
3235 struct constraint_expr
&result
= results
->last ();
3237 if (result
.type
== SCALAR
3238 && get_varinfo (result
.var
)->is_full_var
)
3239 /* For single-field vars do not bother about the offset. */
3241 else if (result
.type
== SCALAR
)
3243 /* In languages like C, you can access one past the end of an
3244 array. You aren't allowed to dereference it, so we can
3245 ignore this constraint. When we handle pointer subtraction,
3246 we may have to do something cute here. */
3248 if ((unsigned HOST_WIDE_INT
)bitpos
< get_varinfo (result
.var
)->fullsize
3251 /* It's also not true that the constraint will actually start at the
3252 right offset, it may start in some padding. We only care about
3253 setting the constraint to the first actual field it touches, so
3255 struct constraint_expr cexpr
= result
;
3259 for (curr
= get_varinfo (cexpr
.var
); curr
; curr
= vi_next (curr
))
3261 if (ranges_overlap_p (curr
->offset
, curr
->size
,
3262 bitpos
, bitmaxsize
))
3264 cexpr
.var
= curr
->id
;
3265 results
->safe_push (cexpr
);
3270 /* If we are going to take the address of this field then
3271 to be able to compute reachability correctly add at least
3272 the last field of the variable. */
3273 if (address_p
&& results
->length () == 0)
3275 curr
= get_varinfo (cexpr
.var
);
3276 while (curr
->next
!= 0)
3277 curr
= vi_next (curr
);
3278 cexpr
.var
= curr
->id
;
3279 results
->safe_push (cexpr
);
3281 else if (results
->length () == 0)
3282 /* Assert that we found *some* field there. The user couldn't be
3283 accessing *only* padding. */
3284 /* Still the user could access one past the end of an array
3285 embedded in a struct resulting in accessing *only* padding. */
3286 /* Or accessing only padding via type-punning to a type
3287 that has a filed just in padding space. */
3289 cexpr
.type
= SCALAR
;
3290 cexpr
.var
= anything_id
;
3292 results
->safe_push (cexpr
);
3295 else if (bitmaxsize
== 0)
3297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3298 fprintf (dump_file
, "Access to zero-sized part of variable, "
3302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3303 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
3305 else if (result
.type
== DEREF
)
3307 /* If we do not know exactly where the access goes say so. Note
3308 that only for non-structure accesses we know that we access
3309 at most one subfiled of any variable. */
3311 || bitsize
!= bitmaxsize
3312 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t
))
3313 || result
.offset
== UNKNOWN_OFFSET
)
3314 result
.offset
= UNKNOWN_OFFSET
;
3316 result
.offset
+= bitpos
;
3318 else if (result
.type
== ADDRESSOF
)
3320 /* We can end up here for component references on constants like
3321 VIEW_CONVERT_EXPR <>({ 0, 1, 2, 3 })[i]. */
3322 result
.type
= SCALAR
;
3323 result
.var
= anything_id
;
3331 /* Dereference the constraint expression CONS, and return the result.
3332 DEREF (ADDRESSOF) = SCALAR
3333 DEREF (SCALAR) = DEREF
3334 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3335 This is needed so that we can handle dereferencing DEREF constraints. */
3338 do_deref (vec
<ce_s
> *constraints
)
3340 struct constraint_expr
*c
;
3343 FOR_EACH_VEC_ELT (*constraints
, i
, c
)
3345 if (c
->type
== SCALAR
)
3347 else if (c
->type
== ADDRESSOF
)
3349 else if (c
->type
== DEREF
)
3351 struct constraint_expr tmplhs
;
3352 tmplhs
= new_scalar_tmp_constraint_exp ("dereftmp", true);
3353 process_constraint (new_constraint (tmplhs
, *c
));
3354 c
->var
= tmplhs
.var
;
3361 /* Given a tree T, return the constraint expression for taking the
3365 get_constraint_for_address_of (tree t
, vec
<ce_s
> *results
)
3367 struct constraint_expr
*c
;
3370 get_constraint_for_1 (t
, results
, true, true);
3372 FOR_EACH_VEC_ELT (*results
, i
, c
)
3374 if (c
->type
== DEREF
)
3377 c
->type
= ADDRESSOF
;
3381 /* Given a tree T, return the constraint expression for it. */
3384 get_constraint_for_1 (tree t
, vec
<ce_s
> *results
, bool address_p
,
3387 struct constraint_expr temp
;
3389 /* x = integer is all glommed to a single variable, which doesn't
3390 point to anything by itself. That is, of course, unless it is an
3391 integer constant being treated as a pointer, in which case, we
3392 will return that this is really the addressof anything. This
3393 happens below, since it will fall into the default case. The only
3394 case we know something about an integer treated like a pointer is
3395 when it is the NULL pointer, and then we just say it points to
3398 Do not do that if -fno-delete-null-pointer-checks though, because
3399 in that case *NULL does not fail, so it _should_ alias *anything.
3400 It is not worth adding a new option or renaming the existing one,
3401 since this case is relatively obscure. */
3402 if ((TREE_CODE (t
) == INTEGER_CST
3403 && integer_zerop (t
))
3404 /* The only valid CONSTRUCTORs in gimple with pointer typed
3405 elements are zero-initializer. But in IPA mode we also
3406 process global initializers, so verify at least. */
3407 || (TREE_CODE (t
) == CONSTRUCTOR
3408 && CONSTRUCTOR_NELTS (t
) == 0))
3410 if (flag_delete_null_pointer_checks
)
3411 temp
.var
= nothing_id
;
3413 temp
.var
= nonlocal_id
;
3414 temp
.type
= ADDRESSOF
;
3416 results
->safe_push (temp
);
3420 /* String constants are read-only, ideally we'd have a CONST_DECL
3422 if (TREE_CODE (t
) == STRING_CST
)
3424 temp
.var
= string_id
;
3427 results
->safe_push (temp
);
3431 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
3433 case tcc_expression
:
3435 switch (TREE_CODE (t
))
3438 get_constraint_for_address_of (TREE_OPERAND (t
, 0), results
);
3446 switch (TREE_CODE (t
))
3450 struct constraint_expr cs
;
3452 get_constraint_for_ptr_offset (TREE_OPERAND (t
, 0),
3453 TREE_OPERAND (t
, 1), results
);
3456 /* If we are not taking the address then make sure to process
3457 all subvariables we might access. */
3461 cs
= results
->last ();
3462 if (cs
.type
== DEREF
3463 && type_can_have_subvars (TREE_TYPE (t
)))
3465 /* For dereferences this means we have to defer it
3467 results
->last ().offset
= UNKNOWN_OFFSET
;
3470 if (cs
.type
!= SCALAR
)
3473 vi
= get_varinfo (cs
.var
);
3474 curr
= vi_next (vi
);
3475 if (!vi
->is_full_var
3478 unsigned HOST_WIDE_INT size
;
3479 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t
))))
3480 size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t
)));
3483 for (; curr
; curr
= vi_next (curr
))
3485 if (curr
->offset
- vi
->offset
< size
)
3488 results
->safe_push (cs
);
3497 case ARRAY_RANGE_REF
:
3502 get_constraint_for_component_ref (t
, results
, address_p
, lhs_p
);
3504 case VIEW_CONVERT_EXPR
:
3505 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, address_p
,
3508 /* We are missing handling for TARGET_MEM_REF here. */
3513 case tcc_exceptional
:
3515 switch (TREE_CODE (t
))
3519 get_constraint_for_ssa_var (t
, results
, address_p
);
3527 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t
), i
, val
)
3529 struct constraint_expr
*rhsp
;
3531 get_constraint_for_1 (val
, &tmp
, address_p
, lhs_p
);
3532 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
3533 results
->safe_push (*rhsp
);
3536 /* We do not know whether the constructor was complete,
3537 so technically we have to add &NOTHING or &ANYTHING
3538 like we do for an empty constructor as well. */
3545 case tcc_declaration
:
3547 get_constraint_for_ssa_var (t
, results
, address_p
);
3552 /* We cannot refer to automatic variables through constants. */
3553 temp
.type
= ADDRESSOF
;
3554 temp
.var
= nonlocal_id
;
3556 results
->safe_push (temp
);
3562 /* The default fallback is a constraint from anything. */
3563 temp
.type
= ADDRESSOF
;
3564 temp
.var
= anything_id
;
3566 results
->safe_push (temp
);
3569 /* Given a gimple tree T, return the constraint expression vector for it. */
3572 get_constraint_for (tree t
, vec
<ce_s
> *results
)
3574 gcc_assert (results
->length () == 0);
3576 get_constraint_for_1 (t
, results
, false, true);
3579 /* Given a gimple tree T, return the constraint expression vector for it
3580 to be used as the rhs of a constraint. */
3583 get_constraint_for_rhs (tree t
, vec
<ce_s
> *results
)
3585 gcc_assert (results
->length () == 0);
3587 get_constraint_for_1 (t
, results
, false, false);
3591 /* Efficiently generates constraints from all entries in *RHSC to all
3592 entries in *LHSC. */
3595 process_all_all_constraints (vec
<ce_s
> lhsc
,
3598 struct constraint_expr
*lhsp
, *rhsp
;
3601 if (lhsc
.length () <= 1 || rhsc
.length () <= 1)
3603 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3604 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
3605 process_constraint (new_constraint (*lhsp
, *rhsp
));
3609 struct constraint_expr tmp
;
3610 tmp
= new_scalar_tmp_constraint_exp ("allalltmp", true);
3611 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
3612 process_constraint (new_constraint (tmp
, *rhsp
));
3613 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3614 process_constraint (new_constraint (*lhsp
, tmp
));
3618 /* Handle aggregate copies by expanding into copies of the respective
3619 fields of the structures. */
3622 do_structure_copy (tree lhsop
, tree rhsop
)
3624 struct constraint_expr
*lhsp
, *rhsp
;
3625 auto_vec
<ce_s
> lhsc
;
3626 auto_vec
<ce_s
> rhsc
;
3629 get_constraint_for (lhsop
, &lhsc
);
3630 get_constraint_for_rhs (rhsop
, &rhsc
);
3633 if (lhsp
->type
== DEREF
3634 || (lhsp
->type
== ADDRESSOF
&& lhsp
->var
== anything_id
)
3635 || rhsp
->type
== DEREF
)
3637 if (lhsp
->type
== DEREF
)
3639 gcc_assert (lhsc
.length () == 1);
3640 lhsp
->offset
= UNKNOWN_OFFSET
;
3642 if (rhsp
->type
== DEREF
)
3644 gcc_assert (rhsc
.length () == 1);
3645 rhsp
->offset
= UNKNOWN_OFFSET
;
3647 process_all_all_constraints (lhsc
, rhsc
);
3649 else if (lhsp
->type
== SCALAR
3650 && (rhsp
->type
== SCALAR
3651 || rhsp
->type
== ADDRESSOF
))
3653 HOST_WIDE_INT lhssize
, lhsmaxsize
, lhsoffset
;
3654 HOST_WIDE_INT rhssize
, rhsmaxsize
, rhsoffset
;
3657 get_ref_base_and_extent (lhsop
, &lhsoffset
, &lhssize
, &lhsmaxsize
,
3659 get_ref_base_and_extent (rhsop
, &rhsoffset
, &rhssize
, &rhsmaxsize
,
3661 for (j
= 0; lhsc
.iterate (j
, &lhsp
);)
3663 varinfo_t lhsv
, rhsv
;
3665 lhsv
= get_varinfo (lhsp
->var
);
3666 rhsv
= get_varinfo (rhsp
->var
);
3667 if (lhsv
->may_have_pointers
3668 && (lhsv
->is_full_var
3669 || rhsv
->is_full_var
3670 || ranges_overlap_p (lhsv
->offset
+ rhsoffset
, lhsv
->size
,
3671 rhsv
->offset
+ lhsoffset
, rhsv
->size
)))
3672 process_constraint (new_constraint (*lhsp
, *rhsp
));
3673 if (!rhsv
->is_full_var
3674 && (lhsv
->is_full_var
3675 || (lhsv
->offset
+ rhsoffset
+ lhsv
->size
3676 > rhsv
->offset
+ lhsoffset
+ rhsv
->size
)))
3679 if (k
>= rhsc
.length ())
3690 /* Create constraints ID = { rhsc }. */
3693 make_constraints_to (unsigned id
, vec
<ce_s
> rhsc
)
3695 struct constraint_expr
*c
;
3696 struct constraint_expr includes
;
3700 includes
.offset
= 0;
3701 includes
.type
= SCALAR
;
3703 FOR_EACH_VEC_ELT (rhsc
, j
, c
)
3704 process_constraint (new_constraint (includes
, *c
));
3707 /* Create a constraint ID = OP. */
3710 make_constraint_to (unsigned id
, tree op
)
3712 auto_vec
<ce_s
> rhsc
;
3713 get_constraint_for_rhs (op
, &rhsc
);
3714 make_constraints_to (id
, rhsc
);
3717 /* Create a constraint ID = &FROM. */
3720 make_constraint_from (varinfo_t vi
, int from
)
3722 struct constraint_expr lhs
, rhs
;
3730 rhs
.type
= ADDRESSOF
;
3731 process_constraint (new_constraint (lhs
, rhs
));
3734 /* Create a constraint ID = FROM. */
3737 make_copy_constraint (varinfo_t vi
, int from
)
3739 struct constraint_expr lhs
, rhs
;
3748 process_constraint (new_constraint (lhs
, rhs
));
3751 /* Make constraints necessary to make OP escape. */
3754 make_escape_constraint (tree op
)
3756 make_constraint_to (escaped_id
, op
);
3759 /* Add constraints to that the solution of VI is transitively closed. */
3762 make_transitive_closure_constraints (varinfo_t vi
)
3764 struct constraint_expr lhs
, rhs
;
3766 /* VAR = *(VAR + UNKNOWN); */
3772 rhs
.offset
= UNKNOWN_OFFSET
;
3773 process_constraint (new_constraint (lhs
, rhs
));
3776 /* Add constraints to that the solution of VI has all subvariables added. */
3779 make_any_offset_constraints (varinfo_t vi
)
3781 struct constraint_expr lhs
, rhs
;
3783 /* VAR = VAR + UNKNOWN; */
3789 rhs
.offset
= UNKNOWN_OFFSET
;
3790 process_constraint (new_constraint (lhs
, rhs
));
3793 /* Temporary storage for fake var decls. */
3794 struct obstack fake_var_decl_obstack
;
3796 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3799 build_fake_var_decl (tree type
)
3801 tree decl
= (tree
) XOBNEW (&fake_var_decl_obstack
, struct tree_var_decl
);
3802 memset (decl
, 0, sizeof (struct tree_var_decl
));
3803 TREE_SET_CODE (decl
, VAR_DECL
);
3804 TREE_TYPE (decl
) = type
;
3805 DECL_UID (decl
) = allocate_decl_uid ();
3806 SET_DECL_PT_UID (decl
, -1);
3807 layout_decl (decl
, 0);
3811 /* Create a new artificial heap variable with NAME.
3812 Return the created variable. */
3815 make_heapvar (const char *name
, bool add_id
)
3820 heapvar
= build_fake_var_decl (ptr_type_node
);
3821 DECL_EXTERNAL (heapvar
) = 1;
3823 vi
= new_var_info (heapvar
, name
, add_id
);
3824 vi
->is_artificial_var
= true;
3825 vi
->is_heap_var
= true;
3826 vi
->is_unknown_size_var
= true;
3830 vi
->is_full_var
= true;
3831 insert_vi_for_tree (heapvar
, vi
);
3836 /* Create a new artificial heap variable with NAME and make a
3837 constraint from it to LHS. Set flags according to a tag used
3838 for tracking restrict pointers. */
3841 make_constraint_from_restrict (varinfo_t lhs
, const char *name
, bool add_id
)
3843 varinfo_t vi
= make_heapvar (name
, add_id
);
3844 vi
->is_restrict_var
= 1;
3845 vi
->is_global_var
= 1;
3846 vi
->may_have_pointers
= 1;
3847 make_constraint_from (lhs
, vi
->id
);
3851 /* Create a new artificial heap variable with NAME and make a
3852 constraint from it to LHS. Set flags according to a tag used
3853 for tracking restrict pointers and make the artificial heap
3854 point to global memory. */
3857 make_constraint_from_global_restrict (varinfo_t lhs
, const char *name
,
3860 varinfo_t vi
= make_constraint_from_restrict (lhs
, name
, add_id
);
3861 make_copy_constraint (vi
, nonlocal_id
);
3865 /* In IPA mode there are varinfos for different aspects of reach
3866 function designator. One for the points-to set of the return
3867 value, one for the variables that are clobbered by the function,
3868 one for its uses and one for each parameter (including a single
3869 glob for remaining variadic arguments). */
3871 enum { fi_clobbers
= 1, fi_uses
= 2,
3872 fi_static_chain
= 3, fi_result
= 4, fi_parm_base
= 5 };
3874 /* Get a constraint for the requested part of a function designator FI
3875 when operating in IPA mode. */
3877 static struct constraint_expr
3878 get_function_part_constraint (varinfo_t fi
, unsigned part
)
3880 struct constraint_expr c
;
3882 gcc_assert (in_ipa_mode
);
3884 if (fi
->id
== anything_id
)
3886 /* ??? We probably should have a ANYFN special variable. */
3887 c
.var
= anything_id
;
3891 else if (TREE_CODE (fi
->decl
) == FUNCTION_DECL
)
3893 varinfo_t ai
= first_vi_for_offset (fi
, part
);
3897 c
.var
= anything_id
;
3911 /* For non-IPA mode, generate constraints necessary for a call on the
3915 handle_rhs_call (gcall
*stmt
, vec
<ce_s
> *results
)
3917 struct constraint_expr rhsc
;
3919 bool returns_uses
= false;
3921 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3923 tree arg
= gimple_call_arg (stmt
, i
);
3924 int flags
= gimple_call_arg_flags (stmt
, i
);
3926 /* If the argument is not used we can ignore it. */
3927 if (flags
& EAF_UNUSED
)
3930 /* As we compute ESCAPED context-insensitive we do not gain
3931 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3932 set. The argument would still get clobbered through the
3934 if ((flags
& EAF_NOCLOBBER
)
3935 && (flags
& EAF_NOESCAPE
))
3937 varinfo_t uses
= get_call_use_vi (stmt
);
3938 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg", true);
3939 make_constraint_to (tem
->id
, arg
);
3940 make_any_offset_constraints (tem
);
3941 if (!(flags
& EAF_DIRECT
))
3942 make_transitive_closure_constraints (tem
);
3943 make_copy_constraint (uses
, tem
->id
);
3944 returns_uses
= true;
3946 else if (flags
& EAF_NOESCAPE
)
3948 struct constraint_expr lhs
, rhs
;
3949 varinfo_t uses
= get_call_use_vi (stmt
);
3950 varinfo_t clobbers
= get_call_clobber_vi (stmt
);
3951 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg", true);
3952 make_constraint_to (tem
->id
, arg
);
3953 make_any_offset_constraints (tem
);
3954 if (!(flags
& EAF_DIRECT
))
3955 make_transitive_closure_constraints (tem
);
3956 make_copy_constraint (uses
, tem
->id
);
3957 make_copy_constraint (clobbers
, tem
->id
);
3958 /* Add *tem = nonlocal, do not add *tem = callused as
3959 EAF_NOESCAPE parameters do not escape to other parameters
3960 and all other uses appear in NONLOCAL as well. */
3965 rhs
.var
= nonlocal_id
;
3967 process_constraint (new_constraint (lhs
, rhs
));
3968 returns_uses
= true;
3971 make_escape_constraint (arg
);
3974 /* If we added to the calls uses solution make sure we account for
3975 pointers to it to be returned. */
3978 rhsc
.var
= get_call_use_vi (stmt
)->id
;
3979 rhsc
.offset
= UNKNOWN_OFFSET
;
3981 results
->safe_push (rhsc
);
3984 /* The static chain escapes as well. */
3985 if (gimple_call_chain (stmt
))
3986 make_escape_constraint (gimple_call_chain (stmt
));
3988 /* And if we applied NRV the address of the return slot escapes as well. */
3989 if (gimple_call_return_slot_opt_p (stmt
)
3990 && gimple_call_lhs (stmt
) != NULL_TREE
3991 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
3993 auto_vec
<ce_s
> tmpc
;
3994 struct constraint_expr lhsc
, *c
;
3995 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
3996 lhsc
.var
= escaped_id
;
3999 FOR_EACH_VEC_ELT (tmpc
, i
, c
)
4000 process_constraint (new_constraint (lhsc
, *c
));
4003 /* Regular functions return nonlocal memory. */
4004 rhsc
.var
= nonlocal_id
;
4007 results
->safe_push (rhsc
);
4010 /* For non-IPA mode, generate constraints necessary for a call
4011 that returns a pointer and assigns it to LHS. This simply makes
4012 the LHS point to global and escaped variables. */
4015 handle_lhs_call (gcall
*stmt
, tree lhs
, int flags
, vec
<ce_s
> rhsc
,
4018 auto_vec
<ce_s
> lhsc
;
4020 get_constraint_for (lhs
, &lhsc
);
4021 /* If the store is to a global decl make sure to
4022 add proper escape constraints. */
4023 lhs
= get_base_address (lhs
);
4026 && is_global_var (lhs
))
4028 struct constraint_expr tmpc
;
4029 tmpc
.var
= escaped_id
;
4032 lhsc
.safe_push (tmpc
);
4035 /* If the call returns an argument unmodified override the rhs
4037 if (flags
& ERF_RETURNS_ARG
4038 && (flags
& ERF_RETURN_ARG_MASK
) < gimple_call_num_args (stmt
))
4042 arg
= gimple_call_arg (stmt
, flags
& ERF_RETURN_ARG_MASK
);
4043 get_constraint_for (arg
, &rhsc
);
4044 process_all_all_constraints (lhsc
, rhsc
);
4047 else if (flags
& ERF_NOALIAS
)
4050 struct constraint_expr tmpc
;
4052 vi
= make_heapvar ("HEAP", true);
4053 /* We are marking allocated storage local, we deal with it becoming
4054 global by escaping and setting of vars_contains_escaped_heap. */
4055 DECL_EXTERNAL (vi
->decl
) = 0;
4056 vi
->is_global_var
= 0;
4057 /* If this is not a real malloc call assume the memory was
4058 initialized and thus may point to global memory. All
4059 builtin functions with the malloc attribute behave in a sane way. */
4061 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
4062 make_constraint_from (vi
, nonlocal_id
);
4065 tmpc
.type
= ADDRESSOF
;
4066 rhsc
.safe_push (tmpc
);
4067 process_all_all_constraints (lhsc
, rhsc
);
4071 process_all_all_constraints (lhsc
, rhsc
);
4074 /* For non-IPA mode, generate constraints necessary for a call of a
4075 const function that returns a pointer in the statement STMT. */
4078 handle_const_call (gcall
*stmt
, vec
<ce_s
> *results
)
4080 struct constraint_expr rhsc
;
4082 bool need_uses
= false;
4084 /* Treat nested const functions the same as pure functions as far
4085 as the static chain is concerned. */
4086 if (gimple_call_chain (stmt
))
4088 varinfo_t uses
= get_call_use_vi (stmt
);
4089 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4093 /* And if we applied NRV the address of the return slot escapes as well. */
4094 if (gimple_call_return_slot_opt_p (stmt
)
4095 && gimple_call_lhs (stmt
) != NULL_TREE
4096 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
4098 varinfo_t uses
= get_call_use_vi (stmt
);
4099 auto_vec
<ce_s
> tmpc
;
4100 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
4101 make_constraints_to (uses
->id
, tmpc
);
4107 varinfo_t uses
= get_call_use_vi (stmt
);
4108 make_any_offset_constraints (uses
);
4109 make_transitive_closure_constraints (uses
);
4110 rhsc
.var
= uses
->id
;
4113 results
->safe_push (rhsc
);
4116 /* May return offsetted arguments. */
4117 varinfo_t tem
= NULL
;
4118 if (gimple_call_num_args (stmt
) != 0)
4119 tem
= new_var_info (NULL_TREE
, "callarg", true);
4120 for (k
= 0; k
< gimple_call_num_args (stmt
); ++k
)
4122 tree arg
= gimple_call_arg (stmt
, k
);
4123 auto_vec
<ce_s
> argc
;
4124 get_constraint_for_rhs (arg
, &argc
);
4125 make_constraints_to (tem
->id
, argc
);
4132 ce
.offset
= UNKNOWN_OFFSET
;
4133 results
->safe_push (ce
);
4136 /* May return addresses of globals. */
4137 rhsc
.var
= nonlocal_id
;
4139 rhsc
.type
= ADDRESSOF
;
4140 results
->safe_push (rhsc
);
4143 /* For non-IPA mode, generate constraints necessary for a call to a
4144 pure function in statement STMT. */
4147 handle_pure_call (gcall
*stmt
, vec
<ce_s
> *results
)
4149 struct constraint_expr rhsc
;
4151 varinfo_t uses
= NULL
;
4153 /* Memory reached from pointer arguments is call-used. */
4154 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
4156 tree arg
= gimple_call_arg (stmt
, i
);
4159 uses
= get_call_use_vi (stmt
);
4160 make_any_offset_constraints (uses
);
4161 make_transitive_closure_constraints (uses
);
4163 make_constraint_to (uses
->id
, arg
);
4166 /* The static chain is used as well. */
4167 if (gimple_call_chain (stmt
))
4171 uses
= get_call_use_vi (stmt
);
4172 make_any_offset_constraints (uses
);
4173 make_transitive_closure_constraints (uses
);
4175 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4178 /* And if we applied NRV the address of the return slot. */
4179 if (gimple_call_return_slot_opt_p (stmt
)
4180 && gimple_call_lhs (stmt
) != NULL_TREE
4181 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
4185 uses
= get_call_use_vi (stmt
);
4186 make_any_offset_constraints (uses
);
4187 make_transitive_closure_constraints (uses
);
4189 auto_vec
<ce_s
> tmpc
;
4190 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
4191 make_constraints_to (uses
->id
, tmpc
);
4194 /* Pure functions may return call-used and nonlocal memory. */
4197 rhsc
.var
= uses
->id
;
4200 results
->safe_push (rhsc
);
4202 rhsc
.var
= nonlocal_id
;
4205 results
->safe_push (rhsc
);
4209 /* Return the varinfo for the callee of CALL. */
4212 get_fi_for_callee (gcall
*call
)
4214 tree decl
, fn
= gimple_call_fn (call
);
4216 if (fn
&& TREE_CODE (fn
) == OBJ_TYPE_REF
)
4217 fn
= OBJ_TYPE_REF_EXPR (fn
);
4219 /* If we can directly resolve the function being called, do so.
4220 Otherwise, it must be some sort of indirect expression that
4221 we should still be able to handle. */
4222 decl
= gimple_call_addr_fndecl (fn
);
4224 return get_vi_for_tree (decl
);
4226 /* If the function is anything other than a SSA name pointer we have no
4227 clue and should be getting ANYFN (well, ANYTHING for now). */
4228 if (!fn
|| TREE_CODE (fn
) != SSA_NAME
)
4229 return get_varinfo (anything_id
);
4231 if (SSA_NAME_IS_DEFAULT_DEF (fn
)
4232 && (TREE_CODE (SSA_NAME_VAR (fn
)) == PARM_DECL
4233 || TREE_CODE (SSA_NAME_VAR (fn
)) == RESULT_DECL
))
4234 fn
= SSA_NAME_VAR (fn
);
4236 return get_vi_for_tree (fn
);
4239 /* Create constraints for assigning call argument ARG to the incoming parameter
4240 INDEX of function FI. */
4243 find_func_aliases_for_call_arg (varinfo_t fi
, unsigned index
, tree arg
)
4245 struct constraint_expr lhs
;
4246 lhs
= get_function_part_constraint (fi
, fi_parm_base
+ index
);
4248 auto_vec
<ce_s
, 2> rhsc
;
4249 get_constraint_for_rhs (arg
, &rhsc
);
4252 struct constraint_expr
*rhsp
;
4253 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4254 process_constraint (new_constraint (lhs
, *rhsp
));
4257 /* Return true if FNDECL may be part of another lto partition. */
4260 fndecl_maybe_in_other_partition (tree fndecl
)
4262 cgraph_node
*fn_node
= cgraph_node::get (fndecl
);
4263 if (fn_node
== NULL
)
4266 return fn_node
->in_other_partition
;
4269 /* Create constraints for the builtin call T. Return true if the call
4270 was handled, otherwise false. */
4273 find_func_aliases_for_builtin_call (struct function
*fn
, gcall
*t
)
4275 tree fndecl
= gimple_call_fndecl (t
);
4276 auto_vec
<ce_s
, 2> lhsc
;
4277 auto_vec
<ce_s
, 4> rhsc
;
4280 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
4281 /* ??? All builtins that are handled here need to be handled
4282 in the alias-oracle query functions explicitly! */
4283 switch (DECL_FUNCTION_CODE (fndecl
))
4285 /* All the following functions return a pointer to the same object
4286 as their first argument points to. The functions do not add
4287 to the ESCAPED solution. The functions make the first argument
4288 pointed to memory point to what the second argument pointed to
4289 memory points to. */
4290 case BUILT_IN_STRCPY
:
4291 case BUILT_IN_STRNCPY
:
4292 case BUILT_IN_BCOPY
:
4293 case BUILT_IN_MEMCPY
:
4294 case BUILT_IN_MEMMOVE
:
4295 case BUILT_IN_MEMPCPY
:
4296 case BUILT_IN_STPCPY
:
4297 case BUILT_IN_STPNCPY
:
4298 case BUILT_IN_STRCAT
:
4299 case BUILT_IN_STRNCAT
:
4300 case BUILT_IN_STRCPY_CHK
:
4301 case BUILT_IN_STRNCPY_CHK
:
4302 case BUILT_IN_MEMCPY_CHK
:
4303 case BUILT_IN_MEMMOVE_CHK
:
4304 case BUILT_IN_MEMPCPY_CHK
:
4305 case BUILT_IN_STPCPY_CHK
:
4306 case BUILT_IN_STPNCPY_CHK
:
4307 case BUILT_IN_STRCAT_CHK
:
4308 case BUILT_IN_STRNCAT_CHK
:
4309 case BUILT_IN_TM_MEMCPY
:
4310 case BUILT_IN_TM_MEMMOVE
:
4312 tree res
= gimple_call_lhs (t
);
4313 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4314 == BUILT_IN_BCOPY
? 1 : 0));
4315 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4316 == BUILT_IN_BCOPY
? 0 : 1));
4317 if (res
!= NULL_TREE
)
4319 get_constraint_for (res
, &lhsc
);
4320 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY
4321 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY
4322 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY
4323 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY_CHK
4324 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY_CHK
4325 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY_CHK
)
4326 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &rhsc
);
4328 get_constraint_for (dest
, &rhsc
);
4329 process_all_all_constraints (lhsc
, rhsc
);
4333 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4334 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4337 process_all_all_constraints (lhsc
, rhsc
);
4340 case BUILT_IN_MEMSET
:
4341 case BUILT_IN_MEMSET_CHK
:
4342 case BUILT_IN_TM_MEMSET
:
4344 tree res
= gimple_call_lhs (t
);
4345 tree dest
= gimple_call_arg (t
, 0);
4348 struct constraint_expr ac
;
4349 if (res
!= NULL_TREE
)
4351 get_constraint_for (res
, &lhsc
);
4352 get_constraint_for (dest
, &rhsc
);
4353 process_all_all_constraints (lhsc
, rhsc
);
4356 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4358 if (flag_delete_null_pointer_checks
4359 && integer_zerop (gimple_call_arg (t
, 1)))
4361 ac
.type
= ADDRESSOF
;
4362 ac
.var
= nothing_id
;
4367 ac
.var
= integer_id
;
4370 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4371 process_constraint (new_constraint (*lhsp
, ac
));
4374 case BUILT_IN_POSIX_MEMALIGN
:
4376 tree ptrptr
= gimple_call_arg (t
, 0);
4377 get_constraint_for (ptrptr
, &lhsc
);
4379 varinfo_t vi
= make_heapvar ("HEAP", true);
4380 /* We are marking allocated storage local, we deal with it becoming
4381 global by escaping and setting of vars_contains_escaped_heap. */
4382 DECL_EXTERNAL (vi
->decl
) = 0;
4383 vi
->is_global_var
= 0;
4384 struct constraint_expr tmpc
;
4387 tmpc
.type
= ADDRESSOF
;
4388 rhsc
.safe_push (tmpc
);
4389 process_all_all_constraints (lhsc
, rhsc
);
4392 case BUILT_IN_ASSUME_ALIGNED
:
4394 tree res
= gimple_call_lhs (t
);
4395 tree dest
= gimple_call_arg (t
, 0);
4396 if (res
!= NULL_TREE
)
4398 get_constraint_for (res
, &lhsc
);
4399 get_constraint_for (dest
, &rhsc
);
4400 process_all_all_constraints (lhsc
, rhsc
);
4404 /* All the following functions do not return pointers, do not
4405 modify the points-to sets of memory reachable from their
4406 arguments and do not add to the ESCAPED solution. */
4407 case BUILT_IN_SINCOS
:
4408 case BUILT_IN_SINCOSF
:
4409 case BUILT_IN_SINCOSL
:
4410 case BUILT_IN_FREXP
:
4411 case BUILT_IN_FREXPF
:
4412 case BUILT_IN_FREXPL
:
4413 case BUILT_IN_GAMMA_R
:
4414 case BUILT_IN_GAMMAF_R
:
4415 case BUILT_IN_GAMMAL_R
:
4416 case BUILT_IN_LGAMMA_R
:
4417 case BUILT_IN_LGAMMAF_R
:
4418 case BUILT_IN_LGAMMAL_R
:
4420 case BUILT_IN_MODFF
:
4421 case BUILT_IN_MODFL
:
4422 case BUILT_IN_REMQUO
:
4423 case BUILT_IN_REMQUOF
:
4424 case BUILT_IN_REMQUOL
:
4427 case BUILT_IN_STRDUP
:
4428 case BUILT_IN_STRNDUP
:
4429 case BUILT_IN_REALLOC
:
4430 if (gimple_call_lhs (t
))
4432 handle_lhs_call (t
, gimple_call_lhs (t
),
4433 gimple_call_return_flags (t
) | ERF_NOALIAS
,
4435 get_constraint_for_ptr_offset (gimple_call_lhs (t
),
4437 get_constraint_for_ptr_offset (gimple_call_arg (t
, 0),
4441 process_all_all_constraints (lhsc
, rhsc
);
4444 /* For realloc the resulting pointer can be equal to the
4445 argument as well. But only doing this wouldn't be
4446 correct because with ptr == 0 realloc behaves like malloc. */
4447 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_REALLOC
)
4449 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4450 get_constraint_for (gimple_call_arg (t
, 0), &rhsc
);
4451 process_all_all_constraints (lhsc
, rhsc
);
4456 /* String / character search functions return a pointer into the
4457 source string or NULL. */
4458 case BUILT_IN_INDEX
:
4459 case BUILT_IN_STRCHR
:
4460 case BUILT_IN_STRRCHR
:
4461 case BUILT_IN_MEMCHR
:
4462 case BUILT_IN_STRSTR
:
4463 case BUILT_IN_STRPBRK
:
4464 if (gimple_call_lhs (t
))
4466 tree src
= gimple_call_arg (t
, 0);
4467 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4468 constraint_expr nul
;
4469 nul
.var
= nothing_id
;
4471 nul
.type
= ADDRESSOF
;
4472 rhsc
.safe_push (nul
);
4473 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4474 process_all_all_constraints (lhsc
, rhsc
);
4477 /* Pure functions that return something not based on any object and
4478 that use the memory pointed to by their arguments (but not
4480 case BUILT_IN_STRCMP
:
4481 case BUILT_IN_STRNCMP
:
4482 case BUILT_IN_STRCASECMP
:
4483 case BUILT_IN_STRNCASECMP
:
4484 case BUILT_IN_MEMCMP
:
4486 case BUILT_IN_STRSPN
:
4487 case BUILT_IN_STRCSPN
:
4489 varinfo_t uses
= get_call_use_vi (t
);
4490 make_any_offset_constraints (uses
);
4491 make_constraint_to (uses
->id
, gimple_call_arg (t
, 0));
4492 make_constraint_to (uses
->id
, gimple_call_arg (t
, 1));
4493 /* No constraints are necessary for the return value. */
4496 case BUILT_IN_STRLEN
:
4498 varinfo_t uses
= get_call_use_vi (t
);
4499 make_any_offset_constraints (uses
);
4500 make_constraint_to (uses
->id
, gimple_call_arg (t
, 0));
4501 /* No constraints are necessary for the return value. */
4504 case BUILT_IN_OBJECT_SIZE
:
4505 case BUILT_IN_CONSTANT_P
:
4507 /* No constraints are necessary for the return value or the
4511 /* Trampolines are special - they set up passing the static
4513 case BUILT_IN_INIT_TRAMPOLINE
:
4515 tree tramp
= gimple_call_arg (t
, 0);
4516 tree nfunc
= gimple_call_arg (t
, 1);
4517 tree frame
= gimple_call_arg (t
, 2);
4519 struct constraint_expr lhs
, *rhsp
;
4522 varinfo_t nfi
= NULL
;
4523 gcc_assert (TREE_CODE (nfunc
) == ADDR_EXPR
);
4524 nfi
= lookup_vi_for_tree (TREE_OPERAND (nfunc
, 0));
4527 lhs
= get_function_part_constraint (nfi
, fi_static_chain
);
4528 get_constraint_for (frame
, &rhsc
);
4529 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4530 process_constraint (new_constraint (lhs
, *rhsp
));
4533 /* Make the frame point to the function for
4534 the trampoline adjustment call. */
4535 get_constraint_for (tramp
, &lhsc
);
4537 get_constraint_for (nfunc
, &rhsc
);
4538 process_all_all_constraints (lhsc
, rhsc
);
4543 /* Else fallthru to generic handling which will let
4544 the frame escape. */
4547 case BUILT_IN_ADJUST_TRAMPOLINE
:
4549 tree tramp
= gimple_call_arg (t
, 0);
4550 tree res
= gimple_call_lhs (t
);
4551 if (in_ipa_mode
&& res
)
4553 get_constraint_for (res
, &lhsc
);
4554 get_constraint_for (tramp
, &rhsc
);
4556 process_all_all_constraints (lhsc
, rhsc
);
4560 CASE_BUILT_IN_TM_STORE (1):
4561 CASE_BUILT_IN_TM_STORE (2):
4562 CASE_BUILT_IN_TM_STORE (4):
4563 CASE_BUILT_IN_TM_STORE (8):
4564 CASE_BUILT_IN_TM_STORE (FLOAT
):
4565 CASE_BUILT_IN_TM_STORE (DOUBLE
):
4566 CASE_BUILT_IN_TM_STORE (LDOUBLE
):
4567 CASE_BUILT_IN_TM_STORE (M64
):
4568 CASE_BUILT_IN_TM_STORE (M128
):
4569 CASE_BUILT_IN_TM_STORE (M256
):
4571 tree addr
= gimple_call_arg (t
, 0);
4572 tree src
= gimple_call_arg (t
, 1);
4574 get_constraint_for (addr
, &lhsc
);
4576 get_constraint_for (src
, &rhsc
);
4577 process_all_all_constraints (lhsc
, rhsc
);
4580 CASE_BUILT_IN_TM_LOAD (1):
4581 CASE_BUILT_IN_TM_LOAD (2):
4582 CASE_BUILT_IN_TM_LOAD (4):
4583 CASE_BUILT_IN_TM_LOAD (8):
4584 CASE_BUILT_IN_TM_LOAD (FLOAT
):
4585 CASE_BUILT_IN_TM_LOAD (DOUBLE
):
4586 CASE_BUILT_IN_TM_LOAD (LDOUBLE
):
4587 CASE_BUILT_IN_TM_LOAD (M64
):
4588 CASE_BUILT_IN_TM_LOAD (M128
):
4589 CASE_BUILT_IN_TM_LOAD (M256
):
4591 tree dest
= gimple_call_lhs (t
);
4592 tree addr
= gimple_call_arg (t
, 0);
4594 get_constraint_for (dest
, &lhsc
);
4595 get_constraint_for (addr
, &rhsc
);
4597 process_all_all_constraints (lhsc
, rhsc
);
4600 /* Variadic argument handling needs to be handled in IPA
4602 case BUILT_IN_VA_START
:
4604 tree valist
= gimple_call_arg (t
, 0);
4605 struct constraint_expr rhs
, *lhsp
;
4607 get_constraint_for_ptr_offset (valist
, NULL_TREE
, &lhsc
);
4609 /* The va_list gets access to pointers in variadic
4610 arguments. Which we know in the case of IPA analysis
4611 and otherwise are just all nonlocal variables. */
4614 fi
= lookup_vi_for_tree (fn
->decl
);
4615 rhs
= get_function_part_constraint (fi
, ~0);
4616 rhs
.type
= ADDRESSOF
;
4620 rhs
.var
= nonlocal_id
;
4621 rhs
.type
= ADDRESSOF
;
4624 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4625 process_constraint (new_constraint (*lhsp
, rhs
));
4626 /* va_list is clobbered. */
4627 make_constraint_to (get_call_clobber_vi (t
)->id
, valist
);
4630 /* va_end doesn't have any effect that matters. */
4631 case BUILT_IN_VA_END
:
4633 /* Alternate return. Simply give up for now. */
4634 case BUILT_IN_RETURN
:
4638 || !(fi
= get_vi_for_tree (fn
->decl
)))
4639 make_constraint_from (get_varinfo (escaped_id
), anything_id
);
4640 else if (in_ipa_mode
4643 struct constraint_expr lhs
, rhs
;
4644 lhs
= get_function_part_constraint (fi
, fi_result
);
4645 rhs
.var
= anything_id
;
4648 process_constraint (new_constraint (lhs
, rhs
));
4652 case BUILT_IN_GOMP_PARALLEL
:
4653 case BUILT_IN_GOACC_PARALLEL
:
4657 unsigned int fnpos
, argpos
;
4658 switch (DECL_FUNCTION_CODE (fndecl
))
4660 case BUILT_IN_GOMP_PARALLEL
:
4661 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
4665 case BUILT_IN_GOACC_PARALLEL
:
4666 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
4667 sizes, kinds, ...). */
4675 tree fnarg
= gimple_call_arg (t
, fnpos
);
4676 gcc_assert (TREE_CODE (fnarg
) == ADDR_EXPR
);
4677 tree fndecl
= TREE_OPERAND (fnarg
, 0);
4678 if (fndecl_maybe_in_other_partition (fndecl
))
4679 /* Fallthru to general call handling. */
4682 tree arg
= gimple_call_arg (t
, argpos
);
4684 varinfo_t fi
= get_vi_for_tree (fndecl
);
4685 find_func_aliases_for_call_arg (fi
, 0, arg
);
4688 /* Else fallthru to generic call handling. */
4691 /* printf-style functions may have hooks to set pointers to
4692 point to somewhere into the generated string. Leave them
4693 for a later exercise... */
4695 /* Fallthru to general call handling. */;
4701 /* Create constraints for the call T. */
4704 find_func_aliases_for_call (struct function
*fn
, gcall
*t
)
4706 tree fndecl
= gimple_call_fndecl (t
);
4709 if (fndecl
!= NULL_TREE
4710 && DECL_BUILT_IN (fndecl
)
4711 && find_func_aliases_for_builtin_call (fn
, t
))
4714 fi
= get_fi_for_callee (t
);
4716 || (fndecl
&& !fi
->is_fn_info
))
4718 auto_vec
<ce_s
, 16> rhsc
;
4719 int flags
= gimple_call_flags (t
);
4721 /* Const functions can return their arguments and addresses
4722 of global memory but not of escaped memory. */
4723 if (flags
& (ECF_CONST
|ECF_NOVOPS
))
4725 if (gimple_call_lhs (t
))
4726 handle_const_call (t
, &rhsc
);
4728 /* Pure functions can return addresses in and of memory
4729 reachable from their arguments, but they are not an escape
4730 point for reachable memory of their arguments. */
4731 else if (flags
& (ECF_PURE
|ECF_LOOPING_CONST_OR_PURE
))
4732 handle_pure_call (t
, &rhsc
);
4734 handle_rhs_call (t
, &rhsc
);
4735 if (gimple_call_lhs (t
))
4736 handle_lhs_call (t
, gimple_call_lhs (t
),
4737 gimple_call_return_flags (t
), rhsc
, fndecl
);
4741 auto_vec
<ce_s
, 2> rhsc
;
4745 /* Assign all the passed arguments to the appropriate incoming
4746 parameters of the function. */
4747 for (j
= 0; j
< gimple_call_num_args (t
); j
++)
4749 tree arg
= gimple_call_arg (t
, j
);
4750 find_func_aliases_for_call_arg (fi
, j
, arg
);
4753 /* If we are returning a value, assign it to the result. */
4754 lhsop
= gimple_call_lhs (t
);
4757 auto_vec
<ce_s
, 2> lhsc
;
4758 struct constraint_expr rhs
;
4759 struct constraint_expr
*lhsp
;
4760 bool aggr_p
= aggregate_value_p (lhsop
, gimple_call_fntype (t
));
4762 get_constraint_for (lhsop
, &lhsc
);
4763 rhs
= get_function_part_constraint (fi
, fi_result
);
4766 auto_vec
<ce_s
, 2> tem
;
4767 tem
.quick_push (rhs
);
4769 gcc_checking_assert (tem
.length () == 1);
4772 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4773 process_constraint (new_constraint (*lhsp
, rhs
));
4775 /* If we pass the result decl by reference, honor that. */
4778 struct constraint_expr lhs
;
4779 struct constraint_expr
*rhsp
;
4781 get_constraint_for_address_of (lhsop
, &rhsc
);
4782 lhs
= get_function_part_constraint (fi
, fi_result
);
4783 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4784 process_constraint (new_constraint (lhs
, *rhsp
));
4789 /* If we use a static chain, pass it along. */
4790 if (gimple_call_chain (t
))
4792 struct constraint_expr lhs
;
4793 struct constraint_expr
*rhsp
;
4795 get_constraint_for (gimple_call_chain (t
), &rhsc
);
4796 lhs
= get_function_part_constraint (fi
, fi_static_chain
);
4797 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4798 process_constraint (new_constraint (lhs
, *rhsp
));
4803 /* Walk statement T setting up aliasing constraints according to the
4804 references found in T. This function is the main part of the
4805 constraint builder. AI points to auxiliary alias information used
4806 when building alias sets and computing alias grouping heuristics. */
4809 find_func_aliases (struct function
*fn
, gimple
*origt
)
4812 auto_vec
<ce_s
, 16> lhsc
;
4813 auto_vec
<ce_s
, 16> rhsc
;
4814 struct constraint_expr
*c
;
4817 /* Now build constraints expressions. */
4818 if (gimple_code (t
) == GIMPLE_PHI
)
4823 /* For a phi node, assign all the arguments to
4825 get_constraint_for (gimple_phi_result (t
), &lhsc
);
4826 for (i
= 0; i
< gimple_phi_num_args (t
); i
++)
4828 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
4830 STRIP_NOPS (strippedrhs
);
4831 get_constraint_for_rhs (gimple_phi_arg_def (t
, i
), &rhsc
);
4833 FOR_EACH_VEC_ELT (lhsc
, j
, c
)
4835 struct constraint_expr
*c2
;
4836 while (rhsc
.length () > 0)
4839 process_constraint (new_constraint (*c
, *c2
));
4845 /* In IPA mode, we need to generate constraints to pass call
4846 arguments through their calls. There are two cases,
4847 either a GIMPLE_CALL returning a value, or just a plain
4848 GIMPLE_CALL when we are not.
4850 In non-ipa mode, we need to generate constraints for each
4851 pointer passed by address. */
4852 else if (is_gimple_call (t
))
4853 find_func_aliases_for_call (fn
, as_a
<gcall
*> (t
));
4855 /* Otherwise, just a regular assignment statement. Only care about
4856 operations with pointer result, others are dealt with as escape
4857 points if they have pointer operands. */
4858 else if (is_gimple_assign (t
))
4860 /* Otherwise, just a regular assignment statement. */
4861 tree lhsop
= gimple_assign_lhs (t
);
4862 tree rhsop
= (gimple_num_ops (t
) == 2) ? gimple_assign_rhs1 (t
) : NULL
;
4864 if (rhsop
&& TREE_CLOBBER_P (rhsop
))
4865 /* Ignore clobbers, they don't actually store anything into
4868 else if (rhsop
&& AGGREGATE_TYPE_P (TREE_TYPE (lhsop
)))
4869 do_structure_copy (lhsop
, rhsop
);
4872 enum tree_code code
= gimple_assign_rhs_code (t
);
4874 get_constraint_for (lhsop
, &lhsc
);
4876 if (code
== POINTER_PLUS_EXPR
)
4877 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4878 gimple_assign_rhs2 (t
), &rhsc
);
4879 else if (code
== BIT_AND_EXPR
4880 && TREE_CODE (gimple_assign_rhs2 (t
)) == INTEGER_CST
)
4882 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4883 the pointer. Handle it by offsetting it by UNKNOWN. */
4884 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4887 else if ((CONVERT_EXPR_CODE_P (code
)
4888 && !(POINTER_TYPE_P (gimple_expr_type (t
))
4889 && !POINTER_TYPE_P (TREE_TYPE (rhsop
))))
4890 || gimple_assign_single_p (t
))
4891 get_constraint_for_rhs (rhsop
, &rhsc
);
4892 else if (code
== COND_EXPR
)
4894 /* The result is a merge of both COND_EXPR arms. */
4895 auto_vec
<ce_s
, 2> tmp
;
4896 struct constraint_expr
*rhsp
;
4898 get_constraint_for_rhs (gimple_assign_rhs2 (t
), &rhsc
);
4899 get_constraint_for_rhs (gimple_assign_rhs3 (t
), &tmp
);
4900 FOR_EACH_VEC_ELT (tmp
, i
, rhsp
)
4901 rhsc
.safe_push (*rhsp
);
4903 else if (truth_value_p (code
))
4904 /* Truth value results are not pointer (parts). Or at least
4905 very unreasonable obfuscation of a part. */
4909 /* All other operations are merges. */
4910 auto_vec
<ce_s
, 4> tmp
;
4911 struct constraint_expr
*rhsp
;
4913 get_constraint_for_rhs (gimple_assign_rhs1 (t
), &rhsc
);
4914 for (i
= 2; i
< gimple_num_ops (t
); ++i
)
4916 get_constraint_for_rhs (gimple_op (t
, i
), &tmp
);
4917 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
4918 rhsc
.safe_push (*rhsp
);
4922 process_all_all_constraints (lhsc
, rhsc
);
4924 /* If there is a store to a global variable the rhs escapes. */
4925 if ((lhsop
= get_base_address (lhsop
)) != NULL_TREE
4928 varinfo_t vi
= get_vi_for_tree (lhsop
);
4929 if ((! in_ipa_mode
&& vi
->is_global_var
)
4930 || vi
->is_ipa_escape_point
)
4931 make_escape_constraint (rhsop
);
4934 /* Handle escapes through return. */
4935 else if (gimple_code (t
) == GIMPLE_RETURN
4936 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
)
4938 greturn
*return_stmt
= as_a
<greturn
*> (t
);
4941 || !(fi
= get_vi_for_tree (fn
->decl
)))
4942 make_escape_constraint (gimple_return_retval (return_stmt
));
4943 else if (in_ipa_mode
)
4945 struct constraint_expr lhs
;
4946 struct constraint_expr
*rhsp
;
4949 lhs
= get_function_part_constraint (fi
, fi_result
);
4950 get_constraint_for_rhs (gimple_return_retval (return_stmt
), &rhsc
);
4951 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4952 process_constraint (new_constraint (lhs
, *rhsp
));
4955 /* Handle asms conservatively by adding escape constraints to everything. */
4956 else if (gasm
*asm_stmt
= dyn_cast
<gasm
*> (t
))
4958 unsigned i
, noutputs
;
4959 const char **oconstraints
;
4960 const char *constraint
;
4961 bool allows_mem
, allows_reg
, is_inout
;
4963 noutputs
= gimple_asm_noutputs (asm_stmt
);
4964 oconstraints
= XALLOCAVEC (const char *, noutputs
);
4966 for (i
= 0; i
< noutputs
; ++i
)
4968 tree link
= gimple_asm_output_op (asm_stmt
, i
);
4969 tree op
= TREE_VALUE (link
);
4971 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4972 oconstraints
[i
] = constraint
;
4973 parse_output_constraint (&constraint
, i
, 0, 0, &allows_mem
,
4974 &allows_reg
, &is_inout
);
4976 /* A memory constraint makes the address of the operand escape. */
4977 if (!allows_reg
&& allows_mem
)
4978 make_escape_constraint (build_fold_addr_expr (op
));
4980 /* The asm may read global memory, so outputs may point to
4981 any global memory. */
4984 auto_vec
<ce_s
, 2> lhsc
;
4985 struct constraint_expr rhsc
, *lhsp
;
4987 get_constraint_for (op
, &lhsc
);
4988 rhsc
.var
= nonlocal_id
;
4991 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4992 process_constraint (new_constraint (*lhsp
, rhsc
));
4995 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); ++i
)
4997 tree link
= gimple_asm_input_op (asm_stmt
, i
);
4998 tree op
= TREE_VALUE (link
);
5000 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
5002 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0, oconstraints
,
5003 &allows_mem
, &allows_reg
);
5005 /* A memory constraint makes the address of the operand escape. */
5006 if (!allows_reg
&& allows_mem
)
5007 make_escape_constraint (build_fold_addr_expr (op
));
5008 /* Strictly we'd only need the constraint to ESCAPED if
5009 the asm clobbers memory, otherwise using something
5010 along the lines of per-call clobbers/uses would be enough. */
5012 make_escape_constraint (op
);
5018 /* Create a constraint adding to the clobber set of FI the memory
5019 pointed to by PTR. */
5022 process_ipa_clobber (varinfo_t fi
, tree ptr
)
5024 vec
<ce_s
> ptrc
= vNULL
;
5025 struct constraint_expr
*c
, lhs
;
5027 get_constraint_for_rhs (ptr
, &ptrc
);
5028 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5029 FOR_EACH_VEC_ELT (ptrc
, i
, c
)
5030 process_constraint (new_constraint (lhs
, *c
));
5034 /* Walk statement T setting up clobber and use constraints according to the
5035 references found in T. This function is a main part of the
5036 IPA constraint builder. */
5039 find_func_clobbers (struct function
*fn
, gimple
*origt
)
5042 auto_vec
<ce_s
, 16> lhsc
;
5043 auto_vec
<ce_s
, 16> rhsc
;
5046 /* Add constraints for clobbered/used in IPA mode.
5047 We are not interested in what automatic variables are clobbered
5048 or used as we only use the information in the caller to which
5049 they do not escape. */
5050 gcc_assert (in_ipa_mode
);
5052 /* If the stmt refers to memory in any way it better had a VUSE. */
5053 if (gimple_vuse (t
) == NULL_TREE
)
5056 /* We'd better have function information for the current function. */
5057 fi
= lookup_vi_for_tree (fn
->decl
);
5058 gcc_assert (fi
!= NULL
);
5060 /* Account for stores in assignments and calls. */
5061 if (gimple_vdef (t
) != NULL_TREE
5062 && gimple_has_lhs (t
))
5064 tree lhs
= gimple_get_lhs (t
);
5066 while (handled_component_p (tem
))
5067 tem
= TREE_OPERAND (tem
, 0);
5069 && !auto_var_in_fn_p (tem
, fn
->decl
))
5070 || INDIRECT_REF_P (tem
)
5071 || (TREE_CODE (tem
) == MEM_REF
5072 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
5074 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
5076 struct constraint_expr lhsc
, *rhsp
;
5078 lhsc
= get_function_part_constraint (fi
, fi_clobbers
);
5079 get_constraint_for_address_of (lhs
, &rhsc
);
5080 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5081 process_constraint (new_constraint (lhsc
, *rhsp
));
5086 /* Account for uses in assigments and returns. */
5087 if (gimple_assign_single_p (t
)
5088 || (gimple_code (t
) == GIMPLE_RETURN
5089 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
))
5091 tree rhs
= (gimple_assign_single_p (t
)
5092 ? gimple_assign_rhs1 (t
)
5093 : gimple_return_retval (as_a
<greturn
*> (t
)));
5095 while (handled_component_p (tem
))
5096 tem
= TREE_OPERAND (tem
, 0);
5098 && !auto_var_in_fn_p (tem
, fn
->decl
))
5099 || INDIRECT_REF_P (tem
)
5100 || (TREE_CODE (tem
) == MEM_REF
5101 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
5103 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
5105 struct constraint_expr lhs
, *rhsp
;
5107 lhs
= get_function_part_constraint (fi
, fi_uses
);
5108 get_constraint_for_address_of (rhs
, &rhsc
);
5109 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5110 process_constraint (new_constraint (lhs
, *rhsp
));
5115 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (t
))
5117 varinfo_t cfi
= NULL
;
5118 tree decl
= gimple_call_fndecl (t
);
5119 struct constraint_expr lhs
, rhs
;
5122 /* For builtins we do not have separate function info. For those
5123 we do not generate escapes for we have to generate clobbers/uses. */
5124 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
5125 switch (DECL_FUNCTION_CODE (decl
))
5127 /* The following functions use and clobber memory pointed to
5128 by their arguments. */
5129 case BUILT_IN_STRCPY
:
5130 case BUILT_IN_STRNCPY
:
5131 case BUILT_IN_BCOPY
:
5132 case BUILT_IN_MEMCPY
:
5133 case BUILT_IN_MEMMOVE
:
5134 case BUILT_IN_MEMPCPY
:
5135 case BUILT_IN_STPCPY
:
5136 case BUILT_IN_STPNCPY
:
5137 case BUILT_IN_STRCAT
:
5138 case BUILT_IN_STRNCAT
:
5139 case BUILT_IN_STRCPY_CHK
:
5140 case BUILT_IN_STRNCPY_CHK
:
5141 case BUILT_IN_MEMCPY_CHK
:
5142 case BUILT_IN_MEMMOVE_CHK
:
5143 case BUILT_IN_MEMPCPY_CHK
:
5144 case BUILT_IN_STPCPY_CHK
:
5145 case BUILT_IN_STPNCPY_CHK
:
5146 case BUILT_IN_STRCAT_CHK
:
5147 case BUILT_IN_STRNCAT_CHK
:
5149 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
5150 == BUILT_IN_BCOPY
? 1 : 0));
5151 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
5152 == BUILT_IN_BCOPY
? 0 : 1));
5154 struct constraint_expr
*rhsp
, *lhsp
;
5155 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5156 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5157 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5158 process_constraint (new_constraint (lhs
, *lhsp
));
5159 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
5160 lhs
= get_function_part_constraint (fi
, fi_uses
);
5161 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5162 process_constraint (new_constraint (lhs
, *rhsp
));
5165 /* The following function clobbers memory pointed to by
5167 case BUILT_IN_MEMSET
:
5168 case BUILT_IN_MEMSET_CHK
:
5169 case BUILT_IN_POSIX_MEMALIGN
:
5171 tree dest
= gimple_call_arg (t
, 0);
5174 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5175 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5176 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5177 process_constraint (new_constraint (lhs
, *lhsp
));
5180 /* The following functions clobber their second and third
5182 case BUILT_IN_SINCOS
:
5183 case BUILT_IN_SINCOSF
:
5184 case BUILT_IN_SINCOSL
:
5186 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5187 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5190 /* The following functions clobber their second argument. */
5191 case BUILT_IN_FREXP
:
5192 case BUILT_IN_FREXPF
:
5193 case BUILT_IN_FREXPL
:
5194 case BUILT_IN_LGAMMA_R
:
5195 case BUILT_IN_LGAMMAF_R
:
5196 case BUILT_IN_LGAMMAL_R
:
5197 case BUILT_IN_GAMMA_R
:
5198 case BUILT_IN_GAMMAF_R
:
5199 case BUILT_IN_GAMMAL_R
:
5201 case BUILT_IN_MODFF
:
5202 case BUILT_IN_MODFL
:
5204 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5207 /* The following functions clobber their third argument. */
5208 case BUILT_IN_REMQUO
:
5209 case BUILT_IN_REMQUOF
:
5210 case BUILT_IN_REMQUOL
:
5212 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5215 /* The following functions neither read nor clobber memory. */
5216 case BUILT_IN_ASSUME_ALIGNED
:
5219 /* Trampolines are of no interest to us. */
5220 case BUILT_IN_INIT_TRAMPOLINE
:
5221 case BUILT_IN_ADJUST_TRAMPOLINE
:
5223 case BUILT_IN_VA_START
:
5224 case BUILT_IN_VA_END
:
5226 case BUILT_IN_GOMP_PARALLEL
:
5227 case BUILT_IN_GOACC_PARALLEL
:
5229 unsigned int fnpos
, argpos
;
5230 unsigned int implicit_use_args
[2];
5231 unsigned int num_implicit_use_args
= 0;
5232 switch (DECL_FUNCTION_CODE (decl
))
5234 case BUILT_IN_GOMP_PARALLEL
:
5235 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
5239 case BUILT_IN_GOACC_PARALLEL
:
5240 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
5241 sizes, kinds, ...). */
5244 implicit_use_args
[num_implicit_use_args
++] = 4;
5245 implicit_use_args
[num_implicit_use_args
++] = 5;
5251 tree fnarg
= gimple_call_arg (t
, fnpos
);
5252 gcc_assert (TREE_CODE (fnarg
) == ADDR_EXPR
);
5253 tree fndecl
= TREE_OPERAND (fnarg
, 0);
5254 if (fndecl_maybe_in_other_partition (fndecl
))
5255 /* Fallthru to general call handling. */
5258 varinfo_t cfi
= get_vi_for_tree (fndecl
);
5260 tree arg
= gimple_call_arg (t
, argpos
);
5262 /* Parameter passed by value is used. */
5263 lhs
= get_function_part_constraint (fi
, fi_uses
);
5264 struct constraint_expr
*rhsp
;
5265 get_constraint_for (arg
, &rhsc
);
5266 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5267 process_constraint (new_constraint (lhs
, *rhsp
));
5270 /* Handle parameters used by the call, but not used in cfi, as
5271 implicitly used by cfi. */
5272 lhs
= get_function_part_constraint (cfi
, fi_uses
);
5273 for (unsigned i
= 0; i
< num_implicit_use_args
; ++i
)
5275 tree arg
= gimple_call_arg (t
, implicit_use_args
[i
]);
5276 get_constraint_for (arg
, &rhsc
);
5277 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5278 process_constraint (new_constraint (lhs
, *rhsp
));
5282 /* The caller clobbers what the callee does. */
5283 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5284 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5285 process_constraint (new_constraint (lhs
, rhs
));
5287 /* The caller uses what the callee does. */
5288 lhs
= get_function_part_constraint (fi
, fi_uses
);
5289 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5290 process_constraint (new_constraint (lhs
, rhs
));
5294 /* printf-style functions may have hooks to set pointers to
5295 point to somewhere into the generated string. Leave them
5296 for a later exercise... */
5298 /* Fallthru to general call handling. */;
5301 /* Parameters passed by value are used. */
5302 lhs
= get_function_part_constraint (fi
, fi_uses
);
5303 for (i
= 0; i
< gimple_call_num_args (t
); i
++)
5305 struct constraint_expr
*rhsp
;
5306 tree arg
= gimple_call_arg (t
, i
);
5308 if (TREE_CODE (arg
) == SSA_NAME
5309 || is_gimple_min_invariant (arg
))
5312 get_constraint_for_address_of (arg
, &rhsc
);
5313 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5314 process_constraint (new_constraint (lhs
, *rhsp
));
5318 /* Build constraints for propagating clobbers/uses along the
5320 cfi
= get_fi_for_callee (call_stmt
);
5321 if (cfi
->id
== anything_id
)
5323 if (gimple_vdef (t
))
5324 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5326 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5331 /* For callees without function info (that's external functions),
5332 ESCAPED is clobbered and used. */
5333 if (gimple_call_fndecl (t
)
5334 && !cfi
->is_fn_info
)
5338 if (gimple_vdef (t
))
5339 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5341 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
), escaped_id
);
5343 /* Also honor the call statement use/clobber info. */
5344 if ((vi
= lookup_call_clobber_vi (call_stmt
)) != NULL
)
5345 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5347 if ((vi
= lookup_call_use_vi (call_stmt
)) != NULL
)
5348 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
),
5353 /* Otherwise the caller clobbers and uses what the callee does.
5354 ??? This should use a new complex constraint that filters
5355 local variables of the callee. */
5356 if (gimple_vdef (t
))
5358 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5359 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5360 process_constraint (new_constraint (lhs
, rhs
));
5362 lhs
= get_function_part_constraint (fi
, fi_uses
);
5363 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5364 process_constraint (new_constraint (lhs
, rhs
));
5366 else if (gimple_code (t
) == GIMPLE_ASM
)
5368 /* ??? Ick. We can do better. */
5369 if (gimple_vdef (t
))
5370 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5372 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5378 /* Find the first varinfo in the same variable as START that overlaps with
5379 OFFSET. Return NULL if we can't find one. */
5382 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
5384 /* If the offset is outside of the variable, bail out. */
5385 if (offset
>= start
->fullsize
)
5388 /* If we cannot reach offset from start, lookup the first field
5389 and start from there. */
5390 if (start
->offset
> offset
)
5391 start
= get_varinfo (start
->head
);
5395 /* We may not find a variable in the field list with the actual
5396 offset when we have glommed a structure to a variable.
5397 In that case, however, offset should still be within the size
5399 if (offset
>= start
->offset
5400 && (offset
- start
->offset
) < start
->size
)
5403 start
= vi_next (start
);
5409 /* Find the first varinfo in the same variable as START that overlaps with
5410 OFFSET. If there is no such varinfo the varinfo directly preceding
5411 OFFSET is returned. */
5414 first_or_preceding_vi_for_offset (varinfo_t start
,
5415 unsigned HOST_WIDE_INT offset
)
5417 /* If we cannot reach offset from start, lookup the first field
5418 and start from there. */
5419 if (start
->offset
> offset
)
5420 start
= get_varinfo (start
->head
);
5422 /* We may not find a variable in the field list with the actual
5423 offset when we have glommed a structure to a variable.
5424 In that case, however, offset should still be within the size
5426 If we got beyond the offset we look for return the field
5427 directly preceding offset which may be the last field. */
5429 && offset
>= start
->offset
5430 && !((offset
- start
->offset
) < start
->size
))
5431 start
= vi_next (start
);
5437 /* This structure is used during pushing fields onto the fieldstack
5438 to track the offset of the field, since bitpos_of_field gives it
5439 relative to its immediate containing type, and we want it relative
5440 to the ultimate containing object. */
5444 /* Offset from the base of the base containing object to this field. */
5445 HOST_WIDE_INT offset
;
5447 /* Size, in bits, of the field. */
5448 unsigned HOST_WIDE_INT size
;
5450 unsigned has_unknown_size
: 1;
5452 unsigned must_have_pointers
: 1;
5454 unsigned may_have_pointers
: 1;
5456 unsigned only_restrict_pointers
: 1;
5458 tree restrict_pointed_type
;
5460 typedef struct fieldoff fieldoff_s
;
5463 /* qsort comparison function for two fieldoff's PA and PB */
5466 fieldoff_compare (const void *pa
, const void *pb
)
5468 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
5469 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
5470 unsigned HOST_WIDE_INT foasize
, fobsize
;
5472 if (foa
->offset
< fob
->offset
)
5474 else if (foa
->offset
> fob
->offset
)
5477 foasize
= foa
->size
;
5478 fobsize
= fob
->size
;
5479 if (foasize
< fobsize
)
5481 else if (foasize
> fobsize
)
5486 /* Sort a fieldstack according to the field offset and sizes. */
5488 sort_fieldstack (vec
<fieldoff_s
> fieldstack
)
5490 fieldstack
.qsort (fieldoff_compare
);
5493 /* Return true if T is a type that can have subvars. */
5496 type_can_have_subvars (const_tree t
)
5498 /* Aggregates without overlapping fields can have subvars. */
5499 return TREE_CODE (t
) == RECORD_TYPE
;
5502 /* Return true if V is a tree that we can have subvars for.
5503 Normally, this is any aggregate type. Also complex
5504 types which are not gimple registers can have subvars. */
5507 var_can_have_subvars (const_tree v
)
5509 /* Volatile variables should never have subvars. */
5510 if (TREE_THIS_VOLATILE (v
))
5513 /* Non decls or memory tags can never have subvars. */
5517 return type_can_have_subvars (TREE_TYPE (v
));
5520 /* Return true if T is a type that does contain pointers. */
5523 type_must_have_pointers (tree type
)
5525 if (POINTER_TYPE_P (type
))
5528 if (TREE_CODE (type
) == ARRAY_TYPE
)
5529 return type_must_have_pointers (TREE_TYPE (type
));
5531 /* A function or method can have pointers as arguments, so track
5532 those separately. */
5533 if (TREE_CODE (type
) == FUNCTION_TYPE
5534 || TREE_CODE (type
) == METHOD_TYPE
)
5541 field_must_have_pointers (tree t
)
5543 return type_must_have_pointers (TREE_TYPE (t
));
5546 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5547 the fields of TYPE onto fieldstack, recording their offsets along
5550 OFFSET is used to keep track of the offset in this entire
5551 structure, rather than just the immediately containing structure.
5552 Returns false if the caller is supposed to handle the field we
5556 push_fields_onto_fieldstack (tree type
, vec
<fieldoff_s
> *fieldstack
,
5557 HOST_WIDE_INT offset
)
5560 bool empty_p
= true;
5562 if (TREE_CODE (type
) != RECORD_TYPE
)
5565 /* If the vector of fields is growing too big, bail out early.
5566 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5568 if (fieldstack
->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5571 for (field
= TYPE_FIELDS (type
); field
; field
= DECL_CHAIN (field
))
5572 if (TREE_CODE (field
) == FIELD_DECL
)
5575 HOST_WIDE_INT foff
= bitpos_of_field (field
);
5576 tree field_type
= TREE_TYPE (field
);
5578 if (!var_can_have_subvars (field
)
5579 || TREE_CODE (field_type
) == QUAL_UNION_TYPE
5580 || TREE_CODE (field_type
) == UNION_TYPE
)
5582 else if (!push_fields_onto_fieldstack
5583 (field_type
, fieldstack
, offset
+ foff
)
5584 && (DECL_SIZE (field
)
5585 && !integer_zerop (DECL_SIZE (field
))))
5586 /* Empty structures may have actual size, like in C++. So
5587 see if we didn't push any subfields and the size is
5588 nonzero, push the field onto the stack. */
5593 fieldoff_s
*pair
= NULL
;
5594 bool has_unknown_size
= false;
5595 bool must_have_pointers_p
;
5597 if (!fieldstack
->is_empty ())
5598 pair
= &fieldstack
->last ();
5600 /* If there isn't anything at offset zero, create sth. */
5602 && offset
+ foff
!= 0)
5605 = {0, offset
+ foff
, false, false, true, false, NULL_TREE
};
5606 pair
= fieldstack
->safe_push (e
);
5609 if (!DECL_SIZE (field
)
5610 || !tree_fits_uhwi_p (DECL_SIZE (field
)))
5611 has_unknown_size
= true;
5613 /* If adjacent fields do not contain pointers merge them. */
5614 must_have_pointers_p
= field_must_have_pointers (field
);
5616 && !has_unknown_size
5617 && !must_have_pointers_p
5618 && !pair
->must_have_pointers
5619 && !pair
->has_unknown_size
5620 && pair
->offset
+ (HOST_WIDE_INT
)pair
->size
== offset
+ foff
)
5622 pair
->size
+= tree_to_uhwi (DECL_SIZE (field
));
5627 e
.offset
= offset
+ foff
;
5628 e
.has_unknown_size
= has_unknown_size
;
5629 if (!has_unknown_size
)
5630 e
.size
= tree_to_uhwi (DECL_SIZE (field
));
5633 e
.must_have_pointers
= must_have_pointers_p
;
5634 e
.may_have_pointers
= true;
5635 e
.only_restrict_pointers
5636 = (!has_unknown_size
5637 && POINTER_TYPE_P (field_type
)
5638 && TYPE_RESTRICT (field_type
));
5639 if (e
.only_restrict_pointers
)
5640 e
.restrict_pointed_type
= TREE_TYPE (field_type
);
5641 fieldstack
->safe_push (e
);
5651 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5652 if it is a varargs function. */
5655 count_num_arguments (tree decl
, bool *is_varargs
)
5657 unsigned int num
= 0;
5660 /* Capture named arguments for K&R functions. They do not
5661 have a prototype and thus no TYPE_ARG_TYPES. */
5662 for (t
= DECL_ARGUMENTS (decl
); t
; t
= DECL_CHAIN (t
))
5665 /* Check if the function has variadic arguments. */
5666 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
)); t
; t
= TREE_CHAIN (t
))
5667 if (TREE_VALUE (t
) == void_type_node
)
5675 /* Creation function node for DECL, using NAME, and return the index
5676 of the variable we've created for the function. If NONLOCAL_p, create
5677 initial constraints. */
5680 create_function_info_for (tree decl
, const char *name
, bool add_id
,
5683 struct function
*fn
= DECL_STRUCT_FUNCTION (decl
);
5684 varinfo_t vi
, prev_vi
;
5687 bool is_varargs
= false;
5688 unsigned int num_args
= count_num_arguments (decl
, &is_varargs
);
5690 /* Create the variable info. */
5692 vi
= new_var_info (decl
, name
, add_id
);
5695 vi
->fullsize
= fi_parm_base
+ num_args
;
5697 vi
->may_have_pointers
= false;
5700 insert_vi_for_tree (vi
->decl
, vi
);
5704 /* Create a variable for things the function clobbers and one for
5705 things the function uses. */
5707 varinfo_t clobbervi
, usevi
;
5708 const char *newname
;
5711 tempname
= xasprintf ("%s.clobber", name
);
5712 newname
= ggc_strdup (tempname
);
5715 clobbervi
= new_var_info (NULL
, newname
, false);
5716 clobbervi
->offset
= fi_clobbers
;
5717 clobbervi
->size
= 1;
5718 clobbervi
->fullsize
= vi
->fullsize
;
5719 clobbervi
->is_full_var
= true;
5720 clobbervi
->is_global_var
= false;
5722 gcc_assert (prev_vi
->offset
< clobbervi
->offset
);
5723 prev_vi
->next
= clobbervi
->id
;
5724 prev_vi
= clobbervi
;
5726 tempname
= xasprintf ("%s.use", name
);
5727 newname
= ggc_strdup (tempname
);
5730 usevi
= new_var_info (NULL
, newname
, false);
5731 usevi
->offset
= fi_uses
;
5733 usevi
->fullsize
= vi
->fullsize
;
5734 usevi
->is_full_var
= true;
5735 usevi
->is_global_var
= false;
5737 gcc_assert (prev_vi
->offset
< usevi
->offset
);
5738 prev_vi
->next
= usevi
->id
;
5742 /* And one for the static chain. */
5743 if (fn
->static_chain_decl
!= NULL_TREE
)
5746 const char *newname
;
5749 tempname
= xasprintf ("%s.chain", name
);
5750 newname
= ggc_strdup (tempname
);
5753 chainvi
= new_var_info (fn
->static_chain_decl
, newname
, false);
5754 chainvi
->offset
= fi_static_chain
;
5756 chainvi
->fullsize
= vi
->fullsize
;
5757 chainvi
->is_full_var
= true;
5758 chainvi
->is_global_var
= false;
5760 insert_vi_for_tree (fn
->static_chain_decl
, chainvi
);
5763 && chainvi
->may_have_pointers
)
5764 make_constraint_from (chainvi
, nonlocal_id
);
5766 gcc_assert (prev_vi
->offset
< chainvi
->offset
);
5767 prev_vi
->next
= chainvi
->id
;
5771 /* Create a variable for the return var. */
5772 if (DECL_RESULT (decl
) != NULL
5773 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
5776 const char *newname
;
5778 tree resultdecl
= decl
;
5780 if (DECL_RESULT (decl
))
5781 resultdecl
= DECL_RESULT (decl
);
5783 tempname
= xasprintf ("%s.result", name
);
5784 newname
= ggc_strdup (tempname
);
5787 resultvi
= new_var_info (resultdecl
, newname
, false);
5788 resultvi
->offset
= fi_result
;
5790 resultvi
->fullsize
= vi
->fullsize
;
5791 resultvi
->is_full_var
= true;
5792 if (DECL_RESULT (decl
))
5793 resultvi
->may_have_pointers
= true;
5795 if (DECL_RESULT (decl
))
5796 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
5799 && DECL_RESULT (decl
)
5800 && DECL_BY_REFERENCE (DECL_RESULT (decl
)))
5801 make_constraint_from (resultvi
, nonlocal_id
);
5803 gcc_assert (prev_vi
->offset
< resultvi
->offset
);
5804 prev_vi
->next
= resultvi
->id
;
5808 /* We also need to make function return values escape. Nothing
5809 escapes by returning from main though. */
5811 && !MAIN_NAME_P (DECL_NAME (decl
)))
5814 fi
= lookup_vi_for_tree (decl
);
5815 rvi
= first_vi_for_offset (fi
, fi_result
);
5816 if (rvi
&& rvi
->offset
== fi_result
)
5817 make_copy_constraint (get_varinfo (escaped_id
), rvi
->id
);
5820 /* Set up variables for each argument. */
5821 arg
= DECL_ARGUMENTS (decl
);
5822 for (i
= 0; i
< num_args
; i
++)
5825 const char *newname
;
5827 tree argdecl
= decl
;
5832 tempname
= xasprintf ("%s.arg%d", name
, i
);
5833 newname
= ggc_strdup (tempname
);
5836 argvi
= new_var_info (argdecl
, newname
, false);
5837 argvi
->offset
= fi_parm_base
+ i
;
5839 argvi
->is_full_var
= true;
5840 argvi
->fullsize
= vi
->fullsize
;
5842 argvi
->may_have_pointers
= true;
5845 insert_vi_for_tree (arg
, argvi
);
5848 && argvi
->may_have_pointers
)
5849 make_constraint_from (argvi
, nonlocal_id
);
5851 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5852 prev_vi
->next
= argvi
->id
;
5855 arg
= DECL_CHAIN (arg
);
5858 /* Add one representative for all further args. */
5862 const char *newname
;
5866 tempname
= xasprintf ("%s.varargs", name
);
5867 newname
= ggc_strdup (tempname
);
5870 /* We need sth that can be pointed to for va_start. */
5871 decl
= build_fake_var_decl (ptr_type_node
);
5873 argvi
= new_var_info (decl
, newname
, false);
5874 argvi
->offset
= fi_parm_base
+ num_args
;
5876 argvi
->is_full_var
= true;
5877 argvi
->is_heap_var
= true;
5878 argvi
->fullsize
= vi
->fullsize
;
5881 && argvi
->may_have_pointers
)
5882 make_constraint_from (argvi
, nonlocal_id
);
5884 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5885 prev_vi
->next
= argvi
->id
;
5893 /* Return true if FIELDSTACK contains fields that overlap.
5894 FIELDSTACK is assumed to be sorted by offset. */
5897 check_for_overlaps (vec
<fieldoff_s
> fieldstack
)
5899 fieldoff_s
*fo
= NULL
;
5901 HOST_WIDE_INT lastoffset
= -1;
5903 FOR_EACH_VEC_ELT (fieldstack
, i
, fo
)
5905 if (fo
->offset
== lastoffset
)
5907 lastoffset
= fo
->offset
;
5912 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5913 This will also create any varinfo structures necessary for fields
5914 of DECL. DECL is a function parameter if HANDLE_PARAM is set.
5915 HANDLED_STRUCT_TYPE is used to register struct types reached by following
5916 restrict pointers. This is needed to prevent infinite recursion. */
5919 create_variable_info_for_1 (tree decl
, const char *name
, bool add_id
,
5920 bool handle_param
, bitmap handled_struct_type
)
5922 varinfo_t vi
, newvi
;
5923 tree decl_type
= TREE_TYPE (decl
);
5924 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decl_type
);
5925 auto_vec
<fieldoff_s
> fieldstack
;
5930 || !tree_fits_uhwi_p (declsize
))
5932 vi
= new_var_info (decl
, name
, add_id
);
5936 vi
->is_unknown_size_var
= true;
5937 vi
->is_full_var
= true;
5938 vi
->may_have_pointers
= true;
5942 /* Collect field information. */
5943 if (use_field_sensitive
5944 && var_can_have_subvars (decl
)
5945 /* ??? Force us to not use subfields for globals in IPA mode.
5946 Else we'd have to parse arbitrary initializers. */
5948 && is_global_var (decl
)))
5950 fieldoff_s
*fo
= NULL
;
5951 bool notokay
= false;
5954 push_fields_onto_fieldstack (decl_type
, &fieldstack
, 0);
5956 for (i
= 0; !notokay
&& fieldstack
.iterate (i
, &fo
); i
++)
5957 if (fo
->has_unknown_size
5964 /* We can't sort them if we have a field with a variable sized type,
5965 which will make notokay = true. In that case, we are going to return
5966 without creating varinfos for the fields anyway, so sorting them is a
5970 sort_fieldstack (fieldstack
);
5971 /* Due to some C++ FE issues, like PR 22488, we might end up
5972 what appear to be overlapping fields even though they,
5973 in reality, do not overlap. Until the C++ FE is fixed,
5974 we will simply disable field-sensitivity for these cases. */
5975 notokay
= check_for_overlaps (fieldstack
);
5979 fieldstack
.release ();
5982 /* If we didn't end up collecting sub-variables create a full
5983 variable for the decl. */
5984 if (fieldstack
.length () == 0
5985 || fieldstack
.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5987 vi
= new_var_info (decl
, name
, add_id
);
5989 vi
->may_have_pointers
= true;
5990 vi
->fullsize
= tree_to_uhwi (declsize
);
5991 vi
->size
= vi
->fullsize
;
5992 vi
->is_full_var
= true;
5993 if (POINTER_TYPE_P (decl_type
)
5994 && TYPE_RESTRICT (decl_type
))
5995 vi
->only_restrict_pointers
= 1;
5996 if (vi
->only_restrict_pointers
5997 && !type_contains_placeholder_p (TREE_TYPE (decl_type
))
5999 && !bitmap_bit_p (handled_struct_type
,
6000 TYPE_UID (TREE_TYPE (decl_type
))))
6003 tree heapvar
= build_fake_var_decl (TREE_TYPE (decl_type
));
6004 DECL_EXTERNAL (heapvar
) = 1;
6005 if (var_can_have_subvars (heapvar
))
6006 bitmap_set_bit (handled_struct_type
,
6007 TYPE_UID (TREE_TYPE (decl_type
)));
6008 rvi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS", true,
6009 true, handled_struct_type
);
6010 if (var_can_have_subvars (heapvar
))
6011 bitmap_clear_bit (handled_struct_type
,
6012 TYPE_UID (TREE_TYPE (decl_type
)));
6013 rvi
->is_restrict_var
= 1;
6014 insert_vi_for_tree (heapvar
, rvi
);
6015 make_constraint_from (vi
, rvi
->id
);
6016 make_param_constraints (rvi
);
6018 fieldstack
.release ();
6022 vi
= new_var_info (decl
, name
, add_id
);
6023 vi
->fullsize
= tree_to_uhwi (declsize
);
6024 if (fieldstack
.length () == 1)
6025 vi
->is_full_var
= true;
6026 for (i
= 0, newvi
= vi
;
6027 fieldstack
.iterate (i
, &fo
);
6028 ++i
, newvi
= vi_next (newvi
))
6030 const char *newname
= NULL
;
6035 if (fieldstack
.length () != 1)
6038 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC
6039 "+" HOST_WIDE_INT_PRINT_DEC
, name
,
6040 fo
->offset
, fo
->size
);
6041 newname
= ggc_strdup (tempname
);
6049 newvi
->name
= newname
;
6050 newvi
->offset
= fo
->offset
;
6051 newvi
->size
= fo
->size
;
6052 newvi
->fullsize
= vi
->fullsize
;
6053 newvi
->may_have_pointers
= fo
->may_have_pointers
;
6054 newvi
->only_restrict_pointers
= fo
->only_restrict_pointers
;
6056 && newvi
->only_restrict_pointers
6057 && !type_contains_placeholder_p (fo
->restrict_pointed_type
)
6058 && !bitmap_bit_p (handled_struct_type
,
6059 TYPE_UID (fo
->restrict_pointed_type
)))
6062 tree heapvar
= build_fake_var_decl (fo
->restrict_pointed_type
);
6063 DECL_EXTERNAL (heapvar
) = 1;
6064 if (var_can_have_subvars (heapvar
))
6065 bitmap_set_bit (handled_struct_type
,
6066 TYPE_UID (fo
->restrict_pointed_type
));
6067 rvi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS", true,
6068 true, handled_struct_type
);
6069 if (var_can_have_subvars (heapvar
))
6070 bitmap_clear_bit (handled_struct_type
,
6071 TYPE_UID (fo
->restrict_pointed_type
));
6072 rvi
->is_restrict_var
= 1;
6073 insert_vi_for_tree (heapvar
, rvi
);
6074 make_constraint_from (newvi
, rvi
->id
);
6075 make_param_constraints (rvi
);
6077 if (i
+ 1 < fieldstack
.length ())
6079 varinfo_t tem
= new_var_info (decl
, name
, false);
6080 newvi
->next
= tem
->id
;
6089 create_variable_info_for (tree decl
, const char *name
, bool add_id
)
6091 varinfo_t vi
= create_variable_info_for_1 (decl
, name
, add_id
, false, NULL
);
6092 unsigned int id
= vi
->id
;
6094 insert_vi_for_tree (decl
, vi
);
6099 /* Create initial constraints for globals. */
6100 for (; vi
; vi
= vi_next (vi
))
6102 if (!vi
->may_have_pointers
6103 || !vi
->is_global_var
)
6106 /* Mark global restrict qualified pointers. */
6107 if ((POINTER_TYPE_P (TREE_TYPE (decl
))
6108 && TYPE_RESTRICT (TREE_TYPE (decl
)))
6109 || vi
->only_restrict_pointers
)
6112 = make_constraint_from_global_restrict (vi
, "GLOBAL_RESTRICT",
6114 /* ??? For now exclude reads from globals as restrict sources
6115 if those are not (indirectly) from incoming parameters. */
6116 rvi
->is_restrict_var
= false;
6120 /* In non-IPA mode the initializer from nonlocal is all we need. */
6122 || DECL_HARD_REGISTER (decl
))
6123 make_copy_constraint (vi
, nonlocal_id
);
6125 /* In IPA mode parse the initializer and generate proper constraints
6129 varpool_node
*vnode
= varpool_node::get (decl
);
6131 /* For escaped variables initialize them from nonlocal. */
6132 if (!vnode
->all_refs_explicit_p ())
6133 make_copy_constraint (vi
, nonlocal_id
);
6135 /* If this is a global variable with an initializer and we are in
6136 IPA mode generate constraints for it. */
6138 for (unsigned idx
= 0; vnode
->iterate_reference (idx
, ref
); ++idx
)
6140 auto_vec
<ce_s
> rhsc
;
6141 struct constraint_expr lhs
, *rhsp
;
6143 get_constraint_for_address_of (ref
->referred
->decl
, &rhsc
);
6147 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
6148 process_constraint (new_constraint (lhs
, *rhsp
));
6149 /* If this is a variable that escapes from the unit
6150 the initializer escapes as well. */
6151 if (!vnode
->all_refs_explicit_p ())
6153 lhs
.var
= escaped_id
;
6156 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
6157 process_constraint (new_constraint (lhs
, *rhsp
));
6166 /* Print out the points-to solution for VAR to FILE. */
6169 dump_solution_for_var (FILE *file
, unsigned int var
)
6171 varinfo_t vi
= get_varinfo (var
);
6175 /* Dump the solution for unified vars anyway, this avoids difficulties
6176 in scanning dumps in the testsuite. */
6177 fprintf (file
, "%s = { ", vi
->name
);
6178 vi
= get_varinfo (find (var
));
6179 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6180 fprintf (file
, "%s ", get_varinfo (i
)->name
);
6181 fprintf (file
, "}");
6183 /* But note when the variable was unified. */
6185 fprintf (file
, " same as %s", vi
->name
);
6187 fprintf (file
, "\n");
6190 /* Print the points-to solution for VAR to stderr. */
6193 debug_solution_for_var (unsigned int var
)
6195 dump_solution_for_var (stderr
, var
);
6198 /* Register the constraints for function parameter related VI. */
6201 make_param_constraints (varinfo_t vi
)
6203 for (; vi
; vi
= vi_next (vi
))
6205 if (vi
->only_restrict_pointers
)
6207 else if (vi
->may_have_pointers
)
6208 make_constraint_from (vi
, nonlocal_id
);
6210 if (vi
->is_full_var
)
6215 /* Create varinfo structures for all of the variables in the
6216 function for intraprocedural mode. */
6219 intra_create_variable_infos (struct function
*fn
)
6222 bitmap handled_struct_type
= NULL
;
6224 /* For each incoming pointer argument arg, create the constraint ARG
6225 = NONLOCAL or a dummy variable if it is a restrict qualified
6226 passed-by-reference argument. */
6227 for (t
= DECL_ARGUMENTS (fn
->decl
); t
; t
= DECL_CHAIN (t
))
6229 if (handled_struct_type
== NULL
)
6230 handled_struct_type
= BITMAP_ALLOC (NULL
);
6233 = create_variable_info_for_1 (t
, alias_get_name (t
), false, true,
6234 handled_struct_type
);
6235 insert_vi_for_tree (t
, p
);
6237 make_param_constraints (p
);
6240 if (handled_struct_type
!= NULL
)
6241 BITMAP_FREE (handled_struct_type
);
6243 /* Add a constraint for a result decl that is passed by reference. */
6244 if (DECL_RESULT (fn
->decl
)
6245 && DECL_BY_REFERENCE (DECL_RESULT (fn
->decl
)))
6247 varinfo_t p
, result_vi
= get_vi_for_tree (DECL_RESULT (fn
->decl
));
6249 for (p
= result_vi
; p
; p
= vi_next (p
))
6250 make_constraint_from (p
, nonlocal_id
);
6253 /* Add a constraint for the incoming static chain parameter. */
6254 if (fn
->static_chain_decl
!= NULL_TREE
)
6256 varinfo_t p
, chain_vi
= get_vi_for_tree (fn
->static_chain_decl
);
6258 for (p
= chain_vi
; p
; p
= vi_next (p
))
6259 make_constraint_from (p
, nonlocal_id
);
6263 /* Structure used to put solution bitmaps in a hashtable so they can
6264 be shared among variables with the same points-to set. */
6266 typedef struct shared_bitmap_info
6270 } *shared_bitmap_info_t
;
6271 typedef const struct shared_bitmap_info
*const_shared_bitmap_info_t
;
6273 /* Shared_bitmap hashtable helpers. */
6275 struct shared_bitmap_hasher
: free_ptr_hash
<shared_bitmap_info
>
6277 static inline hashval_t
hash (const shared_bitmap_info
*);
6278 static inline bool equal (const shared_bitmap_info
*,
6279 const shared_bitmap_info
*);
6282 /* Hash function for a shared_bitmap_info_t */
6285 shared_bitmap_hasher::hash (const shared_bitmap_info
*bi
)
6287 return bi
->hashcode
;
6290 /* Equality function for two shared_bitmap_info_t's. */
6293 shared_bitmap_hasher::equal (const shared_bitmap_info
*sbi1
,
6294 const shared_bitmap_info
*sbi2
)
6296 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
6299 /* Shared_bitmap hashtable. */
6301 static hash_table
<shared_bitmap_hasher
> *shared_bitmap_table
;
6303 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
6304 existing instance if there is one, NULL otherwise. */
6307 shared_bitmap_lookup (bitmap pt_vars
)
6309 shared_bitmap_info
**slot
;
6310 struct shared_bitmap_info sbi
;
6312 sbi
.pt_vars
= pt_vars
;
6313 sbi
.hashcode
= bitmap_hash (pt_vars
);
6315 slot
= shared_bitmap_table
->find_slot (&sbi
, NO_INSERT
);
6319 return (*slot
)->pt_vars
;
6323 /* Add a bitmap to the shared bitmap hashtable. */
6326 shared_bitmap_add (bitmap pt_vars
)
6328 shared_bitmap_info
**slot
;
6329 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
6331 sbi
->pt_vars
= pt_vars
;
6332 sbi
->hashcode
= bitmap_hash (pt_vars
);
6334 slot
= shared_bitmap_table
->find_slot (sbi
, INSERT
);
6335 gcc_assert (!*slot
);
6340 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
6343 set_uids_in_ptset (bitmap into
, bitmap from
, struct pt_solution
*pt
,
6348 varinfo_t escaped_vi
= get_varinfo (find (escaped_id
));
6349 bool everything_escaped
6350 = escaped_vi
->solution
&& bitmap_bit_p (escaped_vi
->solution
, anything_id
);
6352 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
6354 varinfo_t vi
= get_varinfo (i
);
6356 /* The only artificial variables that are allowed in a may-alias
6357 set are heap variables. */
6358 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
6361 if (everything_escaped
6362 || (escaped_vi
->solution
6363 && bitmap_bit_p (escaped_vi
->solution
, i
)))
6365 pt
->vars_contains_escaped
= true;
6366 pt
->vars_contains_escaped_heap
= vi
->is_heap_var
;
6369 if (vi
->is_restrict_var
)
6370 pt
->vars_contains_restrict
= true;
6372 if (VAR_P (vi
->decl
)
6373 || TREE_CODE (vi
->decl
) == PARM_DECL
6374 || TREE_CODE (vi
->decl
) == RESULT_DECL
)
6376 /* If we are in IPA mode we will not recompute points-to
6377 sets after inlining so make sure they stay valid. */
6379 && !DECL_PT_UID_SET_P (vi
->decl
))
6380 SET_DECL_PT_UID (vi
->decl
, DECL_UID (vi
->decl
));
6382 /* Add the decl to the points-to set. Note that the points-to
6383 set contains global variables. */
6384 bitmap_set_bit (into
, DECL_PT_UID (vi
->decl
));
6385 if (vi
->is_global_var
6386 /* In IPA mode the escaped_heap trick doesn't work as
6387 ESCAPED is escaped from the unit but
6388 pt_solution_includes_global needs to answer true for
6389 all variables not automatic within a function.
6390 For the same reason is_global_var is not the
6391 correct flag to track - local variables from other
6392 functions also need to be considered global.
6393 Conveniently all HEAP vars are not put in function
6397 && ! auto_var_in_fn_p (vi
->decl
, fndecl
)))
6398 pt
->vars_contains_nonlocal
= true;
6400 /* If we have a variable that is interposable record that fact
6401 for pointer comparison simplification. */
6402 if (VAR_P (vi
->decl
)
6403 && (TREE_STATIC (vi
->decl
) || DECL_EXTERNAL (vi
->decl
))
6404 && ! decl_binds_to_current_def_p (vi
->decl
))
6405 pt
->vars_contains_interposable
= true;
6408 else if (TREE_CODE (vi
->decl
) == FUNCTION_DECL
6409 || TREE_CODE (vi
->decl
) == LABEL_DECL
)
6411 /* Nothing should read/write from/to code so we can
6412 save bits by not including them in the points-to bitmaps.
6413 Still mark the points-to set as containing global memory
6414 to make code-patching possible - see PR70128. */
6415 pt
->vars_contains_nonlocal
= true;
6421 /* Compute the points-to solution *PT for the variable VI. */
6423 static struct pt_solution
6424 find_what_var_points_to (tree fndecl
, varinfo_t orig_vi
)
6428 bitmap finished_solution
;
6431 struct pt_solution
*pt
;
6433 /* This variable may have been collapsed, let's get the real
6435 vi
= get_varinfo (find (orig_vi
->id
));
6437 /* See if we have already computed the solution and return it. */
6438 pt_solution
**slot
= &final_solutions
->get_or_insert (vi
);
6442 *slot
= pt
= XOBNEW (&final_solutions_obstack
, struct pt_solution
);
6443 memset (pt
, 0, sizeof (struct pt_solution
));
6445 /* Translate artificial variables into SSA_NAME_PTR_INFO
6447 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6449 varinfo_t vi
= get_varinfo (i
);
6451 if (vi
->is_artificial_var
)
6453 if (vi
->id
== nothing_id
)
6455 else if (vi
->id
== escaped_id
)
6458 pt
->ipa_escaped
= 1;
6461 /* Expand some special vars of ESCAPED in-place here. */
6462 varinfo_t evi
= get_varinfo (find (escaped_id
));
6463 if (bitmap_bit_p (evi
->solution
, nonlocal_id
))
6466 else if (vi
->id
== nonlocal_id
)
6468 else if (vi
->is_heap_var
)
6469 /* We represent heapvars in the points-to set properly. */
6471 else if (vi
->id
== string_id
)
6472 /* Nobody cares - STRING_CSTs are read-only entities. */
6474 else if (vi
->id
== anything_id
6475 || vi
->id
== integer_id
)
6480 /* Instead of doing extra work, simply do not create
6481 elaborate points-to information for pt_anything pointers. */
6485 /* Share the final set of variables when possible. */
6486 finished_solution
= BITMAP_GGC_ALLOC ();
6487 stats
.points_to_sets_created
++;
6489 set_uids_in_ptset (finished_solution
, vi
->solution
, pt
, fndecl
);
6490 result
= shared_bitmap_lookup (finished_solution
);
6493 shared_bitmap_add (finished_solution
);
6494 pt
->vars
= finished_solution
;
6499 bitmap_clear (finished_solution
);
6505 /* Given a pointer variable P, fill in its points-to set. */
6508 find_what_p_points_to (tree fndecl
, tree p
)
6510 struct ptr_info_def
*pi
;
6513 bool nonnull
= get_ptr_nonnull (p
);
6515 /* For parameters, get at the points-to set for the actual parm
6517 if (TREE_CODE (p
) == SSA_NAME
6518 && SSA_NAME_IS_DEFAULT_DEF (p
)
6519 && (TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
6520 || TREE_CODE (SSA_NAME_VAR (p
)) == RESULT_DECL
))
6521 lookup_p
= SSA_NAME_VAR (p
);
6523 vi
= lookup_vi_for_tree (lookup_p
);
6527 pi
= get_ptr_info (p
);
6528 pi
->pt
= find_what_var_points_to (fndecl
, vi
);
6529 /* Conservatively set to NULL from PTA (to true). */
6531 /* Preserve pointer nonnull computed by VRP. See get_ptr_nonnull
6532 in gcc/tree-ssaname.c for more information. */
6534 set_ptr_nonnull (p
);
6538 /* Query statistics for points-to solutions. */
6541 unsigned HOST_WIDE_INT pt_solution_includes_may_alias
;
6542 unsigned HOST_WIDE_INT pt_solution_includes_no_alias
;
6543 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias
;
6544 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias
;
6548 dump_pta_stats (FILE *s
)
6550 fprintf (s
, "\nPTA query stats:\n");
6551 fprintf (s
, " pt_solution_includes: "
6552 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6553 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6554 pta_stats
.pt_solution_includes_no_alias
,
6555 pta_stats
.pt_solution_includes_no_alias
6556 + pta_stats
.pt_solution_includes_may_alias
);
6557 fprintf (s
, " pt_solutions_intersect: "
6558 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6559 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6560 pta_stats
.pt_solutions_intersect_no_alias
,
6561 pta_stats
.pt_solutions_intersect_no_alias
6562 + pta_stats
.pt_solutions_intersect_may_alias
);
6566 /* Reset the points-to solution *PT to a conservative default
6567 (point to anything). */
6570 pt_solution_reset (struct pt_solution
*pt
)
6572 memset (pt
, 0, sizeof (struct pt_solution
));
6573 pt
->anything
= true;
6577 /* Set the points-to solution *PT to point only to the variables
6578 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6579 global variables and VARS_CONTAINS_RESTRICT specifies whether
6580 it contains restrict tag variables. */
6583 pt_solution_set (struct pt_solution
*pt
, bitmap vars
,
6584 bool vars_contains_nonlocal
)
6586 memset (pt
, 0, sizeof (struct pt_solution
));
6588 pt
->vars_contains_nonlocal
= vars_contains_nonlocal
;
6589 pt
->vars_contains_escaped
6590 = (cfun
->gimple_df
->escaped
.anything
6591 || bitmap_intersect_p (cfun
->gimple_df
->escaped
.vars
, vars
));
6594 /* Set the points-to solution *PT to point only to the variable VAR. */
6597 pt_solution_set_var (struct pt_solution
*pt
, tree var
)
6599 memset (pt
, 0, sizeof (struct pt_solution
));
6600 pt
->vars
= BITMAP_GGC_ALLOC ();
6601 bitmap_set_bit (pt
->vars
, DECL_PT_UID (var
));
6602 pt
->vars_contains_nonlocal
= is_global_var (var
);
6603 pt
->vars_contains_escaped
6604 = (cfun
->gimple_df
->escaped
.anything
6605 || bitmap_bit_p (cfun
->gimple_df
->escaped
.vars
, DECL_PT_UID (var
)));
6608 /* Computes the union of the points-to solutions *DEST and *SRC and
6609 stores the result in *DEST. This changes the points-to bitmap
6610 of *DEST and thus may not be used if that might be shared.
6611 The points-to bitmap of *SRC and *DEST will not be shared after
6612 this function if they were not before. */
6615 pt_solution_ior_into (struct pt_solution
*dest
, struct pt_solution
*src
)
6617 dest
->anything
|= src
->anything
;
6620 pt_solution_reset (dest
);
6624 dest
->nonlocal
|= src
->nonlocal
;
6625 dest
->escaped
|= src
->escaped
;
6626 dest
->ipa_escaped
|= src
->ipa_escaped
;
6627 dest
->null
|= src
->null
;
6628 dest
->vars_contains_nonlocal
|= src
->vars_contains_nonlocal
;
6629 dest
->vars_contains_escaped
|= src
->vars_contains_escaped
;
6630 dest
->vars_contains_escaped_heap
|= src
->vars_contains_escaped_heap
;
6635 dest
->vars
= BITMAP_GGC_ALLOC ();
6636 bitmap_ior_into (dest
->vars
, src
->vars
);
6639 /* Return true if the points-to solution *PT is empty. */
6642 pt_solution_empty_p (struct pt_solution
*pt
)
6649 && !bitmap_empty_p (pt
->vars
))
6652 /* If the solution includes ESCAPED, check if that is empty. */
6654 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
6657 /* If the solution includes ESCAPED, check if that is empty. */
6659 && !pt_solution_empty_p (&ipa_escaped_pt
))
6665 /* Return true if the points-to solution *PT only point to a single var, and
6666 return the var uid in *UID. */
6669 pt_solution_singleton_or_null_p (struct pt_solution
*pt
, unsigned *uid
)
6671 if (pt
->anything
|| pt
->nonlocal
|| pt
->escaped
|| pt
->ipa_escaped
6673 || !bitmap_single_bit_set_p (pt
->vars
))
6676 *uid
= bitmap_first_set_bit (pt
->vars
);
6680 /* Return true if the points-to solution *PT includes global memory. */
6683 pt_solution_includes_global (struct pt_solution
*pt
)
6687 || pt
->vars_contains_nonlocal
6688 /* The following is a hack to make the malloc escape hack work.
6689 In reality we'd need different sets for escaped-through-return
6690 and escaped-to-callees and passes would need to be updated. */
6691 || pt
->vars_contains_escaped_heap
)
6694 /* 'escaped' is also a placeholder so we have to look into it. */
6696 return pt_solution_includes_global (&cfun
->gimple_df
->escaped
);
6698 if (pt
->ipa_escaped
)
6699 return pt_solution_includes_global (&ipa_escaped_pt
);
6704 /* Return true if the points-to solution *PT includes the variable
6705 declaration DECL. */
6708 pt_solution_includes_1 (struct pt_solution
*pt
, const_tree decl
)
6714 && is_global_var (decl
))
6718 && bitmap_bit_p (pt
->vars
, DECL_PT_UID (decl
)))
6721 /* If the solution includes ESCAPED, check it. */
6723 && pt_solution_includes_1 (&cfun
->gimple_df
->escaped
, decl
))
6726 /* If the solution includes ESCAPED, check it. */
6728 && pt_solution_includes_1 (&ipa_escaped_pt
, decl
))
6735 pt_solution_includes (struct pt_solution
*pt
, const_tree decl
)
6737 bool res
= pt_solution_includes_1 (pt
, decl
);
6739 ++pta_stats
.pt_solution_includes_may_alias
;
6741 ++pta_stats
.pt_solution_includes_no_alias
;
6745 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6749 pt_solutions_intersect_1 (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6751 if (pt1
->anything
|| pt2
->anything
)
6754 /* If either points to unknown global memory and the other points to
6755 any global memory they alias. */
6758 || pt2
->vars_contains_nonlocal
))
6760 && pt1
->vars_contains_nonlocal
))
6763 /* If either points to all escaped memory and the other points to
6764 any escaped memory they alias. */
6767 || pt2
->vars_contains_escaped
))
6769 && pt1
->vars_contains_escaped
))
6772 /* Check the escaped solution if required.
6773 ??? Do we need to check the local against the IPA escaped sets? */
6774 if ((pt1
->ipa_escaped
|| pt2
->ipa_escaped
)
6775 && !pt_solution_empty_p (&ipa_escaped_pt
))
6777 /* If both point to escaped memory and that solution
6778 is not empty they alias. */
6779 if (pt1
->ipa_escaped
&& pt2
->ipa_escaped
)
6782 /* If either points to escaped memory see if the escaped solution
6783 intersects with the other. */
6784 if ((pt1
->ipa_escaped
6785 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt2
))
6786 || (pt2
->ipa_escaped
6787 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt1
)))
6791 /* Now both pointers alias if their points-to solution intersects. */
6794 && bitmap_intersect_p (pt1
->vars
, pt2
->vars
));
6798 pt_solutions_intersect (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6800 bool res
= pt_solutions_intersect_1 (pt1
, pt2
);
6802 ++pta_stats
.pt_solutions_intersect_may_alias
;
6804 ++pta_stats
.pt_solutions_intersect_no_alias
;
6809 /* Dump points-to information to OUTFILE. */
6812 dump_sa_points_to_info (FILE *outfile
)
6816 fprintf (outfile
, "\nPoints-to sets\n\n");
6818 if (dump_flags
& TDF_STATS
)
6820 fprintf (outfile
, "Stats:\n");
6821 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
6822 fprintf (outfile
, "Non-pointer vars: %d\n",
6823 stats
.nonpointer_vars
);
6824 fprintf (outfile
, "Statically unified vars: %d\n",
6825 stats
.unified_vars_static
);
6826 fprintf (outfile
, "Dynamically unified vars: %d\n",
6827 stats
.unified_vars_dynamic
);
6828 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
6829 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
6830 fprintf (outfile
, "Number of implicit edges: %d\n",
6831 stats
.num_implicit_edges
);
6834 for (i
= 1; i
< varmap
.length (); i
++)
6836 varinfo_t vi
= get_varinfo (i
);
6837 if (!vi
->may_have_pointers
)
6839 dump_solution_for_var (outfile
, i
);
6844 /* Debug points-to information to stderr. */
6847 debug_sa_points_to_info (void)
6849 dump_sa_points_to_info (stderr
);
6853 /* Initialize the always-existing constraint variables for NULL
6854 ANYTHING, READONLY, and INTEGER */
6857 init_base_vars (void)
6859 struct constraint_expr lhs
, rhs
;
6860 varinfo_t var_anything
;
6861 varinfo_t var_nothing
;
6862 varinfo_t var_string
;
6863 varinfo_t var_escaped
;
6864 varinfo_t var_nonlocal
;
6865 varinfo_t var_storedanything
;
6866 varinfo_t var_integer
;
6868 /* Variable ID zero is reserved and should be NULL. */
6869 varmap
.safe_push (NULL
);
6871 /* Create the NULL variable, used to represent that a variable points
6873 var_nothing
= new_var_info (NULL_TREE
, "NULL", false);
6874 gcc_assert (var_nothing
->id
== nothing_id
);
6875 var_nothing
->is_artificial_var
= 1;
6876 var_nothing
->offset
= 0;
6877 var_nothing
->size
= ~0;
6878 var_nothing
->fullsize
= ~0;
6879 var_nothing
->is_special_var
= 1;
6880 var_nothing
->may_have_pointers
= 0;
6881 var_nothing
->is_global_var
= 0;
6883 /* Create the ANYTHING variable, used to represent that a variable
6884 points to some unknown piece of memory. */
6885 var_anything
= new_var_info (NULL_TREE
, "ANYTHING", false);
6886 gcc_assert (var_anything
->id
== anything_id
);
6887 var_anything
->is_artificial_var
= 1;
6888 var_anything
->size
= ~0;
6889 var_anything
->offset
= 0;
6890 var_anything
->fullsize
= ~0;
6891 var_anything
->is_special_var
= 1;
6893 /* Anything points to anything. This makes deref constraints just
6894 work in the presence of linked list and other p = *p type loops,
6895 by saying that *ANYTHING = ANYTHING. */
6897 lhs
.var
= anything_id
;
6899 rhs
.type
= ADDRESSOF
;
6900 rhs
.var
= anything_id
;
6903 /* This specifically does not use process_constraint because
6904 process_constraint ignores all anything = anything constraints, since all
6905 but this one are redundant. */
6906 constraints
.safe_push (new_constraint (lhs
, rhs
));
6908 /* Create the STRING variable, used to represent that a variable
6909 points to a string literal. String literals don't contain
6910 pointers so STRING doesn't point to anything. */
6911 var_string
= new_var_info (NULL_TREE
, "STRING", false);
6912 gcc_assert (var_string
->id
== string_id
);
6913 var_string
->is_artificial_var
= 1;
6914 var_string
->offset
= 0;
6915 var_string
->size
= ~0;
6916 var_string
->fullsize
= ~0;
6917 var_string
->is_special_var
= 1;
6918 var_string
->may_have_pointers
= 0;
6920 /* Create the ESCAPED variable, used to represent the set of escaped
6922 var_escaped
= new_var_info (NULL_TREE
, "ESCAPED", false);
6923 gcc_assert (var_escaped
->id
== escaped_id
);
6924 var_escaped
->is_artificial_var
= 1;
6925 var_escaped
->offset
= 0;
6926 var_escaped
->size
= ~0;
6927 var_escaped
->fullsize
= ~0;
6928 var_escaped
->is_special_var
= 0;
6930 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6932 var_nonlocal
= new_var_info (NULL_TREE
, "NONLOCAL", false);
6933 gcc_assert (var_nonlocal
->id
== nonlocal_id
);
6934 var_nonlocal
->is_artificial_var
= 1;
6935 var_nonlocal
->offset
= 0;
6936 var_nonlocal
->size
= ~0;
6937 var_nonlocal
->fullsize
= ~0;
6938 var_nonlocal
->is_special_var
= 1;
6940 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6942 lhs
.var
= escaped_id
;
6945 rhs
.var
= escaped_id
;
6947 process_constraint (new_constraint (lhs
, rhs
));
6949 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6950 whole variable escapes. */
6952 lhs
.var
= escaped_id
;
6955 rhs
.var
= escaped_id
;
6956 rhs
.offset
= UNKNOWN_OFFSET
;
6957 process_constraint (new_constraint (lhs
, rhs
));
6959 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6960 everything pointed to by escaped points to what global memory can
6963 lhs
.var
= escaped_id
;
6966 rhs
.var
= nonlocal_id
;
6968 process_constraint (new_constraint (lhs
, rhs
));
6970 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6971 global memory may point to global memory and escaped memory. */
6973 lhs
.var
= nonlocal_id
;
6975 rhs
.type
= ADDRESSOF
;
6976 rhs
.var
= nonlocal_id
;
6978 process_constraint (new_constraint (lhs
, rhs
));
6979 rhs
.type
= ADDRESSOF
;
6980 rhs
.var
= escaped_id
;
6982 process_constraint (new_constraint (lhs
, rhs
));
6984 /* Create the STOREDANYTHING variable, used to represent the set of
6985 variables stored to *ANYTHING. */
6986 var_storedanything
= new_var_info (NULL_TREE
, "STOREDANYTHING", false);
6987 gcc_assert (var_storedanything
->id
== storedanything_id
);
6988 var_storedanything
->is_artificial_var
= 1;
6989 var_storedanything
->offset
= 0;
6990 var_storedanything
->size
= ~0;
6991 var_storedanything
->fullsize
= ~0;
6992 var_storedanything
->is_special_var
= 0;
6994 /* Create the INTEGER variable, used to represent that a variable points
6995 to what an INTEGER "points to". */
6996 var_integer
= new_var_info (NULL_TREE
, "INTEGER", false);
6997 gcc_assert (var_integer
->id
== integer_id
);
6998 var_integer
->is_artificial_var
= 1;
6999 var_integer
->size
= ~0;
7000 var_integer
->fullsize
= ~0;
7001 var_integer
->offset
= 0;
7002 var_integer
->is_special_var
= 1;
7004 /* INTEGER = ANYTHING, because we don't know where a dereference of
7005 a random integer will point to. */
7007 lhs
.var
= integer_id
;
7009 rhs
.type
= ADDRESSOF
;
7010 rhs
.var
= anything_id
;
7012 process_constraint (new_constraint (lhs
, rhs
));
7015 /* Initialize things necessary to perform PTA */
7018 init_alias_vars (void)
7020 use_field_sensitive
= (MAX_FIELDS_FOR_FIELD_SENSITIVE
> 1);
7022 bitmap_obstack_initialize (&pta_obstack
);
7023 bitmap_obstack_initialize (&oldpta_obstack
);
7024 bitmap_obstack_initialize (&predbitmap_obstack
);
7026 constraints
.create (8);
7028 vi_for_tree
= new hash_map
<tree
, varinfo_t
>;
7029 call_stmt_vars
= new hash_map
<gimple
*, varinfo_t
>;
7031 memset (&stats
, 0, sizeof (stats
));
7032 shared_bitmap_table
= new hash_table
<shared_bitmap_hasher
> (511);
7035 gcc_obstack_init (&fake_var_decl_obstack
);
7037 final_solutions
= new hash_map
<varinfo_t
, pt_solution
*>;
7038 gcc_obstack_init (&final_solutions_obstack
);
7041 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
7042 predecessor edges. */
7045 remove_preds_and_fake_succs (constraint_graph_t graph
)
7049 /* Clear the implicit ref and address nodes from the successor
7051 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
7053 if (graph
->succs
[i
])
7054 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
7055 FIRST_REF_NODE
* 2);
7058 /* Free the successor list for the non-ref nodes. */
7059 for (i
= FIRST_REF_NODE
+ 1; i
< graph
->size
; i
++)
7061 if (graph
->succs
[i
])
7062 BITMAP_FREE (graph
->succs
[i
]);
7065 /* Now reallocate the size of the successor list as, and blow away
7066 the predecessor bitmaps. */
7067 graph
->size
= varmap
.length ();
7068 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
7070 free (graph
->implicit_preds
);
7071 graph
->implicit_preds
= NULL
;
7072 free (graph
->preds
);
7073 graph
->preds
= NULL
;
7074 bitmap_obstack_release (&predbitmap_obstack
);
7077 /* Solve the constraint set. */
7080 solve_constraints (void)
7082 struct scc_info
*si
;
7086 "\nCollapsing static cycles and doing variable "
7089 init_graph (varmap
.length () * 2);
7092 fprintf (dump_file
, "Building predecessor graph\n");
7093 build_pred_graph ();
7096 fprintf (dump_file
, "Detecting pointer and location "
7098 si
= perform_var_substitution (graph
);
7101 fprintf (dump_file
, "Rewriting constraints and unifying "
7103 rewrite_constraints (graph
, si
);
7105 build_succ_graph ();
7107 free_var_substitution_info (si
);
7109 /* Attach complex constraints to graph nodes. */
7110 move_complex_constraints (graph
);
7113 fprintf (dump_file
, "Uniting pointer but not location equivalent "
7115 unite_pointer_equivalences (graph
);
7118 fprintf (dump_file
, "Finding indirect cycles\n");
7119 find_indirect_cycles (graph
);
7121 /* Implicit nodes and predecessors are no longer necessary at this
7123 remove_preds_and_fake_succs (graph
);
7125 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
7127 fprintf (dump_file
, "\n\n// The constraint graph before solve-graph "
7128 "in dot format:\n");
7129 dump_constraint_graph (dump_file
);
7130 fprintf (dump_file
, "\n\n");
7134 fprintf (dump_file
, "Solving graph\n");
7136 solve_graph (graph
);
7138 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
7140 fprintf (dump_file
, "\n\n// The constraint graph after solve-graph "
7141 "in dot format:\n");
7142 dump_constraint_graph (dump_file
);
7143 fprintf (dump_file
, "\n\n");
7147 dump_sa_points_to_info (dump_file
);
7150 /* Create points-to sets for the current function. See the comments
7151 at the start of the file for an algorithmic overview. */
7154 compute_points_to_sets (void)
7159 timevar_push (TV_TREE_PTA
);
7163 intra_create_variable_infos (cfun
);
7165 /* Now walk all statements and build the constraint set. */
7166 FOR_EACH_BB_FN (bb
, cfun
)
7168 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7171 gphi
*phi
= gsi
.phi ();
7173 if (! virtual_operand_p (gimple_phi_result (phi
)))
7174 find_func_aliases (cfun
, phi
);
7177 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
7180 gimple
*stmt
= gsi_stmt (gsi
);
7182 find_func_aliases (cfun
, stmt
);
7188 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
7189 dump_constraints (dump_file
, 0);
7192 /* From the constraints compute the points-to sets. */
7193 solve_constraints ();
7195 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
7196 cfun
->gimple_df
->escaped
= find_what_var_points_to (cfun
->decl
,
7197 get_varinfo (escaped_id
));
7199 /* Make sure the ESCAPED solution (which is used as placeholder in
7200 other solutions) does not reference itself. This simplifies
7201 points-to solution queries. */
7202 cfun
->gimple_df
->escaped
.escaped
= 0;
7204 /* Compute the points-to sets for pointer SSA_NAMEs. */
7208 FOR_EACH_SSA_NAME (i
, ptr
, cfun
)
7210 if (POINTER_TYPE_P (TREE_TYPE (ptr
)))
7211 find_what_p_points_to (cfun
->decl
, ptr
);
7214 /* Compute the call-used/clobbered sets. */
7215 FOR_EACH_BB_FN (bb
, cfun
)
7217 gimple_stmt_iterator gsi
;
7219 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7222 struct pt_solution
*pt
;
7224 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
7228 pt
= gimple_call_use_set (stmt
);
7229 if (gimple_call_flags (stmt
) & ECF_CONST
)
7230 memset (pt
, 0, sizeof (struct pt_solution
));
7231 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
7233 *pt
= find_what_var_points_to (cfun
->decl
, vi
);
7234 /* Escaped (and thus nonlocal) variables are always
7235 implicitly used by calls. */
7236 /* ??? ESCAPED can be empty even though NONLOCAL
7243 /* If there is nothing special about this call then
7244 we have made everything that is used also escape. */
7245 *pt
= cfun
->gimple_df
->escaped
;
7249 pt
= gimple_call_clobber_set (stmt
);
7250 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
7251 memset (pt
, 0, sizeof (struct pt_solution
));
7252 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
7254 *pt
= find_what_var_points_to (cfun
->decl
, vi
);
7255 /* Escaped (and thus nonlocal) variables are always
7256 implicitly clobbered by calls. */
7257 /* ??? ESCAPED can be empty even though NONLOCAL
7264 /* If there is nothing special about this call then
7265 we have made everything that is used also escape. */
7266 *pt
= cfun
->gimple_df
->escaped
;
7272 timevar_pop (TV_TREE_PTA
);
7276 /* Delete created points-to sets. */
7279 delete_points_to_sets (void)
7283 delete shared_bitmap_table
;
7284 shared_bitmap_table
= NULL
;
7285 if (dump_file
&& (dump_flags
& TDF_STATS
))
7286 fprintf (dump_file
, "Points to sets created:%d\n",
7287 stats
.points_to_sets_created
);
7290 delete call_stmt_vars
;
7291 bitmap_obstack_release (&pta_obstack
);
7292 constraints
.release ();
7294 for (i
= 0; i
< graph
->size
; i
++)
7295 graph
->complex[i
].release ();
7296 free (graph
->complex);
7299 free (graph
->succs
);
7301 free (graph
->pe_rep
);
7302 free (graph
->indirect_cycles
);
7306 variable_info_pool
.release ();
7307 constraint_pool
.release ();
7309 obstack_free (&fake_var_decl_obstack
, NULL
);
7311 delete final_solutions
;
7312 obstack_free (&final_solutions_obstack
, NULL
);
7317 unsigned short clique
;
7321 /* Mark "other" loads and stores as belonging to CLIQUE and with
7325 visit_loadstore (gimple
*, tree base
, tree ref
, void *data
)
7327 unsigned short clique
= ((vls_data
*) data
)->clique
;
7328 bitmap rvars
= ((vls_data
*) data
)->rvars
;
7329 if (TREE_CODE (base
) == MEM_REF
7330 || TREE_CODE (base
) == TARGET_MEM_REF
)
7332 tree ptr
= TREE_OPERAND (base
, 0);
7333 if (TREE_CODE (ptr
) == SSA_NAME
)
7335 /* For parameters, get at the points-to set for the actual parm
7337 if (SSA_NAME_IS_DEFAULT_DEF (ptr
)
7338 && (TREE_CODE (SSA_NAME_VAR (ptr
)) == PARM_DECL
7339 || TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
))
7340 ptr
= SSA_NAME_VAR (ptr
);
7342 /* We need to make sure 'ptr' doesn't include any of
7343 the restrict tags we added bases for in its points-to set. */
7344 varinfo_t vi
= lookup_vi_for_tree (ptr
);
7348 vi
= get_varinfo (find (vi
->id
));
7349 if (bitmap_intersect_p (rvars
, vi
->solution
))
7353 /* Do not overwrite existing cliques (that includes clique, base
7354 pairs we just set). */
7355 if (MR_DEPENDENCE_CLIQUE (base
) == 0)
7357 MR_DEPENDENCE_CLIQUE (base
) = clique
;
7358 MR_DEPENDENCE_BASE (base
) = 0;
7362 /* For plain decl accesses see whether they are accesses to globals
7363 and rewrite them to MEM_REFs with { clique, 0 }. */
7365 && is_global_var (base
)
7366 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
7371 while (handled_component_p (*basep
))
7372 basep
= &TREE_OPERAND (*basep
, 0);
7373 gcc_assert (VAR_P (*basep
));
7374 tree ptr
= build_fold_addr_expr (*basep
);
7375 tree zero
= build_int_cst (TREE_TYPE (ptr
), 0);
7376 *basep
= build2 (MEM_REF
, TREE_TYPE (*basep
), ptr
, zero
);
7377 MR_DEPENDENCE_CLIQUE (*basep
) = clique
;
7378 MR_DEPENDENCE_BASE (*basep
) = 0;
7384 /* If REF is a MEM_REF then assign a clique, base pair to it, updating
7385 CLIQUE, *RESTRICT_VAR and LAST_RUID. Return whether dependence info
7386 was assigned to REF. */
7389 maybe_set_dependence_info (tree ref
, tree ptr
,
7390 unsigned short &clique
, varinfo_t restrict_var
,
7391 unsigned short &last_ruid
)
7393 while (handled_component_p (ref
))
7394 ref
= TREE_OPERAND (ref
, 0);
7395 if ((TREE_CODE (ref
) == MEM_REF
7396 || TREE_CODE (ref
) == TARGET_MEM_REF
)
7397 && TREE_OPERAND (ref
, 0) == ptr
)
7399 /* Do not overwrite existing cliques. This avoids overwriting dependence
7400 info inlined from a function with restrict parameters inlined
7401 into a function with restrict parameters. This usually means we
7402 prefer to be precise in innermost loops. */
7403 if (MR_DEPENDENCE_CLIQUE (ref
) == 0)
7406 clique
= ++cfun
->last_clique
;
7407 if (restrict_var
->ruid
== 0)
7408 restrict_var
->ruid
= ++last_ruid
;
7409 MR_DEPENDENCE_CLIQUE (ref
) = clique
;
7410 MR_DEPENDENCE_BASE (ref
) = restrict_var
->ruid
;
7417 /* Compute the set of independend memory references based on restrict
7418 tags and their conservative propagation to the points-to sets. */
7421 compute_dependence_clique (void)
7423 unsigned short clique
= 0;
7424 unsigned short last_ruid
= 0;
7425 bitmap rvars
= BITMAP_ALLOC (NULL
);
7426 for (unsigned i
= 0; i
< num_ssa_names
; ++i
)
7428 tree ptr
= ssa_name (i
);
7429 if (!ptr
|| !POINTER_TYPE_P (TREE_TYPE (ptr
)))
7432 /* Avoid all this when ptr is not dereferenced? */
7434 if (SSA_NAME_IS_DEFAULT_DEF (ptr
)
7435 && (TREE_CODE (SSA_NAME_VAR (ptr
)) == PARM_DECL
7436 || TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
))
7437 p
= SSA_NAME_VAR (ptr
);
7438 varinfo_t vi
= lookup_vi_for_tree (p
);
7441 vi
= get_varinfo (find (vi
->id
));
7444 varinfo_t restrict_var
= NULL
;
7445 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, j
, bi
)
7447 varinfo_t oi
= get_varinfo (j
);
7448 if (oi
->is_restrict_var
)
7452 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7454 fprintf (dump_file
, "found restrict pointed-to "
7456 print_generic_expr (dump_file
, ptr
, 0);
7457 fprintf (dump_file
, " but not exclusively\n");
7459 restrict_var
= NULL
;
7464 /* NULL is the only other valid points-to entry. */
7465 else if (oi
->id
!= nothing_id
)
7467 restrict_var
= NULL
;
7471 /* Ok, found that ptr must(!) point to a single(!) restrict
7473 /* ??? PTA isn't really a proper propagation engine to compute
7475 ??? We could handle merging of two restricts by unifying them. */
7478 /* Now look at possible dereferences of ptr. */
7479 imm_use_iterator ui
;
7482 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, ptr
)
7484 /* ??? Calls and asms. */
7485 if (!gimple_assign_single_p (use_stmt
))
7487 used
|= maybe_set_dependence_info (gimple_assign_lhs (use_stmt
),
7488 ptr
, clique
, restrict_var
,
7490 used
|= maybe_set_dependence_info (gimple_assign_rhs1 (use_stmt
),
7491 ptr
, clique
, restrict_var
,
7495 bitmap_set_bit (rvars
, restrict_var
->id
);
7501 /* Assign the BASE id zero to all accesses not based on a restrict
7502 pointer. That way they get disambiguated against restrict
7503 accesses but not against each other. */
7504 /* ??? For restricts derived from globals (thus not incoming
7505 parameters) we can't restrict scoping properly thus the following
7506 is too aggressive there. For now we have excluded those globals from
7507 getting into the MR_DEPENDENCE machinery. */
7508 vls_data data
= { clique
, rvars
};
7510 FOR_EACH_BB_FN (bb
, cfun
)
7511 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
7512 !gsi_end_p (gsi
); gsi_next (&gsi
))
7514 gimple
*stmt
= gsi_stmt (gsi
);
7515 walk_stmt_load_store_ops (stmt
, &data
,
7516 visit_loadstore
, visit_loadstore
);
7520 BITMAP_FREE (rvars
);
7523 /* Compute points-to information for every SSA_NAME pointer in the
7524 current function and compute the transitive closure of escaped
7525 variables to re-initialize the call-clobber states of local variables. */
7528 compute_may_aliases (void)
7530 if (cfun
->gimple_df
->ipa_pta
)
7534 fprintf (dump_file
, "\nNot re-computing points-to information "
7535 "because IPA points-to information is available.\n\n");
7537 /* But still dump what we have remaining it. */
7538 dump_alias_info (dump_file
);
7544 /* For each pointer P_i, determine the sets of variables that P_i may
7545 point-to. Compute the reachability set of escaped and call-used
7547 compute_points_to_sets ();
7549 /* Debugging dumps. */
7551 dump_alias_info (dump_file
);
7553 /* Compute restrict-based memory disambiguations. */
7554 compute_dependence_clique ();
7556 /* Deallocate memory used by aliasing data structures and the internal
7557 points-to solution. */
7558 delete_points_to_sets ();
7560 gcc_assert (!need_ssa_update_p (cfun
));
7565 /* A dummy pass to cause points-to information to be computed via
7566 TODO_rebuild_alias. */
7570 const pass_data pass_data_build_alias
=
7572 GIMPLE_PASS
, /* type */
7574 OPTGROUP_NONE
, /* optinfo_flags */
7575 TV_NONE
, /* tv_id */
7576 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7577 0, /* properties_provided */
7578 0, /* properties_destroyed */
7579 0, /* todo_flags_start */
7580 TODO_rebuild_alias
, /* todo_flags_finish */
7583 class pass_build_alias
: public gimple_opt_pass
7586 pass_build_alias (gcc::context
*ctxt
)
7587 : gimple_opt_pass (pass_data_build_alias
, ctxt
)
7590 /* opt_pass methods: */
7591 virtual bool gate (function
*) { return flag_tree_pta
; }
7593 }; // class pass_build_alias
7598 make_pass_build_alias (gcc::context
*ctxt
)
7600 return new pass_build_alias (ctxt
);
7603 /* A dummy pass to cause points-to information to be computed via
7604 TODO_rebuild_alias. */
7608 const pass_data pass_data_build_ealias
=
7610 GIMPLE_PASS
, /* type */
7611 "ealias", /* name */
7612 OPTGROUP_NONE
, /* optinfo_flags */
7613 TV_NONE
, /* tv_id */
7614 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7615 0, /* properties_provided */
7616 0, /* properties_destroyed */
7617 0, /* todo_flags_start */
7618 TODO_rebuild_alias
, /* todo_flags_finish */
7621 class pass_build_ealias
: public gimple_opt_pass
7624 pass_build_ealias (gcc::context
*ctxt
)
7625 : gimple_opt_pass (pass_data_build_ealias
, ctxt
)
7628 /* opt_pass methods: */
7629 virtual bool gate (function
*) { return flag_tree_pta
; }
7631 }; // class pass_build_ealias
7636 make_pass_build_ealias (gcc::context
*ctxt
)
7638 return new pass_build_ealias (ctxt
);
7642 /* IPA PTA solutions for ESCAPED. */
7643 struct pt_solution ipa_escaped_pt
7644 = { true, false, false, false, false,
7645 false, false, false, false, false, NULL
};
7647 /* Associate node with varinfo DATA. Worker for
7648 cgraph_for_symbol_thunks_and_aliases. */
7650 associate_varinfo_to_alias (struct cgraph_node
*node
, void *data
)
7653 || (node
->thunk
.thunk_p
7654 && ! node
->global
.inlined_to
))
7656 insert_vi_for_tree (node
->decl
, (varinfo_t
)data
);
7660 /* Dump varinfo VI to FILE. */
7663 dump_varinfo (FILE *file
, varinfo_t vi
)
7668 fprintf (file
, "%u: %s\n", vi
->id
, vi
->name
);
7670 const char *sep
= " ";
7671 if (vi
->is_artificial_var
)
7672 fprintf (file
, "%sartificial", sep
);
7673 if (vi
->is_special_var
)
7674 fprintf (file
, "%sspecial", sep
);
7675 if (vi
->is_unknown_size_var
)
7676 fprintf (file
, "%sunknown-size", sep
);
7677 if (vi
->is_full_var
)
7678 fprintf (file
, "%sfull", sep
);
7679 if (vi
->is_heap_var
)
7680 fprintf (file
, "%sheap", sep
);
7681 if (vi
->may_have_pointers
)
7682 fprintf (file
, "%smay-have-pointers", sep
);
7683 if (vi
->only_restrict_pointers
)
7684 fprintf (file
, "%sonly-restrict-pointers", sep
);
7685 if (vi
->is_restrict_var
)
7686 fprintf (file
, "%sis-restrict-var", sep
);
7687 if (vi
->is_global_var
)
7688 fprintf (file
, "%sglobal", sep
);
7689 if (vi
->is_ipa_escape_point
)
7690 fprintf (file
, "%sipa-escape-point", sep
);
7692 fprintf (file
, "%sfn-info", sep
);
7694 fprintf (file
, "%srestrict-uid:%u", sep
, vi
->ruid
);
7696 fprintf (file
, "%snext:%u", sep
, vi
->next
);
7697 if (vi
->head
!= vi
->id
)
7698 fprintf (file
, "%shead:%u", sep
, vi
->head
);
7700 fprintf (file
, "%soffset:" HOST_WIDE_INT_PRINT_DEC
, sep
, vi
->offset
);
7701 if (vi
->size
!= ~(unsigned HOST_WIDE_INT
)0)
7702 fprintf (file
, "%ssize:" HOST_WIDE_INT_PRINT_DEC
, sep
, vi
->size
);
7703 if (vi
->fullsize
!= ~(unsigned HOST_WIDE_INT
)0
7704 && vi
->fullsize
!= vi
->size
)
7705 fprintf (file
, "%sfullsize:" HOST_WIDE_INT_PRINT_DEC
, sep
,
7707 fprintf (file
, "\n");
7709 if (vi
->solution
&& !bitmap_empty_p (vi
->solution
))
7713 fprintf (file
, " solution: {");
7714 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
7715 fprintf (file
, " %u", i
);
7716 fprintf (file
, " }\n");
7719 if (vi
->oldsolution
&& !bitmap_empty_p (vi
->oldsolution
)
7720 && !bitmap_equal_p (vi
->solution
, vi
->oldsolution
))
7724 fprintf (file
, " oldsolution: {");
7725 EXECUTE_IF_SET_IN_BITMAP (vi
->oldsolution
, 0, i
, bi
)
7726 fprintf (file
, " %u", i
);
7727 fprintf (file
, " }\n");
7731 /* Dump varinfo VI to stderr. */
7734 debug_varinfo (varinfo_t vi
)
7736 dump_varinfo (stderr
, vi
);
7739 /* Dump varmap to FILE. */
7742 dump_varmap (FILE *file
)
7744 if (varmap
.length () == 0)
7747 fprintf (file
, "variables:\n");
7749 for (unsigned int i
= 0; i
< varmap
.length (); ++i
)
7751 varinfo_t vi
= get_varinfo (i
);
7752 dump_varinfo (file
, vi
);
7755 fprintf (file
, "\n");
7758 /* Dump varmap to stderr. */
7763 dump_varmap (stderr
);
7766 /* Compute whether node is refered to non-locally. Worker for
7767 cgraph_for_symbol_thunks_and_aliases. */
7769 refered_from_nonlocal_fn (struct cgraph_node
*node
, void *data
)
7771 bool *nonlocal_p
= (bool *)data
;
7772 *nonlocal_p
|= (node
->used_from_other_partition
7773 || node
->externally_visible
7774 || node
->force_output
);
7778 /* Same for varpool nodes. */
7780 refered_from_nonlocal_var (struct varpool_node
*node
, void *data
)
7782 bool *nonlocal_p
= (bool *)data
;
7783 *nonlocal_p
|= (node
->used_from_other_partition
7784 || node
->externally_visible
7785 || node
->force_output
);
7789 /* Execute the driver for IPA PTA. */
7791 ipa_pta_execute (void)
7793 struct cgraph_node
*node
;
7795 unsigned int from
= 0;
7801 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7803 symtab_node::dump_table (dump_file
);
7804 fprintf (dump_file
, "\n");
7809 fprintf (dump_file
, "Generating generic constraints\n\n");
7810 dump_constraints (dump_file
, from
);
7811 fprintf (dump_file
, "\n");
7812 from
= constraints
.length ();
7815 /* Build the constraints. */
7816 FOR_EACH_DEFINED_FUNCTION (node
)
7819 /* Nodes without a body are not interesting. Especially do not
7820 visit clones at this point for now - we get duplicate decls
7821 there for inline clones at least. */
7822 if (!node
->has_gimple_body_p () || node
->global
.inlined_to
)
7826 gcc_assert (!node
->clone_of
);
7828 /* For externally visible or attribute used annotated functions use
7829 local constraints for their arguments.
7830 For local functions we see all callers and thus do not need initial
7831 constraints for parameters. */
7832 bool nonlocal_p
= (node
->used_from_other_partition
7833 || node
->externally_visible
7834 || node
->force_output
);
7835 node
->call_for_symbol_thunks_and_aliases (refered_from_nonlocal_fn
,
7838 vi
= create_function_info_for (node
->decl
,
7839 alias_get_name (node
->decl
), false,
7842 && from
!= constraints
.length ())
7845 "Generating intial constraints for %s", node
->name ());
7846 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
7847 fprintf (dump_file
, " (%s)",
7849 (DECL_ASSEMBLER_NAME (node
->decl
)));
7850 fprintf (dump_file
, "\n\n");
7851 dump_constraints (dump_file
, from
);
7852 fprintf (dump_file
, "\n");
7854 from
= constraints
.length ();
7857 node
->call_for_symbol_thunks_and_aliases
7858 (associate_varinfo_to_alias
, vi
, true);
7861 /* Create constraints for global variables and their initializers. */
7862 FOR_EACH_VARIABLE (var
)
7864 if (var
->alias
&& var
->analyzed
)
7867 varinfo_t vi
= get_vi_for_tree (var
->decl
);
7869 /* For the purpose of IPA PTA unit-local globals are not
7871 bool nonlocal_p
= (var
->used_from_other_partition
7872 || var
->externally_visible
7873 || var
->force_output
);
7874 var
->call_for_symbol_and_aliases (refered_from_nonlocal_var
,
7877 vi
->is_ipa_escape_point
= true;
7881 && from
!= constraints
.length ())
7884 "Generating constraints for global initializers\n\n");
7885 dump_constraints (dump_file
, from
);
7886 fprintf (dump_file
, "\n");
7887 from
= constraints
.length ();
7890 FOR_EACH_DEFINED_FUNCTION (node
)
7892 struct function
*func
;
7895 /* Nodes without a body are not interesting. */
7896 if (!node
->has_gimple_body_p () || node
->clone_of
)
7902 "Generating constraints for %s", node
->name ());
7903 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
7904 fprintf (dump_file
, " (%s)",
7906 (DECL_ASSEMBLER_NAME (node
->decl
)));
7907 fprintf (dump_file
, "\n");
7910 func
= DECL_STRUCT_FUNCTION (node
->decl
);
7911 gcc_assert (cfun
== NULL
);
7913 /* Build constriants for the function body. */
7914 FOR_EACH_BB_FN (bb
, func
)
7916 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7919 gphi
*phi
= gsi
.phi ();
7921 if (! virtual_operand_p (gimple_phi_result (phi
)))
7922 find_func_aliases (func
, phi
);
7925 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
7928 gimple
*stmt
= gsi_stmt (gsi
);
7930 find_func_aliases (func
, stmt
);
7931 find_func_clobbers (func
, stmt
);
7937 fprintf (dump_file
, "\n");
7938 dump_constraints (dump_file
, from
);
7939 fprintf (dump_file
, "\n");
7940 from
= constraints
.length ();
7944 /* From the constraints compute the points-to sets. */
7945 solve_constraints ();
7947 /* Compute the global points-to sets for ESCAPED.
7948 ??? Note that the computed escape set is not correct
7949 for the whole unit as we fail to consider graph edges to
7950 externally visible functions. */
7951 ipa_escaped_pt
= find_what_var_points_to (NULL
, get_varinfo (escaped_id
));
7953 /* Make sure the ESCAPED solution (which is used as placeholder in
7954 other solutions) does not reference itself. This simplifies
7955 points-to solution queries. */
7956 ipa_escaped_pt
.ipa_escaped
= 0;
7958 /* Assign the points-to sets to the SSA names in the unit. */
7959 FOR_EACH_DEFINED_FUNCTION (node
)
7962 struct function
*fn
;
7966 /* Nodes without a body are not interesting. */
7967 if (!node
->has_gimple_body_p () || node
->clone_of
)
7970 fn
= DECL_STRUCT_FUNCTION (node
->decl
);
7972 /* Compute the points-to sets for pointer SSA_NAMEs. */
7973 FOR_EACH_VEC_ELT (*fn
->gimple_df
->ssa_names
, i
, ptr
)
7976 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
7977 find_what_p_points_to (node
->decl
, ptr
);
7980 /* Compute the call-use and call-clobber sets for indirect calls
7981 and calls to external functions. */
7982 FOR_EACH_BB_FN (bb
, fn
)
7984 gimple_stmt_iterator gsi
;
7986 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7989 struct pt_solution
*pt
;
7993 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
7997 /* Handle direct calls to functions with body. */
7998 decl
= gimple_call_fndecl (stmt
);
8001 tree called_decl
= NULL_TREE
;
8002 if (gimple_call_builtin_p (stmt
, BUILT_IN_GOMP_PARALLEL
))
8003 called_decl
= TREE_OPERAND (gimple_call_arg (stmt
, 0), 0);
8004 else if (gimple_call_builtin_p (stmt
, BUILT_IN_GOACC_PARALLEL
))
8005 called_decl
= TREE_OPERAND (gimple_call_arg (stmt
, 1), 0);
8007 if (called_decl
!= NULL_TREE
8008 && !fndecl_maybe_in_other_partition (called_decl
))
8013 && (fi
= lookup_vi_for_tree (decl
))
8016 *gimple_call_clobber_set (stmt
)
8017 = find_what_var_points_to
8018 (node
->decl
, first_vi_for_offset (fi
, fi_clobbers
));
8019 *gimple_call_use_set (stmt
)
8020 = find_what_var_points_to
8021 (node
->decl
, first_vi_for_offset (fi
, fi_uses
));
8023 /* Handle direct calls to external functions. */
8026 pt
= gimple_call_use_set (stmt
);
8027 if (gimple_call_flags (stmt
) & ECF_CONST
)
8028 memset (pt
, 0, sizeof (struct pt_solution
));
8029 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
8031 *pt
= find_what_var_points_to (node
->decl
, vi
);
8032 /* Escaped (and thus nonlocal) variables are always
8033 implicitly used by calls. */
8034 /* ??? ESCAPED can be empty even though NONLOCAL
8037 pt
->ipa_escaped
= 1;
8041 /* If there is nothing special about this call then
8042 we have made everything that is used also escape. */
8043 *pt
= ipa_escaped_pt
;
8047 pt
= gimple_call_clobber_set (stmt
);
8048 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
8049 memset (pt
, 0, sizeof (struct pt_solution
));
8050 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
8052 *pt
= find_what_var_points_to (node
->decl
, vi
);
8053 /* Escaped (and thus nonlocal) variables are always
8054 implicitly clobbered by calls. */
8055 /* ??? ESCAPED can be empty even though NONLOCAL
8058 pt
->ipa_escaped
= 1;
8062 /* If there is nothing special about this call then
8063 we have made everything that is used also escape. */
8064 *pt
= ipa_escaped_pt
;
8068 /* Handle indirect calls. */
8070 && (fi
= get_fi_for_callee (stmt
)))
8072 /* We need to accumulate all clobbers/uses of all possible
8074 fi
= get_varinfo (find (fi
->id
));
8075 /* If we cannot constrain the set of functions we'll end up
8076 calling we end up using/clobbering everything. */
8077 if (bitmap_bit_p (fi
->solution
, anything_id
)
8078 || bitmap_bit_p (fi
->solution
, nonlocal_id
)
8079 || bitmap_bit_p (fi
->solution
, escaped_id
))
8081 pt_solution_reset (gimple_call_clobber_set (stmt
));
8082 pt_solution_reset (gimple_call_use_set (stmt
));
8088 struct pt_solution
*uses
, *clobbers
;
8090 uses
= gimple_call_use_set (stmt
);
8091 clobbers
= gimple_call_clobber_set (stmt
);
8092 memset (uses
, 0, sizeof (struct pt_solution
));
8093 memset (clobbers
, 0, sizeof (struct pt_solution
));
8094 EXECUTE_IF_SET_IN_BITMAP (fi
->solution
, 0, i
, bi
)
8096 struct pt_solution sol
;
8098 vi
= get_varinfo (i
);
8099 if (!vi
->is_fn_info
)
8101 /* ??? We could be more precise here? */
8103 uses
->ipa_escaped
= 1;
8104 clobbers
->nonlocal
= 1;
8105 clobbers
->ipa_escaped
= 1;
8109 if (!uses
->anything
)
8111 sol
= find_what_var_points_to
8113 first_vi_for_offset (vi
, fi_uses
));
8114 pt_solution_ior_into (uses
, &sol
);
8116 if (!clobbers
->anything
)
8118 sol
= find_what_var_points_to
8120 first_vi_for_offset (vi
, fi_clobbers
));
8121 pt_solution_ior_into (clobbers
, &sol
);
8129 fn
->gimple_df
->ipa_pta
= true;
8131 /* We have to re-set the final-solution cache after each function
8132 because what is a "global" is dependent on function context. */
8133 final_solutions
->empty ();
8134 obstack_free (&final_solutions_obstack
, NULL
);
8135 gcc_obstack_init (&final_solutions_obstack
);
8138 delete_points_to_sets ();
8147 const pass_data pass_data_ipa_pta
=
8149 SIMPLE_IPA_PASS
, /* type */
8151 OPTGROUP_NONE
, /* optinfo_flags */
8152 TV_IPA_PTA
, /* tv_id */
8153 0, /* properties_required */
8154 0, /* properties_provided */
8155 0, /* properties_destroyed */
8156 0, /* todo_flags_start */
8157 0, /* todo_flags_finish */
8160 class pass_ipa_pta
: public simple_ipa_opt_pass
8163 pass_ipa_pta (gcc::context
*ctxt
)
8164 : simple_ipa_opt_pass (pass_data_ipa_pta
, ctxt
)
8167 /* opt_pass methods: */
8168 virtual bool gate (function
*)
8172 /* Don't bother doing anything if the program has errors. */
8176 opt_pass
* clone () { return new pass_ipa_pta (m_ctxt
); }
8178 virtual unsigned int execute (function
*) { return ipa_pta_execute (); }
8180 }; // class pass_ipa_pta
8184 simple_ipa_opt_pass
*
8185 make_pass_ipa_pta (gcc::context
*ctxt
)
8187 return new pass_ipa_pta (ctxt
);