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
;
2834 if (TREE_CODE (decl
) == SSA_NAME
)
2836 res
= get_name (decl
);
2838 temp
= xasprintf ("%s_%u", res
, SSA_NAME_VERSION (decl
));
2840 temp
= xasprintf ("_%u", SSA_NAME_VERSION (decl
));
2841 res
= ggc_strdup (temp
);
2844 else if (DECL_P (decl
))
2846 if (DECL_ASSEMBLER_NAME_SET_P (decl
))
2847 res
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
2850 res
= get_name (decl
);
2853 temp
= xasprintf ("D.%u", DECL_UID (decl
));
2854 res
= ggc_strdup (temp
);
2865 /* Find the variable id for tree T in the map.
2866 If T doesn't exist in the map, create an entry for it and return it. */
2869 get_vi_for_tree (tree t
)
2871 varinfo_t
*slot
= vi_for_tree
->get (t
);
2874 unsigned int id
= create_variable_info_for (t
, alias_get_name (t
), false);
2875 return get_varinfo (id
);
2881 /* Get a scalar constraint expression for a new temporary variable. */
2883 static struct constraint_expr
2884 new_scalar_tmp_constraint_exp (const char *name
, bool add_id
)
2886 struct constraint_expr tmp
;
2889 vi
= new_var_info (NULL_TREE
, name
, add_id
);
2893 vi
->is_full_var
= 1;
2902 /* Get a constraint expression vector from an SSA_VAR_P node.
2903 If address_p is true, the result will be taken its address of. */
2906 get_constraint_for_ssa_var (tree t
, vec
<ce_s
> *results
, bool address_p
)
2908 struct constraint_expr cexpr
;
2911 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2912 gcc_assert (TREE_CODE (t
) == SSA_NAME
|| DECL_P (t
));
2914 /* For parameters, get at the points-to set for the actual parm
2916 if (TREE_CODE (t
) == SSA_NAME
2917 && SSA_NAME_IS_DEFAULT_DEF (t
)
2918 && (TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2919 || TREE_CODE (SSA_NAME_VAR (t
)) == RESULT_DECL
))
2921 get_constraint_for_ssa_var (SSA_NAME_VAR (t
), results
, address_p
);
2925 /* For global variables resort to the alias target. */
2926 if (VAR_P (t
) && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
2928 varpool_node
*node
= varpool_node::get (t
);
2929 if (node
&& node
->alias
&& node
->analyzed
)
2931 node
= node
->ultimate_alias_target ();
2932 /* Canonicalize the PT uid of all aliases to the ultimate target.
2933 ??? Hopefully the set of aliases can't change in a way that
2934 changes the ultimate alias target. */
2935 gcc_assert ((! DECL_PT_UID_SET_P (node
->decl
)
2936 || DECL_PT_UID (node
->decl
) == DECL_UID (node
->decl
))
2937 && (! DECL_PT_UID_SET_P (t
)
2938 || DECL_PT_UID (t
) == DECL_UID (node
->decl
)));
2939 DECL_PT_UID (t
) = DECL_UID (node
->decl
);
2943 /* If this is decl may bind to NULL note that. */
2945 && (! node
|| ! node
->nonzero_address ()))
2947 cexpr
.var
= nothing_id
;
2948 cexpr
.type
= SCALAR
;
2950 results
->safe_push (cexpr
);
2954 vi
= get_vi_for_tree (t
);
2956 cexpr
.type
= SCALAR
;
2959 /* If we are not taking the address of the constraint expr, add all
2960 sub-fiels of the variable as well. */
2962 && !vi
->is_full_var
)
2964 for (; vi
; vi
= vi_next (vi
))
2967 results
->safe_push (cexpr
);
2972 results
->safe_push (cexpr
);
2975 /* Process constraint T, performing various simplifications and then
2976 adding it to our list of overall constraints. */
2979 process_constraint (constraint_t t
)
2981 struct constraint_expr rhs
= t
->rhs
;
2982 struct constraint_expr lhs
= t
->lhs
;
2984 gcc_assert (rhs
.var
< varmap
.length ());
2985 gcc_assert (lhs
.var
< varmap
.length ());
2987 /* If we didn't get any useful constraint from the lhs we get
2988 &ANYTHING as fallback from get_constraint_for. Deal with
2989 it here by turning it into *ANYTHING. */
2990 if (lhs
.type
== ADDRESSOF
2991 && lhs
.var
== anything_id
)
2994 /* ADDRESSOF on the lhs is invalid. */
2995 gcc_assert (lhs
.type
!= ADDRESSOF
);
2997 /* We shouldn't add constraints from things that cannot have pointers.
2998 It's not completely trivial to avoid in the callers, so do it here. */
2999 if (rhs
.type
!= ADDRESSOF
3000 && !get_varinfo (rhs
.var
)->may_have_pointers
)
3003 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3004 if (!get_varinfo (lhs
.var
)->may_have_pointers
)
3007 /* This can happen in our IR with things like n->a = *p */
3008 if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
3010 /* Split into tmp = *rhs, *lhs = tmp */
3011 struct constraint_expr tmplhs
;
3012 tmplhs
= new_scalar_tmp_constraint_exp ("doubledereftmp", true);
3013 process_constraint (new_constraint (tmplhs
, rhs
));
3014 process_constraint (new_constraint (lhs
, tmplhs
));
3016 else if ((rhs
.type
!= SCALAR
|| rhs
.offset
!= 0) && lhs
.type
== DEREF
)
3018 /* Split into tmp = &rhs, *lhs = tmp */
3019 struct constraint_expr tmplhs
;
3020 tmplhs
= new_scalar_tmp_constraint_exp ("derefaddrtmp", true);
3021 process_constraint (new_constraint (tmplhs
, rhs
));
3022 process_constraint (new_constraint (lhs
, tmplhs
));
3026 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
3027 constraints
.safe_push (t
);
3032 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3035 static HOST_WIDE_INT
3036 bitpos_of_field (const tree fdecl
)
3038 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl
))
3039 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl
)))
3042 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl
)) * BITS_PER_UNIT
3043 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl
)));
3047 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3048 resulting constraint expressions in *RESULTS. */
3051 get_constraint_for_ptr_offset (tree ptr
, tree offset
,
3054 struct constraint_expr c
;
3056 HOST_WIDE_INT rhsoffset
;
3058 /* If we do not do field-sensitive PTA adding offsets to pointers
3059 does not change the points-to solution. */
3060 if (!use_field_sensitive
)
3062 get_constraint_for_rhs (ptr
, results
);
3066 /* If the offset is not a non-negative integer constant that fits
3067 in a HOST_WIDE_INT, we have to fall back to a conservative
3068 solution which includes all sub-fields of all pointed-to
3069 variables of ptr. */
3070 if (offset
== NULL_TREE
3071 || TREE_CODE (offset
) != INTEGER_CST
)
3072 rhsoffset
= UNKNOWN_OFFSET
;
3075 /* Sign-extend the offset. */
3076 offset_int soffset
= offset_int::from (offset
, SIGNED
);
3077 if (!wi::fits_shwi_p (soffset
))
3078 rhsoffset
= UNKNOWN_OFFSET
;
3081 /* Make sure the bit-offset also fits. */
3082 HOST_WIDE_INT rhsunitoffset
= soffset
.to_shwi ();
3083 rhsoffset
= rhsunitoffset
* (unsigned HOST_WIDE_INT
) BITS_PER_UNIT
;
3084 if (rhsunitoffset
!= rhsoffset
/ BITS_PER_UNIT
)
3085 rhsoffset
= UNKNOWN_OFFSET
;
3089 get_constraint_for_rhs (ptr
, results
);
3093 /* As we are eventually appending to the solution do not use
3094 vec::iterate here. */
3095 n
= results
->length ();
3096 for (j
= 0; j
< n
; j
++)
3100 curr
= get_varinfo (c
.var
);
3102 if (c
.type
== ADDRESSOF
3103 /* If this varinfo represents a full variable just use it. */
3104 && curr
->is_full_var
)
3106 else if (c
.type
== ADDRESSOF
3107 /* If we do not know the offset add all subfields. */
3108 && rhsoffset
== UNKNOWN_OFFSET
)
3110 varinfo_t temp
= get_varinfo (curr
->head
);
3113 struct constraint_expr c2
;
3115 c2
.type
= ADDRESSOF
;
3117 if (c2
.var
!= c
.var
)
3118 results
->safe_push (c2
);
3119 temp
= vi_next (temp
);
3123 else if (c
.type
== ADDRESSOF
)
3126 unsigned HOST_WIDE_INT offset
= curr
->offset
+ rhsoffset
;
3128 /* If curr->offset + rhsoffset is less than zero adjust it. */
3130 && curr
->offset
< offset
)
3133 /* We have to include all fields that overlap the current
3134 field shifted by rhsoffset. And we include at least
3135 the last or the first field of the variable to represent
3136 reachability of off-bound addresses, in particular &object + 1,
3137 conservatively correct. */
3138 temp
= first_or_preceding_vi_for_offset (curr
, offset
);
3141 temp
= vi_next (temp
);
3143 && temp
->offset
< offset
+ curr
->size
)
3145 struct constraint_expr c2
;
3147 c2
.type
= ADDRESSOF
;
3149 results
->safe_push (c2
);
3150 temp
= vi_next (temp
);
3153 else if (c
.type
== SCALAR
)
3155 gcc_assert (c
.offset
== 0);
3156 c
.offset
= rhsoffset
;
3159 /* We shouldn't get any DEREFs here. */
3167 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3168 If address_p is true the result will be taken its address of.
3169 If lhs_p is true then the constraint expression is assumed to be used
3173 get_constraint_for_component_ref (tree t
, vec
<ce_s
> *results
,
3174 bool address_p
, bool lhs_p
)
3177 HOST_WIDE_INT bitsize
= -1;
3178 HOST_WIDE_INT bitmaxsize
= -1;
3179 HOST_WIDE_INT bitpos
;
3183 /* Some people like to do cute things like take the address of
3186 while (handled_component_p (forzero
)
3187 || INDIRECT_REF_P (forzero
)
3188 || TREE_CODE (forzero
) == MEM_REF
)
3189 forzero
= TREE_OPERAND (forzero
, 0);
3191 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
3193 struct constraint_expr temp
;
3196 temp
.var
= integer_id
;
3198 results
->safe_push (temp
);
3202 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
, &reverse
);
3204 /* We can end up here for component references on a
3205 VIEW_CONVERT_EXPR <>(&foobar) or things like a
3206 BIT_FIELD_REF <&MEM[(void *)&b + 4B], ...>. So for
3207 symbolic constants simply give up. */
3208 if (TREE_CODE (t
) == ADDR_EXPR
)
3210 constraint_expr result
;
3211 result
.type
= SCALAR
;
3212 result
.var
= anything_id
;
3214 results
->safe_push (result
);
3218 /* Pretend to take the address of the base, we'll take care of
3219 adding the required subset of sub-fields below. */
3220 get_constraint_for_1 (t
, results
, true, lhs_p
);
3221 /* Strip off nothing_id. */
3222 if (results
->length () == 2)
3224 gcc_assert ((*results
)[0].var
== nothing_id
);
3225 results
->unordered_remove (0);
3227 gcc_assert (results
->length () == 1);
3228 struct constraint_expr
&result
= results
->last ();
3230 if (result
.type
== SCALAR
3231 && get_varinfo (result
.var
)->is_full_var
)
3232 /* For single-field vars do not bother about the offset. */
3234 else if (result
.type
== SCALAR
)
3236 /* In languages like C, you can access one past the end of an
3237 array. You aren't allowed to dereference it, so we can
3238 ignore this constraint. When we handle pointer subtraction,
3239 we may have to do something cute here. */
3241 if ((unsigned HOST_WIDE_INT
)bitpos
< get_varinfo (result
.var
)->fullsize
3244 /* It's also not true that the constraint will actually start at the
3245 right offset, it may start in some padding. We only care about
3246 setting the constraint to the first actual field it touches, so
3248 struct constraint_expr cexpr
= result
;
3252 for (curr
= get_varinfo (cexpr
.var
); curr
; curr
= vi_next (curr
))
3254 if (ranges_overlap_p (curr
->offset
, curr
->size
,
3255 bitpos
, bitmaxsize
))
3257 cexpr
.var
= curr
->id
;
3258 results
->safe_push (cexpr
);
3263 /* If we are going to take the address of this field then
3264 to be able to compute reachability correctly add at least
3265 the last field of the variable. */
3266 if (address_p
&& results
->length () == 0)
3268 curr
= get_varinfo (cexpr
.var
);
3269 while (curr
->next
!= 0)
3270 curr
= vi_next (curr
);
3271 cexpr
.var
= curr
->id
;
3272 results
->safe_push (cexpr
);
3274 else if (results
->length () == 0)
3275 /* Assert that we found *some* field there. The user couldn't be
3276 accessing *only* padding. */
3277 /* Still the user could access one past the end of an array
3278 embedded in a struct resulting in accessing *only* padding. */
3279 /* Or accessing only padding via type-punning to a type
3280 that has a filed just in padding space. */
3282 cexpr
.type
= SCALAR
;
3283 cexpr
.var
= anything_id
;
3285 results
->safe_push (cexpr
);
3288 else if (bitmaxsize
== 0)
3290 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3291 fprintf (dump_file
, "Access to zero-sized part of variable, "
3295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3296 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
3298 else if (result
.type
== DEREF
)
3300 /* If we do not know exactly where the access goes say so. Note
3301 that only for non-structure accesses we know that we access
3302 at most one subfiled of any variable. */
3304 || bitsize
!= bitmaxsize
3305 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t
))
3306 || result
.offset
== UNKNOWN_OFFSET
)
3307 result
.offset
= UNKNOWN_OFFSET
;
3309 result
.offset
+= bitpos
;
3311 else if (result
.type
== ADDRESSOF
)
3313 /* We can end up here for component references on constants like
3314 VIEW_CONVERT_EXPR <>({ 0, 1, 2, 3 })[i]. */
3315 result
.type
= SCALAR
;
3316 result
.var
= anything_id
;
3324 /* Dereference the constraint expression CONS, and return the result.
3325 DEREF (ADDRESSOF) = SCALAR
3326 DEREF (SCALAR) = DEREF
3327 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3328 This is needed so that we can handle dereferencing DEREF constraints. */
3331 do_deref (vec
<ce_s
> *constraints
)
3333 struct constraint_expr
*c
;
3336 FOR_EACH_VEC_ELT (*constraints
, i
, c
)
3338 if (c
->type
== SCALAR
)
3340 else if (c
->type
== ADDRESSOF
)
3342 else if (c
->type
== DEREF
)
3344 struct constraint_expr tmplhs
;
3345 tmplhs
= new_scalar_tmp_constraint_exp ("dereftmp", true);
3346 process_constraint (new_constraint (tmplhs
, *c
));
3347 c
->var
= tmplhs
.var
;
3354 /* Given a tree T, return the constraint expression for taking the
3358 get_constraint_for_address_of (tree t
, vec
<ce_s
> *results
)
3360 struct constraint_expr
*c
;
3363 get_constraint_for_1 (t
, results
, true, true);
3365 FOR_EACH_VEC_ELT (*results
, i
, c
)
3367 if (c
->type
== DEREF
)
3370 c
->type
= ADDRESSOF
;
3374 /* Given a tree T, return the constraint expression for it. */
3377 get_constraint_for_1 (tree t
, vec
<ce_s
> *results
, bool address_p
,
3380 struct constraint_expr temp
;
3382 /* x = integer is all glommed to a single variable, which doesn't
3383 point to anything by itself. That is, of course, unless it is an
3384 integer constant being treated as a pointer, in which case, we
3385 will return that this is really the addressof anything. This
3386 happens below, since it will fall into the default case. The only
3387 case we know something about an integer treated like a pointer is
3388 when it is the NULL pointer, and then we just say it points to
3391 Do not do that if -fno-delete-null-pointer-checks though, because
3392 in that case *NULL does not fail, so it _should_ alias *anything.
3393 It is not worth adding a new option or renaming the existing one,
3394 since this case is relatively obscure. */
3395 if ((TREE_CODE (t
) == INTEGER_CST
3396 && integer_zerop (t
))
3397 /* The only valid CONSTRUCTORs in gimple with pointer typed
3398 elements are zero-initializer. But in IPA mode we also
3399 process global initializers, so verify at least. */
3400 || (TREE_CODE (t
) == CONSTRUCTOR
3401 && CONSTRUCTOR_NELTS (t
) == 0))
3403 if (flag_delete_null_pointer_checks
)
3404 temp
.var
= nothing_id
;
3406 temp
.var
= nonlocal_id
;
3407 temp
.type
= ADDRESSOF
;
3409 results
->safe_push (temp
);
3413 /* String constants are read-only, ideally we'd have a CONST_DECL
3415 if (TREE_CODE (t
) == STRING_CST
)
3417 temp
.var
= string_id
;
3420 results
->safe_push (temp
);
3424 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
3426 case tcc_expression
:
3428 switch (TREE_CODE (t
))
3431 get_constraint_for_address_of (TREE_OPERAND (t
, 0), results
);
3439 switch (TREE_CODE (t
))
3443 struct constraint_expr cs
;
3445 get_constraint_for_ptr_offset (TREE_OPERAND (t
, 0),
3446 TREE_OPERAND (t
, 1), results
);
3449 /* If we are not taking the address then make sure to process
3450 all subvariables we might access. */
3454 cs
= results
->last ();
3455 if (cs
.type
== DEREF
3456 && type_can_have_subvars (TREE_TYPE (t
)))
3458 /* For dereferences this means we have to defer it
3460 results
->last ().offset
= UNKNOWN_OFFSET
;
3463 if (cs
.type
!= SCALAR
)
3466 vi
= get_varinfo (cs
.var
);
3467 curr
= vi_next (vi
);
3468 if (!vi
->is_full_var
3471 unsigned HOST_WIDE_INT size
;
3472 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t
))))
3473 size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t
)));
3476 for (; curr
; curr
= vi_next (curr
))
3478 if (curr
->offset
- vi
->offset
< size
)
3481 results
->safe_push (cs
);
3490 case ARRAY_RANGE_REF
:
3495 get_constraint_for_component_ref (t
, results
, address_p
, lhs_p
);
3497 case VIEW_CONVERT_EXPR
:
3498 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, address_p
,
3501 /* We are missing handling for TARGET_MEM_REF here. */
3506 case tcc_exceptional
:
3508 switch (TREE_CODE (t
))
3512 get_constraint_for_ssa_var (t
, results
, address_p
);
3520 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t
), i
, val
)
3522 struct constraint_expr
*rhsp
;
3524 get_constraint_for_1 (val
, &tmp
, address_p
, lhs_p
);
3525 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
3526 results
->safe_push (*rhsp
);
3529 /* We do not know whether the constructor was complete,
3530 so technically we have to add &NOTHING or &ANYTHING
3531 like we do for an empty constructor as well. */
3538 case tcc_declaration
:
3540 get_constraint_for_ssa_var (t
, results
, address_p
);
3545 /* We cannot refer to automatic variables through constants. */
3546 temp
.type
= ADDRESSOF
;
3547 temp
.var
= nonlocal_id
;
3549 results
->safe_push (temp
);
3555 /* The default fallback is a constraint from anything. */
3556 temp
.type
= ADDRESSOF
;
3557 temp
.var
= anything_id
;
3559 results
->safe_push (temp
);
3562 /* Given a gimple tree T, return the constraint expression vector for it. */
3565 get_constraint_for (tree t
, vec
<ce_s
> *results
)
3567 gcc_assert (results
->length () == 0);
3569 get_constraint_for_1 (t
, results
, false, true);
3572 /* Given a gimple tree T, return the constraint expression vector for it
3573 to be used as the rhs of a constraint. */
3576 get_constraint_for_rhs (tree t
, vec
<ce_s
> *results
)
3578 gcc_assert (results
->length () == 0);
3580 get_constraint_for_1 (t
, results
, false, false);
3584 /* Efficiently generates constraints from all entries in *RHSC to all
3585 entries in *LHSC. */
3588 process_all_all_constraints (vec
<ce_s
> lhsc
,
3591 struct constraint_expr
*lhsp
, *rhsp
;
3594 if (lhsc
.length () <= 1 || rhsc
.length () <= 1)
3596 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3597 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
3598 process_constraint (new_constraint (*lhsp
, *rhsp
));
3602 struct constraint_expr tmp
;
3603 tmp
= new_scalar_tmp_constraint_exp ("allalltmp", true);
3604 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
3605 process_constraint (new_constraint (tmp
, *rhsp
));
3606 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3607 process_constraint (new_constraint (*lhsp
, tmp
));
3611 /* Handle aggregate copies by expanding into copies of the respective
3612 fields of the structures. */
3615 do_structure_copy (tree lhsop
, tree rhsop
)
3617 struct constraint_expr
*lhsp
, *rhsp
;
3618 auto_vec
<ce_s
> lhsc
;
3619 auto_vec
<ce_s
> rhsc
;
3622 get_constraint_for (lhsop
, &lhsc
);
3623 get_constraint_for_rhs (rhsop
, &rhsc
);
3626 if (lhsp
->type
== DEREF
3627 || (lhsp
->type
== ADDRESSOF
&& lhsp
->var
== anything_id
)
3628 || rhsp
->type
== DEREF
)
3630 if (lhsp
->type
== DEREF
)
3632 gcc_assert (lhsc
.length () == 1);
3633 lhsp
->offset
= UNKNOWN_OFFSET
;
3635 if (rhsp
->type
== DEREF
)
3637 gcc_assert (rhsc
.length () == 1);
3638 rhsp
->offset
= UNKNOWN_OFFSET
;
3640 process_all_all_constraints (lhsc
, rhsc
);
3642 else if (lhsp
->type
== SCALAR
3643 && (rhsp
->type
== SCALAR
3644 || rhsp
->type
== ADDRESSOF
))
3646 HOST_WIDE_INT lhssize
, lhsmaxsize
, lhsoffset
;
3647 HOST_WIDE_INT rhssize
, rhsmaxsize
, rhsoffset
;
3650 get_ref_base_and_extent (lhsop
, &lhsoffset
, &lhssize
, &lhsmaxsize
,
3652 get_ref_base_and_extent (rhsop
, &rhsoffset
, &rhssize
, &rhsmaxsize
,
3654 for (j
= 0; lhsc
.iterate (j
, &lhsp
);)
3656 varinfo_t lhsv
, rhsv
;
3658 lhsv
= get_varinfo (lhsp
->var
);
3659 rhsv
= get_varinfo (rhsp
->var
);
3660 if (lhsv
->may_have_pointers
3661 && (lhsv
->is_full_var
3662 || rhsv
->is_full_var
3663 || ranges_overlap_p (lhsv
->offset
+ rhsoffset
, lhsv
->size
,
3664 rhsv
->offset
+ lhsoffset
, rhsv
->size
)))
3665 process_constraint (new_constraint (*lhsp
, *rhsp
));
3666 if (!rhsv
->is_full_var
3667 && (lhsv
->is_full_var
3668 || (lhsv
->offset
+ rhsoffset
+ lhsv
->size
3669 > rhsv
->offset
+ lhsoffset
+ rhsv
->size
)))
3672 if (k
>= rhsc
.length ())
3683 /* Create constraints ID = { rhsc }. */
3686 make_constraints_to (unsigned id
, vec
<ce_s
> rhsc
)
3688 struct constraint_expr
*c
;
3689 struct constraint_expr includes
;
3693 includes
.offset
= 0;
3694 includes
.type
= SCALAR
;
3696 FOR_EACH_VEC_ELT (rhsc
, j
, c
)
3697 process_constraint (new_constraint (includes
, *c
));
3700 /* Create a constraint ID = OP. */
3703 make_constraint_to (unsigned id
, tree op
)
3705 auto_vec
<ce_s
> rhsc
;
3706 get_constraint_for_rhs (op
, &rhsc
);
3707 make_constraints_to (id
, rhsc
);
3710 /* Create a constraint ID = &FROM. */
3713 make_constraint_from (varinfo_t vi
, int from
)
3715 struct constraint_expr lhs
, rhs
;
3723 rhs
.type
= ADDRESSOF
;
3724 process_constraint (new_constraint (lhs
, rhs
));
3727 /* Create a constraint ID = FROM. */
3730 make_copy_constraint (varinfo_t vi
, int from
)
3732 struct constraint_expr lhs
, rhs
;
3741 process_constraint (new_constraint (lhs
, rhs
));
3744 /* Make constraints necessary to make OP escape. */
3747 make_escape_constraint (tree op
)
3749 make_constraint_to (escaped_id
, op
);
3752 /* Add constraints to that the solution of VI is transitively closed. */
3755 make_transitive_closure_constraints (varinfo_t vi
)
3757 struct constraint_expr lhs
, rhs
;
3759 /* VAR = *(VAR + UNKNOWN); */
3765 rhs
.offset
= UNKNOWN_OFFSET
;
3766 process_constraint (new_constraint (lhs
, rhs
));
3769 /* Add constraints to that the solution of VI has all subvariables added. */
3772 make_any_offset_constraints (varinfo_t vi
)
3774 struct constraint_expr lhs
, rhs
;
3776 /* VAR = VAR + UNKNOWN; */
3782 rhs
.offset
= UNKNOWN_OFFSET
;
3783 process_constraint (new_constraint (lhs
, rhs
));
3786 /* Temporary storage for fake var decls. */
3787 struct obstack fake_var_decl_obstack
;
3789 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3792 build_fake_var_decl (tree type
)
3794 tree decl
= (tree
) XOBNEW (&fake_var_decl_obstack
, struct tree_var_decl
);
3795 memset (decl
, 0, sizeof (struct tree_var_decl
));
3796 TREE_SET_CODE (decl
, VAR_DECL
);
3797 TREE_TYPE (decl
) = type
;
3798 DECL_UID (decl
) = allocate_decl_uid ();
3799 SET_DECL_PT_UID (decl
, -1);
3800 layout_decl (decl
, 0);
3804 /* Create a new artificial heap variable with NAME.
3805 Return the created variable. */
3808 make_heapvar (const char *name
, bool add_id
)
3813 heapvar
= build_fake_var_decl (ptr_type_node
);
3814 DECL_EXTERNAL (heapvar
) = 1;
3816 vi
= new_var_info (heapvar
, name
, add_id
);
3817 vi
->is_artificial_var
= true;
3818 vi
->is_heap_var
= true;
3819 vi
->is_unknown_size_var
= true;
3823 vi
->is_full_var
= true;
3824 insert_vi_for_tree (heapvar
, vi
);
3829 /* Create a new artificial heap variable with NAME and make a
3830 constraint from it to LHS. Set flags according to a tag used
3831 for tracking restrict pointers. */
3834 make_constraint_from_restrict (varinfo_t lhs
, const char *name
, bool add_id
)
3836 varinfo_t vi
= make_heapvar (name
, add_id
);
3837 vi
->is_restrict_var
= 1;
3838 vi
->is_global_var
= 1;
3839 vi
->may_have_pointers
= 1;
3840 make_constraint_from (lhs
, vi
->id
);
3844 /* Create a new artificial heap variable with NAME and make a
3845 constraint from it to LHS. Set flags according to a tag used
3846 for tracking restrict pointers and make the artificial heap
3847 point to global memory. */
3850 make_constraint_from_global_restrict (varinfo_t lhs
, const char *name
,
3853 varinfo_t vi
= make_constraint_from_restrict (lhs
, name
, add_id
);
3854 make_copy_constraint (vi
, nonlocal_id
);
3858 /* In IPA mode there are varinfos for different aspects of reach
3859 function designator. One for the points-to set of the return
3860 value, one for the variables that are clobbered by the function,
3861 one for its uses and one for each parameter (including a single
3862 glob for remaining variadic arguments). */
3864 enum { fi_clobbers
= 1, fi_uses
= 2,
3865 fi_static_chain
= 3, fi_result
= 4, fi_parm_base
= 5 };
3867 /* Get a constraint for the requested part of a function designator FI
3868 when operating in IPA mode. */
3870 static struct constraint_expr
3871 get_function_part_constraint (varinfo_t fi
, unsigned part
)
3873 struct constraint_expr c
;
3875 gcc_assert (in_ipa_mode
);
3877 if (fi
->id
== anything_id
)
3879 /* ??? We probably should have a ANYFN special variable. */
3880 c
.var
= anything_id
;
3884 else if (TREE_CODE (fi
->decl
) == FUNCTION_DECL
)
3886 varinfo_t ai
= first_vi_for_offset (fi
, part
);
3890 c
.var
= anything_id
;
3904 /* For non-IPA mode, generate constraints necessary for a call on the
3908 handle_rhs_call (gcall
*stmt
, vec
<ce_s
> *results
)
3910 struct constraint_expr rhsc
;
3912 bool returns_uses
= false;
3914 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3916 tree arg
= gimple_call_arg (stmt
, i
);
3917 int flags
= gimple_call_arg_flags (stmt
, i
);
3919 /* If the argument is not used we can ignore it. */
3920 if (flags
& EAF_UNUSED
)
3923 /* As we compute ESCAPED context-insensitive we do not gain
3924 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3925 set. The argument would still get clobbered through the
3927 if ((flags
& EAF_NOCLOBBER
)
3928 && (flags
& EAF_NOESCAPE
))
3930 varinfo_t uses
= get_call_use_vi (stmt
);
3931 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg", true);
3932 make_constraint_to (tem
->id
, arg
);
3933 make_any_offset_constraints (tem
);
3934 if (!(flags
& EAF_DIRECT
))
3935 make_transitive_closure_constraints (tem
);
3936 make_copy_constraint (uses
, tem
->id
);
3937 returns_uses
= true;
3939 else if (flags
& EAF_NOESCAPE
)
3941 struct constraint_expr lhs
, rhs
;
3942 varinfo_t uses
= get_call_use_vi (stmt
);
3943 varinfo_t clobbers
= get_call_clobber_vi (stmt
);
3944 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg", true);
3945 make_constraint_to (tem
->id
, arg
);
3946 make_any_offset_constraints (tem
);
3947 if (!(flags
& EAF_DIRECT
))
3948 make_transitive_closure_constraints (tem
);
3949 make_copy_constraint (uses
, tem
->id
);
3950 make_copy_constraint (clobbers
, tem
->id
);
3951 /* Add *tem = nonlocal, do not add *tem = callused as
3952 EAF_NOESCAPE parameters do not escape to other parameters
3953 and all other uses appear in NONLOCAL as well. */
3958 rhs
.var
= nonlocal_id
;
3960 process_constraint (new_constraint (lhs
, rhs
));
3961 returns_uses
= true;
3964 make_escape_constraint (arg
);
3967 /* If we added to the calls uses solution make sure we account for
3968 pointers to it to be returned. */
3971 rhsc
.var
= get_call_use_vi (stmt
)->id
;
3972 rhsc
.offset
= UNKNOWN_OFFSET
;
3974 results
->safe_push (rhsc
);
3977 /* The static chain escapes as well. */
3978 if (gimple_call_chain (stmt
))
3979 make_escape_constraint (gimple_call_chain (stmt
));
3981 /* And if we applied NRV the address of the return slot escapes as well. */
3982 if (gimple_call_return_slot_opt_p (stmt
)
3983 && gimple_call_lhs (stmt
) != NULL_TREE
3984 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
3986 auto_vec
<ce_s
> tmpc
;
3987 struct constraint_expr lhsc
, *c
;
3988 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
3989 lhsc
.var
= escaped_id
;
3992 FOR_EACH_VEC_ELT (tmpc
, i
, c
)
3993 process_constraint (new_constraint (lhsc
, *c
));
3996 /* Regular functions return nonlocal memory. */
3997 rhsc
.var
= nonlocal_id
;
4000 results
->safe_push (rhsc
);
4003 /* For non-IPA mode, generate constraints necessary for a call
4004 that returns a pointer and assigns it to LHS. This simply makes
4005 the LHS point to global and escaped variables. */
4008 handle_lhs_call (gcall
*stmt
, tree lhs
, int flags
, vec
<ce_s
> rhsc
,
4011 auto_vec
<ce_s
> lhsc
;
4013 get_constraint_for (lhs
, &lhsc
);
4014 /* If the store is to a global decl make sure to
4015 add proper escape constraints. */
4016 lhs
= get_base_address (lhs
);
4019 && is_global_var (lhs
))
4021 struct constraint_expr tmpc
;
4022 tmpc
.var
= escaped_id
;
4025 lhsc
.safe_push (tmpc
);
4028 /* If the call returns an argument unmodified override the rhs
4030 if (flags
& ERF_RETURNS_ARG
4031 && (flags
& ERF_RETURN_ARG_MASK
) < gimple_call_num_args (stmt
))
4035 arg
= gimple_call_arg (stmt
, flags
& ERF_RETURN_ARG_MASK
);
4036 get_constraint_for (arg
, &rhsc
);
4037 process_all_all_constraints (lhsc
, rhsc
);
4040 else if (flags
& ERF_NOALIAS
)
4043 struct constraint_expr tmpc
;
4045 vi
= make_heapvar ("HEAP", true);
4046 /* We are marking allocated storage local, we deal with it becoming
4047 global by escaping and setting of vars_contains_escaped_heap. */
4048 DECL_EXTERNAL (vi
->decl
) = 0;
4049 vi
->is_global_var
= 0;
4050 /* If this is not a real malloc call assume the memory was
4051 initialized and thus may point to global memory. All
4052 builtin functions with the malloc attribute behave in a sane way. */
4054 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
4055 make_constraint_from (vi
, nonlocal_id
);
4058 tmpc
.type
= ADDRESSOF
;
4059 rhsc
.safe_push (tmpc
);
4060 process_all_all_constraints (lhsc
, rhsc
);
4064 process_all_all_constraints (lhsc
, rhsc
);
4067 /* For non-IPA mode, generate constraints necessary for a call of a
4068 const function that returns a pointer in the statement STMT. */
4071 handle_const_call (gcall
*stmt
, vec
<ce_s
> *results
)
4073 struct constraint_expr rhsc
;
4075 bool need_uses
= false;
4077 /* Treat nested const functions the same as pure functions as far
4078 as the static chain is concerned. */
4079 if (gimple_call_chain (stmt
))
4081 varinfo_t uses
= get_call_use_vi (stmt
);
4082 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4086 /* And if we applied NRV the address of the return slot escapes as well. */
4087 if (gimple_call_return_slot_opt_p (stmt
)
4088 && gimple_call_lhs (stmt
) != NULL_TREE
4089 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
4091 varinfo_t uses
= get_call_use_vi (stmt
);
4092 auto_vec
<ce_s
> tmpc
;
4093 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
4094 make_constraints_to (uses
->id
, tmpc
);
4100 varinfo_t uses
= get_call_use_vi (stmt
);
4101 make_any_offset_constraints (uses
);
4102 make_transitive_closure_constraints (uses
);
4103 rhsc
.var
= uses
->id
;
4106 results
->safe_push (rhsc
);
4109 /* May return offsetted arguments. */
4110 varinfo_t tem
= NULL
;
4111 if (gimple_call_num_args (stmt
) != 0)
4112 tem
= new_var_info (NULL_TREE
, "callarg", true);
4113 for (k
= 0; k
< gimple_call_num_args (stmt
); ++k
)
4115 tree arg
= gimple_call_arg (stmt
, k
);
4116 auto_vec
<ce_s
> argc
;
4117 get_constraint_for_rhs (arg
, &argc
);
4118 make_constraints_to (tem
->id
, argc
);
4125 ce
.offset
= UNKNOWN_OFFSET
;
4126 results
->safe_push (ce
);
4129 /* May return addresses of globals. */
4130 rhsc
.var
= nonlocal_id
;
4132 rhsc
.type
= ADDRESSOF
;
4133 results
->safe_push (rhsc
);
4136 /* For non-IPA mode, generate constraints necessary for a call to a
4137 pure function in statement STMT. */
4140 handle_pure_call (gcall
*stmt
, vec
<ce_s
> *results
)
4142 struct constraint_expr rhsc
;
4144 varinfo_t uses
= NULL
;
4146 /* Memory reached from pointer arguments is call-used. */
4147 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
4149 tree arg
= gimple_call_arg (stmt
, i
);
4152 uses
= get_call_use_vi (stmt
);
4153 make_any_offset_constraints (uses
);
4154 make_transitive_closure_constraints (uses
);
4156 make_constraint_to (uses
->id
, arg
);
4159 /* The static chain is used as well. */
4160 if (gimple_call_chain (stmt
))
4164 uses
= get_call_use_vi (stmt
);
4165 make_any_offset_constraints (uses
);
4166 make_transitive_closure_constraints (uses
);
4168 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4171 /* And if we applied NRV the address of the return slot. */
4172 if (gimple_call_return_slot_opt_p (stmt
)
4173 && gimple_call_lhs (stmt
) != NULL_TREE
4174 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
4178 uses
= get_call_use_vi (stmt
);
4179 make_any_offset_constraints (uses
);
4180 make_transitive_closure_constraints (uses
);
4182 auto_vec
<ce_s
> tmpc
;
4183 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
4184 make_constraints_to (uses
->id
, tmpc
);
4187 /* Pure functions may return call-used and nonlocal memory. */
4190 rhsc
.var
= uses
->id
;
4193 results
->safe_push (rhsc
);
4195 rhsc
.var
= nonlocal_id
;
4198 results
->safe_push (rhsc
);
4202 /* Return the varinfo for the callee of CALL. */
4205 get_fi_for_callee (gcall
*call
)
4207 tree decl
, fn
= gimple_call_fn (call
);
4209 if (fn
&& TREE_CODE (fn
) == OBJ_TYPE_REF
)
4210 fn
= OBJ_TYPE_REF_EXPR (fn
);
4212 /* If we can directly resolve the function being called, do so.
4213 Otherwise, it must be some sort of indirect expression that
4214 we should still be able to handle. */
4215 decl
= gimple_call_addr_fndecl (fn
);
4217 return get_vi_for_tree (decl
);
4219 /* If the function is anything other than a SSA name pointer we have no
4220 clue and should be getting ANYFN (well, ANYTHING for now). */
4221 if (!fn
|| TREE_CODE (fn
) != SSA_NAME
)
4222 return get_varinfo (anything_id
);
4224 if (SSA_NAME_IS_DEFAULT_DEF (fn
)
4225 && (TREE_CODE (SSA_NAME_VAR (fn
)) == PARM_DECL
4226 || TREE_CODE (SSA_NAME_VAR (fn
)) == RESULT_DECL
))
4227 fn
= SSA_NAME_VAR (fn
);
4229 return get_vi_for_tree (fn
);
4232 /* Create constraints for assigning call argument ARG to the incoming parameter
4233 INDEX of function FI. */
4236 find_func_aliases_for_call_arg (varinfo_t fi
, unsigned index
, tree arg
)
4238 struct constraint_expr lhs
;
4239 lhs
= get_function_part_constraint (fi
, fi_parm_base
+ index
);
4241 auto_vec
<ce_s
, 2> rhsc
;
4242 get_constraint_for_rhs (arg
, &rhsc
);
4245 struct constraint_expr
*rhsp
;
4246 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4247 process_constraint (new_constraint (lhs
, *rhsp
));
4250 /* Return true if FNDECL may be part of another lto partition. */
4253 fndecl_maybe_in_other_partition (tree fndecl
)
4255 cgraph_node
*fn_node
= cgraph_node::get (fndecl
);
4256 if (fn_node
== NULL
)
4259 return fn_node
->in_other_partition
;
4262 /* Create constraints for the builtin call T. Return true if the call
4263 was handled, otherwise false. */
4266 find_func_aliases_for_builtin_call (struct function
*fn
, gcall
*t
)
4268 tree fndecl
= gimple_call_fndecl (t
);
4269 auto_vec
<ce_s
, 2> lhsc
;
4270 auto_vec
<ce_s
, 4> rhsc
;
4273 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
4274 /* ??? All builtins that are handled here need to be handled
4275 in the alias-oracle query functions explicitly! */
4276 switch (DECL_FUNCTION_CODE (fndecl
))
4278 /* All the following functions return a pointer to the same object
4279 as their first argument points to. The functions do not add
4280 to the ESCAPED solution. The functions make the first argument
4281 pointed to memory point to what the second argument pointed to
4282 memory points to. */
4283 case BUILT_IN_STRCPY
:
4284 case BUILT_IN_STRNCPY
:
4285 case BUILT_IN_BCOPY
:
4286 case BUILT_IN_MEMCPY
:
4287 case BUILT_IN_MEMMOVE
:
4288 case BUILT_IN_MEMPCPY
:
4289 case BUILT_IN_STPCPY
:
4290 case BUILT_IN_STPNCPY
:
4291 case BUILT_IN_STRCAT
:
4292 case BUILT_IN_STRNCAT
:
4293 case BUILT_IN_STRCPY_CHK
:
4294 case BUILT_IN_STRNCPY_CHK
:
4295 case BUILT_IN_MEMCPY_CHK
:
4296 case BUILT_IN_MEMMOVE_CHK
:
4297 case BUILT_IN_MEMPCPY_CHK
:
4298 case BUILT_IN_STPCPY_CHK
:
4299 case BUILT_IN_STPNCPY_CHK
:
4300 case BUILT_IN_STRCAT_CHK
:
4301 case BUILT_IN_STRNCAT_CHK
:
4302 case BUILT_IN_TM_MEMCPY
:
4303 case BUILT_IN_TM_MEMMOVE
:
4305 tree res
= gimple_call_lhs (t
);
4306 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4307 == BUILT_IN_BCOPY
? 1 : 0));
4308 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4309 == BUILT_IN_BCOPY
? 0 : 1));
4310 if (res
!= NULL_TREE
)
4312 get_constraint_for (res
, &lhsc
);
4313 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY
4314 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY
4315 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY
4316 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY_CHK
4317 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY_CHK
4318 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY_CHK
)
4319 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &rhsc
);
4321 get_constraint_for (dest
, &rhsc
);
4322 process_all_all_constraints (lhsc
, rhsc
);
4326 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4327 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4330 process_all_all_constraints (lhsc
, rhsc
);
4333 case BUILT_IN_MEMSET
:
4334 case BUILT_IN_MEMSET_CHK
:
4335 case BUILT_IN_TM_MEMSET
:
4337 tree res
= gimple_call_lhs (t
);
4338 tree dest
= gimple_call_arg (t
, 0);
4341 struct constraint_expr ac
;
4342 if (res
!= NULL_TREE
)
4344 get_constraint_for (res
, &lhsc
);
4345 get_constraint_for (dest
, &rhsc
);
4346 process_all_all_constraints (lhsc
, rhsc
);
4349 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4351 if (flag_delete_null_pointer_checks
4352 && integer_zerop (gimple_call_arg (t
, 1)))
4354 ac
.type
= ADDRESSOF
;
4355 ac
.var
= nothing_id
;
4360 ac
.var
= integer_id
;
4363 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4364 process_constraint (new_constraint (*lhsp
, ac
));
4367 case BUILT_IN_POSIX_MEMALIGN
:
4369 tree ptrptr
= gimple_call_arg (t
, 0);
4370 get_constraint_for (ptrptr
, &lhsc
);
4372 varinfo_t vi
= make_heapvar ("HEAP", true);
4373 /* We are marking allocated storage local, we deal with it becoming
4374 global by escaping and setting of vars_contains_escaped_heap. */
4375 DECL_EXTERNAL (vi
->decl
) = 0;
4376 vi
->is_global_var
= 0;
4377 struct constraint_expr tmpc
;
4380 tmpc
.type
= ADDRESSOF
;
4381 rhsc
.safe_push (tmpc
);
4382 process_all_all_constraints (lhsc
, rhsc
);
4385 case BUILT_IN_ASSUME_ALIGNED
:
4387 tree res
= gimple_call_lhs (t
);
4388 tree dest
= gimple_call_arg (t
, 0);
4389 if (res
!= NULL_TREE
)
4391 get_constraint_for (res
, &lhsc
);
4392 get_constraint_for (dest
, &rhsc
);
4393 process_all_all_constraints (lhsc
, rhsc
);
4397 /* All the following functions do not return pointers, do not
4398 modify the points-to sets of memory reachable from their
4399 arguments and do not add to the ESCAPED solution. */
4400 case BUILT_IN_SINCOS
:
4401 case BUILT_IN_SINCOSF
:
4402 case BUILT_IN_SINCOSL
:
4403 case BUILT_IN_FREXP
:
4404 case BUILT_IN_FREXPF
:
4405 case BUILT_IN_FREXPL
:
4406 case BUILT_IN_GAMMA_R
:
4407 case BUILT_IN_GAMMAF_R
:
4408 case BUILT_IN_GAMMAL_R
:
4409 case BUILT_IN_LGAMMA_R
:
4410 case BUILT_IN_LGAMMAF_R
:
4411 case BUILT_IN_LGAMMAL_R
:
4413 case BUILT_IN_MODFF
:
4414 case BUILT_IN_MODFL
:
4415 case BUILT_IN_REMQUO
:
4416 case BUILT_IN_REMQUOF
:
4417 case BUILT_IN_REMQUOL
:
4420 case BUILT_IN_STRDUP
:
4421 case BUILT_IN_STRNDUP
:
4422 case BUILT_IN_REALLOC
:
4423 if (gimple_call_lhs (t
))
4425 handle_lhs_call (t
, gimple_call_lhs (t
),
4426 gimple_call_return_flags (t
) | ERF_NOALIAS
,
4428 get_constraint_for_ptr_offset (gimple_call_lhs (t
),
4430 get_constraint_for_ptr_offset (gimple_call_arg (t
, 0),
4434 process_all_all_constraints (lhsc
, rhsc
);
4437 /* For realloc the resulting pointer can be equal to the
4438 argument as well. But only doing this wouldn't be
4439 correct because with ptr == 0 realloc behaves like malloc. */
4440 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_REALLOC
)
4442 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4443 get_constraint_for (gimple_call_arg (t
, 0), &rhsc
);
4444 process_all_all_constraints (lhsc
, rhsc
);
4449 /* String / character search functions return a pointer into the
4450 source string or NULL. */
4451 case BUILT_IN_INDEX
:
4452 case BUILT_IN_STRCHR
:
4453 case BUILT_IN_STRRCHR
:
4454 case BUILT_IN_MEMCHR
:
4455 case BUILT_IN_STRSTR
:
4456 case BUILT_IN_STRPBRK
:
4457 if (gimple_call_lhs (t
))
4459 tree src
= gimple_call_arg (t
, 0);
4460 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4461 constraint_expr nul
;
4462 nul
.var
= nothing_id
;
4464 nul
.type
= ADDRESSOF
;
4465 rhsc
.safe_push (nul
);
4466 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4467 process_all_all_constraints (lhsc
, rhsc
);
4470 /* Pure functions that return something not based on any object and
4471 that use the memory pointed to by their arguments (but not
4473 case BUILT_IN_STRCMP
:
4474 case BUILT_IN_STRNCMP
:
4475 case BUILT_IN_STRCASECMP
:
4476 case BUILT_IN_STRNCASECMP
:
4477 case BUILT_IN_MEMCMP
:
4479 case BUILT_IN_STRSPN
:
4480 case BUILT_IN_STRCSPN
:
4482 varinfo_t uses
= get_call_use_vi (t
);
4483 make_any_offset_constraints (uses
);
4484 make_constraint_to (uses
->id
, gimple_call_arg (t
, 0));
4485 make_constraint_to (uses
->id
, gimple_call_arg (t
, 1));
4486 /* No constraints are necessary for the return value. */
4489 case BUILT_IN_STRLEN
:
4491 varinfo_t uses
= get_call_use_vi (t
);
4492 make_any_offset_constraints (uses
);
4493 make_constraint_to (uses
->id
, gimple_call_arg (t
, 0));
4494 /* No constraints are necessary for the return value. */
4497 case BUILT_IN_OBJECT_SIZE
:
4498 case BUILT_IN_CONSTANT_P
:
4500 /* No constraints are necessary for the return value or the
4504 /* Trampolines are special - they set up passing the static
4506 case BUILT_IN_INIT_TRAMPOLINE
:
4508 tree tramp
= gimple_call_arg (t
, 0);
4509 tree nfunc
= gimple_call_arg (t
, 1);
4510 tree frame
= gimple_call_arg (t
, 2);
4512 struct constraint_expr lhs
, *rhsp
;
4515 varinfo_t nfi
= NULL
;
4516 gcc_assert (TREE_CODE (nfunc
) == ADDR_EXPR
);
4517 nfi
= lookup_vi_for_tree (TREE_OPERAND (nfunc
, 0));
4520 lhs
= get_function_part_constraint (nfi
, fi_static_chain
);
4521 get_constraint_for (frame
, &rhsc
);
4522 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4523 process_constraint (new_constraint (lhs
, *rhsp
));
4526 /* Make the frame point to the function for
4527 the trampoline adjustment call. */
4528 get_constraint_for (tramp
, &lhsc
);
4530 get_constraint_for (nfunc
, &rhsc
);
4531 process_all_all_constraints (lhsc
, rhsc
);
4536 /* Else fallthru to generic handling which will let
4537 the frame escape. */
4540 case BUILT_IN_ADJUST_TRAMPOLINE
:
4542 tree tramp
= gimple_call_arg (t
, 0);
4543 tree res
= gimple_call_lhs (t
);
4544 if (in_ipa_mode
&& res
)
4546 get_constraint_for (res
, &lhsc
);
4547 get_constraint_for (tramp
, &rhsc
);
4549 process_all_all_constraints (lhsc
, rhsc
);
4553 CASE_BUILT_IN_TM_STORE (1):
4554 CASE_BUILT_IN_TM_STORE (2):
4555 CASE_BUILT_IN_TM_STORE (4):
4556 CASE_BUILT_IN_TM_STORE (8):
4557 CASE_BUILT_IN_TM_STORE (FLOAT
):
4558 CASE_BUILT_IN_TM_STORE (DOUBLE
):
4559 CASE_BUILT_IN_TM_STORE (LDOUBLE
):
4560 CASE_BUILT_IN_TM_STORE (M64
):
4561 CASE_BUILT_IN_TM_STORE (M128
):
4562 CASE_BUILT_IN_TM_STORE (M256
):
4564 tree addr
= gimple_call_arg (t
, 0);
4565 tree src
= gimple_call_arg (t
, 1);
4567 get_constraint_for (addr
, &lhsc
);
4569 get_constraint_for (src
, &rhsc
);
4570 process_all_all_constraints (lhsc
, rhsc
);
4573 CASE_BUILT_IN_TM_LOAD (1):
4574 CASE_BUILT_IN_TM_LOAD (2):
4575 CASE_BUILT_IN_TM_LOAD (4):
4576 CASE_BUILT_IN_TM_LOAD (8):
4577 CASE_BUILT_IN_TM_LOAD (FLOAT
):
4578 CASE_BUILT_IN_TM_LOAD (DOUBLE
):
4579 CASE_BUILT_IN_TM_LOAD (LDOUBLE
):
4580 CASE_BUILT_IN_TM_LOAD (M64
):
4581 CASE_BUILT_IN_TM_LOAD (M128
):
4582 CASE_BUILT_IN_TM_LOAD (M256
):
4584 tree dest
= gimple_call_lhs (t
);
4585 tree addr
= gimple_call_arg (t
, 0);
4587 get_constraint_for (dest
, &lhsc
);
4588 get_constraint_for (addr
, &rhsc
);
4590 process_all_all_constraints (lhsc
, rhsc
);
4593 /* Variadic argument handling needs to be handled in IPA
4595 case BUILT_IN_VA_START
:
4597 tree valist
= gimple_call_arg (t
, 0);
4598 struct constraint_expr rhs
, *lhsp
;
4600 get_constraint_for_ptr_offset (valist
, NULL_TREE
, &lhsc
);
4602 /* The va_list gets access to pointers in variadic
4603 arguments. Which we know in the case of IPA analysis
4604 and otherwise are just all nonlocal variables. */
4607 fi
= lookup_vi_for_tree (fn
->decl
);
4608 rhs
= get_function_part_constraint (fi
, ~0);
4609 rhs
.type
= ADDRESSOF
;
4613 rhs
.var
= nonlocal_id
;
4614 rhs
.type
= ADDRESSOF
;
4617 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4618 process_constraint (new_constraint (*lhsp
, rhs
));
4619 /* va_list is clobbered. */
4620 make_constraint_to (get_call_clobber_vi (t
)->id
, valist
);
4623 /* va_end doesn't have any effect that matters. */
4624 case BUILT_IN_VA_END
:
4626 /* Alternate return. Simply give up for now. */
4627 case BUILT_IN_RETURN
:
4631 || !(fi
= get_vi_for_tree (fn
->decl
)))
4632 make_constraint_from (get_varinfo (escaped_id
), anything_id
);
4633 else if (in_ipa_mode
4636 struct constraint_expr lhs
, rhs
;
4637 lhs
= get_function_part_constraint (fi
, fi_result
);
4638 rhs
.var
= anything_id
;
4641 process_constraint (new_constraint (lhs
, rhs
));
4645 case BUILT_IN_GOMP_PARALLEL
:
4646 case BUILT_IN_GOACC_PARALLEL
:
4650 unsigned int fnpos
, argpos
;
4651 switch (DECL_FUNCTION_CODE (fndecl
))
4653 case BUILT_IN_GOMP_PARALLEL
:
4654 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
4658 case BUILT_IN_GOACC_PARALLEL
:
4659 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
4660 sizes, kinds, ...). */
4668 tree fnarg
= gimple_call_arg (t
, fnpos
);
4669 gcc_assert (TREE_CODE (fnarg
) == ADDR_EXPR
);
4670 tree fndecl
= TREE_OPERAND (fnarg
, 0);
4671 if (fndecl_maybe_in_other_partition (fndecl
))
4672 /* Fallthru to general call handling. */
4675 tree arg
= gimple_call_arg (t
, argpos
);
4677 varinfo_t fi
= get_vi_for_tree (fndecl
);
4678 find_func_aliases_for_call_arg (fi
, 0, arg
);
4681 /* Else fallthru to generic call handling. */
4684 /* printf-style functions may have hooks to set pointers to
4685 point to somewhere into the generated string. Leave them
4686 for a later exercise... */
4688 /* Fallthru to general call handling. */;
4694 /* Create constraints for the call T. */
4697 find_func_aliases_for_call (struct function
*fn
, gcall
*t
)
4699 tree fndecl
= gimple_call_fndecl (t
);
4702 if (fndecl
!= NULL_TREE
4703 && DECL_BUILT_IN (fndecl
)
4704 && find_func_aliases_for_builtin_call (fn
, t
))
4707 fi
= get_fi_for_callee (t
);
4709 || (fndecl
&& !fi
->is_fn_info
))
4711 auto_vec
<ce_s
, 16> rhsc
;
4712 int flags
= gimple_call_flags (t
);
4714 /* Const functions can return their arguments and addresses
4715 of global memory but not of escaped memory. */
4716 if (flags
& (ECF_CONST
|ECF_NOVOPS
))
4718 if (gimple_call_lhs (t
))
4719 handle_const_call (t
, &rhsc
);
4721 /* Pure functions can return addresses in and of memory
4722 reachable from their arguments, but they are not an escape
4723 point for reachable memory of their arguments. */
4724 else if (flags
& (ECF_PURE
|ECF_LOOPING_CONST_OR_PURE
))
4725 handle_pure_call (t
, &rhsc
);
4727 handle_rhs_call (t
, &rhsc
);
4728 if (gimple_call_lhs (t
))
4729 handle_lhs_call (t
, gimple_call_lhs (t
),
4730 gimple_call_return_flags (t
), rhsc
, fndecl
);
4734 auto_vec
<ce_s
, 2> rhsc
;
4738 /* Assign all the passed arguments to the appropriate incoming
4739 parameters of the function. */
4740 for (j
= 0; j
< gimple_call_num_args (t
); j
++)
4742 tree arg
= gimple_call_arg (t
, j
);
4743 find_func_aliases_for_call_arg (fi
, j
, arg
);
4746 /* If we are returning a value, assign it to the result. */
4747 lhsop
= gimple_call_lhs (t
);
4750 auto_vec
<ce_s
, 2> lhsc
;
4751 struct constraint_expr rhs
;
4752 struct constraint_expr
*lhsp
;
4753 bool aggr_p
= aggregate_value_p (lhsop
, gimple_call_fntype (t
));
4755 get_constraint_for (lhsop
, &lhsc
);
4756 rhs
= get_function_part_constraint (fi
, fi_result
);
4759 auto_vec
<ce_s
, 2> tem
;
4760 tem
.quick_push (rhs
);
4762 gcc_checking_assert (tem
.length () == 1);
4765 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4766 process_constraint (new_constraint (*lhsp
, rhs
));
4768 /* If we pass the result decl by reference, honor that. */
4771 struct constraint_expr lhs
;
4772 struct constraint_expr
*rhsp
;
4774 get_constraint_for_address_of (lhsop
, &rhsc
);
4775 lhs
= get_function_part_constraint (fi
, fi_result
);
4776 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4777 process_constraint (new_constraint (lhs
, *rhsp
));
4782 /* If we use a static chain, pass it along. */
4783 if (gimple_call_chain (t
))
4785 struct constraint_expr lhs
;
4786 struct constraint_expr
*rhsp
;
4788 get_constraint_for (gimple_call_chain (t
), &rhsc
);
4789 lhs
= get_function_part_constraint (fi
, fi_static_chain
);
4790 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4791 process_constraint (new_constraint (lhs
, *rhsp
));
4796 /* Walk statement T setting up aliasing constraints according to the
4797 references found in T. This function is the main part of the
4798 constraint builder. AI points to auxiliary alias information used
4799 when building alias sets and computing alias grouping heuristics. */
4802 find_func_aliases (struct function
*fn
, gimple
*origt
)
4805 auto_vec
<ce_s
, 16> lhsc
;
4806 auto_vec
<ce_s
, 16> rhsc
;
4807 struct constraint_expr
*c
;
4810 /* Now build constraints expressions. */
4811 if (gimple_code (t
) == GIMPLE_PHI
)
4816 /* For a phi node, assign all the arguments to
4818 get_constraint_for (gimple_phi_result (t
), &lhsc
);
4819 for (i
= 0; i
< gimple_phi_num_args (t
); i
++)
4821 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
4823 STRIP_NOPS (strippedrhs
);
4824 get_constraint_for_rhs (gimple_phi_arg_def (t
, i
), &rhsc
);
4826 FOR_EACH_VEC_ELT (lhsc
, j
, c
)
4828 struct constraint_expr
*c2
;
4829 while (rhsc
.length () > 0)
4832 process_constraint (new_constraint (*c
, *c2
));
4838 /* In IPA mode, we need to generate constraints to pass call
4839 arguments through their calls. There are two cases,
4840 either a GIMPLE_CALL returning a value, or just a plain
4841 GIMPLE_CALL when we are not.
4843 In non-ipa mode, we need to generate constraints for each
4844 pointer passed by address. */
4845 else if (is_gimple_call (t
))
4846 find_func_aliases_for_call (fn
, as_a
<gcall
*> (t
));
4848 /* Otherwise, just a regular assignment statement. Only care about
4849 operations with pointer result, others are dealt with as escape
4850 points if they have pointer operands. */
4851 else if (is_gimple_assign (t
))
4853 /* Otherwise, just a regular assignment statement. */
4854 tree lhsop
= gimple_assign_lhs (t
);
4855 tree rhsop
= (gimple_num_ops (t
) == 2) ? gimple_assign_rhs1 (t
) : NULL
;
4857 if (rhsop
&& TREE_CLOBBER_P (rhsop
))
4858 /* Ignore clobbers, they don't actually store anything into
4861 else if (rhsop
&& AGGREGATE_TYPE_P (TREE_TYPE (lhsop
)))
4862 do_structure_copy (lhsop
, rhsop
);
4865 enum tree_code code
= gimple_assign_rhs_code (t
);
4867 get_constraint_for (lhsop
, &lhsc
);
4869 if (code
== POINTER_PLUS_EXPR
)
4870 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4871 gimple_assign_rhs2 (t
), &rhsc
);
4872 else if (code
== BIT_AND_EXPR
4873 && TREE_CODE (gimple_assign_rhs2 (t
)) == INTEGER_CST
)
4875 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4876 the pointer. Handle it by offsetting it by UNKNOWN. */
4877 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4880 else if ((CONVERT_EXPR_CODE_P (code
)
4881 && !(POINTER_TYPE_P (gimple_expr_type (t
))
4882 && !POINTER_TYPE_P (TREE_TYPE (rhsop
))))
4883 || gimple_assign_single_p (t
))
4884 get_constraint_for_rhs (rhsop
, &rhsc
);
4885 else if (code
== COND_EXPR
)
4887 /* The result is a merge of both COND_EXPR arms. */
4888 auto_vec
<ce_s
, 2> tmp
;
4889 struct constraint_expr
*rhsp
;
4891 get_constraint_for_rhs (gimple_assign_rhs2 (t
), &rhsc
);
4892 get_constraint_for_rhs (gimple_assign_rhs3 (t
), &tmp
);
4893 FOR_EACH_VEC_ELT (tmp
, i
, rhsp
)
4894 rhsc
.safe_push (*rhsp
);
4896 else if (truth_value_p (code
))
4897 /* Truth value results are not pointer (parts). Or at least
4898 very unreasonable obfuscation of a part. */
4902 /* All other operations are merges. */
4903 auto_vec
<ce_s
, 4> tmp
;
4904 struct constraint_expr
*rhsp
;
4906 get_constraint_for_rhs (gimple_assign_rhs1 (t
), &rhsc
);
4907 for (i
= 2; i
< gimple_num_ops (t
); ++i
)
4909 get_constraint_for_rhs (gimple_op (t
, i
), &tmp
);
4910 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
4911 rhsc
.safe_push (*rhsp
);
4915 process_all_all_constraints (lhsc
, rhsc
);
4917 /* If there is a store to a global variable the rhs escapes. */
4918 if ((lhsop
= get_base_address (lhsop
)) != NULL_TREE
4921 varinfo_t vi
= get_vi_for_tree (lhsop
);
4922 if ((! in_ipa_mode
&& vi
->is_global_var
)
4923 || vi
->is_ipa_escape_point
)
4924 make_escape_constraint (rhsop
);
4927 /* Handle escapes through return. */
4928 else if (gimple_code (t
) == GIMPLE_RETURN
4929 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
)
4931 greturn
*return_stmt
= as_a
<greturn
*> (t
);
4934 || !(fi
= get_vi_for_tree (fn
->decl
)))
4935 make_escape_constraint (gimple_return_retval (return_stmt
));
4936 else if (in_ipa_mode
)
4938 struct constraint_expr lhs
;
4939 struct constraint_expr
*rhsp
;
4942 lhs
= get_function_part_constraint (fi
, fi_result
);
4943 get_constraint_for_rhs (gimple_return_retval (return_stmt
), &rhsc
);
4944 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4945 process_constraint (new_constraint (lhs
, *rhsp
));
4948 /* Handle asms conservatively by adding escape constraints to everything. */
4949 else if (gasm
*asm_stmt
= dyn_cast
<gasm
*> (t
))
4951 unsigned i
, noutputs
;
4952 const char **oconstraints
;
4953 const char *constraint
;
4954 bool allows_mem
, allows_reg
, is_inout
;
4956 noutputs
= gimple_asm_noutputs (asm_stmt
);
4957 oconstraints
= XALLOCAVEC (const char *, noutputs
);
4959 for (i
= 0; i
< noutputs
; ++i
)
4961 tree link
= gimple_asm_output_op (asm_stmt
, i
);
4962 tree op
= TREE_VALUE (link
);
4964 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4965 oconstraints
[i
] = constraint
;
4966 parse_output_constraint (&constraint
, i
, 0, 0, &allows_mem
,
4967 &allows_reg
, &is_inout
);
4969 /* A memory constraint makes the address of the operand escape. */
4970 if (!allows_reg
&& allows_mem
)
4971 make_escape_constraint (build_fold_addr_expr (op
));
4973 /* The asm may read global memory, so outputs may point to
4974 any global memory. */
4977 auto_vec
<ce_s
, 2> lhsc
;
4978 struct constraint_expr rhsc
, *lhsp
;
4980 get_constraint_for (op
, &lhsc
);
4981 rhsc
.var
= nonlocal_id
;
4984 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4985 process_constraint (new_constraint (*lhsp
, rhsc
));
4988 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); ++i
)
4990 tree link
= gimple_asm_input_op (asm_stmt
, i
);
4991 tree op
= TREE_VALUE (link
);
4993 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4995 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0, oconstraints
,
4996 &allows_mem
, &allows_reg
);
4998 /* A memory constraint makes the address of the operand escape. */
4999 if (!allows_reg
&& allows_mem
)
5000 make_escape_constraint (build_fold_addr_expr (op
));
5001 /* Strictly we'd only need the constraint to ESCAPED if
5002 the asm clobbers memory, otherwise using something
5003 along the lines of per-call clobbers/uses would be enough. */
5005 make_escape_constraint (op
);
5011 /* Create a constraint adding to the clobber set of FI the memory
5012 pointed to by PTR. */
5015 process_ipa_clobber (varinfo_t fi
, tree ptr
)
5017 vec
<ce_s
> ptrc
= vNULL
;
5018 struct constraint_expr
*c
, lhs
;
5020 get_constraint_for_rhs (ptr
, &ptrc
);
5021 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5022 FOR_EACH_VEC_ELT (ptrc
, i
, c
)
5023 process_constraint (new_constraint (lhs
, *c
));
5027 /* Walk statement T setting up clobber and use constraints according to the
5028 references found in T. This function is a main part of the
5029 IPA constraint builder. */
5032 find_func_clobbers (struct function
*fn
, gimple
*origt
)
5035 auto_vec
<ce_s
, 16> lhsc
;
5036 auto_vec
<ce_s
, 16> rhsc
;
5039 /* Add constraints for clobbered/used in IPA mode.
5040 We are not interested in what automatic variables are clobbered
5041 or used as we only use the information in the caller to which
5042 they do not escape. */
5043 gcc_assert (in_ipa_mode
);
5045 /* If the stmt refers to memory in any way it better had a VUSE. */
5046 if (gimple_vuse (t
) == NULL_TREE
)
5049 /* We'd better have function information for the current function. */
5050 fi
= lookup_vi_for_tree (fn
->decl
);
5051 gcc_assert (fi
!= NULL
);
5053 /* Account for stores in assignments and calls. */
5054 if (gimple_vdef (t
) != NULL_TREE
5055 && gimple_has_lhs (t
))
5057 tree lhs
= gimple_get_lhs (t
);
5059 while (handled_component_p (tem
))
5060 tem
= TREE_OPERAND (tem
, 0);
5062 && !auto_var_in_fn_p (tem
, fn
->decl
))
5063 || INDIRECT_REF_P (tem
)
5064 || (TREE_CODE (tem
) == MEM_REF
5065 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
5067 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
5069 struct constraint_expr lhsc
, *rhsp
;
5071 lhsc
= get_function_part_constraint (fi
, fi_clobbers
);
5072 get_constraint_for_address_of (lhs
, &rhsc
);
5073 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5074 process_constraint (new_constraint (lhsc
, *rhsp
));
5079 /* Account for uses in assigments and returns. */
5080 if (gimple_assign_single_p (t
)
5081 || (gimple_code (t
) == GIMPLE_RETURN
5082 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
))
5084 tree rhs
= (gimple_assign_single_p (t
)
5085 ? gimple_assign_rhs1 (t
)
5086 : gimple_return_retval (as_a
<greturn
*> (t
)));
5088 while (handled_component_p (tem
))
5089 tem
= TREE_OPERAND (tem
, 0);
5091 && !auto_var_in_fn_p (tem
, fn
->decl
))
5092 || INDIRECT_REF_P (tem
)
5093 || (TREE_CODE (tem
) == MEM_REF
5094 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
5096 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
5098 struct constraint_expr lhs
, *rhsp
;
5100 lhs
= get_function_part_constraint (fi
, fi_uses
);
5101 get_constraint_for_address_of (rhs
, &rhsc
);
5102 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5103 process_constraint (new_constraint (lhs
, *rhsp
));
5108 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (t
))
5110 varinfo_t cfi
= NULL
;
5111 tree decl
= gimple_call_fndecl (t
);
5112 struct constraint_expr lhs
, rhs
;
5115 /* For builtins we do not have separate function info. For those
5116 we do not generate escapes for we have to generate clobbers/uses. */
5117 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
5118 switch (DECL_FUNCTION_CODE (decl
))
5120 /* The following functions use and clobber memory pointed to
5121 by their arguments. */
5122 case BUILT_IN_STRCPY
:
5123 case BUILT_IN_STRNCPY
:
5124 case BUILT_IN_BCOPY
:
5125 case BUILT_IN_MEMCPY
:
5126 case BUILT_IN_MEMMOVE
:
5127 case BUILT_IN_MEMPCPY
:
5128 case BUILT_IN_STPCPY
:
5129 case BUILT_IN_STPNCPY
:
5130 case BUILT_IN_STRCAT
:
5131 case BUILT_IN_STRNCAT
:
5132 case BUILT_IN_STRCPY_CHK
:
5133 case BUILT_IN_STRNCPY_CHK
:
5134 case BUILT_IN_MEMCPY_CHK
:
5135 case BUILT_IN_MEMMOVE_CHK
:
5136 case BUILT_IN_MEMPCPY_CHK
:
5137 case BUILT_IN_STPCPY_CHK
:
5138 case BUILT_IN_STPNCPY_CHK
:
5139 case BUILT_IN_STRCAT_CHK
:
5140 case BUILT_IN_STRNCAT_CHK
:
5142 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
5143 == BUILT_IN_BCOPY
? 1 : 0));
5144 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
5145 == BUILT_IN_BCOPY
? 0 : 1));
5147 struct constraint_expr
*rhsp
, *lhsp
;
5148 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5149 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5150 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5151 process_constraint (new_constraint (lhs
, *lhsp
));
5152 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
5153 lhs
= get_function_part_constraint (fi
, fi_uses
);
5154 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5155 process_constraint (new_constraint (lhs
, *rhsp
));
5158 /* The following function clobbers memory pointed to by
5160 case BUILT_IN_MEMSET
:
5161 case BUILT_IN_MEMSET_CHK
:
5162 case BUILT_IN_POSIX_MEMALIGN
:
5164 tree dest
= gimple_call_arg (t
, 0);
5167 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5168 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5169 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5170 process_constraint (new_constraint (lhs
, *lhsp
));
5173 /* The following functions clobber their second and third
5175 case BUILT_IN_SINCOS
:
5176 case BUILT_IN_SINCOSF
:
5177 case BUILT_IN_SINCOSL
:
5179 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5180 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5183 /* The following functions clobber their second argument. */
5184 case BUILT_IN_FREXP
:
5185 case BUILT_IN_FREXPF
:
5186 case BUILT_IN_FREXPL
:
5187 case BUILT_IN_LGAMMA_R
:
5188 case BUILT_IN_LGAMMAF_R
:
5189 case BUILT_IN_LGAMMAL_R
:
5190 case BUILT_IN_GAMMA_R
:
5191 case BUILT_IN_GAMMAF_R
:
5192 case BUILT_IN_GAMMAL_R
:
5194 case BUILT_IN_MODFF
:
5195 case BUILT_IN_MODFL
:
5197 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5200 /* The following functions clobber their third argument. */
5201 case BUILT_IN_REMQUO
:
5202 case BUILT_IN_REMQUOF
:
5203 case BUILT_IN_REMQUOL
:
5205 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5208 /* The following functions neither read nor clobber memory. */
5209 case BUILT_IN_ASSUME_ALIGNED
:
5212 /* Trampolines are of no interest to us. */
5213 case BUILT_IN_INIT_TRAMPOLINE
:
5214 case BUILT_IN_ADJUST_TRAMPOLINE
:
5216 case BUILT_IN_VA_START
:
5217 case BUILT_IN_VA_END
:
5219 case BUILT_IN_GOMP_PARALLEL
:
5220 case BUILT_IN_GOACC_PARALLEL
:
5222 unsigned int fnpos
, argpos
;
5223 unsigned int implicit_use_args
[2];
5224 unsigned int num_implicit_use_args
= 0;
5225 switch (DECL_FUNCTION_CODE (decl
))
5227 case BUILT_IN_GOMP_PARALLEL
:
5228 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
5232 case BUILT_IN_GOACC_PARALLEL
:
5233 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
5234 sizes, kinds, ...). */
5237 implicit_use_args
[num_implicit_use_args
++] = 4;
5238 implicit_use_args
[num_implicit_use_args
++] = 5;
5244 tree fnarg
= gimple_call_arg (t
, fnpos
);
5245 gcc_assert (TREE_CODE (fnarg
) == ADDR_EXPR
);
5246 tree fndecl
= TREE_OPERAND (fnarg
, 0);
5247 if (fndecl_maybe_in_other_partition (fndecl
))
5248 /* Fallthru to general call handling. */
5251 varinfo_t cfi
= get_vi_for_tree (fndecl
);
5253 tree arg
= gimple_call_arg (t
, argpos
);
5255 /* Parameter passed by value is used. */
5256 lhs
= get_function_part_constraint (fi
, fi_uses
);
5257 struct constraint_expr
*rhsp
;
5258 get_constraint_for (arg
, &rhsc
);
5259 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5260 process_constraint (new_constraint (lhs
, *rhsp
));
5263 /* Handle parameters used by the call, but not used in cfi, as
5264 implicitly used by cfi. */
5265 lhs
= get_function_part_constraint (cfi
, fi_uses
);
5266 for (unsigned i
= 0; i
< num_implicit_use_args
; ++i
)
5268 tree arg
= gimple_call_arg (t
, implicit_use_args
[i
]);
5269 get_constraint_for (arg
, &rhsc
);
5270 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5271 process_constraint (new_constraint (lhs
, *rhsp
));
5275 /* The caller clobbers what the callee does. */
5276 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5277 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5278 process_constraint (new_constraint (lhs
, rhs
));
5280 /* The caller uses what the callee does. */
5281 lhs
= get_function_part_constraint (fi
, fi_uses
);
5282 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5283 process_constraint (new_constraint (lhs
, rhs
));
5287 /* printf-style functions may have hooks to set pointers to
5288 point to somewhere into the generated string. Leave them
5289 for a later exercise... */
5291 /* Fallthru to general call handling. */;
5294 /* Parameters passed by value are used. */
5295 lhs
= get_function_part_constraint (fi
, fi_uses
);
5296 for (i
= 0; i
< gimple_call_num_args (t
); i
++)
5298 struct constraint_expr
*rhsp
;
5299 tree arg
= gimple_call_arg (t
, i
);
5301 if (TREE_CODE (arg
) == SSA_NAME
5302 || is_gimple_min_invariant (arg
))
5305 get_constraint_for_address_of (arg
, &rhsc
);
5306 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5307 process_constraint (new_constraint (lhs
, *rhsp
));
5311 /* Build constraints for propagating clobbers/uses along the
5313 cfi
= get_fi_for_callee (call_stmt
);
5314 if (cfi
->id
== anything_id
)
5316 if (gimple_vdef (t
))
5317 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5319 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5324 /* For callees without function info (that's external functions),
5325 ESCAPED is clobbered and used. */
5326 if (gimple_call_fndecl (t
)
5327 && !cfi
->is_fn_info
)
5331 if (gimple_vdef (t
))
5332 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5334 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
), escaped_id
);
5336 /* Also honor the call statement use/clobber info. */
5337 if ((vi
= lookup_call_clobber_vi (call_stmt
)) != NULL
)
5338 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5340 if ((vi
= lookup_call_use_vi (call_stmt
)) != NULL
)
5341 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
),
5346 /* Otherwise the caller clobbers and uses what the callee does.
5347 ??? This should use a new complex constraint that filters
5348 local variables of the callee. */
5349 if (gimple_vdef (t
))
5351 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5352 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5353 process_constraint (new_constraint (lhs
, rhs
));
5355 lhs
= get_function_part_constraint (fi
, fi_uses
);
5356 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5357 process_constraint (new_constraint (lhs
, rhs
));
5359 else if (gimple_code (t
) == GIMPLE_ASM
)
5361 /* ??? Ick. We can do better. */
5362 if (gimple_vdef (t
))
5363 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5365 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5371 /* Find the first varinfo in the same variable as START that overlaps with
5372 OFFSET. Return NULL if we can't find one. */
5375 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
5377 /* If the offset is outside of the variable, bail out. */
5378 if (offset
>= start
->fullsize
)
5381 /* If we cannot reach offset from start, lookup the first field
5382 and start from there. */
5383 if (start
->offset
> offset
)
5384 start
= get_varinfo (start
->head
);
5388 /* We may not find a variable in the field list with the actual
5389 offset when we have glommed a structure to a variable.
5390 In that case, however, offset should still be within the size
5392 if (offset
>= start
->offset
5393 && (offset
- start
->offset
) < start
->size
)
5396 start
= vi_next (start
);
5402 /* Find the first varinfo in the same variable as START that overlaps with
5403 OFFSET. If there is no such varinfo the varinfo directly preceding
5404 OFFSET is returned. */
5407 first_or_preceding_vi_for_offset (varinfo_t start
,
5408 unsigned HOST_WIDE_INT offset
)
5410 /* If we cannot reach offset from start, lookup the first field
5411 and start from there. */
5412 if (start
->offset
> offset
)
5413 start
= get_varinfo (start
->head
);
5415 /* We may not find a variable in the field list with the actual
5416 offset when we have glommed a structure to a variable.
5417 In that case, however, offset should still be within the size
5419 If we got beyond the offset we look for return the field
5420 directly preceding offset which may be the last field. */
5422 && offset
>= start
->offset
5423 && !((offset
- start
->offset
) < start
->size
))
5424 start
= vi_next (start
);
5430 /* This structure is used during pushing fields onto the fieldstack
5431 to track the offset of the field, since bitpos_of_field gives it
5432 relative to its immediate containing type, and we want it relative
5433 to the ultimate containing object. */
5437 /* Offset from the base of the base containing object to this field. */
5438 HOST_WIDE_INT offset
;
5440 /* Size, in bits, of the field. */
5441 unsigned HOST_WIDE_INT size
;
5443 unsigned has_unknown_size
: 1;
5445 unsigned must_have_pointers
: 1;
5447 unsigned may_have_pointers
: 1;
5449 unsigned only_restrict_pointers
: 1;
5451 tree restrict_pointed_type
;
5453 typedef struct fieldoff fieldoff_s
;
5456 /* qsort comparison function for two fieldoff's PA and PB */
5459 fieldoff_compare (const void *pa
, const void *pb
)
5461 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
5462 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
5463 unsigned HOST_WIDE_INT foasize
, fobsize
;
5465 if (foa
->offset
< fob
->offset
)
5467 else if (foa
->offset
> fob
->offset
)
5470 foasize
= foa
->size
;
5471 fobsize
= fob
->size
;
5472 if (foasize
< fobsize
)
5474 else if (foasize
> fobsize
)
5479 /* Sort a fieldstack according to the field offset and sizes. */
5481 sort_fieldstack (vec
<fieldoff_s
> fieldstack
)
5483 fieldstack
.qsort (fieldoff_compare
);
5486 /* Return true if T is a type that can have subvars. */
5489 type_can_have_subvars (const_tree t
)
5491 /* Aggregates without overlapping fields can have subvars. */
5492 return TREE_CODE (t
) == RECORD_TYPE
;
5495 /* Return true if V is a tree that we can have subvars for.
5496 Normally, this is any aggregate type. Also complex
5497 types which are not gimple registers can have subvars. */
5500 var_can_have_subvars (const_tree v
)
5502 /* Volatile variables should never have subvars. */
5503 if (TREE_THIS_VOLATILE (v
))
5506 /* Non decls or memory tags can never have subvars. */
5510 return type_can_have_subvars (TREE_TYPE (v
));
5513 /* Return true if T is a type that does contain pointers. */
5516 type_must_have_pointers (tree type
)
5518 if (POINTER_TYPE_P (type
))
5521 if (TREE_CODE (type
) == ARRAY_TYPE
)
5522 return type_must_have_pointers (TREE_TYPE (type
));
5524 /* A function or method can have pointers as arguments, so track
5525 those separately. */
5526 if (TREE_CODE (type
) == FUNCTION_TYPE
5527 || TREE_CODE (type
) == METHOD_TYPE
)
5534 field_must_have_pointers (tree t
)
5536 return type_must_have_pointers (TREE_TYPE (t
));
5539 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5540 the fields of TYPE onto fieldstack, recording their offsets along
5543 OFFSET is used to keep track of the offset in this entire
5544 structure, rather than just the immediately containing structure.
5545 Returns false if the caller is supposed to handle the field we
5549 push_fields_onto_fieldstack (tree type
, vec
<fieldoff_s
> *fieldstack
,
5550 HOST_WIDE_INT offset
)
5553 bool empty_p
= true;
5555 if (TREE_CODE (type
) != RECORD_TYPE
)
5558 /* If the vector of fields is growing too big, bail out early.
5559 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5561 if (fieldstack
->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5564 for (field
= TYPE_FIELDS (type
); field
; field
= DECL_CHAIN (field
))
5565 if (TREE_CODE (field
) == FIELD_DECL
)
5568 HOST_WIDE_INT foff
= bitpos_of_field (field
);
5569 tree field_type
= TREE_TYPE (field
);
5571 if (!var_can_have_subvars (field
)
5572 || TREE_CODE (field_type
) == QUAL_UNION_TYPE
5573 || TREE_CODE (field_type
) == UNION_TYPE
)
5575 else if (!push_fields_onto_fieldstack
5576 (field_type
, fieldstack
, offset
+ foff
)
5577 && (DECL_SIZE (field
)
5578 && !integer_zerop (DECL_SIZE (field
))))
5579 /* Empty structures may have actual size, like in C++. So
5580 see if we didn't push any subfields and the size is
5581 nonzero, push the field onto the stack. */
5586 fieldoff_s
*pair
= NULL
;
5587 bool has_unknown_size
= false;
5588 bool must_have_pointers_p
;
5590 if (!fieldstack
->is_empty ())
5591 pair
= &fieldstack
->last ();
5593 /* If there isn't anything at offset zero, create sth. */
5595 && offset
+ foff
!= 0)
5598 = {0, offset
+ foff
, false, false, true, false, NULL_TREE
};
5599 pair
= fieldstack
->safe_push (e
);
5602 if (!DECL_SIZE (field
)
5603 || !tree_fits_uhwi_p (DECL_SIZE (field
)))
5604 has_unknown_size
= true;
5606 /* If adjacent fields do not contain pointers merge them. */
5607 must_have_pointers_p
= field_must_have_pointers (field
);
5609 && !has_unknown_size
5610 && !must_have_pointers_p
5611 && !pair
->must_have_pointers
5612 && !pair
->has_unknown_size
5613 && pair
->offset
+ (HOST_WIDE_INT
)pair
->size
== offset
+ foff
)
5615 pair
->size
+= tree_to_uhwi (DECL_SIZE (field
));
5620 e
.offset
= offset
+ foff
;
5621 e
.has_unknown_size
= has_unknown_size
;
5622 if (!has_unknown_size
)
5623 e
.size
= tree_to_uhwi (DECL_SIZE (field
));
5626 e
.must_have_pointers
= must_have_pointers_p
;
5627 e
.may_have_pointers
= true;
5628 e
.only_restrict_pointers
5629 = (!has_unknown_size
5630 && POINTER_TYPE_P (field_type
)
5631 && TYPE_RESTRICT (field_type
));
5632 if (e
.only_restrict_pointers
)
5633 e
.restrict_pointed_type
= TREE_TYPE (field_type
);
5634 fieldstack
->safe_push (e
);
5644 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5645 if it is a varargs function. */
5648 count_num_arguments (tree decl
, bool *is_varargs
)
5650 unsigned int num
= 0;
5653 /* Capture named arguments for K&R functions. They do not
5654 have a prototype and thus no TYPE_ARG_TYPES. */
5655 for (t
= DECL_ARGUMENTS (decl
); t
; t
= DECL_CHAIN (t
))
5658 /* Check if the function has variadic arguments. */
5659 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
)); t
; t
= TREE_CHAIN (t
))
5660 if (TREE_VALUE (t
) == void_type_node
)
5668 /* Creation function node for DECL, using NAME, and return the index
5669 of the variable we've created for the function. If NONLOCAL_p, create
5670 initial constraints. */
5673 create_function_info_for (tree decl
, const char *name
, bool add_id
,
5676 struct function
*fn
= DECL_STRUCT_FUNCTION (decl
);
5677 varinfo_t vi
, prev_vi
;
5680 bool is_varargs
= false;
5681 unsigned int num_args
= count_num_arguments (decl
, &is_varargs
);
5683 /* Create the variable info. */
5685 vi
= new_var_info (decl
, name
, add_id
);
5688 vi
->fullsize
= fi_parm_base
+ num_args
;
5690 vi
->may_have_pointers
= false;
5693 insert_vi_for_tree (vi
->decl
, vi
);
5697 /* Create a variable for things the function clobbers and one for
5698 things the function uses. */
5700 varinfo_t clobbervi
, usevi
;
5701 const char *newname
;
5704 tempname
= xasprintf ("%s.clobber", name
);
5705 newname
= ggc_strdup (tempname
);
5708 clobbervi
= new_var_info (NULL
, newname
, false);
5709 clobbervi
->offset
= fi_clobbers
;
5710 clobbervi
->size
= 1;
5711 clobbervi
->fullsize
= vi
->fullsize
;
5712 clobbervi
->is_full_var
= true;
5713 clobbervi
->is_global_var
= false;
5715 gcc_assert (prev_vi
->offset
< clobbervi
->offset
);
5716 prev_vi
->next
= clobbervi
->id
;
5717 prev_vi
= clobbervi
;
5719 tempname
= xasprintf ("%s.use", name
);
5720 newname
= ggc_strdup (tempname
);
5723 usevi
= new_var_info (NULL
, newname
, false);
5724 usevi
->offset
= fi_uses
;
5726 usevi
->fullsize
= vi
->fullsize
;
5727 usevi
->is_full_var
= true;
5728 usevi
->is_global_var
= false;
5730 gcc_assert (prev_vi
->offset
< usevi
->offset
);
5731 prev_vi
->next
= usevi
->id
;
5735 /* And one for the static chain. */
5736 if (fn
->static_chain_decl
!= NULL_TREE
)
5739 const char *newname
;
5742 tempname
= xasprintf ("%s.chain", name
);
5743 newname
= ggc_strdup (tempname
);
5746 chainvi
= new_var_info (fn
->static_chain_decl
, newname
, false);
5747 chainvi
->offset
= fi_static_chain
;
5749 chainvi
->fullsize
= vi
->fullsize
;
5750 chainvi
->is_full_var
= true;
5751 chainvi
->is_global_var
= false;
5753 insert_vi_for_tree (fn
->static_chain_decl
, chainvi
);
5756 && chainvi
->may_have_pointers
)
5757 make_constraint_from (chainvi
, nonlocal_id
);
5759 gcc_assert (prev_vi
->offset
< chainvi
->offset
);
5760 prev_vi
->next
= chainvi
->id
;
5764 /* Create a variable for the return var. */
5765 if (DECL_RESULT (decl
) != NULL
5766 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
5769 const char *newname
;
5771 tree resultdecl
= decl
;
5773 if (DECL_RESULT (decl
))
5774 resultdecl
= DECL_RESULT (decl
);
5776 tempname
= xasprintf ("%s.result", name
);
5777 newname
= ggc_strdup (tempname
);
5780 resultvi
= new_var_info (resultdecl
, newname
, false);
5781 resultvi
->offset
= fi_result
;
5783 resultvi
->fullsize
= vi
->fullsize
;
5784 resultvi
->is_full_var
= true;
5785 if (DECL_RESULT (decl
))
5786 resultvi
->may_have_pointers
= true;
5788 if (DECL_RESULT (decl
))
5789 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
5792 && DECL_RESULT (decl
)
5793 && DECL_BY_REFERENCE (DECL_RESULT (decl
)))
5794 make_constraint_from (resultvi
, nonlocal_id
);
5796 gcc_assert (prev_vi
->offset
< resultvi
->offset
);
5797 prev_vi
->next
= resultvi
->id
;
5801 /* We also need to make function return values escape. Nothing
5802 escapes by returning from main though. */
5804 && !MAIN_NAME_P (DECL_NAME (decl
)))
5807 fi
= lookup_vi_for_tree (decl
);
5808 rvi
= first_vi_for_offset (fi
, fi_result
);
5809 if (rvi
&& rvi
->offset
== fi_result
)
5810 make_copy_constraint (get_varinfo (escaped_id
), rvi
->id
);
5813 /* Set up variables for each argument. */
5814 arg
= DECL_ARGUMENTS (decl
);
5815 for (i
= 0; i
< num_args
; i
++)
5818 const char *newname
;
5820 tree argdecl
= decl
;
5825 tempname
= xasprintf ("%s.arg%d", name
, i
);
5826 newname
= ggc_strdup (tempname
);
5829 argvi
= new_var_info (argdecl
, newname
, false);
5830 argvi
->offset
= fi_parm_base
+ i
;
5832 argvi
->is_full_var
= true;
5833 argvi
->fullsize
= vi
->fullsize
;
5835 argvi
->may_have_pointers
= true;
5838 insert_vi_for_tree (arg
, argvi
);
5841 && argvi
->may_have_pointers
)
5842 make_constraint_from (argvi
, nonlocal_id
);
5844 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5845 prev_vi
->next
= argvi
->id
;
5848 arg
= DECL_CHAIN (arg
);
5851 /* Add one representative for all further args. */
5855 const char *newname
;
5859 tempname
= xasprintf ("%s.varargs", name
);
5860 newname
= ggc_strdup (tempname
);
5863 /* We need sth that can be pointed to for va_start. */
5864 decl
= build_fake_var_decl (ptr_type_node
);
5866 argvi
= new_var_info (decl
, newname
, false);
5867 argvi
->offset
= fi_parm_base
+ num_args
;
5869 argvi
->is_full_var
= true;
5870 argvi
->is_heap_var
= true;
5871 argvi
->fullsize
= vi
->fullsize
;
5874 && argvi
->may_have_pointers
)
5875 make_constraint_from (argvi
, nonlocal_id
);
5877 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5878 prev_vi
->next
= argvi
->id
;
5886 /* Return true if FIELDSTACK contains fields that overlap.
5887 FIELDSTACK is assumed to be sorted by offset. */
5890 check_for_overlaps (vec
<fieldoff_s
> fieldstack
)
5892 fieldoff_s
*fo
= NULL
;
5894 HOST_WIDE_INT lastoffset
= -1;
5896 FOR_EACH_VEC_ELT (fieldstack
, i
, fo
)
5898 if (fo
->offset
== lastoffset
)
5900 lastoffset
= fo
->offset
;
5905 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5906 This will also create any varinfo structures necessary for fields
5907 of DECL. DECL is a function parameter if HANDLE_PARAM is set.
5908 HANDLED_STRUCT_TYPE is used to register struct types reached by following
5909 restrict pointers. This is needed to prevent infinite recursion. */
5912 create_variable_info_for_1 (tree decl
, const char *name
, bool add_id
,
5913 bool handle_param
, bitmap handled_struct_type
)
5915 varinfo_t vi
, newvi
;
5916 tree decl_type
= TREE_TYPE (decl
);
5917 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decl_type
);
5918 auto_vec
<fieldoff_s
> fieldstack
;
5923 || !tree_fits_uhwi_p (declsize
))
5925 vi
= new_var_info (decl
, name
, add_id
);
5929 vi
->is_unknown_size_var
= true;
5930 vi
->is_full_var
= true;
5931 vi
->may_have_pointers
= true;
5935 /* Collect field information. */
5936 if (use_field_sensitive
5937 && var_can_have_subvars (decl
)
5938 /* ??? Force us to not use subfields for globals in IPA mode.
5939 Else we'd have to parse arbitrary initializers. */
5941 && is_global_var (decl
)))
5943 fieldoff_s
*fo
= NULL
;
5944 bool notokay
= false;
5947 push_fields_onto_fieldstack (decl_type
, &fieldstack
, 0);
5949 for (i
= 0; !notokay
&& fieldstack
.iterate (i
, &fo
); i
++)
5950 if (fo
->has_unknown_size
5957 /* We can't sort them if we have a field with a variable sized type,
5958 which will make notokay = true. In that case, we are going to return
5959 without creating varinfos for the fields anyway, so sorting them is a
5963 sort_fieldstack (fieldstack
);
5964 /* Due to some C++ FE issues, like PR 22488, we might end up
5965 what appear to be overlapping fields even though they,
5966 in reality, do not overlap. Until the C++ FE is fixed,
5967 we will simply disable field-sensitivity for these cases. */
5968 notokay
= check_for_overlaps (fieldstack
);
5972 fieldstack
.release ();
5975 /* If we didn't end up collecting sub-variables create a full
5976 variable for the decl. */
5977 if (fieldstack
.length () == 0
5978 || fieldstack
.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5980 vi
= new_var_info (decl
, name
, add_id
);
5982 vi
->may_have_pointers
= true;
5983 vi
->fullsize
= tree_to_uhwi (declsize
);
5984 vi
->size
= vi
->fullsize
;
5985 vi
->is_full_var
= true;
5986 if (POINTER_TYPE_P (decl_type
)
5987 && TYPE_RESTRICT (decl_type
))
5988 vi
->only_restrict_pointers
= 1;
5989 if (vi
->only_restrict_pointers
5990 && !type_contains_placeholder_p (TREE_TYPE (decl_type
))
5992 && !bitmap_bit_p (handled_struct_type
,
5993 TYPE_UID (TREE_TYPE (decl_type
))))
5996 tree heapvar
= build_fake_var_decl (TREE_TYPE (decl_type
));
5997 DECL_EXTERNAL (heapvar
) = 1;
5998 if (var_can_have_subvars (heapvar
))
5999 bitmap_set_bit (handled_struct_type
,
6000 TYPE_UID (TREE_TYPE (decl_type
)));
6001 rvi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS", true,
6002 true, handled_struct_type
);
6003 if (var_can_have_subvars (heapvar
))
6004 bitmap_clear_bit (handled_struct_type
,
6005 TYPE_UID (TREE_TYPE (decl_type
)));
6006 rvi
->is_restrict_var
= 1;
6007 insert_vi_for_tree (heapvar
, rvi
);
6008 make_constraint_from (vi
, rvi
->id
);
6009 make_param_constraints (rvi
);
6011 fieldstack
.release ();
6015 vi
= new_var_info (decl
, name
, add_id
);
6016 vi
->fullsize
= tree_to_uhwi (declsize
);
6017 if (fieldstack
.length () == 1)
6018 vi
->is_full_var
= true;
6019 for (i
= 0, newvi
= vi
;
6020 fieldstack
.iterate (i
, &fo
);
6021 ++i
, newvi
= vi_next (newvi
))
6023 const char *newname
= NULL
;
6028 if (fieldstack
.length () != 1)
6031 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC
6032 "+" HOST_WIDE_INT_PRINT_DEC
, name
,
6033 fo
->offset
, fo
->size
);
6034 newname
= ggc_strdup (tempname
);
6042 newvi
->name
= newname
;
6043 newvi
->offset
= fo
->offset
;
6044 newvi
->size
= fo
->size
;
6045 newvi
->fullsize
= vi
->fullsize
;
6046 newvi
->may_have_pointers
= fo
->may_have_pointers
;
6047 newvi
->only_restrict_pointers
= fo
->only_restrict_pointers
;
6049 && newvi
->only_restrict_pointers
6050 && !type_contains_placeholder_p (fo
->restrict_pointed_type
)
6051 && !bitmap_bit_p (handled_struct_type
,
6052 TYPE_UID (fo
->restrict_pointed_type
)))
6055 tree heapvar
= build_fake_var_decl (fo
->restrict_pointed_type
);
6056 DECL_EXTERNAL (heapvar
) = 1;
6057 if (var_can_have_subvars (heapvar
))
6058 bitmap_set_bit (handled_struct_type
,
6059 TYPE_UID (fo
->restrict_pointed_type
));
6060 rvi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS", true,
6061 true, handled_struct_type
);
6062 if (var_can_have_subvars (heapvar
))
6063 bitmap_clear_bit (handled_struct_type
,
6064 TYPE_UID (fo
->restrict_pointed_type
));
6065 rvi
->is_restrict_var
= 1;
6066 insert_vi_for_tree (heapvar
, rvi
);
6067 make_constraint_from (newvi
, rvi
->id
);
6068 make_param_constraints (rvi
);
6070 if (i
+ 1 < fieldstack
.length ())
6072 varinfo_t tem
= new_var_info (decl
, name
, false);
6073 newvi
->next
= tem
->id
;
6082 create_variable_info_for (tree decl
, const char *name
, bool add_id
)
6084 varinfo_t vi
= create_variable_info_for_1 (decl
, name
, add_id
, false, NULL
);
6085 unsigned int id
= vi
->id
;
6087 insert_vi_for_tree (decl
, vi
);
6092 /* Create initial constraints for globals. */
6093 for (; vi
; vi
= vi_next (vi
))
6095 if (!vi
->may_have_pointers
6096 || !vi
->is_global_var
)
6099 /* Mark global restrict qualified pointers. */
6100 if ((POINTER_TYPE_P (TREE_TYPE (decl
))
6101 && TYPE_RESTRICT (TREE_TYPE (decl
)))
6102 || vi
->only_restrict_pointers
)
6105 = make_constraint_from_global_restrict (vi
, "GLOBAL_RESTRICT",
6107 /* ??? For now exclude reads from globals as restrict sources
6108 if those are not (indirectly) from incoming parameters. */
6109 rvi
->is_restrict_var
= false;
6113 /* In non-IPA mode the initializer from nonlocal is all we need. */
6115 || DECL_HARD_REGISTER (decl
))
6116 make_copy_constraint (vi
, nonlocal_id
);
6118 /* In IPA mode parse the initializer and generate proper constraints
6122 varpool_node
*vnode
= varpool_node::get (decl
);
6124 /* For escaped variables initialize them from nonlocal. */
6125 if (!vnode
->all_refs_explicit_p ())
6126 make_copy_constraint (vi
, nonlocal_id
);
6128 /* If this is a global variable with an initializer and we are in
6129 IPA mode generate constraints for it. */
6131 for (unsigned idx
= 0; vnode
->iterate_reference (idx
, ref
); ++idx
)
6133 auto_vec
<ce_s
> rhsc
;
6134 struct constraint_expr lhs
, *rhsp
;
6136 get_constraint_for_address_of (ref
->referred
->decl
, &rhsc
);
6140 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
6141 process_constraint (new_constraint (lhs
, *rhsp
));
6142 /* If this is a variable that escapes from the unit
6143 the initializer escapes as well. */
6144 if (!vnode
->all_refs_explicit_p ())
6146 lhs
.var
= escaped_id
;
6149 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
6150 process_constraint (new_constraint (lhs
, *rhsp
));
6159 /* Print out the points-to solution for VAR to FILE. */
6162 dump_solution_for_var (FILE *file
, unsigned int var
)
6164 varinfo_t vi
= get_varinfo (var
);
6168 /* Dump the solution for unified vars anyway, this avoids difficulties
6169 in scanning dumps in the testsuite. */
6170 fprintf (file
, "%s = { ", vi
->name
);
6171 vi
= get_varinfo (find (var
));
6172 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6173 fprintf (file
, "%s ", get_varinfo (i
)->name
);
6174 fprintf (file
, "}");
6176 /* But note when the variable was unified. */
6178 fprintf (file
, " same as %s", vi
->name
);
6180 fprintf (file
, "\n");
6183 /* Print the points-to solution for VAR to stderr. */
6186 debug_solution_for_var (unsigned int var
)
6188 dump_solution_for_var (stderr
, var
);
6191 /* Register the constraints for function parameter related VI. */
6194 make_param_constraints (varinfo_t vi
)
6196 for (; vi
; vi
= vi_next (vi
))
6198 if (vi
->only_restrict_pointers
)
6200 else if (vi
->may_have_pointers
)
6201 make_constraint_from (vi
, nonlocal_id
);
6203 if (vi
->is_full_var
)
6208 /* Create varinfo structures for all of the variables in the
6209 function for intraprocedural mode. */
6212 intra_create_variable_infos (struct function
*fn
)
6215 bitmap handled_struct_type
= NULL
;
6217 /* For each incoming pointer argument arg, create the constraint ARG
6218 = NONLOCAL or a dummy variable if it is a restrict qualified
6219 passed-by-reference argument. */
6220 for (t
= DECL_ARGUMENTS (fn
->decl
); t
; t
= DECL_CHAIN (t
))
6222 if (handled_struct_type
== NULL
)
6223 handled_struct_type
= BITMAP_ALLOC (NULL
);
6226 = create_variable_info_for_1 (t
, alias_get_name (t
), false, true,
6227 handled_struct_type
);
6228 insert_vi_for_tree (t
, p
);
6230 make_param_constraints (p
);
6233 if (handled_struct_type
!= NULL
)
6234 BITMAP_FREE (handled_struct_type
);
6236 /* Add a constraint for a result decl that is passed by reference. */
6237 if (DECL_RESULT (fn
->decl
)
6238 && DECL_BY_REFERENCE (DECL_RESULT (fn
->decl
)))
6240 varinfo_t p
, result_vi
= get_vi_for_tree (DECL_RESULT (fn
->decl
));
6242 for (p
= result_vi
; p
; p
= vi_next (p
))
6243 make_constraint_from (p
, nonlocal_id
);
6246 /* Add a constraint for the incoming static chain parameter. */
6247 if (fn
->static_chain_decl
!= NULL_TREE
)
6249 varinfo_t p
, chain_vi
= get_vi_for_tree (fn
->static_chain_decl
);
6251 for (p
= chain_vi
; p
; p
= vi_next (p
))
6252 make_constraint_from (p
, nonlocal_id
);
6256 /* Structure used to put solution bitmaps in a hashtable so they can
6257 be shared among variables with the same points-to set. */
6259 typedef struct shared_bitmap_info
6263 } *shared_bitmap_info_t
;
6264 typedef const struct shared_bitmap_info
*const_shared_bitmap_info_t
;
6266 /* Shared_bitmap hashtable helpers. */
6268 struct shared_bitmap_hasher
: free_ptr_hash
<shared_bitmap_info
>
6270 static inline hashval_t
hash (const shared_bitmap_info
*);
6271 static inline bool equal (const shared_bitmap_info
*,
6272 const shared_bitmap_info
*);
6275 /* Hash function for a shared_bitmap_info_t */
6278 shared_bitmap_hasher::hash (const shared_bitmap_info
*bi
)
6280 return bi
->hashcode
;
6283 /* Equality function for two shared_bitmap_info_t's. */
6286 shared_bitmap_hasher::equal (const shared_bitmap_info
*sbi1
,
6287 const shared_bitmap_info
*sbi2
)
6289 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
6292 /* Shared_bitmap hashtable. */
6294 static hash_table
<shared_bitmap_hasher
> *shared_bitmap_table
;
6296 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
6297 existing instance if there is one, NULL otherwise. */
6300 shared_bitmap_lookup (bitmap pt_vars
)
6302 shared_bitmap_info
**slot
;
6303 struct shared_bitmap_info sbi
;
6305 sbi
.pt_vars
= pt_vars
;
6306 sbi
.hashcode
= bitmap_hash (pt_vars
);
6308 slot
= shared_bitmap_table
->find_slot (&sbi
, NO_INSERT
);
6312 return (*slot
)->pt_vars
;
6316 /* Add a bitmap to the shared bitmap hashtable. */
6319 shared_bitmap_add (bitmap pt_vars
)
6321 shared_bitmap_info
**slot
;
6322 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
6324 sbi
->pt_vars
= pt_vars
;
6325 sbi
->hashcode
= bitmap_hash (pt_vars
);
6327 slot
= shared_bitmap_table
->find_slot (sbi
, INSERT
);
6328 gcc_assert (!*slot
);
6333 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
6336 set_uids_in_ptset (bitmap into
, bitmap from
, struct pt_solution
*pt
,
6341 varinfo_t escaped_vi
= get_varinfo (find (escaped_id
));
6342 bool everything_escaped
6343 = escaped_vi
->solution
&& bitmap_bit_p (escaped_vi
->solution
, anything_id
);
6345 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
6347 varinfo_t vi
= get_varinfo (i
);
6349 /* The only artificial variables that are allowed in a may-alias
6350 set are heap variables. */
6351 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
6354 if (everything_escaped
6355 || (escaped_vi
->solution
6356 && bitmap_bit_p (escaped_vi
->solution
, i
)))
6358 pt
->vars_contains_escaped
= true;
6359 pt
->vars_contains_escaped_heap
= vi
->is_heap_var
;
6362 if (vi
->is_restrict_var
)
6363 pt
->vars_contains_restrict
= true;
6365 if (VAR_P (vi
->decl
)
6366 || TREE_CODE (vi
->decl
) == PARM_DECL
6367 || TREE_CODE (vi
->decl
) == RESULT_DECL
)
6369 /* If we are in IPA mode we will not recompute points-to
6370 sets after inlining so make sure they stay valid. */
6372 && !DECL_PT_UID_SET_P (vi
->decl
))
6373 SET_DECL_PT_UID (vi
->decl
, DECL_UID (vi
->decl
));
6375 /* Add the decl to the points-to set. Note that the points-to
6376 set contains global variables. */
6377 bitmap_set_bit (into
, DECL_PT_UID (vi
->decl
));
6378 if (vi
->is_global_var
6379 /* In IPA mode the escaped_heap trick doesn't work as
6380 ESCAPED is escaped from the unit but
6381 pt_solution_includes_global needs to answer true for
6382 all variables not automatic within a function.
6383 For the same reason is_global_var is not the
6384 correct flag to track - local variables from other
6385 functions also need to be considered global.
6386 Conveniently all HEAP vars are not put in function
6390 && ! auto_var_in_fn_p (vi
->decl
, fndecl
)))
6391 pt
->vars_contains_nonlocal
= true;
6393 /* If we have a variable that is interposable record that fact
6394 for pointer comparison simplification. */
6395 if (VAR_P (vi
->decl
)
6396 && (TREE_STATIC (vi
->decl
) || DECL_EXTERNAL (vi
->decl
))
6397 && ! decl_binds_to_current_def_p (vi
->decl
))
6398 pt
->vars_contains_interposable
= true;
6401 else if (TREE_CODE (vi
->decl
) == FUNCTION_DECL
6402 || TREE_CODE (vi
->decl
) == LABEL_DECL
)
6404 /* Nothing should read/write from/to code so we can
6405 save bits by not including them in the points-to bitmaps.
6406 Still mark the points-to set as containing global memory
6407 to make code-patching possible - see PR70128. */
6408 pt
->vars_contains_nonlocal
= true;
6414 /* Compute the points-to solution *PT for the variable VI. */
6416 static struct pt_solution
6417 find_what_var_points_to (tree fndecl
, varinfo_t orig_vi
)
6421 bitmap finished_solution
;
6424 struct pt_solution
*pt
;
6426 /* This variable may have been collapsed, let's get the real
6428 vi
= get_varinfo (find (orig_vi
->id
));
6430 /* See if we have already computed the solution and return it. */
6431 pt_solution
**slot
= &final_solutions
->get_or_insert (vi
);
6435 *slot
= pt
= XOBNEW (&final_solutions_obstack
, struct pt_solution
);
6436 memset (pt
, 0, sizeof (struct pt_solution
));
6438 /* Translate artificial variables into SSA_NAME_PTR_INFO
6440 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6442 varinfo_t vi
= get_varinfo (i
);
6444 if (vi
->is_artificial_var
)
6446 if (vi
->id
== nothing_id
)
6448 else if (vi
->id
== escaped_id
)
6451 pt
->ipa_escaped
= 1;
6454 /* Expand some special vars of ESCAPED in-place here. */
6455 varinfo_t evi
= get_varinfo (find (escaped_id
));
6456 if (bitmap_bit_p (evi
->solution
, nonlocal_id
))
6459 else if (vi
->id
== nonlocal_id
)
6461 else if (vi
->is_heap_var
)
6462 /* We represent heapvars in the points-to set properly. */
6464 else if (vi
->id
== string_id
)
6465 /* Nobody cares - STRING_CSTs are read-only entities. */
6467 else if (vi
->id
== anything_id
6468 || vi
->id
== integer_id
)
6473 /* Instead of doing extra work, simply do not create
6474 elaborate points-to information for pt_anything pointers. */
6478 /* Share the final set of variables when possible. */
6479 finished_solution
= BITMAP_GGC_ALLOC ();
6480 stats
.points_to_sets_created
++;
6482 set_uids_in_ptset (finished_solution
, vi
->solution
, pt
, fndecl
);
6483 result
= shared_bitmap_lookup (finished_solution
);
6486 shared_bitmap_add (finished_solution
);
6487 pt
->vars
= finished_solution
;
6492 bitmap_clear (finished_solution
);
6498 /* Given a pointer variable P, fill in its points-to set. */
6501 find_what_p_points_to (tree fndecl
, tree p
)
6503 struct ptr_info_def
*pi
;
6506 bool nonnull
= get_ptr_nonnull (p
);
6508 /* For parameters, get at the points-to set for the actual parm
6510 if (TREE_CODE (p
) == SSA_NAME
6511 && SSA_NAME_IS_DEFAULT_DEF (p
)
6512 && (TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
6513 || TREE_CODE (SSA_NAME_VAR (p
)) == RESULT_DECL
))
6514 lookup_p
= SSA_NAME_VAR (p
);
6516 vi
= lookup_vi_for_tree (lookup_p
);
6520 pi
= get_ptr_info (p
);
6521 pi
->pt
= find_what_var_points_to (fndecl
, vi
);
6522 /* Conservatively set to NULL from PTA (to true). */
6524 /* Preserve pointer nonnull computed by VRP. See get_ptr_nonnull
6525 in gcc/tree-ssaname.c for more information. */
6527 set_ptr_nonnull (p
);
6531 /* Query statistics for points-to solutions. */
6534 unsigned HOST_WIDE_INT pt_solution_includes_may_alias
;
6535 unsigned HOST_WIDE_INT pt_solution_includes_no_alias
;
6536 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias
;
6537 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias
;
6541 dump_pta_stats (FILE *s
)
6543 fprintf (s
, "\nPTA query stats:\n");
6544 fprintf (s
, " pt_solution_includes: "
6545 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6546 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6547 pta_stats
.pt_solution_includes_no_alias
,
6548 pta_stats
.pt_solution_includes_no_alias
6549 + pta_stats
.pt_solution_includes_may_alias
);
6550 fprintf (s
, " pt_solutions_intersect: "
6551 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6552 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6553 pta_stats
.pt_solutions_intersect_no_alias
,
6554 pta_stats
.pt_solutions_intersect_no_alias
6555 + pta_stats
.pt_solutions_intersect_may_alias
);
6559 /* Reset the points-to solution *PT to a conservative default
6560 (point to anything). */
6563 pt_solution_reset (struct pt_solution
*pt
)
6565 memset (pt
, 0, sizeof (struct pt_solution
));
6566 pt
->anything
= true;
6570 /* Set the points-to solution *PT to point only to the variables
6571 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6572 global variables and VARS_CONTAINS_RESTRICT specifies whether
6573 it contains restrict tag variables. */
6576 pt_solution_set (struct pt_solution
*pt
, bitmap vars
,
6577 bool vars_contains_nonlocal
)
6579 memset (pt
, 0, sizeof (struct pt_solution
));
6581 pt
->vars_contains_nonlocal
= vars_contains_nonlocal
;
6582 pt
->vars_contains_escaped
6583 = (cfun
->gimple_df
->escaped
.anything
6584 || bitmap_intersect_p (cfun
->gimple_df
->escaped
.vars
, vars
));
6587 /* Set the points-to solution *PT to point only to the variable VAR. */
6590 pt_solution_set_var (struct pt_solution
*pt
, tree var
)
6592 memset (pt
, 0, sizeof (struct pt_solution
));
6593 pt
->vars
= BITMAP_GGC_ALLOC ();
6594 bitmap_set_bit (pt
->vars
, DECL_PT_UID (var
));
6595 pt
->vars_contains_nonlocal
= is_global_var (var
);
6596 pt
->vars_contains_escaped
6597 = (cfun
->gimple_df
->escaped
.anything
6598 || bitmap_bit_p (cfun
->gimple_df
->escaped
.vars
, DECL_PT_UID (var
)));
6601 /* Computes the union of the points-to solutions *DEST and *SRC and
6602 stores the result in *DEST. This changes the points-to bitmap
6603 of *DEST and thus may not be used if that might be shared.
6604 The points-to bitmap of *SRC and *DEST will not be shared after
6605 this function if they were not before. */
6608 pt_solution_ior_into (struct pt_solution
*dest
, struct pt_solution
*src
)
6610 dest
->anything
|= src
->anything
;
6613 pt_solution_reset (dest
);
6617 dest
->nonlocal
|= src
->nonlocal
;
6618 dest
->escaped
|= src
->escaped
;
6619 dest
->ipa_escaped
|= src
->ipa_escaped
;
6620 dest
->null
|= src
->null
;
6621 dest
->vars_contains_nonlocal
|= src
->vars_contains_nonlocal
;
6622 dest
->vars_contains_escaped
|= src
->vars_contains_escaped
;
6623 dest
->vars_contains_escaped_heap
|= src
->vars_contains_escaped_heap
;
6628 dest
->vars
= BITMAP_GGC_ALLOC ();
6629 bitmap_ior_into (dest
->vars
, src
->vars
);
6632 /* Return true if the points-to solution *PT is empty. */
6635 pt_solution_empty_p (struct pt_solution
*pt
)
6642 && !bitmap_empty_p (pt
->vars
))
6645 /* If the solution includes ESCAPED, check if that is empty. */
6647 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
6650 /* If the solution includes ESCAPED, check if that is empty. */
6652 && !pt_solution_empty_p (&ipa_escaped_pt
))
6658 /* Return true if the points-to solution *PT only point to a single var, and
6659 return the var uid in *UID. */
6662 pt_solution_singleton_or_null_p (struct pt_solution
*pt
, unsigned *uid
)
6664 if (pt
->anything
|| pt
->nonlocal
|| pt
->escaped
|| pt
->ipa_escaped
6666 || !bitmap_single_bit_set_p (pt
->vars
))
6669 *uid
= bitmap_first_set_bit (pt
->vars
);
6673 /* Return true if the points-to solution *PT includes global memory. */
6676 pt_solution_includes_global (struct pt_solution
*pt
)
6680 || pt
->vars_contains_nonlocal
6681 /* The following is a hack to make the malloc escape hack work.
6682 In reality we'd need different sets for escaped-through-return
6683 and escaped-to-callees and passes would need to be updated. */
6684 || pt
->vars_contains_escaped_heap
)
6687 /* 'escaped' is also a placeholder so we have to look into it. */
6689 return pt_solution_includes_global (&cfun
->gimple_df
->escaped
);
6691 if (pt
->ipa_escaped
)
6692 return pt_solution_includes_global (&ipa_escaped_pt
);
6697 /* Return true if the points-to solution *PT includes the variable
6698 declaration DECL. */
6701 pt_solution_includes_1 (struct pt_solution
*pt
, const_tree decl
)
6707 && is_global_var (decl
))
6711 && bitmap_bit_p (pt
->vars
, DECL_PT_UID (decl
)))
6714 /* If the solution includes ESCAPED, check it. */
6716 && pt_solution_includes_1 (&cfun
->gimple_df
->escaped
, decl
))
6719 /* If the solution includes ESCAPED, check it. */
6721 && pt_solution_includes_1 (&ipa_escaped_pt
, decl
))
6728 pt_solution_includes (struct pt_solution
*pt
, const_tree decl
)
6730 bool res
= pt_solution_includes_1 (pt
, decl
);
6732 ++pta_stats
.pt_solution_includes_may_alias
;
6734 ++pta_stats
.pt_solution_includes_no_alias
;
6738 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6742 pt_solutions_intersect_1 (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6744 if (pt1
->anything
|| pt2
->anything
)
6747 /* If either points to unknown global memory and the other points to
6748 any global memory they alias. */
6751 || pt2
->vars_contains_nonlocal
))
6753 && pt1
->vars_contains_nonlocal
))
6756 /* If either points to all escaped memory and the other points to
6757 any escaped memory they alias. */
6760 || pt2
->vars_contains_escaped
))
6762 && pt1
->vars_contains_escaped
))
6765 /* Check the escaped solution if required.
6766 ??? Do we need to check the local against the IPA escaped sets? */
6767 if ((pt1
->ipa_escaped
|| pt2
->ipa_escaped
)
6768 && !pt_solution_empty_p (&ipa_escaped_pt
))
6770 /* If both point to escaped memory and that solution
6771 is not empty they alias. */
6772 if (pt1
->ipa_escaped
&& pt2
->ipa_escaped
)
6775 /* If either points to escaped memory see if the escaped solution
6776 intersects with the other. */
6777 if ((pt1
->ipa_escaped
6778 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt2
))
6779 || (pt2
->ipa_escaped
6780 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt1
)))
6784 /* Now both pointers alias if their points-to solution intersects. */
6787 && bitmap_intersect_p (pt1
->vars
, pt2
->vars
));
6791 pt_solutions_intersect (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6793 bool res
= pt_solutions_intersect_1 (pt1
, pt2
);
6795 ++pta_stats
.pt_solutions_intersect_may_alias
;
6797 ++pta_stats
.pt_solutions_intersect_no_alias
;
6802 /* Dump points-to information to OUTFILE. */
6805 dump_sa_points_to_info (FILE *outfile
)
6809 fprintf (outfile
, "\nPoints-to sets\n\n");
6811 if (dump_flags
& TDF_STATS
)
6813 fprintf (outfile
, "Stats:\n");
6814 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
6815 fprintf (outfile
, "Non-pointer vars: %d\n",
6816 stats
.nonpointer_vars
);
6817 fprintf (outfile
, "Statically unified vars: %d\n",
6818 stats
.unified_vars_static
);
6819 fprintf (outfile
, "Dynamically unified vars: %d\n",
6820 stats
.unified_vars_dynamic
);
6821 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
6822 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
6823 fprintf (outfile
, "Number of implicit edges: %d\n",
6824 stats
.num_implicit_edges
);
6827 for (i
= 1; i
< varmap
.length (); i
++)
6829 varinfo_t vi
= get_varinfo (i
);
6830 if (!vi
->may_have_pointers
)
6832 dump_solution_for_var (outfile
, i
);
6837 /* Debug points-to information to stderr. */
6840 debug_sa_points_to_info (void)
6842 dump_sa_points_to_info (stderr
);
6846 /* Initialize the always-existing constraint variables for NULL
6847 ANYTHING, READONLY, and INTEGER */
6850 init_base_vars (void)
6852 struct constraint_expr lhs
, rhs
;
6853 varinfo_t var_anything
;
6854 varinfo_t var_nothing
;
6855 varinfo_t var_string
;
6856 varinfo_t var_escaped
;
6857 varinfo_t var_nonlocal
;
6858 varinfo_t var_storedanything
;
6859 varinfo_t var_integer
;
6861 /* Variable ID zero is reserved and should be NULL. */
6862 varmap
.safe_push (NULL
);
6864 /* Create the NULL variable, used to represent that a variable points
6866 var_nothing
= new_var_info (NULL_TREE
, "NULL", false);
6867 gcc_assert (var_nothing
->id
== nothing_id
);
6868 var_nothing
->is_artificial_var
= 1;
6869 var_nothing
->offset
= 0;
6870 var_nothing
->size
= ~0;
6871 var_nothing
->fullsize
= ~0;
6872 var_nothing
->is_special_var
= 1;
6873 var_nothing
->may_have_pointers
= 0;
6874 var_nothing
->is_global_var
= 0;
6876 /* Create the ANYTHING variable, used to represent that a variable
6877 points to some unknown piece of memory. */
6878 var_anything
= new_var_info (NULL_TREE
, "ANYTHING", false);
6879 gcc_assert (var_anything
->id
== anything_id
);
6880 var_anything
->is_artificial_var
= 1;
6881 var_anything
->size
= ~0;
6882 var_anything
->offset
= 0;
6883 var_anything
->fullsize
= ~0;
6884 var_anything
->is_special_var
= 1;
6886 /* Anything points to anything. This makes deref constraints just
6887 work in the presence of linked list and other p = *p type loops,
6888 by saying that *ANYTHING = ANYTHING. */
6890 lhs
.var
= anything_id
;
6892 rhs
.type
= ADDRESSOF
;
6893 rhs
.var
= anything_id
;
6896 /* This specifically does not use process_constraint because
6897 process_constraint ignores all anything = anything constraints, since all
6898 but this one are redundant. */
6899 constraints
.safe_push (new_constraint (lhs
, rhs
));
6901 /* Create the STRING variable, used to represent that a variable
6902 points to a string literal. String literals don't contain
6903 pointers so STRING doesn't point to anything. */
6904 var_string
= new_var_info (NULL_TREE
, "STRING", false);
6905 gcc_assert (var_string
->id
== string_id
);
6906 var_string
->is_artificial_var
= 1;
6907 var_string
->offset
= 0;
6908 var_string
->size
= ~0;
6909 var_string
->fullsize
= ~0;
6910 var_string
->is_special_var
= 1;
6911 var_string
->may_have_pointers
= 0;
6913 /* Create the ESCAPED variable, used to represent the set of escaped
6915 var_escaped
= new_var_info (NULL_TREE
, "ESCAPED", false);
6916 gcc_assert (var_escaped
->id
== escaped_id
);
6917 var_escaped
->is_artificial_var
= 1;
6918 var_escaped
->offset
= 0;
6919 var_escaped
->size
= ~0;
6920 var_escaped
->fullsize
= ~0;
6921 var_escaped
->is_special_var
= 0;
6923 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6925 var_nonlocal
= new_var_info (NULL_TREE
, "NONLOCAL", false);
6926 gcc_assert (var_nonlocal
->id
== nonlocal_id
);
6927 var_nonlocal
->is_artificial_var
= 1;
6928 var_nonlocal
->offset
= 0;
6929 var_nonlocal
->size
= ~0;
6930 var_nonlocal
->fullsize
= ~0;
6931 var_nonlocal
->is_special_var
= 1;
6933 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6935 lhs
.var
= escaped_id
;
6938 rhs
.var
= escaped_id
;
6940 process_constraint (new_constraint (lhs
, rhs
));
6942 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6943 whole variable escapes. */
6945 lhs
.var
= escaped_id
;
6948 rhs
.var
= escaped_id
;
6949 rhs
.offset
= UNKNOWN_OFFSET
;
6950 process_constraint (new_constraint (lhs
, rhs
));
6952 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6953 everything pointed to by escaped points to what global memory can
6956 lhs
.var
= escaped_id
;
6959 rhs
.var
= nonlocal_id
;
6961 process_constraint (new_constraint (lhs
, rhs
));
6963 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6964 global memory may point to global memory and escaped memory. */
6966 lhs
.var
= nonlocal_id
;
6968 rhs
.type
= ADDRESSOF
;
6969 rhs
.var
= nonlocal_id
;
6971 process_constraint (new_constraint (lhs
, rhs
));
6972 rhs
.type
= ADDRESSOF
;
6973 rhs
.var
= escaped_id
;
6975 process_constraint (new_constraint (lhs
, rhs
));
6977 /* Create the STOREDANYTHING variable, used to represent the set of
6978 variables stored to *ANYTHING. */
6979 var_storedanything
= new_var_info (NULL_TREE
, "STOREDANYTHING", false);
6980 gcc_assert (var_storedanything
->id
== storedanything_id
);
6981 var_storedanything
->is_artificial_var
= 1;
6982 var_storedanything
->offset
= 0;
6983 var_storedanything
->size
= ~0;
6984 var_storedanything
->fullsize
= ~0;
6985 var_storedanything
->is_special_var
= 0;
6987 /* Create the INTEGER variable, used to represent that a variable points
6988 to what an INTEGER "points to". */
6989 var_integer
= new_var_info (NULL_TREE
, "INTEGER", false);
6990 gcc_assert (var_integer
->id
== integer_id
);
6991 var_integer
->is_artificial_var
= 1;
6992 var_integer
->size
= ~0;
6993 var_integer
->fullsize
= ~0;
6994 var_integer
->offset
= 0;
6995 var_integer
->is_special_var
= 1;
6997 /* INTEGER = ANYTHING, because we don't know where a dereference of
6998 a random integer will point to. */
7000 lhs
.var
= integer_id
;
7002 rhs
.type
= ADDRESSOF
;
7003 rhs
.var
= anything_id
;
7005 process_constraint (new_constraint (lhs
, rhs
));
7008 /* Initialize things necessary to perform PTA */
7011 init_alias_vars (void)
7013 use_field_sensitive
= (MAX_FIELDS_FOR_FIELD_SENSITIVE
> 1);
7015 bitmap_obstack_initialize (&pta_obstack
);
7016 bitmap_obstack_initialize (&oldpta_obstack
);
7017 bitmap_obstack_initialize (&predbitmap_obstack
);
7019 constraints
.create (8);
7021 vi_for_tree
= new hash_map
<tree
, varinfo_t
>;
7022 call_stmt_vars
= new hash_map
<gimple
*, varinfo_t
>;
7024 memset (&stats
, 0, sizeof (stats
));
7025 shared_bitmap_table
= new hash_table
<shared_bitmap_hasher
> (511);
7028 gcc_obstack_init (&fake_var_decl_obstack
);
7030 final_solutions
= new hash_map
<varinfo_t
, pt_solution
*>;
7031 gcc_obstack_init (&final_solutions_obstack
);
7034 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
7035 predecessor edges. */
7038 remove_preds_and_fake_succs (constraint_graph_t graph
)
7042 /* Clear the implicit ref and address nodes from the successor
7044 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
7046 if (graph
->succs
[i
])
7047 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
7048 FIRST_REF_NODE
* 2);
7051 /* Free the successor list for the non-ref nodes. */
7052 for (i
= FIRST_REF_NODE
+ 1; i
< graph
->size
; i
++)
7054 if (graph
->succs
[i
])
7055 BITMAP_FREE (graph
->succs
[i
]);
7058 /* Now reallocate the size of the successor list as, and blow away
7059 the predecessor bitmaps. */
7060 graph
->size
= varmap
.length ();
7061 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
7063 free (graph
->implicit_preds
);
7064 graph
->implicit_preds
= NULL
;
7065 free (graph
->preds
);
7066 graph
->preds
= NULL
;
7067 bitmap_obstack_release (&predbitmap_obstack
);
7070 /* Solve the constraint set. */
7073 solve_constraints (void)
7075 struct scc_info
*si
;
7079 "\nCollapsing static cycles and doing variable "
7082 init_graph (varmap
.length () * 2);
7085 fprintf (dump_file
, "Building predecessor graph\n");
7086 build_pred_graph ();
7089 fprintf (dump_file
, "Detecting pointer and location "
7091 si
= perform_var_substitution (graph
);
7094 fprintf (dump_file
, "Rewriting constraints and unifying "
7096 rewrite_constraints (graph
, si
);
7098 build_succ_graph ();
7100 free_var_substitution_info (si
);
7102 /* Attach complex constraints to graph nodes. */
7103 move_complex_constraints (graph
);
7106 fprintf (dump_file
, "Uniting pointer but not location equivalent "
7108 unite_pointer_equivalences (graph
);
7111 fprintf (dump_file
, "Finding indirect cycles\n");
7112 find_indirect_cycles (graph
);
7114 /* Implicit nodes and predecessors are no longer necessary at this
7116 remove_preds_and_fake_succs (graph
);
7118 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
7120 fprintf (dump_file
, "\n\n// The constraint graph before solve-graph "
7121 "in dot format:\n");
7122 dump_constraint_graph (dump_file
);
7123 fprintf (dump_file
, "\n\n");
7127 fprintf (dump_file
, "Solving graph\n");
7129 solve_graph (graph
);
7131 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
7133 fprintf (dump_file
, "\n\n// The constraint graph after solve-graph "
7134 "in dot format:\n");
7135 dump_constraint_graph (dump_file
);
7136 fprintf (dump_file
, "\n\n");
7140 dump_sa_points_to_info (dump_file
);
7143 /* Create points-to sets for the current function. See the comments
7144 at the start of the file for an algorithmic overview. */
7147 compute_points_to_sets (void)
7152 timevar_push (TV_TREE_PTA
);
7156 intra_create_variable_infos (cfun
);
7158 /* Now walk all statements and build the constraint set. */
7159 FOR_EACH_BB_FN (bb
, cfun
)
7161 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7164 gphi
*phi
= gsi
.phi ();
7166 if (! virtual_operand_p (gimple_phi_result (phi
)))
7167 find_func_aliases (cfun
, phi
);
7170 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
7173 gimple
*stmt
= gsi_stmt (gsi
);
7175 find_func_aliases (cfun
, stmt
);
7181 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
7182 dump_constraints (dump_file
, 0);
7185 /* From the constraints compute the points-to sets. */
7186 solve_constraints ();
7188 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
7189 cfun
->gimple_df
->escaped
= find_what_var_points_to (cfun
->decl
,
7190 get_varinfo (escaped_id
));
7192 /* Make sure the ESCAPED solution (which is used as placeholder in
7193 other solutions) does not reference itself. This simplifies
7194 points-to solution queries. */
7195 cfun
->gimple_df
->escaped
.escaped
= 0;
7197 /* Compute the points-to sets for pointer SSA_NAMEs. */
7201 FOR_EACH_SSA_NAME (i
, ptr
, cfun
)
7203 if (POINTER_TYPE_P (TREE_TYPE (ptr
)))
7204 find_what_p_points_to (cfun
->decl
, ptr
);
7207 /* Compute the call-used/clobbered sets. */
7208 FOR_EACH_BB_FN (bb
, cfun
)
7210 gimple_stmt_iterator gsi
;
7212 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7215 struct pt_solution
*pt
;
7217 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
7221 pt
= gimple_call_use_set (stmt
);
7222 if (gimple_call_flags (stmt
) & ECF_CONST
)
7223 memset (pt
, 0, sizeof (struct pt_solution
));
7224 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
7226 *pt
= find_what_var_points_to (cfun
->decl
, vi
);
7227 /* Escaped (and thus nonlocal) variables are always
7228 implicitly used by calls. */
7229 /* ??? ESCAPED can be empty even though NONLOCAL
7236 /* If there is nothing special about this call then
7237 we have made everything that is used also escape. */
7238 *pt
= cfun
->gimple_df
->escaped
;
7242 pt
= gimple_call_clobber_set (stmt
);
7243 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
7244 memset (pt
, 0, sizeof (struct pt_solution
));
7245 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
7247 *pt
= find_what_var_points_to (cfun
->decl
, vi
);
7248 /* Escaped (and thus nonlocal) variables are always
7249 implicitly clobbered by calls. */
7250 /* ??? ESCAPED can be empty even though NONLOCAL
7257 /* If there is nothing special about this call then
7258 we have made everything that is used also escape. */
7259 *pt
= cfun
->gimple_df
->escaped
;
7265 timevar_pop (TV_TREE_PTA
);
7269 /* Delete created points-to sets. */
7272 delete_points_to_sets (void)
7276 delete shared_bitmap_table
;
7277 shared_bitmap_table
= NULL
;
7278 if (dump_file
&& (dump_flags
& TDF_STATS
))
7279 fprintf (dump_file
, "Points to sets created:%d\n",
7280 stats
.points_to_sets_created
);
7283 delete call_stmt_vars
;
7284 bitmap_obstack_release (&pta_obstack
);
7285 constraints
.release ();
7287 for (i
= 0; i
< graph
->size
; i
++)
7288 graph
->complex[i
].release ();
7289 free (graph
->complex);
7292 free (graph
->succs
);
7294 free (graph
->pe_rep
);
7295 free (graph
->indirect_cycles
);
7299 variable_info_pool
.release ();
7300 constraint_pool
.release ();
7302 obstack_free (&fake_var_decl_obstack
, NULL
);
7304 delete final_solutions
;
7305 obstack_free (&final_solutions_obstack
, NULL
);
7310 unsigned short clique
;
7314 /* Mark "other" loads and stores as belonging to CLIQUE and with
7318 visit_loadstore (gimple
*, tree base
, tree ref
, void *data
)
7320 unsigned short clique
= ((vls_data
*) data
)->clique
;
7321 bitmap rvars
= ((vls_data
*) data
)->rvars
;
7322 if (TREE_CODE (base
) == MEM_REF
7323 || TREE_CODE (base
) == TARGET_MEM_REF
)
7325 tree ptr
= TREE_OPERAND (base
, 0);
7326 if (TREE_CODE (ptr
) == SSA_NAME
)
7328 /* For parameters, get at the points-to set for the actual parm
7330 if (SSA_NAME_IS_DEFAULT_DEF (ptr
)
7331 && (TREE_CODE (SSA_NAME_VAR (ptr
)) == PARM_DECL
7332 || TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
))
7333 ptr
= SSA_NAME_VAR (ptr
);
7335 /* We need to make sure 'ptr' doesn't include any of
7336 the restrict tags we added bases for in its points-to set. */
7337 varinfo_t vi
= lookup_vi_for_tree (ptr
);
7341 vi
= get_varinfo (find (vi
->id
));
7342 if (bitmap_intersect_p (rvars
, vi
->solution
))
7346 /* Do not overwrite existing cliques (that includes clique, base
7347 pairs we just set). */
7348 if (MR_DEPENDENCE_CLIQUE (base
) == 0)
7350 MR_DEPENDENCE_CLIQUE (base
) = clique
;
7351 MR_DEPENDENCE_BASE (base
) = 0;
7355 /* For plain decl accesses see whether they are accesses to globals
7356 and rewrite them to MEM_REFs with { clique, 0 }. */
7358 && is_global_var (base
)
7359 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
7364 while (handled_component_p (*basep
))
7365 basep
= &TREE_OPERAND (*basep
, 0);
7366 gcc_assert (VAR_P (*basep
));
7367 tree ptr
= build_fold_addr_expr (*basep
);
7368 tree zero
= build_int_cst (TREE_TYPE (ptr
), 0);
7369 *basep
= build2 (MEM_REF
, TREE_TYPE (*basep
), ptr
, zero
);
7370 MR_DEPENDENCE_CLIQUE (*basep
) = clique
;
7371 MR_DEPENDENCE_BASE (*basep
) = 0;
7377 /* If REF is a MEM_REF then assign a clique, base pair to it, updating
7378 CLIQUE, *RESTRICT_VAR and LAST_RUID. Return whether dependence info
7379 was assigned to REF. */
7382 maybe_set_dependence_info (tree ref
, tree ptr
,
7383 unsigned short &clique
, varinfo_t restrict_var
,
7384 unsigned short &last_ruid
)
7386 while (handled_component_p (ref
))
7387 ref
= TREE_OPERAND (ref
, 0);
7388 if ((TREE_CODE (ref
) == MEM_REF
7389 || TREE_CODE (ref
) == TARGET_MEM_REF
)
7390 && TREE_OPERAND (ref
, 0) == ptr
)
7392 /* Do not overwrite existing cliques. This avoids overwriting dependence
7393 info inlined from a function with restrict parameters inlined
7394 into a function with restrict parameters. This usually means we
7395 prefer to be precise in innermost loops. */
7396 if (MR_DEPENDENCE_CLIQUE (ref
) == 0)
7399 clique
= ++cfun
->last_clique
;
7400 if (restrict_var
->ruid
== 0)
7401 restrict_var
->ruid
= ++last_ruid
;
7402 MR_DEPENDENCE_CLIQUE (ref
) = clique
;
7403 MR_DEPENDENCE_BASE (ref
) = restrict_var
->ruid
;
7410 /* Compute the set of independend memory references based on restrict
7411 tags and their conservative propagation to the points-to sets. */
7414 compute_dependence_clique (void)
7416 unsigned short clique
= 0;
7417 unsigned short last_ruid
= 0;
7418 bitmap rvars
= BITMAP_ALLOC (NULL
);
7419 for (unsigned i
= 0; i
< num_ssa_names
; ++i
)
7421 tree ptr
= ssa_name (i
);
7422 if (!ptr
|| !POINTER_TYPE_P (TREE_TYPE (ptr
)))
7425 /* Avoid all this when ptr is not dereferenced? */
7427 if (SSA_NAME_IS_DEFAULT_DEF (ptr
)
7428 && (TREE_CODE (SSA_NAME_VAR (ptr
)) == PARM_DECL
7429 || TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
))
7430 p
= SSA_NAME_VAR (ptr
);
7431 varinfo_t vi
= lookup_vi_for_tree (p
);
7434 vi
= get_varinfo (find (vi
->id
));
7437 varinfo_t restrict_var
= NULL
;
7438 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, j
, bi
)
7440 varinfo_t oi
= get_varinfo (j
);
7441 if (oi
->is_restrict_var
)
7445 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7447 fprintf (dump_file
, "found restrict pointed-to "
7449 print_generic_expr (dump_file
, ptr
);
7450 fprintf (dump_file
, " but not exclusively\n");
7452 restrict_var
= NULL
;
7457 /* NULL is the only other valid points-to entry. */
7458 else if (oi
->id
!= nothing_id
)
7460 restrict_var
= NULL
;
7464 /* Ok, found that ptr must(!) point to a single(!) restrict
7466 /* ??? PTA isn't really a proper propagation engine to compute
7468 ??? We could handle merging of two restricts by unifying them. */
7471 /* Now look at possible dereferences of ptr. */
7472 imm_use_iterator ui
;
7475 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, ptr
)
7477 /* ??? Calls and asms. */
7478 if (!gimple_assign_single_p (use_stmt
))
7480 used
|= maybe_set_dependence_info (gimple_assign_lhs (use_stmt
),
7481 ptr
, clique
, restrict_var
,
7483 used
|= maybe_set_dependence_info (gimple_assign_rhs1 (use_stmt
),
7484 ptr
, clique
, restrict_var
,
7488 bitmap_set_bit (rvars
, restrict_var
->id
);
7494 /* Assign the BASE id zero to all accesses not based on a restrict
7495 pointer. That way they get disambiguated against restrict
7496 accesses but not against each other. */
7497 /* ??? For restricts derived from globals (thus not incoming
7498 parameters) we can't restrict scoping properly thus the following
7499 is too aggressive there. For now we have excluded those globals from
7500 getting into the MR_DEPENDENCE machinery. */
7501 vls_data data
= { clique
, rvars
};
7503 FOR_EACH_BB_FN (bb
, cfun
)
7504 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
7505 !gsi_end_p (gsi
); gsi_next (&gsi
))
7507 gimple
*stmt
= gsi_stmt (gsi
);
7508 walk_stmt_load_store_ops (stmt
, &data
,
7509 visit_loadstore
, visit_loadstore
);
7513 BITMAP_FREE (rvars
);
7516 /* Compute points-to information for every SSA_NAME pointer in the
7517 current function and compute the transitive closure of escaped
7518 variables to re-initialize the call-clobber states of local variables. */
7521 compute_may_aliases (void)
7523 if (cfun
->gimple_df
->ipa_pta
)
7527 fprintf (dump_file
, "\nNot re-computing points-to information "
7528 "because IPA points-to information is available.\n\n");
7530 /* But still dump what we have remaining it. */
7531 dump_alias_info (dump_file
);
7537 /* For each pointer P_i, determine the sets of variables that P_i may
7538 point-to. Compute the reachability set of escaped and call-used
7540 compute_points_to_sets ();
7542 /* Debugging dumps. */
7544 dump_alias_info (dump_file
);
7546 /* Compute restrict-based memory disambiguations. */
7547 compute_dependence_clique ();
7549 /* Deallocate memory used by aliasing data structures and the internal
7550 points-to solution. */
7551 delete_points_to_sets ();
7553 gcc_assert (!need_ssa_update_p (cfun
));
7558 /* A dummy pass to cause points-to information to be computed via
7559 TODO_rebuild_alias. */
7563 const pass_data pass_data_build_alias
=
7565 GIMPLE_PASS
, /* type */
7567 OPTGROUP_NONE
, /* optinfo_flags */
7568 TV_NONE
, /* tv_id */
7569 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7570 0, /* properties_provided */
7571 0, /* properties_destroyed */
7572 0, /* todo_flags_start */
7573 TODO_rebuild_alias
, /* todo_flags_finish */
7576 class pass_build_alias
: public gimple_opt_pass
7579 pass_build_alias (gcc::context
*ctxt
)
7580 : gimple_opt_pass (pass_data_build_alias
, ctxt
)
7583 /* opt_pass methods: */
7584 virtual bool gate (function
*) { return flag_tree_pta
; }
7586 }; // class pass_build_alias
7591 make_pass_build_alias (gcc::context
*ctxt
)
7593 return new pass_build_alias (ctxt
);
7596 /* A dummy pass to cause points-to information to be computed via
7597 TODO_rebuild_alias. */
7601 const pass_data pass_data_build_ealias
=
7603 GIMPLE_PASS
, /* type */
7604 "ealias", /* name */
7605 OPTGROUP_NONE
, /* optinfo_flags */
7606 TV_NONE
, /* tv_id */
7607 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7608 0, /* properties_provided */
7609 0, /* properties_destroyed */
7610 0, /* todo_flags_start */
7611 TODO_rebuild_alias
, /* todo_flags_finish */
7614 class pass_build_ealias
: public gimple_opt_pass
7617 pass_build_ealias (gcc::context
*ctxt
)
7618 : gimple_opt_pass (pass_data_build_ealias
, ctxt
)
7621 /* opt_pass methods: */
7622 virtual bool gate (function
*) { return flag_tree_pta
; }
7624 }; // class pass_build_ealias
7629 make_pass_build_ealias (gcc::context
*ctxt
)
7631 return new pass_build_ealias (ctxt
);
7635 /* IPA PTA solutions for ESCAPED. */
7636 struct pt_solution ipa_escaped_pt
7637 = { true, false, false, false, false,
7638 false, false, false, false, false, NULL
};
7640 /* Associate node with varinfo DATA. Worker for
7641 cgraph_for_symbol_thunks_and_aliases. */
7643 associate_varinfo_to_alias (struct cgraph_node
*node
, void *data
)
7646 || (node
->thunk
.thunk_p
7647 && ! node
->global
.inlined_to
))
7649 insert_vi_for_tree (node
->decl
, (varinfo_t
)data
);
7653 /* Dump varinfo VI to FILE. */
7656 dump_varinfo (FILE *file
, varinfo_t vi
)
7661 fprintf (file
, "%u: %s\n", vi
->id
, vi
->name
);
7663 const char *sep
= " ";
7664 if (vi
->is_artificial_var
)
7665 fprintf (file
, "%sartificial", sep
);
7666 if (vi
->is_special_var
)
7667 fprintf (file
, "%sspecial", sep
);
7668 if (vi
->is_unknown_size_var
)
7669 fprintf (file
, "%sunknown-size", sep
);
7670 if (vi
->is_full_var
)
7671 fprintf (file
, "%sfull", sep
);
7672 if (vi
->is_heap_var
)
7673 fprintf (file
, "%sheap", sep
);
7674 if (vi
->may_have_pointers
)
7675 fprintf (file
, "%smay-have-pointers", sep
);
7676 if (vi
->only_restrict_pointers
)
7677 fprintf (file
, "%sonly-restrict-pointers", sep
);
7678 if (vi
->is_restrict_var
)
7679 fprintf (file
, "%sis-restrict-var", sep
);
7680 if (vi
->is_global_var
)
7681 fprintf (file
, "%sglobal", sep
);
7682 if (vi
->is_ipa_escape_point
)
7683 fprintf (file
, "%sipa-escape-point", sep
);
7685 fprintf (file
, "%sfn-info", sep
);
7687 fprintf (file
, "%srestrict-uid:%u", sep
, vi
->ruid
);
7689 fprintf (file
, "%snext:%u", sep
, vi
->next
);
7690 if (vi
->head
!= vi
->id
)
7691 fprintf (file
, "%shead:%u", sep
, vi
->head
);
7693 fprintf (file
, "%soffset:" HOST_WIDE_INT_PRINT_DEC
, sep
, vi
->offset
);
7694 if (vi
->size
!= ~(unsigned HOST_WIDE_INT
)0)
7695 fprintf (file
, "%ssize:" HOST_WIDE_INT_PRINT_DEC
, sep
, vi
->size
);
7696 if (vi
->fullsize
!= ~(unsigned HOST_WIDE_INT
)0
7697 && vi
->fullsize
!= vi
->size
)
7698 fprintf (file
, "%sfullsize:" HOST_WIDE_INT_PRINT_DEC
, sep
,
7700 fprintf (file
, "\n");
7702 if (vi
->solution
&& !bitmap_empty_p (vi
->solution
))
7706 fprintf (file
, " solution: {");
7707 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
7708 fprintf (file
, " %u", i
);
7709 fprintf (file
, " }\n");
7712 if (vi
->oldsolution
&& !bitmap_empty_p (vi
->oldsolution
)
7713 && !bitmap_equal_p (vi
->solution
, vi
->oldsolution
))
7717 fprintf (file
, " oldsolution: {");
7718 EXECUTE_IF_SET_IN_BITMAP (vi
->oldsolution
, 0, i
, bi
)
7719 fprintf (file
, " %u", i
);
7720 fprintf (file
, " }\n");
7724 /* Dump varinfo VI to stderr. */
7727 debug_varinfo (varinfo_t vi
)
7729 dump_varinfo (stderr
, vi
);
7732 /* Dump varmap to FILE. */
7735 dump_varmap (FILE *file
)
7737 if (varmap
.length () == 0)
7740 fprintf (file
, "variables:\n");
7742 for (unsigned int i
= 0; i
< varmap
.length (); ++i
)
7744 varinfo_t vi
= get_varinfo (i
);
7745 dump_varinfo (file
, vi
);
7748 fprintf (file
, "\n");
7751 /* Dump varmap to stderr. */
7756 dump_varmap (stderr
);
7759 /* Compute whether node is refered to non-locally. Worker for
7760 cgraph_for_symbol_thunks_and_aliases. */
7762 refered_from_nonlocal_fn (struct cgraph_node
*node
, void *data
)
7764 bool *nonlocal_p
= (bool *)data
;
7765 *nonlocal_p
|= (node
->used_from_other_partition
7766 || node
->externally_visible
7767 || node
->force_output
7768 || lookup_attribute ("noipa", DECL_ATTRIBUTES (node
->decl
)));
7772 /* Same for varpool nodes. */
7774 refered_from_nonlocal_var (struct varpool_node
*node
, void *data
)
7776 bool *nonlocal_p
= (bool *)data
;
7777 *nonlocal_p
|= (node
->used_from_other_partition
7778 || node
->externally_visible
7779 || node
->force_output
);
7783 /* Execute the driver for IPA PTA. */
7785 ipa_pta_execute (void)
7787 struct cgraph_node
*node
;
7789 unsigned int from
= 0;
7795 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7797 symtab
->dump (dump_file
);
7798 fprintf (dump_file
, "\n");
7803 fprintf (dump_file
, "Generating generic constraints\n\n");
7804 dump_constraints (dump_file
, from
);
7805 fprintf (dump_file
, "\n");
7806 from
= constraints
.length ();
7809 /* Build the constraints. */
7810 FOR_EACH_DEFINED_FUNCTION (node
)
7813 /* Nodes without a body are not interesting. Especially do not
7814 visit clones at this point for now - we get duplicate decls
7815 there for inline clones at least. */
7816 if (!node
->has_gimple_body_p () || node
->global
.inlined_to
)
7820 gcc_assert (!node
->clone_of
);
7822 /* For externally visible or attribute used annotated functions use
7823 local constraints for their arguments.
7824 For local functions we see all callers and thus do not need initial
7825 constraints for parameters. */
7826 bool nonlocal_p
= (node
->used_from_other_partition
7827 || node
->externally_visible
7828 || node
->force_output
7829 || lookup_attribute ("noipa",
7830 DECL_ATTRIBUTES (node
->decl
)));
7831 node
->call_for_symbol_thunks_and_aliases (refered_from_nonlocal_fn
,
7834 vi
= create_function_info_for (node
->decl
,
7835 alias_get_name (node
->decl
), false,
7838 && from
!= constraints
.length ())
7841 "Generating intial constraints for %s", node
->name ());
7842 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
7843 fprintf (dump_file
, " (%s)",
7845 (DECL_ASSEMBLER_NAME (node
->decl
)));
7846 fprintf (dump_file
, "\n\n");
7847 dump_constraints (dump_file
, from
);
7848 fprintf (dump_file
, "\n");
7850 from
= constraints
.length ();
7853 node
->call_for_symbol_thunks_and_aliases
7854 (associate_varinfo_to_alias
, vi
, true);
7857 /* Create constraints for global variables and their initializers. */
7858 FOR_EACH_VARIABLE (var
)
7860 if (var
->alias
&& var
->analyzed
)
7863 varinfo_t vi
= get_vi_for_tree (var
->decl
);
7865 /* For the purpose of IPA PTA unit-local globals are not
7867 bool nonlocal_p
= (var
->used_from_other_partition
7868 || var
->externally_visible
7869 || var
->force_output
);
7870 var
->call_for_symbol_and_aliases (refered_from_nonlocal_var
,
7873 vi
->is_ipa_escape_point
= true;
7877 && from
!= constraints
.length ())
7880 "Generating constraints for global initializers\n\n");
7881 dump_constraints (dump_file
, from
);
7882 fprintf (dump_file
, "\n");
7883 from
= constraints
.length ();
7886 FOR_EACH_DEFINED_FUNCTION (node
)
7888 struct function
*func
;
7891 /* Nodes without a body are not interesting. */
7892 if (!node
->has_gimple_body_p () || node
->clone_of
)
7898 "Generating constraints for %s", node
->name ());
7899 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
7900 fprintf (dump_file
, " (%s)",
7902 (DECL_ASSEMBLER_NAME (node
->decl
)));
7903 fprintf (dump_file
, "\n");
7906 func
= DECL_STRUCT_FUNCTION (node
->decl
);
7907 gcc_assert (cfun
== NULL
);
7909 /* Build constriants for the function body. */
7910 FOR_EACH_BB_FN (bb
, func
)
7912 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7915 gphi
*phi
= gsi
.phi ();
7917 if (! virtual_operand_p (gimple_phi_result (phi
)))
7918 find_func_aliases (func
, phi
);
7921 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
7924 gimple
*stmt
= gsi_stmt (gsi
);
7926 find_func_aliases (func
, stmt
);
7927 find_func_clobbers (func
, stmt
);
7933 fprintf (dump_file
, "\n");
7934 dump_constraints (dump_file
, from
);
7935 fprintf (dump_file
, "\n");
7936 from
= constraints
.length ();
7940 /* From the constraints compute the points-to sets. */
7941 solve_constraints ();
7943 /* Compute the global points-to sets for ESCAPED.
7944 ??? Note that the computed escape set is not correct
7945 for the whole unit as we fail to consider graph edges to
7946 externally visible functions. */
7947 ipa_escaped_pt
= find_what_var_points_to (NULL
, get_varinfo (escaped_id
));
7949 /* Make sure the ESCAPED solution (which is used as placeholder in
7950 other solutions) does not reference itself. This simplifies
7951 points-to solution queries. */
7952 ipa_escaped_pt
.ipa_escaped
= 0;
7954 /* Assign the points-to sets to the SSA names in the unit. */
7955 FOR_EACH_DEFINED_FUNCTION (node
)
7958 struct function
*fn
;
7962 /* Nodes without a body are not interesting. */
7963 if (!node
->has_gimple_body_p () || node
->clone_of
)
7966 fn
= DECL_STRUCT_FUNCTION (node
->decl
);
7968 /* Compute the points-to sets for pointer SSA_NAMEs. */
7969 FOR_EACH_VEC_ELT (*fn
->gimple_df
->ssa_names
, i
, ptr
)
7972 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
7973 find_what_p_points_to (node
->decl
, ptr
);
7976 /* Compute the call-use and call-clobber sets for indirect calls
7977 and calls to external functions. */
7978 FOR_EACH_BB_FN (bb
, fn
)
7980 gimple_stmt_iterator gsi
;
7982 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7985 struct pt_solution
*pt
;
7989 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
7993 /* Handle direct calls to functions with body. */
7994 decl
= gimple_call_fndecl (stmt
);
7997 tree called_decl
= NULL_TREE
;
7998 if (gimple_call_builtin_p (stmt
, BUILT_IN_GOMP_PARALLEL
))
7999 called_decl
= TREE_OPERAND (gimple_call_arg (stmt
, 0), 0);
8000 else if (gimple_call_builtin_p (stmt
, BUILT_IN_GOACC_PARALLEL
))
8001 called_decl
= TREE_OPERAND (gimple_call_arg (stmt
, 1), 0);
8003 if (called_decl
!= NULL_TREE
8004 && !fndecl_maybe_in_other_partition (called_decl
))
8009 && (fi
= lookup_vi_for_tree (decl
))
8012 *gimple_call_clobber_set (stmt
)
8013 = find_what_var_points_to
8014 (node
->decl
, first_vi_for_offset (fi
, fi_clobbers
));
8015 *gimple_call_use_set (stmt
)
8016 = find_what_var_points_to
8017 (node
->decl
, first_vi_for_offset (fi
, fi_uses
));
8019 /* Handle direct calls to external functions. */
8022 pt
= gimple_call_use_set (stmt
);
8023 if (gimple_call_flags (stmt
) & ECF_CONST
)
8024 memset (pt
, 0, sizeof (struct pt_solution
));
8025 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
8027 *pt
= find_what_var_points_to (node
->decl
, vi
);
8028 /* Escaped (and thus nonlocal) variables are always
8029 implicitly used by calls. */
8030 /* ??? ESCAPED can be empty even though NONLOCAL
8033 pt
->ipa_escaped
= 1;
8037 /* If there is nothing special about this call then
8038 we have made everything that is used also escape. */
8039 *pt
= ipa_escaped_pt
;
8043 pt
= gimple_call_clobber_set (stmt
);
8044 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
8045 memset (pt
, 0, sizeof (struct pt_solution
));
8046 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
8048 *pt
= find_what_var_points_to (node
->decl
, vi
);
8049 /* Escaped (and thus nonlocal) variables are always
8050 implicitly clobbered by calls. */
8051 /* ??? ESCAPED can be empty even though NONLOCAL
8054 pt
->ipa_escaped
= 1;
8058 /* If there is nothing special about this call then
8059 we have made everything that is used also escape. */
8060 *pt
= ipa_escaped_pt
;
8064 /* Handle indirect calls. */
8066 && (fi
= get_fi_for_callee (stmt
)))
8068 /* We need to accumulate all clobbers/uses of all possible
8070 fi
= get_varinfo (find (fi
->id
));
8071 /* If we cannot constrain the set of functions we'll end up
8072 calling we end up using/clobbering everything. */
8073 if (bitmap_bit_p (fi
->solution
, anything_id
)
8074 || bitmap_bit_p (fi
->solution
, nonlocal_id
)
8075 || bitmap_bit_p (fi
->solution
, escaped_id
))
8077 pt_solution_reset (gimple_call_clobber_set (stmt
));
8078 pt_solution_reset (gimple_call_use_set (stmt
));
8084 struct pt_solution
*uses
, *clobbers
;
8086 uses
= gimple_call_use_set (stmt
);
8087 clobbers
= gimple_call_clobber_set (stmt
);
8088 memset (uses
, 0, sizeof (struct pt_solution
));
8089 memset (clobbers
, 0, sizeof (struct pt_solution
));
8090 EXECUTE_IF_SET_IN_BITMAP (fi
->solution
, 0, i
, bi
)
8092 struct pt_solution sol
;
8094 vi
= get_varinfo (i
);
8095 if (!vi
->is_fn_info
)
8097 /* ??? We could be more precise here? */
8099 uses
->ipa_escaped
= 1;
8100 clobbers
->nonlocal
= 1;
8101 clobbers
->ipa_escaped
= 1;
8105 if (!uses
->anything
)
8107 sol
= find_what_var_points_to
8109 first_vi_for_offset (vi
, fi_uses
));
8110 pt_solution_ior_into (uses
, &sol
);
8112 if (!clobbers
->anything
)
8114 sol
= find_what_var_points_to
8116 first_vi_for_offset (vi
, fi_clobbers
));
8117 pt_solution_ior_into (clobbers
, &sol
);
8125 fn
->gimple_df
->ipa_pta
= true;
8127 /* We have to re-set the final-solution cache after each function
8128 because what is a "global" is dependent on function context. */
8129 final_solutions
->empty ();
8130 obstack_free (&final_solutions_obstack
, NULL
);
8131 gcc_obstack_init (&final_solutions_obstack
);
8134 delete_points_to_sets ();
8143 const pass_data pass_data_ipa_pta
=
8145 SIMPLE_IPA_PASS
, /* type */
8147 OPTGROUP_NONE
, /* optinfo_flags */
8148 TV_IPA_PTA
, /* tv_id */
8149 0, /* properties_required */
8150 0, /* properties_provided */
8151 0, /* properties_destroyed */
8152 0, /* todo_flags_start */
8153 0, /* todo_flags_finish */
8156 class pass_ipa_pta
: public simple_ipa_opt_pass
8159 pass_ipa_pta (gcc::context
*ctxt
)
8160 : simple_ipa_opt_pass (pass_data_ipa_pta
, ctxt
)
8163 /* opt_pass methods: */
8164 virtual bool gate (function
*)
8168 /* Don't bother doing anything if the program has errors. */
8172 opt_pass
* clone () { return new pass_ipa_pta (m_ctxt
); }
8174 virtual unsigned int execute (function
*) { return ipa_pta_execute (); }
8176 }; // class pass_ipa_pta
8180 simple_ipa_opt_pass
*
8181 make_pass_ipa_pta (gcc::context
*ctxt
)
8183 return new pass_ipa_pta (ctxt
);