1 /* Tree based points-to analysis
2 Copyright (C) 2005-2016 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"
43 /* The idea behind this analyzer is to generate set constraints from the
44 program, then solve the resulting constraints in order to generate the
47 Set constraints are a way of modeling program analysis problems that
48 involve sets. They consist of an inclusion constraint language,
49 describing the variables (each variable is a set) and operations that
50 are involved on the variables, and a set of rules that derive facts
51 from these operations. To solve a system of set constraints, you derive
52 all possible facts under the rules, which gives you the correct sets
55 See "Efficient Field-sensitive pointer analysis for C" by "David
56 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
57 http://citeseer.ist.psu.edu/pearce04efficient.html
59 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
60 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
61 http://citeseer.ist.psu.edu/heintze01ultrafast.html
63 There are three types of real constraint expressions, DEREF,
64 ADDRESSOF, and SCALAR. Each constraint expression consists
65 of a constraint type, a variable, and an offset.
67 SCALAR is a constraint expression type used to represent x, whether
68 it appears on the LHS or the RHS of a statement.
69 DEREF is a constraint expression type used to represent *x, whether
70 it appears on the LHS or the RHS of a statement.
71 ADDRESSOF is a constraint expression used to represent &x, whether
72 it appears on the LHS or the RHS of a statement.
74 Each pointer variable in the program is assigned an integer id, and
75 each field of a structure variable is assigned an integer id as well.
77 Structure variables are linked to their list of fields through a "next
78 field" in each variable that points to the next field in offset
80 Each variable for a structure field has
82 1. "size", that tells the size in bits of that field.
83 2. "fullsize, that tells the size in bits of the entire structure.
84 3. "offset", that tells the offset in bits from the beginning of the
85 structure to this field.
97 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
98 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
99 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
102 In order to solve the system of set constraints, the following is
105 1. Each constraint variable x has a solution set associated with it,
108 2. Constraints are separated into direct, copy, and complex.
109 Direct constraints are ADDRESSOF constraints that require no extra
110 processing, such as P = &Q
111 Copy constraints are those of the form P = Q.
112 Complex constraints are all the constraints involving dereferences
113 and offsets (including offsetted copies).
115 3. All direct constraints of the form P = &Q are processed, such
116 that Q is added to Sol(P)
118 4. All complex constraints for a given constraint variable are stored in a
119 linked list attached to that variable's node.
121 5. A directed graph is built out of the copy constraints. Each
122 constraint variable is a node in the graph, and an edge from
123 Q to P is added for each copy constraint of the form P = Q
125 6. The graph is then walked, and solution sets are
126 propagated along the copy edges, such that an edge from Q to P
127 causes Sol(P) <- Sol(P) union Sol(Q).
129 7. As we visit each node, all complex constraints associated with
130 that node are processed by adding appropriate copy edges to the graph, or the
131 appropriate variables to the solution set.
133 8. The process of walking the graph is iterated until no solution
136 Prior to walking the graph in steps 6 and 7, We perform static
137 cycle elimination on the constraint graph, as well
138 as off-line variable substitution.
140 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
141 on and turned into anything), but isn't. You can just see what offset
142 inside the pointed-to struct it's going to access.
144 TODO: Constant bounded arrays can be handled as if they were structs of the
145 same number of elements.
147 TODO: Modeling heap and incoming pointers becomes much better if we
148 add fields to them as we discover them, which we could do.
150 TODO: We could handle unions, but to be honest, it's probably not
151 worth the pain or slowdown. */
153 /* IPA-PTA optimizations possible.
155 When the indirect function called is ANYTHING we can add disambiguation
156 based on the function signatures (or simply the parameter count which
157 is the varinfo size). We also do not need to consider functions that
158 do not have their address taken.
160 The is_global_var bit which marks escape points is overly conservative
161 in IPA mode. Split it to is_escape_point and is_global_var - only
162 externally visible globals are escape points in IPA mode.
163 There is now is_ipa_escape_point but this is only used in a few
166 The way we introduce DECL_PT_UID to avoid fixing up all points-to
167 sets in the translation unit when we copy a DECL during inlining
168 pessimizes precision. The advantage is that the DECL_PT_UID keeps
169 compile-time and memory usage overhead low - the points-to sets
170 do not grow or get unshared as they would during a fixup phase.
171 An alternative solution is to delay IPA PTA until after all
172 inlining transformations have been applied.
174 The way we propagate clobber/use information isn't optimized.
175 It should use a new complex constraint that properly filters
176 out local variables of the callee (though that would make
177 the sets invalid after inlining). OTOH we might as well
178 admit defeat to WHOPR and simply do all the clobber/use analysis
179 and propagation after PTA finished but before we threw away
180 points-to information for memory variables. WHOPR and PTA
181 do not play along well anyway - the whole constraint solving
182 would need to be done in WPA phase and it will be very interesting
183 to apply the results to local SSA names during LTRANS phase.
185 We probably should compute a per-function unit-ESCAPE solution
186 propagating it simply like the clobber / uses solutions. The
187 solution can go alongside the non-IPA espaced solution and be
188 used to query which vars escape the unit through a function.
189 This is also required to make the escaped-HEAP trick work in IPA mode.
191 We never put function decls in points-to sets so we do not
192 keep the set of called functions for indirect calls.
194 And probably more. */
196 static bool use_field_sensitive
= true;
197 static int in_ipa_mode
= 0;
199 /* Used for predecessor bitmaps. */
200 static bitmap_obstack predbitmap_obstack
;
202 /* Used for points-to sets. */
203 static bitmap_obstack pta_obstack
;
205 /* Used for oldsolution members of variables. */
206 static bitmap_obstack oldpta_obstack
;
208 /* Used for per-solver-iteration bitmaps. */
209 static bitmap_obstack iteration_obstack
;
211 static unsigned int create_variable_info_for (tree
, const char *, bool);
212 typedef struct constraint_graph
*constraint_graph_t
;
213 static void unify_nodes (constraint_graph_t
, unsigned int, unsigned int, bool);
216 typedef struct constraint
*constraint_t
;
219 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
221 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
223 static struct constraint_stats
225 unsigned int total_vars
;
226 unsigned int nonpointer_vars
;
227 unsigned int unified_vars_static
;
228 unsigned int unified_vars_dynamic
;
229 unsigned int iterations
;
230 unsigned int num_edges
;
231 unsigned int num_implicit_edges
;
232 unsigned int points_to_sets_created
;
237 /* ID of this variable */
240 /* True if this is a variable created by the constraint analysis, such as
241 heap variables and constraints we had to break up. */
242 unsigned int is_artificial_var
: 1;
244 /* True if this is a special variable whose solution set should not be
246 unsigned int is_special_var
: 1;
248 /* True for variables whose size is not known or variable. */
249 unsigned int is_unknown_size_var
: 1;
251 /* True for (sub-)fields that represent a whole variable. */
252 unsigned int is_full_var
: 1;
254 /* True if this is a heap variable. */
255 unsigned int is_heap_var
: 1;
257 /* True if this field may contain pointers. */
258 unsigned int may_have_pointers
: 1;
260 /* True if this field has only restrict qualified pointers. */
261 unsigned int only_restrict_pointers
: 1;
263 /* True if this represents a heap var created for a restrict qualified
265 unsigned int is_restrict_var
: 1;
267 /* True if this represents a global variable. */
268 unsigned int is_global_var
: 1;
270 /* True if this represents a module escape point for IPA analysis. */
271 unsigned int is_ipa_escape_point
: 1;
273 /* True if this represents a IPA function info. */
274 unsigned int is_fn_info
: 1;
276 /* ??? Store somewhere better. */
279 /* The ID of the variable for the next field in this structure
280 or zero for the last field in this structure. */
283 /* The ID of the variable for the first field in this structure. */
286 /* Offset of this variable, in bits, from the base variable */
287 unsigned HOST_WIDE_INT offset
;
289 /* Size of the variable, in bits. */
290 unsigned HOST_WIDE_INT size
;
292 /* Full size of the base variable, in bits. */
293 unsigned HOST_WIDE_INT fullsize
;
295 /* Name of this variable */
298 /* Tree that this variable is associated with. */
301 /* Points-to set for this variable. */
304 /* Old points-to set for this variable. */
307 typedef struct variable_info
*varinfo_t
;
309 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
310 static varinfo_t
first_or_preceding_vi_for_offset (varinfo_t
,
311 unsigned HOST_WIDE_INT
);
312 static varinfo_t
lookup_vi_for_tree (tree
);
313 static inline bool type_can_have_subvars (const_tree
);
314 static void make_param_constraints (varinfo_t
);
316 /* Pool of variable info structures. */
317 static object_allocator
<variable_info
> variable_info_pool
318 ("Variable info pool");
320 /* Map varinfo to final pt_solution. */
321 static hash_map
<varinfo_t
, pt_solution
*> *final_solutions
;
322 struct obstack final_solutions_obstack
;
324 /* Table of variable info structures for constraint variables.
325 Indexed directly by variable info id. */
326 static vec
<varinfo_t
> varmap
;
328 /* Return the varmap element N */
330 static inline varinfo_t
331 get_varinfo (unsigned int n
)
336 /* Return the next variable in the list of sub-variables of VI
337 or NULL if VI is the last sub-variable. */
339 static inline varinfo_t
340 vi_next (varinfo_t vi
)
342 return get_varinfo (vi
->next
);
345 /* Static IDs for the special variables. Variable ID zero is unused
346 and used as terminator for the sub-variable chain. */
347 enum { nothing_id
= 1, anything_id
= 2, string_id
= 3,
348 escaped_id
= 4, nonlocal_id
= 5,
349 storedanything_id
= 6, integer_id
= 7 };
351 /* Return a new variable info structure consisting for a variable
352 named NAME, and using constraint graph node NODE. Append it
353 to the vector of variable info structures. */
356 new_var_info (tree t
, const char *name
, bool add_id
)
358 unsigned index
= varmap
.length ();
359 varinfo_t ret
= variable_info_pool
.allocate ();
361 if (dump_file
&& add_id
)
363 char *tempname
= xasprintf ("%s(%d)", name
, index
);
364 name
= ggc_strdup (tempname
);
371 /* Vars without decl are artificial and do not have sub-variables. */
372 ret
->is_artificial_var
= (t
== NULL_TREE
);
373 ret
->is_special_var
= false;
374 ret
->is_unknown_size_var
= false;
375 ret
->is_full_var
= (t
== NULL_TREE
);
376 ret
->is_heap_var
= false;
377 ret
->may_have_pointers
= true;
378 ret
->only_restrict_pointers
= false;
379 ret
->is_restrict_var
= false;
381 ret
->is_global_var
= (t
== NULL_TREE
);
382 ret
->is_ipa_escape_point
= false;
383 ret
->is_fn_info
= false;
385 ret
->is_global_var
= (is_global_var (t
)
386 /* We have to treat even local register variables
388 || (TREE_CODE (t
) == VAR_DECL
389 && DECL_HARD_REGISTER (t
)));
390 ret
->solution
= BITMAP_ALLOC (&pta_obstack
);
391 ret
->oldsolution
= NULL
;
397 varmap
.safe_push (ret
);
402 /* A map mapping call statements to per-stmt variables for uses
403 and clobbers specific to the call. */
404 static hash_map
<gimple
*, varinfo_t
> *call_stmt_vars
;
406 /* Lookup or create the variable for the call statement CALL. */
409 get_call_vi (gcall
*call
)
414 varinfo_t
*slot_p
= &call_stmt_vars
->get_or_insert (call
, &existed
);
418 vi
= new_var_info (NULL_TREE
, "CALLUSED", true);
422 vi
->is_full_var
= true;
424 vi2
= new_var_info (NULL_TREE
, "CALLCLOBBERED", true);
428 vi2
->is_full_var
= true;
436 /* Lookup the variable for the call statement CALL representing
437 the uses. Returns NULL if there is nothing special about this call. */
440 lookup_call_use_vi (gcall
*call
)
442 varinfo_t
*slot_p
= call_stmt_vars
->get (call
);
449 /* Lookup the variable for the call statement CALL representing
450 the clobbers. Returns NULL if there is nothing special about this call. */
453 lookup_call_clobber_vi (gcall
*call
)
455 varinfo_t uses
= lookup_call_use_vi (call
);
459 return vi_next (uses
);
462 /* Lookup or create the variable for the call statement CALL representing
466 get_call_use_vi (gcall
*call
)
468 return get_call_vi (call
);
471 /* Lookup or create the variable for the call statement CALL representing
474 static varinfo_t ATTRIBUTE_UNUSED
475 get_call_clobber_vi (gcall
*call
)
477 return vi_next (get_call_vi (call
));
481 enum constraint_expr_type
{SCALAR
, DEREF
, ADDRESSOF
};
483 /* An expression that appears in a constraint. */
485 struct constraint_expr
487 /* Constraint type. */
488 constraint_expr_type type
;
490 /* Variable we are referring to in the constraint. */
493 /* Offset, in bits, of this constraint from the beginning of
494 variables it ends up referring to.
496 IOW, in a deref constraint, we would deref, get the result set,
497 then add OFFSET to each member. */
498 HOST_WIDE_INT offset
;
501 /* Use 0x8000... as special unknown offset. */
502 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
504 typedef struct constraint_expr ce_s
;
505 static void get_constraint_for_1 (tree
, vec
<ce_s
> *, bool, bool);
506 static void get_constraint_for (tree
, vec
<ce_s
> *);
507 static void get_constraint_for_rhs (tree
, vec
<ce_s
> *);
508 static void do_deref (vec
<ce_s
> *);
510 /* Our set constraints are made up of two constraint expressions, one
513 As described in the introduction, our set constraints each represent an
514 operation between set valued variables.
518 struct constraint_expr lhs
;
519 struct constraint_expr rhs
;
522 /* List of constraints that we use to build the constraint graph from. */
524 static vec
<constraint_t
> constraints
;
525 static object_allocator
<constraint
> constraint_pool ("Constraint pool");
527 /* The constraint graph is represented as an array of bitmaps
528 containing successor nodes. */
530 struct constraint_graph
532 /* Size of this graph, which may be different than the number of
533 nodes in the variable map. */
536 /* Explicit successors of each node. */
539 /* Implicit predecessors of each node (Used for variable
541 bitmap
*implicit_preds
;
543 /* Explicit predecessors of each node (Used for variable substitution). */
546 /* Indirect cycle representatives, or -1 if the node has no indirect
548 int *indirect_cycles
;
550 /* Representative node for a node. rep[a] == a unless the node has
554 /* Equivalence class representative for a label. This is used for
555 variable substitution. */
558 /* Pointer equivalence label for a node. All nodes with the same
559 pointer equivalence label can be unified together at some point
560 (either during constraint optimization or after the constraint
564 /* Pointer equivalence representative for a label. This is used to
565 handle nodes that are pointer equivalent but not location
566 equivalent. We can unite these once the addressof constraints
567 are transformed into initial points-to sets. */
570 /* Pointer equivalence label for each node, used during variable
572 unsigned int *pointer_label
;
574 /* Location equivalence label for each node, used during location
575 equivalence finding. */
576 unsigned int *loc_label
;
578 /* Pointed-by set for each node, used during location equivalence
579 finding. This is pointed-by rather than pointed-to, because it
580 is constructed using the predecessor graph. */
583 /* Points to sets for pointer equivalence. This is *not* the actual
584 points-to sets for nodes. */
587 /* Bitmap of nodes where the bit is set if the node is a direct
588 node. Used for variable substitution. */
589 sbitmap direct_nodes
;
591 /* Bitmap of nodes where the bit is set if the node is address
592 taken. Used for variable substitution. */
593 bitmap address_taken
;
595 /* Vector of complex constraints for each graph node. Complex
596 constraints are those involving dereferences or offsets that are
598 vec
<constraint_t
> *complex;
601 static constraint_graph_t graph
;
603 /* During variable substitution and the offline version of indirect
604 cycle finding, we create nodes to represent dereferences and
605 address taken constraints. These represent where these start and
607 #define FIRST_REF_NODE (varmap).length ()
608 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
610 /* Return the representative node for NODE, if NODE has been unioned
612 This function performs path compression along the way to finding
613 the representative. */
616 find (unsigned int node
)
618 gcc_checking_assert (node
< graph
->size
);
619 if (graph
->rep
[node
] != node
)
620 return graph
->rep
[node
] = find (graph
->rep
[node
]);
624 /* Union the TO and FROM nodes to the TO nodes.
625 Note that at some point in the future, we may want to do
626 union-by-rank, in which case we are going to have to return the
627 node we unified to. */
630 unite (unsigned int to
, unsigned int from
)
632 gcc_checking_assert (to
< graph
->size
&& from
< graph
->size
);
633 if (to
!= from
&& graph
->rep
[from
] != to
)
635 graph
->rep
[from
] = to
;
641 /* Create a new constraint consisting of LHS and RHS expressions. */
644 new_constraint (const struct constraint_expr lhs
,
645 const struct constraint_expr rhs
)
647 constraint_t ret
= constraint_pool
.allocate ();
653 /* Print out constraint C to FILE. */
656 dump_constraint (FILE *file
, constraint_t c
)
658 if (c
->lhs
.type
== ADDRESSOF
)
660 else if (c
->lhs
.type
== DEREF
)
662 fprintf (file
, "%s", get_varinfo (c
->lhs
.var
)->name
);
663 if (c
->lhs
.offset
== UNKNOWN_OFFSET
)
664 fprintf (file
, " + UNKNOWN");
665 else if (c
->lhs
.offset
!= 0)
666 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
667 fprintf (file
, " = ");
668 if (c
->rhs
.type
== ADDRESSOF
)
670 else if (c
->rhs
.type
== DEREF
)
672 fprintf (file
, "%s", get_varinfo (c
->rhs
.var
)->name
);
673 if (c
->rhs
.offset
== UNKNOWN_OFFSET
)
674 fprintf (file
, " + UNKNOWN");
675 else if (c
->rhs
.offset
!= 0)
676 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
680 void debug_constraint (constraint_t
);
681 void debug_constraints (void);
682 void debug_constraint_graph (void);
683 void debug_solution_for_var (unsigned int);
684 void debug_sa_points_to_info (void);
686 /* Print out constraint C to stderr. */
689 debug_constraint (constraint_t c
)
691 dump_constraint (stderr
, c
);
692 fprintf (stderr
, "\n");
695 /* Print out all constraints to FILE */
698 dump_constraints (FILE *file
, int from
)
702 for (i
= from
; constraints
.iterate (i
, &c
); i
++)
705 dump_constraint (file
, c
);
706 fprintf (file
, "\n");
710 /* Print out all constraints to stderr. */
713 debug_constraints (void)
715 dump_constraints (stderr
, 0);
718 /* Print the constraint graph in dot format. */
721 dump_constraint_graph (FILE *file
)
725 /* Only print the graph if it has already been initialized: */
729 /* Prints the header of the dot file: */
730 fprintf (file
, "strict digraph {\n");
731 fprintf (file
, " node [\n shape = box\n ]\n");
732 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
733 fprintf (file
, "\n // List of nodes and complex constraints in "
734 "the constraint graph:\n");
736 /* The next lines print the nodes in the graph together with the
737 complex constraints attached to them. */
738 for (i
= 1; i
< graph
->size
; i
++)
740 if (i
== FIRST_REF_NODE
)
744 if (i
< FIRST_REF_NODE
)
745 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
747 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
748 if (graph
->complex[i
].exists ())
752 fprintf (file
, " [label=\"\\N\\n");
753 for (j
= 0; graph
->complex[i
].iterate (j
, &c
); ++j
)
755 dump_constraint (file
, c
);
756 fprintf (file
, "\\l");
758 fprintf (file
, "\"]");
760 fprintf (file
, ";\n");
763 /* Go over the edges. */
764 fprintf (file
, "\n // Edges in the constraint graph:\n");
765 for (i
= 1; i
< graph
->size
; i
++)
771 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
], 0, j
, bi
)
773 unsigned to
= find (j
);
776 if (i
< FIRST_REF_NODE
)
777 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
779 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
780 fprintf (file
, " -> ");
781 if (to
< FIRST_REF_NODE
)
782 fprintf (file
, "\"%s\"", get_varinfo (to
)->name
);
784 fprintf (file
, "\"*%s\"", get_varinfo (to
- FIRST_REF_NODE
)->name
);
785 fprintf (file
, ";\n");
789 /* Prints the tail of the dot file. */
790 fprintf (file
, "}\n");
793 /* Print out the constraint graph to stderr. */
796 debug_constraint_graph (void)
798 dump_constraint_graph (stderr
);
803 The solver is a simple worklist solver, that works on the following
806 sbitmap changed_nodes = all zeroes;
808 For each node that is not already collapsed:
810 set bit in changed nodes
812 while (changed_count > 0)
814 compute topological ordering for constraint graph
816 find and collapse cycles in the constraint graph (updating
817 changed if necessary)
819 for each node (n) in the graph in topological order:
822 Process each complex constraint associated with the node,
823 updating changed if necessary.
825 For each outgoing edge from n, propagate the solution from n to
826 the destination of the edge, updating changed as necessary.
830 /* Return true if two constraint expressions A and B are equal. */
833 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
835 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
838 /* Return true if constraint expression A is less than constraint expression
839 B. This is just arbitrary, but consistent, in order to give them an
843 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
845 if (a
.type
== b
.type
)
848 return a
.offset
< b
.offset
;
850 return a
.var
< b
.var
;
853 return a
.type
< b
.type
;
856 /* Return true if constraint A is less than constraint B. This is just
857 arbitrary, but consistent, in order to give them an ordering. */
860 constraint_less (const constraint_t
&a
, const constraint_t
&b
)
862 if (constraint_expr_less (a
->lhs
, b
->lhs
))
864 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
867 return constraint_expr_less (a
->rhs
, b
->rhs
);
870 /* Return true if two constraints A and B are equal. */
873 constraint_equal (struct constraint a
, struct constraint b
)
875 return constraint_expr_equal (a
.lhs
, b
.lhs
)
876 && constraint_expr_equal (a
.rhs
, b
.rhs
);
880 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
883 constraint_vec_find (vec
<constraint_t
> vec
,
884 struct constraint lookfor
)
892 place
= vec
.lower_bound (&lookfor
, constraint_less
);
893 if (place
>= vec
.length ())
896 if (!constraint_equal (*found
, lookfor
))
901 /* Union two constraint vectors, TO and FROM. Put the result in TO.
902 Returns true of TO set is changed. */
905 constraint_set_union (vec
<constraint_t
> *to
,
906 vec
<constraint_t
> *from
)
910 bool any_change
= false;
912 FOR_EACH_VEC_ELT (*from
, i
, c
)
914 if (constraint_vec_find (*to
, *c
) == NULL
)
916 unsigned int place
= to
->lower_bound (c
, constraint_less
);
917 to
->safe_insert (place
, c
);
924 /* Expands the solution in SET to all sub-fields of variables included. */
927 solution_set_expand (bitmap set
, bitmap
*expanded
)
935 *expanded
= BITMAP_ALLOC (&iteration_obstack
);
937 /* In a first pass expand to the head of the variables we need to
938 add all sub-fields off. This avoids quadratic behavior. */
939 EXECUTE_IF_SET_IN_BITMAP (set
, 0, j
, bi
)
941 varinfo_t v
= get_varinfo (j
);
942 if (v
->is_artificial_var
945 bitmap_set_bit (*expanded
, v
->head
);
948 /* In the second pass now expand all head variables with subfields. */
949 EXECUTE_IF_SET_IN_BITMAP (*expanded
, 0, j
, bi
)
951 varinfo_t v
= get_varinfo (j
);
954 for (v
= vi_next (v
); v
!= NULL
; v
= vi_next (v
))
955 bitmap_set_bit (*expanded
, v
->id
);
958 /* And finally set the rest of the bits from SET. */
959 bitmap_ior_into (*expanded
, set
);
964 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
968 set_union_with_increment (bitmap to
, bitmap delta
, HOST_WIDE_INT inc
,
969 bitmap
*expanded_delta
)
971 bool changed
= false;
975 /* If the solution of DELTA contains anything it is good enough to transfer
977 if (bitmap_bit_p (delta
, anything_id
))
978 return bitmap_set_bit (to
, anything_id
);
980 /* If the offset is unknown we have to expand the solution to
982 if (inc
== UNKNOWN_OFFSET
)
984 delta
= solution_set_expand (delta
, expanded_delta
);
985 changed
|= bitmap_ior_into (to
, delta
);
989 /* For non-zero offset union the offsetted solution into the destination. */
990 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, i
, bi
)
992 varinfo_t vi
= get_varinfo (i
);
994 /* If this is a variable with just one field just set its bit
996 if (vi
->is_artificial_var
997 || vi
->is_unknown_size_var
999 changed
|= bitmap_set_bit (to
, i
);
1002 HOST_WIDE_INT fieldoffset
= vi
->offset
+ inc
;
1003 unsigned HOST_WIDE_INT size
= vi
->size
;
1005 /* If the offset makes the pointer point to before the
1006 variable use offset zero for the field lookup. */
1007 if (fieldoffset
< 0)
1008 vi
= get_varinfo (vi
->head
);
1010 vi
= first_or_preceding_vi_for_offset (vi
, fieldoffset
);
1014 changed
|= bitmap_set_bit (to
, vi
->id
);
1019 /* We have to include all fields that overlap the current field
1023 while (vi
->offset
< fieldoffset
+ size
);
1030 /* Insert constraint C into the list of complex constraints for graph
1034 insert_into_complex (constraint_graph_t graph
,
1035 unsigned int var
, constraint_t c
)
1037 vec
<constraint_t
> complex = graph
->complex[var
];
1038 unsigned int place
= complex.lower_bound (c
, constraint_less
);
1040 /* Only insert constraints that do not already exist. */
1041 if (place
>= complex.length ()
1042 || !constraint_equal (*c
, *complex[place
]))
1043 graph
->complex[var
].safe_insert (place
, c
);
1047 /* Condense two variable nodes into a single variable node, by moving
1048 all associated info from FROM to TO. Returns true if TO node's
1049 constraint set changes after the merge. */
1052 merge_node_constraints (constraint_graph_t graph
, unsigned int to
,
1057 bool any_change
= false;
1059 gcc_checking_assert (find (from
) == to
);
1061 /* Move all complex constraints from src node into to node */
1062 FOR_EACH_VEC_ELT (graph
->complex[from
], i
, c
)
1064 /* In complex constraints for node FROM, we may have either
1065 a = *FROM, and *FROM = a, or an offseted constraint which are
1066 always added to the rhs node's constraints. */
1068 if (c
->rhs
.type
== DEREF
)
1070 else if (c
->lhs
.type
== DEREF
)
1076 any_change
= constraint_set_union (&graph
->complex[to
],
1077 &graph
->complex[from
]);
1078 graph
->complex[from
].release ();
1083 /* Remove edges involving NODE from GRAPH. */
1086 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
1088 if (graph
->succs
[node
])
1089 BITMAP_FREE (graph
->succs
[node
]);
1092 /* Merge GRAPH nodes FROM and TO into node TO. */
1095 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1098 if (graph
->indirect_cycles
[from
] != -1)
1100 /* If we have indirect cycles with the from node, and we have
1101 none on the to node, the to node has indirect cycles from the
1102 from node now that they are unified.
1103 If indirect cycles exist on both, unify the nodes that they
1104 are in a cycle with, since we know they are in a cycle with
1106 if (graph
->indirect_cycles
[to
] == -1)
1107 graph
->indirect_cycles
[to
] = graph
->indirect_cycles
[from
];
1110 /* Merge all the successor edges. */
1111 if (graph
->succs
[from
])
1113 if (!graph
->succs
[to
])
1114 graph
->succs
[to
] = BITMAP_ALLOC (&pta_obstack
);
1115 bitmap_ior_into (graph
->succs
[to
],
1116 graph
->succs
[from
]);
1119 clear_edges_for_node (graph
, from
);
1123 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1124 it doesn't exist in the graph already. */
1127 add_implicit_graph_edge (constraint_graph_t graph
, unsigned int to
,
1133 if (!graph
->implicit_preds
[to
])
1134 graph
->implicit_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1136 if (bitmap_set_bit (graph
->implicit_preds
[to
], from
))
1137 stats
.num_implicit_edges
++;
1140 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1141 it doesn't exist in the graph already.
1142 Return false if the edge already existed, true otherwise. */
1145 add_pred_graph_edge (constraint_graph_t graph
, unsigned int to
,
1148 if (!graph
->preds
[to
])
1149 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1150 bitmap_set_bit (graph
->preds
[to
], from
);
1153 /* Add a graph edge to GRAPH, going from FROM to TO if
1154 it doesn't exist in the graph already.
1155 Return false if the edge already existed, true otherwise. */
1158 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1169 if (!graph
->succs
[from
])
1170 graph
->succs
[from
] = BITMAP_ALLOC (&pta_obstack
);
1171 if (bitmap_set_bit (graph
->succs
[from
], to
))
1174 if (to
< FIRST_REF_NODE
&& from
< FIRST_REF_NODE
)
1182 /* Initialize the constraint graph structure to contain SIZE nodes. */
1185 init_graph (unsigned int size
)
1189 graph
= XCNEW (struct constraint_graph
);
1191 graph
->succs
= XCNEWVEC (bitmap
, graph
->size
);
1192 graph
->indirect_cycles
= XNEWVEC (int, graph
->size
);
1193 graph
->rep
= XNEWVEC (unsigned int, graph
->size
);
1194 /* ??? Macros do not support template types with multiple arguments,
1195 so we use a typedef to work around it. */
1196 typedef vec
<constraint_t
> vec_constraint_t_heap
;
1197 graph
->complex = XCNEWVEC (vec_constraint_t_heap
, size
);
1198 graph
->pe
= XCNEWVEC (unsigned int, graph
->size
);
1199 graph
->pe_rep
= XNEWVEC (int, graph
->size
);
1201 for (j
= 0; j
< graph
->size
; j
++)
1204 graph
->pe_rep
[j
] = -1;
1205 graph
->indirect_cycles
[j
] = -1;
1209 /* Build the constraint graph, adding only predecessor edges right now. */
1212 build_pred_graph (void)
1218 graph
->implicit_preds
= XCNEWVEC (bitmap
, graph
->size
);
1219 graph
->preds
= XCNEWVEC (bitmap
, graph
->size
);
1220 graph
->pointer_label
= XCNEWVEC (unsigned int, graph
->size
);
1221 graph
->loc_label
= XCNEWVEC (unsigned int, graph
->size
);
1222 graph
->pointed_by
= XCNEWVEC (bitmap
, graph
->size
);
1223 graph
->points_to
= XCNEWVEC (bitmap
, graph
->size
);
1224 graph
->eq_rep
= XNEWVEC (int, graph
->size
);
1225 graph
->direct_nodes
= sbitmap_alloc (graph
->size
);
1226 graph
->address_taken
= BITMAP_ALLOC (&predbitmap_obstack
);
1227 bitmap_clear (graph
->direct_nodes
);
1229 for (j
= 1; j
< FIRST_REF_NODE
; j
++)
1231 if (!get_varinfo (j
)->is_special_var
)
1232 bitmap_set_bit (graph
->direct_nodes
, j
);
1235 for (j
= 0; j
< graph
->size
; j
++)
1236 graph
->eq_rep
[j
] = -1;
1238 for (j
= 0; j
< varmap
.length (); j
++)
1239 graph
->indirect_cycles
[j
] = -1;
1241 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1243 struct constraint_expr lhs
= c
->lhs
;
1244 struct constraint_expr rhs
= c
->rhs
;
1245 unsigned int lhsvar
= lhs
.var
;
1246 unsigned int rhsvar
= rhs
.var
;
1248 if (lhs
.type
== DEREF
)
1251 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1252 add_pred_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1254 else if (rhs
.type
== DEREF
)
1257 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1258 add_pred_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1260 bitmap_clear_bit (graph
->direct_nodes
, lhsvar
);
1262 else if (rhs
.type
== ADDRESSOF
)
1267 if (graph
->points_to
[lhsvar
] == NULL
)
1268 graph
->points_to
[lhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1269 bitmap_set_bit (graph
->points_to
[lhsvar
], rhsvar
);
1271 if (graph
->pointed_by
[rhsvar
] == NULL
)
1272 graph
->pointed_by
[rhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1273 bitmap_set_bit (graph
->pointed_by
[rhsvar
], lhsvar
);
1275 /* Implicitly, *x = y */
1276 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1278 /* All related variables are no longer direct nodes. */
1279 bitmap_clear_bit (graph
->direct_nodes
, rhsvar
);
1280 v
= get_varinfo (rhsvar
);
1281 if (!v
->is_full_var
)
1283 v
= get_varinfo (v
->head
);
1286 bitmap_clear_bit (graph
->direct_nodes
, v
->id
);
1291 bitmap_set_bit (graph
->address_taken
, rhsvar
);
1293 else if (lhsvar
> anything_id
1294 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1297 add_pred_graph_edge (graph
, lhsvar
, rhsvar
);
1298 /* Implicitly, *x = *y */
1299 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
,
1300 FIRST_REF_NODE
+ rhsvar
);
1302 else if (lhs
.offset
!= 0 || rhs
.offset
!= 0)
1304 if (rhs
.offset
!= 0)
1305 bitmap_clear_bit (graph
->direct_nodes
, lhs
.var
);
1306 else if (lhs
.offset
!= 0)
1307 bitmap_clear_bit (graph
->direct_nodes
, rhs
.var
);
1312 /* Build the constraint graph, adding successor edges. */
1315 build_succ_graph (void)
1320 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1322 struct constraint_expr lhs
;
1323 struct constraint_expr rhs
;
1324 unsigned int lhsvar
;
1325 unsigned int rhsvar
;
1332 lhsvar
= find (lhs
.var
);
1333 rhsvar
= find (rhs
.var
);
1335 if (lhs
.type
== DEREF
)
1337 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1338 add_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1340 else if (rhs
.type
== DEREF
)
1342 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1343 add_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1345 else if (rhs
.type
== ADDRESSOF
)
1348 gcc_checking_assert (find (rhs
.var
) == rhs
.var
);
1349 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1351 else if (lhsvar
> anything_id
1352 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1354 add_graph_edge (graph
, lhsvar
, rhsvar
);
1358 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1359 receive pointers. */
1360 t
= find (storedanything_id
);
1361 for (i
= integer_id
+ 1; i
< FIRST_REF_NODE
; ++i
)
1363 if (!bitmap_bit_p (graph
->direct_nodes
, i
)
1364 && get_varinfo (i
)->may_have_pointers
)
1365 add_graph_edge (graph
, find (i
), t
);
1368 /* Everything stored to ANYTHING also potentially escapes. */
1369 add_graph_edge (graph
, find (escaped_id
), t
);
1373 /* Changed variables on the last iteration. */
1374 static bitmap changed
;
1376 /* Strongly Connected Component visitation info. */
1383 unsigned int *node_mapping
;
1385 vec
<unsigned> scc_stack
;
1389 /* Recursive routine to find strongly connected components in GRAPH.
1390 SI is the SCC info to store the information in, and N is the id of current
1391 graph node we are processing.
1393 This is Tarjan's strongly connected component finding algorithm, as
1394 modified by Nuutila to keep only non-root nodes on the stack.
1395 The algorithm can be found in "On finding the strongly connected
1396 connected components in a directed graph" by Esko Nuutila and Eljas
1397 Soisalon-Soininen, in Information Processing Letters volume 49,
1398 number 1, pages 9-14. */
1401 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1405 unsigned int my_dfs
;
1407 bitmap_set_bit (si
->visited
, n
);
1408 si
->dfs
[n
] = si
->current_index
++;
1409 my_dfs
= si
->dfs
[n
];
1411 /* Visit all the successors. */
1412 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
1416 if (i
> LAST_REF_NODE
)
1420 if (bitmap_bit_p (si
->deleted
, w
))
1423 if (!bitmap_bit_p (si
->visited
, w
))
1424 scc_visit (graph
, si
, w
);
1426 unsigned int t
= find (w
);
1427 gcc_checking_assert (find (n
) == n
);
1428 if (si
->dfs
[t
] < si
->dfs
[n
])
1429 si
->dfs
[n
] = si
->dfs
[t
];
1432 /* See if any components have been identified. */
1433 if (si
->dfs
[n
] == my_dfs
)
1435 if (si
->scc_stack
.length () > 0
1436 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1438 bitmap scc
= BITMAP_ALLOC (NULL
);
1439 unsigned int lowest_node
;
1442 bitmap_set_bit (scc
, n
);
1444 while (si
->scc_stack
.length () != 0
1445 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1447 unsigned int w
= si
->scc_stack
.pop ();
1449 bitmap_set_bit (scc
, w
);
1452 lowest_node
= bitmap_first_set_bit (scc
);
1453 gcc_assert (lowest_node
< FIRST_REF_NODE
);
1455 /* Collapse the SCC nodes into a single node, and mark the
1457 EXECUTE_IF_SET_IN_BITMAP (scc
, 0, i
, bi
)
1459 if (i
< FIRST_REF_NODE
)
1461 if (unite (lowest_node
, i
))
1462 unify_nodes (graph
, lowest_node
, i
, false);
1466 unite (lowest_node
, i
);
1467 graph
->indirect_cycles
[i
- FIRST_REF_NODE
] = lowest_node
;
1471 bitmap_set_bit (si
->deleted
, n
);
1474 si
->scc_stack
.safe_push (n
);
1477 /* Unify node FROM into node TO, updating the changed count if
1478 necessary when UPDATE_CHANGED is true. */
1481 unify_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1482 bool update_changed
)
1484 gcc_checking_assert (to
!= from
&& find (to
) == to
);
1486 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1487 fprintf (dump_file
, "Unifying %s to %s\n",
1488 get_varinfo (from
)->name
,
1489 get_varinfo (to
)->name
);
1492 stats
.unified_vars_dynamic
++;
1494 stats
.unified_vars_static
++;
1496 merge_graph_nodes (graph
, to
, from
);
1497 if (merge_node_constraints (graph
, to
, from
))
1500 bitmap_set_bit (changed
, to
);
1503 /* Mark TO as changed if FROM was changed. If TO was already marked
1504 as changed, decrease the changed count. */
1507 && bitmap_clear_bit (changed
, from
))
1508 bitmap_set_bit (changed
, to
);
1509 varinfo_t fromvi
= get_varinfo (from
);
1510 if (fromvi
->solution
)
1512 /* If the solution changes because of the merging, we need to mark
1513 the variable as changed. */
1514 varinfo_t tovi
= get_varinfo (to
);
1515 if (bitmap_ior_into (tovi
->solution
, fromvi
->solution
))
1518 bitmap_set_bit (changed
, to
);
1521 BITMAP_FREE (fromvi
->solution
);
1522 if (fromvi
->oldsolution
)
1523 BITMAP_FREE (fromvi
->oldsolution
);
1525 if (stats
.iterations
> 0
1526 && tovi
->oldsolution
)
1527 BITMAP_FREE (tovi
->oldsolution
);
1529 if (graph
->succs
[to
])
1530 bitmap_clear_bit (graph
->succs
[to
], to
);
1533 /* Information needed to compute the topological ordering of a graph. */
1537 /* sbitmap of visited nodes. */
1539 /* Array that stores the topological order of the graph, *in
1541 vec
<unsigned> topo_order
;
1545 /* Initialize and return a topological info structure. */
1547 static struct topo_info
*
1548 init_topo_info (void)
1550 size_t size
= graph
->size
;
1551 struct topo_info
*ti
= XNEW (struct topo_info
);
1552 ti
->visited
= sbitmap_alloc (size
);
1553 bitmap_clear (ti
->visited
);
1554 ti
->topo_order
.create (1);
1559 /* Free the topological sort info pointed to by TI. */
1562 free_topo_info (struct topo_info
*ti
)
1564 sbitmap_free (ti
->visited
);
1565 ti
->topo_order
.release ();
1569 /* Visit the graph in topological order, and store the order in the
1570 topo_info structure. */
1573 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1579 bitmap_set_bit (ti
->visited
, n
);
1581 if (graph
->succs
[n
])
1582 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[n
], 0, j
, bi
)
1584 if (!bitmap_bit_p (ti
->visited
, j
))
1585 topo_visit (graph
, ti
, j
);
1588 ti
->topo_order
.safe_push (n
);
1591 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1592 starting solution for y. */
1595 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1596 bitmap delta
, bitmap
*expanded_delta
)
1598 unsigned int lhs
= c
->lhs
.var
;
1600 bitmap sol
= get_varinfo (lhs
)->solution
;
1603 HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1605 /* Our IL does not allow this. */
1606 gcc_checking_assert (c
->lhs
.offset
== 0);
1608 /* If the solution of Y contains anything it is good enough to transfer
1610 if (bitmap_bit_p (delta
, anything_id
))
1612 flag
|= bitmap_set_bit (sol
, anything_id
);
1616 /* If we do not know at with offset the rhs is dereferenced compute
1617 the reachability set of DELTA, conservatively assuming it is
1618 dereferenced at all valid offsets. */
1619 if (roffset
== UNKNOWN_OFFSET
)
1621 delta
= solution_set_expand (delta
, expanded_delta
);
1622 /* No further offset processing is necessary. */
1626 /* For each variable j in delta (Sol(y)), add
1627 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1628 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1630 varinfo_t v
= get_varinfo (j
);
1631 HOST_WIDE_INT fieldoffset
= v
->offset
+ roffset
;
1632 unsigned HOST_WIDE_INT size
= v
->size
;
1637 else if (roffset
!= 0)
1639 if (fieldoffset
< 0)
1640 v
= get_varinfo (v
->head
);
1642 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1645 /* We have to include all fields that overlap the current field
1646 shifted by roffset. */
1651 /* Adding edges from the special vars is pointless.
1652 They don't have sets that can change. */
1653 if (get_varinfo (t
)->is_special_var
)
1654 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1655 /* Merging the solution from ESCAPED needlessly increases
1656 the set. Use ESCAPED as representative instead. */
1657 else if (v
->id
== escaped_id
)
1658 flag
|= bitmap_set_bit (sol
, escaped_id
);
1659 else if (v
->may_have_pointers
1660 && add_graph_edge (graph
, lhs
, t
))
1661 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1669 while (v
->offset
< fieldoffset
+ size
);
1673 /* If the LHS solution changed, mark the var as changed. */
1676 get_varinfo (lhs
)->solution
= sol
;
1677 bitmap_set_bit (changed
, lhs
);
1681 /* Process a constraint C that represents *(x + off) = y using DELTA
1682 as the starting solution for x. */
1685 do_ds_constraint (constraint_t c
, bitmap delta
, bitmap
*expanded_delta
)
1687 unsigned int rhs
= c
->rhs
.var
;
1688 bitmap sol
= get_varinfo (rhs
)->solution
;
1691 HOST_WIDE_INT loff
= c
->lhs
.offset
;
1692 bool escaped_p
= false;
1694 /* Our IL does not allow this. */
1695 gcc_checking_assert (c
->rhs
.offset
== 0);
1697 /* If the solution of y contains ANYTHING simply use the ANYTHING
1698 solution. This avoids needlessly increasing the points-to sets. */
1699 if (bitmap_bit_p (sol
, anything_id
))
1700 sol
= get_varinfo (find (anything_id
))->solution
;
1702 /* If the solution for x contains ANYTHING we have to merge the
1703 solution of y into all pointer variables which we do via
1705 if (bitmap_bit_p (delta
, anything_id
))
1707 unsigned t
= find (storedanything_id
);
1708 if (add_graph_edge (graph
, t
, rhs
))
1710 if (bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1711 bitmap_set_bit (changed
, t
);
1716 /* If we do not know at with offset the rhs is dereferenced compute
1717 the reachability set of DELTA, conservatively assuming it is
1718 dereferenced at all valid offsets. */
1719 if (loff
== UNKNOWN_OFFSET
)
1721 delta
= solution_set_expand (delta
, expanded_delta
);
1725 /* For each member j of delta (Sol(x)), add an edge from y to j and
1726 union Sol(y) into Sol(j) */
1727 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1729 varinfo_t v
= get_varinfo (j
);
1731 HOST_WIDE_INT fieldoffset
= v
->offset
+ loff
;
1732 unsigned HOST_WIDE_INT size
= v
->size
;
1738 if (fieldoffset
< 0)
1739 v
= get_varinfo (v
->head
);
1741 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1744 /* We have to include all fields that overlap the current field
1748 if (v
->may_have_pointers
)
1750 /* If v is a global variable then this is an escape point. */
1751 if (v
->is_global_var
1754 t
= find (escaped_id
);
1755 if (add_graph_edge (graph
, t
, rhs
)
1756 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1757 bitmap_set_bit (changed
, t
);
1758 /* Enough to let rhs escape once. */
1762 if (v
->is_special_var
)
1766 if (add_graph_edge (graph
, t
, rhs
)
1767 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1768 bitmap_set_bit (changed
, t
);
1777 while (v
->offset
< fieldoffset
+ size
);
1781 /* Handle a non-simple (simple meaning requires no iteration),
1782 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1785 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
,
1786 bitmap
*expanded_delta
)
1788 if (c
->lhs
.type
== DEREF
)
1790 if (c
->rhs
.type
== ADDRESSOF
)
1797 do_ds_constraint (c
, delta
, expanded_delta
);
1800 else if (c
->rhs
.type
== DEREF
)
1803 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1804 do_sd_constraint (graph
, c
, delta
, expanded_delta
);
1811 gcc_checking_assert (c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
1812 && c
->rhs
.offset
!= 0 && c
->lhs
.offset
== 0);
1813 tmp
= get_varinfo (c
->lhs
.var
)->solution
;
1815 flag
= set_union_with_increment (tmp
, delta
, c
->rhs
.offset
,
1819 bitmap_set_bit (changed
, c
->lhs
.var
);
1823 /* Initialize and return a new SCC info structure. */
1825 static struct scc_info
*
1826 init_scc_info (size_t size
)
1828 struct scc_info
*si
= XNEW (struct scc_info
);
1831 si
->current_index
= 0;
1832 si
->visited
= sbitmap_alloc (size
);
1833 bitmap_clear (si
->visited
);
1834 si
->deleted
= sbitmap_alloc (size
);
1835 bitmap_clear (si
->deleted
);
1836 si
->node_mapping
= XNEWVEC (unsigned int, size
);
1837 si
->dfs
= XCNEWVEC (unsigned int, size
);
1839 for (i
= 0; i
< size
; i
++)
1840 si
->node_mapping
[i
] = i
;
1842 si
->scc_stack
.create (1);
1846 /* Free an SCC info structure pointed to by SI */
1849 free_scc_info (struct scc_info
*si
)
1851 sbitmap_free (si
->visited
);
1852 sbitmap_free (si
->deleted
);
1853 free (si
->node_mapping
);
1855 si
->scc_stack
.release ();
1860 /* Find indirect cycles in GRAPH that occur, using strongly connected
1861 components, and note them in the indirect cycles map.
1863 This technique comes from Ben Hardekopf and Calvin Lin,
1864 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1865 Lines of Code", submitted to PLDI 2007. */
1868 find_indirect_cycles (constraint_graph_t graph
)
1871 unsigned int size
= graph
->size
;
1872 struct scc_info
*si
= init_scc_info (size
);
1874 for (i
= 0; i
< MIN (LAST_REF_NODE
, size
); i
++ )
1875 if (!bitmap_bit_p (si
->visited
, i
) && find (i
) == i
)
1876 scc_visit (graph
, si
, i
);
1881 /* Compute a topological ordering for GRAPH, and store the result in the
1882 topo_info structure TI. */
1885 compute_topo_order (constraint_graph_t graph
,
1886 struct topo_info
*ti
)
1889 unsigned int size
= graph
->size
;
1891 for (i
= 0; i
!= size
; ++i
)
1892 if (!bitmap_bit_p (ti
->visited
, i
) && find (i
) == i
)
1893 topo_visit (graph
, ti
, i
);
1896 /* Structure used to for hash value numbering of pointer equivalence
1899 typedef struct equiv_class_label
1902 unsigned int equivalence_class
;
1904 } *equiv_class_label_t
;
1905 typedef const struct equiv_class_label
*const_equiv_class_label_t
;
1907 /* Equiv_class_label hashtable helpers. */
1909 struct equiv_class_hasher
: free_ptr_hash
<equiv_class_label
>
1911 static inline hashval_t
hash (const equiv_class_label
*);
1912 static inline bool equal (const equiv_class_label
*,
1913 const equiv_class_label
*);
1916 /* Hash function for a equiv_class_label_t */
1919 equiv_class_hasher::hash (const equiv_class_label
*ecl
)
1921 return ecl
->hashcode
;
1924 /* Equality function for two equiv_class_label_t's. */
1927 equiv_class_hasher::equal (const equiv_class_label
*eql1
,
1928 const equiv_class_label
*eql2
)
1930 return (eql1
->hashcode
== eql2
->hashcode
1931 && bitmap_equal_p (eql1
->labels
, eql2
->labels
));
1934 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1936 static hash_table
<equiv_class_hasher
> *pointer_equiv_class_table
;
1938 /* A hashtable for mapping a bitmap of labels->location equivalence
1940 static hash_table
<equiv_class_hasher
> *location_equiv_class_table
;
1942 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1943 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1944 is equivalent to. */
1946 static equiv_class_label
*
1947 equiv_class_lookup_or_add (hash_table
<equiv_class_hasher
> *table
,
1950 equiv_class_label
**slot
;
1951 equiv_class_label ecl
;
1953 ecl
.labels
= labels
;
1954 ecl
.hashcode
= bitmap_hash (labels
);
1955 slot
= table
->find_slot (&ecl
, INSERT
);
1958 *slot
= XNEW (struct equiv_class_label
);
1959 (*slot
)->labels
= labels
;
1960 (*slot
)->hashcode
= ecl
.hashcode
;
1961 (*slot
)->equivalence_class
= 0;
1967 /* Perform offline variable substitution.
1969 This is a worst case quadratic time way of identifying variables
1970 that must have equivalent points-to sets, including those caused by
1971 static cycles, and single entry subgraphs, in the constraint graph.
1973 The technique is described in "Exploiting Pointer and Location
1974 Equivalence to Optimize Pointer Analysis. In the 14th International
1975 Static Analysis Symposium (SAS), August 2007." It is known as the
1976 "HU" algorithm, and is equivalent to value numbering the collapsed
1977 constraint graph including evaluating unions.
1979 The general method of finding equivalence classes is as follows:
1980 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1981 Initialize all non-REF nodes to be direct nodes.
1982 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1984 For each constraint containing the dereference, we also do the same
1987 We then compute SCC's in the graph and unify nodes in the same SCC,
1990 For each non-collapsed node x:
1991 Visit all unvisited explicit incoming edges.
1992 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1994 Lookup the equivalence class for pts(x).
1995 If we found one, equivalence_class(x) = found class.
1996 Otherwise, equivalence_class(x) = new class, and new_class is
1997 added to the lookup table.
1999 All direct nodes with the same equivalence class can be replaced
2000 with a single representative node.
2001 All unlabeled nodes (label == 0) are not pointers and all edges
2002 involving them can be eliminated.
2003 We perform these optimizations during rewrite_constraints
2005 In addition to pointer equivalence class finding, we also perform
2006 location equivalence class finding. This is the set of variables
2007 that always appear together in points-to sets. We use this to
2008 compress the size of the points-to sets. */
2010 /* Current maximum pointer equivalence class id. */
2011 static int pointer_equiv_class
;
2013 /* Current maximum location equivalence class id. */
2014 static int location_equiv_class
;
2016 /* Recursive routine to find strongly connected components in GRAPH,
2017 and label it's nodes with DFS numbers. */
2020 condense_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2024 unsigned int my_dfs
;
2026 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2027 bitmap_set_bit (si
->visited
, n
);
2028 si
->dfs
[n
] = si
->current_index
++;
2029 my_dfs
= si
->dfs
[n
];
2031 /* Visit all the successors. */
2032 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2034 unsigned int w
= si
->node_mapping
[i
];
2036 if (bitmap_bit_p (si
->deleted
, w
))
2039 if (!bitmap_bit_p (si
->visited
, w
))
2040 condense_visit (graph
, si
, w
);
2042 unsigned int t
= si
->node_mapping
[w
];
2043 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2044 if (si
->dfs
[t
] < si
->dfs
[n
])
2045 si
->dfs
[n
] = si
->dfs
[t
];
2048 /* Visit all the implicit predecessors. */
2049 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->implicit_preds
[n
], 0, i
, bi
)
2051 unsigned int w
= si
->node_mapping
[i
];
2053 if (bitmap_bit_p (si
->deleted
, w
))
2056 if (!bitmap_bit_p (si
->visited
, w
))
2057 condense_visit (graph
, si
, w
);
2059 unsigned int t
= si
->node_mapping
[w
];
2060 gcc_assert (si
->node_mapping
[n
] == n
);
2061 if (si
->dfs
[t
] < si
->dfs
[n
])
2062 si
->dfs
[n
] = si
->dfs
[t
];
2065 /* See if any components have been identified. */
2066 if (si
->dfs
[n
] == my_dfs
)
2068 while (si
->scc_stack
.length () != 0
2069 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
2071 unsigned int w
= si
->scc_stack
.pop ();
2072 si
->node_mapping
[w
] = n
;
2074 if (!bitmap_bit_p (graph
->direct_nodes
, w
))
2075 bitmap_clear_bit (graph
->direct_nodes
, n
);
2077 /* Unify our nodes. */
2078 if (graph
->preds
[w
])
2080 if (!graph
->preds
[n
])
2081 graph
->preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2082 bitmap_ior_into (graph
->preds
[n
], graph
->preds
[w
]);
2084 if (graph
->implicit_preds
[w
])
2086 if (!graph
->implicit_preds
[n
])
2087 graph
->implicit_preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2088 bitmap_ior_into (graph
->implicit_preds
[n
],
2089 graph
->implicit_preds
[w
]);
2091 if (graph
->points_to
[w
])
2093 if (!graph
->points_to
[n
])
2094 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2095 bitmap_ior_into (graph
->points_to
[n
],
2096 graph
->points_to
[w
]);
2099 bitmap_set_bit (si
->deleted
, n
);
2102 si
->scc_stack
.safe_push (n
);
2105 /* Label pointer equivalences.
2107 This performs a value numbering of the constraint graph to
2108 discover which variables will always have the same points-to sets
2109 under the current set of constraints.
2111 The way it value numbers is to store the set of points-to bits
2112 generated by the constraints and graph edges. This is just used as a
2113 hash and equality comparison. The *actual set of points-to bits* is
2114 completely irrelevant, in that we don't care about being able to
2117 The equality values (currently bitmaps) just have to satisfy a few
2118 constraints, the main ones being:
2119 1. The combining operation must be order independent.
2120 2. The end result of a given set of operations must be unique iff the
2121 combination of input values is unique
2125 label_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2127 unsigned int i
, first_pred
;
2130 bitmap_set_bit (si
->visited
, n
);
2132 /* Label and union our incoming edges's points to sets. */
2134 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2136 unsigned int w
= si
->node_mapping
[i
];
2137 if (!bitmap_bit_p (si
->visited
, w
))
2138 label_visit (graph
, si
, w
);
2140 /* Skip unused edges */
2141 if (w
== n
|| graph
->pointer_label
[w
] == 0)
2144 if (graph
->points_to
[w
])
2146 if (!graph
->points_to
[n
])
2148 if (first_pred
== -1U)
2152 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2153 bitmap_ior (graph
->points_to
[n
],
2154 graph
->points_to
[first_pred
],
2155 graph
->points_to
[w
]);
2159 bitmap_ior_into (graph
->points_to
[n
], graph
->points_to
[w
]);
2163 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2164 if (!bitmap_bit_p (graph
->direct_nodes
, n
))
2166 if (!graph
->points_to
[n
])
2168 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2169 if (first_pred
!= -1U)
2170 bitmap_copy (graph
->points_to
[n
], graph
->points_to
[first_pred
]);
2172 bitmap_set_bit (graph
->points_to
[n
], FIRST_REF_NODE
+ n
);
2173 graph
->pointer_label
[n
] = pointer_equiv_class
++;
2174 equiv_class_label_t ecl
;
2175 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2176 graph
->points_to
[n
]);
2177 ecl
->equivalence_class
= graph
->pointer_label
[n
];
2181 /* If there was only a single non-empty predecessor the pointer equiv
2182 class is the same. */
2183 if (!graph
->points_to
[n
])
2185 if (first_pred
!= -1U)
2187 graph
->pointer_label
[n
] = graph
->pointer_label
[first_pred
];
2188 graph
->points_to
[n
] = graph
->points_to
[first_pred
];
2193 if (!bitmap_empty_p (graph
->points_to
[n
]))
2195 equiv_class_label_t ecl
;
2196 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2197 graph
->points_to
[n
]);
2198 if (ecl
->equivalence_class
== 0)
2199 ecl
->equivalence_class
= pointer_equiv_class
++;
2202 BITMAP_FREE (graph
->points_to
[n
]);
2203 graph
->points_to
[n
] = ecl
->labels
;
2205 graph
->pointer_label
[n
] = ecl
->equivalence_class
;
2209 /* Print the pred graph in dot format. */
2212 dump_pred_graph (struct scc_info
*si
, FILE *file
)
2216 /* Only print the graph if it has already been initialized: */
2220 /* Prints the header of the dot file: */
2221 fprintf (file
, "strict digraph {\n");
2222 fprintf (file
, " node [\n shape = box\n ]\n");
2223 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
2224 fprintf (file
, "\n // List of nodes and complex constraints in "
2225 "the constraint graph:\n");
2227 /* The next lines print the nodes in the graph together with the
2228 complex constraints attached to them. */
2229 for (i
= 1; i
< graph
->size
; i
++)
2231 if (i
== FIRST_REF_NODE
)
2233 if (si
->node_mapping
[i
] != i
)
2235 if (i
< FIRST_REF_NODE
)
2236 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2238 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2239 if (graph
->points_to
[i
]
2240 && !bitmap_empty_p (graph
->points_to
[i
]))
2242 fprintf (file
, "[label=\"%s = {", get_varinfo (i
)->name
);
2245 EXECUTE_IF_SET_IN_BITMAP (graph
->points_to
[i
], 0, j
, bi
)
2246 fprintf (file
, " %d", j
);
2247 fprintf (file
, " }\"]");
2249 fprintf (file
, ";\n");
2252 /* Go over the edges. */
2253 fprintf (file
, "\n // Edges in the constraint graph:\n");
2254 for (i
= 1; i
< graph
->size
; i
++)
2258 if (si
->node_mapping
[i
] != i
)
2260 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[i
], 0, j
, bi
)
2262 unsigned from
= si
->node_mapping
[j
];
2263 if (from
< FIRST_REF_NODE
)
2264 fprintf (file
, "\"%s\"", get_varinfo (from
)->name
);
2266 fprintf (file
, "\"*%s\"", get_varinfo (from
- FIRST_REF_NODE
)->name
);
2267 fprintf (file
, " -> ");
2268 if (i
< FIRST_REF_NODE
)
2269 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2271 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2272 fprintf (file
, ";\n");
2276 /* Prints the tail of the dot file. */
2277 fprintf (file
, "}\n");
2280 /* Perform offline variable substitution, discovering equivalence
2281 classes, and eliminating non-pointer variables. */
2283 static struct scc_info
*
2284 perform_var_substitution (constraint_graph_t graph
)
2287 unsigned int size
= graph
->size
;
2288 struct scc_info
*si
= init_scc_info (size
);
2290 bitmap_obstack_initialize (&iteration_obstack
);
2291 pointer_equiv_class_table
= new hash_table
<equiv_class_hasher
> (511);
2292 location_equiv_class_table
2293 = new hash_table
<equiv_class_hasher
> (511);
2294 pointer_equiv_class
= 1;
2295 location_equiv_class
= 1;
2297 /* Condense the nodes, which means to find SCC's, count incoming
2298 predecessors, and unite nodes in SCC's. */
2299 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2300 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2301 condense_visit (graph
, si
, si
->node_mapping
[i
]);
2303 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
2305 fprintf (dump_file
, "\n\n// The constraint graph before var-substitution "
2306 "in dot format:\n");
2307 dump_pred_graph (si
, dump_file
);
2308 fprintf (dump_file
, "\n\n");
2311 bitmap_clear (si
->visited
);
2312 /* Actually the label the nodes for pointer equivalences */
2313 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2314 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2315 label_visit (graph
, si
, si
->node_mapping
[i
]);
2317 /* Calculate location equivalence labels. */
2318 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2324 if (!graph
->pointed_by
[i
])
2326 pointed_by
= BITMAP_ALLOC (&iteration_obstack
);
2328 /* Translate the pointed-by mapping for pointer equivalence
2330 EXECUTE_IF_SET_IN_BITMAP (graph
->pointed_by
[i
], 0, j
, bi
)
2332 bitmap_set_bit (pointed_by
,
2333 graph
->pointer_label
[si
->node_mapping
[j
]]);
2335 /* The original pointed_by is now dead. */
2336 BITMAP_FREE (graph
->pointed_by
[i
]);
2338 /* Look up the location equivalence label if one exists, or make
2340 equiv_class_label_t ecl
;
2341 ecl
= equiv_class_lookup_or_add (location_equiv_class_table
, pointed_by
);
2342 if (ecl
->equivalence_class
== 0)
2343 ecl
->equivalence_class
= location_equiv_class
++;
2346 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2347 fprintf (dump_file
, "Found location equivalence for node %s\n",
2348 get_varinfo (i
)->name
);
2349 BITMAP_FREE (pointed_by
);
2351 graph
->loc_label
[i
] = ecl
->equivalence_class
;
2355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2356 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2358 unsigned j
= si
->node_mapping
[i
];
2361 fprintf (dump_file
, "%s node id %d ",
2362 bitmap_bit_p (graph
->direct_nodes
, i
)
2363 ? "Direct" : "Indirect", i
);
2364 if (i
< FIRST_REF_NODE
)
2365 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2367 fprintf (dump_file
, "\"*%s\"",
2368 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2369 fprintf (dump_file
, " mapped to SCC leader node id %d ", j
);
2370 if (j
< FIRST_REF_NODE
)
2371 fprintf (dump_file
, "\"%s\"\n", get_varinfo (j
)->name
);
2373 fprintf (dump_file
, "\"*%s\"\n",
2374 get_varinfo (j
- FIRST_REF_NODE
)->name
);
2379 "Equivalence classes for %s node id %d ",
2380 bitmap_bit_p (graph
->direct_nodes
, i
)
2381 ? "direct" : "indirect", i
);
2382 if (i
< FIRST_REF_NODE
)
2383 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2385 fprintf (dump_file
, "\"*%s\"",
2386 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2388 ": pointer %d, location %d\n",
2389 graph
->pointer_label
[i
], graph
->loc_label
[i
]);
2393 /* Quickly eliminate our non-pointer variables. */
2395 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2397 unsigned int node
= si
->node_mapping
[i
];
2399 if (graph
->pointer_label
[node
] == 0)
2401 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2403 "%s is a non-pointer variable, eliminating edges.\n",
2404 get_varinfo (node
)->name
);
2405 stats
.nonpointer_vars
++;
2406 clear_edges_for_node (graph
, node
);
2413 /* Free information that was only necessary for variable
2417 free_var_substitution_info (struct scc_info
*si
)
2420 free (graph
->pointer_label
);
2421 free (graph
->loc_label
);
2422 free (graph
->pointed_by
);
2423 free (graph
->points_to
);
2424 free (graph
->eq_rep
);
2425 sbitmap_free (graph
->direct_nodes
);
2426 delete pointer_equiv_class_table
;
2427 pointer_equiv_class_table
= NULL
;
2428 delete location_equiv_class_table
;
2429 location_equiv_class_table
= NULL
;
2430 bitmap_obstack_release (&iteration_obstack
);
2433 /* Return an existing node that is equivalent to NODE, which has
2434 equivalence class LABEL, if one exists. Return NODE otherwise. */
2437 find_equivalent_node (constraint_graph_t graph
,
2438 unsigned int node
, unsigned int label
)
2440 /* If the address version of this variable is unused, we can
2441 substitute it for anything else with the same label.
2442 Otherwise, we know the pointers are equivalent, but not the
2443 locations, and we can unite them later. */
2445 if (!bitmap_bit_p (graph
->address_taken
, node
))
2447 gcc_checking_assert (label
< graph
->size
);
2449 if (graph
->eq_rep
[label
] != -1)
2451 /* Unify the two variables since we know they are equivalent. */
2452 if (unite (graph
->eq_rep
[label
], node
))
2453 unify_nodes (graph
, graph
->eq_rep
[label
], node
, false);
2454 return graph
->eq_rep
[label
];
2458 graph
->eq_rep
[label
] = node
;
2459 graph
->pe_rep
[label
] = node
;
2464 gcc_checking_assert (label
< graph
->size
);
2465 graph
->pe
[node
] = label
;
2466 if (graph
->pe_rep
[label
] == -1)
2467 graph
->pe_rep
[label
] = node
;
2473 /* Unite pointer equivalent but not location equivalent nodes in
2474 GRAPH. This may only be performed once variable substitution is
2478 unite_pointer_equivalences (constraint_graph_t graph
)
2482 /* Go through the pointer equivalences and unite them to their
2483 representative, if they aren't already. */
2484 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2486 unsigned int label
= graph
->pe
[i
];
2489 int label_rep
= graph
->pe_rep
[label
];
2491 if (label_rep
== -1)
2494 label_rep
= find (label_rep
);
2495 if (label_rep
>= 0 && unite (label_rep
, find (i
)))
2496 unify_nodes (graph
, label_rep
, i
, false);
2501 /* Move complex constraints to the GRAPH nodes they belong to. */
2504 move_complex_constraints (constraint_graph_t graph
)
2509 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2513 struct constraint_expr lhs
= c
->lhs
;
2514 struct constraint_expr rhs
= c
->rhs
;
2516 if (lhs
.type
== DEREF
)
2518 insert_into_complex (graph
, lhs
.var
, c
);
2520 else if (rhs
.type
== DEREF
)
2522 if (!(get_varinfo (lhs
.var
)->is_special_var
))
2523 insert_into_complex (graph
, rhs
.var
, c
);
2525 else if (rhs
.type
!= ADDRESSOF
&& lhs
.var
> anything_id
2526 && (lhs
.offset
!= 0 || rhs
.offset
!= 0))
2528 insert_into_complex (graph
, rhs
.var
, c
);
2535 /* Optimize and rewrite complex constraints while performing
2536 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2537 result of perform_variable_substitution. */
2540 rewrite_constraints (constraint_graph_t graph
,
2541 struct scc_info
*si
)
2548 for (unsigned int j
= 0; j
< graph
->size
; j
++)
2549 gcc_assert (find (j
) == j
);
2552 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2554 struct constraint_expr lhs
= c
->lhs
;
2555 struct constraint_expr rhs
= c
->rhs
;
2556 unsigned int lhsvar
= find (lhs
.var
);
2557 unsigned int rhsvar
= find (rhs
.var
);
2558 unsigned int lhsnode
, rhsnode
;
2559 unsigned int lhslabel
, rhslabel
;
2561 lhsnode
= si
->node_mapping
[lhsvar
];
2562 rhsnode
= si
->node_mapping
[rhsvar
];
2563 lhslabel
= graph
->pointer_label
[lhsnode
];
2564 rhslabel
= graph
->pointer_label
[rhsnode
];
2566 /* See if it is really a non-pointer variable, and if so, ignore
2570 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2573 fprintf (dump_file
, "%s is a non-pointer variable,"
2574 "ignoring constraint:",
2575 get_varinfo (lhs
.var
)->name
);
2576 dump_constraint (dump_file
, c
);
2577 fprintf (dump_file
, "\n");
2579 constraints
[i
] = NULL
;
2585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2588 fprintf (dump_file
, "%s is a non-pointer variable,"
2589 "ignoring constraint:",
2590 get_varinfo (rhs
.var
)->name
);
2591 dump_constraint (dump_file
, c
);
2592 fprintf (dump_file
, "\n");
2594 constraints
[i
] = NULL
;
2598 lhsvar
= find_equivalent_node (graph
, lhsvar
, lhslabel
);
2599 rhsvar
= find_equivalent_node (graph
, rhsvar
, rhslabel
);
2600 c
->lhs
.var
= lhsvar
;
2601 c
->rhs
.var
= rhsvar
;
2605 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2606 part of an SCC, false otherwise. */
2609 eliminate_indirect_cycles (unsigned int node
)
2611 if (graph
->indirect_cycles
[node
] != -1
2612 && !bitmap_empty_p (get_varinfo (node
)->solution
))
2615 auto_vec
<unsigned> queue
;
2617 unsigned int to
= find (graph
->indirect_cycles
[node
]);
2620 /* We can't touch the solution set and call unify_nodes
2621 at the same time, because unify_nodes is going to do
2622 bitmap unions into it. */
2624 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node
)->solution
, 0, i
, bi
)
2626 if (find (i
) == i
&& i
!= to
)
2629 queue
.safe_push (i
);
2634 queue
.iterate (queuepos
, &i
);
2637 unify_nodes (graph
, to
, i
, true);
2644 /* Solve the constraint graph GRAPH using our worklist solver.
2645 This is based on the PW* family of solvers from the "Efficient Field
2646 Sensitive Pointer Analysis for C" paper.
2647 It works by iterating over all the graph nodes, processing the complex
2648 constraints and propagating the copy constraints, until everything stops
2649 changed. This corresponds to steps 6-8 in the solving list given above. */
2652 solve_graph (constraint_graph_t graph
)
2654 unsigned int size
= graph
->size
;
2658 changed
= BITMAP_ALLOC (NULL
);
2660 /* Mark all initial non-collapsed nodes as changed. */
2661 for (i
= 1; i
< size
; i
++)
2663 varinfo_t ivi
= get_varinfo (i
);
2664 if (find (i
) == i
&& !bitmap_empty_p (ivi
->solution
)
2665 && ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
2666 || graph
->complex[i
].length () > 0))
2667 bitmap_set_bit (changed
, i
);
2670 /* Allocate a bitmap to be used to store the changed bits. */
2671 pts
= BITMAP_ALLOC (&pta_obstack
);
2673 while (!bitmap_empty_p (changed
))
2676 struct topo_info
*ti
= init_topo_info ();
2679 bitmap_obstack_initialize (&iteration_obstack
);
2681 compute_topo_order (graph
, ti
);
2683 while (ti
->topo_order
.length () != 0)
2686 i
= ti
->topo_order
.pop ();
2688 /* If this variable is not a representative, skip it. */
2692 /* In certain indirect cycle cases, we may merge this
2693 variable to another. */
2694 if (eliminate_indirect_cycles (i
) && find (i
) != i
)
2697 /* If the node has changed, we need to process the
2698 complex constraints and outgoing edges again. */
2699 if (bitmap_clear_bit (changed
, i
))
2704 vec
<constraint_t
> complex = graph
->complex[i
];
2705 varinfo_t vi
= get_varinfo (i
);
2706 bool solution_empty
;
2708 /* Compute the changed set of solution bits. If anything
2709 is in the solution just propagate that. */
2710 if (bitmap_bit_p (vi
->solution
, anything_id
))
2712 /* If anything is also in the old solution there is
2714 ??? But we shouldn't ended up with "changed" set ... */
2716 && bitmap_bit_p (vi
->oldsolution
, anything_id
))
2718 bitmap_copy (pts
, get_varinfo (find (anything_id
))->solution
);
2720 else if (vi
->oldsolution
)
2721 bitmap_and_compl (pts
, vi
->solution
, vi
->oldsolution
);
2723 bitmap_copy (pts
, vi
->solution
);
2725 if (bitmap_empty_p (pts
))
2728 if (vi
->oldsolution
)
2729 bitmap_ior_into (vi
->oldsolution
, pts
);
2732 vi
->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
2733 bitmap_copy (vi
->oldsolution
, pts
);
2736 solution
= vi
->solution
;
2737 solution_empty
= bitmap_empty_p (solution
);
2739 /* Process the complex constraints */
2740 bitmap expanded_pts
= NULL
;
2741 FOR_EACH_VEC_ELT (complex, j
, c
)
2743 /* XXX: This is going to unsort the constraints in
2744 some cases, which will occasionally add duplicate
2745 constraints during unification. This does not
2746 affect correctness. */
2747 c
->lhs
.var
= find (c
->lhs
.var
);
2748 c
->rhs
.var
= find (c
->rhs
.var
);
2750 /* The only complex constraint that can change our
2751 solution to non-empty, given an empty solution,
2752 is a constraint where the lhs side is receiving
2753 some set from elsewhere. */
2754 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2755 do_complex_constraint (graph
, c
, pts
, &expanded_pts
);
2757 BITMAP_FREE (expanded_pts
);
2759 solution_empty
= bitmap_empty_p (solution
);
2761 if (!solution_empty
)
2764 unsigned eff_escaped_id
= find (escaped_id
);
2766 /* Propagate solution to all successors. */
2767 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
2773 unsigned int to
= find (j
);
2774 tmp
= get_varinfo (to
)->solution
;
2777 /* Don't try to propagate to ourselves. */
2781 /* If we propagate from ESCAPED use ESCAPED as
2783 if (i
== eff_escaped_id
)
2784 flag
= bitmap_set_bit (tmp
, escaped_id
);
2786 flag
= bitmap_ior_into (tmp
, pts
);
2789 bitmap_set_bit (changed
, to
);
2794 free_topo_info (ti
);
2795 bitmap_obstack_release (&iteration_obstack
);
2799 BITMAP_FREE (changed
);
2800 bitmap_obstack_release (&oldpta_obstack
);
2803 /* Map from trees to variable infos. */
2804 static hash_map
<tree
, varinfo_t
> *vi_for_tree
;
2807 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2810 insert_vi_for_tree (tree t
, varinfo_t vi
)
2813 gcc_assert (!vi_for_tree
->put (t
, vi
));
2816 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2817 exist in the map, return NULL, otherwise, return the varinfo we found. */
2820 lookup_vi_for_tree (tree t
)
2822 varinfo_t
*slot
= vi_for_tree
->get (t
);
2829 /* Return a printable name for DECL */
2832 alias_get_name (tree decl
)
2834 const char *res
= NULL
;
2836 int num_printed
= 0;
2841 if (TREE_CODE (decl
) == SSA_NAME
)
2843 res
= get_name (decl
);
2845 num_printed
= asprintf (&temp
, "%s_%u", res
, SSA_NAME_VERSION (decl
));
2847 num_printed
= asprintf (&temp
, "_%u", SSA_NAME_VERSION (decl
));
2848 if (num_printed
> 0)
2850 res
= ggc_strdup (temp
);
2854 else if (DECL_P (decl
))
2856 if (DECL_ASSEMBLER_NAME_SET_P (decl
))
2857 res
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
2860 res
= get_name (decl
);
2863 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2864 if (num_printed
> 0)
2866 res
= ggc_strdup (temp
);
2878 /* Find the variable id for tree T in the map.
2879 If T doesn't exist in the map, create an entry for it and return it. */
2882 get_vi_for_tree (tree t
)
2884 varinfo_t
*slot
= vi_for_tree
->get (t
);
2887 unsigned int id
= create_variable_info_for (t
, alias_get_name (t
), false);
2888 return get_varinfo (id
);
2894 /* Get a scalar constraint expression for a new temporary variable. */
2896 static struct constraint_expr
2897 new_scalar_tmp_constraint_exp (const char *name
, bool add_id
)
2899 struct constraint_expr tmp
;
2902 vi
= new_var_info (NULL_TREE
, name
, add_id
);
2906 vi
->is_full_var
= 1;
2915 /* Get a constraint expression vector from an SSA_VAR_P node.
2916 If address_p is true, the result will be taken its address of. */
2919 get_constraint_for_ssa_var (tree t
, vec
<ce_s
> *results
, bool address_p
)
2921 struct constraint_expr cexpr
;
2924 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2925 gcc_assert (TREE_CODE (t
) == SSA_NAME
|| DECL_P (t
));
2927 /* For parameters, get at the points-to set for the actual parm
2929 if (TREE_CODE (t
) == SSA_NAME
2930 && SSA_NAME_IS_DEFAULT_DEF (t
)
2931 && (TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2932 || TREE_CODE (SSA_NAME_VAR (t
)) == RESULT_DECL
))
2934 get_constraint_for_ssa_var (SSA_NAME_VAR (t
), results
, address_p
);
2938 /* For global variables resort to the alias target. */
2939 if (TREE_CODE (t
) == VAR_DECL
2940 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
2942 varpool_node
*node
= varpool_node::get (t
);
2943 if (node
&& node
->alias
&& node
->analyzed
)
2945 node
= node
->ultimate_alias_target ();
2946 /* Canonicalize the PT uid of all aliases to the ultimate target.
2947 ??? Hopefully the set of aliases can't change in a way that
2948 changes the ultimate alias target. */
2949 gcc_assert ((! DECL_PT_UID_SET_P (node
->decl
)
2950 || DECL_PT_UID (node
->decl
) == DECL_UID (node
->decl
))
2951 && (! DECL_PT_UID_SET_P (t
)
2952 || DECL_PT_UID (t
) == DECL_UID (node
->decl
)));
2953 DECL_PT_UID (t
) = DECL_UID (node
->decl
);
2958 vi
= get_vi_for_tree (t
);
2960 cexpr
.type
= SCALAR
;
2963 /* If we are not taking the address of the constraint expr, add all
2964 sub-fiels of the variable as well. */
2966 && !vi
->is_full_var
)
2968 for (; vi
; vi
= vi_next (vi
))
2971 results
->safe_push (cexpr
);
2976 results
->safe_push (cexpr
);
2979 /* Process constraint T, performing various simplifications and then
2980 adding it to our list of overall constraints. */
2983 process_constraint (constraint_t t
)
2985 struct constraint_expr rhs
= t
->rhs
;
2986 struct constraint_expr lhs
= t
->lhs
;
2988 gcc_assert (rhs
.var
< varmap
.length ());
2989 gcc_assert (lhs
.var
< varmap
.length ());
2991 /* If we didn't get any useful constraint from the lhs we get
2992 &ANYTHING as fallback from get_constraint_for. Deal with
2993 it here by turning it into *ANYTHING. */
2994 if (lhs
.type
== ADDRESSOF
2995 && lhs
.var
== anything_id
)
2998 /* ADDRESSOF on the lhs is invalid. */
2999 gcc_assert (lhs
.type
!= ADDRESSOF
);
3001 /* We shouldn't add constraints from things that cannot have pointers.
3002 It's not completely trivial to avoid in the callers, so do it here. */
3003 if (rhs
.type
!= ADDRESSOF
3004 && !get_varinfo (rhs
.var
)->may_have_pointers
)
3007 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3008 if (!get_varinfo (lhs
.var
)->may_have_pointers
)
3011 /* This can happen in our IR with things like n->a = *p */
3012 if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
3014 /* Split into tmp = *rhs, *lhs = tmp */
3015 struct constraint_expr tmplhs
;
3016 tmplhs
= new_scalar_tmp_constraint_exp ("doubledereftmp", true);
3017 process_constraint (new_constraint (tmplhs
, rhs
));
3018 process_constraint (new_constraint (lhs
, tmplhs
));
3020 else if (rhs
.type
== ADDRESSOF
&& lhs
.type
== DEREF
)
3022 /* Split into tmp = &rhs, *lhs = tmp */
3023 struct constraint_expr tmplhs
;
3024 tmplhs
= new_scalar_tmp_constraint_exp ("derefaddrtmp", true);
3025 process_constraint (new_constraint (tmplhs
, rhs
));
3026 process_constraint (new_constraint (lhs
, tmplhs
));
3030 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
3031 constraints
.safe_push (t
);
3036 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3039 static HOST_WIDE_INT
3040 bitpos_of_field (const tree fdecl
)
3042 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl
))
3043 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl
)))
3046 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl
)) * BITS_PER_UNIT
3047 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl
)));
3051 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3052 resulting constraint expressions in *RESULTS. */
3055 get_constraint_for_ptr_offset (tree ptr
, tree offset
,
3058 struct constraint_expr c
;
3060 HOST_WIDE_INT rhsoffset
;
3062 /* If we do not do field-sensitive PTA adding offsets to pointers
3063 does not change the points-to solution. */
3064 if (!use_field_sensitive
)
3066 get_constraint_for_rhs (ptr
, results
);
3070 /* If the offset is not a non-negative integer constant that fits
3071 in a HOST_WIDE_INT, we have to fall back to a conservative
3072 solution which includes all sub-fields of all pointed-to
3073 variables of ptr. */
3074 if (offset
== NULL_TREE
3075 || TREE_CODE (offset
) != INTEGER_CST
)
3076 rhsoffset
= UNKNOWN_OFFSET
;
3079 /* Sign-extend the offset. */
3080 offset_int soffset
= offset_int::from (offset
, SIGNED
);
3081 if (!wi::fits_shwi_p (soffset
))
3082 rhsoffset
= UNKNOWN_OFFSET
;
3085 /* Make sure the bit-offset also fits. */
3086 HOST_WIDE_INT rhsunitoffset
= soffset
.to_shwi ();
3087 rhsoffset
= rhsunitoffset
* BITS_PER_UNIT
;
3088 if (rhsunitoffset
!= rhsoffset
/ BITS_PER_UNIT
)
3089 rhsoffset
= UNKNOWN_OFFSET
;
3093 get_constraint_for_rhs (ptr
, results
);
3097 /* As we are eventually appending to the solution do not use
3098 vec::iterate here. */
3099 n
= results
->length ();
3100 for (j
= 0; j
< n
; j
++)
3104 curr
= get_varinfo (c
.var
);
3106 if (c
.type
== ADDRESSOF
3107 /* If this varinfo represents a full variable just use it. */
3108 && curr
->is_full_var
)
3110 else if (c
.type
== ADDRESSOF
3111 /* If we do not know the offset add all subfields. */
3112 && rhsoffset
== UNKNOWN_OFFSET
)
3114 varinfo_t temp
= get_varinfo (curr
->head
);
3117 struct constraint_expr c2
;
3119 c2
.type
= ADDRESSOF
;
3121 if (c2
.var
!= c
.var
)
3122 results
->safe_push (c2
);
3123 temp
= vi_next (temp
);
3127 else if (c
.type
== ADDRESSOF
)
3130 unsigned HOST_WIDE_INT offset
= curr
->offset
+ rhsoffset
;
3132 /* If curr->offset + rhsoffset is less than zero adjust it. */
3134 && curr
->offset
< offset
)
3137 /* We have to include all fields that overlap the current
3138 field shifted by rhsoffset. And we include at least
3139 the last or the first field of the variable to represent
3140 reachability of off-bound addresses, in particular &object + 1,
3141 conservatively correct. */
3142 temp
= first_or_preceding_vi_for_offset (curr
, offset
);
3145 temp
= vi_next (temp
);
3147 && temp
->offset
< offset
+ curr
->size
)
3149 struct constraint_expr c2
;
3151 c2
.type
= ADDRESSOF
;
3153 results
->safe_push (c2
);
3154 temp
= vi_next (temp
);
3157 else if (c
.type
== SCALAR
)
3159 gcc_assert (c
.offset
== 0);
3160 c
.offset
= rhsoffset
;
3163 /* We shouldn't get any DEREFs here. */
3171 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3172 If address_p is true the result will be taken its address of.
3173 If lhs_p is true then the constraint expression is assumed to be used
3177 get_constraint_for_component_ref (tree t
, vec
<ce_s
> *results
,
3178 bool address_p
, bool lhs_p
)
3181 HOST_WIDE_INT bitsize
= -1;
3182 HOST_WIDE_INT bitmaxsize
= -1;
3183 HOST_WIDE_INT bitpos
;
3187 /* Some people like to do cute things like take the address of
3190 while (handled_component_p (forzero
)
3191 || INDIRECT_REF_P (forzero
)
3192 || TREE_CODE (forzero
) == MEM_REF
)
3193 forzero
= TREE_OPERAND (forzero
, 0);
3195 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
3197 struct constraint_expr temp
;
3200 temp
.var
= integer_id
;
3202 results
->safe_push (temp
);
3206 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
, &reverse
);
3208 /* Pretend to take the address of the base, we'll take care of
3209 adding the required subset of sub-fields below. */
3210 get_constraint_for_1 (t
, results
, true, lhs_p
);
3211 gcc_assert (results
->length () == 1);
3212 struct constraint_expr
&result
= results
->last ();
3214 if (result
.type
== SCALAR
3215 && get_varinfo (result
.var
)->is_full_var
)
3216 /* For single-field vars do not bother about the offset. */
3218 else if (result
.type
== SCALAR
)
3220 /* In languages like C, you can access one past the end of an
3221 array. You aren't allowed to dereference it, so we can
3222 ignore this constraint. When we handle pointer subtraction,
3223 we may have to do something cute here. */
3225 if ((unsigned HOST_WIDE_INT
)bitpos
< get_varinfo (result
.var
)->fullsize
3228 /* It's also not true that the constraint will actually start at the
3229 right offset, it may start in some padding. We only care about
3230 setting the constraint to the first actual field it touches, so
3232 struct constraint_expr cexpr
= result
;
3236 for (curr
= get_varinfo (cexpr
.var
); curr
; curr
= vi_next (curr
))
3238 if (ranges_overlap_p (curr
->offset
, curr
->size
,
3239 bitpos
, bitmaxsize
))
3241 cexpr
.var
= curr
->id
;
3242 results
->safe_push (cexpr
);
3247 /* If we are going to take the address of this field then
3248 to be able to compute reachability correctly add at least
3249 the last field of the variable. */
3250 if (address_p
&& results
->length () == 0)
3252 curr
= get_varinfo (cexpr
.var
);
3253 while (curr
->next
!= 0)
3254 curr
= vi_next (curr
);
3255 cexpr
.var
= curr
->id
;
3256 results
->safe_push (cexpr
);
3258 else if (results
->length () == 0)
3259 /* Assert that we found *some* field there. The user couldn't be
3260 accessing *only* padding. */
3261 /* Still the user could access one past the end of an array
3262 embedded in a struct resulting in accessing *only* padding. */
3263 /* Or accessing only padding via type-punning to a type
3264 that has a filed just in padding space. */
3266 cexpr
.type
= SCALAR
;
3267 cexpr
.var
= anything_id
;
3269 results
->safe_push (cexpr
);
3272 else if (bitmaxsize
== 0)
3274 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3275 fprintf (dump_file
, "Access to zero-sized part of variable,"
3279 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3280 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
3282 else if (result
.type
== DEREF
)
3284 /* If we do not know exactly where the access goes say so. Note
3285 that only for non-structure accesses we know that we access
3286 at most one subfiled of any variable. */
3288 || bitsize
!= bitmaxsize
3289 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t
))
3290 || result
.offset
== UNKNOWN_OFFSET
)
3291 result
.offset
= UNKNOWN_OFFSET
;
3293 result
.offset
+= bitpos
;
3295 else if (result
.type
== ADDRESSOF
)
3297 /* We can end up here for component references on a
3298 VIEW_CONVERT_EXPR <>(&foobar). */
3299 result
.type
= SCALAR
;
3300 result
.var
= anything_id
;
3308 /* Dereference the constraint expression CONS, and return the result.
3309 DEREF (ADDRESSOF) = SCALAR
3310 DEREF (SCALAR) = DEREF
3311 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3312 This is needed so that we can handle dereferencing DEREF constraints. */
3315 do_deref (vec
<ce_s
> *constraints
)
3317 struct constraint_expr
*c
;
3320 FOR_EACH_VEC_ELT (*constraints
, i
, c
)
3322 if (c
->type
== SCALAR
)
3324 else if (c
->type
== ADDRESSOF
)
3326 else if (c
->type
== DEREF
)
3328 struct constraint_expr tmplhs
;
3329 tmplhs
= new_scalar_tmp_constraint_exp ("dereftmp", true);
3330 process_constraint (new_constraint (tmplhs
, *c
));
3331 c
->var
= tmplhs
.var
;
3338 /* Given a tree T, return the constraint expression for taking the
3342 get_constraint_for_address_of (tree t
, vec
<ce_s
> *results
)
3344 struct constraint_expr
*c
;
3347 get_constraint_for_1 (t
, results
, true, true);
3349 FOR_EACH_VEC_ELT (*results
, i
, c
)
3351 if (c
->type
== DEREF
)
3354 c
->type
= ADDRESSOF
;
3358 /* Given a tree T, return the constraint expression for it. */
3361 get_constraint_for_1 (tree t
, vec
<ce_s
> *results
, bool address_p
,
3364 struct constraint_expr temp
;
3366 /* x = integer is all glommed to a single variable, which doesn't
3367 point to anything by itself. That is, of course, unless it is an
3368 integer constant being treated as a pointer, in which case, we
3369 will return that this is really the addressof anything. This
3370 happens below, since it will fall into the default case. The only
3371 case we know something about an integer treated like a pointer is
3372 when it is the NULL pointer, and then we just say it points to
3375 Do not do that if -fno-delete-null-pointer-checks though, because
3376 in that case *NULL does not fail, so it _should_ alias *anything.
3377 It is not worth adding a new option or renaming the existing one,
3378 since this case is relatively obscure. */
3379 if ((TREE_CODE (t
) == INTEGER_CST
3380 && integer_zerop (t
))
3381 /* The only valid CONSTRUCTORs in gimple with pointer typed
3382 elements are zero-initializer. But in IPA mode we also
3383 process global initializers, so verify at least. */
3384 || (TREE_CODE (t
) == CONSTRUCTOR
3385 && CONSTRUCTOR_NELTS (t
) == 0))
3387 if (flag_delete_null_pointer_checks
)
3388 temp
.var
= nothing_id
;
3390 temp
.var
= nonlocal_id
;
3391 temp
.type
= ADDRESSOF
;
3393 results
->safe_push (temp
);
3397 /* String constants are read-only, ideally we'd have a CONST_DECL
3399 if (TREE_CODE (t
) == STRING_CST
)
3401 temp
.var
= string_id
;
3404 results
->safe_push (temp
);
3408 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
3410 case tcc_expression
:
3412 switch (TREE_CODE (t
))
3415 get_constraint_for_address_of (TREE_OPERAND (t
, 0), results
);
3423 switch (TREE_CODE (t
))
3427 struct constraint_expr cs
;
3429 get_constraint_for_ptr_offset (TREE_OPERAND (t
, 0),
3430 TREE_OPERAND (t
, 1), results
);
3433 /* If we are not taking the address then make sure to process
3434 all subvariables we might access. */
3438 cs
= results
->last ();
3439 if (cs
.type
== DEREF
3440 && type_can_have_subvars (TREE_TYPE (t
)))
3442 /* For dereferences this means we have to defer it
3444 results
->last ().offset
= UNKNOWN_OFFSET
;
3447 if (cs
.type
!= SCALAR
)
3450 vi
= get_varinfo (cs
.var
);
3451 curr
= vi_next (vi
);
3452 if (!vi
->is_full_var
3455 unsigned HOST_WIDE_INT size
;
3456 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t
))))
3457 size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t
)));
3460 for (; curr
; curr
= vi_next (curr
))
3462 if (curr
->offset
- vi
->offset
< size
)
3465 results
->safe_push (cs
);
3474 case ARRAY_RANGE_REF
:
3479 get_constraint_for_component_ref (t
, results
, address_p
, lhs_p
);
3481 case VIEW_CONVERT_EXPR
:
3482 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, address_p
,
3485 /* We are missing handling for TARGET_MEM_REF here. */
3490 case tcc_exceptional
:
3492 switch (TREE_CODE (t
))
3496 get_constraint_for_ssa_var (t
, results
, address_p
);
3504 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t
), i
, val
)
3506 struct constraint_expr
*rhsp
;
3508 get_constraint_for_1 (val
, &tmp
, address_p
, lhs_p
);
3509 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
3510 results
->safe_push (*rhsp
);
3513 /* We do not know whether the constructor was complete,
3514 so technically we have to add &NOTHING or &ANYTHING
3515 like we do for an empty constructor as well. */
3522 case tcc_declaration
:
3524 get_constraint_for_ssa_var (t
, results
, address_p
);
3529 /* We cannot refer to automatic variables through constants. */
3530 temp
.type
= ADDRESSOF
;
3531 temp
.var
= nonlocal_id
;
3533 results
->safe_push (temp
);
3539 /* The default fallback is a constraint from anything. */
3540 temp
.type
= ADDRESSOF
;
3541 temp
.var
= anything_id
;
3543 results
->safe_push (temp
);
3546 /* Given a gimple tree T, return the constraint expression vector for it. */
3549 get_constraint_for (tree t
, vec
<ce_s
> *results
)
3551 gcc_assert (results
->length () == 0);
3553 get_constraint_for_1 (t
, results
, false, true);
3556 /* Given a gimple tree T, return the constraint expression vector for it
3557 to be used as the rhs of a constraint. */
3560 get_constraint_for_rhs (tree t
, vec
<ce_s
> *results
)
3562 gcc_assert (results
->length () == 0);
3564 get_constraint_for_1 (t
, results
, false, false);
3568 /* Efficiently generates constraints from all entries in *RHSC to all
3569 entries in *LHSC. */
3572 process_all_all_constraints (vec
<ce_s
> lhsc
,
3575 struct constraint_expr
*lhsp
, *rhsp
;
3578 if (lhsc
.length () <= 1 || rhsc
.length () <= 1)
3580 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3581 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
3582 process_constraint (new_constraint (*lhsp
, *rhsp
));
3586 struct constraint_expr tmp
;
3587 tmp
= new_scalar_tmp_constraint_exp ("allalltmp", true);
3588 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
3589 process_constraint (new_constraint (tmp
, *rhsp
));
3590 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3591 process_constraint (new_constraint (*lhsp
, tmp
));
3595 /* Handle aggregate copies by expanding into copies of the respective
3596 fields of the structures. */
3599 do_structure_copy (tree lhsop
, tree rhsop
)
3601 struct constraint_expr
*lhsp
, *rhsp
;
3602 auto_vec
<ce_s
> lhsc
;
3603 auto_vec
<ce_s
> rhsc
;
3606 get_constraint_for (lhsop
, &lhsc
);
3607 get_constraint_for_rhs (rhsop
, &rhsc
);
3610 if (lhsp
->type
== DEREF
3611 || (lhsp
->type
== ADDRESSOF
&& lhsp
->var
== anything_id
)
3612 || rhsp
->type
== DEREF
)
3614 if (lhsp
->type
== DEREF
)
3616 gcc_assert (lhsc
.length () == 1);
3617 lhsp
->offset
= UNKNOWN_OFFSET
;
3619 if (rhsp
->type
== DEREF
)
3621 gcc_assert (rhsc
.length () == 1);
3622 rhsp
->offset
= UNKNOWN_OFFSET
;
3624 process_all_all_constraints (lhsc
, rhsc
);
3626 else if (lhsp
->type
== SCALAR
3627 && (rhsp
->type
== SCALAR
3628 || rhsp
->type
== ADDRESSOF
))
3630 HOST_WIDE_INT lhssize
, lhsmaxsize
, lhsoffset
;
3631 HOST_WIDE_INT rhssize
, rhsmaxsize
, rhsoffset
;
3634 get_ref_base_and_extent (lhsop
, &lhsoffset
, &lhssize
, &lhsmaxsize
,
3636 get_ref_base_and_extent (rhsop
, &rhsoffset
, &rhssize
, &rhsmaxsize
,
3638 for (j
= 0; lhsc
.iterate (j
, &lhsp
);)
3640 varinfo_t lhsv
, rhsv
;
3642 lhsv
= get_varinfo (lhsp
->var
);
3643 rhsv
= get_varinfo (rhsp
->var
);
3644 if (lhsv
->may_have_pointers
3645 && (lhsv
->is_full_var
3646 || rhsv
->is_full_var
3647 || ranges_overlap_p (lhsv
->offset
+ rhsoffset
, lhsv
->size
,
3648 rhsv
->offset
+ lhsoffset
, rhsv
->size
)))
3649 process_constraint (new_constraint (*lhsp
, *rhsp
));
3650 if (!rhsv
->is_full_var
3651 && (lhsv
->is_full_var
3652 || (lhsv
->offset
+ rhsoffset
+ lhsv
->size
3653 > rhsv
->offset
+ lhsoffset
+ rhsv
->size
)))
3656 if (k
>= rhsc
.length ())
3667 /* Create constraints ID = { rhsc }. */
3670 make_constraints_to (unsigned id
, vec
<ce_s
> rhsc
)
3672 struct constraint_expr
*c
;
3673 struct constraint_expr includes
;
3677 includes
.offset
= 0;
3678 includes
.type
= SCALAR
;
3680 FOR_EACH_VEC_ELT (rhsc
, j
, c
)
3681 process_constraint (new_constraint (includes
, *c
));
3684 /* Create a constraint ID = OP. */
3687 make_constraint_to (unsigned id
, tree op
)
3689 auto_vec
<ce_s
> rhsc
;
3690 get_constraint_for_rhs (op
, &rhsc
);
3691 make_constraints_to (id
, rhsc
);
3694 /* Create a constraint ID = &FROM. */
3697 make_constraint_from (varinfo_t vi
, int from
)
3699 struct constraint_expr lhs
, rhs
;
3707 rhs
.type
= ADDRESSOF
;
3708 process_constraint (new_constraint (lhs
, rhs
));
3711 /* Create a constraint ID = FROM. */
3714 make_copy_constraint (varinfo_t vi
, int from
)
3716 struct constraint_expr lhs
, rhs
;
3725 process_constraint (new_constraint (lhs
, rhs
));
3728 /* Make constraints necessary to make OP escape. */
3731 make_escape_constraint (tree op
)
3733 make_constraint_to (escaped_id
, op
);
3736 /* Add constraints to that the solution of VI is transitively closed. */
3739 make_transitive_closure_constraints (varinfo_t vi
)
3741 struct constraint_expr lhs
, rhs
;
3749 rhs
.offset
= UNKNOWN_OFFSET
;
3750 process_constraint (new_constraint (lhs
, rhs
));
3753 /* Temporary storage for fake var decls. */
3754 struct obstack fake_var_decl_obstack
;
3756 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3759 build_fake_var_decl (tree type
)
3761 tree decl
= (tree
) XOBNEW (&fake_var_decl_obstack
, struct tree_var_decl
);
3762 memset (decl
, 0, sizeof (struct tree_var_decl
));
3763 TREE_SET_CODE (decl
, VAR_DECL
);
3764 TREE_TYPE (decl
) = type
;
3765 DECL_UID (decl
) = allocate_decl_uid ();
3766 SET_DECL_PT_UID (decl
, -1);
3767 layout_decl (decl
, 0);
3771 /* Create a new artificial heap variable with NAME.
3772 Return the created variable. */
3775 make_heapvar (const char *name
, bool add_id
)
3780 heapvar
= build_fake_var_decl (ptr_type_node
);
3781 DECL_EXTERNAL (heapvar
) = 1;
3783 vi
= new_var_info (heapvar
, name
, add_id
);
3784 vi
->is_artificial_var
= true;
3785 vi
->is_heap_var
= true;
3786 vi
->is_unknown_size_var
= true;
3790 vi
->is_full_var
= true;
3791 insert_vi_for_tree (heapvar
, vi
);
3796 /* Create a new artificial heap variable with NAME and make a
3797 constraint from it to LHS. Set flags according to a tag used
3798 for tracking restrict pointers. */
3801 make_constraint_from_restrict (varinfo_t lhs
, const char *name
, bool add_id
)
3803 varinfo_t vi
= make_heapvar (name
, add_id
);
3804 vi
->is_restrict_var
= 1;
3805 vi
->is_global_var
= 1;
3806 vi
->may_have_pointers
= 1;
3807 make_constraint_from (lhs
, vi
->id
);
3811 /* Create a new artificial heap variable with NAME and make a
3812 constraint from it to LHS. Set flags according to a tag used
3813 for tracking restrict pointers and make the artificial heap
3814 point to global memory. */
3817 make_constraint_from_global_restrict (varinfo_t lhs
, const char *name
,
3820 varinfo_t vi
= make_constraint_from_restrict (lhs
, name
, add_id
);
3821 make_copy_constraint (vi
, nonlocal_id
);
3825 /* In IPA mode there are varinfos for different aspects of reach
3826 function designator. One for the points-to set of the return
3827 value, one for the variables that are clobbered by the function,
3828 one for its uses and one for each parameter (including a single
3829 glob for remaining variadic arguments). */
3831 enum { fi_clobbers
= 1, fi_uses
= 2,
3832 fi_static_chain
= 3, fi_result
= 4, fi_parm_base
= 5 };
3834 /* Get a constraint for the requested part of a function designator FI
3835 when operating in IPA mode. */
3837 static struct constraint_expr
3838 get_function_part_constraint (varinfo_t fi
, unsigned part
)
3840 struct constraint_expr c
;
3842 gcc_assert (in_ipa_mode
);
3844 if (fi
->id
== anything_id
)
3846 /* ??? We probably should have a ANYFN special variable. */
3847 c
.var
= anything_id
;
3851 else if (TREE_CODE (fi
->decl
) == FUNCTION_DECL
)
3853 varinfo_t ai
= first_vi_for_offset (fi
, part
);
3857 c
.var
= anything_id
;
3871 /* For non-IPA mode, generate constraints necessary for a call on the
3875 handle_rhs_call (gcall
*stmt
, vec
<ce_s
> *results
)
3877 struct constraint_expr rhsc
;
3879 bool returns_uses
= false;
3881 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3883 tree arg
= gimple_call_arg (stmt
, i
);
3884 int flags
= gimple_call_arg_flags (stmt
, i
);
3886 /* If the argument is not used we can ignore it. */
3887 if (flags
& EAF_UNUSED
)
3890 /* As we compute ESCAPED context-insensitive we do not gain
3891 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3892 set. The argument would still get clobbered through the
3894 if ((flags
& EAF_NOCLOBBER
)
3895 && (flags
& EAF_NOESCAPE
))
3897 varinfo_t uses
= get_call_use_vi (stmt
);
3898 if (!(flags
& EAF_DIRECT
))
3900 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg", true);
3901 make_constraint_to (tem
->id
, arg
);
3902 make_transitive_closure_constraints (tem
);
3903 make_copy_constraint (uses
, tem
->id
);
3906 make_constraint_to (uses
->id
, arg
);
3907 returns_uses
= true;
3909 else if (flags
& EAF_NOESCAPE
)
3911 struct constraint_expr lhs
, rhs
;
3912 varinfo_t uses
= get_call_use_vi (stmt
);
3913 varinfo_t clobbers
= get_call_clobber_vi (stmt
);
3914 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg", true);
3915 make_constraint_to (tem
->id
, arg
);
3916 if (!(flags
& EAF_DIRECT
))
3917 make_transitive_closure_constraints (tem
);
3918 make_copy_constraint (uses
, tem
->id
);
3919 make_copy_constraint (clobbers
, tem
->id
);
3920 /* Add *tem = nonlocal, do not add *tem = callused as
3921 EAF_NOESCAPE parameters do not escape to other parameters
3922 and all other uses appear in NONLOCAL as well. */
3927 rhs
.var
= nonlocal_id
;
3929 process_constraint (new_constraint (lhs
, rhs
));
3930 returns_uses
= true;
3933 make_escape_constraint (arg
);
3936 /* If we added to the calls uses solution make sure we account for
3937 pointers to it to be returned. */
3940 rhsc
.var
= get_call_use_vi (stmt
)->id
;
3943 results
->safe_push (rhsc
);
3946 /* The static chain escapes as well. */
3947 if (gimple_call_chain (stmt
))
3948 make_escape_constraint (gimple_call_chain (stmt
));
3950 /* And if we applied NRV the address of the return slot escapes as well. */
3951 if (gimple_call_return_slot_opt_p (stmt
)
3952 && gimple_call_lhs (stmt
) != NULL_TREE
3953 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
3955 auto_vec
<ce_s
> tmpc
;
3956 struct constraint_expr lhsc
, *c
;
3957 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
3958 lhsc
.var
= escaped_id
;
3961 FOR_EACH_VEC_ELT (tmpc
, i
, c
)
3962 process_constraint (new_constraint (lhsc
, *c
));
3965 /* Regular functions return nonlocal memory. */
3966 rhsc
.var
= nonlocal_id
;
3969 results
->safe_push (rhsc
);
3972 /* For non-IPA mode, generate constraints necessary for a call
3973 that returns a pointer and assigns it to LHS. This simply makes
3974 the LHS point to global and escaped variables. */
3977 handle_lhs_call (gcall
*stmt
, tree lhs
, int flags
, vec
<ce_s
> rhsc
,
3980 auto_vec
<ce_s
> lhsc
;
3982 get_constraint_for (lhs
, &lhsc
);
3983 /* If the store is to a global decl make sure to
3984 add proper escape constraints. */
3985 lhs
= get_base_address (lhs
);
3988 && is_global_var (lhs
))
3990 struct constraint_expr tmpc
;
3991 tmpc
.var
= escaped_id
;
3994 lhsc
.safe_push (tmpc
);
3997 /* If the call returns an argument unmodified override the rhs
3999 if (flags
& ERF_RETURNS_ARG
4000 && (flags
& ERF_RETURN_ARG_MASK
) < gimple_call_num_args (stmt
))
4004 arg
= gimple_call_arg (stmt
, flags
& ERF_RETURN_ARG_MASK
);
4005 get_constraint_for (arg
, &rhsc
);
4006 process_all_all_constraints (lhsc
, rhsc
);
4009 else if (flags
& ERF_NOALIAS
)
4012 struct constraint_expr tmpc
;
4014 vi
= make_heapvar ("HEAP", true);
4015 /* We are marking allocated storage local, we deal with it becoming
4016 global by escaping and setting of vars_contains_escaped_heap. */
4017 DECL_EXTERNAL (vi
->decl
) = 0;
4018 vi
->is_global_var
= 0;
4019 /* If this is not a real malloc call assume the memory was
4020 initialized and thus may point to global memory. All
4021 builtin functions with the malloc attribute behave in a sane way. */
4023 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
4024 make_constraint_from (vi
, nonlocal_id
);
4027 tmpc
.type
= ADDRESSOF
;
4028 rhsc
.safe_push (tmpc
);
4029 process_all_all_constraints (lhsc
, rhsc
);
4033 process_all_all_constraints (lhsc
, rhsc
);
4036 /* For non-IPA mode, generate constraints necessary for a call of a
4037 const function that returns a pointer in the statement STMT. */
4040 handle_const_call (gcall
*stmt
, vec
<ce_s
> *results
)
4042 struct constraint_expr rhsc
;
4045 /* Treat nested const functions the same as pure functions as far
4046 as the static chain is concerned. */
4047 if (gimple_call_chain (stmt
))
4049 varinfo_t uses
= get_call_use_vi (stmt
);
4050 make_transitive_closure_constraints (uses
);
4051 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4052 rhsc
.var
= uses
->id
;
4055 results
->safe_push (rhsc
);
4058 /* May return arguments. */
4059 for (k
= 0; k
< gimple_call_num_args (stmt
); ++k
)
4061 tree arg
= gimple_call_arg (stmt
, k
);
4062 auto_vec
<ce_s
> argc
;
4064 struct constraint_expr
*argp
;
4065 get_constraint_for_rhs (arg
, &argc
);
4066 FOR_EACH_VEC_ELT (argc
, i
, argp
)
4067 results
->safe_push (*argp
);
4070 /* May return addresses of globals. */
4071 rhsc
.var
= nonlocal_id
;
4073 rhsc
.type
= ADDRESSOF
;
4074 results
->safe_push (rhsc
);
4077 /* For non-IPA mode, generate constraints necessary for a call to a
4078 pure function in statement STMT. */
4081 handle_pure_call (gcall
*stmt
, vec
<ce_s
> *results
)
4083 struct constraint_expr rhsc
;
4085 varinfo_t uses
= NULL
;
4087 /* Memory reached from pointer arguments is call-used. */
4088 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
4090 tree arg
= gimple_call_arg (stmt
, i
);
4093 uses
= get_call_use_vi (stmt
);
4094 make_transitive_closure_constraints (uses
);
4096 make_constraint_to (uses
->id
, arg
);
4099 /* The static chain is used as well. */
4100 if (gimple_call_chain (stmt
))
4104 uses
= get_call_use_vi (stmt
);
4105 make_transitive_closure_constraints (uses
);
4107 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4110 /* Pure functions may return call-used and nonlocal memory. */
4113 rhsc
.var
= uses
->id
;
4116 results
->safe_push (rhsc
);
4118 rhsc
.var
= nonlocal_id
;
4121 results
->safe_push (rhsc
);
4125 /* Return the varinfo for the callee of CALL. */
4128 get_fi_for_callee (gcall
*call
)
4130 tree decl
, fn
= gimple_call_fn (call
);
4132 if (fn
&& TREE_CODE (fn
) == OBJ_TYPE_REF
)
4133 fn
= OBJ_TYPE_REF_EXPR (fn
);
4135 /* If we can directly resolve the function being called, do so.
4136 Otherwise, it must be some sort of indirect expression that
4137 we should still be able to handle. */
4138 decl
= gimple_call_addr_fndecl (fn
);
4140 return get_vi_for_tree (decl
);
4142 /* If the function is anything other than a SSA name pointer we have no
4143 clue and should be getting ANYFN (well, ANYTHING for now). */
4144 if (!fn
|| TREE_CODE (fn
) != SSA_NAME
)
4145 return get_varinfo (anything_id
);
4147 if (SSA_NAME_IS_DEFAULT_DEF (fn
)
4148 && (TREE_CODE (SSA_NAME_VAR (fn
)) == PARM_DECL
4149 || TREE_CODE (SSA_NAME_VAR (fn
)) == RESULT_DECL
))
4150 fn
= SSA_NAME_VAR (fn
);
4152 return get_vi_for_tree (fn
);
4155 /* Create constraints for assigning call argument ARG to the incoming parameter
4156 INDEX of function FI. */
4159 find_func_aliases_for_call_arg (varinfo_t fi
, unsigned index
, tree arg
)
4161 struct constraint_expr lhs
;
4162 lhs
= get_function_part_constraint (fi
, fi_parm_base
+ index
);
4164 auto_vec
<ce_s
, 2> rhsc
;
4165 get_constraint_for_rhs (arg
, &rhsc
);
4168 struct constraint_expr
*rhsp
;
4169 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4170 process_constraint (new_constraint (lhs
, *rhsp
));
4173 /* Return true if FNDECL may be part of another lto partition. */
4176 fndecl_maybe_in_other_partition (tree fndecl
)
4178 cgraph_node
*fn_node
= cgraph_node::get (fndecl
);
4179 if (fn_node
== NULL
)
4182 return fn_node
->in_other_partition
;
4185 /* Create constraints for the builtin call T. Return true if the call
4186 was handled, otherwise false. */
4189 find_func_aliases_for_builtin_call (struct function
*fn
, gcall
*t
)
4191 tree fndecl
= gimple_call_fndecl (t
);
4192 auto_vec
<ce_s
, 2> lhsc
;
4193 auto_vec
<ce_s
, 4> rhsc
;
4196 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
4197 /* ??? All builtins that are handled here need to be handled
4198 in the alias-oracle query functions explicitly! */
4199 switch (DECL_FUNCTION_CODE (fndecl
))
4201 /* All the following functions return a pointer to the same object
4202 as their first argument points to. The functions do not add
4203 to the ESCAPED solution. The functions make the first argument
4204 pointed to memory point to what the second argument pointed to
4205 memory points to. */
4206 case BUILT_IN_STRCPY
:
4207 case BUILT_IN_STRNCPY
:
4208 case BUILT_IN_BCOPY
:
4209 case BUILT_IN_MEMCPY
:
4210 case BUILT_IN_MEMMOVE
:
4211 case BUILT_IN_MEMPCPY
:
4212 case BUILT_IN_STPCPY
:
4213 case BUILT_IN_STPNCPY
:
4214 case BUILT_IN_STRCAT
:
4215 case BUILT_IN_STRNCAT
:
4216 case BUILT_IN_STRCPY_CHK
:
4217 case BUILT_IN_STRNCPY_CHK
:
4218 case BUILT_IN_MEMCPY_CHK
:
4219 case BUILT_IN_MEMMOVE_CHK
:
4220 case BUILT_IN_MEMPCPY_CHK
:
4221 case BUILT_IN_STPCPY_CHK
:
4222 case BUILT_IN_STPNCPY_CHK
:
4223 case BUILT_IN_STRCAT_CHK
:
4224 case BUILT_IN_STRNCAT_CHK
:
4225 case BUILT_IN_TM_MEMCPY
:
4226 case BUILT_IN_TM_MEMMOVE
:
4228 tree res
= gimple_call_lhs (t
);
4229 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4230 == BUILT_IN_BCOPY
? 1 : 0));
4231 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4232 == BUILT_IN_BCOPY
? 0 : 1));
4233 if (res
!= NULL_TREE
)
4235 get_constraint_for (res
, &lhsc
);
4236 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY
4237 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY
4238 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY
4239 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY_CHK
4240 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY_CHK
4241 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY_CHK
)
4242 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &rhsc
);
4244 get_constraint_for (dest
, &rhsc
);
4245 process_all_all_constraints (lhsc
, rhsc
);
4249 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4250 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4253 process_all_all_constraints (lhsc
, rhsc
);
4256 case BUILT_IN_MEMSET
:
4257 case BUILT_IN_MEMSET_CHK
:
4258 case BUILT_IN_TM_MEMSET
:
4260 tree res
= gimple_call_lhs (t
);
4261 tree dest
= gimple_call_arg (t
, 0);
4264 struct constraint_expr ac
;
4265 if (res
!= NULL_TREE
)
4267 get_constraint_for (res
, &lhsc
);
4268 get_constraint_for (dest
, &rhsc
);
4269 process_all_all_constraints (lhsc
, rhsc
);
4272 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4274 if (flag_delete_null_pointer_checks
4275 && integer_zerop (gimple_call_arg (t
, 1)))
4277 ac
.type
= ADDRESSOF
;
4278 ac
.var
= nothing_id
;
4283 ac
.var
= integer_id
;
4286 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4287 process_constraint (new_constraint (*lhsp
, ac
));
4290 case BUILT_IN_POSIX_MEMALIGN
:
4292 tree ptrptr
= gimple_call_arg (t
, 0);
4293 get_constraint_for (ptrptr
, &lhsc
);
4295 varinfo_t vi
= make_heapvar ("HEAP", true);
4296 /* We are marking allocated storage local, we deal with it becoming
4297 global by escaping and setting of vars_contains_escaped_heap. */
4298 DECL_EXTERNAL (vi
->decl
) = 0;
4299 vi
->is_global_var
= 0;
4300 struct constraint_expr tmpc
;
4303 tmpc
.type
= ADDRESSOF
;
4304 rhsc
.safe_push (tmpc
);
4305 process_all_all_constraints (lhsc
, rhsc
);
4308 case BUILT_IN_ASSUME_ALIGNED
:
4310 tree res
= gimple_call_lhs (t
);
4311 tree dest
= gimple_call_arg (t
, 0);
4312 if (res
!= NULL_TREE
)
4314 get_constraint_for (res
, &lhsc
);
4315 get_constraint_for (dest
, &rhsc
);
4316 process_all_all_constraints (lhsc
, rhsc
);
4320 /* All the following functions do not return pointers, do not
4321 modify the points-to sets of memory reachable from their
4322 arguments and do not add to the ESCAPED solution. */
4323 case BUILT_IN_SINCOS
:
4324 case BUILT_IN_SINCOSF
:
4325 case BUILT_IN_SINCOSL
:
4326 case BUILT_IN_FREXP
:
4327 case BUILT_IN_FREXPF
:
4328 case BUILT_IN_FREXPL
:
4329 case BUILT_IN_GAMMA_R
:
4330 case BUILT_IN_GAMMAF_R
:
4331 case BUILT_IN_GAMMAL_R
:
4332 case BUILT_IN_LGAMMA_R
:
4333 case BUILT_IN_LGAMMAF_R
:
4334 case BUILT_IN_LGAMMAL_R
:
4336 case BUILT_IN_MODFF
:
4337 case BUILT_IN_MODFL
:
4338 case BUILT_IN_REMQUO
:
4339 case BUILT_IN_REMQUOF
:
4340 case BUILT_IN_REMQUOL
:
4343 case BUILT_IN_STRDUP
:
4344 case BUILT_IN_STRNDUP
:
4345 case BUILT_IN_REALLOC
:
4346 if (gimple_call_lhs (t
))
4348 handle_lhs_call (t
, gimple_call_lhs (t
),
4349 gimple_call_return_flags (t
) | ERF_NOALIAS
,
4351 get_constraint_for_ptr_offset (gimple_call_lhs (t
),
4353 get_constraint_for_ptr_offset (gimple_call_arg (t
, 0),
4357 process_all_all_constraints (lhsc
, rhsc
);
4360 /* For realloc the resulting pointer can be equal to the
4361 argument as well. But only doing this wouldn't be
4362 correct because with ptr == 0 realloc behaves like malloc. */
4363 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_REALLOC
)
4365 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4366 get_constraint_for (gimple_call_arg (t
, 0), &rhsc
);
4367 process_all_all_constraints (lhsc
, rhsc
);
4372 /* String / character search functions return a pointer into the
4373 source string or NULL. */
4374 case BUILT_IN_INDEX
:
4375 case BUILT_IN_STRCHR
:
4376 case BUILT_IN_STRRCHR
:
4377 case BUILT_IN_MEMCHR
:
4378 case BUILT_IN_STRSTR
:
4379 case BUILT_IN_STRPBRK
:
4380 if (gimple_call_lhs (t
))
4382 tree src
= gimple_call_arg (t
, 0);
4383 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4384 constraint_expr nul
;
4385 nul
.var
= nothing_id
;
4387 nul
.type
= ADDRESSOF
;
4388 rhsc
.safe_push (nul
);
4389 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4390 process_all_all_constraints (lhsc
, rhsc
);
4393 /* Trampolines are special - they set up passing the static
4395 case BUILT_IN_INIT_TRAMPOLINE
:
4397 tree tramp
= gimple_call_arg (t
, 0);
4398 tree nfunc
= gimple_call_arg (t
, 1);
4399 tree frame
= gimple_call_arg (t
, 2);
4401 struct constraint_expr lhs
, *rhsp
;
4404 varinfo_t nfi
= NULL
;
4405 gcc_assert (TREE_CODE (nfunc
) == ADDR_EXPR
);
4406 nfi
= lookup_vi_for_tree (TREE_OPERAND (nfunc
, 0));
4409 lhs
= get_function_part_constraint (nfi
, fi_static_chain
);
4410 get_constraint_for (frame
, &rhsc
);
4411 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4412 process_constraint (new_constraint (lhs
, *rhsp
));
4415 /* Make the frame point to the function for
4416 the trampoline adjustment call. */
4417 get_constraint_for (tramp
, &lhsc
);
4419 get_constraint_for (nfunc
, &rhsc
);
4420 process_all_all_constraints (lhsc
, rhsc
);
4425 /* Else fallthru to generic handling which will let
4426 the frame escape. */
4429 case BUILT_IN_ADJUST_TRAMPOLINE
:
4431 tree tramp
= gimple_call_arg (t
, 0);
4432 tree res
= gimple_call_lhs (t
);
4433 if (in_ipa_mode
&& res
)
4435 get_constraint_for (res
, &lhsc
);
4436 get_constraint_for (tramp
, &rhsc
);
4438 process_all_all_constraints (lhsc
, rhsc
);
4442 CASE_BUILT_IN_TM_STORE (1):
4443 CASE_BUILT_IN_TM_STORE (2):
4444 CASE_BUILT_IN_TM_STORE (4):
4445 CASE_BUILT_IN_TM_STORE (8):
4446 CASE_BUILT_IN_TM_STORE (FLOAT
):
4447 CASE_BUILT_IN_TM_STORE (DOUBLE
):
4448 CASE_BUILT_IN_TM_STORE (LDOUBLE
):
4449 CASE_BUILT_IN_TM_STORE (M64
):
4450 CASE_BUILT_IN_TM_STORE (M128
):
4451 CASE_BUILT_IN_TM_STORE (M256
):
4453 tree addr
= gimple_call_arg (t
, 0);
4454 tree src
= gimple_call_arg (t
, 1);
4456 get_constraint_for (addr
, &lhsc
);
4458 get_constraint_for (src
, &rhsc
);
4459 process_all_all_constraints (lhsc
, rhsc
);
4462 CASE_BUILT_IN_TM_LOAD (1):
4463 CASE_BUILT_IN_TM_LOAD (2):
4464 CASE_BUILT_IN_TM_LOAD (4):
4465 CASE_BUILT_IN_TM_LOAD (8):
4466 CASE_BUILT_IN_TM_LOAD (FLOAT
):
4467 CASE_BUILT_IN_TM_LOAD (DOUBLE
):
4468 CASE_BUILT_IN_TM_LOAD (LDOUBLE
):
4469 CASE_BUILT_IN_TM_LOAD (M64
):
4470 CASE_BUILT_IN_TM_LOAD (M128
):
4471 CASE_BUILT_IN_TM_LOAD (M256
):
4473 tree dest
= gimple_call_lhs (t
);
4474 tree addr
= gimple_call_arg (t
, 0);
4476 get_constraint_for (dest
, &lhsc
);
4477 get_constraint_for (addr
, &rhsc
);
4479 process_all_all_constraints (lhsc
, rhsc
);
4482 /* Variadic argument handling needs to be handled in IPA
4484 case BUILT_IN_VA_START
:
4486 tree valist
= gimple_call_arg (t
, 0);
4487 struct constraint_expr rhs
, *lhsp
;
4489 get_constraint_for (valist
, &lhsc
);
4491 /* The va_list gets access to pointers in variadic
4492 arguments. Which we know in the case of IPA analysis
4493 and otherwise are just all nonlocal variables. */
4496 fi
= lookup_vi_for_tree (fn
->decl
);
4497 rhs
= get_function_part_constraint (fi
, ~0);
4498 rhs
.type
= ADDRESSOF
;
4502 rhs
.var
= nonlocal_id
;
4503 rhs
.type
= ADDRESSOF
;
4506 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4507 process_constraint (new_constraint (*lhsp
, rhs
));
4508 /* va_list is clobbered. */
4509 make_constraint_to (get_call_clobber_vi (t
)->id
, valist
);
4512 /* va_end doesn't have any effect that matters. */
4513 case BUILT_IN_VA_END
:
4515 /* Alternate return. Simply give up for now. */
4516 case BUILT_IN_RETURN
:
4520 || !(fi
= get_vi_for_tree (fn
->decl
)))
4521 make_constraint_from (get_varinfo (escaped_id
), anything_id
);
4522 else if (in_ipa_mode
4525 struct constraint_expr lhs
, rhs
;
4526 lhs
= get_function_part_constraint (fi
, fi_result
);
4527 rhs
.var
= anything_id
;
4530 process_constraint (new_constraint (lhs
, rhs
));
4534 case BUILT_IN_GOMP_PARALLEL
:
4535 case BUILT_IN_GOACC_PARALLEL
:
4539 unsigned int fnpos
, argpos
;
4540 switch (DECL_FUNCTION_CODE (fndecl
))
4542 case BUILT_IN_GOMP_PARALLEL
:
4543 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
4547 case BUILT_IN_GOACC_PARALLEL
:
4548 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
4549 sizes, kinds, ...). */
4557 tree fnarg
= gimple_call_arg (t
, fnpos
);
4558 gcc_assert (TREE_CODE (fnarg
) == ADDR_EXPR
);
4559 tree fndecl
= TREE_OPERAND (fnarg
, 0);
4560 if (fndecl_maybe_in_other_partition (fndecl
))
4561 /* Fallthru to general call handling. */
4564 tree arg
= gimple_call_arg (t
, argpos
);
4566 varinfo_t fi
= get_vi_for_tree (fndecl
);
4567 find_func_aliases_for_call_arg (fi
, 0, arg
);
4570 /* Else fallthru to generic call handling. */
4573 /* printf-style functions may have hooks to set pointers to
4574 point to somewhere into the generated string. Leave them
4575 for a later exercise... */
4577 /* Fallthru to general call handling. */;
4583 /* Create constraints for the call T. */
4586 find_func_aliases_for_call (struct function
*fn
, gcall
*t
)
4588 tree fndecl
= gimple_call_fndecl (t
);
4591 if (fndecl
!= NULL_TREE
4592 && DECL_BUILT_IN (fndecl
)
4593 && find_func_aliases_for_builtin_call (fn
, t
))
4596 fi
= get_fi_for_callee (t
);
4598 || (fndecl
&& !fi
->is_fn_info
))
4600 auto_vec
<ce_s
, 16> rhsc
;
4601 int flags
= gimple_call_flags (t
);
4603 /* Const functions can return their arguments and addresses
4604 of global memory but not of escaped memory. */
4605 if (flags
& (ECF_CONST
|ECF_NOVOPS
))
4607 if (gimple_call_lhs (t
))
4608 handle_const_call (t
, &rhsc
);
4610 /* Pure functions can return addresses in and of memory
4611 reachable from their arguments, but they are not an escape
4612 point for reachable memory of their arguments. */
4613 else if (flags
& (ECF_PURE
|ECF_LOOPING_CONST_OR_PURE
))
4614 handle_pure_call (t
, &rhsc
);
4616 handle_rhs_call (t
, &rhsc
);
4617 if (gimple_call_lhs (t
))
4618 handle_lhs_call (t
, gimple_call_lhs (t
),
4619 gimple_call_return_flags (t
), rhsc
, fndecl
);
4623 auto_vec
<ce_s
, 2> rhsc
;
4627 /* Assign all the passed arguments to the appropriate incoming
4628 parameters of the function. */
4629 for (j
= 0; j
< gimple_call_num_args (t
); j
++)
4631 tree arg
= gimple_call_arg (t
, j
);
4632 find_func_aliases_for_call_arg (fi
, j
, arg
);
4635 /* If we are returning a value, assign it to the result. */
4636 lhsop
= gimple_call_lhs (t
);
4639 auto_vec
<ce_s
, 2> lhsc
;
4640 struct constraint_expr rhs
;
4641 struct constraint_expr
*lhsp
;
4643 get_constraint_for (lhsop
, &lhsc
);
4644 rhs
= get_function_part_constraint (fi
, fi_result
);
4646 && DECL_RESULT (fndecl
)
4647 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4649 auto_vec
<ce_s
, 2> tem
;
4650 tem
.quick_push (rhs
);
4652 gcc_checking_assert (tem
.length () == 1);
4655 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4656 process_constraint (new_constraint (*lhsp
, rhs
));
4659 /* If we pass the result decl by reference, honor that. */
4662 && DECL_RESULT (fndecl
)
4663 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4665 struct constraint_expr lhs
;
4666 struct constraint_expr
*rhsp
;
4668 get_constraint_for_address_of (lhsop
, &rhsc
);
4669 lhs
= get_function_part_constraint (fi
, fi_result
);
4670 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4671 process_constraint (new_constraint (lhs
, *rhsp
));
4675 /* If we use a static chain, pass it along. */
4676 if (gimple_call_chain (t
))
4678 struct constraint_expr lhs
;
4679 struct constraint_expr
*rhsp
;
4681 get_constraint_for (gimple_call_chain (t
), &rhsc
);
4682 lhs
= get_function_part_constraint (fi
, fi_static_chain
);
4683 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4684 process_constraint (new_constraint (lhs
, *rhsp
));
4689 /* Walk statement T setting up aliasing constraints according to the
4690 references found in T. This function is the main part of the
4691 constraint builder. AI points to auxiliary alias information used
4692 when building alias sets and computing alias grouping heuristics. */
4695 find_func_aliases (struct function
*fn
, gimple
*origt
)
4698 auto_vec
<ce_s
, 16> lhsc
;
4699 auto_vec
<ce_s
, 16> rhsc
;
4700 struct constraint_expr
*c
;
4703 /* Now build constraints expressions. */
4704 if (gimple_code (t
) == GIMPLE_PHI
)
4709 /* For a phi node, assign all the arguments to
4711 get_constraint_for (gimple_phi_result (t
), &lhsc
);
4712 for (i
= 0; i
< gimple_phi_num_args (t
); i
++)
4714 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
4716 STRIP_NOPS (strippedrhs
);
4717 get_constraint_for_rhs (gimple_phi_arg_def (t
, i
), &rhsc
);
4719 FOR_EACH_VEC_ELT (lhsc
, j
, c
)
4721 struct constraint_expr
*c2
;
4722 while (rhsc
.length () > 0)
4725 process_constraint (new_constraint (*c
, *c2
));
4731 /* In IPA mode, we need to generate constraints to pass call
4732 arguments through their calls. There are two cases,
4733 either a GIMPLE_CALL returning a value, or just a plain
4734 GIMPLE_CALL when we are not.
4736 In non-ipa mode, we need to generate constraints for each
4737 pointer passed by address. */
4738 else if (is_gimple_call (t
))
4739 find_func_aliases_for_call (fn
, as_a
<gcall
*> (t
));
4741 /* Otherwise, just a regular assignment statement. Only care about
4742 operations with pointer result, others are dealt with as escape
4743 points if they have pointer operands. */
4744 else if (is_gimple_assign (t
))
4746 /* Otherwise, just a regular assignment statement. */
4747 tree lhsop
= gimple_assign_lhs (t
);
4748 tree rhsop
= (gimple_num_ops (t
) == 2) ? gimple_assign_rhs1 (t
) : NULL
;
4750 if (rhsop
&& TREE_CLOBBER_P (rhsop
))
4751 /* Ignore clobbers, they don't actually store anything into
4754 else if (rhsop
&& AGGREGATE_TYPE_P (TREE_TYPE (lhsop
)))
4755 do_structure_copy (lhsop
, rhsop
);
4758 enum tree_code code
= gimple_assign_rhs_code (t
);
4760 get_constraint_for (lhsop
, &lhsc
);
4762 if (code
== POINTER_PLUS_EXPR
)
4763 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4764 gimple_assign_rhs2 (t
), &rhsc
);
4765 else if (code
== BIT_AND_EXPR
4766 && TREE_CODE (gimple_assign_rhs2 (t
)) == INTEGER_CST
)
4768 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4769 the pointer. Handle it by offsetting it by UNKNOWN. */
4770 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4773 else if ((CONVERT_EXPR_CODE_P (code
)
4774 && !(POINTER_TYPE_P (gimple_expr_type (t
))
4775 && !POINTER_TYPE_P (TREE_TYPE (rhsop
))))
4776 || gimple_assign_single_p (t
))
4777 get_constraint_for_rhs (rhsop
, &rhsc
);
4778 else if (code
== COND_EXPR
)
4780 /* The result is a merge of both COND_EXPR arms. */
4781 auto_vec
<ce_s
, 2> tmp
;
4782 struct constraint_expr
*rhsp
;
4784 get_constraint_for_rhs (gimple_assign_rhs2 (t
), &rhsc
);
4785 get_constraint_for_rhs (gimple_assign_rhs3 (t
), &tmp
);
4786 FOR_EACH_VEC_ELT (tmp
, i
, rhsp
)
4787 rhsc
.safe_push (*rhsp
);
4789 else if (truth_value_p (code
))
4790 /* Truth value results are not pointer (parts). Or at least
4791 very unreasonable obfuscation of a part. */
4795 /* All other operations are merges. */
4796 auto_vec
<ce_s
, 4> tmp
;
4797 struct constraint_expr
*rhsp
;
4799 get_constraint_for_rhs (gimple_assign_rhs1 (t
), &rhsc
);
4800 for (i
= 2; i
< gimple_num_ops (t
); ++i
)
4802 get_constraint_for_rhs (gimple_op (t
, i
), &tmp
);
4803 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
4804 rhsc
.safe_push (*rhsp
);
4808 process_all_all_constraints (lhsc
, rhsc
);
4810 /* If there is a store to a global variable the rhs escapes. */
4811 if ((lhsop
= get_base_address (lhsop
)) != NULL_TREE
4814 varinfo_t vi
= get_vi_for_tree (lhsop
);
4815 if ((! in_ipa_mode
&& vi
->is_global_var
)
4816 || vi
->is_ipa_escape_point
)
4817 make_escape_constraint (rhsop
);
4820 /* Handle escapes through return. */
4821 else if (gimple_code (t
) == GIMPLE_RETURN
4822 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
)
4824 greturn
*return_stmt
= as_a
<greturn
*> (t
);
4827 || !(fi
= get_vi_for_tree (fn
->decl
)))
4828 make_escape_constraint (gimple_return_retval (return_stmt
));
4829 else if (in_ipa_mode
)
4831 struct constraint_expr lhs
;
4832 struct constraint_expr
*rhsp
;
4835 lhs
= get_function_part_constraint (fi
, fi_result
);
4836 get_constraint_for_rhs (gimple_return_retval (return_stmt
), &rhsc
);
4837 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4838 process_constraint (new_constraint (lhs
, *rhsp
));
4841 /* Handle asms conservatively by adding escape constraints to everything. */
4842 else if (gasm
*asm_stmt
= dyn_cast
<gasm
*> (t
))
4844 unsigned i
, noutputs
;
4845 const char **oconstraints
;
4846 const char *constraint
;
4847 bool allows_mem
, allows_reg
, is_inout
;
4849 noutputs
= gimple_asm_noutputs (asm_stmt
);
4850 oconstraints
= XALLOCAVEC (const char *, noutputs
);
4852 for (i
= 0; i
< noutputs
; ++i
)
4854 tree link
= gimple_asm_output_op (asm_stmt
, i
);
4855 tree op
= TREE_VALUE (link
);
4857 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4858 oconstraints
[i
] = constraint
;
4859 parse_output_constraint (&constraint
, i
, 0, 0, &allows_mem
,
4860 &allows_reg
, &is_inout
);
4862 /* A memory constraint makes the address of the operand escape. */
4863 if (!allows_reg
&& allows_mem
)
4864 make_escape_constraint (build_fold_addr_expr (op
));
4866 /* The asm may read global memory, so outputs may point to
4867 any global memory. */
4870 auto_vec
<ce_s
, 2> lhsc
;
4871 struct constraint_expr rhsc
, *lhsp
;
4873 get_constraint_for (op
, &lhsc
);
4874 rhsc
.var
= nonlocal_id
;
4877 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4878 process_constraint (new_constraint (*lhsp
, rhsc
));
4881 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); ++i
)
4883 tree link
= gimple_asm_input_op (asm_stmt
, i
);
4884 tree op
= TREE_VALUE (link
);
4886 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4888 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0, oconstraints
,
4889 &allows_mem
, &allows_reg
);
4891 /* A memory constraint makes the address of the operand escape. */
4892 if (!allows_reg
&& allows_mem
)
4893 make_escape_constraint (build_fold_addr_expr (op
));
4894 /* Strictly we'd only need the constraint to ESCAPED if
4895 the asm clobbers memory, otherwise using something
4896 along the lines of per-call clobbers/uses would be enough. */
4898 make_escape_constraint (op
);
4904 /* Create a constraint adding to the clobber set of FI the memory
4905 pointed to by PTR. */
4908 process_ipa_clobber (varinfo_t fi
, tree ptr
)
4910 vec
<ce_s
> ptrc
= vNULL
;
4911 struct constraint_expr
*c
, lhs
;
4913 get_constraint_for_rhs (ptr
, &ptrc
);
4914 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4915 FOR_EACH_VEC_ELT (ptrc
, i
, c
)
4916 process_constraint (new_constraint (lhs
, *c
));
4920 /* Walk statement T setting up clobber and use constraints according to the
4921 references found in T. This function is a main part of the
4922 IPA constraint builder. */
4925 find_func_clobbers (struct function
*fn
, gimple
*origt
)
4928 auto_vec
<ce_s
, 16> lhsc
;
4929 auto_vec
<ce_s
, 16> rhsc
;
4932 /* Add constraints for clobbered/used in IPA mode.
4933 We are not interested in what automatic variables are clobbered
4934 or used as we only use the information in the caller to which
4935 they do not escape. */
4936 gcc_assert (in_ipa_mode
);
4938 /* If the stmt refers to memory in any way it better had a VUSE. */
4939 if (gimple_vuse (t
) == NULL_TREE
)
4942 /* We'd better have function information for the current function. */
4943 fi
= lookup_vi_for_tree (fn
->decl
);
4944 gcc_assert (fi
!= NULL
);
4946 /* Account for stores in assignments and calls. */
4947 if (gimple_vdef (t
) != NULL_TREE
4948 && gimple_has_lhs (t
))
4950 tree lhs
= gimple_get_lhs (t
);
4952 while (handled_component_p (tem
))
4953 tem
= TREE_OPERAND (tem
, 0);
4955 && !auto_var_in_fn_p (tem
, fn
->decl
))
4956 || INDIRECT_REF_P (tem
)
4957 || (TREE_CODE (tem
) == MEM_REF
4958 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
4960 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
4962 struct constraint_expr lhsc
, *rhsp
;
4964 lhsc
= get_function_part_constraint (fi
, fi_clobbers
);
4965 get_constraint_for_address_of (lhs
, &rhsc
);
4966 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4967 process_constraint (new_constraint (lhsc
, *rhsp
));
4972 /* Account for uses in assigments and returns. */
4973 if (gimple_assign_single_p (t
)
4974 || (gimple_code (t
) == GIMPLE_RETURN
4975 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
))
4977 tree rhs
= (gimple_assign_single_p (t
)
4978 ? gimple_assign_rhs1 (t
)
4979 : gimple_return_retval (as_a
<greturn
*> (t
)));
4981 while (handled_component_p (tem
))
4982 tem
= TREE_OPERAND (tem
, 0);
4984 && !auto_var_in_fn_p (tem
, fn
->decl
))
4985 || INDIRECT_REF_P (tem
)
4986 || (TREE_CODE (tem
) == MEM_REF
4987 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
4989 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
4991 struct constraint_expr lhs
, *rhsp
;
4993 lhs
= get_function_part_constraint (fi
, fi_uses
);
4994 get_constraint_for_address_of (rhs
, &rhsc
);
4995 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4996 process_constraint (new_constraint (lhs
, *rhsp
));
5001 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (t
))
5003 varinfo_t cfi
= NULL
;
5004 tree decl
= gimple_call_fndecl (t
);
5005 struct constraint_expr lhs
, rhs
;
5008 /* For builtins we do not have separate function info. For those
5009 we do not generate escapes for we have to generate clobbers/uses. */
5010 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
5011 switch (DECL_FUNCTION_CODE (decl
))
5013 /* The following functions use and clobber memory pointed to
5014 by their arguments. */
5015 case BUILT_IN_STRCPY
:
5016 case BUILT_IN_STRNCPY
:
5017 case BUILT_IN_BCOPY
:
5018 case BUILT_IN_MEMCPY
:
5019 case BUILT_IN_MEMMOVE
:
5020 case BUILT_IN_MEMPCPY
:
5021 case BUILT_IN_STPCPY
:
5022 case BUILT_IN_STPNCPY
:
5023 case BUILT_IN_STRCAT
:
5024 case BUILT_IN_STRNCAT
:
5025 case BUILT_IN_STRCPY_CHK
:
5026 case BUILT_IN_STRNCPY_CHK
:
5027 case BUILT_IN_MEMCPY_CHK
:
5028 case BUILT_IN_MEMMOVE_CHK
:
5029 case BUILT_IN_MEMPCPY_CHK
:
5030 case BUILT_IN_STPCPY_CHK
:
5031 case BUILT_IN_STPNCPY_CHK
:
5032 case BUILT_IN_STRCAT_CHK
:
5033 case BUILT_IN_STRNCAT_CHK
:
5035 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
5036 == BUILT_IN_BCOPY
? 1 : 0));
5037 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
5038 == BUILT_IN_BCOPY
? 0 : 1));
5040 struct constraint_expr
*rhsp
, *lhsp
;
5041 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5042 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5043 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5044 process_constraint (new_constraint (lhs
, *lhsp
));
5045 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
5046 lhs
= get_function_part_constraint (fi
, fi_uses
);
5047 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5048 process_constraint (new_constraint (lhs
, *rhsp
));
5051 /* The following function clobbers memory pointed to by
5053 case BUILT_IN_MEMSET
:
5054 case BUILT_IN_MEMSET_CHK
:
5055 case BUILT_IN_POSIX_MEMALIGN
:
5057 tree dest
= gimple_call_arg (t
, 0);
5060 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5061 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5062 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5063 process_constraint (new_constraint (lhs
, *lhsp
));
5066 /* The following functions clobber their second and third
5068 case BUILT_IN_SINCOS
:
5069 case BUILT_IN_SINCOSF
:
5070 case BUILT_IN_SINCOSL
:
5072 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5073 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5076 /* The following functions clobber their second argument. */
5077 case BUILT_IN_FREXP
:
5078 case BUILT_IN_FREXPF
:
5079 case BUILT_IN_FREXPL
:
5080 case BUILT_IN_LGAMMA_R
:
5081 case BUILT_IN_LGAMMAF_R
:
5082 case BUILT_IN_LGAMMAL_R
:
5083 case BUILT_IN_GAMMA_R
:
5084 case BUILT_IN_GAMMAF_R
:
5085 case BUILT_IN_GAMMAL_R
:
5087 case BUILT_IN_MODFF
:
5088 case BUILT_IN_MODFL
:
5090 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5093 /* The following functions clobber their third argument. */
5094 case BUILT_IN_REMQUO
:
5095 case BUILT_IN_REMQUOF
:
5096 case BUILT_IN_REMQUOL
:
5098 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5101 /* The following functions neither read nor clobber memory. */
5102 case BUILT_IN_ASSUME_ALIGNED
:
5105 /* Trampolines are of no interest to us. */
5106 case BUILT_IN_INIT_TRAMPOLINE
:
5107 case BUILT_IN_ADJUST_TRAMPOLINE
:
5109 case BUILT_IN_VA_START
:
5110 case BUILT_IN_VA_END
:
5112 case BUILT_IN_GOMP_PARALLEL
:
5113 case BUILT_IN_GOACC_PARALLEL
:
5115 unsigned int fnpos
, argpos
;
5116 unsigned int implicit_use_args
[2];
5117 unsigned int num_implicit_use_args
= 0;
5118 switch (DECL_FUNCTION_CODE (decl
))
5120 case BUILT_IN_GOMP_PARALLEL
:
5121 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
5125 case BUILT_IN_GOACC_PARALLEL
:
5126 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
5127 sizes, kinds, ...). */
5130 implicit_use_args
[num_implicit_use_args
++] = 4;
5131 implicit_use_args
[num_implicit_use_args
++] = 5;
5137 tree fnarg
= gimple_call_arg (t
, fnpos
);
5138 gcc_assert (TREE_CODE (fnarg
) == ADDR_EXPR
);
5139 tree fndecl
= TREE_OPERAND (fnarg
, 0);
5140 if (fndecl_maybe_in_other_partition (fndecl
))
5141 /* Fallthru to general call handling. */
5144 varinfo_t cfi
= get_vi_for_tree (fndecl
);
5146 tree arg
= gimple_call_arg (t
, argpos
);
5148 /* Parameter passed by value is used. */
5149 lhs
= get_function_part_constraint (fi
, fi_uses
);
5150 struct constraint_expr
*rhsp
;
5151 get_constraint_for (arg
, &rhsc
);
5152 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5153 process_constraint (new_constraint (lhs
, *rhsp
));
5156 /* Handle parameters used by the call, but not used in cfi, as
5157 implicitly used by cfi. */
5158 lhs
= get_function_part_constraint (cfi
, fi_uses
);
5159 for (unsigned i
= 0; i
< num_implicit_use_args
; ++i
)
5161 tree arg
= gimple_call_arg (t
, implicit_use_args
[i
]);
5162 get_constraint_for (arg
, &rhsc
);
5163 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5164 process_constraint (new_constraint (lhs
, *rhsp
));
5168 /* The caller clobbers what the callee does. */
5169 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5170 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5171 process_constraint (new_constraint (lhs
, rhs
));
5173 /* The caller uses what the callee does. */
5174 lhs
= get_function_part_constraint (fi
, fi_uses
);
5175 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5176 process_constraint (new_constraint (lhs
, rhs
));
5180 /* printf-style functions may have hooks to set pointers to
5181 point to somewhere into the generated string. Leave them
5182 for a later exercise... */
5184 /* Fallthru to general call handling. */;
5187 /* Parameters passed by value are used. */
5188 lhs
= get_function_part_constraint (fi
, fi_uses
);
5189 for (i
= 0; i
< gimple_call_num_args (t
); i
++)
5191 struct constraint_expr
*rhsp
;
5192 tree arg
= gimple_call_arg (t
, i
);
5194 if (TREE_CODE (arg
) == SSA_NAME
5195 || is_gimple_min_invariant (arg
))
5198 get_constraint_for_address_of (arg
, &rhsc
);
5199 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5200 process_constraint (new_constraint (lhs
, *rhsp
));
5204 /* Build constraints for propagating clobbers/uses along the
5206 cfi
= get_fi_for_callee (call_stmt
);
5207 if (cfi
->id
== anything_id
)
5209 if (gimple_vdef (t
))
5210 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5212 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5217 /* For callees without function info (that's external functions),
5218 ESCAPED is clobbered and used. */
5219 if (gimple_call_fndecl (t
)
5220 && !cfi
->is_fn_info
)
5224 if (gimple_vdef (t
))
5225 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5227 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
), escaped_id
);
5229 /* Also honor the call statement use/clobber info. */
5230 if ((vi
= lookup_call_clobber_vi (call_stmt
)) != NULL
)
5231 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5233 if ((vi
= lookup_call_use_vi (call_stmt
)) != NULL
)
5234 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
),
5239 /* Otherwise the caller clobbers and uses what the callee does.
5240 ??? This should use a new complex constraint that filters
5241 local variables of the callee. */
5242 if (gimple_vdef (t
))
5244 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5245 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5246 process_constraint (new_constraint (lhs
, rhs
));
5248 lhs
= get_function_part_constraint (fi
, fi_uses
);
5249 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5250 process_constraint (new_constraint (lhs
, rhs
));
5252 else if (gimple_code (t
) == GIMPLE_ASM
)
5254 /* ??? Ick. We can do better. */
5255 if (gimple_vdef (t
))
5256 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5258 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5264 /* Find the first varinfo in the same variable as START that overlaps with
5265 OFFSET. Return NULL if we can't find one. */
5268 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
5270 /* If the offset is outside of the variable, bail out. */
5271 if (offset
>= start
->fullsize
)
5274 /* If we cannot reach offset from start, lookup the first field
5275 and start from there. */
5276 if (start
->offset
> offset
)
5277 start
= get_varinfo (start
->head
);
5281 /* We may not find a variable in the field list with the actual
5282 offset when we have glommed a structure to a variable.
5283 In that case, however, offset should still be within the size
5285 if (offset
>= start
->offset
5286 && (offset
- start
->offset
) < start
->size
)
5289 start
= vi_next (start
);
5295 /* Find the first varinfo in the same variable as START that overlaps with
5296 OFFSET. If there is no such varinfo the varinfo directly preceding
5297 OFFSET is returned. */
5300 first_or_preceding_vi_for_offset (varinfo_t start
,
5301 unsigned HOST_WIDE_INT offset
)
5303 /* If we cannot reach offset from start, lookup the first field
5304 and start from there. */
5305 if (start
->offset
> offset
)
5306 start
= get_varinfo (start
->head
);
5308 /* We may not find a variable in the field list with the actual
5309 offset when we have glommed a structure to a variable.
5310 In that case, however, offset should still be within the size
5312 If we got beyond the offset we look for return the field
5313 directly preceding offset which may be the last field. */
5315 && offset
>= start
->offset
5316 && !((offset
- start
->offset
) < start
->size
))
5317 start
= vi_next (start
);
5323 /* This structure is used during pushing fields onto the fieldstack
5324 to track the offset of the field, since bitpos_of_field gives it
5325 relative to its immediate containing type, and we want it relative
5326 to the ultimate containing object. */
5330 /* Offset from the base of the base containing object to this field. */
5331 HOST_WIDE_INT offset
;
5333 /* Size, in bits, of the field. */
5334 unsigned HOST_WIDE_INT size
;
5336 unsigned has_unknown_size
: 1;
5338 unsigned must_have_pointers
: 1;
5340 unsigned may_have_pointers
: 1;
5342 unsigned only_restrict_pointers
: 1;
5344 tree restrict_pointed_type
;
5346 typedef struct fieldoff fieldoff_s
;
5349 /* qsort comparison function for two fieldoff's PA and PB */
5352 fieldoff_compare (const void *pa
, const void *pb
)
5354 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
5355 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
5356 unsigned HOST_WIDE_INT foasize
, fobsize
;
5358 if (foa
->offset
< fob
->offset
)
5360 else if (foa
->offset
> fob
->offset
)
5363 foasize
= foa
->size
;
5364 fobsize
= fob
->size
;
5365 if (foasize
< fobsize
)
5367 else if (foasize
> fobsize
)
5372 /* Sort a fieldstack according to the field offset and sizes. */
5374 sort_fieldstack (vec
<fieldoff_s
> fieldstack
)
5376 fieldstack
.qsort (fieldoff_compare
);
5379 /* Return true if T is a type that can have subvars. */
5382 type_can_have_subvars (const_tree t
)
5384 /* Aggregates without overlapping fields can have subvars. */
5385 return TREE_CODE (t
) == RECORD_TYPE
;
5388 /* Return true if V is a tree that we can have subvars for.
5389 Normally, this is any aggregate type. Also complex
5390 types which are not gimple registers can have subvars. */
5393 var_can_have_subvars (const_tree v
)
5395 /* Volatile variables should never have subvars. */
5396 if (TREE_THIS_VOLATILE (v
))
5399 /* Non decls or memory tags can never have subvars. */
5403 return type_can_have_subvars (TREE_TYPE (v
));
5406 /* Return true if T is a type that does contain pointers. */
5409 type_must_have_pointers (tree type
)
5411 if (POINTER_TYPE_P (type
))
5414 if (TREE_CODE (type
) == ARRAY_TYPE
)
5415 return type_must_have_pointers (TREE_TYPE (type
));
5417 /* A function or method can have pointers as arguments, so track
5418 those separately. */
5419 if (TREE_CODE (type
) == FUNCTION_TYPE
5420 || TREE_CODE (type
) == METHOD_TYPE
)
5427 field_must_have_pointers (tree t
)
5429 return type_must_have_pointers (TREE_TYPE (t
));
5432 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5433 the fields of TYPE onto fieldstack, recording their offsets along
5436 OFFSET is used to keep track of the offset in this entire
5437 structure, rather than just the immediately containing structure.
5438 Returns false if the caller is supposed to handle the field we
5442 push_fields_onto_fieldstack (tree type
, vec
<fieldoff_s
> *fieldstack
,
5443 HOST_WIDE_INT offset
)
5446 bool empty_p
= true;
5448 if (TREE_CODE (type
) != RECORD_TYPE
)
5451 /* If the vector of fields is growing too big, bail out early.
5452 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5454 if (fieldstack
->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5457 for (field
= TYPE_FIELDS (type
); field
; field
= DECL_CHAIN (field
))
5458 if (TREE_CODE (field
) == FIELD_DECL
)
5461 HOST_WIDE_INT foff
= bitpos_of_field (field
);
5462 tree field_type
= TREE_TYPE (field
);
5464 if (!var_can_have_subvars (field
)
5465 || TREE_CODE (field_type
) == QUAL_UNION_TYPE
5466 || TREE_CODE (field_type
) == UNION_TYPE
)
5468 else if (!push_fields_onto_fieldstack
5469 (field_type
, fieldstack
, offset
+ foff
)
5470 && (DECL_SIZE (field
)
5471 && !integer_zerop (DECL_SIZE (field
))))
5472 /* Empty structures may have actual size, like in C++. So
5473 see if we didn't push any subfields and the size is
5474 nonzero, push the field onto the stack. */
5479 fieldoff_s
*pair
= NULL
;
5480 bool has_unknown_size
= false;
5481 bool must_have_pointers_p
;
5483 if (!fieldstack
->is_empty ())
5484 pair
= &fieldstack
->last ();
5486 /* If there isn't anything at offset zero, create sth. */
5488 && offset
+ foff
!= 0)
5491 = {0, offset
+ foff
, false, false, false, false, NULL_TREE
};
5492 pair
= fieldstack
->safe_push (e
);
5495 if (!DECL_SIZE (field
)
5496 || !tree_fits_uhwi_p (DECL_SIZE (field
)))
5497 has_unknown_size
= true;
5499 /* If adjacent fields do not contain pointers merge them. */
5500 must_have_pointers_p
= field_must_have_pointers (field
);
5502 && !has_unknown_size
5503 && !must_have_pointers_p
5504 && !pair
->must_have_pointers
5505 && !pair
->has_unknown_size
5506 && pair
->offset
+ (HOST_WIDE_INT
)pair
->size
== offset
+ foff
)
5508 pair
->size
+= tree_to_uhwi (DECL_SIZE (field
));
5513 e
.offset
= offset
+ foff
;
5514 e
.has_unknown_size
= has_unknown_size
;
5515 if (!has_unknown_size
)
5516 e
.size
= tree_to_uhwi (DECL_SIZE (field
));
5519 e
.must_have_pointers
= must_have_pointers_p
;
5520 e
.may_have_pointers
= true;
5521 e
.only_restrict_pointers
5522 = (!has_unknown_size
5523 && POINTER_TYPE_P (field_type
)
5524 && TYPE_RESTRICT (field_type
));
5525 if (e
.only_restrict_pointers
)
5526 e
.restrict_pointed_type
= TREE_TYPE (field_type
);
5527 fieldstack
->safe_push (e
);
5537 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5538 if it is a varargs function. */
5541 count_num_arguments (tree decl
, bool *is_varargs
)
5543 unsigned int num
= 0;
5546 /* Capture named arguments for K&R functions. They do not
5547 have a prototype and thus no TYPE_ARG_TYPES. */
5548 for (t
= DECL_ARGUMENTS (decl
); t
; t
= DECL_CHAIN (t
))
5551 /* Check if the function has variadic arguments. */
5552 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
)); t
; t
= TREE_CHAIN (t
))
5553 if (TREE_VALUE (t
) == void_type_node
)
5561 /* Creation function node for DECL, using NAME, and return the index
5562 of the variable we've created for the function. If NONLOCAL_p, create
5563 initial constraints. */
5566 create_function_info_for (tree decl
, const char *name
, bool add_id
,
5569 struct function
*fn
= DECL_STRUCT_FUNCTION (decl
);
5570 varinfo_t vi
, prev_vi
;
5573 bool is_varargs
= false;
5574 unsigned int num_args
= count_num_arguments (decl
, &is_varargs
);
5576 /* Create the variable info. */
5578 vi
= new_var_info (decl
, name
, add_id
);
5581 vi
->fullsize
= fi_parm_base
+ num_args
;
5583 vi
->may_have_pointers
= false;
5586 insert_vi_for_tree (vi
->decl
, vi
);
5590 /* Create a variable for things the function clobbers and one for
5591 things the function uses. */
5593 varinfo_t clobbervi
, usevi
;
5594 const char *newname
;
5597 tempname
= xasprintf ("%s.clobber", name
);
5598 newname
= ggc_strdup (tempname
);
5601 clobbervi
= new_var_info (NULL
, newname
, false);
5602 clobbervi
->offset
= fi_clobbers
;
5603 clobbervi
->size
= 1;
5604 clobbervi
->fullsize
= vi
->fullsize
;
5605 clobbervi
->is_full_var
= true;
5606 clobbervi
->is_global_var
= false;
5608 gcc_assert (prev_vi
->offset
< clobbervi
->offset
);
5609 prev_vi
->next
= clobbervi
->id
;
5610 prev_vi
= clobbervi
;
5612 tempname
= xasprintf ("%s.use", name
);
5613 newname
= ggc_strdup (tempname
);
5616 usevi
= new_var_info (NULL
, newname
, false);
5617 usevi
->offset
= fi_uses
;
5619 usevi
->fullsize
= vi
->fullsize
;
5620 usevi
->is_full_var
= true;
5621 usevi
->is_global_var
= false;
5623 gcc_assert (prev_vi
->offset
< usevi
->offset
);
5624 prev_vi
->next
= usevi
->id
;
5628 /* And one for the static chain. */
5629 if (fn
->static_chain_decl
!= NULL_TREE
)
5632 const char *newname
;
5635 tempname
= xasprintf ("%s.chain", name
);
5636 newname
= ggc_strdup (tempname
);
5639 chainvi
= new_var_info (fn
->static_chain_decl
, newname
, false);
5640 chainvi
->offset
= fi_static_chain
;
5642 chainvi
->fullsize
= vi
->fullsize
;
5643 chainvi
->is_full_var
= true;
5644 chainvi
->is_global_var
= false;
5646 insert_vi_for_tree (fn
->static_chain_decl
, chainvi
);
5649 && chainvi
->may_have_pointers
)
5650 make_constraint_from (chainvi
, nonlocal_id
);
5652 gcc_assert (prev_vi
->offset
< chainvi
->offset
);
5653 prev_vi
->next
= chainvi
->id
;
5657 /* Create a variable for the return var. */
5658 if (DECL_RESULT (decl
) != NULL
5659 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
5662 const char *newname
;
5664 tree resultdecl
= decl
;
5666 if (DECL_RESULT (decl
))
5667 resultdecl
= DECL_RESULT (decl
);
5669 tempname
= xasprintf ("%s.result", name
);
5670 newname
= ggc_strdup (tempname
);
5673 resultvi
= new_var_info (resultdecl
, newname
, false);
5674 resultvi
->offset
= fi_result
;
5676 resultvi
->fullsize
= vi
->fullsize
;
5677 resultvi
->is_full_var
= true;
5678 if (DECL_RESULT (decl
))
5679 resultvi
->may_have_pointers
= true;
5681 if (DECL_RESULT (decl
))
5682 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
5685 && DECL_RESULT (decl
)
5686 && DECL_BY_REFERENCE (DECL_RESULT (decl
)))
5687 make_constraint_from (resultvi
, nonlocal_id
);
5689 gcc_assert (prev_vi
->offset
< resultvi
->offset
);
5690 prev_vi
->next
= resultvi
->id
;
5694 /* We also need to make function return values escape. Nothing
5695 escapes by returning from main though. */
5697 && !MAIN_NAME_P (DECL_NAME (decl
)))
5700 fi
= lookup_vi_for_tree (decl
);
5701 rvi
= first_vi_for_offset (fi
, fi_result
);
5702 if (rvi
&& rvi
->offset
== fi_result
)
5703 make_copy_constraint (get_varinfo (escaped_id
), rvi
->id
);
5706 /* Set up variables for each argument. */
5707 arg
= DECL_ARGUMENTS (decl
);
5708 for (i
= 0; i
< num_args
; i
++)
5711 const char *newname
;
5713 tree argdecl
= decl
;
5718 tempname
= xasprintf ("%s.arg%d", name
, i
);
5719 newname
= ggc_strdup (tempname
);
5722 argvi
= new_var_info (argdecl
, newname
, false);
5723 argvi
->offset
= fi_parm_base
+ i
;
5725 argvi
->is_full_var
= true;
5726 argvi
->fullsize
= vi
->fullsize
;
5728 argvi
->may_have_pointers
= true;
5731 insert_vi_for_tree (arg
, argvi
);
5734 && argvi
->may_have_pointers
)
5735 make_constraint_from (argvi
, nonlocal_id
);
5737 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5738 prev_vi
->next
= argvi
->id
;
5741 arg
= DECL_CHAIN (arg
);
5744 /* Add one representative for all further args. */
5748 const char *newname
;
5752 tempname
= xasprintf ("%s.varargs", name
);
5753 newname
= ggc_strdup (tempname
);
5756 /* We need sth that can be pointed to for va_start. */
5757 decl
= build_fake_var_decl (ptr_type_node
);
5759 argvi
= new_var_info (decl
, newname
, false);
5760 argvi
->offset
= fi_parm_base
+ num_args
;
5762 argvi
->is_full_var
= true;
5763 argvi
->is_heap_var
= true;
5764 argvi
->fullsize
= vi
->fullsize
;
5767 && argvi
->may_have_pointers
)
5768 make_constraint_from (argvi
, nonlocal_id
);
5770 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5771 prev_vi
->next
= argvi
->id
;
5779 /* Return true if FIELDSTACK contains fields that overlap.
5780 FIELDSTACK is assumed to be sorted by offset. */
5783 check_for_overlaps (vec
<fieldoff_s
> fieldstack
)
5785 fieldoff_s
*fo
= NULL
;
5787 HOST_WIDE_INT lastoffset
= -1;
5789 FOR_EACH_VEC_ELT (fieldstack
, i
, fo
)
5791 if (fo
->offset
== lastoffset
)
5793 lastoffset
= fo
->offset
;
5798 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5799 This will also create any varinfo structures necessary for fields
5800 of DECL. DECL is a function parameter if HANDLE_PARAM is set.
5801 HANDLED_STRUCT_TYPE is used to register struct types reached by following
5802 restrict pointers. This is needed to prevent infinite recursion. */
5805 create_variable_info_for_1 (tree decl
, const char *name
, bool add_id
,
5806 bool handle_param
, bitmap handled_struct_type
)
5808 varinfo_t vi
, newvi
;
5809 tree decl_type
= TREE_TYPE (decl
);
5810 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decl_type
);
5811 auto_vec
<fieldoff_s
> fieldstack
;
5816 || !tree_fits_uhwi_p (declsize
))
5818 vi
= new_var_info (decl
, name
, add_id
);
5822 vi
->is_unknown_size_var
= true;
5823 vi
->is_full_var
= true;
5824 vi
->may_have_pointers
= true;
5828 /* Collect field information. */
5829 if (use_field_sensitive
5830 && var_can_have_subvars (decl
)
5831 /* ??? Force us to not use subfields for globals in IPA mode.
5832 Else we'd have to parse arbitrary initializers. */
5834 && is_global_var (decl
)))
5836 fieldoff_s
*fo
= NULL
;
5837 bool notokay
= false;
5840 push_fields_onto_fieldstack (decl_type
, &fieldstack
, 0);
5842 for (i
= 0; !notokay
&& fieldstack
.iterate (i
, &fo
); i
++)
5843 if (fo
->has_unknown_size
5850 /* We can't sort them if we have a field with a variable sized type,
5851 which will make notokay = true. In that case, we are going to return
5852 without creating varinfos for the fields anyway, so sorting them is a
5856 sort_fieldstack (fieldstack
);
5857 /* Due to some C++ FE issues, like PR 22488, we might end up
5858 what appear to be overlapping fields even though they,
5859 in reality, do not overlap. Until the C++ FE is fixed,
5860 we will simply disable field-sensitivity for these cases. */
5861 notokay
= check_for_overlaps (fieldstack
);
5865 fieldstack
.release ();
5868 /* If we didn't end up collecting sub-variables create a full
5869 variable for the decl. */
5870 if (fieldstack
.length () == 0
5871 || fieldstack
.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5873 vi
= new_var_info (decl
, name
, add_id
);
5875 vi
->may_have_pointers
= true;
5876 vi
->fullsize
= tree_to_uhwi (declsize
);
5877 vi
->size
= vi
->fullsize
;
5878 vi
->is_full_var
= true;
5879 if (POINTER_TYPE_P (decl_type
)
5880 && TYPE_RESTRICT (decl_type
))
5881 vi
->only_restrict_pointers
= 1;
5882 if (vi
->only_restrict_pointers
5883 && !type_contains_placeholder_p (TREE_TYPE (decl_type
))
5885 && !bitmap_bit_p (handled_struct_type
,
5886 TYPE_UID (TREE_TYPE (decl_type
))))
5889 tree heapvar
= build_fake_var_decl (TREE_TYPE (decl_type
));
5890 DECL_EXTERNAL (heapvar
) = 1;
5891 if (var_can_have_subvars (heapvar
))
5892 bitmap_set_bit (handled_struct_type
,
5893 TYPE_UID (TREE_TYPE (decl_type
)));
5894 rvi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS", true,
5895 true, handled_struct_type
);
5896 if (var_can_have_subvars (heapvar
))
5897 bitmap_clear_bit (handled_struct_type
,
5898 TYPE_UID (TREE_TYPE (decl_type
)));
5899 rvi
->is_restrict_var
= 1;
5900 insert_vi_for_tree (heapvar
, rvi
);
5901 make_constraint_from (vi
, rvi
->id
);
5902 make_param_constraints (rvi
);
5904 fieldstack
.release ();
5908 vi
= new_var_info (decl
, name
, add_id
);
5909 vi
->fullsize
= tree_to_uhwi (declsize
);
5910 if (fieldstack
.length () == 1)
5911 vi
->is_full_var
= true;
5912 for (i
= 0, newvi
= vi
;
5913 fieldstack
.iterate (i
, &fo
);
5914 ++i
, newvi
= vi_next (newvi
))
5916 const char *newname
= NULL
;
5921 if (fieldstack
.length () != 1)
5924 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC
5925 "+" HOST_WIDE_INT_PRINT_DEC
, name
,
5926 fo
->offset
, fo
->size
);
5927 newname
= ggc_strdup (tempname
);
5935 newvi
->name
= newname
;
5936 newvi
->offset
= fo
->offset
;
5937 newvi
->size
= fo
->size
;
5938 newvi
->fullsize
= vi
->fullsize
;
5939 newvi
->may_have_pointers
= fo
->may_have_pointers
;
5940 newvi
->only_restrict_pointers
= fo
->only_restrict_pointers
;
5942 && newvi
->only_restrict_pointers
5943 && !type_contains_placeholder_p (fo
->restrict_pointed_type
)
5944 && !bitmap_bit_p (handled_struct_type
,
5945 TYPE_UID (fo
->restrict_pointed_type
)))
5948 tree heapvar
= build_fake_var_decl (fo
->restrict_pointed_type
);
5949 DECL_EXTERNAL (heapvar
) = 1;
5950 if (var_can_have_subvars (heapvar
))
5951 bitmap_set_bit (handled_struct_type
,
5952 TYPE_UID (fo
->restrict_pointed_type
));
5953 rvi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS", true,
5954 true, handled_struct_type
);
5955 if (var_can_have_subvars (heapvar
))
5956 bitmap_clear_bit (handled_struct_type
,
5957 TYPE_UID (fo
->restrict_pointed_type
));
5958 rvi
->is_restrict_var
= 1;
5959 insert_vi_for_tree (heapvar
, rvi
);
5960 make_constraint_from (newvi
, rvi
->id
);
5961 make_param_constraints (rvi
);
5963 if (i
+ 1 < fieldstack
.length ())
5965 varinfo_t tem
= new_var_info (decl
, name
, false);
5966 newvi
->next
= tem
->id
;
5975 create_variable_info_for (tree decl
, const char *name
, bool add_id
)
5977 varinfo_t vi
= create_variable_info_for_1 (decl
, name
, add_id
, false, NULL
);
5978 unsigned int id
= vi
->id
;
5980 insert_vi_for_tree (decl
, vi
);
5982 if (TREE_CODE (decl
) != VAR_DECL
)
5985 /* Create initial constraints for globals. */
5986 for (; vi
; vi
= vi_next (vi
))
5988 if (!vi
->may_have_pointers
5989 || !vi
->is_global_var
)
5992 /* Mark global restrict qualified pointers. */
5993 if ((POINTER_TYPE_P (TREE_TYPE (decl
))
5994 && TYPE_RESTRICT (TREE_TYPE (decl
)))
5995 || vi
->only_restrict_pointers
)
5998 = make_constraint_from_global_restrict (vi
, "GLOBAL_RESTRICT",
6000 /* ??? For now exclude reads from globals as restrict sources
6001 if those are not (indirectly) from incoming parameters. */
6002 rvi
->is_restrict_var
= false;
6006 /* In non-IPA mode the initializer from nonlocal is all we need. */
6008 || DECL_HARD_REGISTER (decl
))
6009 make_copy_constraint (vi
, nonlocal_id
);
6011 /* In IPA mode parse the initializer and generate proper constraints
6015 varpool_node
*vnode
= varpool_node::get (decl
);
6017 /* For escaped variables initialize them from nonlocal. */
6018 if (!vnode
->all_refs_explicit_p ())
6019 make_copy_constraint (vi
, nonlocal_id
);
6021 /* If this is a global variable with an initializer and we are in
6022 IPA mode generate constraints for it. */
6024 for (unsigned idx
= 0; vnode
->iterate_reference (idx
, ref
); ++idx
)
6026 auto_vec
<ce_s
> rhsc
;
6027 struct constraint_expr lhs
, *rhsp
;
6029 get_constraint_for_address_of (ref
->referred
->decl
, &rhsc
);
6033 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
6034 process_constraint (new_constraint (lhs
, *rhsp
));
6035 /* If this is a variable that escapes from the unit
6036 the initializer escapes as well. */
6037 if (!vnode
->all_refs_explicit_p ())
6039 lhs
.var
= escaped_id
;
6042 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
6043 process_constraint (new_constraint (lhs
, *rhsp
));
6052 /* Print out the points-to solution for VAR to FILE. */
6055 dump_solution_for_var (FILE *file
, unsigned int var
)
6057 varinfo_t vi
= get_varinfo (var
);
6061 /* Dump the solution for unified vars anyway, this avoids difficulties
6062 in scanning dumps in the testsuite. */
6063 fprintf (file
, "%s = { ", vi
->name
);
6064 vi
= get_varinfo (find (var
));
6065 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6066 fprintf (file
, "%s ", get_varinfo (i
)->name
);
6067 fprintf (file
, "}");
6069 /* But note when the variable was unified. */
6071 fprintf (file
, " same as %s", vi
->name
);
6073 fprintf (file
, "\n");
6076 /* Print the points-to solution for VAR to stderr. */
6079 debug_solution_for_var (unsigned int var
)
6081 dump_solution_for_var (stderr
, var
);
6084 /* Register the constraints for function parameter related VI. */
6087 make_param_constraints (varinfo_t vi
)
6089 for (; vi
; vi
= vi_next (vi
))
6091 if (vi
->only_restrict_pointers
)
6093 else if (vi
->may_have_pointers
)
6094 make_constraint_from (vi
, nonlocal_id
);
6096 if (vi
->is_full_var
)
6101 /* Create varinfo structures for all of the variables in the
6102 function for intraprocedural mode. */
6105 intra_create_variable_infos (struct function
*fn
)
6108 bitmap handled_struct_type
= NULL
;
6110 /* For each incoming pointer argument arg, create the constraint ARG
6111 = NONLOCAL or a dummy variable if it is a restrict qualified
6112 passed-by-reference argument. */
6113 for (t
= DECL_ARGUMENTS (fn
->decl
); t
; t
= DECL_CHAIN (t
))
6115 if (handled_struct_type
== NULL
)
6116 handled_struct_type
= BITMAP_ALLOC (NULL
);
6119 = create_variable_info_for_1 (t
, alias_get_name (t
), false, true,
6120 handled_struct_type
);
6121 insert_vi_for_tree (t
, p
);
6123 make_param_constraints (p
);
6126 if (handled_struct_type
!= NULL
)
6127 BITMAP_FREE (handled_struct_type
);
6129 /* Add a constraint for a result decl that is passed by reference. */
6130 if (DECL_RESULT (fn
->decl
)
6131 && DECL_BY_REFERENCE (DECL_RESULT (fn
->decl
)))
6133 varinfo_t p
, result_vi
= get_vi_for_tree (DECL_RESULT (fn
->decl
));
6135 for (p
= result_vi
; p
; p
= vi_next (p
))
6136 make_constraint_from (p
, nonlocal_id
);
6139 /* Add a constraint for the incoming static chain parameter. */
6140 if (fn
->static_chain_decl
!= NULL_TREE
)
6142 varinfo_t p
, chain_vi
= get_vi_for_tree (fn
->static_chain_decl
);
6144 for (p
= chain_vi
; p
; p
= vi_next (p
))
6145 make_constraint_from (p
, nonlocal_id
);
6149 /* Structure used to put solution bitmaps in a hashtable so they can
6150 be shared among variables with the same points-to set. */
6152 typedef struct shared_bitmap_info
6156 } *shared_bitmap_info_t
;
6157 typedef const struct shared_bitmap_info
*const_shared_bitmap_info_t
;
6159 /* Shared_bitmap hashtable helpers. */
6161 struct shared_bitmap_hasher
: free_ptr_hash
<shared_bitmap_info
>
6163 static inline hashval_t
hash (const shared_bitmap_info
*);
6164 static inline bool equal (const shared_bitmap_info
*,
6165 const shared_bitmap_info
*);
6168 /* Hash function for a shared_bitmap_info_t */
6171 shared_bitmap_hasher::hash (const shared_bitmap_info
*bi
)
6173 return bi
->hashcode
;
6176 /* Equality function for two shared_bitmap_info_t's. */
6179 shared_bitmap_hasher::equal (const shared_bitmap_info
*sbi1
,
6180 const shared_bitmap_info
*sbi2
)
6182 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
6185 /* Shared_bitmap hashtable. */
6187 static hash_table
<shared_bitmap_hasher
> *shared_bitmap_table
;
6189 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
6190 existing instance if there is one, NULL otherwise. */
6193 shared_bitmap_lookup (bitmap pt_vars
)
6195 shared_bitmap_info
**slot
;
6196 struct shared_bitmap_info sbi
;
6198 sbi
.pt_vars
= pt_vars
;
6199 sbi
.hashcode
= bitmap_hash (pt_vars
);
6201 slot
= shared_bitmap_table
->find_slot (&sbi
, NO_INSERT
);
6205 return (*slot
)->pt_vars
;
6209 /* Add a bitmap to the shared bitmap hashtable. */
6212 shared_bitmap_add (bitmap pt_vars
)
6214 shared_bitmap_info
**slot
;
6215 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
6217 sbi
->pt_vars
= pt_vars
;
6218 sbi
->hashcode
= bitmap_hash (pt_vars
);
6220 slot
= shared_bitmap_table
->find_slot (sbi
, INSERT
);
6221 gcc_assert (!*slot
);
6226 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
6229 set_uids_in_ptset (bitmap into
, bitmap from
, struct pt_solution
*pt
,
6234 varinfo_t escaped_vi
= get_varinfo (find (escaped_id
));
6235 bool everything_escaped
6236 = escaped_vi
->solution
&& bitmap_bit_p (escaped_vi
->solution
, anything_id
);
6238 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
6240 varinfo_t vi
= get_varinfo (i
);
6242 /* The only artificial variables that are allowed in a may-alias
6243 set are heap variables. */
6244 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
6247 if (everything_escaped
6248 || (escaped_vi
->solution
6249 && bitmap_bit_p (escaped_vi
->solution
, i
)))
6251 pt
->vars_contains_escaped
= true;
6252 pt
->vars_contains_escaped_heap
= vi
->is_heap_var
;
6255 if (TREE_CODE (vi
->decl
) == VAR_DECL
6256 || TREE_CODE (vi
->decl
) == PARM_DECL
6257 || TREE_CODE (vi
->decl
) == RESULT_DECL
)
6259 /* If we are in IPA mode we will not recompute points-to
6260 sets after inlining so make sure they stay valid. */
6262 && !DECL_PT_UID_SET_P (vi
->decl
))
6263 SET_DECL_PT_UID (vi
->decl
, DECL_UID (vi
->decl
));
6265 /* Add the decl to the points-to set. Note that the points-to
6266 set contains global variables. */
6267 bitmap_set_bit (into
, DECL_PT_UID (vi
->decl
));
6268 if (vi
->is_global_var
6269 /* In IPA mode the escaped_heap trick doesn't work as
6270 ESCAPED is escaped from the unit but
6271 pt_solution_includes_global needs to answer true for
6272 all variables not automatic within a function.
6273 For the same reason is_global_var is not the
6274 correct flag to track - local variables from other
6275 functions also need to be considered global.
6276 Conveniently all HEAP vars are not put in function
6280 && ! auto_var_in_fn_p (vi
->decl
, fndecl
)))
6281 pt
->vars_contains_nonlocal
= true;
6287 /* Compute the points-to solution *PT for the variable VI. */
6289 static struct pt_solution
6290 find_what_var_points_to (tree fndecl
, varinfo_t orig_vi
)
6294 bitmap finished_solution
;
6297 struct pt_solution
*pt
;
6299 /* This variable may have been collapsed, let's get the real
6301 vi
= get_varinfo (find (orig_vi
->id
));
6303 /* See if we have already computed the solution and return it. */
6304 pt_solution
**slot
= &final_solutions
->get_or_insert (vi
);
6308 *slot
= pt
= XOBNEW (&final_solutions_obstack
, struct pt_solution
);
6309 memset (pt
, 0, sizeof (struct pt_solution
));
6311 /* Translate artificial variables into SSA_NAME_PTR_INFO
6313 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6315 varinfo_t vi
= get_varinfo (i
);
6317 if (vi
->is_artificial_var
)
6319 if (vi
->id
== nothing_id
)
6321 else if (vi
->id
== escaped_id
)
6324 pt
->ipa_escaped
= 1;
6327 /* Expand some special vars of ESCAPED in-place here. */
6328 varinfo_t evi
= get_varinfo (find (escaped_id
));
6329 if (bitmap_bit_p (evi
->solution
, nonlocal_id
))
6332 else if (vi
->id
== nonlocal_id
)
6334 else if (vi
->is_heap_var
)
6335 /* We represent heapvars in the points-to set properly. */
6337 else if (vi
->id
== string_id
)
6338 /* Nobody cares - STRING_CSTs are read-only entities. */
6340 else if (vi
->id
== anything_id
6341 || vi
->id
== integer_id
)
6346 /* Instead of doing extra work, simply do not create
6347 elaborate points-to information for pt_anything pointers. */
6351 /* Share the final set of variables when possible. */
6352 finished_solution
= BITMAP_GGC_ALLOC ();
6353 stats
.points_to_sets_created
++;
6355 set_uids_in_ptset (finished_solution
, vi
->solution
, pt
, fndecl
);
6356 result
= shared_bitmap_lookup (finished_solution
);
6359 shared_bitmap_add (finished_solution
);
6360 pt
->vars
= finished_solution
;
6365 bitmap_clear (finished_solution
);
6371 /* Given a pointer variable P, fill in its points-to set. */
6374 find_what_p_points_to (tree fndecl
, tree p
)
6376 struct ptr_info_def
*pi
;
6380 /* For parameters, get at the points-to set for the actual parm
6382 if (TREE_CODE (p
) == SSA_NAME
6383 && SSA_NAME_IS_DEFAULT_DEF (p
)
6384 && (TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
6385 || TREE_CODE (SSA_NAME_VAR (p
)) == RESULT_DECL
))
6386 lookup_p
= SSA_NAME_VAR (p
);
6388 vi
= lookup_vi_for_tree (lookup_p
);
6392 pi
= get_ptr_info (p
);
6393 pi
->pt
= find_what_var_points_to (fndecl
, vi
);
6397 /* Query statistics for points-to solutions. */
6400 unsigned HOST_WIDE_INT pt_solution_includes_may_alias
;
6401 unsigned HOST_WIDE_INT pt_solution_includes_no_alias
;
6402 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias
;
6403 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias
;
6407 dump_pta_stats (FILE *s
)
6409 fprintf (s
, "\nPTA query stats:\n");
6410 fprintf (s
, " pt_solution_includes: "
6411 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6412 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6413 pta_stats
.pt_solution_includes_no_alias
,
6414 pta_stats
.pt_solution_includes_no_alias
6415 + pta_stats
.pt_solution_includes_may_alias
);
6416 fprintf (s
, " pt_solutions_intersect: "
6417 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6418 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6419 pta_stats
.pt_solutions_intersect_no_alias
,
6420 pta_stats
.pt_solutions_intersect_no_alias
6421 + pta_stats
.pt_solutions_intersect_may_alias
);
6425 /* Reset the points-to solution *PT to a conservative default
6426 (point to anything). */
6429 pt_solution_reset (struct pt_solution
*pt
)
6431 memset (pt
, 0, sizeof (struct pt_solution
));
6432 pt
->anything
= true;
6435 /* Set the points-to solution *PT to point only to the variables
6436 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6437 global variables and VARS_CONTAINS_RESTRICT specifies whether
6438 it contains restrict tag variables. */
6441 pt_solution_set (struct pt_solution
*pt
, bitmap vars
,
6442 bool vars_contains_nonlocal
)
6444 memset (pt
, 0, sizeof (struct pt_solution
));
6446 pt
->vars_contains_nonlocal
= vars_contains_nonlocal
;
6447 pt
->vars_contains_escaped
6448 = (cfun
->gimple_df
->escaped
.anything
6449 || bitmap_intersect_p (cfun
->gimple_df
->escaped
.vars
, vars
));
6452 /* Set the points-to solution *PT to point only to the variable VAR. */
6455 pt_solution_set_var (struct pt_solution
*pt
, tree var
)
6457 memset (pt
, 0, sizeof (struct pt_solution
));
6458 pt
->vars
= BITMAP_GGC_ALLOC ();
6459 bitmap_set_bit (pt
->vars
, DECL_PT_UID (var
));
6460 pt
->vars_contains_nonlocal
= is_global_var (var
);
6461 pt
->vars_contains_escaped
6462 = (cfun
->gimple_df
->escaped
.anything
6463 || bitmap_bit_p (cfun
->gimple_df
->escaped
.vars
, DECL_PT_UID (var
)));
6466 /* Computes the union of the points-to solutions *DEST and *SRC and
6467 stores the result in *DEST. This changes the points-to bitmap
6468 of *DEST and thus may not be used if that might be shared.
6469 The points-to bitmap of *SRC and *DEST will not be shared after
6470 this function if they were not before. */
6473 pt_solution_ior_into (struct pt_solution
*dest
, struct pt_solution
*src
)
6475 dest
->anything
|= src
->anything
;
6478 pt_solution_reset (dest
);
6482 dest
->nonlocal
|= src
->nonlocal
;
6483 dest
->escaped
|= src
->escaped
;
6484 dest
->ipa_escaped
|= src
->ipa_escaped
;
6485 dest
->null
|= src
->null
;
6486 dest
->vars_contains_nonlocal
|= src
->vars_contains_nonlocal
;
6487 dest
->vars_contains_escaped
|= src
->vars_contains_escaped
;
6488 dest
->vars_contains_escaped_heap
|= src
->vars_contains_escaped_heap
;
6493 dest
->vars
= BITMAP_GGC_ALLOC ();
6494 bitmap_ior_into (dest
->vars
, src
->vars
);
6497 /* Return true if the points-to solution *PT is empty. */
6500 pt_solution_empty_p (struct pt_solution
*pt
)
6507 && !bitmap_empty_p (pt
->vars
))
6510 /* If the solution includes ESCAPED, check if that is empty. */
6512 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
6515 /* If the solution includes ESCAPED, check if that is empty. */
6517 && !pt_solution_empty_p (&ipa_escaped_pt
))
6523 /* Return true if the points-to solution *PT only point to a single var, and
6524 return the var uid in *UID. */
6527 pt_solution_singleton_p (struct pt_solution
*pt
, unsigned *uid
)
6529 if (pt
->anything
|| pt
->nonlocal
|| pt
->escaped
|| pt
->ipa_escaped
6530 || pt
->null
|| pt
->vars
== NULL
6531 || !bitmap_single_bit_set_p (pt
->vars
))
6534 *uid
= bitmap_first_set_bit (pt
->vars
);
6538 /* Return true if the points-to solution *PT includes global memory. */
6541 pt_solution_includes_global (struct pt_solution
*pt
)
6545 || pt
->vars_contains_nonlocal
6546 /* The following is a hack to make the malloc escape hack work.
6547 In reality we'd need different sets for escaped-through-return
6548 and escaped-to-callees and passes would need to be updated. */
6549 || pt
->vars_contains_escaped_heap
)
6552 /* 'escaped' is also a placeholder so we have to look into it. */
6554 return pt_solution_includes_global (&cfun
->gimple_df
->escaped
);
6556 if (pt
->ipa_escaped
)
6557 return pt_solution_includes_global (&ipa_escaped_pt
);
6562 /* Return true if the points-to solution *PT includes the variable
6563 declaration DECL. */
6566 pt_solution_includes_1 (struct pt_solution
*pt
, const_tree decl
)
6572 && is_global_var (decl
))
6576 && bitmap_bit_p (pt
->vars
, DECL_PT_UID (decl
)))
6579 /* If the solution includes ESCAPED, check it. */
6581 && pt_solution_includes_1 (&cfun
->gimple_df
->escaped
, decl
))
6584 /* If the solution includes ESCAPED, check it. */
6586 && pt_solution_includes_1 (&ipa_escaped_pt
, decl
))
6593 pt_solution_includes (struct pt_solution
*pt
, const_tree decl
)
6595 bool res
= pt_solution_includes_1 (pt
, decl
);
6597 ++pta_stats
.pt_solution_includes_may_alias
;
6599 ++pta_stats
.pt_solution_includes_no_alias
;
6603 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6607 pt_solutions_intersect_1 (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6609 if (pt1
->anything
|| pt2
->anything
)
6612 /* If either points to unknown global memory and the other points to
6613 any global memory they alias. */
6616 || pt2
->vars_contains_nonlocal
))
6618 && pt1
->vars_contains_nonlocal
))
6621 /* If either points to all escaped memory and the other points to
6622 any escaped memory they alias. */
6625 || pt2
->vars_contains_escaped
))
6627 && pt1
->vars_contains_escaped
))
6630 /* Check the escaped solution if required.
6631 ??? Do we need to check the local against the IPA escaped sets? */
6632 if ((pt1
->ipa_escaped
|| pt2
->ipa_escaped
)
6633 && !pt_solution_empty_p (&ipa_escaped_pt
))
6635 /* If both point to escaped memory and that solution
6636 is not empty they alias. */
6637 if (pt1
->ipa_escaped
&& pt2
->ipa_escaped
)
6640 /* If either points to escaped memory see if the escaped solution
6641 intersects with the other. */
6642 if ((pt1
->ipa_escaped
6643 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt2
))
6644 || (pt2
->ipa_escaped
6645 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt1
)))
6649 /* Now both pointers alias if their points-to solution intersects. */
6652 && bitmap_intersect_p (pt1
->vars
, pt2
->vars
));
6656 pt_solutions_intersect (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6658 bool res
= pt_solutions_intersect_1 (pt1
, pt2
);
6660 ++pta_stats
.pt_solutions_intersect_may_alias
;
6662 ++pta_stats
.pt_solutions_intersect_no_alias
;
6667 /* Dump points-to information to OUTFILE. */
6670 dump_sa_points_to_info (FILE *outfile
)
6674 fprintf (outfile
, "\nPoints-to sets\n\n");
6676 if (dump_flags
& TDF_STATS
)
6678 fprintf (outfile
, "Stats:\n");
6679 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
6680 fprintf (outfile
, "Non-pointer vars: %d\n",
6681 stats
.nonpointer_vars
);
6682 fprintf (outfile
, "Statically unified vars: %d\n",
6683 stats
.unified_vars_static
);
6684 fprintf (outfile
, "Dynamically unified vars: %d\n",
6685 stats
.unified_vars_dynamic
);
6686 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
6687 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
6688 fprintf (outfile
, "Number of implicit edges: %d\n",
6689 stats
.num_implicit_edges
);
6692 for (i
= 1; i
< varmap
.length (); i
++)
6694 varinfo_t vi
= get_varinfo (i
);
6695 if (!vi
->may_have_pointers
)
6697 dump_solution_for_var (outfile
, i
);
6702 /* Debug points-to information to stderr. */
6705 debug_sa_points_to_info (void)
6707 dump_sa_points_to_info (stderr
);
6711 /* Initialize the always-existing constraint variables for NULL
6712 ANYTHING, READONLY, and INTEGER */
6715 init_base_vars (void)
6717 struct constraint_expr lhs
, rhs
;
6718 varinfo_t var_anything
;
6719 varinfo_t var_nothing
;
6720 varinfo_t var_string
;
6721 varinfo_t var_escaped
;
6722 varinfo_t var_nonlocal
;
6723 varinfo_t var_storedanything
;
6724 varinfo_t var_integer
;
6726 /* Variable ID zero is reserved and should be NULL. */
6727 varmap
.safe_push (NULL
);
6729 /* Create the NULL variable, used to represent that a variable points
6731 var_nothing
= new_var_info (NULL_TREE
, "NULL", false);
6732 gcc_assert (var_nothing
->id
== nothing_id
);
6733 var_nothing
->is_artificial_var
= 1;
6734 var_nothing
->offset
= 0;
6735 var_nothing
->size
= ~0;
6736 var_nothing
->fullsize
= ~0;
6737 var_nothing
->is_special_var
= 1;
6738 var_nothing
->may_have_pointers
= 0;
6739 var_nothing
->is_global_var
= 0;
6741 /* Create the ANYTHING variable, used to represent that a variable
6742 points to some unknown piece of memory. */
6743 var_anything
= new_var_info (NULL_TREE
, "ANYTHING", false);
6744 gcc_assert (var_anything
->id
== anything_id
);
6745 var_anything
->is_artificial_var
= 1;
6746 var_anything
->size
= ~0;
6747 var_anything
->offset
= 0;
6748 var_anything
->fullsize
= ~0;
6749 var_anything
->is_special_var
= 1;
6751 /* Anything points to anything. This makes deref constraints just
6752 work in the presence of linked list and other p = *p type loops,
6753 by saying that *ANYTHING = ANYTHING. */
6755 lhs
.var
= anything_id
;
6757 rhs
.type
= ADDRESSOF
;
6758 rhs
.var
= anything_id
;
6761 /* This specifically does not use process_constraint because
6762 process_constraint ignores all anything = anything constraints, since all
6763 but this one are redundant. */
6764 constraints
.safe_push (new_constraint (lhs
, rhs
));
6766 /* Create the STRING variable, used to represent that a variable
6767 points to a string literal. String literals don't contain
6768 pointers so STRING doesn't point to anything. */
6769 var_string
= new_var_info (NULL_TREE
, "STRING", false);
6770 gcc_assert (var_string
->id
== string_id
);
6771 var_string
->is_artificial_var
= 1;
6772 var_string
->offset
= 0;
6773 var_string
->size
= ~0;
6774 var_string
->fullsize
= ~0;
6775 var_string
->is_special_var
= 1;
6776 var_string
->may_have_pointers
= 0;
6778 /* Create the ESCAPED variable, used to represent the set of escaped
6780 var_escaped
= new_var_info (NULL_TREE
, "ESCAPED", false);
6781 gcc_assert (var_escaped
->id
== escaped_id
);
6782 var_escaped
->is_artificial_var
= 1;
6783 var_escaped
->offset
= 0;
6784 var_escaped
->size
= ~0;
6785 var_escaped
->fullsize
= ~0;
6786 var_escaped
->is_special_var
= 0;
6788 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6790 var_nonlocal
= new_var_info (NULL_TREE
, "NONLOCAL", false);
6791 gcc_assert (var_nonlocal
->id
== nonlocal_id
);
6792 var_nonlocal
->is_artificial_var
= 1;
6793 var_nonlocal
->offset
= 0;
6794 var_nonlocal
->size
= ~0;
6795 var_nonlocal
->fullsize
= ~0;
6796 var_nonlocal
->is_special_var
= 1;
6798 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6800 lhs
.var
= escaped_id
;
6803 rhs
.var
= escaped_id
;
6805 process_constraint (new_constraint (lhs
, rhs
));
6807 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6808 whole variable escapes. */
6810 lhs
.var
= escaped_id
;
6813 rhs
.var
= escaped_id
;
6814 rhs
.offset
= UNKNOWN_OFFSET
;
6815 process_constraint (new_constraint (lhs
, rhs
));
6817 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6818 everything pointed to by escaped points to what global memory can
6821 lhs
.var
= escaped_id
;
6824 rhs
.var
= nonlocal_id
;
6826 process_constraint (new_constraint (lhs
, rhs
));
6828 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6829 global memory may point to global memory and escaped memory. */
6831 lhs
.var
= nonlocal_id
;
6833 rhs
.type
= ADDRESSOF
;
6834 rhs
.var
= nonlocal_id
;
6836 process_constraint (new_constraint (lhs
, rhs
));
6837 rhs
.type
= ADDRESSOF
;
6838 rhs
.var
= escaped_id
;
6840 process_constraint (new_constraint (lhs
, rhs
));
6842 /* Create the STOREDANYTHING variable, used to represent the set of
6843 variables stored to *ANYTHING. */
6844 var_storedanything
= new_var_info (NULL_TREE
, "STOREDANYTHING", false);
6845 gcc_assert (var_storedanything
->id
== storedanything_id
);
6846 var_storedanything
->is_artificial_var
= 1;
6847 var_storedanything
->offset
= 0;
6848 var_storedanything
->size
= ~0;
6849 var_storedanything
->fullsize
= ~0;
6850 var_storedanything
->is_special_var
= 0;
6852 /* Create the INTEGER variable, used to represent that a variable points
6853 to what an INTEGER "points to". */
6854 var_integer
= new_var_info (NULL_TREE
, "INTEGER", false);
6855 gcc_assert (var_integer
->id
== integer_id
);
6856 var_integer
->is_artificial_var
= 1;
6857 var_integer
->size
= ~0;
6858 var_integer
->fullsize
= ~0;
6859 var_integer
->offset
= 0;
6860 var_integer
->is_special_var
= 1;
6862 /* INTEGER = ANYTHING, because we don't know where a dereference of
6863 a random integer will point to. */
6865 lhs
.var
= integer_id
;
6867 rhs
.type
= ADDRESSOF
;
6868 rhs
.var
= anything_id
;
6870 process_constraint (new_constraint (lhs
, rhs
));
6873 /* Initialize things necessary to perform PTA */
6876 init_alias_vars (void)
6878 use_field_sensitive
= (MAX_FIELDS_FOR_FIELD_SENSITIVE
> 1);
6880 bitmap_obstack_initialize (&pta_obstack
);
6881 bitmap_obstack_initialize (&oldpta_obstack
);
6882 bitmap_obstack_initialize (&predbitmap_obstack
);
6884 constraints
.create (8);
6886 vi_for_tree
= new hash_map
<tree
, varinfo_t
>;
6887 call_stmt_vars
= new hash_map
<gimple
*, varinfo_t
>;
6889 memset (&stats
, 0, sizeof (stats
));
6890 shared_bitmap_table
= new hash_table
<shared_bitmap_hasher
> (511);
6893 gcc_obstack_init (&fake_var_decl_obstack
);
6895 final_solutions
= new hash_map
<varinfo_t
, pt_solution
*>;
6896 gcc_obstack_init (&final_solutions_obstack
);
6899 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6900 predecessor edges. */
6903 remove_preds_and_fake_succs (constraint_graph_t graph
)
6907 /* Clear the implicit ref and address nodes from the successor
6909 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
6911 if (graph
->succs
[i
])
6912 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
6913 FIRST_REF_NODE
* 2);
6916 /* Free the successor list for the non-ref nodes. */
6917 for (i
= FIRST_REF_NODE
+ 1; i
< graph
->size
; i
++)
6919 if (graph
->succs
[i
])
6920 BITMAP_FREE (graph
->succs
[i
]);
6923 /* Now reallocate the size of the successor list as, and blow away
6924 the predecessor bitmaps. */
6925 graph
->size
= varmap
.length ();
6926 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
6928 free (graph
->implicit_preds
);
6929 graph
->implicit_preds
= NULL
;
6930 free (graph
->preds
);
6931 graph
->preds
= NULL
;
6932 bitmap_obstack_release (&predbitmap_obstack
);
6935 /* Solve the constraint set. */
6938 solve_constraints (void)
6940 struct scc_info
*si
;
6944 "\nCollapsing static cycles and doing variable "
6947 init_graph (varmap
.length () * 2);
6950 fprintf (dump_file
, "Building predecessor graph\n");
6951 build_pred_graph ();
6954 fprintf (dump_file
, "Detecting pointer and location "
6956 si
= perform_var_substitution (graph
);
6959 fprintf (dump_file
, "Rewriting constraints and unifying "
6961 rewrite_constraints (graph
, si
);
6963 build_succ_graph ();
6965 free_var_substitution_info (si
);
6967 /* Attach complex constraints to graph nodes. */
6968 move_complex_constraints (graph
);
6971 fprintf (dump_file
, "Uniting pointer but not location equivalent "
6973 unite_pointer_equivalences (graph
);
6976 fprintf (dump_file
, "Finding indirect cycles\n");
6977 find_indirect_cycles (graph
);
6979 /* Implicit nodes and predecessors are no longer necessary at this
6981 remove_preds_and_fake_succs (graph
);
6983 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
6985 fprintf (dump_file
, "\n\n// The constraint graph before solve-graph "
6986 "in dot format:\n");
6987 dump_constraint_graph (dump_file
);
6988 fprintf (dump_file
, "\n\n");
6992 fprintf (dump_file
, "Solving graph\n");
6994 solve_graph (graph
);
6996 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
6998 fprintf (dump_file
, "\n\n// The constraint graph after solve-graph "
6999 "in dot format:\n");
7000 dump_constraint_graph (dump_file
);
7001 fprintf (dump_file
, "\n\n");
7005 dump_sa_points_to_info (dump_file
);
7008 /* Create points-to sets for the current function. See the comments
7009 at the start of the file for an algorithmic overview. */
7012 compute_points_to_sets (void)
7018 timevar_push (TV_TREE_PTA
);
7022 intra_create_variable_infos (cfun
);
7024 /* Now walk all statements and build the constraint set. */
7025 FOR_EACH_BB_FN (bb
, cfun
)
7027 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7030 gphi
*phi
= gsi
.phi ();
7032 if (! virtual_operand_p (gimple_phi_result (phi
)))
7033 find_func_aliases (cfun
, phi
);
7036 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
7039 gimple
*stmt
= gsi_stmt (gsi
);
7041 find_func_aliases (cfun
, stmt
);
7047 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
7048 dump_constraints (dump_file
, 0);
7051 /* From the constraints compute the points-to sets. */
7052 solve_constraints ();
7054 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
7055 cfun
->gimple_df
->escaped
= find_what_var_points_to (cfun
->decl
,
7056 get_varinfo (escaped_id
));
7058 /* Make sure the ESCAPED solution (which is used as placeholder in
7059 other solutions) does not reference itself. This simplifies
7060 points-to solution queries. */
7061 cfun
->gimple_df
->escaped
.escaped
= 0;
7063 /* Compute the points-to sets for pointer SSA_NAMEs. */
7064 for (i
= 0; i
< num_ssa_names
; ++i
)
7066 tree ptr
= ssa_name (i
);
7068 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
7069 find_what_p_points_to (cfun
->decl
, ptr
);
7072 /* Compute the call-used/clobbered sets. */
7073 FOR_EACH_BB_FN (bb
, cfun
)
7075 gimple_stmt_iterator gsi
;
7077 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7080 struct pt_solution
*pt
;
7082 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
7086 pt
= gimple_call_use_set (stmt
);
7087 if (gimple_call_flags (stmt
) & ECF_CONST
)
7088 memset (pt
, 0, sizeof (struct pt_solution
));
7089 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
7091 *pt
= find_what_var_points_to (cfun
->decl
, vi
);
7092 /* Escaped (and thus nonlocal) variables are always
7093 implicitly used by calls. */
7094 /* ??? ESCAPED can be empty even though NONLOCAL
7101 /* If there is nothing special about this call then
7102 we have made everything that is used also escape. */
7103 *pt
= cfun
->gimple_df
->escaped
;
7107 pt
= gimple_call_clobber_set (stmt
);
7108 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
7109 memset (pt
, 0, sizeof (struct pt_solution
));
7110 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
7112 *pt
= find_what_var_points_to (cfun
->decl
, vi
);
7113 /* Escaped (and thus nonlocal) variables are always
7114 implicitly clobbered by calls. */
7115 /* ??? ESCAPED can be empty even though NONLOCAL
7122 /* If there is nothing special about this call then
7123 we have made everything that is used also escape. */
7124 *pt
= cfun
->gimple_df
->escaped
;
7130 timevar_pop (TV_TREE_PTA
);
7134 /* Delete created points-to sets. */
7137 delete_points_to_sets (void)
7141 delete shared_bitmap_table
;
7142 shared_bitmap_table
= NULL
;
7143 if (dump_file
&& (dump_flags
& TDF_STATS
))
7144 fprintf (dump_file
, "Points to sets created:%d\n",
7145 stats
.points_to_sets_created
);
7148 delete call_stmt_vars
;
7149 bitmap_obstack_release (&pta_obstack
);
7150 constraints
.release ();
7152 for (i
= 0; i
< graph
->size
; i
++)
7153 graph
->complex[i
].release ();
7154 free (graph
->complex);
7157 free (graph
->succs
);
7159 free (graph
->pe_rep
);
7160 free (graph
->indirect_cycles
);
7164 variable_info_pool
.release ();
7165 constraint_pool
.release ();
7167 obstack_free (&fake_var_decl_obstack
, NULL
);
7169 delete final_solutions
;
7170 obstack_free (&final_solutions_obstack
, NULL
);
7173 /* Mark "other" loads and stores as belonging to CLIQUE and with
7177 visit_loadstore (gimple
*, tree base
, tree ref
, void *clique_
)
7179 unsigned short clique
= (uintptr_t)clique_
;
7180 if (TREE_CODE (base
) == MEM_REF
7181 || TREE_CODE (base
) == TARGET_MEM_REF
)
7183 tree ptr
= TREE_OPERAND (base
, 0);
7184 if (TREE_CODE (ptr
) == SSA_NAME
7185 && ! SSA_NAME_IS_DEFAULT_DEF (ptr
))
7187 /* ??? We need to make sure 'ptr' doesn't include any of
7188 the restrict tags we added bases for in its points-to set. */
7192 /* For now let decls through. */
7194 /* Do not overwrite existing cliques (that includes clique, base
7195 pairs we just set). */
7196 if (MR_DEPENDENCE_CLIQUE (base
) == 0)
7198 MR_DEPENDENCE_CLIQUE (base
) = clique
;
7199 MR_DEPENDENCE_BASE (base
) = 0;
7203 /* For plain decl accesses see whether they are accesses to globals
7204 and rewrite them to MEM_REFs with { clique, 0 }. */
7205 if (TREE_CODE (base
) == VAR_DECL
7206 && is_global_var (base
)
7207 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
7212 while (handled_component_p (*basep
))
7213 basep
= &TREE_OPERAND (*basep
, 0);
7214 gcc_assert (TREE_CODE (*basep
) == VAR_DECL
);
7215 tree ptr
= build_fold_addr_expr (*basep
);
7216 tree zero
= build_int_cst (TREE_TYPE (ptr
), 0);
7217 *basep
= build2 (MEM_REF
, TREE_TYPE (*basep
), ptr
, zero
);
7218 MR_DEPENDENCE_CLIQUE (*basep
) = clique
;
7219 MR_DEPENDENCE_BASE (*basep
) = 0;
7225 /* If REF is a MEM_REF then assign a clique, base pair to it, updating
7226 CLIQUE, *RESTRICT_VAR and LAST_RUID. Return whether dependence info
7227 was assigned to REF. */
7230 maybe_set_dependence_info (tree ref
, tree ptr
,
7231 unsigned short &clique
, varinfo_t restrict_var
,
7232 unsigned short &last_ruid
)
7234 while (handled_component_p (ref
))
7235 ref
= TREE_OPERAND (ref
, 0);
7236 if ((TREE_CODE (ref
) == MEM_REF
7237 || TREE_CODE (ref
) == TARGET_MEM_REF
)
7238 && TREE_OPERAND (ref
, 0) == ptr
)
7240 /* Do not overwrite existing cliques. This avoids overwriting dependence
7241 info inlined from a function with restrict parameters inlined
7242 into a function with restrict parameters. This usually means we
7243 prefer to be precise in innermost loops. */
7244 if (MR_DEPENDENCE_CLIQUE (ref
) == 0)
7247 clique
= ++cfun
->last_clique
;
7248 if (restrict_var
->ruid
== 0)
7249 restrict_var
->ruid
= ++last_ruid
;
7250 MR_DEPENDENCE_CLIQUE (ref
) = clique
;
7251 MR_DEPENDENCE_BASE (ref
) = restrict_var
->ruid
;
7258 /* Compute the set of independend memory references based on restrict
7259 tags and their conservative propagation to the points-to sets. */
7262 compute_dependence_clique (void)
7264 unsigned short clique
= 0;
7265 unsigned short last_ruid
= 0;
7266 for (unsigned i
= 0; i
< num_ssa_names
; ++i
)
7268 tree ptr
= ssa_name (i
);
7269 if (!ptr
|| !POINTER_TYPE_P (TREE_TYPE (ptr
)))
7272 /* Avoid all this when ptr is not dereferenced? */
7274 if (SSA_NAME_IS_DEFAULT_DEF (ptr
)
7275 && (TREE_CODE (SSA_NAME_VAR (ptr
)) == PARM_DECL
7276 || TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
))
7277 p
= SSA_NAME_VAR (ptr
);
7278 varinfo_t vi
= lookup_vi_for_tree (p
);
7281 vi
= get_varinfo (find (vi
->id
));
7284 varinfo_t restrict_var
= NULL
;
7285 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, j
, bi
)
7287 varinfo_t oi
= get_varinfo (j
);
7288 if (oi
->is_restrict_var
)
7292 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7294 fprintf (dump_file
, "found restrict pointed-to "
7296 print_generic_expr (dump_file
, ptr
, 0);
7297 fprintf (dump_file
, " but not exclusively\n");
7299 restrict_var
= NULL
;
7304 /* NULL is the only other valid points-to entry. */
7305 else if (oi
->id
!= nothing_id
)
7307 restrict_var
= NULL
;
7311 /* Ok, found that ptr must(!) point to a single(!) restrict
7313 /* ??? PTA isn't really a proper propagation engine to compute
7315 ??? We could handle merging of two restricts by unifying them. */
7318 /* Now look at possible dereferences of ptr. */
7319 imm_use_iterator ui
;
7321 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, ptr
)
7323 /* ??? Calls and asms. */
7324 if (!gimple_assign_single_p (use_stmt
))
7326 maybe_set_dependence_info (gimple_assign_lhs (use_stmt
), ptr
,
7327 clique
, restrict_var
, last_ruid
);
7328 maybe_set_dependence_info (gimple_assign_rhs1 (use_stmt
), ptr
,
7329 clique
, restrict_var
, last_ruid
);
7337 /* Assign the BASE id zero to all accesses not based on a restrict
7338 pointer. That way they get disabiguated against restrict
7339 accesses but not against each other. */
7340 /* ??? For restricts derived from globals (thus not incoming
7341 parameters) we can't restrict scoping properly thus the following
7342 is too aggressive there. For now we have excluded those globals from
7343 getting into the MR_DEPENDENCE machinery. */
7345 FOR_EACH_BB_FN (bb
, cfun
)
7346 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
7347 !gsi_end_p (gsi
); gsi_next (&gsi
))
7349 gimple
*stmt
= gsi_stmt (gsi
);
7350 walk_stmt_load_store_ops (stmt
, (void *)(uintptr_t)clique
,
7351 visit_loadstore
, visit_loadstore
);
7355 /* Compute points-to information for every SSA_NAME pointer in the
7356 current function and compute the transitive closure of escaped
7357 variables to re-initialize the call-clobber states of local variables. */
7360 compute_may_aliases (void)
7362 if (cfun
->gimple_df
->ipa_pta
)
7366 fprintf (dump_file
, "\nNot re-computing points-to information "
7367 "because IPA points-to information is available.\n\n");
7369 /* But still dump what we have remaining it. */
7370 dump_alias_info (dump_file
);
7376 /* For each pointer P_i, determine the sets of variables that P_i may
7377 point-to. Compute the reachability set of escaped and call-used
7379 compute_points_to_sets ();
7381 /* Debugging dumps. */
7383 dump_alias_info (dump_file
);
7385 /* Compute restrict-based memory disambiguations. */
7386 compute_dependence_clique ();
7388 /* Deallocate memory used by aliasing data structures and the internal
7389 points-to solution. */
7390 delete_points_to_sets ();
7392 gcc_assert (!need_ssa_update_p (cfun
));
7397 /* A dummy pass to cause points-to information to be computed via
7398 TODO_rebuild_alias. */
7402 const pass_data pass_data_build_alias
=
7404 GIMPLE_PASS
, /* type */
7406 OPTGROUP_NONE
, /* optinfo_flags */
7407 TV_NONE
, /* tv_id */
7408 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7409 0, /* properties_provided */
7410 0, /* properties_destroyed */
7411 0, /* todo_flags_start */
7412 TODO_rebuild_alias
, /* todo_flags_finish */
7415 class pass_build_alias
: public gimple_opt_pass
7418 pass_build_alias (gcc::context
*ctxt
)
7419 : gimple_opt_pass (pass_data_build_alias
, ctxt
)
7422 /* opt_pass methods: */
7423 virtual bool gate (function
*) { return flag_tree_pta
; }
7425 }; // class pass_build_alias
7430 make_pass_build_alias (gcc::context
*ctxt
)
7432 return new pass_build_alias (ctxt
);
7435 /* A dummy pass to cause points-to information to be computed via
7436 TODO_rebuild_alias. */
7440 const pass_data pass_data_build_ealias
=
7442 GIMPLE_PASS
, /* type */
7443 "ealias", /* name */
7444 OPTGROUP_NONE
, /* optinfo_flags */
7445 TV_NONE
, /* tv_id */
7446 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7447 0, /* properties_provided */
7448 0, /* properties_destroyed */
7449 0, /* todo_flags_start */
7450 TODO_rebuild_alias
, /* todo_flags_finish */
7453 class pass_build_ealias
: public gimple_opt_pass
7456 pass_build_ealias (gcc::context
*ctxt
)
7457 : gimple_opt_pass (pass_data_build_ealias
, ctxt
)
7460 /* opt_pass methods: */
7461 virtual bool gate (function
*) { return flag_tree_pta
; }
7463 }; // class pass_build_ealias
7468 make_pass_build_ealias (gcc::context
*ctxt
)
7470 return new pass_build_ealias (ctxt
);
7474 /* IPA PTA solutions for ESCAPED. */
7475 struct pt_solution ipa_escaped_pt
7476 = { true, false, false, false, false, false, false, false, NULL
};
7478 /* Associate node with varinfo DATA. Worker for
7479 cgraph_for_node_and_aliases. */
7481 associate_varinfo_to_alias (struct cgraph_node
*node
, void *data
)
7483 if ((node
->alias
|| node
->thunk
.thunk_p
)
7485 insert_vi_for_tree (node
->decl
, (varinfo_t
)data
);
7489 /* Execute the driver for IPA PTA. */
7491 ipa_pta_execute (void)
7493 struct cgraph_node
*node
;
7495 unsigned int from
= 0;
7501 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7503 symtab_node::dump_table (dump_file
);
7504 fprintf (dump_file
, "\n");
7509 fprintf (dump_file
, "Generating generic constraints\n\n");
7510 dump_constraints (dump_file
, from
);
7511 fprintf (dump_file
, "\n");
7512 from
= constraints
.length ();
7515 /* Build the constraints. */
7516 FOR_EACH_DEFINED_FUNCTION (node
)
7519 /* Nodes without a body are not interesting. Especially do not
7520 visit clones at this point for now - we get duplicate decls
7521 there for inline clones at least. */
7522 if (!node
->has_gimple_body_p () || node
->global
.inlined_to
)
7526 gcc_assert (!node
->clone_of
);
7528 /* When parallelizing a code region, we split the region off into a
7529 separate function, to be run by several threads in parallel. So for a
7530 function foo, we split off a region into a function
7531 foo._0 (void *foodata), and replace the region with some variant of a
7532 function call run_on_threads (&foo._0, data). The '&foo._0' sets the
7533 address_taken bit for function foo._0, which would make it non-local.
7534 But for the purpose of ipa-pta, we can regard the run_on_threads call
7535 as a local call foo._0 (data), so we ignore address_taken on nodes
7536 with parallelized_function set.
7537 Note: this is only safe, if foo and foo._0 are in the same lto
7539 bool node_address_taken
= ((node
->parallelized_function
7540 && !node
->used_from_other_partition
)
7542 : node
->address_taken
);
7544 /* For externally visible or attribute used annotated functions use
7545 local constraints for their arguments.
7546 For local functions we see all callers and thus do not need initial
7547 constraints for parameters. */
7548 bool nonlocal_p
= (node
->used_from_other_partition
7549 || node
->externally_visible
7550 || node
->force_output
7551 || node_address_taken
);
7553 vi
= create_function_info_for (node
->decl
,
7554 alias_get_name (node
->decl
), false,
7557 && from
!= constraints
.length ())
7560 "Generating intial constraints for %s", node
->name ());
7561 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
7562 fprintf (dump_file
, " (%s)",
7564 (DECL_ASSEMBLER_NAME (node
->decl
)));
7565 fprintf (dump_file
, "\n\n");
7566 dump_constraints (dump_file
, from
);
7567 fprintf (dump_file
, "\n");
7569 from
= constraints
.length ();
7572 node
->call_for_symbol_thunks_and_aliases
7573 (associate_varinfo_to_alias
, vi
, true);
7576 /* Create constraints for global variables and their initializers. */
7577 FOR_EACH_VARIABLE (var
)
7579 if (var
->alias
&& var
->analyzed
)
7582 varinfo_t vi
= get_vi_for_tree (var
->decl
);
7584 /* For the purpose of IPA PTA unit-local globals are not
7586 bool nonlocal_p
= (var
->used_from_other_partition
7587 || var
->externally_visible
7588 || var
->force_output
);
7590 vi
->is_ipa_escape_point
= true;
7594 && from
!= constraints
.length ())
7597 "Generating constraints for global initializers\n\n");
7598 dump_constraints (dump_file
, from
);
7599 fprintf (dump_file
, "\n");
7600 from
= constraints
.length ();
7603 FOR_EACH_DEFINED_FUNCTION (node
)
7605 struct function
*func
;
7608 /* Nodes without a body are not interesting. */
7609 if (!node
->has_gimple_body_p () || node
->clone_of
)
7615 "Generating constraints for %s", node
->name ());
7616 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
7617 fprintf (dump_file
, " (%s)",
7619 (DECL_ASSEMBLER_NAME (node
->decl
)));
7620 fprintf (dump_file
, "\n");
7623 func
= DECL_STRUCT_FUNCTION (node
->decl
);
7624 gcc_assert (cfun
== NULL
);
7626 /* Build constriants for the function body. */
7627 FOR_EACH_BB_FN (bb
, func
)
7629 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7632 gphi
*phi
= gsi
.phi ();
7634 if (! virtual_operand_p (gimple_phi_result (phi
)))
7635 find_func_aliases (func
, phi
);
7638 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
7641 gimple
*stmt
= gsi_stmt (gsi
);
7643 find_func_aliases (func
, stmt
);
7644 find_func_clobbers (func
, stmt
);
7650 fprintf (dump_file
, "\n");
7651 dump_constraints (dump_file
, from
);
7652 fprintf (dump_file
, "\n");
7653 from
= constraints
.length ();
7657 /* From the constraints compute the points-to sets. */
7658 solve_constraints ();
7660 /* Compute the global points-to sets for ESCAPED.
7661 ??? Note that the computed escape set is not correct
7662 for the whole unit as we fail to consider graph edges to
7663 externally visible functions. */
7664 ipa_escaped_pt
= find_what_var_points_to (NULL
, get_varinfo (escaped_id
));
7666 /* Make sure the ESCAPED solution (which is used as placeholder in
7667 other solutions) does not reference itself. This simplifies
7668 points-to solution queries. */
7669 ipa_escaped_pt
.ipa_escaped
= 0;
7671 /* Assign the points-to sets to the SSA names in the unit. */
7672 FOR_EACH_DEFINED_FUNCTION (node
)
7675 struct function
*fn
;
7679 /* Nodes without a body are not interesting. */
7680 if (!node
->has_gimple_body_p () || node
->clone_of
)
7683 fn
= DECL_STRUCT_FUNCTION (node
->decl
);
7685 /* Compute the points-to sets for pointer SSA_NAMEs. */
7686 FOR_EACH_VEC_ELT (*fn
->gimple_df
->ssa_names
, i
, ptr
)
7689 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
7690 find_what_p_points_to (node
->decl
, ptr
);
7693 /* Compute the call-use and call-clobber sets for indirect calls
7694 and calls to external functions. */
7695 FOR_EACH_BB_FN (bb
, fn
)
7697 gimple_stmt_iterator gsi
;
7699 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7702 struct pt_solution
*pt
;
7706 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
7710 /* Handle direct calls to functions with body. */
7711 decl
= gimple_call_fndecl (stmt
);
7714 tree called_decl
= NULL_TREE
;
7715 if (gimple_call_builtin_p (stmt
, BUILT_IN_GOMP_PARALLEL
))
7716 called_decl
= TREE_OPERAND (gimple_call_arg (stmt
, 0), 0);
7717 else if (gimple_call_builtin_p (stmt
, BUILT_IN_GOACC_PARALLEL
))
7718 called_decl
= TREE_OPERAND (gimple_call_arg (stmt
, 1), 0);
7720 if (called_decl
!= NULL_TREE
7721 && !fndecl_maybe_in_other_partition (called_decl
))
7726 && (fi
= lookup_vi_for_tree (decl
))
7729 *gimple_call_clobber_set (stmt
)
7730 = find_what_var_points_to
7731 (node
->decl
, first_vi_for_offset (fi
, fi_clobbers
));
7732 *gimple_call_use_set (stmt
)
7733 = find_what_var_points_to
7734 (node
->decl
, first_vi_for_offset (fi
, fi_uses
));
7736 /* Handle direct calls to external functions. */
7739 pt
= gimple_call_use_set (stmt
);
7740 if (gimple_call_flags (stmt
) & ECF_CONST
)
7741 memset (pt
, 0, sizeof (struct pt_solution
));
7742 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
7744 *pt
= find_what_var_points_to (node
->decl
, vi
);
7745 /* Escaped (and thus nonlocal) variables are always
7746 implicitly used by calls. */
7747 /* ??? ESCAPED can be empty even though NONLOCAL
7750 pt
->ipa_escaped
= 1;
7754 /* If there is nothing special about this call then
7755 we have made everything that is used also escape. */
7756 *pt
= ipa_escaped_pt
;
7760 pt
= gimple_call_clobber_set (stmt
);
7761 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
7762 memset (pt
, 0, sizeof (struct pt_solution
));
7763 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
7765 *pt
= find_what_var_points_to (node
->decl
, vi
);
7766 /* Escaped (and thus nonlocal) variables are always
7767 implicitly clobbered by calls. */
7768 /* ??? ESCAPED can be empty even though NONLOCAL
7771 pt
->ipa_escaped
= 1;
7775 /* If there is nothing special about this call then
7776 we have made everything that is used also escape. */
7777 *pt
= ipa_escaped_pt
;
7781 /* Handle indirect calls. */
7783 && (fi
= get_fi_for_callee (stmt
)))
7785 /* We need to accumulate all clobbers/uses of all possible
7787 fi
= get_varinfo (find (fi
->id
));
7788 /* If we cannot constrain the set of functions we'll end up
7789 calling we end up using/clobbering everything. */
7790 if (bitmap_bit_p (fi
->solution
, anything_id
)
7791 || bitmap_bit_p (fi
->solution
, nonlocal_id
)
7792 || bitmap_bit_p (fi
->solution
, escaped_id
))
7794 pt_solution_reset (gimple_call_clobber_set (stmt
));
7795 pt_solution_reset (gimple_call_use_set (stmt
));
7801 struct pt_solution
*uses
, *clobbers
;
7803 uses
= gimple_call_use_set (stmt
);
7804 clobbers
= gimple_call_clobber_set (stmt
);
7805 memset (uses
, 0, sizeof (struct pt_solution
));
7806 memset (clobbers
, 0, sizeof (struct pt_solution
));
7807 EXECUTE_IF_SET_IN_BITMAP (fi
->solution
, 0, i
, bi
)
7809 struct pt_solution sol
;
7811 vi
= get_varinfo (i
);
7812 if (!vi
->is_fn_info
)
7814 /* ??? We could be more precise here? */
7816 uses
->ipa_escaped
= 1;
7817 clobbers
->nonlocal
= 1;
7818 clobbers
->ipa_escaped
= 1;
7822 if (!uses
->anything
)
7824 sol
= find_what_var_points_to
7826 first_vi_for_offset (vi
, fi_uses
));
7827 pt_solution_ior_into (uses
, &sol
);
7829 if (!clobbers
->anything
)
7831 sol
= find_what_var_points_to
7833 first_vi_for_offset (vi
, fi_clobbers
));
7834 pt_solution_ior_into (clobbers
, &sol
);
7842 fn
->gimple_df
->ipa_pta
= true;
7844 /* We have to re-set the final-solution cache after each function
7845 because what is a "global" is dependent on function context. */
7846 final_solutions
->empty ();
7847 obstack_free (&final_solutions_obstack
, NULL
);
7848 gcc_obstack_init (&final_solutions_obstack
);
7851 delete_points_to_sets ();
7860 const pass_data pass_data_ipa_pta
=
7862 SIMPLE_IPA_PASS
, /* type */
7864 OPTGROUP_NONE
, /* optinfo_flags */
7865 TV_IPA_PTA
, /* tv_id */
7866 0, /* properties_required */
7867 0, /* properties_provided */
7868 0, /* properties_destroyed */
7869 0, /* todo_flags_start */
7870 0, /* todo_flags_finish */
7873 class pass_ipa_pta
: public simple_ipa_opt_pass
7876 pass_ipa_pta (gcc::context
*ctxt
)
7877 : simple_ipa_opt_pass (pass_data_ipa_pta
, ctxt
)
7880 /* opt_pass methods: */
7881 virtual bool gate (function
*)
7885 /* Don't bother doing anything if the program has errors. */
7889 opt_pass
* clone () { return new pass_ipa_pta (m_ctxt
); }
7891 virtual unsigned int execute (function
*) { return ipa_pta_execute (); }
7893 }; // class pass_ipa_pta
7897 simple_ipa_opt_pass
*
7898 make_pass_ipa_pta (gcc::context
*ctxt
)
7900 return new pass_ipa_pta (ctxt
);