1 /* Tree based points-to analysis
2 Copyright (C) 2005-2015 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
34 #include "hard-reg-set.h"
37 #include "dominance.h"
39 #include "basic-block.h"
40 #include "double-int.h"
46 #include "fold-const.h"
47 #include "stor-layout.h"
49 #include "hash-table.h"
50 #include "tree-ssa-alias.h"
51 #include "internal-fn.h"
52 #include "gimple-expr.h"
55 #include "gimple-iterator.h"
56 #include "gimple-ssa.h"
58 #include "plugin-api.h"
61 #include "stringpool.h"
62 #include "tree-ssanames.h"
63 #include "tree-into-ssa.h"
65 #include "statistics.h"
67 #include "fixed-value.h"
68 #include "insn-config.h"
77 #include "tree-inline.h"
78 #include "diagnostic-core.h"
79 #include "tree-pass.h"
80 #include "alloc-pool.h"
81 #include "splay-tree.h"
83 #include "tree-phinodes.h"
84 #include "ssa-iterators.h"
85 #include "tree-pretty-print.h"
86 #include "gimple-walk.h"
88 /* The idea behind this analyzer is to generate set constraints from the
89 program, then solve the resulting constraints in order to generate the
92 Set constraints are a way of modeling program analysis problems that
93 involve sets. They consist of an inclusion constraint language,
94 describing the variables (each variable is a set) and operations that
95 are involved on the variables, and a set of rules that derive facts
96 from these operations. To solve a system of set constraints, you derive
97 all possible facts under the rules, which gives you the correct sets
100 See "Efficient Field-sensitive pointer analysis for C" by "David
101 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
102 http://citeseer.ist.psu.edu/pearce04efficient.html
104 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
105 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
106 http://citeseer.ist.psu.edu/heintze01ultrafast.html
108 There are three types of real constraint expressions, DEREF,
109 ADDRESSOF, and SCALAR. Each constraint expression consists
110 of a constraint type, a variable, and an offset.
112 SCALAR is a constraint expression type used to represent x, whether
113 it appears on the LHS or the RHS of a statement.
114 DEREF is a constraint expression type used to represent *x, whether
115 it appears on the LHS or the RHS of a statement.
116 ADDRESSOF is a constraint expression used to represent &x, whether
117 it appears on the LHS or the RHS of a statement.
119 Each pointer variable in the program is assigned an integer id, and
120 each field of a structure variable is assigned an integer id as well.
122 Structure variables are linked to their list of fields through a "next
123 field" in each variable that points to the next field in offset
125 Each variable for a structure field has
127 1. "size", that tells the size in bits of that field.
128 2. "fullsize, that tells the size in bits of the entire structure.
129 3. "offset", that tells the offset in bits from the beginning of the
130 structure to this field.
142 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
143 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
144 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
147 In order to solve the system of set constraints, the following is
150 1. Each constraint variable x has a solution set associated with it,
153 2. Constraints are separated into direct, copy, and complex.
154 Direct constraints are ADDRESSOF constraints that require no extra
155 processing, such as P = &Q
156 Copy constraints are those of the form P = Q.
157 Complex constraints are all the constraints involving dereferences
158 and offsets (including offsetted copies).
160 3. All direct constraints of the form P = &Q are processed, such
161 that Q is added to Sol(P)
163 4. All complex constraints for a given constraint variable are stored in a
164 linked list attached to that variable's node.
166 5. A directed graph is built out of the copy constraints. Each
167 constraint variable is a node in the graph, and an edge from
168 Q to P is added for each copy constraint of the form P = Q
170 6. The graph is then walked, and solution sets are
171 propagated along the copy edges, such that an edge from Q to P
172 causes Sol(P) <- Sol(P) union Sol(Q).
174 7. As we visit each node, all complex constraints associated with
175 that node are processed by adding appropriate copy edges to the graph, or the
176 appropriate variables to the solution set.
178 8. The process of walking the graph is iterated until no solution
181 Prior to walking the graph in steps 6 and 7, We perform static
182 cycle elimination on the constraint graph, as well
183 as off-line variable substitution.
185 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
186 on and turned into anything), but isn't. You can just see what offset
187 inside the pointed-to struct it's going to access.
189 TODO: Constant bounded arrays can be handled as if they were structs of the
190 same number of elements.
192 TODO: Modeling heap and incoming pointers becomes much better if we
193 add fields to them as we discover them, which we could do.
195 TODO: We could handle unions, but to be honest, it's probably not
196 worth the pain or slowdown. */
198 /* IPA-PTA optimizations possible.
200 When the indirect function called is ANYTHING we can add disambiguation
201 based on the function signatures (or simply the parameter count which
202 is the varinfo size). We also do not need to consider functions that
203 do not have their address taken.
205 The is_global_var bit which marks escape points is overly conservative
206 in IPA mode. Split it to is_escape_point and is_global_var - only
207 externally visible globals are escape points in IPA mode. This is
208 also needed to fix the pt_solution_includes_global predicate
209 (and thus ptr_deref_may_alias_global_p).
211 The way we introduce DECL_PT_UID to avoid fixing up all points-to
212 sets in the translation unit when we copy a DECL during inlining
213 pessimizes precision. The advantage is that the DECL_PT_UID keeps
214 compile-time and memory usage overhead low - the points-to sets
215 do not grow or get unshared as they would during a fixup phase.
216 An alternative solution is to delay IPA PTA until after all
217 inlining transformations have been applied.
219 The way we propagate clobber/use information isn't optimized.
220 It should use a new complex constraint that properly filters
221 out local variables of the callee (though that would make
222 the sets invalid after inlining). OTOH we might as well
223 admit defeat to WHOPR and simply do all the clobber/use analysis
224 and propagation after PTA finished but before we threw away
225 points-to information for memory variables. WHOPR and PTA
226 do not play along well anyway - the whole constraint solving
227 would need to be done in WPA phase and it will be very interesting
228 to apply the results to local SSA names during LTRANS phase.
230 We probably should compute a per-function unit-ESCAPE solution
231 propagating it simply like the clobber / uses solutions. The
232 solution can go alongside the non-IPA espaced solution and be
233 used to query which vars escape the unit through a function.
235 We never put function decls in points-to sets so we do not
236 keep the set of called functions for indirect calls.
238 And probably more. */
240 static bool use_field_sensitive
= true;
241 static int in_ipa_mode
= 0;
243 /* Used for predecessor bitmaps. */
244 static bitmap_obstack predbitmap_obstack
;
246 /* Used for points-to sets. */
247 static bitmap_obstack pta_obstack
;
249 /* Used for oldsolution members of variables. */
250 static bitmap_obstack oldpta_obstack
;
252 /* Used for per-solver-iteration bitmaps. */
253 static bitmap_obstack iteration_obstack
;
255 static unsigned int create_variable_info_for (tree
, const char *);
256 typedef struct constraint_graph
*constraint_graph_t
;
257 static void unify_nodes (constraint_graph_t
, unsigned int, unsigned int, bool);
260 typedef struct constraint
*constraint_t
;
263 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
265 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
267 static struct constraint_stats
269 unsigned int total_vars
;
270 unsigned int nonpointer_vars
;
271 unsigned int unified_vars_static
;
272 unsigned int unified_vars_dynamic
;
273 unsigned int iterations
;
274 unsigned int num_edges
;
275 unsigned int num_implicit_edges
;
276 unsigned int points_to_sets_created
;
281 /* ID of this variable */
284 /* True if this is a variable created by the constraint analysis, such as
285 heap variables and constraints we had to break up. */
286 unsigned int is_artificial_var
: 1;
288 /* True if this is a special variable whose solution set should not be
290 unsigned int is_special_var
: 1;
292 /* True for variables whose size is not known or variable. */
293 unsigned int is_unknown_size_var
: 1;
295 /* True for (sub-)fields that represent a whole variable. */
296 unsigned int is_full_var
: 1;
298 /* True if this is a heap variable. */
299 unsigned int is_heap_var
: 1;
301 /* True if this field may contain pointers. */
302 unsigned int may_have_pointers
: 1;
304 /* True if this field has only restrict qualified pointers. */
305 unsigned int only_restrict_pointers
: 1;
307 /* True if this represents a heap var created for a restrict qualified
309 unsigned int is_restrict_var
: 1;
311 /* True if this represents a global variable. */
312 unsigned int is_global_var
: 1;
314 /* True if this represents a IPA function info. */
315 unsigned int is_fn_info
: 1;
317 /* ??? Store somewhere better. */
320 /* The ID of the variable for the next field in this structure
321 or zero for the last field in this structure. */
324 /* The ID of the variable for the first field in this structure. */
327 /* Offset of this variable, in bits, from the base variable */
328 unsigned HOST_WIDE_INT offset
;
330 /* Size of the variable, in bits. */
331 unsigned HOST_WIDE_INT size
;
333 /* Full size of the base variable, in bits. */
334 unsigned HOST_WIDE_INT fullsize
;
336 /* Name of this variable */
339 /* Tree that this variable is associated with. */
342 /* Points-to set for this variable. */
345 /* Old points-to set for this variable. */
348 typedef struct variable_info
*varinfo_t
;
350 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
351 static varinfo_t
first_or_preceding_vi_for_offset (varinfo_t
,
352 unsigned HOST_WIDE_INT
);
353 static varinfo_t
lookup_vi_for_tree (tree
);
354 static inline bool type_can_have_subvars (const_tree
);
356 /* Pool of variable info structures. */
357 static alloc_pool variable_info_pool
;
359 /* Map varinfo to final pt_solution. */
360 static hash_map
<varinfo_t
, pt_solution
*> *final_solutions
;
361 struct obstack final_solutions_obstack
;
363 /* Table of variable info structures for constraint variables.
364 Indexed directly by variable info id. */
365 static vec
<varinfo_t
> varmap
;
367 /* Return the varmap element N */
369 static inline varinfo_t
370 get_varinfo (unsigned int n
)
375 /* Return the next variable in the list of sub-variables of VI
376 or NULL if VI is the last sub-variable. */
378 static inline varinfo_t
379 vi_next (varinfo_t vi
)
381 return get_varinfo (vi
->next
);
384 /* Static IDs for the special variables. Variable ID zero is unused
385 and used as terminator for the sub-variable chain. */
386 enum { nothing_id
= 1, anything_id
= 2, string_id
= 3,
387 escaped_id
= 4, nonlocal_id
= 5,
388 storedanything_id
= 6, integer_id
= 7 };
390 /* Return a new variable info structure consisting for a variable
391 named NAME, and using constraint graph node NODE. Append it
392 to the vector of variable info structures. */
395 new_var_info (tree t
, const char *name
)
397 unsigned index
= varmap
.length ();
398 varinfo_t ret
= (varinfo_t
) pool_alloc (variable_info_pool
);
403 /* Vars without decl are artificial and do not have sub-variables. */
404 ret
->is_artificial_var
= (t
== NULL_TREE
);
405 ret
->is_special_var
= false;
406 ret
->is_unknown_size_var
= false;
407 ret
->is_full_var
= (t
== NULL_TREE
);
408 ret
->is_heap_var
= false;
409 ret
->may_have_pointers
= true;
410 ret
->only_restrict_pointers
= false;
411 ret
->is_restrict_var
= false;
413 ret
->is_global_var
= (t
== NULL_TREE
);
414 ret
->is_fn_info
= false;
416 ret
->is_global_var
= (is_global_var (t
)
417 /* We have to treat even local register variables
419 || (TREE_CODE (t
) == VAR_DECL
420 && DECL_HARD_REGISTER (t
)));
421 ret
->solution
= BITMAP_ALLOC (&pta_obstack
);
422 ret
->oldsolution
= NULL
;
428 varmap
.safe_push (ret
);
434 /* A map mapping call statements to per-stmt variables for uses
435 and clobbers specific to the call. */
436 static hash_map
<gimple
, varinfo_t
> *call_stmt_vars
;
438 /* Lookup or create the variable for the call statement CALL. */
441 get_call_vi (gcall
*call
)
446 varinfo_t
*slot_p
= &call_stmt_vars
->get_or_insert (call
, &existed
);
450 vi
= new_var_info (NULL_TREE
, "CALLUSED");
454 vi
->is_full_var
= true;
456 vi2
= new_var_info (NULL_TREE
, "CALLCLOBBERED");
460 vi2
->is_full_var
= true;
468 /* Lookup the variable for the call statement CALL representing
469 the uses. Returns NULL if there is nothing special about this call. */
472 lookup_call_use_vi (gcall
*call
)
474 varinfo_t
*slot_p
= call_stmt_vars
->get (call
);
481 /* Lookup the variable for the call statement CALL representing
482 the clobbers. Returns NULL if there is nothing special about this call. */
485 lookup_call_clobber_vi (gcall
*call
)
487 varinfo_t uses
= lookup_call_use_vi (call
);
491 return vi_next (uses
);
494 /* Lookup or create the variable for the call statement CALL representing
498 get_call_use_vi (gcall
*call
)
500 return get_call_vi (call
);
503 /* Lookup or create the variable for the call statement CALL representing
506 static varinfo_t ATTRIBUTE_UNUSED
507 get_call_clobber_vi (gcall
*call
)
509 return vi_next (get_call_vi (call
));
513 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
515 /* An expression that appears in a constraint. */
517 struct constraint_expr
519 /* Constraint type. */
520 constraint_expr_type type
;
522 /* Variable we are referring to in the constraint. */
525 /* Offset, in bits, of this constraint from the beginning of
526 variables it ends up referring to.
528 IOW, in a deref constraint, we would deref, get the result set,
529 then add OFFSET to each member. */
530 HOST_WIDE_INT offset
;
533 /* Use 0x8000... as special unknown offset. */
534 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
536 typedef struct constraint_expr ce_s
;
537 static void get_constraint_for_1 (tree
, vec
<ce_s
> *, bool, bool);
538 static void get_constraint_for (tree
, vec
<ce_s
> *);
539 static void get_constraint_for_rhs (tree
, vec
<ce_s
> *);
540 static void do_deref (vec
<ce_s
> *);
542 /* Our set constraints are made up of two constraint expressions, one
545 As described in the introduction, our set constraints each represent an
546 operation between set valued variables.
550 struct constraint_expr lhs
;
551 struct constraint_expr rhs
;
554 /* List of constraints that we use to build the constraint graph from. */
556 static vec
<constraint_t
> constraints
;
557 static alloc_pool constraint_pool
;
559 /* The constraint graph is represented as an array of bitmaps
560 containing successor nodes. */
562 struct constraint_graph
564 /* Size of this graph, which may be different than the number of
565 nodes in the variable map. */
568 /* Explicit successors of each node. */
571 /* Implicit predecessors of each node (Used for variable
573 bitmap
*implicit_preds
;
575 /* Explicit predecessors of each node (Used for variable substitution). */
578 /* Indirect cycle representatives, or -1 if the node has no indirect
580 int *indirect_cycles
;
582 /* Representative node for a node. rep[a] == a unless the node has
586 /* Equivalence class representative for a label. This is used for
587 variable substitution. */
590 /* Pointer equivalence label for a node. All nodes with the same
591 pointer equivalence label can be unified together at some point
592 (either during constraint optimization or after the constraint
596 /* Pointer equivalence representative for a label. This is used to
597 handle nodes that are pointer equivalent but not location
598 equivalent. We can unite these once the addressof constraints
599 are transformed into initial points-to sets. */
602 /* Pointer equivalence label for each node, used during variable
604 unsigned int *pointer_label
;
606 /* Location equivalence label for each node, used during location
607 equivalence finding. */
608 unsigned int *loc_label
;
610 /* Pointed-by set for each node, used during location equivalence
611 finding. This is pointed-by rather than pointed-to, because it
612 is constructed using the predecessor graph. */
615 /* Points to sets for pointer equivalence. This is *not* the actual
616 points-to sets for nodes. */
619 /* Bitmap of nodes where the bit is set if the node is a direct
620 node. Used for variable substitution. */
621 sbitmap direct_nodes
;
623 /* Bitmap of nodes where the bit is set if the node is address
624 taken. Used for variable substitution. */
625 bitmap address_taken
;
627 /* Vector of complex constraints for each graph node. Complex
628 constraints are those involving dereferences or offsets that are
630 vec
<constraint_t
> *complex;
633 static constraint_graph_t graph
;
635 /* During variable substitution and the offline version of indirect
636 cycle finding, we create nodes to represent dereferences and
637 address taken constraints. These represent where these start and
639 #define FIRST_REF_NODE (varmap).length ()
640 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
642 /* Return the representative node for NODE, if NODE has been unioned
644 This function performs path compression along the way to finding
645 the representative. */
648 find (unsigned int node
)
650 gcc_checking_assert (node
< graph
->size
);
651 if (graph
->rep
[node
] != node
)
652 return graph
->rep
[node
] = find (graph
->rep
[node
]);
656 /* Union the TO and FROM nodes to the TO nodes.
657 Note that at some point in the future, we may want to do
658 union-by-rank, in which case we are going to have to return the
659 node we unified to. */
662 unite (unsigned int to
, unsigned int from
)
664 gcc_checking_assert (to
< graph
->size
&& from
< graph
->size
);
665 if (to
!= from
&& graph
->rep
[from
] != to
)
667 graph
->rep
[from
] = to
;
673 /* Create a new constraint consisting of LHS and RHS expressions. */
676 new_constraint (const struct constraint_expr lhs
,
677 const struct constraint_expr rhs
)
679 constraint_t ret
= (constraint_t
) pool_alloc (constraint_pool
);
685 /* Print out constraint C to FILE. */
688 dump_constraint (FILE *file
, constraint_t c
)
690 if (c
->lhs
.type
== ADDRESSOF
)
692 else if (c
->lhs
.type
== DEREF
)
694 fprintf (file
, "%s", get_varinfo (c
->lhs
.var
)->name
);
695 if (c
->lhs
.offset
== UNKNOWN_OFFSET
)
696 fprintf (file
, " + UNKNOWN");
697 else if (c
->lhs
.offset
!= 0)
698 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
699 fprintf (file
, " = ");
700 if (c
->rhs
.type
== ADDRESSOF
)
702 else if (c
->rhs
.type
== DEREF
)
704 fprintf (file
, "%s", get_varinfo (c
->rhs
.var
)->name
);
705 if (c
->rhs
.offset
== UNKNOWN_OFFSET
)
706 fprintf (file
, " + UNKNOWN");
707 else if (c
->rhs
.offset
!= 0)
708 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
712 void debug_constraint (constraint_t
);
713 void debug_constraints (void);
714 void debug_constraint_graph (void);
715 void debug_solution_for_var (unsigned int);
716 void debug_sa_points_to_info (void);
718 /* Print out constraint C to stderr. */
721 debug_constraint (constraint_t c
)
723 dump_constraint (stderr
, c
);
724 fprintf (stderr
, "\n");
727 /* Print out all constraints to FILE */
730 dump_constraints (FILE *file
, int from
)
734 for (i
= from
; constraints
.iterate (i
, &c
); i
++)
737 dump_constraint (file
, c
);
738 fprintf (file
, "\n");
742 /* Print out all constraints to stderr. */
745 debug_constraints (void)
747 dump_constraints (stderr
, 0);
750 /* Print the constraint graph in dot format. */
753 dump_constraint_graph (FILE *file
)
757 /* Only print the graph if it has already been initialized: */
761 /* Prints the header of the dot file: */
762 fprintf (file
, "strict digraph {\n");
763 fprintf (file
, " node [\n shape = box\n ]\n");
764 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
765 fprintf (file
, "\n // List of nodes and complex constraints in "
766 "the constraint graph:\n");
768 /* The next lines print the nodes in the graph together with the
769 complex constraints attached to them. */
770 for (i
= 1; i
< graph
->size
; i
++)
772 if (i
== FIRST_REF_NODE
)
776 if (i
< FIRST_REF_NODE
)
777 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
779 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
780 if (graph
->complex[i
].exists ())
784 fprintf (file
, " [label=\"\\N\\n");
785 for (j
= 0; graph
->complex[i
].iterate (j
, &c
); ++j
)
787 dump_constraint (file
, c
);
788 fprintf (file
, "\\l");
790 fprintf (file
, "\"]");
792 fprintf (file
, ";\n");
795 /* Go over the edges. */
796 fprintf (file
, "\n // Edges in the constraint graph:\n");
797 for (i
= 1; i
< graph
->size
; i
++)
803 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
], 0, j
, bi
)
805 unsigned to
= find (j
);
808 if (i
< FIRST_REF_NODE
)
809 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
811 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
812 fprintf (file
, " -> ");
813 if (to
< FIRST_REF_NODE
)
814 fprintf (file
, "\"%s\"", get_varinfo (to
)->name
);
816 fprintf (file
, "\"*%s\"", get_varinfo (to
- FIRST_REF_NODE
)->name
);
817 fprintf (file
, ";\n");
821 /* Prints the tail of the dot file. */
822 fprintf (file
, "}\n");
825 /* Print out the constraint graph to stderr. */
828 debug_constraint_graph (void)
830 dump_constraint_graph (stderr
);
835 The solver is a simple worklist solver, that works on the following
838 sbitmap changed_nodes = all zeroes;
840 For each node that is not already collapsed:
842 set bit in changed nodes
844 while (changed_count > 0)
846 compute topological ordering for constraint graph
848 find and collapse cycles in the constraint graph (updating
849 changed if necessary)
851 for each node (n) in the graph in topological order:
854 Process each complex constraint associated with the node,
855 updating changed if necessary.
857 For each outgoing edge from n, propagate the solution from n to
858 the destination of the edge, updating changed as necessary.
862 /* Return true if two constraint expressions A and B are equal. */
865 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
867 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
870 /* Return true if constraint expression A is less than constraint expression
871 B. This is just arbitrary, but consistent, in order to give them an
875 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
877 if (a
.type
== b
.type
)
880 return a
.offset
< b
.offset
;
882 return a
.var
< b
.var
;
885 return a
.type
< b
.type
;
888 /* Return true if constraint A is less than constraint B. This is just
889 arbitrary, but consistent, in order to give them an ordering. */
892 constraint_less (const constraint_t
&a
, const constraint_t
&b
)
894 if (constraint_expr_less (a
->lhs
, b
->lhs
))
896 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
899 return constraint_expr_less (a
->rhs
, b
->rhs
);
902 /* Return true if two constraints A and B are equal. */
905 constraint_equal (struct constraint a
, struct constraint b
)
907 return constraint_expr_equal (a
.lhs
, b
.lhs
)
908 && constraint_expr_equal (a
.rhs
, b
.rhs
);
912 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
915 constraint_vec_find (vec
<constraint_t
> vec
,
916 struct constraint lookfor
)
924 place
= vec
.lower_bound (&lookfor
, constraint_less
);
925 if (place
>= vec
.length ())
928 if (!constraint_equal (*found
, lookfor
))
933 /* Union two constraint vectors, TO and FROM. Put the result in TO.
934 Returns true of TO set is changed. */
937 constraint_set_union (vec
<constraint_t
> *to
,
938 vec
<constraint_t
> *from
)
942 bool any_change
= false;
944 FOR_EACH_VEC_ELT (*from
, i
, c
)
946 if (constraint_vec_find (*to
, *c
) == NULL
)
948 unsigned int place
= to
->lower_bound (c
, constraint_less
);
949 to
->safe_insert (place
, c
);
956 /* Expands the solution in SET to all sub-fields of variables included. */
959 solution_set_expand (bitmap set
, bitmap
*expanded
)
967 *expanded
= BITMAP_ALLOC (&iteration_obstack
);
969 /* In a first pass expand to the head of the variables we need to
970 add all sub-fields off. This avoids quadratic behavior. */
971 EXECUTE_IF_SET_IN_BITMAP (set
, 0, j
, bi
)
973 varinfo_t v
= get_varinfo (j
);
974 if (v
->is_artificial_var
977 bitmap_set_bit (*expanded
, v
->head
);
980 /* In the second pass now expand all head variables with subfields. */
981 EXECUTE_IF_SET_IN_BITMAP (*expanded
, 0, j
, bi
)
983 varinfo_t v
= get_varinfo (j
);
986 for (v
= vi_next (v
); v
!= NULL
; v
= vi_next (v
))
987 bitmap_set_bit (*expanded
, v
->id
);
990 /* And finally set the rest of the bits from SET. */
991 bitmap_ior_into (*expanded
, set
);
996 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
1000 set_union_with_increment (bitmap to
, bitmap delta
, HOST_WIDE_INT inc
,
1001 bitmap
*expanded_delta
)
1003 bool changed
= false;
1007 /* If the solution of DELTA contains anything it is good enough to transfer
1009 if (bitmap_bit_p (delta
, anything_id
))
1010 return bitmap_set_bit (to
, anything_id
);
1012 /* If the offset is unknown we have to expand the solution to
1014 if (inc
== UNKNOWN_OFFSET
)
1016 delta
= solution_set_expand (delta
, expanded_delta
);
1017 changed
|= bitmap_ior_into (to
, delta
);
1021 /* For non-zero offset union the offsetted solution into the destination. */
1022 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, i
, bi
)
1024 varinfo_t vi
= get_varinfo (i
);
1026 /* If this is a variable with just one field just set its bit
1028 if (vi
->is_artificial_var
1029 || vi
->is_unknown_size_var
1031 changed
|= bitmap_set_bit (to
, i
);
1034 HOST_WIDE_INT fieldoffset
= vi
->offset
+ inc
;
1035 unsigned HOST_WIDE_INT size
= vi
->size
;
1037 /* If the offset makes the pointer point to before the
1038 variable use offset zero for the field lookup. */
1039 if (fieldoffset
< 0)
1040 vi
= get_varinfo (vi
->head
);
1042 vi
= first_or_preceding_vi_for_offset (vi
, fieldoffset
);
1046 changed
|= bitmap_set_bit (to
, vi
->id
);
1051 /* We have to include all fields that overlap the current field
1055 while (vi
->offset
< fieldoffset
+ size
);
1062 /* Insert constraint C into the list of complex constraints for graph
1066 insert_into_complex (constraint_graph_t graph
,
1067 unsigned int var
, constraint_t c
)
1069 vec
<constraint_t
> complex = graph
->complex[var
];
1070 unsigned int place
= complex.lower_bound (c
, constraint_less
);
1072 /* Only insert constraints that do not already exist. */
1073 if (place
>= complex.length ()
1074 || !constraint_equal (*c
, *complex[place
]))
1075 graph
->complex[var
].safe_insert (place
, c
);
1079 /* Condense two variable nodes into a single variable node, by moving
1080 all associated info from FROM to TO. Returns true if TO node's
1081 constraint set changes after the merge. */
1084 merge_node_constraints (constraint_graph_t graph
, unsigned int to
,
1089 bool any_change
= false;
1091 gcc_checking_assert (find (from
) == to
);
1093 /* Move all complex constraints from src node into to node */
1094 FOR_EACH_VEC_ELT (graph
->complex[from
], i
, c
)
1096 /* In complex constraints for node FROM, we may have either
1097 a = *FROM, and *FROM = a, or an offseted constraint which are
1098 always added to the rhs node's constraints. */
1100 if (c
->rhs
.type
== DEREF
)
1102 else if (c
->lhs
.type
== DEREF
)
1108 any_change
= constraint_set_union (&graph
->complex[to
],
1109 &graph
->complex[from
]);
1110 graph
->complex[from
].release ();
1115 /* Remove edges involving NODE from GRAPH. */
1118 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
1120 if (graph
->succs
[node
])
1121 BITMAP_FREE (graph
->succs
[node
]);
1124 /* Merge GRAPH nodes FROM and TO into node TO. */
1127 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1130 if (graph
->indirect_cycles
[from
] != -1)
1132 /* If we have indirect cycles with the from node, and we have
1133 none on the to node, the to node has indirect cycles from the
1134 from node now that they are unified.
1135 If indirect cycles exist on both, unify the nodes that they
1136 are in a cycle with, since we know they are in a cycle with
1138 if (graph
->indirect_cycles
[to
] == -1)
1139 graph
->indirect_cycles
[to
] = graph
->indirect_cycles
[from
];
1142 /* Merge all the successor edges. */
1143 if (graph
->succs
[from
])
1145 if (!graph
->succs
[to
])
1146 graph
->succs
[to
] = BITMAP_ALLOC (&pta_obstack
);
1147 bitmap_ior_into (graph
->succs
[to
],
1148 graph
->succs
[from
]);
1151 clear_edges_for_node (graph
, from
);
1155 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1156 it doesn't exist in the graph already. */
1159 add_implicit_graph_edge (constraint_graph_t graph
, unsigned int to
,
1165 if (!graph
->implicit_preds
[to
])
1166 graph
->implicit_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1168 if (bitmap_set_bit (graph
->implicit_preds
[to
], from
))
1169 stats
.num_implicit_edges
++;
1172 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1173 it doesn't exist in the graph already.
1174 Return false if the edge already existed, true otherwise. */
1177 add_pred_graph_edge (constraint_graph_t graph
, unsigned int to
,
1180 if (!graph
->preds
[to
])
1181 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1182 bitmap_set_bit (graph
->preds
[to
], from
);
1185 /* Add a graph edge to GRAPH, going from FROM to TO if
1186 it doesn't exist in the graph already.
1187 Return false if the edge already existed, true otherwise. */
1190 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1201 if (!graph
->succs
[from
])
1202 graph
->succs
[from
] = BITMAP_ALLOC (&pta_obstack
);
1203 if (bitmap_set_bit (graph
->succs
[from
], to
))
1206 if (to
< FIRST_REF_NODE
&& from
< FIRST_REF_NODE
)
1214 /* Initialize the constraint graph structure to contain SIZE nodes. */
1217 init_graph (unsigned int size
)
1221 graph
= XCNEW (struct constraint_graph
);
1223 graph
->succs
= XCNEWVEC (bitmap
, graph
->size
);
1224 graph
->indirect_cycles
= XNEWVEC (int, graph
->size
);
1225 graph
->rep
= XNEWVEC (unsigned int, graph
->size
);
1226 /* ??? Macros do not support template types with multiple arguments,
1227 so we use a typedef to work around it. */
1228 typedef vec
<constraint_t
> vec_constraint_t_heap
;
1229 graph
->complex = XCNEWVEC (vec_constraint_t_heap
, size
);
1230 graph
->pe
= XCNEWVEC (unsigned int, graph
->size
);
1231 graph
->pe_rep
= XNEWVEC (int, graph
->size
);
1233 for (j
= 0; j
< graph
->size
; j
++)
1236 graph
->pe_rep
[j
] = -1;
1237 graph
->indirect_cycles
[j
] = -1;
1241 /* Build the constraint graph, adding only predecessor edges right now. */
1244 build_pred_graph (void)
1250 graph
->implicit_preds
= XCNEWVEC (bitmap
, graph
->size
);
1251 graph
->preds
= XCNEWVEC (bitmap
, graph
->size
);
1252 graph
->pointer_label
= XCNEWVEC (unsigned int, graph
->size
);
1253 graph
->loc_label
= XCNEWVEC (unsigned int, graph
->size
);
1254 graph
->pointed_by
= XCNEWVEC (bitmap
, graph
->size
);
1255 graph
->points_to
= XCNEWVEC (bitmap
, graph
->size
);
1256 graph
->eq_rep
= XNEWVEC (int, graph
->size
);
1257 graph
->direct_nodes
= sbitmap_alloc (graph
->size
);
1258 graph
->address_taken
= BITMAP_ALLOC (&predbitmap_obstack
);
1259 bitmap_clear (graph
->direct_nodes
);
1261 for (j
= 1; j
< FIRST_REF_NODE
; j
++)
1263 if (!get_varinfo (j
)->is_special_var
)
1264 bitmap_set_bit (graph
->direct_nodes
, j
);
1267 for (j
= 0; j
< graph
->size
; j
++)
1268 graph
->eq_rep
[j
] = -1;
1270 for (j
= 0; j
< varmap
.length (); j
++)
1271 graph
->indirect_cycles
[j
] = -1;
1273 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1275 struct constraint_expr lhs
= c
->lhs
;
1276 struct constraint_expr rhs
= c
->rhs
;
1277 unsigned int lhsvar
= lhs
.var
;
1278 unsigned int rhsvar
= rhs
.var
;
1280 if (lhs
.type
== DEREF
)
1283 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1284 add_pred_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1286 else if (rhs
.type
== DEREF
)
1289 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1290 add_pred_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1292 bitmap_clear_bit (graph
->direct_nodes
, lhsvar
);
1294 else if (rhs
.type
== ADDRESSOF
)
1299 if (graph
->points_to
[lhsvar
] == NULL
)
1300 graph
->points_to
[lhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1301 bitmap_set_bit (graph
->points_to
[lhsvar
], rhsvar
);
1303 if (graph
->pointed_by
[rhsvar
] == NULL
)
1304 graph
->pointed_by
[rhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1305 bitmap_set_bit (graph
->pointed_by
[rhsvar
], lhsvar
);
1307 /* Implicitly, *x = y */
1308 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1310 /* All related variables are no longer direct nodes. */
1311 bitmap_clear_bit (graph
->direct_nodes
, rhsvar
);
1312 v
= get_varinfo (rhsvar
);
1313 if (!v
->is_full_var
)
1315 v
= get_varinfo (v
->head
);
1318 bitmap_clear_bit (graph
->direct_nodes
, v
->id
);
1323 bitmap_set_bit (graph
->address_taken
, rhsvar
);
1325 else if (lhsvar
> anything_id
1326 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1329 add_pred_graph_edge (graph
, lhsvar
, rhsvar
);
1330 /* Implicitly, *x = *y */
1331 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
,
1332 FIRST_REF_NODE
+ rhsvar
);
1334 else if (lhs
.offset
!= 0 || rhs
.offset
!= 0)
1336 if (rhs
.offset
!= 0)
1337 bitmap_clear_bit (graph
->direct_nodes
, lhs
.var
);
1338 else if (lhs
.offset
!= 0)
1339 bitmap_clear_bit (graph
->direct_nodes
, rhs
.var
);
1344 /* Build the constraint graph, adding successor edges. */
1347 build_succ_graph (void)
1352 FOR_EACH_VEC_ELT (constraints
, i
, c
)
1354 struct constraint_expr lhs
;
1355 struct constraint_expr rhs
;
1356 unsigned int lhsvar
;
1357 unsigned int rhsvar
;
1364 lhsvar
= find (lhs
.var
);
1365 rhsvar
= find (rhs
.var
);
1367 if (lhs
.type
== DEREF
)
1369 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1370 add_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1372 else if (rhs
.type
== DEREF
)
1374 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1375 add_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1377 else if (rhs
.type
== ADDRESSOF
)
1380 gcc_checking_assert (find (rhs
.var
) == rhs
.var
);
1381 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1383 else if (lhsvar
> anything_id
1384 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1386 add_graph_edge (graph
, lhsvar
, rhsvar
);
1390 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1391 receive pointers. */
1392 t
= find (storedanything_id
);
1393 for (i
= integer_id
+ 1; i
< FIRST_REF_NODE
; ++i
)
1395 if (!bitmap_bit_p (graph
->direct_nodes
, i
)
1396 && get_varinfo (i
)->may_have_pointers
)
1397 add_graph_edge (graph
, find (i
), t
);
1400 /* Everything stored to ANYTHING also potentially escapes. */
1401 add_graph_edge (graph
, find (escaped_id
), t
);
1405 /* Changed variables on the last iteration. */
1406 static bitmap changed
;
1408 /* Strongly Connected Component visitation info. */
1415 unsigned int *node_mapping
;
1417 vec
<unsigned> scc_stack
;
1421 /* Recursive routine to find strongly connected components in GRAPH.
1422 SI is the SCC info to store the information in, and N is the id of current
1423 graph node we are processing.
1425 This is Tarjan's strongly connected component finding algorithm, as
1426 modified by Nuutila to keep only non-root nodes on the stack.
1427 The algorithm can be found in "On finding the strongly connected
1428 connected components in a directed graph" by Esko Nuutila and Eljas
1429 Soisalon-Soininen, in Information Processing Letters volume 49,
1430 number 1, pages 9-14. */
1433 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1437 unsigned int my_dfs
;
1439 bitmap_set_bit (si
->visited
, n
);
1440 si
->dfs
[n
] = si
->current_index
++;
1441 my_dfs
= si
->dfs
[n
];
1443 /* Visit all the successors. */
1444 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
1448 if (i
> LAST_REF_NODE
)
1452 if (bitmap_bit_p (si
->deleted
, w
))
1455 if (!bitmap_bit_p (si
->visited
, w
))
1456 scc_visit (graph
, si
, w
);
1458 unsigned int t
= find (w
);
1459 gcc_checking_assert (find (n
) == n
);
1460 if (si
->dfs
[t
] < si
->dfs
[n
])
1461 si
->dfs
[n
] = si
->dfs
[t
];
1464 /* See if any components have been identified. */
1465 if (si
->dfs
[n
] == my_dfs
)
1467 if (si
->scc_stack
.length () > 0
1468 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1470 bitmap scc
= BITMAP_ALLOC (NULL
);
1471 unsigned int lowest_node
;
1474 bitmap_set_bit (scc
, n
);
1476 while (si
->scc_stack
.length () != 0
1477 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
1479 unsigned int w
= si
->scc_stack
.pop ();
1481 bitmap_set_bit (scc
, w
);
1484 lowest_node
= bitmap_first_set_bit (scc
);
1485 gcc_assert (lowest_node
< FIRST_REF_NODE
);
1487 /* Collapse the SCC nodes into a single node, and mark the
1489 EXECUTE_IF_SET_IN_BITMAP (scc
, 0, i
, bi
)
1491 if (i
< FIRST_REF_NODE
)
1493 if (unite (lowest_node
, i
))
1494 unify_nodes (graph
, lowest_node
, i
, false);
1498 unite (lowest_node
, i
);
1499 graph
->indirect_cycles
[i
- FIRST_REF_NODE
] = lowest_node
;
1503 bitmap_set_bit (si
->deleted
, n
);
1506 si
->scc_stack
.safe_push (n
);
1509 /* Unify node FROM into node TO, updating the changed count if
1510 necessary when UPDATE_CHANGED is true. */
1513 unify_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1514 bool update_changed
)
1516 gcc_checking_assert (to
!= from
&& find (to
) == to
);
1518 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1519 fprintf (dump_file
, "Unifying %s to %s\n",
1520 get_varinfo (from
)->name
,
1521 get_varinfo (to
)->name
);
1524 stats
.unified_vars_dynamic
++;
1526 stats
.unified_vars_static
++;
1528 merge_graph_nodes (graph
, to
, from
);
1529 if (merge_node_constraints (graph
, to
, from
))
1532 bitmap_set_bit (changed
, to
);
1535 /* Mark TO as changed if FROM was changed. If TO was already marked
1536 as changed, decrease the changed count. */
1539 && bitmap_clear_bit (changed
, from
))
1540 bitmap_set_bit (changed
, to
);
1541 varinfo_t fromvi
= get_varinfo (from
);
1542 if (fromvi
->solution
)
1544 /* If the solution changes because of the merging, we need to mark
1545 the variable as changed. */
1546 varinfo_t tovi
= get_varinfo (to
);
1547 if (bitmap_ior_into (tovi
->solution
, fromvi
->solution
))
1550 bitmap_set_bit (changed
, to
);
1553 BITMAP_FREE (fromvi
->solution
);
1554 if (fromvi
->oldsolution
)
1555 BITMAP_FREE (fromvi
->oldsolution
);
1557 if (stats
.iterations
> 0
1558 && tovi
->oldsolution
)
1559 BITMAP_FREE (tovi
->oldsolution
);
1561 if (graph
->succs
[to
])
1562 bitmap_clear_bit (graph
->succs
[to
], to
);
1565 /* Information needed to compute the topological ordering of a graph. */
1569 /* sbitmap of visited nodes. */
1571 /* Array that stores the topological order of the graph, *in
1573 vec
<unsigned> topo_order
;
1577 /* Initialize and return a topological info structure. */
1579 static struct topo_info
*
1580 init_topo_info (void)
1582 size_t size
= graph
->size
;
1583 struct topo_info
*ti
= XNEW (struct topo_info
);
1584 ti
->visited
= sbitmap_alloc (size
);
1585 bitmap_clear (ti
->visited
);
1586 ti
->topo_order
.create (1);
1591 /* Free the topological sort info pointed to by TI. */
1594 free_topo_info (struct topo_info
*ti
)
1596 sbitmap_free (ti
->visited
);
1597 ti
->topo_order
.release ();
1601 /* Visit the graph in topological order, and store the order in the
1602 topo_info structure. */
1605 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1611 bitmap_set_bit (ti
->visited
, n
);
1613 if (graph
->succs
[n
])
1614 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[n
], 0, j
, bi
)
1616 if (!bitmap_bit_p (ti
->visited
, j
))
1617 topo_visit (graph
, ti
, j
);
1620 ti
->topo_order
.safe_push (n
);
1623 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1624 starting solution for y. */
1627 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1628 bitmap delta
, bitmap
*expanded_delta
)
1630 unsigned int lhs
= c
->lhs
.var
;
1632 bitmap sol
= get_varinfo (lhs
)->solution
;
1635 HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1637 /* Our IL does not allow this. */
1638 gcc_checking_assert (c
->lhs
.offset
== 0);
1640 /* If the solution of Y contains anything it is good enough to transfer
1642 if (bitmap_bit_p (delta
, anything_id
))
1644 flag
|= bitmap_set_bit (sol
, anything_id
);
1648 /* If we do not know at with offset the rhs is dereferenced compute
1649 the reachability set of DELTA, conservatively assuming it is
1650 dereferenced at all valid offsets. */
1651 if (roffset
== UNKNOWN_OFFSET
)
1653 delta
= solution_set_expand (delta
, expanded_delta
);
1654 /* No further offset processing is necessary. */
1658 /* For each variable j in delta (Sol(y)), add
1659 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1660 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1662 varinfo_t v
= get_varinfo (j
);
1663 HOST_WIDE_INT fieldoffset
= v
->offset
+ roffset
;
1664 unsigned HOST_WIDE_INT size
= v
->size
;
1669 else if (roffset
!= 0)
1671 if (fieldoffset
< 0)
1672 v
= get_varinfo (v
->head
);
1674 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1677 /* We have to include all fields that overlap the current field
1678 shifted by roffset. */
1683 /* Adding edges from the special vars is pointless.
1684 They don't have sets that can change. */
1685 if (get_varinfo (t
)->is_special_var
)
1686 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1687 /* Merging the solution from ESCAPED needlessly increases
1688 the set. Use ESCAPED as representative instead. */
1689 else if (v
->id
== escaped_id
)
1690 flag
|= bitmap_set_bit (sol
, escaped_id
);
1691 else if (v
->may_have_pointers
1692 && add_graph_edge (graph
, lhs
, t
))
1693 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1701 while (v
->offset
< fieldoffset
+ size
);
1705 /* If the LHS solution changed, mark the var as changed. */
1708 get_varinfo (lhs
)->solution
= sol
;
1709 bitmap_set_bit (changed
, lhs
);
1713 /* Process a constraint C that represents *(x + off) = y using DELTA
1714 as the starting solution for x. */
1717 do_ds_constraint (constraint_t c
, bitmap delta
, bitmap
*expanded_delta
)
1719 unsigned int rhs
= c
->rhs
.var
;
1720 bitmap sol
= get_varinfo (rhs
)->solution
;
1723 HOST_WIDE_INT loff
= c
->lhs
.offset
;
1724 bool escaped_p
= false;
1726 /* Our IL does not allow this. */
1727 gcc_checking_assert (c
->rhs
.offset
== 0);
1729 /* If the solution of y contains ANYTHING simply use the ANYTHING
1730 solution. This avoids needlessly increasing the points-to sets. */
1731 if (bitmap_bit_p (sol
, anything_id
))
1732 sol
= get_varinfo (find (anything_id
))->solution
;
1734 /* If the solution for x contains ANYTHING we have to merge the
1735 solution of y into all pointer variables which we do via
1737 if (bitmap_bit_p (delta
, anything_id
))
1739 unsigned t
= find (storedanything_id
);
1740 if (add_graph_edge (graph
, t
, rhs
))
1742 if (bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1743 bitmap_set_bit (changed
, t
);
1748 /* If we do not know at with offset the rhs is dereferenced compute
1749 the reachability set of DELTA, conservatively assuming it is
1750 dereferenced at all valid offsets. */
1751 if (loff
== UNKNOWN_OFFSET
)
1753 delta
= solution_set_expand (delta
, expanded_delta
);
1757 /* For each member j of delta (Sol(x)), add an edge from y to j and
1758 union Sol(y) into Sol(j) */
1759 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1761 varinfo_t v
= get_varinfo (j
);
1763 HOST_WIDE_INT fieldoffset
= v
->offset
+ loff
;
1764 unsigned HOST_WIDE_INT size
= v
->size
;
1770 if (fieldoffset
< 0)
1771 v
= get_varinfo (v
->head
);
1773 v
= first_or_preceding_vi_for_offset (v
, fieldoffset
);
1776 /* We have to include all fields that overlap the current field
1780 if (v
->may_have_pointers
)
1782 /* If v is a global variable then this is an escape point. */
1783 if (v
->is_global_var
1786 t
= find (escaped_id
);
1787 if (add_graph_edge (graph
, t
, rhs
)
1788 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1789 bitmap_set_bit (changed
, t
);
1790 /* Enough to let rhs escape once. */
1794 if (v
->is_special_var
)
1798 if (add_graph_edge (graph
, t
, rhs
)
1799 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1800 bitmap_set_bit (changed
, t
);
1809 while (v
->offset
< fieldoffset
+ size
);
1813 /* Handle a non-simple (simple meaning requires no iteration),
1814 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1817 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
,
1818 bitmap
*expanded_delta
)
1820 if (c
->lhs
.type
== DEREF
)
1822 if (c
->rhs
.type
== ADDRESSOF
)
1829 do_ds_constraint (c
, delta
, expanded_delta
);
1832 else if (c
->rhs
.type
== DEREF
)
1835 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1836 do_sd_constraint (graph
, c
, delta
, expanded_delta
);
1843 gcc_checking_assert (c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
1844 && c
->rhs
.offset
!= 0 && c
->lhs
.offset
== 0);
1845 tmp
= get_varinfo (c
->lhs
.var
)->solution
;
1847 flag
= set_union_with_increment (tmp
, delta
, c
->rhs
.offset
,
1851 bitmap_set_bit (changed
, c
->lhs
.var
);
1855 /* Initialize and return a new SCC info structure. */
1857 static struct scc_info
*
1858 init_scc_info (size_t size
)
1860 struct scc_info
*si
= XNEW (struct scc_info
);
1863 si
->current_index
= 0;
1864 si
->visited
= sbitmap_alloc (size
);
1865 bitmap_clear (si
->visited
);
1866 si
->deleted
= sbitmap_alloc (size
);
1867 bitmap_clear (si
->deleted
);
1868 si
->node_mapping
= XNEWVEC (unsigned int, size
);
1869 si
->dfs
= XCNEWVEC (unsigned int, size
);
1871 for (i
= 0; i
< size
; i
++)
1872 si
->node_mapping
[i
] = i
;
1874 si
->scc_stack
.create (1);
1878 /* Free an SCC info structure pointed to by SI */
1881 free_scc_info (struct scc_info
*si
)
1883 sbitmap_free (si
->visited
);
1884 sbitmap_free (si
->deleted
);
1885 free (si
->node_mapping
);
1887 si
->scc_stack
.release ();
1892 /* Find indirect cycles in GRAPH that occur, using strongly connected
1893 components, and note them in the indirect cycles map.
1895 This technique comes from Ben Hardekopf and Calvin Lin,
1896 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1897 Lines of Code", submitted to PLDI 2007. */
1900 find_indirect_cycles (constraint_graph_t graph
)
1903 unsigned int size
= graph
->size
;
1904 struct scc_info
*si
= init_scc_info (size
);
1906 for (i
= 0; i
< MIN (LAST_REF_NODE
, size
); i
++ )
1907 if (!bitmap_bit_p (si
->visited
, i
) && find (i
) == i
)
1908 scc_visit (graph
, si
, i
);
1913 /* Compute a topological ordering for GRAPH, and store the result in the
1914 topo_info structure TI. */
1917 compute_topo_order (constraint_graph_t graph
,
1918 struct topo_info
*ti
)
1921 unsigned int size
= graph
->size
;
1923 for (i
= 0; i
!= size
; ++i
)
1924 if (!bitmap_bit_p (ti
->visited
, i
) && find (i
) == i
)
1925 topo_visit (graph
, ti
, i
);
1928 /* Structure used to for hash value numbering of pointer equivalence
1931 typedef struct equiv_class_label
1934 unsigned int equivalence_class
;
1936 } *equiv_class_label_t
;
1937 typedef const struct equiv_class_label
*const_equiv_class_label_t
;
1939 /* Equiv_class_label hashtable helpers. */
1941 struct equiv_class_hasher
: typed_free_remove
<equiv_class_label
>
1943 typedef equiv_class_label
*value_type
;
1944 typedef equiv_class_label
*compare_type
;
1945 static inline hashval_t
hash (const equiv_class_label
*);
1946 static inline bool equal (const equiv_class_label
*,
1947 const equiv_class_label
*);
1950 /* Hash function for a equiv_class_label_t */
1953 equiv_class_hasher::hash (const equiv_class_label
*ecl
)
1955 return ecl
->hashcode
;
1958 /* Equality function for two equiv_class_label_t's. */
1961 equiv_class_hasher::equal (const equiv_class_label
*eql1
,
1962 const equiv_class_label
*eql2
)
1964 return (eql1
->hashcode
== eql2
->hashcode
1965 && bitmap_equal_p (eql1
->labels
, eql2
->labels
));
1968 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1970 static hash_table
<equiv_class_hasher
> *pointer_equiv_class_table
;
1972 /* A hashtable for mapping a bitmap of labels->location equivalence
1974 static hash_table
<equiv_class_hasher
> *location_equiv_class_table
;
1976 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1977 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1978 is equivalent to. */
1980 static equiv_class_label
*
1981 equiv_class_lookup_or_add (hash_table
<equiv_class_hasher
> *table
,
1984 equiv_class_label
**slot
;
1985 equiv_class_label ecl
;
1987 ecl
.labels
= labels
;
1988 ecl
.hashcode
= bitmap_hash (labels
);
1989 slot
= table
->find_slot (&ecl
, INSERT
);
1992 *slot
= XNEW (struct equiv_class_label
);
1993 (*slot
)->labels
= labels
;
1994 (*slot
)->hashcode
= ecl
.hashcode
;
1995 (*slot
)->equivalence_class
= 0;
2001 /* Perform offline variable substitution.
2003 This is a worst case quadratic time way of identifying variables
2004 that must have equivalent points-to sets, including those caused by
2005 static cycles, and single entry subgraphs, in the constraint graph.
2007 The technique is described in "Exploiting Pointer and Location
2008 Equivalence to Optimize Pointer Analysis. In the 14th International
2009 Static Analysis Symposium (SAS), August 2007." It is known as the
2010 "HU" algorithm, and is equivalent to value numbering the collapsed
2011 constraint graph including evaluating unions.
2013 The general method of finding equivalence classes is as follows:
2014 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
2015 Initialize all non-REF nodes to be direct nodes.
2016 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
2018 For each constraint containing the dereference, we also do the same
2021 We then compute SCC's in the graph and unify nodes in the same SCC,
2024 For each non-collapsed node x:
2025 Visit all unvisited explicit incoming edges.
2026 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
2028 Lookup the equivalence class for pts(x).
2029 If we found one, equivalence_class(x) = found class.
2030 Otherwise, equivalence_class(x) = new class, and new_class is
2031 added to the lookup table.
2033 All direct nodes with the same equivalence class can be replaced
2034 with a single representative node.
2035 All unlabeled nodes (label == 0) are not pointers and all edges
2036 involving them can be eliminated.
2037 We perform these optimizations during rewrite_constraints
2039 In addition to pointer equivalence class finding, we also perform
2040 location equivalence class finding. This is the set of variables
2041 that always appear together in points-to sets. We use this to
2042 compress the size of the points-to sets. */
2044 /* Current maximum pointer equivalence class id. */
2045 static int pointer_equiv_class
;
2047 /* Current maximum location equivalence class id. */
2048 static int location_equiv_class
;
2050 /* Recursive routine to find strongly connected components in GRAPH,
2051 and label it's nodes with DFS numbers. */
2054 condense_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2058 unsigned int my_dfs
;
2060 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2061 bitmap_set_bit (si
->visited
, n
);
2062 si
->dfs
[n
] = si
->current_index
++;
2063 my_dfs
= si
->dfs
[n
];
2065 /* Visit all the successors. */
2066 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2068 unsigned int w
= si
->node_mapping
[i
];
2070 if (bitmap_bit_p (si
->deleted
, w
))
2073 if (!bitmap_bit_p (si
->visited
, w
))
2074 condense_visit (graph
, si
, w
);
2076 unsigned int t
= si
->node_mapping
[w
];
2077 gcc_checking_assert (si
->node_mapping
[n
] == n
);
2078 if (si
->dfs
[t
] < si
->dfs
[n
])
2079 si
->dfs
[n
] = si
->dfs
[t
];
2082 /* Visit all the implicit predecessors. */
2083 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->implicit_preds
[n
], 0, i
, bi
)
2085 unsigned int w
= si
->node_mapping
[i
];
2087 if (bitmap_bit_p (si
->deleted
, w
))
2090 if (!bitmap_bit_p (si
->visited
, w
))
2091 condense_visit (graph
, si
, w
);
2093 unsigned int t
= si
->node_mapping
[w
];
2094 gcc_assert (si
->node_mapping
[n
] == n
);
2095 if (si
->dfs
[t
] < si
->dfs
[n
])
2096 si
->dfs
[n
] = si
->dfs
[t
];
2099 /* See if any components have been identified. */
2100 if (si
->dfs
[n
] == my_dfs
)
2102 while (si
->scc_stack
.length () != 0
2103 && si
->dfs
[si
->scc_stack
.last ()] >= my_dfs
)
2105 unsigned int w
= si
->scc_stack
.pop ();
2106 si
->node_mapping
[w
] = n
;
2108 if (!bitmap_bit_p (graph
->direct_nodes
, w
))
2109 bitmap_clear_bit (graph
->direct_nodes
, n
);
2111 /* Unify our nodes. */
2112 if (graph
->preds
[w
])
2114 if (!graph
->preds
[n
])
2115 graph
->preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2116 bitmap_ior_into (graph
->preds
[n
], graph
->preds
[w
]);
2118 if (graph
->implicit_preds
[w
])
2120 if (!graph
->implicit_preds
[n
])
2121 graph
->implicit_preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2122 bitmap_ior_into (graph
->implicit_preds
[n
],
2123 graph
->implicit_preds
[w
]);
2125 if (graph
->points_to
[w
])
2127 if (!graph
->points_to
[n
])
2128 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2129 bitmap_ior_into (graph
->points_to
[n
],
2130 graph
->points_to
[w
]);
2133 bitmap_set_bit (si
->deleted
, n
);
2136 si
->scc_stack
.safe_push (n
);
2139 /* Label pointer equivalences.
2141 This performs a value numbering of the constraint graph to
2142 discover which variables will always have the same points-to sets
2143 under the current set of constraints.
2145 The way it value numbers is to store the set of points-to bits
2146 generated by the constraints and graph edges. This is just used as a
2147 hash and equality comparison. The *actual set of points-to bits* is
2148 completely irrelevant, in that we don't care about being able to
2151 The equality values (currently bitmaps) just have to satisfy a few
2152 constraints, the main ones being:
2153 1. The combining operation must be order independent.
2154 2. The end result of a given set of operations must be unique iff the
2155 combination of input values is unique
2159 label_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2161 unsigned int i
, first_pred
;
2164 bitmap_set_bit (si
->visited
, n
);
2166 /* Label and union our incoming edges's points to sets. */
2168 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2170 unsigned int w
= si
->node_mapping
[i
];
2171 if (!bitmap_bit_p (si
->visited
, w
))
2172 label_visit (graph
, si
, w
);
2174 /* Skip unused edges */
2175 if (w
== n
|| graph
->pointer_label
[w
] == 0)
2178 if (graph
->points_to
[w
])
2180 if (!graph
->points_to
[n
])
2182 if (first_pred
== -1U)
2186 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2187 bitmap_ior (graph
->points_to
[n
],
2188 graph
->points_to
[first_pred
],
2189 graph
->points_to
[w
]);
2193 bitmap_ior_into (graph
->points_to
[n
], graph
->points_to
[w
]);
2197 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2198 if (!bitmap_bit_p (graph
->direct_nodes
, n
))
2200 if (!graph
->points_to
[n
])
2202 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2203 if (first_pred
!= -1U)
2204 bitmap_copy (graph
->points_to
[n
], graph
->points_to
[first_pred
]);
2206 bitmap_set_bit (graph
->points_to
[n
], FIRST_REF_NODE
+ n
);
2207 graph
->pointer_label
[n
] = pointer_equiv_class
++;
2208 equiv_class_label_t ecl
;
2209 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2210 graph
->points_to
[n
]);
2211 ecl
->equivalence_class
= graph
->pointer_label
[n
];
2215 /* If there was only a single non-empty predecessor the pointer equiv
2216 class is the same. */
2217 if (!graph
->points_to
[n
])
2219 if (first_pred
!= -1U)
2221 graph
->pointer_label
[n
] = graph
->pointer_label
[first_pred
];
2222 graph
->points_to
[n
] = graph
->points_to
[first_pred
];
2227 if (!bitmap_empty_p (graph
->points_to
[n
]))
2229 equiv_class_label_t ecl
;
2230 ecl
= equiv_class_lookup_or_add (pointer_equiv_class_table
,
2231 graph
->points_to
[n
]);
2232 if (ecl
->equivalence_class
== 0)
2233 ecl
->equivalence_class
= pointer_equiv_class
++;
2236 BITMAP_FREE (graph
->points_to
[n
]);
2237 graph
->points_to
[n
] = ecl
->labels
;
2239 graph
->pointer_label
[n
] = ecl
->equivalence_class
;
2243 /* Print the pred graph in dot format. */
2246 dump_pred_graph (struct scc_info
*si
, FILE *file
)
2250 /* Only print the graph if it has already been initialized: */
2254 /* Prints the header of the dot file: */
2255 fprintf (file
, "strict digraph {\n");
2256 fprintf (file
, " node [\n shape = box\n ]\n");
2257 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
2258 fprintf (file
, "\n // List of nodes and complex constraints in "
2259 "the constraint graph:\n");
2261 /* The next lines print the nodes in the graph together with the
2262 complex constraints attached to them. */
2263 for (i
= 1; i
< graph
->size
; i
++)
2265 if (i
== FIRST_REF_NODE
)
2267 if (si
->node_mapping
[i
] != i
)
2269 if (i
< FIRST_REF_NODE
)
2270 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2272 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2273 if (graph
->points_to
[i
]
2274 && !bitmap_empty_p (graph
->points_to
[i
]))
2276 fprintf (file
, "[label=\"%s = {", get_varinfo (i
)->name
);
2279 EXECUTE_IF_SET_IN_BITMAP (graph
->points_to
[i
], 0, j
, bi
)
2280 fprintf (file
, " %d", j
);
2281 fprintf (file
, " }\"]");
2283 fprintf (file
, ";\n");
2286 /* Go over the edges. */
2287 fprintf (file
, "\n // Edges in the constraint graph:\n");
2288 for (i
= 1; i
< graph
->size
; i
++)
2292 if (si
->node_mapping
[i
] != i
)
2294 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[i
], 0, j
, bi
)
2296 unsigned from
= si
->node_mapping
[j
];
2297 if (from
< FIRST_REF_NODE
)
2298 fprintf (file
, "\"%s\"", get_varinfo (from
)->name
);
2300 fprintf (file
, "\"*%s\"", get_varinfo (from
- FIRST_REF_NODE
)->name
);
2301 fprintf (file
, " -> ");
2302 if (i
< FIRST_REF_NODE
)
2303 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
2305 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
2306 fprintf (file
, ";\n");
2310 /* Prints the tail of the dot file. */
2311 fprintf (file
, "}\n");
2314 /* Perform offline variable substitution, discovering equivalence
2315 classes, and eliminating non-pointer variables. */
2317 static struct scc_info
*
2318 perform_var_substitution (constraint_graph_t graph
)
2321 unsigned int size
= graph
->size
;
2322 struct scc_info
*si
= init_scc_info (size
);
2324 bitmap_obstack_initialize (&iteration_obstack
);
2325 pointer_equiv_class_table
= new hash_table
<equiv_class_hasher
> (511);
2326 location_equiv_class_table
2327 = new hash_table
<equiv_class_hasher
> (511);
2328 pointer_equiv_class
= 1;
2329 location_equiv_class
= 1;
2331 /* Condense the nodes, which means to find SCC's, count incoming
2332 predecessors, and unite nodes in SCC's. */
2333 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2334 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2335 condense_visit (graph
, si
, si
->node_mapping
[i
]);
2337 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
2339 fprintf (dump_file
, "\n\n// The constraint graph before var-substitution "
2340 "in dot format:\n");
2341 dump_pred_graph (si
, dump_file
);
2342 fprintf (dump_file
, "\n\n");
2345 bitmap_clear (si
->visited
);
2346 /* Actually the label the nodes for pointer equivalences */
2347 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2348 if (!bitmap_bit_p (si
->visited
, si
->node_mapping
[i
]))
2349 label_visit (graph
, si
, si
->node_mapping
[i
]);
2351 /* Calculate location equivalence labels. */
2352 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2358 if (!graph
->pointed_by
[i
])
2360 pointed_by
= BITMAP_ALLOC (&iteration_obstack
);
2362 /* Translate the pointed-by mapping for pointer equivalence
2364 EXECUTE_IF_SET_IN_BITMAP (graph
->pointed_by
[i
], 0, j
, bi
)
2366 bitmap_set_bit (pointed_by
,
2367 graph
->pointer_label
[si
->node_mapping
[j
]]);
2369 /* The original pointed_by is now dead. */
2370 BITMAP_FREE (graph
->pointed_by
[i
]);
2372 /* Look up the location equivalence label if one exists, or make
2374 equiv_class_label_t ecl
;
2375 ecl
= equiv_class_lookup_or_add (location_equiv_class_table
, pointed_by
);
2376 if (ecl
->equivalence_class
== 0)
2377 ecl
->equivalence_class
= location_equiv_class
++;
2380 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2381 fprintf (dump_file
, "Found location equivalence for node %s\n",
2382 get_varinfo (i
)->name
);
2383 BITMAP_FREE (pointed_by
);
2385 graph
->loc_label
[i
] = ecl
->equivalence_class
;
2389 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2390 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2392 unsigned j
= si
->node_mapping
[i
];
2395 fprintf (dump_file
, "%s node id %d ",
2396 bitmap_bit_p (graph
->direct_nodes
, i
)
2397 ? "Direct" : "Indirect", i
);
2398 if (i
< FIRST_REF_NODE
)
2399 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2401 fprintf (dump_file
, "\"*%s\"",
2402 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2403 fprintf (dump_file
, " mapped to SCC leader node id %d ", j
);
2404 if (j
< FIRST_REF_NODE
)
2405 fprintf (dump_file
, "\"%s\"\n", get_varinfo (j
)->name
);
2407 fprintf (dump_file
, "\"*%s\"\n",
2408 get_varinfo (j
- FIRST_REF_NODE
)->name
);
2413 "Equivalence classes for %s node id %d ",
2414 bitmap_bit_p (graph
->direct_nodes
, i
)
2415 ? "direct" : "indirect", i
);
2416 if (i
< FIRST_REF_NODE
)
2417 fprintf (dump_file
, "\"%s\"", get_varinfo (i
)->name
);
2419 fprintf (dump_file
, "\"*%s\"",
2420 get_varinfo (i
- FIRST_REF_NODE
)->name
);
2422 ": pointer %d, location %d\n",
2423 graph
->pointer_label
[i
], graph
->loc_label
[i
]);
2427 /* Quickly eliminate our non-pointer variables. */
2429 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2431 unsigned int node
= si
->node_mapping
[i
];
2433 if (graph
->pointer_label
[node
] == 0)
2435 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2437 "%s is a non-pointer variable, eliminating edges.\n",
2438 get_varinfo (node
)->name
);
2439 stats
.nonpointer_vars
++;
2440 clear_edges_for_node (graph
, node
);
2447 /* Free information that was only necessary for variable
2451 free_var_substitution_info (struct scc_info
*si
)
2454 free (graph
->pointer_label
);
2455 free (graph
->loc_label
);
2456 free (graph
->pointed_by
);
2457 free (graph
->points_to
);
2458 free (graph
->eq_rep
);
2459 sbitmap_free (graph
->direct_nodes
);
2460 delete pointer_equiv_class_table
;
2461 pointer_equiv_class_table
= NULL
;
2462 delete location_equiv_class_table
;
2463 location_equiv_class_table
= NULL
;
2464 bitmap_obstack_release (&iteration_obstack
);
2467 /* Return an existing node that is equivalent to NODE, which has
2468 equivalence class LABEL, if one exists. Return NODE otherwise. */
2471 find_equivalent_node (constraint_graph_t graph
,
2472 unsigned int node
, unsigned int label
)
2474 /* If the address version of this variable is unused, we can
2475 substitute it for anything else with the same label.
2476 Otherwise, we know the pointers are equivalent, but not the
2477 locations, and we can unite them later. */
2479 if (!bitmap_bit_p (graph
->address_taken
, node
))
2481 gcc_checking_assert (label
< graph
->size
);
2483 if (graph
->eq_rep
[label
] != -1)
2485 /* Unify the two variables since we know they are equivalent. */
2486 if (unite (graph
->eq_rep
[label
], node
))
2487 unify_nodes (graph
, graph
->eq_rep
[label
], node
, false);
2488 return graph
->eq_rep
[label
];
2492 graph
->eq_rep
[label
] = node
;
2493 graph
->pe_rep
[label
] = node
;
2498 gcc_checking_assert (label
< graph
->size
);
2499 graph
->pe
[node
] = label
;
2500 if (graph
->pe_rep
[label
] == -1)
2501 graph
->pe_rep
[label
] = node
;
2507 /* Unite pointer equivalent but not location equivalent nodes in
2508 GRAPH. This may only be performed once variable substitution is
2512 unite_pointer_equivalences (constraint_graph_t graph
)
2516 /* Go through the pointer equivalences and unite them to their
2517 representative, if they aren't already. */
2518 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
2520 unsigned int label
= graph
->pe
[i
];
2523 int label_rep
= graph
->pe_rep
[label
];
2525 if (label_rep
== -1)
2528 label_rep
= find (label_rep
);
2529 if (label_rep
>= 0 && unite (label_rep
, find (i
)))
2530 unify_nodes (graph
, label_rep
, i
, false);
2535 /* Move complex constraints to the GRAPH nodes they belong to. */
2538 move_complex_constraints (constraint_graph_t graph
)
2543 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2547 struct constraint_expr lhs
= c
->lhs
;
2548 struct constraint_expr rhs
= c
->rhs
;
2550 if (lhs
.type
== DEREF
)
2552 insert_into_complex (graph
, lhs
.var
, c
);
2554 else if (rhs
.type
== DEREF
)
2556 if (!(get_varinfo (lhs
.var
)->is_special_var
))
2557 insert_into_complex (graph
, rhs
.var
, c
);
2559 else if (rhs
.type
!= ADDRESSOF
&& lhs
.var
> anything_id
2560 && (lhs
.offset
!= 0 || rhs
.offset
!= 0))
2562 insert_into_complex (graph
, rhs
.var
, c
);
2569 /* Optimize and rewrite complex constraints while performing
2570 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2571 result of perform_variable_substitution. */
2574 rewrite_constraints (constraint_graph_t graph
,
2575 struct scc_info
*si
)
2580 #ifdef ENABLE_CHECKING
2581 for (unsigned int j
= 0; j
< graph
->size
; j
++)
2582 gcc_assert (find (j
) == j
);
2585 FOR_EACH_VEC_ELT (constraints
, i
, c
)
2587 struct constraint_expr lhs
= c
->lhs
;
2588 struct constraint_expr rhs
= c
->rhs
;
2589 unsigned int lhsvar
= find (lhs
.var
);
2590 unsigned int rhsvar
= find (rhs
.var
);
2591 unsigned int lhsnode
, rhsnode
;
2592 unsigned int lhslabel
, rhslabel
;
2594 lhsnode
= si
->node_mapping
[lhsvar
];
2595 rhsnode
= si
->node_mapping
[rhsvar
];
2596 lhslabel
= graph
->pointer_label
[lhsnode
];
2597 rhslabel
= graph
->pointer_label
[rhsnode
];
2599 /* See if it is really a non-pointer variable, and if so, ignore
2603 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2606 fprintf (dump_file
, "%s is a non-pointer variable,"
2607 "ignoring constraint:",
2608 get_varinfo (lhs
.var
)->name
);
2609 dump_constraint (dump_file
, c
);
2610 fprintf (dump_file
, "\n");
2612 constraints
[i
] = NULL
;
2618 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2621 fprintf (dump_file
, "%s is a non-pointer variable,"
2622 "ignoring constraint:",
2623 get_varinfo (rhs
.var
)->name
);
2624 dump_constraint (dump_file
, c
);
2625 fprintf (dump_file
, "\n");
2627 constraints
[i
] = NULL
;
2631 lhsvar
= find_equivalent_node (graph
, lhsvar
, lhslabel
);
2632 rhsvar
= find_equivalent_node (graph
, rhsvar
, rhslabel
);
2633 c
->lhs
.var
= lhsvar
;
2634 c
->rhs
.var
= rhsvar
;
2638 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2639 part of an SCC, false otherwise. */
2642 eliminate_indirect_cycles (unsigned int node
)
2644 if (graph
->indirect_cycles
[node
] != -1
2645 && !bitmap_empty_p (get_varinfo (node
)->solution
))
2648 auto_vec
<unsigned> queue
;
2650 unsigned int to
= find (graph
->indirect_cycles
[node
]);
2653 /* We can't touch the solution set and call unify_nodes
2654 at the same time, because unify_nodes is going to do
2655 bitmap unions into it. */
2657 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node
)->solution
, 0, i
, bi
)
2659 if (find (i
) == i
&& i
!= to
)
2662 queue
.safe_push (i
);
2667 queue
.iterate (queuepos
, &i
);
2670 unify_nodes (graph
, to
, i
, true);
2677 /* Solve the constraint graph GRAPH using our worklist solver.
2678 This is based on the PW* family of solvers from the "Efficient Field
2679 Sensitive Pointer Analysis for C" paper.
2680 It works by iterating over all the graph nodes, processing the complex
2681 constraints and propagating the copy constraints, until everything stops
2682 changed. This corresponds to steps 6-8 in the solving list given above. */
2685 solve_graph (constraint_graph_t graph
)
2687 unsigned int size
= graph
->size
;
2691 changed
= BITMAP_ALLOC (NULL
);
2693 /* Mark all initial non-collapsed nodes as changed. */
2694 for (i
= 1; i
< size
; i
++)
2696 varinfo_t ivi
= get_varinfo (i
);
2697 if (find (i
) == i
&& !bitmap_empty_p (ivi
->solution
)
2698 && ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
2699 || graph
->complex[i
].length () > 0))
2700 bitmap_set_bit (changed
, i
);
2703 /* Allocate a bitmap to be used to store the changed bits. */
2704 pts
= BITMAP_ALLOC (&pta_obstack
);
2706 while (!bitmap_empty_p (changed
))
2709 struct topo_info
*ti
= init_topo_info ();
2712 bitmap_obstack_initialize (&iteration_obstack
);
2714 compute_topo_order (graph
, ti
);
2716 while (ti
->topo_order
.length () != 0)
2719 i
= ti
->topo_order
.pop ();
2721 /* If this variable is not a representative, skip it. */
2725 /* In certain indirect cycle cases, we may merge this
2726 variable to another. */
2727 if (eliminate_indirect_cycles (i
) && find (i
) != i
)
2730 /* If the node has changed, we need to process the
2731 complex constraints and outgoing edges again. */
2732 if (bitmap_clear_bit (changed
, i
))
2737 vec
<constraint_t
> complex = graph
->complex[i
];
2738 varinfo_t vi
= get_varinfo (i
);
2739 bool solution_empty
;
2741 /* Compute the changed set of solution bits. If anything
2742 is in the solution just propagate that. */
2743 if (bitmap_bit_p (vi
->solution
, anything_id
))
2745 /* If anything is also in the old solution there is
2747 ??? But we shouldn't ended up with "changed" set ... */
2749 && bitmap_bit_p (vi
->oldsolution
, anything_id
))
2751 bitmap_copy (pts
, get_varinfo (find (anything_id
))->solution
);
2753 else if (vi
->oldsolution
)
2754 bitmap_and_compl (pts
, vi
->solution
, vi
->oldsolution
);
2756 bitmap_copy (pts
, vi
->solution
);
2758 if (bitmap_empty_p (pts
))
2761 if (vi
->oldsolution
)
2762 bitmap_ior_into (vi
->oldsolution
, pts
);
2765 vi
->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
2766 bitmap_copy (vi
->oldsolution
, pts
);
2769 solution
= vi
->solution
;
2770 solution_empty
= bitmap_empty_p (solution
);
2772 /* Process the complex constraints */
2773 bitmap expanded_pts
= NULL
;
2774 FOR_EACH_VEC_ELT (complex, j
, c
)
2776 /* XXX: This is going to unsort the constraints in
2777 some cases, which will occasionally add duplicate
2778 constraints during unification. This does not
2779 affect correctness. */
2780 c
->lhs
.var
= find (c
->lhs
.var
);
2781 c
->rhs
.var
= find (c
->rhs
.var
);
2783 /* The only complex constraint that can change our
2784 solution to non-empty, given an empty solution,
2785 is a constraint where the lhs side is receiving
2786 some set from elsewhere. */
2787 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2788 do_complex_constraint (graph
, c
, pts
, &expanded_pts
);
2790 BITMAP_FREE (expanded_pts
);
2792 solution_empty
= bitmap_empty_p (solution
);
2794 if (!solution_empty
)
2797 unsigned eff_escaped_id
= find (escaped_id
);
2799 /* Propagate solution to all successors. */
2800 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
2806 unsigned int to
= find (j
);
2807 tmp
= get_varinfo (to
)->solution
;
2810 /* Don't try to propagate to ourselves. */
2814 /* If we propagate from ESCAPED use ESCAPED as
2816 if (i
== eff_escaped_id
)
2817 flag
= bitmap_set_bit (tmp
, escaped_id
);
2819 flag
= bitmap_ior_into (tmp
, pts
);
2822 bitmap_set_bit (changed
, to
);
2827 free_topo_info (ti
);
2828 bitmap_obstack_release (&iteration_obstack
);
2832 BITMAP_FREE (changed
);
2833 bitmap_obstack_release (&oldpta_obstack
);
2836 /* Map from trees to variable infos. */
2837 static hash_map
<tree
, varinfo_t
> *vi_for_tree
;
2840 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2843 insert_vi_for_tree (tree t
, varinfo_t vi
)
2846 gcc_assert (!vi_for_tree
->put (t
, vi
));
2849 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2850 exist in the map, return NULL, otherwise, return the varinfo we found. */
2853 lookup_vi_for_tree (tree t
)
2855 varinfo_t
*slot
= vi_for_tree
->get (t
);
2862 /* Return a printable name for DECL */
2865 alias_get_name (tree decl
)
2867 const char *res
= NULL
;
2869 int num_printed
= 0;
2874 if (TREE_CODE (decl
) == SSA_NAME
)
2876 res
= get_name (decl
);
2878 num_printed
= asprintf (&temp
, "%s_%u", res
, SSA_NAME_VERSION (decl
));
2880 num_printed
= asprintf (&temp
, "_%u", SSA_NAME_VERSION (decl
));
2881 if (num_printed
> 0)
2883 res
= ggc_strdup (temp
);
2887 else if (DECL_P (decl
))
2889 if (DECL_ASSEMBLER_NAME_SET_P (decl
))
2890 res
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
2893 res
= get_name (decl
);
2896 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2897 if (num_printed
> 0)
2899 res
= ggc_strdup (temp
);
2911 /* Find the variable id for tree T in the map.
2912 If T doesn't exist in the map, create an entry for it and return it. */
2915 get_vi_for_tree (tree t
)
2917 varinfo_t
*slot
= vi_for_tree
->get (t
);
2919 return get_varinfo (create_variable_info_for (t
, alias_get_name (t
)));
2924 /* Get a scalar constraint expression for a new temporary variable. */
2926 static struct constraint_expr
2927 new_scalar_tmp_constraint_exp (const char *name
)
2929 struct constraint_expr tmp
;
2932 vi
= new_var_info (NULL_TREE
, name
);
2936 vi
->is_full_var
= 1;
2945 /* Get a constraint expression vector from an SSA_VAR_P node.
2946 If address_p is true, the result will be taken its address of. */
2949 get_constraint_for_ssa_var (tree t
, vec
<ce_s
> *results
, bool address_p
)
2951 struct constraint_expr cexpr
;
2954 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2955 gcc_assert (TREE_CODE (t
) == SSA_NAME
|| DECL_P (t
));
2957 /* For parameters, get at the points-to set for the actual parm
2959 if (TREE_CODE (t
) == SSA_NAME
2960 && SSA_NAME_IS_DEFAULT_DEF (t
)
2961 && (TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2962 || TREE_CODE (SSA_NAME_VAR (t
)) == RESULT_DECL
))
2964 get_constraint_for_ssa_var (SSA_NAME_VAR (t
), results
, address_p
);
2968 /* For global variables resort to the alias target. */
2969 if (TREE_CODE (t
) == VAR_DECL
2970 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
2972 varpool_node
*node
= varpool_node::get (t
);
2973 if (node
&& node
->alias
&& node
->analyzed
)
2975 node
= node
->ultimate_alias_target ();
2980 vi
= get_vi_for_tree (t
);
2982 cexpr
.type
= SCALAR
;
2985 /* If we are not taking the address of the constraint expr, add all
2986 sub-fiels of the variable as well. */
2988 && !vi
->is_full_var
)
2990 for (; vi
; vi
= vi_next (vi
))
2993 results
->safe_push (cexpr
);
2998 results
->safe_push (cexpr
);
3001 /* Process constraint T, performing various simplifications and then
3002 adding it to our list of overall constraints. */
3005 process_constraint (constraint_t t
)
3007 struct constraint_expr rhs
= t
->rhs
;
3008 struct constraint_expr lhs
= t
->lhs
;
3010 gcc_assert (rhs
.var
< varmap
.length ());
3011 gcc_assert (lhs
.var
< varmap
.length ());
3013 /* If we didn't get any useful constraint from the lhs we get
3014 &ANYTHING as fallback from get_constraint_for. Deal with
3015 it here by turning it into *ANYTHING. */
3016 if (lhs
.type
== ADDRESSOF
3017 && lhs
.var
== anything_id
)
3020 /* ADDRESSOF on the lhs is invalid. */
3021 gcc_assert (lhs
.type
!= ADDRESSOF
);
3023 /* We shouldn't add constraints from things that cannot have pointers.
3024 It's not completely trivial to avoid in the callers, so do it here. */
3025 if (rhs
.type
!= ADDRESSOF
3026 && !get_varinfo (rhs
.var
)->may_have_pointers
)
3029 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3030 if (!get_varinfo (lhs
.var
)->may_have_pointers
)
3033 /* This can happen in our IR with things like n->a = *p */
3034 if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
3036 /* Split into tmp = *rhs, *lhs = tmp */
3037 struct constraint_expr tmplhs
;
3038 tmplhs
= new_scalar_tmp_constraint_exp ("doubledereftmp");
3039 process_constraint (new_constraint (tmplhs
, rhs
));
3040 process_constraint (new_constraint (lhs
, tmplhs
));
3042 else if (rhs
.type
== ADDRESSOF
&& lhs
.type
== DEREF
)
3044 /* Split into tmp = &rhs, *lhs = tmp */
3045 struct constraint_expr tmplhs
;
3046 tmplhs
= new_scalar_tmp_constraint_exp ("derefaddrtmp");
3047 process_constraint (new_constraint (tmplhs
, rhs
));
3048 process_constraint (new_constraint (lhs
, tmplhs
));
3052 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
3053 constraints
.safe_push (t
);
3058 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3061 static HOST_WIDE_INT
3062 bitpos_of_field (const tree fdecl
)
3064 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl
))
3065 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl
)))
3068 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl
)) * BITS_PER_UNIT
3069 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl
)));
3073 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3074 resulting constraint expressions in *RESULTS. */
3077 get_constraint_for_ptr_offset (tree ptr
, tree offset
,
3080 struct constraint_expr c
;
3082 HOST_WIDE_INT rhsoffset
;
3084 /* If we do not do field-sensitive PTA adding offsets to pointers
3085 does not change the points-to solution. */
3086 if (!use_field_sensitive
)
3088 get_constraint_for_rhs (ptr
, results
);
3092 /* If the offset is not a non-negative integer constant that fits
3093 in a HOST_WIDE_INT, we have to fall back to a conservative
3094 solution which includes all sub-fields of all pointed-to
3095 variables of ptr. */
3096 if (offset
== NULL_TREE
3097 || TREE_CODE (offset
) != INTEGER_CST
)
3098 rhsoffset
= UNKNOWN_OFFSET
;
3101 /* Sign-extend the offset. */
3102 offset_int soffset
= offset_int::from (offset
, SIGNED
);
3103 if (!wi::fits_shwi_p (soffset
))
3104 rhsoffset
= UNKNOWN_OFFSET
;
3107 /* Make sure the bit-offset also fits. */
3108 HOST_WIDE_INT rhsunitoffset
= soffset
.to_shwi ();
3109 rhsoffset
= rhsunitoffset
* BITS_PER_UNIT
;
3110 if (rhsunitoffset
!= rhsoffset
/ BITS_PER_UNIT
)
3111 rhsoffset
= UNKNOWN_OFFSET
;
3115 get_constraint_for_rhs (ptr
, results
);
3119 /* As we are eventually appending to the solution do not use
3120 vec::iterate here. */
3121 n
= results
->length ();
3122 for (j
= 0; j
< n
; j
++)
3126 curr
= get_varinfo (c
.var
);
3128 if (c
.type
== ADDRESSOF
3129 /* If this varinfo represents a full variable just use it. */
3130 && curr
->is_full_var
)
3132 else if (c
.type
== ADDRESSOF
3133 /* If we do not know the offset add all subfields. */
3134 && rhsoffset
== UNKNOWN_OFFSET
)
3136 varinfo_t temp
= get_varinfo (curr
->head
);
3139 struct constraint_expr c2
;
3141 c2
.type
= ADDRESSOF
;
3143 if (c2
.var
!= c
.var
)
3144 results
->safe_push (c2
);
3145 temp
= vi_next (temp
);
3149 else if (c
.type
== ADDRESSOF
)
3152 unsigned HOST_WIDE_INT offset
= curr
->offset
+ rhsoffset
;
3154 /* If curr->offset + rhsoffset is less than zero adjust it. */
3156 && curr
->offset
< offset
)
3159 /* We have to include all fields that overlap the current
3160 field shifted by rhsoffset. And we include at least
3161 the last or the first field of the variable to represent
3162 reachability of off-bound addresses, in particular &object + 1,
3163 conservatively correct. */
3164 temp
= first_or_preceding_vi_for_offset (curr
, offset
);
3167 temp
= vi_next (temp
);
3169 && temp
->offset
< offset
+ curr
->size
)
3171 struct constraint_expr c2
;
3173 c2
.type
= ADDRESSOF
;
3175 results
->safe_push (c2
);
3176 temp
= vi_next (temp
);
3179 else if (c
.type
== SCALAR
)
3181 gcc_assert (c
.offset
== 0);
3182 c
.offset
= rhsoffset
;
3185 /* We shouldn't get any DEREFs here. */
3193 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3194 If address_p is true the result will be taken its address of.
3195 If lhs_p is true then the constraint expression is assumed to be used
3199 get_constraint_for_component_ref (tree t
, vec
<ce_s
> *results
,
3200 bool address_p
, bool lhs_p
)
3203 HOST_WIDE_INT bitsize
= -1;
3204 HOST_WIDE_INT bitmaxsize
= -1;
3205 HOST_WIDE_INT bitpos
;
3209 /* Some people like to do cute things like take the address of
3212 while (handled_component_p (forzero
)
3213 || INDIRECT_REF_P (forzero
)
3214 || TREE_CODE (forzero
) == MEM_REF
)
3215 forzero
= TREE_OPERAND (forzero
, 0);
3217 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
3219 struct constraint_expr temp
;
3222 temp
.var
= integer_id
;
3224 results
->safe_push (temp
);
3228 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
, &reverse
);
3230 /* Pretend to take the address of the base, we'll take care of
3231 adding the required subset of sub-fields below. */
3232 get_constraint_for_1 (t
, results
, true, lhs_p
);
3233 gcc_assert (results
->length () == 1);
3234 struct constraint_expr
&result
= results
->last ();
3236 if (result
.type
== SCALAR
3237 && get_varinfo (result
.var
)->is_full_var
)
3238 /* For single-field vars do not bother about the offset. */
3240 else if (result
.type
== SCALAR
)
3242 /* In languages like C, you can access one past the end of an
3243 array. You aren't allowed to dereference it, so we can
3244 ignore this constraint. When we handle pointer subtraction,
3245 we may have to do something cute here. */
3247 if ((unsigned HOST_WIDE_INT
)bitpos
< get_varinfo (result
.var
)->fullsize
3250 /* It's also not true that the constraint will actually start at the
3251 right offset, it may start in some padding. We only care about
3252 setting the constraint to the first actual field it touches, so
3254 struct constraint_expr cexpr
= result
;
3258 for (curr
= get_varinfo (cexpr
.var
); curr
; curr
= vi_next (curr
))
3260 if (ranges_overlap_p (curr
->offset
, curr
->size
,
3261 bitpos
, bitmaxsize
))
3263 cexpr
.var
= curr
->id
;
3264 results
->safe_push (cexpr
);
3269 /* If we are going to take the address of this field then
3270 to be able to compute reachability correctly add at least
3271 the last field of the variable. */
3272 if (address_p
&& results
->length () == 0)
3274 curr
= get_varinfo (cexpr
.var
);
3275 while (curr
->next
!= 0)
3276 curr
= vi_next (curr
);
3277 cexpr
.var
= curr
->id
;
3278 results
->safe_push (cexpr
);
3280 else if (results
->length () == 0)
3281 /* Assert that we found *some* field there. The user couldn't be
3282 accessing *only* padding. */
3283 /* Still the user could access one past the end of an array
3284 embedded in a struct resulting in accessing *only* padding. */
3285 /* Or accessing only padding via type-punning to a type
3286 that has a filed just in padding space. */
3288 cexpr
.type
= SCALAR
;
3289 cexpr
.var
= anything_id
;
3291 results
->safe_push (cexpr
);
3294 else if (bitmaxsize
== 0)
3296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3297 fprintf (dump_file
, "Access to zero-sized part of variable,"
3301 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3302 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
3304 else if (result
.type
== DEREF
)
3306 /* If we do not know exactly where the access goes say so. Note
3307 that only for non-structure accesses we know that we access
3308 at most one subfiled of any variable. */
3310 || bitsize
!= bitmaxsize
3311 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t
))
3312 || result
.offset
== UNKNOWN_OFFSET
)
3313 result
.offset
= UNKNOWN_OFFSET
;
3315 result
.offset
+= bitpos
;
3317 else if (result
.type
== ADDRESSOF
)
3319 /* We can end up here for component references on a
3320 VIEW_CONVERT_EXPR <>(&foobar). */
3321 result
.type
= SCALAR
;
3322 result
.var
= anything_id
;
3330 /* Dereference the constraint expression CONS, and return the result.
3331 DEREF (ADDRESSOF) = SCALAR
3332 DEREF (SCALAR) = DEREF
3333 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3334 This is needed so that we can handle dereferencing DEREF constraints. */
3337 do_deref (vec
<ce_s
> *constraints
)
3339 struct constraint_expr
*c
;
3342 FOR_EACH_VEC_ELT (*constraints
, i
, c
)
3344 if (c
->type
== SCALAR
)
3346 else if (c
->type
== ADDRESSOF
)
3348 else if (c
->type
== DEREF
)
3350 struct constraint_expr tmplhs
;
3351 tmplhs
= new_scalar_tmp_constraint_exp ("dereftmp");
3352 process_constraint (new_constraint (tmplhs
, *c
));
3353 c
->var
= tmplhs
.var
;
3360 /* Given a tree T, return the constraint expression for taking the
3364 get_constraint_for_address_of (tree t
, vec
<ce_s
> *results
)
3366 struct constraint_expr
*c
;
3369 get_constraint_for_1 (t
, results
, true, true);
3371 FOR_EACH_VEC_ELT (*results
, i
, c
)
3373 if (c
->type
== DEREF
)
3376 c
->type
= ADDRESSOF
;
3380 /* Given a tree T, return the constraint expression for it. */
3383 get_constraint_for_1 (tree t
, vec
<ce_s
> *results
, bool address_p
,
3386 struct constraint_expr temp
;
3388 /* x = integer is all glommed to a single variable, which doesn't
3389 point to anything by itself. That is, of course, unless it is an
3390 integer constant being treated as a pointer, in which case, we
3391 will return that this is really the addressof anything. This
3392 happens below, since it will fall into the default case. The only
3393 case we know something about an integer treated like a pointer is
3394 when it is the NULL pointer, and then we just say it points to
3397 Do not do that if -fno-delete-null-pointer-checks though, because
3398 in that case *NULL does not fail, so it _should_ alias *anything.
3399 It is not worth adding a new option or renaming the existing one,
3400 since this case is relatively obscure. */
3401 if ((TREE_CODE (t
) == INTEGER_CST
3402 && integer_zerop (t
))
3403 /* The only valid CONSTRUCTORs in gimple with pointer typed
3404 elements are zero-initializer. But in IPA mode we also
3405 process global initializers, so verify at least. */
3406 || (TREE_CODE (t
) == CONSTRUCTOR
3407 && CONSTRUCTOR_NELTS (t
) == 0))
3409 if (flag_delete_null_pointer_checks
)
3410 temp
.var
= nothing_id
;
3412 temp
.var
= nonlocal_id
;
3413 temp
.type
= ADDRESSOF
;
3415 results
->safe_push (temp
);
3419 /* String constants are read-only, ideally we'd have a CONST_DECL
3421 if (TREE_CODE (t
) == STRING_CST
)
3423 temp
.var
= string_id
;
3426 results
->safe_push (temp
);
3430 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
3432 case tcc_expression
:
3434 switch (TREE_CODE (t
))
3437 get_constraint_for_address_of (TREE_OPERAND (t
, 0), results
);
3445 switch (TREE_CODE (t
))
3449 struct constraint_expr cs
;
3451 get_constraint_for_ptr_offset (TREE_OPERAND (t
, 0),
3452 TREE_OPERAND (t
, 1), results
);
3455 /* If we are not taking the address then make sure to process
3456 all subvariables we might access. */
3460 cs
= results
->last ();
3461 if (cs
.type
== DEREF
3462 && type_can_have_subvars (TREE_TYPE (t
)))
3464 /* For dereferences this means we have to defer it
3466 results
->last ().offset
= UNKNOWN_OFFSET
;
3469 if (cs
.type
!= SCALAR
)
3472 vi
= get_varinfo (cs
.var
);
3473 curr
= vi_next (vi
);
3474 if (!vi
->is_full_var
3477 unsigned HOST_WIDE_INT size
;
3478 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t
))))
3479 size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t
)));
3482 for (; curr
; curr
= vi_next (curr
))
3484 if (curr
->offset
- vi
->offset
< size
)
3487 results
->safe_push (cs
);
3496 case ARRAY_RANGE_REF
:
3501 get_constraint_for_component_ref (t
, results
, address_p
, lhs_p
);
3503 case VIEW_CONVERT_EXPR
:
3504 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, address_p
,
3507 /* We are missing handling for TARGET_MEM_REF here. */
3512 case tcc_exceptional
:
3514 switch (TREE_CODE (t
))
3518 get_constraint_for_ssa_var (t
, results
, address_p
);
3526 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t
), i
, val
)
3528 struct constraint_expr
*rhsp
;
3530 get_constraint_for_1 (val
, &tmp
, address_p
, lhs_p
);
3531 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
3532 results
->safe_push (*rhsp
);
3535 /* We do not know whether the constructor was complete,
3536 so technically we have to add &NOTHING or &ANYTHING
3537 like we do for an empty constructor as well. */
3544 case tcc_declaration
:
3546 get_constraint_for_ssa_var (t
, results
, address_p
);
3551 /* We cannot refer to automatic variables through constants. */
3552 temp
.type
= ADDRESSOF
;
3553 temp
.var
= nonlocal_id
;
3555 results
->safe_push (temp
);
3561 /* The default fallback is a constraint from anything. */
3562 temp
.type
= ADDRESSOF
;
3563 temp
.var
= anything_id
;
3565 results
->safe_push (temp
);
3568 /* Given a gimple tree T, return the constraint expression vector for it. */
3571 get_constraint_for (tree t
, vec
<ce_s
> *results
)
3573 gcc_assert (results
->length () == 0);
3575 get_constraint_for_1 (t
, results
, false, true);
3578 /* Given a gimple tree T, return the constraint expression vector for it
3579 to be used as the rhs of a constraint. */
3582 get_constraint_for_rhs (tree t
, vec
<ce_s
> *results
)
3584 gcc_assert (results
->length () == 0);
3586 get_constraint_for_1 (t
, results
, false, false);
3590 /* Efficiently generates constraints from all entries in *RHSC to all
3591 entries in *LHSC. */
3594 process_all_all_constraints (vec
<ce_s
> lhsc
,
3597 struct constraint_expr
*lhsp
, *rhsp
;
3600 if (lhsc
.length () <= 1 || rhsc
.length () <= 1)
3602 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3603 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
3604 process_constraint (new_constraint (*lhsp
, *rhsp
));
3608 struct constraint_expr tmp
;
3609 tmp
= new_scalar_tmp_constraint_exp ("allalltmp");
3610 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
3611 process_constraint (new_constraint (tmp
, *rhsp
));
3612 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
3613 process_constraint (new_constraint (*lhsp
, tmp
));
3617 /* Handle aggregate copies by expanding into copies of the respective
3618 fields of the structures. */
3621 do_structure_copy (tree lhsop
, tree rhsop
)
3623 struct constraint_expr
*lhsp
, *rhsp
;
3624 auto_vec
<ce_s
> lhsc
;
3625 auto_vec
<ce_s
> rhsc
;
3628 get_constraint_for (lhsop
, &lhsc
);
3629 get_constraint_for_rhs (rhsop
, &rhsc
);
3632 if (lhsp
->type
== DEREF
3633 || (lhsp
->type
== ADDRESSOF
&& lhsp
->var
== anything_id
)
3634 || rhsp
->type
== DEREF
)
3636 if (lhsp
->type
== DEREF
)
3638 gcc_assert (lhsc
.length () == 1);
3639 lhsp
->offset
= UNKNOWN_OFFSET
;
3641 if (rhsp
->type
== DEREF
)
3643 gcc_assert (rhsc
.length () == 1);
3644 rhsp
->offset
= UNKNOWN_OFFSET
;
3646 process_all_all_constraints (lhsc
, rhsc
);
3648 else if (lhsp
->type
== SCALAR
3649 && (rhsp
->type
== SCALAR
3650 || rhsp
->type
== ADDRESSOF
))
3652 HOST_WIDE_INT lhssize
, lhsmaxsize
, lhsoffset
;
3653 HOST_WIDE_INT rhssize
, rhsmaxsize
, rhsoffset
;
3656 get_ref_base_and_extent (lhsop
, &lhsoffset
, &lhssize
, &lhsmaxsize
,
3658 get_ref_base_and_extent (rhsop
, &rhsoffset
, &rhssize
, &rhsmaxsize
,
3660 for (j
= 0; lhsc
.iterate (j
, &lhsp
);)
3662 varinfo_t lhsv
, rhsv
;
3664 lhsv
= get_varinfo (lhsp
->var
);
3665 rhsv
= get_varinfo (rhsp
->var
);
3666 if (lhsv
->may_have_pointers
3667 && (lhsv
->is_full_var
3668 || rhsv
->is_full_var
3669 || ranges_overlap_p (lhsv
->offset
+ rhsoffset
, lhsv
->size
,
3670 rhsv
->offset
+ lhsoffset
, rhsv
->size
)))
3671 process_constraint (new_constraint (*lhsp
, *rhsp
));
3672 if (!rhsv
->is_full_var
3673 && (lhsv
->is_full_var
3674 || (lhsv
->offset
+ rhsoffset
+ lhsv
->size
3675 > rhsv
->offset
+ lhsoffset
+ rhsv
->size
)))
3678 if (k
>= rhsc
.length ())
3689 /* Create constraints ID = { rhsc }. */
3692 make_constraints_to (unsigned id
, vec
<ce_s
> rhsc
)
3694 struct constraint_expr
*c
;
3695 struct constraint_expr includes
;
3699 includes
.offset
= 0;
3700 includes
.type
= SCALAR
;
3702 FOR_EACH_VEC_ELT (rhsc
, j
, c
)
3703 process_constraint (new_constraint (includes
, *c
));
3706 /* Create a constraint ID = OP. */
3709 make_constraint_to (unsigned id
, tree op
)
3711 auto_vec
<ce_s
> rhsc
;
3712 get_constraint_for_rhs (op
, &rhsc
);
3713 make_constraints_to (id
, rhsc
);
3716 /* Create a constraint ID = &FROM. */
3719 make_constraint_from (varinfo_t vi
, int from
)
3721 struct constraint_expr lhs
, rhs
;
3729 rhs
.type
= ADDRESSOF
;
3730 process_constraint (new_constraint (lhs
, rhs
));
3733 /* Create a constraint ID = FROM. */
3736 make_copy_constraint (varinfo_t vi
, int from
)
3738 struct constraint_expr lhs
, rhs
;
3747 process_constraint (new_constraint (lhs
, rhs
));
3750 /* Make constraints necessary to make OP escape. */
3753 make_escape_constraint (tree op
)
3755 make_constraint_to (escaped_id
, op
);
3758 /* Add constraints to that the solution of VI is transitively closed. */
3761 make_transitive_closure_constraints (varinfo_t vi
)
3763 struct constraint_expr lhs
, rhs
;
3771 rhs
.offset
= UNKNOWN_OFFSET
;
3772 process_constraint (new_constraint (lhs
, rhs
));
3775 /* Temporary storage for fake var decls. */
3776 struct obstack fake_var_decl_obstack
;
3778 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3781 build_fake_var_decl (tree type
)
3783 tree decl
= (tree
) XOBNEW (&fake_var_decl_obstack
, struct tree_var_decl
);
3784 memset (decl
, 0, sizeof (struct tree_var_decl
));
3785 TREE_SET_CODE (decl
, VAR_DECL
);
3786 TREE_TYPE (decl
) = type
;
3787 DECL_UID (decl
) = allocate_decl_uid ();
3788 SET_DECL_PT_UID (decl
, -1);
3789 layout_decl (decl
, 0);
3793 /* Create a new artificial heap variable with NAME.
3794 Return the created variable. */
3797 make_heapvar (const char *name
)
3802 heapvar
= build_fake_var_decl (ptr_type_node
);
3803 DECL_EXTERNAL (heapvar
) = 1;
3805 vi
= new_var_info (heapvar
, name
);
3806 vi
->is_artificial_var
= true;
3807 vi
->is_heap_var
= true;
3808 vi
->is_unknown_size_var
= true;
3812 vi
->is_full_var
= true;
3813 insert_vi_for_tree (heapvar
, vi
);
3818 /* Create a new artificial heap variable with NAME and make a
3819 constraint from it to LHS. Set flags according to a tag used
3820 for tracking restrict pointers. */
3823 make_constraint_from_restrict (varinfo_t lhs
, const char *name
)
3825 varinfo_t vi
= make_heapvar (name
);
3826 vi
->is_restrict_var
= 1;
3827 vi
->is_global_var
= 1;
3828 vi
->may_have_pointers
= 1;
3829 make_constraint_from (lhs
, vi
->id
);
3833 /* Create a new artificial heap variable with NAME and make a
3834 constraint from it to LHS. Set flags according to a tag used
3835 for tracking restrict pointers and make the artificial heap
3836 point to global memory. */
3839 make_constraint_from_global_restrict (varinfo_t lhs
, const char *name
)
3841 varinfo_t vi
= make_constraint_from_restrict (lhs
, name
);
3842 make_copy_constraint (vi
, nonlocal_id
);
3846 /* In IPA mode there are varinfos for different aspects of reach
3847 function designator. One for the points-to set of the return
3848 value, one for the variables that are clobbered by the function,
3849 one for its uses and one for each parameter (including a single
3850 glob for remaining variadic arguments). */
3852 enum { fi_clobbers
= 1, fi_uses
= 2,
3853 fi_static_chain
= 3, fi_result
= 4, fi_parm_base
= 5 };
3855 /* Get a constraint for the requested part of a function designator FI
3856 when operating in IPA mode. */
3858 static struct constraint_expr
3859 get_function_part_constraint (varinfo_t fi
, unsigned part
)
3861 struct constraint_expr c
;
3863 gcc_assert (in_ipa_mode
);
3865 if (fi
->id
== anything_id
)
3867 /* ??? We probably should have a ANYFN special variable. */
3868 c
.var
= anything_id
;
3872 else if (TREE_CODE (fi
->decl
) == FUNCTION_DECL
)
3874 varinfo_t ai
= first_vi_for_offset (fi
, part
);
3878 c
.var
= anything_id
;
3892 /* For non-IPA mode, generate constraints necessary for a call on the
3896 handle_rhs_call (gcall
*stmt
, vec
<ce_s
> *results
)
3898 struct constraint_expr rhsc
;
3900 bool returns_uses
= false;
3902 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3904 tree arg
= gimple_call_arg (stmt
, i
);
3905 int flags
= gimple_call_arg_flags (stmt
, i
);
3907 /* If the argument is not used we can ignore it. */
3908 if (flags
& EAF_UNUSED
)
3911 /* As we compute ESCAPED context-insensitive we do not gain
3912 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3913 set. The argument would still get clobbered through the
3915 if ((flags
& EAF_NOCLOBBER
)
3916 && (flags
& EAF_NOESCAPE
))
3918 varinfo_t uses
= get_call_use_vi (stmt
);
3919 if (!(flags
& EAF_DIRECT
))
3921 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg");
3922 make_constraint_to (tem
->id
, arg
);
3923 make_transitive_closure_constraints (tem
);
3924 make_copy_constraint (uses
, tem
->id
);
3927 make_constraint_to (uses
->id
, arg
);
3928 returns_uses
= true;
3930 else if (flags
& EAF_NOESCAPE
)
3932 struct constraint_expr lhs
, rhs
;
3933 varinfo_t uses
= get_call_use_vi (stmt
);
3934 varinfo_t clobbers
= get_call_clobber_vi (stmt
);
3935 varinfo_t tem
= new_var_info (NULL_TREE
, "callarg");
3936 make_constraint_to (tem
->id
, arg
);
3937 if (!(flags
& EAF_DIRECT
))
3938 make_transitive_closure_constraints (tem
);
3939 make_copy_constraint (uses
, tem
->id
);
3940 make_copy_constraint (clobbers
, tem
->id
);
3941 /* Add *tem = nonlocal, do not add *tem = callused as
3942 EAF_NOESCAPE parameters do not escape to other parameters
3943 and all other uses appear in NONLOCAL as well. */
3948 rhs
.var
= nonlocal_id
;
3950 process_constraint (new_constraint (lhs
, rhs
));
3951 returns_uses
= true;
3954 make_escape_constraint (arg
);
3957 /* If we added to the calls uses solution make sure we account for
3958 pointers to it to be returned. */
3961 rhsc
.var
= get_call_use_vi (stmt
)->id
;
3964 results
->safe_push (rhsc
);
3967 /* The static chain escapes as well. */
3968 if (gimple_call_chain (stmt
))
3969 make_escape_constraint (gimple_call_chain (stmt
));
3971 /* And if we applied NRV the address of the return slot escapes as well. */
3972 if (gimple_call_return_slot_opt_p (stmt
)
3973 && gimple_call_lhs (stmt
) != NULL_TREE
3974 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
3976 auto_vec
<ce_s
> tmpc
;
3977 struct constraint_expr lhsc
, *c
;
3978 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
3979 lhsc
.var
= escaped_id
;
3982 FOR_EACH_VEC_ELT (tmpc
, i
, c
)
3983 process_constraint (new_constraint (lhsc
, *c
));
3986 /* Regular functions return nonlocal memory. */
3987 rhsc
.var
= nonlocal_id
;
3990 results
->safe_push (rhsc
);
3993 /* For non-IPA mode, generate constraints necessary for a call
3994 that returns a pointer and assigns it to LHS. This simply makes
3995 the LHS point to global and escaped variables. */
3998 handle_lhs_call (gcall
*stmt
, tree lhs
, int flags
, vec
<ce_s
> rhsc
,
4001 auto_vec
<ce_s
> lhsc
;
4003 get_constraint_for (lhs
, &lhsc
);
4004 /* If the store is to a global decl make sure to
4005 add proper escape constraints. */
4006 lhs
= get_base_address (lhs
);
4009 && is_global_var (lhs
))
4011 struct constraint_expr tmpc
;
4012 tmpc
.var
= escaped_id
;
4015 lhsc
.safe_push (tmpc
);
4018 /* If the call returns an argument unmodified override the rhs
4020 if (flags
& ERF_RETURNS_ARG
4021 && (flags
& ERF_RETURN_ARG_MASK
) < gimple_call_num_args (stmt
))
4025 arg
= gimple_call_arg (stmt
, flags
& ERF_RETURN_ARG_MASK
);
4026 get_constraint_for (arg
, &rhsc
);
4027 process_all_all_constraints (lhsc
, rhsc
);
4030 else if (flags
& ERF_NOALIAS
)
4033 struct constraint_expr tmpc
;
4035 vi
= make_heapvar ("HEAP");
4036 /* We are marking allocated storage local, we deal with it becoming
4037 global by escaping and setting of vars_contains_escaped_heap. */
4038 DECL_EXTERNAL (vi
->decl
) = 0;
4039 vi
->is_global_var
= 0;
4040 /* If this is not a real malloc call assume the memory was
4041 initialized and thus may point to global memory. All
4042 builtin functions with the malloc attribute behave in a sane way. */
4044 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
4045 make_constraint_from (vi
, nonlocal_id
);
4048 tmpc
.type
= ADDRESSOF
;
4049 rhsc
.safe_push (tmpc
);
4050 process_all_all_constraints (lhsc
, rhsc
);
4054 process_all_all_constraints (lhsc
, rhsc
);
4057 /* For non-IPA mode, generate constraints necessary for a call of a
4058 const function that returns a pointer in the statement STMT. */
4061 handle_const_call (gcall
*stmt
, vec
<ce_s
> *results
)
4063 struct constraint_expr rhsc
;
4066 /* Treat nested const functions the same as pure functions as far
4067 as the static chain is concerned. */
4068 if (gimple_call_chain (stmt
))
4070 varinfo_t uses
= get_call_use_vi (stmt
);
4071 make_transitive_closure_constraints (uses
);
4072 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4073 rhsc
.var
= uses
->id
;
4076 results
->safe_push (rhsc
);
4079 /* May return arguments. */
4080 for (k
= 0; k
< gimple_call_num_args (stmt
); ++k
)
4082 tree arg
= gimple_call_arg (stmt
, k
);
4083 auto_vec
<ce_s
> argc
;
4085 struct constraint_expr
*argp
;
4086 get_constraint_for_rhs (arg
, &argc
);
4087 FOR_EACH_VEC_ELT (argc
, i
, argp
)
4088 results
->safe_push (*argp
);
4091 /* May return addresses of globals. */
4092 rhsc
.var
= nonlocal_id
;
4094 rhsc
.type
= ADDRESSOF
;
4095 results
->safe_push (rhsc
);
4098 /* For non-IPA mode, generate constraints necessary for a call to a
4099 pure function in statement STMT. */
4102 handle_pure_call (gcall
*stmt
, vec
<ce_s
> *results
)
4104 struct constraint_expr rhsc
;
4106 varinfo_t uses
= NULL
;
4108 /* Memory reached from pointer arguments is call-used. */
4109 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
4111 tree arg
= gimple_call_arg (stmt
, i
);
4114 uses
= get_call_use_vi (stmt
);
4115 make_transitive_closure_constraints (uses
);
4117 make_constraint_to (uses
->id
, arg
);
4120 /* The static chain is used as well. */
4121 if (gimple_call_chain (stmt
))
4125 uses
= get_call_use_vi (stmt
);
4126 make_transitive_closure_constraints (uses
);
4128 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
4131 /* Pure functions may return call-used and nonlocal memory. */
4134 rhsc
.var
= uses
->id
;
4137 results
->safe_push (rhsc
);
4139 rhsc
.var
= nonlocal_id
;
4142 results
->safe_push (rhsc
);
4146 /* Return the varinfo for the callee of CALL. */
4149 get_fi_for_callee (gcall
*call
)
4151 tree decl
, fn
= gimple_call_fn (call
);
4153 if (fn
&& TREE_CODE (fn
) == OBJ_TYPE_REF
)
4154 fn
= OBJ_TYPE_REF_EXPR (fn
);
4156 /* If we can directly resolve the function being called, do so.
4157 Otherwise, it must be some sort of indirect expression that
4158 we should still be able to handle. */
4159 decl
= gimple_call_addr_fndecl (fn
);
4161 return get_vi_for_tree (decl
);
4163 /* If the function is anything other than a SSA name pointer we have no
4164 clue and should be getting ANYFN (well, ANYTHING for now). */
4165 if (!fn
|| TREE_CODE (fn
) != SSA_NAME
)
4166 return get_varinfo (anything_id
);
4168 if (SSA_NAME_IS_DEFAULT_DEF (fn
)
4169 && (TREE_CODE (SSA_NAME_VAR (fn
)) == PARM_DECL
4170 || TREE_CODE (SSA_NAME_VAR (fn
)) == RESULT_DECL
))
4171 fn
= SSA_NAME_VAR (fn
);
4173 return get_vi_for_tree (fn
);
4176 /* Create constraints for the builtin call T. Return true if the call
4177 was handled, otherwise false. */
4180 find_func_aliases_for_builtin_call (struct function
*fn
, gcall
*t
)
4182 tree fndecl
= gimple_call_fndecl (t
);
4183 auto_vec
<ce_s
, 2> lhsc
;
4184 auto_vec
<ce_s
, 4> rhsc
;
4187 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
4188 /* ??? All builtins that are handled here need to be handled
4189 in the alias-oracle query functions explicitly! */
4190 switch (DECL_FUNCTION_CODE (fndecl
))
4192 /* All the following functions return a pointer to the same object
4193 as their first argument points to. The functions do not add
4194 to the ESCAPED solution. The functions make the first argument
4195 pointed to memory point to what the second argument pointed to
4196 memory points to. */
4197 case BUILT_IN_STRCPY
:
4198 case BUILT_IN_STRNCPY
:
4199 case BUILT_IN_BCOPY
:
4200 case BUILT_IN_MEMCPY
:
4201 case BUILT_IN_MEMMOVE
:
4202 case BUILT_IN_MEMPCPY
:
4203 case BUILT_IN_STPCPY
:
4204 case BUILT_IN_STPNCPY
:
4205 case BUILT_IN_STRCAT
:
4206 case BUILT_IN_STRNCAT
:
4207 case BUILT_IN_STRCPY_CHK
:
4208 case BUILT_IN_STRNCPY_CHK
:
4209 case BUILT_IN_MEMCPY_CHK
:
4210 case BUILT_IN_MEMMOVE_CHK
:
4211 case BUILT_IN_MEMPCPY_CHK
:
4212 case BUILT_IN_STPCPY_CHK
:
4213 case BUILT_IN_STPNCPY_CHK
:
4214 case BUILT_IN_STRCAT_CHK
:
4215 case BUILT_IN_STRNCAT_CHK
:
4216 case BUILT_IN_TM_MEMCPY
:
4217 case BUILT_IN_TM_MEMMOVE
:
4219 tree res
= gimple_call_lhs (t
);
4220 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4221 == BUILT_IN_BCOPY
? 1 : 0));
4222 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
4223 == BUILT_IN_BCOPY
? 0 : 1));
4224 if (res
!= NULL_TREE
)
4226 get_constraint_for (res
, &lhsc
);
4227 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY
4228 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY
4229 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY
4230 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY_CHK
4231 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY_CHK
4232 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY_CHK
)
4233 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &rhsc
);
4235 get_constraint_for (dest
, &rhsc
);
4236 process_all_all_constraints (lhsc
, rhsc
);
4240 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4241 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4244 process_all_all_constraints (lhsc
, rhsc
);
4247 case BUILT_IN_MEMSET
:
4248 case BUILT_IN_MEMSET_CHK
:
4249 case BUILT_IN_TM_MEMSET
:
4251 tree res
= gimple_call_lhs (t
);
4252 tree dest
= gimple_call_arg (t
, 0);
4255 struct constraint_expr ac
;
4256 if (res
!= NULL_TREE
)
4258 get_constraint_for (res
, &lhsc
);
4259 get_constraint_for (dest
, &rhsc
);
4260 process_all_all_constraints (lhsc
, rhsc
);
4263 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4265 if (flag_delete_null_pointer_checks
4266 && integer_zerop (gimple_call_arg (t
, 1)))
4268 ac
.type
= ADDRESSOF
;
4269 ac
.var
= nothing_id
;
4274 ac
.var
= integer_id
;
4277 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4278 process_constraint (new_constraint (*lhsp
, ac
));
4281 case BUILT_IN_POSIX_MEMALIGN
:
4283 tree ptrptr
= gimple_call_arg (t
, 0);
4284 get_constraint_for (ptrptr
, &lhsc
);
4286 varinfo_t vi
= make_heapvar ("HEAP");
4287 /* We are marking allocated storage local, we deal with it becoming
4288 global by escaping and setting of vars_contains_escaped_heap. */
4289 DECL_EXTERNAL (vi
->decl
) = 0;
4290 vi
->is_global_var
= 0;
4291 struct constraint_expr tmpc
;
4294 tmpc
.type
= ADDRESSOF
;
4295 rhsc
.safe_push (tmpc
);
4296 process_all_all_constraints (lhsc
, rhsc
);
4299 case BUILT_IN_ASSUME_ALIGNED
:
4301 tree res
= gimple_call_lhs (t
);
4302 tree dest
= gimple_call_arg (t
, 0);
4303 if (res
!= NULL_TREE
)
4305 get_constraint_for (res
, &lhsc
);
4306 get_constraint_for (dest
, &rhsc
);
4307 process_all_all_constraints (lhsc
, rhsc
);
4311 /* All the following functions do not return pointers, do not
4312 modify the points-to sets of memory reachable from their
4313 arguments and do not add to the ESCAPED solution. */
4314 case BUILT_IN_SINCOS
:
4315 case BUILT_IN_SINCOSF
:
4316 case BUILT_IN_SINCOSL
:
4317 case BUILT_IN_FREXP
:
4318 case BUILT_IN_FREXPF
:
4319 case BUILT_IN_FREXPL
:
4320 case BUILT_IN_GAMMA_R
:
4321 case BUILT_IN_GAMMAF_R
:
4322 case BUILT_IN_GAMMAL_R
:
4323 case BUILT_IN_LGAMMA_R
:
4324 case BUILT_IN_LGAMMAF_R
:
4325 case BUILT_IN_LGAMMAL_R
:
4327 case BUILT_IN_MODFF
:
4328 case BUILT_IN_MODFL
:
4329 case BUILT_IN_REMQUO
:
4330 case BUILT_IN_REMQUOF
:
4331 case BUILT_IN_REMQUOL
:
4334 case BUILT_IN_STRDUP
:
4335 case BUILT_IN_STRNDUP
:
4336 case BUILT_IN_REALLOC
:
4337 if (gimple_call_lhs (t
))
4339 handle_lhs_call (t
, gimple_call_lhs (t
),
4340 gimple_call_return_flags (t
) | ERF_NOALIAS
,
4342 get_constraint_for_ptr_offset (gimple_call_lhs (t
),
4344 get_constraint_for_ptr_offset (gimple_call_arg (t
, 0),
4348 process_all_all_constraints (lhsc
, rhsc
);
4351 /* For realloc the resulting pointer can be equal to the
4352 argument as well. But only doing this wouldn't be
4353 correct because with ptr == 0 realloc behaves like malloc. */
4354 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_REALLOC
)
4356 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4357 get_constraint_for (gimple_call_arg (t
, 0), &rhsc
);
4358 process_all_all_constraints (lhsc
, rhsc
);
4363 /* String / character search functions return a pointer into the
4364 source string or NULL. */
4365 case BUILT_IN_INDEX
:
4366 case BUILT_IN_STRCHR
:
4367 case BUILT_IN_STRRCHR
:
4368 case BUILT_IN_MEMCHR
:
4369 case BUILT_IN_STRSTR
:
4370 case BUILT_IN_STRPBRK
:
4371 if (gimple_call_lhs (t
))
4373 tree src
= gimple_call_arg (t
, 0);
4374 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4375 constraint_expr nul
;
4376 nul
.var
= nothing_id
;
4378 nul
.type
= ADDRESSOF
;
4379 rhsc
.safe_push (nul
);
4380 get_constraint_for (gimple_call_lhs (t
), &lhsc
);
4381 process_all_all_constraints (lhsc
, rhsc
);
4384 /* Trampolines are special - they set up passing the static
4386 case BUILT_IN_INIT_TRAMPOLINE
:
4388 tree tramp
= gimple_call_arg (t
, 0);
4389 tree nfunc
= gimple_call_arg (t
, 1);
4390 tree frame
= gimple_call_arg (t
, 2);
4392 struct constraint_expr lhs
, *rhsp
;
4395 varinfo_t nfi
= NULL
;
4396 gcc_assert (TREE_CODE (nfunc
) == ADDR_EXPR
);
4397 nfi
= lookup_vi_for_tree (TREE_OPERAND (nfunc
, 0));
4400 lhs
= get_function_part_constraint (nfi
, fi_static_chain
);
4401 get_constraint_for (frame
, &rhsc
);
4402 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4403 process_constraint (new_constraint (lhs
, *rhsp
));
4406 /* Make the frame point to the function for
4407 the trampoline adjustment call. */
4408 get_constraint_for (tramp
, &lhsc
);
4410 get_constraint_for (nfunc
, &rhsc
);
4411 process_all_all_constraints (lhsc
, rhsc
);
4416 /* Else fallthru to generic handling which will let
4417 the frame escape. */
4420 case BUILT_IN_ADJUST_TRAMPOLINE
:
4422 tree tramp
= gimple_call_arg (t
, 0);
4423 tree res
= gimple_call_lhs (t
);
4424 if (in_ipa_mode
&& res
)
4426 get_constraint_for (res
, &lhsc
);
4427 get_constraint_for (tramp
, &rhsc
);
4429 process_all_all_constraints (lhsc
, rhsc
);
4433 CASE_BUILT_IN_TM_STORE (1):
4434 CASE_BUILT_IN_TM_STORE (2):
4435 CASE_BUILT_IN_TM_STORE (4):
4436 CASE_BUILT_IN_TM_STORE (8):
4437 CASE_BUILT_IN_TM_STORE (FLOAT
):
4438 CASE_BUILT_IN_TM_STORE (DOUBLE
):
4439 CASE_BUILT_IN_TM_STORE (LDOUBLE
):
4440 CASE_BUILT_IN_TM_STORE (M64
):
4441 CASE_BUILT_IN_TM_STORE (M128
):
4442 CASE_BUILT_IN_TM_STORE (M256
):
4444 tree addr
= gimple_call_arg (t
, 0);
4445 tree src
= gimple_call_arg (t
, 1);
4447 get_constraint_for (addr
, &lhsc
);
4449 get_constraint_for (src
, &rhsc
);
4450 process_all_all_constraints (lhsc
, rhsc
);
4453 CASE_BUILT_IN_TM_LOAD (1):
4454 CASE_BUILT_IN_TM_LOAD (2):
4455 CASE_BUILT_IN_TM_LOAD (4):
4456 CASE_BUILT_IN_TM_LOAD (8):
4457 CASE_BUILT_IN_TM_LOAD (FLOAT
):
4458 CASE_BUILT_IN_TM_LOAD (DOUBLE
):
4459 CASE_BUILT_IN_TM_LOAD (LDOUBLE
):
4460 CASE_BUILT_IN_TM_LOAD (M64
):
4461 CASE_BUILT_IN_TM_LOAD (M128
):
4462 CASE_BUILT_IN_TM_LOAD (M256
):
4464 tree dest
= gimple_call_lhs (t
);
4465 tree addr
= gimple_call_arg (t
, 0);
4467 get_constraint_for (dest
, &lhsc
);
4468 get_constraint_for (addr
, &rhsc
);
4470 process_all_all_constraints (lhsc
, rhsc
);
4473 /* Variadic argument handling needs to be handled in IPA
4475 case BUILT_IN_VA_START
:
4477 tree valist
= gimple_call_arg (t
, 0);
4478 struct constraint_expr rhs
, *lhsp
;
4480 get_constraint_for (valist
, &lhsc
);
4482 /* The va_list gets access to pointers in variadic
4483 arguments. Which we know in the case of IPA analysis
4484 and otherwise are just all nonlocal variables. */
4487 fi
= lookup_vi_for_tree (fn
->decl
);
4488 rhs
= get_function_part_constraint (fi
, ~0);
4489 rhs
.type
= ADDRESSOF
;
4493 rhs
.var
= nonlocal_id
;
4494 rhs
.type
= ADDRESSOF
;
4497 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
4498 process_constraint (new_constraint (*lhsp
, rhs
));
4499 /* va_list is clobbered. */
4500 make_constraint_to (get_call_clobber_vi (t
)->id
, valist
);
4503 /* va_end doesn't have any effect that matters. */
4504 case BUILT_IN_VA_END
:
4506 /* Alternate return. Simply give up for now. */
4507 case BUILT_IN_RETURN
:
4511 || !(fi
= get_vi_for_tree (fn
->decl
)))
4512 make_constraint_from (get_varinfo (escaped_id
), anything_id
);
4513 else if (in_ipa_mode
4516 struct constraint_expr lhs
, rhs
;
4517 lhs
= get_function_part_constraint (fi
, fi_result
);
4518 rhs
.var
= anything_id
;
4521 process_constraint (new_constraint (lhs
, rhs
));
4525 /* printf-style functions may have hooks to set pointers to
4526 point to somewhere into the generated string. Leave them
4527 for a later exercise... */
4529 /* Fallthru to general call handling. */;
4535 /* Create constraints for the call T. */
4538 find_func_aliases_for_call (struct function
*fn
, gcall
*t
)
4540 tree fndecl
= gimple_call_fndecl (t
);
4543 if (fndecl
!= NULL_TREE
4544 && DECL_BUILT_IN (fndecl
)
4545 && find_func_aliases_for_builtin_call (fn
, t
))
4548 fi
= get_fi_for_callee (t
);
4550 || (fndecl
&& !fi
->is_fn_info
))
4552 auto_vec
<ce_s
, 16> rhsc
;
4553 int flags
= gimple_call_flags (t
);
4555 /* Const functions can return their arguments and addresses
4556 of global memory but not of escaped memory. */
4557 if (flags
& (ECF_CONST
|ECF_NOVOPS
))
4559 if (gimple_call_lhs (t
))
4560 handle_const_call (t
, &rhsc
);
4562 /* Pure functions can return addresses in and of memory
4563 reachable from their arguments, but they are not an escape
4564 point for reachable memory of their arguments. */
4565 else if (flags
& (ECF_PURE
|ECF_LOOPING_CONST_OR_PURE
))
4566 handle_pure_call (t
, &rhsc
);
4568 handle_rhs_call (t
, &rhsc
);
4569 if (gimple_call_lhs (t
))
4570 handle_lhs_call (t
, gimple_call_lhs (t
),
4571 gimple_call_return_flags (t
), rhsc
, fndecl
);
4575 auto_vec
<ce_s
, 2> rhsc
;
4579 /* Assign all the passed arguments to the appropriate incoming
4580 parameters of the function. */
4581 for (j
= 0; j
< gimple_call_num_args (t
); j
++)
4583 struct constraint_expr lhs
;
4584 struct constraint_expr
*rhsp
;
4585 tree arg
= gimple_call_arg (t
, j
);
4587 get_constraint_for_rhs (arg
, &rhsc
);
4588 lhs
= get_function_part_constraint (fi
, fi_parm_base
+ j
);
4589 while (rhsc
.length () != 0)
4591 rhsp
= &rhsc
.last ();
4592 process_constraint (new_constraint (lhs
, *rhsp
));
4597 /* If we are returning a value, assign it to the result. */
4598 lhsop
= gimple_call_lhs (t
);
4601 auto_vec
<ce_s
, 2> lhsc
;
4602 struct constraint_expr rhs
;
4603 struct constraint_expr
*lhsp
;
4605 get_constraint_for (lhsop
, &lhsc
);
4606 rhs
= get_function_part_constraint (fi
, fi_result
);
4608 && DECL_RESULT (fndecl
)
4609 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4611 auto_vec
<ce_s
, 2> tem
;
4612 tem
.quick_push (rhs
);
4614 gcc_checking_assert (tem
.length () == 1);
4617 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4618 process_constraint (new_constraint (*lhsp
, rhs
));
4621 /* If we pass the result decl by reference, honor that. */
4624 && DECL_RESULT (fndecl
)
4625 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4627 struct constraint_expr lhs
;
4628 struct constraint_expr
*rhsp
;
4630 get_constraint_for_address_of (lhsop
, &rhsc
);
4631 lhs
= get_function_part_constraint (fi
, fi_result
);
4632 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4633 process_constraint (new_constraint (lhs
, *rhsp
));
4637 /* If we use a static chain, pass it along. */
4638 if (gimple_call_chain (t
))
4640 struct constraint_expr lhs
;
4641 struct constraint_expr
*rhsp
;
4643 get_constraint_for (gimple_call_chain (t
), &rhsc
);
4644 lhs
= get_function_part_constraint (fi
, fi_static_chain
);
4645 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
4646 process_constraint (new_constraint (lhs
, *rhsp
));
4651 /* Walk statement T setting up aliasing constraints according to the
4652 references found in T. This function is the main part of the
4653 constraint builder. AI points to auxiliary alias information used
4654 when building alias sets and computing alias grouping heuristics. */
4657 find_func_aliases (struct function
*fn
, gimple origt
)
4660 auto_vec
<ce_s
, 16> lhsc
;
4661 auto_vec
<ce_s
, 16> rhsc
;
4662 struct constraint_expr
*c
;
4665 /* Now build constraints expressions. */
4666 if (gimple_code (t
) == GIMPLE_PHI
)
4671 /* For a phi node, assign all the arguments to
4673 get_constraint_for (gimple_phi_result (t
), &lhsc
);
4674 for (i
= 0; i
< gimple_phi_num_args (t
); i
++)
4676 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
4678 STRIP_NOPS (strippedrhs
);
4679 get_constraint_for_rhs (gimple_phi_arg_def (t
, i
), &rhsc
);
4681 FOR_EACH_VEC_ELT (lhsc
, j
, c
)
4683 struct constraint_expr
*c2
;
4684 while (rhsc
.length () > 0)
4687 process_constraint (new_constraint (*c
, *c2
));
4693 /* In IPA mode, we need to generate constraints to pass call
4694 arguments through their calls. There are two cases,
4695 either a GIMPLE_CALL returning a value, or just a plain
4696 GIMPLE_CALL when we are not.
4698 In non-ipa mode, we need to generate constraints for each
4699 pointer passed by address. */
4700 else if (is_gimple_call (t
))
4701 find_func_aliases_for_call (fn
, as_a
<gcall
*> (t
));
4703 /* Otherwise, just a regular assignment statement. Only care about
4704 operations with pointer result, others are dealt with as escape
4705 points if they have pointer operands. */
4706 else if (is_gimple_assign (t
))
4708 /* Otherwise, just a regular assignment statement. */
4709 tree lhsop
= gimple_assign_lhs (t
);
4710 tree rhsop
= (gimple_num_ops (t
) == 2) ? gimple_assign_rhs1 (t
) : NULL
;
4712 if (rhsop
&& TREE_CLOBBER_P (rhsop
))
4713 /* Ignore clobbers, they don't actually store anything into
4716 else if (rhsop
&& AGGREGATE_TYPE_P (TREE_TYPE (lhsop
)))
4717 do_structure_copy (lhsop
, rhsop
);
4720 enum tree_code code
= gimple_assign_rhs_code (t
);
4722 get_constraint_for (lhsop
, &lhsc
);
4724 if (code
== POINTER_PLUS_EXPR
)
4725 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4726 gimple_assign_rhs2 (t
), &rhsc
);
4727 else if (code
== BIT_AND_EXPR
4728 && TREE_CODE (gimple_assign_rhs2 (t
)) == INTEGER_CST
)
4730 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4731 the pointer. Handle it by offsetting it by UNKNOWN. */
4732 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4735 else if ((CONVERT_EXPR_CODE_P (code
)
4736 && !(POINTER_TYPE_P (gimple_expr_type (t
))
4737 && !POINTER_TYPE_P (TREE_TYPE (rhsop
))))
4738 || gimple_assign_single_p (t
))
4739 get_constraint_for_rhs (rhsop
, &rhsc
);
4740 else if (code
== COND_EXPR
)
4742 /* The result is a merge of both COND_EXPR arms. */
4743 auto_vec
<ce_s
, 2> tmp
;
4744 struct constraint_expr
*rhsp
;
4746 get_constraint_for_rhs (gimple_assign_rhs2 (t
), &rhsc
);
4747 get_constraint_for_rhs (gimple_assign_rhs3 (t
), &tmp
);
4748 FOR_EACH_VEC_ELT (tmp
, i
, rhsp
)
4749 rhsc
.safe_push (*rhsp
);
4751 else if (truth_value_p (code
))
4752 /* Truth value results are not pointer (parts). Or at least
4753 very very unreasonable obfuscation of a part. */
4757 /* All other operations are merges. */
4758 auto_vec
<ce_s
, 4> tmp
;
4759 struct constraint_expr
*rhsp
;
4761 get_constraint_for_rhs (gimple_assign_rhs1 (t
), &rhsc
);
4762 for (i
= 2; i
< gimple_num_ops (t
); ++i
)
4764 get_constraint_for_rhs (gimple_op (t
, i
), &tmp
);
4765 FOR_EACH_VEC_ELT (tmp
, j
, rhsp
)
4766 rhsc
.safe_push (*rhsp
);
4770 process_all_all_constraints (lhsc
, rhsc
);
4772 /* If there is a store to a global variable the rhs escapes. */
4773 if ((lhsop
= get_base_address (lhsop
)) != NULL_TREE
4775 && is_global_var (lhsop
)
4777 || DECL_EXTERNAL (lhsop
) || TREE_PUBLIC (lhsop
)))
4778 make_escape_constraint (rhsop
);
4780 /* Handle escapes through return. */
4781 else if (gimple_code (t
) == GIMPLE_RETURN
4782 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
)
4784 greturn
*return_stmt
= as_a
<greturn
*> (t
);
4787 || !(fi
= get_vi_for_tree (fn
->decl
)))
4788 make_escape_constraint (gimple_return_retval (return_stmt
));
4789 else if (in_ipa_mode
4792 struct constraint_expr lhs
;
4793 struct constraint_expr
*rhsp
;
4796 lhs
= get_function_part_constraint (fi
, fi_result
);
4797 get_constraint_for_rhs (gimple_return_retval (return_stmt
), &rhsc
);
4798 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4799 process_constraint (new_constraint (lhs
, *rhsp
));
4802 /* Handle asms conservatively by adding escape constraints to everything. */
4803 else if (gasm
*asm_stmt
= dyn_cast
<gasm
*> (t
))
4805 unsigned i
, noutputs
;
4806 const char **oconstraints
;
4807 const char *constraint
;
4808 bool allows_mem
, allows_reg
, is_inout
;
4810 noutputs
= gimple_asm_noutputs (asm_stmt
);
4811 oconstraints
= XALLOCAVEC (const char *, noutputs
);
4813 for (i
= 0; i
< noutputs
; ++i
)
4815 tree link
= gimple_asm_output_op (asm_stmt
, i
);
4816 tree op
= TREE_VALUE (link
);
4818 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4819 oconstraints
[i
] = constraint
;
4820 parse_output_constraint (&constraint
, i
, 0, 0, &allows_mem
,
4821 &allows_reg
, &is_inout
);
4823 /* A memory constraint makes the address of the operand escape. */
4824 if (!allows_reg
&& allows_mem
)
4825 make_escape_constraint (build_fold_addr_expr (op
));
4827 /* The asm may read global memory, so outputs may point to
4828 any global memory. */
4831 auto_vec
<ce_s
, 2> lhsc
;
4832 struct constraint_expr rhsc
, *lhsp
;
4834 get_constraint_for (op
, &lhsc
);
4835 rhsc
.var
= nonlocal_id
;
4838 FOR_EACH_VEC_ELT (lhsc
, j
, lhsp
)
4839 process_constraint (new_constraint (*lhsp
, rhsc
));
4842 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); ++i
)
4844 tree link
= gimple_asm_input_op (asm_stmt
, i
);
4845 tree op
= TREE_VALUE (link
);
4847 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4849 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0, oconstraints
,
4850 &allows_mem
, &allows_reg
);
4852 /* A memory constraint makes the address of the operand escape. */
4853 if (!allows_reg
&& allows_mem
)
4854 make_escape_constraint (build_fold_addr_expr (op
));
4855 /* Strictly we'd only need the constraint to ESCAPED if
4856 the asm clobbers memory, otherwise using something
4857 along the lines of per-call clobbers/uses would be enough. */
4859 make_escape_constraint (op
);
4865 /* Create a constraint adding to the clobber set of FI the memory
4866 pointed to by PTR. */
4869 process_ipa_clobber (varinfo_t fi
, tree ptr
)
4871 vec
<ce_s
> ptrc
= vNULL
;
4872 struct constraint_expr
*c
, lhs
;
4874 get_constraint_for_rhs (ptr
, &ptrc
);
4875 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4876 FOR_EACH_VEC_ELT (ptrc
, i
, c
)
4877 process_constraint (new_constraint (lhs
, *c
));
4881 /* Walk statement T setting up clobber and use constraints according to the
4882 references found in T. This function is a main part of the
4883 IPA constraint builder. */
4886 find_func_clobbers (struct function
*fn
, gimple origt
)
4889 auto_vec
<ce_s
, 16> lhsc
;
4890 auto_vec
<ce_s
, 16> rhsc
;
4893 /* Add constraints for clobbered/used in IPA mode.
4894 We are not interested in what automatic variables are clobbered
4895 or used as we only use the information in the caller to which
4896 they do not escape. */
4897 gcc_assert (in_ipa_mode
);
4899 /* If the stmt refers to memory in any way it better had a VUSE. */
4900 if (gimple_vuse (t
) == NULL_TREE
)
4903 /* We'd better have function information for the current function. */
4904 fi
= lookup_vi_for_tree (fn
->decl
);
4905 gcc_assert (fi
!= NULL
);
4907 /* Account for stores in assignments and calls. */
4908 if (gimple_vdef (t
) != NULL_TREE
4909 && gimple_has_lhs (t
))
4911 tree lhs
= gimple_get_lhs (t
);
4913 while (handled_component_p (tem
))
4914 tem
= TREE_OPERAND (tem
, 0);
4916 && !auto_var_in_fn_p (tem
, fn
->decl
))
4917 || INDIRECT_REF_P (tem
)
4918 || (TREE_CODE (tem
) == MEM_REF
4919 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
4921 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
4923 struct constraint_expr lhsc
, *rhsp
;
4925 lhsc
= get_function_part_constraint (fi
, fi_clobbers
);
4926 get_constraint_for_address_of (lhs
, &rhsc
);
4927 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4928 process_constraint (new_constraint (lhsc
, *rhsp
));
4933 /* Account for uses in assigments and returns. */
4934 if (gimple_assign_single_p (t
)
4935 || (gimple_code (t
) == GIMPLE_RETURN
4936 && gimple_return_retval (as_a
<greturn
*> (t
)) != NULL_TREE
))
4938 tree rhs
= (gimple_assign_single_p (t
)
4939 ? gimple_assign_rhs1 (t
)
4940 : gimple_return_retval (as_a
<greturn
*> (t
)));
4942 while (handled_component_p (tem
))
4943 tem
= TREE_OPERAND (tem
, 0);
4945 && !auto_var_in_fn_p (tem
, fn
->decl
))
4946 || INDIRECT_REF_P (tem
)
4947 || (TREE_CODE (tem
) == MEM_REF
4948 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
4950 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), fn
->decl
))))
4952 struct constraint_expr lhs
, *rhsp
;
4954 lhs
= get_function_part_constraint (fi
, fi_uses
);
4955 get_constraint_for_address_of (rhs
, &rhsc
);
4956 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
4957 process_constraint (new_constraint (lhs
, *rhsp
));
4962 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (t
))
4964 varinfo_t cfi
= NULL
;
4965 tree decl
= gimple_call_fndecl (t
);
4966 struct constraint_expr lhs
, rhs
;
4969 /* For builtins we do not have separate function info. For those
4970 we do not generate escapes for we have to generate clobbers/uses. */
4971 if (gimple_call_builtin_p (t
, BUILT_IN_NORMAL
))
4972 switch (DECL_FUNCTION_CODE (decl
))
4974 /* The following functions use and clobber memory pointed to
4975 by their arguments. */
4976 case BUILT_IN_STRCPY
:
4977 case BUILT_IN_STRNCPY
:
4978 case BUILT_IN_BCOPY
:
4979 case BUILT_IN_MEMCPY
:
4980 case BUILT_IN_MEMMOVE
:
4981 case BUILT_IN_MEMPCPY
:
4982 case BUILT_IN_STPCPY
:
4983 case BUILT_IN_STPNCPY
:
4984 case BUILT_IN_STRCAT
:
4985 case BUILT_IN_STRNCAT
:
4986 case BUILT_IN_STRCPY_CHK
:
4987 case BUILT_IN_STRNCPY_CHK
:
4988 case BUILT_IN_MEMCPY_CHK
:
4989 case BUILT_IN_MEMMOVE_CHK
:
4990 case BUILT_IN_MEMPCPY_CHK
:
4991 case BUILT_IN_STPCPY_CHK
:
4992 case BUILT_IN_STPNCPY_CHK
:
4993 case BUILT_IN_STRCAT_CHK
:
4994 case BUILT_IN_STRNCAT_CHK
:
4996 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
4997 == BUILT_IN_BCOPY
? 1 : 0));
4998 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
4999 == BUILT_IN_BCOPY
? 0 : 1));
5001 struct constraint_expr
*rhsp
, *lhsp
;
5002 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5003 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5004 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5005 process_constraint (new_constraint (lhs
, *lhsp
));
5006 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
5007 lhs
= get_function_part_constraint (fi
, fi_uses
);
5008 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5009 process_constraint (new_constraint (lhs
, *rhsp
));
5012 /* The following function clobbers memory pointed to by
5014 case BUILT_IN_MEMSET
:
5015 case BUILT_IN_MEMSET_CHK
:
5016 case BUILT_IN_POSIX_MEMALIGN
:
5018 tree dest
= gimple_call_arg (t
, 0);
5021 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
5022 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5023 FOR_EACH_VEC_ELT (lhsc
, i
, lhsp
)
5024 process_constraint (new_constraint (lhs
, *lhsp
));
5027 /* The following functions clobber their second and third
5029 case BUILT_IN_SINCOS
:
5030 case BUILT_IN_SINCOSF
:
5031 case BUILT_IN_SINCOSL
:
5033 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5034 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5037 /* The following functions clobber their second argument. */
5038 case BUILT_IN_FREXP
:
5039 case BUILT_IN_FREXPF
:
5040 case BUILT_IN_FREXPL
:
5041 case BUILT_IN_LGAMMA_R
:
5042 case BUILT_IN_LGAMMAF_R
:
5043 case BUILT_IN_LGAMMAL_R
:
5044 case BUILT_IN_GAMMA_R
:
5045 case BUILT_IN_GAMMAF_R
:
5046 case BUILT_IN_GAMMAL_R
:
5048 case BUILT_IN_MODFF
:
5049 case BUILT_IN_MODFL
:
5051 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
5054 /* The following functions clobber their third argument. */
5055 case BUILT_IN_REMQUO
:
5056 case BUILT_IN_REMQUOF
:
5057 case BUILT_IN_REMQUOL
:
5059 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
5062 /* The following functions neither read nor clobber memory. */
5063 case BUILT_IN_ASSUME_ALIGNED
:
5066 /* Trampolines are of no interest to us. */
5067 case BUILT_IN_INIT_TRAMPOLINE
:
5068 case BUILT_IN_ADJUST_TRAMPOLINE
:
5070 case BUILT_IN_VA_START
:
5071 case BUILT_IN_VA_END
:
5073 /* printf-style functions may have hooks to set pointers to
5074 point to somewhere into the generated string. Leave them
5075 for a later exercise... */
5077 /* Fallthru to general call handling. */;
5080 /* Parameters passed by value are used. */
5081 lhs
= get_function_part_constraint (fi
, fi_uses
);
5082 for (i
= 0; i
< gimple_call_num_args (t
); i
++)
5084 struct constraint_expr
*rhsp
;
5085 tree arg
= gimple_call_arg (t
, i
);
5087 if (TREE_CODE (arg
) == SSA_NAME
5088 || is_gimple_min_invariant (arg
))
5091 get_constraint_for_address_of (arg
, &rhsc
);
5092 FOR_EACH_VEC_ELT (rhsc
, j
, rhsp
)
5093 process_constraint (new_constraint (lhs
, *rhsp
));
5097 /* Build constraints for propagating clobbers/uses along the
5099 cfi
= get_fi_for_callee (call_stmt
);
5100 if (cfi
->id
== anything_id
)
5102 if (gimple_vdef (t
))
5103 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5105 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5110 /* For callees without function info (that's external functions),
5111 ESCAPED is clobbered and used. */
5112 if (gimple_call_fndecl (t
)
5113 && !cfi
->is_fn_info
)
5117 if (gimple_vdef (t
))
5118 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5120 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
), escaped_id
);
5122 /* Also honor the call statement use/clobber info. */
5123 if ((vi
= lookup_call_clobber_vi (call_stmt
)) != NULL
)
5124 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
5126 if ((vi
= lookup_call_use_vi (call_stmt
)) != NULL
)
5127 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
),
5132 /* Otherwise the caller clobbers and uses what the callee does.
5133 ??? This should use a new complex constraint that filters
5134 local variables of the callee. */
5135 if (gimple_vdef (t
))
5137 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
5138 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
5139 process_constraint (new_constraint (lhs
, rhs
));
5141 lhs
= get_function_part_constraint (fi
, fi_uses
);
5142 rhs
= get_function_part_constraint (cfi
, fi_uses
);
5143 process_constraint (new_constraint (lhs
, rhs
));
5145 else if (gimple_code (t
) == GIMPLE_ASM
)
5147 /* ??? Ick. We can do better. */
5148 if (gimple_vdef (t
))
5149 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
5151 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
5157 /* Find the first varinfo in the same variable as START that overlaps with
5158 OFFSET. Return NULL if we can't find one. */
5161 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
5163 /* If the offset is outside of the variable, bail out. */
5164 if (offset
>= start
->fullsize
)
5167 /* If we cannot reach offset from start, lookup the first field
5168 and start from there. */
5169 if (start
->offset
> offset
)
5170 start
= get_varinfo (start
->head
);
5174 /* We may not find a variable in the field list with the actual
5175 offset when when we have glommed a structure to a variable.
5176 In that case, however, offset should still be within the size
5178 if (offset
>= start
->offset
5179 && (offset
- start
->offset
) < start
->size
)
5182 start
= vi_next (start
);
5188 /* Find the first varinfo in the same variable as START that overlaps with
5189 OFFSET. If there is no such varinfo the varinfo directly preceding
5190 OFFSET is returned. */
5193 first_or_preceding_vi_for_offset (varinfo_t start
,
5194 unsigned HOST_WIDE_INT offset
)
5196 /* If we cannot reach offset from start, lookup the first field
5197 and start from there. */
5198 if (start
->offset
> offset
)
5199 start
= get_varinfo (start
->head
);
5201 /* We may not find a variable in the field list with the actual
5202 offset when when we have glommed a structure to a variable.
5203 In that case, however, offset should still be within the size
5205 If we got beyond the offset we look for return the field
5206 directly preceding offset which may be the last field. */
5208 && offset
>= start
->offset
5209 && !((offset
- start
->offset
) < start
->size
))
5210 start
= vi_next (start
);
5216 /* This structure is used during pushing fields onto the fieldstack
5217 to track the offset of the field, since bitpos_of_field gives it
5218 relative to its immediate containing type, and we want it relative
5219 to the ultimate containing object. */
5223 /* Offset from the base of the base containing object to this field. */
5224 HOST_WIDE_INT offset
;
5226 /* Size, in bits, of the field. */
5227 unsigned HOST_WIDE_INT size
;
5229 unsigned has_unknown_size
: 1;
5231 unsigned must_have_pointers
: 1;
5233 unsigned may_have_pointers
: 1;
5235 unsigned only_restrict_pointers
: 1;
5237 typedef struct fieldoff fieldoff_s
;
5240 /* qsort comparison function for two fieldoff's PA and PB */
5243 fieldoff_compare (const void *pa
, const void *pb
)
5245 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
5246 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
5247 unsigned HOST_WIDE_INT foasize
, fobsize
;
5249 if (foa
->offset
< fob
->offset
)
5251 else if (foa
->offset
> fob
->offset
)
5254 foasize
= foa
->size
;
5255 fobsize
= fob
->size
;
5256 if (foasize
< fobsize
)
5258 else if (foasize
> fobsize
)
5263 /* Sort a fieldstack according to the field offset and sizes. */
5265 sort_fieldstack (vec
<fieldoff_s
> fieldstack
)
5267 fieldstack
.qsort (fieldoff_compare
);
5270 /* Return true if T is a type that can have subvars. */
5273 type_can_have_subvars (const_tree t
)
5275 /* Aggregates without overlapping fields can have subvars. */
5276 return TREE_CODE (t
) == RECORD_TYPE
;
5279 /* Return true if V is a tree that we can have subvars for.
5280 Normally, this is any aggregate type. Also complex
5281 types which are not gimple registers can have subvars. */
5284 var_can_have_subvars (const_tree v
)
5286 /* Volatile variables should never have subvars. */
5287 if (TREE_THIS_VOLATILE (v
))
5290 /* Non decls or memory tags can never have subvars. */
5294 return type_can_have_subvars (TREE_TYPE (v
));
5297 /* Return true if T is a type that does contain pointers. */
5300 type_must_have_pointers (tree type
)
5302 if (POINTER_TYPE_P (type
))
5305 if (TREE_CODE (type
) == ARRAY_TYPE
)
5306 return type_must_have_pointers (TREE_TYPE (type
));
5308 /* A function or method can have pointers as arguments, so track
5309 those separately. */
5310 if (TREE_CODE (type
) == FUNCTION_TYPE
5311 || TREE_CODE (type
) == METHOD_TYPE
)
5318 field_must_have_pointers (tree t
)
5320 return type_must_have_pointers (TREE_TYPE (t
));
5323 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5324 the fields of TYPE onto fieldstack, recording their offsets along
5327 OFFSET is used to keep track of the offset in this entire
5328 structure, rather than just the immediately containing structure.
5329 Returns false if the caller is supposed to handle the field we
5333 push_fields_onto_fieldstack (tree type
, vec
<fieldoff_s
> *fieldstack
,
5334 HOST_WIDE_INT offset
)
5337 bool empty_p
= true;
5339 if (TREE_CODE (type
) != RECORD_TYPE
)
5342 /* If the vector of fields is growing too big, bail out early.
5343 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5345 if (fieldstack
->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5348 for (field
= TYPE_FIELDS (type
); field
; field
= DECL_CHAIN (field
))
5349 if (TREE_CODE (field
) == FIELD_DECL
)
5352 HOST_WIDE_INT foff
= bitpos_of_field (field
);
5354 if (!var_can_have_subvars (field
)
5355 || TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
5356 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
)
5358 else if (!push_fields_onto_fieldstack
5359 (TREE_TYPE (field
), fieldstack
, offset
+ foff
)
5360 && (DECL_SIZE (field
)
5361 && !integer_zerop (DECL_SIZE (field
))))
5362 /* Empty structures may have actual size, like in C++. So
5363 see if we didn't push any subfields and the size is
5364 nonzero, push the field onto the stack. */
5369 fieldoff_s
*pair
= NULL
;
5370 bool has_unknown_size
= false;
5371 bool must_have_pointers_p
;
5373 if (!fieldstack
->is_empty ())
5374 pair
= &fieldstack
->last ();
5376 /* If there isn't anything at offset zero, create sth. */
5378 && offset
+ foff
!= 0)
5380 fieldoff_s e
= {0, offset
+ foff
, false, false, false, false};
5381 pair
= fieldstack
->safe_push (e
);
5384 if (!DECL_SIZE (field
)
5385 || !tree_fits_uhwi_p (DECL_SIZE (field
)))
5386 has_unknown_size
= true;
5388 /* If adjacent fields do not contain pointers merge them. */
5389 must_have_pointers_p
= field_must_have_pointers (field
);
5391 && !has_unknown_size
5392 && !must_have_pointers_p
5393 && !pair
->must_have_pointers
5394 && !pair
->has_unknown_size
5395 && pair
->offset
+ (HOST_WIDE_INT
)pair
->size
== offset
+ foff
)
5397 pair
->size
+= tree_to_uhwi (DECL_SIZE (field
));
5402 e
.offset
= offset
+ foff
;
5403 e
.has_unknown_size
= has_unknown_size
;
5404 if (!has_unknown_size
)
5405 e
.size
= tree_to_uhwi (DECL_SIZE (field
));
5408 e
.must_have_pointers
= must_have_pointers_p
;
5409 e
.may_have_pointers
= true;
5410 e
.only_restrict_pointers
5411 = (!has_unknown_size
5412 && POINTER_TYPE_P (TREE_TYPE (field
))
5413 && TYPE_RESTRICT (TREE_TYPE (field
)));
5414 fieldstack
->safe_push (e
);
5424 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5425 if it is a varargs function. */
5428 count_num_arguments (tree decl
, bool *is_varargs
)
5430 unsigned int num
= 0;
5433 /* Capture named arguments for K&R functions. They do not
5434 have a prototype and thus no TYPE_ARG_TYPES. */
5435 for (t
= DECL_ARGUMENTS (decl
); t
; t
= DECL_CHAIN (t
))
5438 /* Check if the function has variadic arguments. */
5439 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
)); t
; t
= TREE_CHAIN (t
))
5440 if (TREE_VALUE (t
) == void_type_node
)
5448 /* Creation function node for DECL, using NAME, and return the index
5449 of the variable we've created for the function. */
5452 create_function_info_for (tree decl
, const char *name
)
5454 struct function
*fn
= DECL_STRUCT_FUNCTION (decl
);
5455 varinfo_t vi
, prev_vi
;
5458 bool is_varargs
= false;
5459 unsigned int num_args
= count_num_arguments (decl
, &is_varargs
);
5461 /* Create the variable info. */
5463 vi
= new_var_info (decl
, name
);
5466 vi
->fullsize
= fi_parm_base
+ num_args
;
5468 vi
->may_have_pointers
= false;
5471 insert_vi_for_tree (vi
->decl
, vi
);
5475 /* Create a variable for things the function clobbers and one for
5476 things the function uses. */
5478 varinfo_t clobbervi
, usevi
;
5479 const char *newname
;
5482 tempname
= xasprintf ("%s.clobber", name
);
5483 newname
= ggc_strdup (tempname
);
5486 clobbervi
= new_var_info (NULL
, newname
);
5487 clobbervi
->offset
= fi_clobbers
;
5488 clobbervi
->size
= 1;
5489 clobbervi
->fullsize
= vi
->fullsize
;
5490 clobbervi
->is_full_var
= true;
5491 clobbervi
->is_global_var
= false;
5492 gcc_assert (prev_vi
->offset
< clobbervi
->offset
);
5493 prev_vi
->next
= clobbervi
->id
;
5494 prev_vi
= clobbervi
;
5496 tempname
= xasprintf ("%s.use", name
);
5497 newname
= ggc_strdup (tempname
);
5500 usevi
= new_var_info (NULL
, newname
);
5501 usevi
->offset
= fi_uses
;
5503 usevi
->fullsize
= vi
->fullsize
;
5504 usevi
->is_full_var
= true;
5505 usevi
->is_global_var
= false;
5506 gcc_assert (prev_vi
->offset
< usevi
->offset
);
5507 prev_vi
->next
= usevi
->id
;
5511 /* And one for the static chain. */
5512 if (fn
->static_chain_decl
!= NULL_TREE
)
5515 const char *newname
;
5518 tempname
= xasprintf ("%s.chain", name
);
5519 newname
= ggc_strdup (tempname
);
5522 chainvi
= new_var_info (fn
->static_chain_decl
, newname
);
5523 chainvi
->offset
= fi_static_chain
;
5525 chainvi
->fullsize
= vi
->fullsize
;
5526 chainvi
->is_full_var
= true;
5527 chainvi
->is_global_var
= false;
5528 gcc_assert (prev_vi
->offset
< chainvi
->offset
);
5529 prev_vi
->next
= chainvi
->id
;
5531 insert_vi_for_tree (fn
->static_chain_decl
, chainvi
);
5534 /* Create a variable for the return var. */
5535 if (DECL_RESULT (decl
) != NULL
5536 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
5539 const char *newname
;
5541 tree resultdecl
= decl
;
5543 if (DECL_RESULT (decl
))
5544 resultdecl
= DECL_RESULT (decl
);
5546 tempname
= xasprintf ("%s.result", name
);
5547 newname
= ggc_strdup (tempname
);
5550 resultvi
= new_var_info (resultdecl
, newname
);
5551 resultvi
->offset
= fi_result
;
5553 resultvi
->fullsize
= vi
->fullsize
;
5554 resultvi
->is_full_var
= true;
5555 if (DECL_RESULT (decl
))
5556 resultvi
->may_have_pointers
= true;
5557 gcc_assert (prev_vi
->offset
< resultvi
->offset
);
5558 prev_vi
->next
= resultvi
->id
;
5560 if (DECL_RESULT (decl
))
5561 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
5564 /* Set up variables for each argument. */
5565 arg
= DECL_ARGUMENTS (decl
);
5566 for (i
= 0; i
< num_args
; i
++)
5569 const char *newname
;
5571 tree argdecl
= decl
;
5576 tempname
= xasprintf ("%s.arg%d", name
, i
);
5577 newname
= ggc_strdup (tempname
);
5580 argvi
= new_var_info (argdecl
, newname
);
5581 argvi
->offset
= fi_parm_base
+ i
;
5583 argvi
->is_full_var
= true;
5584 argvi
->fullsize
= vi
->fullsize
;
5586 argvi
->may_have_pointers
= true;
5587 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5588 prev_vi
->next
= argvi
->id
;
5592 insert_vi_for_tree (arg
, argvi
);
5593 arg
= DECL_CHAIN (arg
);
5597 /* Add one representative for all further args. */
5601 const char *newname
;
5605 tempname
= xasprintf ("%s.varargs", name
);
5606 newname
= ggc_strdup (tempname
);
5609 /* We need sth that can be pointed to for va_start. */
5610 decl
= build_fake_var_decl (ptr_type_node
);
5612 argvi
= new_var_info (decl
, newname
);
5613 argvi
->offset
= fi_parm_base
+ num_args
;
5615 argvi
->is_full_var
= true;
5616 argvi
->is_heap_var
= true;
5617 argvi
->fullsize
= vi
->fullsize
;
5618 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5619 prev_vi
->next
= argvi
->id
;
5627 /* Return true if FIELDSTACK contains fields that overlap.
5628 FIELDSTACK is assumed to be sorted by offset. */
5631 check_for_overlaps (vec
<fieldoff_s
> fieldstack
)
5633 fieldoff_s
*fo
= NULL
;
5635 HOST_WIDE_INT lastoffset
= -1;
5637 FOR_EACH_VEC_ELT (fieldstack
, i
, fo
)
5639 if (fo
->offset
== lastoffset
)
5641 lastoffset
= fo
->offset
;
5646 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5647 This will also create any varinfo structures necessary for fields
5651 create_variable_info_for_1 (tree decl
, const char *name
)
5653 varinfo_t vi
, newvi
;
5654 tree decl_type
= TREE_TYPE (decl
);
5655 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decl_type
);
5656 auto_vec
<fieldoff_s
> fieldstack
;
5659 varpool_node
*vnode
;
5662 || !tree_fits_uhwi_p (declsize
))
5664 vi
= new_var_info (decl
, name
);
5668 vi
->is_unknown_size_var
= true;
5669 vi
->is_full_var
= true;
5670 vi
->may_have_pointers
= true;
5674 /* Collect field information. */
5675 if (use_field_sensitive
5676 && var_can_have_subvars (decl
)
5677 /* ??? Force us to not use subfields for global initializers
5678 in IPA mode. Else we'd have to parse arbitrary initializers. */
5680 && is_global_var (decl
)
5681 && (vnode
= varpool_node::get (decl
))
5682 && vnode
->get_constructor ()))
5684 fieldoff_s
*fo
= NULL
;
5685 bool notokay
= false;
5688 push_fields_onto_fieldstack (decl_type
, &fieldstack
, 0);
5690 for (i
= 0; !notokay
&& fieldstack
.iterate (i
, &fo
); i
++)
5691 if (fo
->has_unknown_size
5698 /* We can't sort them if we have a field with a variable sized type,
5699 which will make notokay = true. In that case, we are going to return
5700 without creating varinfos for the fields anyway, so sorting them is a
5704 sort_fieldstack (fieldstack
);
5705 /* Due to some C++ FE issues, like PR 22488, we might end up
5706 what appear to be overlapping fields even though they,
5707 in reality, do not overlap. Until the C++ FE is fixed,
5708 we will simply disable field-sensitivity for these cases. */
5709 notokay
= check_for_overlaps (fieldstack
);
5713 fieldstack
.release ();
5716 /* If we didn't end up collecting sub-variables create a full
5717 variable for the decl. */
5718 if (fieldstack
.length () <= 1
5719 || fieldstack
.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5721 vi
= new_var_info (decl
, name
);
5723 vi
->may_have_pointers
= true;
5724 vi
->fullsize
= tree_to_uhwi (declsize
);
5725 vi
->size
= vi
->fullsize
;
5726 vi
->is_full_var
= true;
5727 fieldstack
.release ();
5731 vi
= new_var_info (decl
, name
);
5732 vi
->fullsize
= tree_to_uhwi (declsize
);
5733 for (i
= 0, newvi
= vi
;
5734 fieldstack
.iterate (i
, &fo
);
5735 ++i
, newvi
= vi_next (newvi
))
5737 const char *newname
= "NULL";
5743 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC
5744 "+" HOST_WIDE_INT_PRINT_DEC
, name
,
5745 fo
->offset
, fo
->size
);
5746 newname
= ggc_strdup (tempname
);
5749 newvi
->name
= newname
;
5750 newvi
->offset
= fo
->offset
;
5751 newvi
->size
= fo
->size
;
5752 newvi
->fullsize
= vi
->fullsize
;
5753 newvi
->may_have_pointers
= fo
->may_have_pointers
;
5754 newvi
->only_restrict_pointers
= fo
->only_restrict_pointers
;
5755 if (i
+ 1 < fieldstack
.length ())
5757 varinfo_t tem
= new_var_info (decl
, name
);
5758 newvi
->next
= tem
->id
;
5767 create_variable_info_for (tree decl
, const char *name
)
5769 varinfo_t vi
= create_variable_info_for_1 (decl
, name
);
5770 unsigned int id
= vi
->id
;
5772 insert_vi_for_tree (decl
, vi
);
5774 if (TREE_CODE (decl
) != VAR_DECL
)
5777 /* Create initial constraints for globals. */
5778 for (; vi
; vi
= vi_next (vi
))
5780 if (!vi
->may_have_pointers
5781 || !vi
->is_global_var
)
5784 /* Mark global restrict qualified pointers. */
5785 if ((POINTER_TYPE_P (TREE_TYPE (decl
))
5786 && TYPE_RESTRICT (TREE_TYPE (decl
)))
5787 || vi
->only_restrict_pointers
)
5790 = make_constraint_from_global_restrict (vi
, "GLOBAL_RESTRICT");
5791 /* ??? For now exclude reads from globals as restrict sources
5792 if those are not (indirectly) from incoming parameters. */
5793 rvi
->is_restrict_var
= false;
5797 /* In non-IPA mode the initializer from nonlocal is all we need. */
5799 || DECL_HARD_REGISTER (decl
))
5800 make_copy_constraint (vi
, nonlocal_id
);
5802 /* In IPA mode parse the initializer and generate proper constraints
5806 varpool_node
*vnode
= varpool_node::get (decl
);
5808 /* For escaped variables initialize them from nonlocal. */
5809 if (!vnode
->all_refs_explicit_p ())
5810 make_copy_constraint (vi
, nonlocal_id
);
5812 /* If this is a global variable with an initializer and we are in
5813 IPA mode generate constraints for it. */
5814 if (vnode
->get_constructor ()
5815 && vnode
->definition
)
5817 auto_vec
<ce_s
> rhsc
;
5818 struct constraint_expr lhs
, *rhsp
;
5820 get_constraint_for_rhs (vnode
->get_constructor (), &rhsc
);
5824 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5825 process_constraint (new_constraint (lhs
, *rhsp
));
5826 /* If this is a variable that escapes from the unit
5827 the initializer escapes as well. */
5828 if (!vnode
->all_refs_explicit_p ())
5830 lhs
.var
= escaped_id
;
5833 FOR_EACH_VEC_ELT (rhsc
, i
, rhsp
)
5834 process_constraint (new_constraint (lhs
, *rhsp
));
5843 /* Print out the points-to solution for VAR to FILE. */
5846 dump_solution_for_var (FILE *file
, unsigned int var
)
5848 varinfo_t vi
= get_varinfo (var
);
5852 /* Dump the solution for unified vars anyway, this avoids difficulties
5853 in scanning dumps in the testsuite. */
5854 fprintf (file
, "%s = { ", vi
->name
);
5855 vi
= get_varinfo (find (var
));
5856 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
5857 fprintf (file
, "%s ", get_varinfo (i
)->name
);
5858 fprintf (file
, "}");
5860 /* But note when the variable was unified. */
5862 fprintf (file
, " same as %s", vi
->name
);
5864 fprintf (file
, "\n");
5867 /* Print the points-to solution for VAR to stderr. */
5870 debug_solution_for_var (unsigned int var
)
5872 dump_solution_for_var (stderr
, var
);
5875 /* Create varinfo structures for all of the variables in the
5876 function for intraprocedural mode. */
5879 intra_create_variable_infos (struct function
*fn
)
5883 /* For each incoming pointer argument arg, create the constraint ARG
5884 = NONLOCAL or a dummy variable if it is a restrict qualified
5885 passed-by-reference argument. */
5886 for (t
= DECL_ARGUMENTS (fn
->decl
); t
; t
= DECL_CHAIN (t
))
5888 varinfo_t p
= get_vi_for_tree (t
);
5890 /* For restrict qualified pointers to objects passed by
5891 reference build a real representative for the pointed-to object.
5892 Treat restrict qualified references the same. */
5893 if (TYPE_RESTRICT (TREE_TYPE (t
))
5894 && ((DECL_BY_REFERENCE (t
) && POINTER_TYPE_P (TREE_TYPE (t
)))
5895 || TREE_CODE (TREE_TYPE (t
)) == REFERENCE_TYPE
)
5896 && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t
))))
5898 struct constraint_expr lhsc
, rhsc
;
5900 tree heapvar
= build_fake_var_decl (TREE_TYPE (TREE_TYPE (t
)));
5901 DECL_EXTERNAL (heapvar
) = 1;
5902 vi
= create_variable_info_for_1 (heapvar
, "PARM_NOALIAS");
5903 vi
->is_restrict_var
= 1;
5904 insert_vi_for_tree (heapvar
, vi
);
5909 rhsc
.type
= ADDRESSOF
;
5911 process_constraint (new_constraint (lhsc
, rhsc
));
5912 for (; vi
; vi
= vi_next (vi
))
5913 if (vi
->may_have_pointers
)
5915 if (vi
->only_restrict_pointers
)
5916 make_constraint_from_global_restrict (vi
, "GLOBAL_RESTRICT");
5918 make_copy_constraint (vi
, nonlocal_id
);
5923 if (POINTER_TYPE_P (TREE_TYPE (t
))
5924 && TYPE_RESTRICT (TREE_TYPE (t
)))
5925 make_constraint_from_global_restrict (p
, "PARM_RESTRICT");
5928 for (; p
; p
= vi_next (p
))
5930 if (p
->only_restrict_pointers
)
5931 make_constraint_from_global_restrict (p
, "PARM_RESTRICT");
5932 else if (p
->may_have_pointers
)
5933 make_constraint_from (p
, nonlocal_id
);
5938 /* Add a constraint for a result decl that is passed by reference. */
5939 if (DECL_RESULT (fn
->decl
)
5940 && DECL_BY_REFERENCE (DECL_RESULT (fn
->decl
)))
5942 varinfo_t p
, result_vi
= get_vi_for_tree (DECL_RESULT (fn
->decl
));
5944 for (p
= result_vi
; p
; p
= vi_next (p
))
5945 make_constraint_from (p
, nonlocal_id
);
5948 /* Add a constraint for the incoming static chain parameter. */
5949 if (fn
->static_chain_decl
!= NULL_TREE
)
5951 varinfo_t p
, chain_vi
= get_vi_for_tree (fn
->static_chain_decl
);
5953 for (p
= chain_vi
; p
; p
= vi_next (p
))
5954 make_constraint_from (p
, nonlocal_id
);
5958 /* Structure used to put solution bitmaps in a hashtable so they can
5959 be shared among variables with the same points-to set. */
5961 typedef struct shared_bitmap_info
5965 } *shared_bitmap_info_t
;
5966 typedef const struct shared_bitmap_info
*const_shared_bitmap_info_t
;
5968 /* Shared_bitmap hashtable helpers. */
5970 struct shared_bitmap_hasher
: typed_free_remove
<shared_bitmap_info
>
5972 typedef shared_bitmap_info
*value_type
;
5973 typedef shared_bitmap_info
*compare_type
;
5974 static inline hashval_t
hash (const shared_bitmap_info
*);
5975 static inline bool equal (const shared_bitmap_info
*,
5976 const shared_bitmap_info
*);
5979 /* Hash function for a shared_bitmap_info_t */
5982 shared_bitmap_hasher::hash (const shared_bitmap_info
*bi
)
5984 return bi
->hashcode
;
5987 /* Equality function for two shared_bitmap_info_t's. */
5990 shared_bitmap_hasher::equal (const shared_bitmap_info
*sbi1
,
5991 const shared_bitmap_info
*sbi2
)
5993 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
5996 /* Shared_bitmap hashtable. */
5998 static hash_table
<shared_bitmap_hasher
> *shared_bitmap_table
;
6000 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
6001 existing instance if there is one, NULL otherwise. */
6004 shared_bitmap_lookup (bitmap pt_vars
)
6006 shared_bitmap_info
**slot
;
6007 struct shared_bitmap_info sbi
;
6009 sbi
.pt_vars
= pt_vars
;
6010 sbi
.hashcode
= bitmap_hash (pt_vars
);
6012 slot
= shared_bitmap_table
->find_slot (&sbi
, NO_INSERT
);
6016 return (*slot
)->pt_vars
;
6020 /* Add a bitmap to the shared bitmap hashtable. */
6023 shared_bitmap_add (bitmap pt_vars
)
6025 shared_bitmap_info
**slot
;
6026 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
6028 sbi
->pt_vars
= pt_vars
;
6029 sbi
->hashcode
= bitmap_hash (pt_vars
);
6031 slot
= shared_bitmap_table
->find_slot (sbi
, INSERT
);
6032 gcc_assert (!*slot
);
6037 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
6040 set_uids_in_ptset (bitmap into
, bitmap from
, struct pt_solution
*pt
)
6044 varinfo_t escaped_vi
= get_varinfo (find (escaped_id
));
6045 bool everything_escaped
6046 = escaped_vi
->solution
&& bitmap_bit_p (escaped_vi
->solution
, anything_id
);
6048 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
6050 varinfo_t vi
= get_varinfo (i
);
6052 /* The only artificial variables that are allowed in a may-alias
6053 set are heap variables. */
6054 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
6057 if (everything_escaped
6058 || (escaped_vi
->solution
6059 && bitmap_bit_p (escaped_vi
->solution
, i
)))
6061 pt
->vars_contains_escaped
= true;
6062 pt
->vars_contains_escaped_heap
= vi
->is_heap_var
;
6065 if (TREE_CODE (vi
->decl
) == VAR_DECL
6066 || TREE_CODE (vi
->decl
) == PARM_DECL
6067 || TREE_CODE (vi
->decl
) == RESULT_DECL
)
6069 /* If we are in IPA mode we will not recompute points-to
6070 sets after inlining so make sure they stay valid. */
6072 && !DECL_PT_UID_SET_P (vi
->decl
))
6073 SET_DECL_PT_UID (vi
->decl
, DECL_UID (vi
->decl
));
6075 /* Add the decl to the points-to set. Note that the points-to
6076 set contains global variables. */
6077 bitmap_set_bit (into
, DECL_PT_UID (vi
->decl
));
6078 if (vi
->is_global_var
)
6079 pt
->vars_contains_nonlocal
= true;
6085 /* Compute the points-to solution *PT for the variable VI. */
6087 static struct pt_solution
6088 find_what_var_points_to (varinfo_t orig_vi
)
6092 bitmap finished_solution
;
6095 struct pt_solution
*pt
;
6097 /* This variable may have been collapsed, let's get the real
6099 vi
= get_varinfo (find (orig_vi
->id
));
6101 /* See if we have already computed the solution and return it. */
6102 pt_solution
**slot
= &final_solutions
->get_or_insert (vi
);
6106 *slot
= pt
= XOBNEW (&final_solutions_obstack
, struct pt_solution
);
6107 memset (pt
, 0, sizeof (struct pt_solution
));
6109 /* Translate artificial variables into SSA_NAME_PTR_INFO
6111 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
6113 varinfo_t vi
= get_varinfo (i
);
6115 if (vi
->is_artificial_var
)
6117 if (vi
->id
== nothing_id
)
6119 else if (vi
->id
== escaped_id
)
6122 pt
->ipa_escaped
= 1;
6125 /* Expand some special vars of ESCAPED in-place here. */
6126 varinfo_t evi
= get_varinfo (find (escaped_id
));
6127 if (bitmap_bit_p (evi
->solution
, nonlocal_id
))
6130 else if (vi
->id
== nonlocal_id
)
6132 else if (vi
->is_heap_var
)
6133 /* We represent heapvars in the points-to set properly. */
6135 else if (vi
->id
== string_id
)
6136 /* Nobody cares - STRING_CSTs are read-only entities. */
6138 else if (vi
->id
== anything_id
6139 || vi
->id
== integer_id
)
6144 /* Instead of doing extra work, simply do not create
6145 elaborate points-to information for pt_anything pointers. */
6149 /* Share the final set of variables when possible. */
6150 finished_solution
= BITMAP_GGC_ALLOC ();
6151 stats
.points_to_sets_created
++;
6153 set_uids_in_ptset (finished_solution
, vi
->solution
, pt
);
6154 result
= shared_bitmap_lookup (finished_solution
);
6157 shared_bitmap_add (finished_solution
);
6158 pt
->vars
= finished_solution
;
6163 bitmap_clear (finished_solution
);
6169 /* Given a pointer variable P, fill in its points-to set. */
6172 find_what_p_points_to (tree p
)
6174 struct ptr_info_def
*pi
;
6178 /* For parameters, get at the points-to set for the actual parm
6180 if (TREE_CODE (p
) == SSA_NAME
6181 && SSA_NAME_IS_DEFAULT_DEF (p
)
6182 && (TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
6183 || TREE_CODE (SSA_NAME_VAR (p
)) == RESULT_DECL
))
6184 lookup_p
= SSA_NAME_VAR (p
);
6186 vi
= lookup_vi_for_tree (lookup_p
);
6190 pi
= get_ptr_info (p
);
6191 pi
->pt
= find_what_var_points_to (vi
);
6195 /* Query statistics for points-to solutions. */
6198 unsigned HOST_WIDE_INT pt_solution_includes_may_alias
;
6199 unsigned HOST_WIDE_INT pt_solution_includes_no_alias
;
6200 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias
;
6201 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias
;
6205 dump_pta_stats (FILE *s
)
6207 fprintf (s
, "\nPTA query stats:\n");
6208 fprintf (s
, " pt_solution_includes: "
6209 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6210 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6211 pta_stats
.pt_solution_includes_no_alias
,
6212 pta_stats
.pt_solution_includes_no_alias
6213 + pta_stats
.pt_solution_includes_may_alias
);
6214 fprintf (s
, " pt_solutions_intersect: "
6215 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
6216 HOST_WIDE_INT_PRINT_DEC
" queries\n",
6217 pta_stats
.pt_solutions_intersect_no_alias
,
6218 pta_stats
.pt_solutions_intersect_no_alias
6219 + pta_stats
.pt_solutions_intersect_may_alias
);
6223 /* Reset the points-to solution *PT to a conservative default
6224 (point to anything). */
6227 pt_solution_reset (struct pt_solution
*pt
)
6229 memset (pt
, 0, sizeof (struct pt_solution
));
6230 pt
->anything
= true;
6233 /* Set the points-to solution *PT to point only to the variables
6234 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6235 global variables and VARS_CONTAINS_RESTRICT specifies whether
6236 it contains restrict tag variables. */
6239 pt_solution_set (struct pt_solution
*pt
, bitmap vars
,
6240 bool vars_contains_nonlocal
)
6242 memset (pt
, 0, sizeof (struct pt_solution
));
6244 pt
->vars_contains_nonlocal
= vars_contains_nonlocal
;
6245 pt
->vars_contains_escaped
6246 = (cfun
->gimple_df
->escaped
.anything
6247 || bitmap_intersect_p (cfun
->gimple_df
->escaped
.vars
, vars
));
6250 /* Set the points-to solution *PT to point only to the variable VAR. */
6253 pt_solution_set_var (struct pt_solution
*pt
, tree var
)
6255 memset (pt
, 0, sizeof (struct pt_solution
));
6256 pt
->vars
= BITMAP_GGC_ALLOC ();
6257 bitmap_set_bit (pt
->vars
, DECL_PT_UID (var
));
6258 pt
->vars_contains_nonlocal
= is_global_var (var
);
6259 pt
->vars_contains_escaped
6260 = (cfun
->gimple_df
->escaped
.anything
6261 || bitmap_bit_p (cfun
->gimple_df
->escaped
.vars
, DECL_PT_UID (var
)));
6264 /* Computes the union of the points-to solutions *DEST and *SRC and
6265 stores the result in *DEST. This changes the points-to bitmap
6266 of *DEST and thus may not be used if that might be shared.
6267 The points-to bitmap of *SRC and *DEST will not be shared after
6268 this function if they were not before. */
6271 pt_solution_ior_into (struct pt_solution
*dest
, struct pt_solution
*src
)
6273 dest
->anything
|= src
->anything
;
6276 pt_solution_reset (dest
);
6280 dest
->nonlocal
|= src
->nonlocal
;
6281 dest
->escaped
|= src
->escaped
;
6282 dest
->ipa_escaped
|= src
->ipa_escaped
;
6283 dest
->null
|= src
->null
;
6284 dest
->vars_contains_nonlocal
|= src
->vars_contains_nonlocal
;
6285 dest
->vars_contains_escaped
|= src
->vars_contains_escaped
;
6286 dest
->vars_contains_escaped_heap
|= src
->vars_contains_escaped_heap
;
6291 dest
->vars
= BITMAP_GGC_ALLOC ();
6292 bitmap_ior_into (dest
->vars
, src
->vars
);
6295 /* Return true if the points-to solution *PT is empty. */
6298 pt_solution_empty_p (struct pt_solution
*pt
)
6305 && !bitmap_empty_p (pt
->vars
))
6308 /* If the solution includes ESCAPED, check if that is empty. */
6310 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
6313 /* If the solution includes ESCAPED, check if that is empty. */
6315 && !pt_solution_empty_p (&ipa_escaped_pt
))
6321 /* Return true if the points-to solution *PT only point to a single var, and
6322 return the var uid in *UID. */
6325 pt_solution_singleton_p (struct pt_solution
*pt
, unsigned *uid
)
6327 if (pt
->anything
|| pt
->nonlocal
|| pt
->escaped
|| pt
->ipa_escaped
6328 || pt
->null
|| pt
->vars
== NULL
6329 || !bitmap_single_bit_set_p (pt
->vars
))
6332 *uid
= bitmap_first_set_bit (pt
->vars
);
6336 /* Return true if the points-to solution *PT includes global memory. */
6339 pt_solution_includes_global (struct pt_solution
*pt
)
6343 || pt
->vars_contains_nonlocal
6344 /* The following is a hack to make the malloc escape hack work.
6345 In reality we'd need different sets for escaped-through-return
6346 and escaped-to-callees and passes would need to be updated. */
6347 || pt
->vars_contains_escaped_heap
)
6350 /* 'escaped' is also a placeholder so we have to look into it. */
6352 return pt_solution_includes_global (&cfun
->gimple_df
->escaped
);
6354 if (pt
->ipa_escaped
)
6355 return pt_solution_includes_global (&ipa_escaped_pt
);
6357 /* ??? This predicate is not correct for the IPA-PTA solution
6358 as we do not properly distinguish between unit escape points
6359 and global variables. */
6360 if (cfun
->gimple_df
->ipa_pta
)
6366 /* Return true if the points-to solution *PT includes the variable
6367 declaration DECL. */
6370 pt_solution_includes_1 (struct pt_solution
*pt
, const_tree decl
)
6376 && is_global_var (decl
))
6380 && bitmap_bit_p (pt
->vars
, DECL_PT_UID (decl
)))
6383 /* If the solution includes ESCAPED, check it. */
6385 && pt_solution_includes_1 (&cfun
->gimple_df
->escaped
, decl
))
6388 /* If the solution includes ESCAPED, check it. */
6390 && pt_solution_includes_1 (&ipa_escaped_pt
, decl
))
6397 pt_solution_includes (struct pt_solution
*pt
, const_tree decl
)
6399 bool res
= pt_solution_includes_1 (pt
, decl
);
6401 ++pta_stats
.pt_solution_includes_may_alias
;
6403 ++pta_stats
.pt_solution_includes_no_alias
;
6407 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6411 pt_solutions_intersect_1 (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6413 if (pt1
->anything
|| pt2
->anything
)
6416 /* If either points to unknown global memory and the other points to
6417 any global memory they alias. */
6420 || pt2
->vars_contains_nonlocal
))
6422 && pt1
->vars_contains_nonlocal
))
6425 /* If either points to all escaped memory and the other points to
6426 any escaped memory they alias. */
6429 || pt2
->vars_contains_escaped
))
6431 && pt1
->vars_contains_escaped
))
6434 /* Check the escaped solution if required.
6435 ??? Do we need to check the local against the IPA escaped sets? */
6436 if ((pt1
->ipa_escaped
|| pt2
->ipa_escaped
)
6437 && !pt_solution_empty_p (&ipa_escaped_pt
))
6439 /* If both point to escaped memory and that solution
6440 is not empty they alias. */
6441 if (pt1
->ipa_escaped
&& pt2
->ipa_escaped
)
6444 /* If either points to escaped memory see if the escaped solution
6445 intersects with the other. */
6446 if ((pt1
->ipa_escaped
6447 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt2
))
6448 || (pt2
->ipa_escaped
6449 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt1
)))
6453 /* Now both pointers alias if their points-to solution intersects. */
6456 && bitmap_intersect_p (pt1
->vars
, pt2
->vars
));
6460 pt_solutions_intersect (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6462 bool res
= pt_solutions_intersect_1 (pt1
, pt2
);
6464 ++pta_stats
.pt_solutions_intersect_may_alias
;
6466 ++pta_stats
.pt_solutions_intersect_no_alias
;
6471 /* Dump points-to information to OUTFILE. */
6474 dump_sa_points_to_info (FILE *outfile
)
6478 fprintf (outfile
, "\nPoints-to sets\n\n");
6480 if (dump_flags
& TDF_STATS
)
6482 fprintf (outfile
, "Stats:\n");
6483 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
6484 fprintf (outfile
, "Non-pointer vars: %d\n",
6485 stats
.nonpointer_vars
);
6486 fprintf (outfile
, "Statically unified vars: %d\n",
6487 stats
.unified_vars_static
);
6488 fprintf (outfile
, "Dynamically unified vars: %d\n",
6489 stats
.unified_vars_dynamic
);
6490 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
6491 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
6492 fprintf (outfile
, "Number of implicit edges: %d\n",
6493 stats
.num_implicit_edges
);
6496 for (i
= 1; i
< varmap
.length (); i
++)
6498 varinfo_t vi
= get_varinfo (i
);
6499 if (!vi
->may_have_pointers
)
6501 dump_solution_for_var (outfile
, i
);
6506 /* Debug points-to information to stderr. */
6509 debug_sa_points_to_info (void)
6511 dump_sa_points_to_info (stderr
);
6515 /* Initialize the always-existing constraint variables for NULL
6516 ANYTHING, READONLY, and INTEGER */
6519 init_base_vars (void)
6521 struct constraint_expr lhs
, rhs
;
6522 varinfo_t var_anything
;
6523 varinfo_t var_nothing
;
6524 varinfo_t var_string
;
6525 varinfo_t var_escaped
;
6526 varinfo_t var_nonlocal
;
6527 varinfo_t var_storedanything
;
6528 varinfo_t var_integer
;
6530 /* Variable ID zero is reserved and should be NULL. */
6531 varmap
.safe_push (NULL
);
6533 /* Create the NULL variable, used to represent that a variable points
6535 var_nothing
= new_var_info (NULL_TREE
, "NULL");
6536 gcc_assert (var_nothing
->id
== nothing_id
);
6537 var_nothing
->is_artificial_var
= 1;
6538 var_nothing
->offset
= 0;
6539 var_nothing
->size
= ~0;
6540 var_nothing
->fullsize
= ~0;
6541 var_nothing
->is_special_var
= 1;
6542 var_nothing
->may_have_pointers
= 0;
6543 var_nothing
->is_global_var
= 0;
6545 /* Create the ANYTHING variable, used to represent that a variable
6546 points to some unknown piece of memory. */
6547 var_anything
= new_var_info (NULL_TREE
, "ANYTHING");
6548 gcc_assert (var_anything
->id
== anything_id
);
6549 var_anything
->is_artificial_var
= 1;
6550 var_anything
->size
= ~0;
6551 var_anything
->offset
= 0;
6552 var_anything
->fullsize
= ~0;
6553 var_anything
->is_special_var
= 1;
6555 /* Anything points to anything. This makes deref constraints just
6556 work in the presence of linked list and other p = *p type loops,
6557 by saying that *ANYTHING = ANYTHING. */
6559 lhs
.var
= anything_id
;
6561 rhs
.type
= ADDRESSOF
;
6562 rhs
.var
= anything_id
;
6565 /* This specifically does not use process_constraint because
6566 process_constraint ignores all anything = anything constraints, since all
6567 but this one are redundant. */
6568 constraints
.safe_push (new_constraint (lhs
, rhs
));
6570 /* Create the STRING variable, used to represent that a variable
6571 points to a string literal. String literals don't contain
6572 pointers so STRING doesn't point to anything. */
6573 var_string
= new_var_info (NULL_TREE
, "STRING");
6574 gcc_assert (var_string
->id
== string_id
);
6575 var_string
->is_artificial_var
= 1;
6576 var_string
->offset
= 0;
6577 var_string
->size
= ~0;
6578 var_string
->fullsize
= ~0;
6579 var_string
->is_special_var
= 1;
6580 var_string
->may_have_pointers
= 0;
6582 /* Create the ESCAPED variable, used to represent the set of escaped
6584 var_escaped
= new_var_info (NULL_TREE
, "ESCAPED");
6585 gcc_assert (var_escaped
->id
== escaped_id
);
6586 var_escaped
->is_artificial_var
= 1;
6587 var_escaped
->offset
= 0;
6588 var_escaped
->size
= ~0;
6589 var_escaped
->fullsize
= ~0;
6590 var_escaped
->is_special_var
= 0;
6592 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6594 var_nonlocal
= new_var_info (NULL_TREE
, "NONLOCAL");
6595 gcc_assert (var_nonlocal
->id
== nonlocal_id
);
6596 var_nonlocal
->is_artificial_var
= 1;
6597 var_nonlocal
->offset
= 0;
6598 var_nonlocal
->size
= ~0;
6599 var_nonlocal
->fullsize
= ~0;
6600 var_nonlocal
->is_special_var
= 1;
6602 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6604 lhs
.var
= escaped_id
;
6607 rhs
.var
= escaped_id
;
6609 process_constraint (new_constraint (lhs
, rhs
));
6611 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6612 whole variable escapes. */
6614 lhs
.var
= escaped_id
;
6617 rhs
.var
= escaped_id
;
6618 rhs
.offset
= UNKNOWN_OFFSET
;
6619 process_constraint (new_constraint (lhs
, rhs
));
6621 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6622 everything pointed to by escaped points to what global memory can
6625 lhs
.var
= escaped_id
;
6628 rhs
.var
= nonlocal_id
;
6630 process_constraint (new_constraint (lhs
, rhs
));
6632 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6633 global memory may point to global memory and escaped memory. */
6635 lhs
.var
= nonlocal_id
;
6637 rhs
.type
= ADDRESSOF
;
6638 rhs
.var
= nonlocal_id
;
6640 process_constraint (new_constraint (lhs
, rhs
));
6641 rhs
.type
= ADDRESSOF
;
6642 rhs
.var
= escaped_id
;
6644 process_constraint (new_constraint (lhs
, rhs
));
6646 /* Create the STOREDANYTHING variable, used to represent the set of
6647 variables stored to *ANYTHING. */
6648 var_storedanything
= new_var_info (NULL_TREE
, "STOREDANYTHING");
6649 gcc_assert (var_storedanything
->id
== storedanything_id
);
6650 var_storedanything
->is_artificial_var
= 1;
6651 var_storedanything
->offset
= 0;
6652 var_storedanything
->size
= ~0;
6653 var_storedanything
->fullsize
= ~0;
6654 var_storedanything
->is_special_var
= 0;
6656 /* Create the INTEGER variable, used to represent that a variable points
6657 to what an INTEGER "points to". */
6658 var_integer
= new_var_info (NULL_TREE
, "INTEGER");
6659 gcc_assert (var_integer
->id
== integer_id
);
6660 var_integer
->is_artificial_var
= 1;
6661 var_integer
->size
= ~0;
6662 var_integer
->fullsize
= ~0;
6663 var_integer
->offset
= 0;
6664 var_integer
->is_special_var
= 1;
6666 /* INTEGER = ANYTHING, because we don't know where a dereference of
6667 a random integer will point to. */
6669 lhs
.var
= integer_id
;
6671 rhs
.type
= ADDRESSOF
;
6672 rhs
.var
= anything_id
;
6674 process_constraint (new_constraint (lhs
, rhs
));
6677 /* Initialize things necessary to perform PTA */
6680 init_alias_vars (void)
6682 use_field_sensitive
= (MAX_FIELDS_FOR_FIELD_SENSITIVE
> 1);
6684 bitmap_obstack_initialize (&pta_obstack
);
6685 bitmap_obstack_initialize (&oldpta_obstack
);
6686 bitmap_obstack_initialize (&predbitmap_obstack
);
6688 constraint_pool
= create_alloc_pool ("Constraint pool",
6689 sizeof (struct constraint
), 30);
6690 variable_info_pool
= create_alloc_pool ("Variable info pool",
6691 sizeof (struct variable_info
), 30);
6692 constraints
.create (8);
6694 vi_for_tree
= new hash_map
<tree
, varinfo_t
>;
6695 call_stmt_vars
= new hash_map
<gimple
, varinfo_t
>;
6697 memset (&stats
, 0, sizeof (stats
));
6698 shared_bitmap_table
= new hash_table
<shared_bitmap_hasher
> (511);
6701 gcc_obstack_init (&fake_var_decl_obstack
);
6703 final_solutions
= new hash_map
<varinfo_t
, pt_solution
*>;
6704 gcc_obstack_init (&final_solutions_obstack
);
6707 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6708 predecessor edges. */
6711 remove_preds_and_fake_succs (constraint_graph_t graph
)
6715 /* Clear the implicit ref and address nodes from the successor
6717 for (i
= 1; i
< FIRST_REF_NODE
; i
++)
6719 if (graph
->succs
[i
])
6720 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
6721 FIRST_REF_NODE
* 2);
6724 /* Free the successor list for the non-ref nodes. */
6725 for (i
= FIRST_REF_NODE
+ 1; i
< graph
->size
; i
++)
6727 if (graph
->succs
[i
])
6728 BITMAP_FREE (graph
->succs
[i
]);
6731 /* Now reallocate the size of the successor list as, and blow away
6732 the predecessor bitmaps. */
6733 graph
->size
= varmap
.length ();
6734 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
6736 free (graph
->implicit_preds
);
6737 graph
->implicit_preds
= NULL
;
6738 free (graph
->preds
);
6739 graph
->preds
= NULL
;
6740 bitmap_obstack_release (&predbitmap_obstack
);
6743 /* Solve the constraint set. */
6746 solve_constraints (void)
6748 struct scc_info
*si
;
6752 "\nCollapsing static cycles and doing variable "
6755 init_graph (varmap
.length () * 2);
6758 fprintf (dump_file
, "Building predecessor graph\n");
6759 build_pred_graph ();
6762 fprintf (dump_file
, "Detecting pointer and location "
6764 si
= perform_var_substitution (graph
);
6767 fprintf (dump_file
, "Rewriting constraints and unifying "
6769 rewrite_constraints (graph
, si
);
6771 build_succ_graph ();
6773 free_var_substitution_info (si
);
6775 /* Attach complex constraints to graph nodes. */
6776 move_complex_constraints (graph
);
6779 fprintf (dump_file
, "Uniting pointer but not location equivalent "
6781 unite_pointer_equivalences (graph
);
6784 fprintf (dump_file
, "Finding indirect cycles\n");
6785 find_indirect_cycles (graph
);
6787 /* Implicit nodes and predecessors are no longer necessary at this
6789 remove_preds_and_fake_succs (graph
);
6791 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
6793 fprintf (dump_file
, "\n\n// The constraint graph before solve-graph "
6794 "in dot format:\n");
6795 dump_constraint_graph (dump_file
);
6796 fprintf (dump_file
, "\n\n");
6800 fprintf (dump_file
, "Solving graph\n");
6802 solve_graph (graph
);
6804 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
6806 fprintf (dump_file
, "\n\n// The constraint graph after solve-graph "
6807 "in dot format:\n");
6808 dump_constraint_graph (dump_file
);
6809 fprintf (dump_file
, "\n\n");
6813 dump_sa_points_to_info (dump_file
);
6816 /* Create points-to sets for the current function. See the comments
6817 at the start of the file for an algorithmic overview. */
6820 compute_points_to_sets (void)
6826 timevar_push (TV_TREE_PTA
);
6830 intra_create_variable_infos (cfun
);
6832 /* Now walk all statements and build the constraint set. */
6833 FOR_EACH_BB_FN (bb
, cfun
)
6835 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
6838 gphi
*phi
= gsi
.phi ();
6840 if (! virtual_operand_p (gimple_phi_result (phi
)))
6841 find_func_aliases (cfun
, phi
);
6844 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
6847 gimple stmt
= gsi_stmt (gsi
);
6849 find_func_aliases (cfun
, stmt
);
6855 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
6856 dump_constraints (dump_file
, 0);
6859 /* From the constraints compute the points-to sets. */
6860 solve_constraints ();
6862 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
6863 cfun
->gimple_df
->escaped
= find_what_var_points_to (get_varinfo (escaped_id
));
6865 /* Make sure the ESCAPED solution (which is used as placeholder in
6866 other solutions) does not reference itself. This simplifies
6867 points-to solution queries. */
6868 cfun
->gimple_df
->escaped
.escaped
= 0;
6870 /* Compute the points-to sets for pointer SSA_NAMEs. */
6871 for (i
= 0; i
< num_ssa_names
; ++i
)
6873 tree ptr
= ssa_name (i
);
6875 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
6876 find_what_p_points_to (ptr
);
6879 /* Compute the call-used/clobbered sets. */
6880 FOR_EACH_BB_FN (bb
, cfun
)
6882 gimple_stmt_iterator gsi
;
6884 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6887 struct pt_solution
*pt
;
6889 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
6893 pt
= gimple_call_use_set (stmt
);
6894 if (gimple_call_flags (stmt
) & ECF_CONST
)
6895 memset (pt
, 0, sizeof (struct pt_solution
));
6896 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
6898 *pt
= find_what_var_points_to (vi
);
6899 /* Escaped (and thus nonlocal) variables are always
6900 implicitly used by calls. */
6901 /* ??? ESCAPED can be empty even though NONLOCAL
6908 /* If there is nothing special about this call then
6909 we have made everything that is used also escape. */
6910 *pt
= cfun
->gimple_df
->escaped
;
6914 pt
= gimple_call_clobber_set (stmt
);
6915 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
6916 memset (pt
, 0, sizeof (struct pt_solution
));
6917 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
6919 *pt
= find_what_var_points_to (vi
);
6920 /* Escaped (and thus nonlocal) variables are always
6921 implicitly clobbered by calls. */
6922 /* ??? ESCAPED can be empty even though NONLOCAL
6929 /* If there is nothing special about this call then
6930 we have made everything that is used also escape. */
6931 *pt
= cfun
->gimple_df
->escaped
;
6937 timevar_pop (TV_TREE_PTA
);
6941 /* Delete created points-to sets. */
6944 delete_points_to_sets (void)
6948 delete shared_bitmap_table
;
6949 shared_bitmap_table
= NULL
;
6950 if (dump_file
&& (dump_flags
& TDF_STATS
))
6951 fprintf (dump_file
, "Points to sets created:%d\n",
6952 stats
.points_to_sets_created
);
6955 delete call_stmt_vars
;
6956 bitmap_obstack_release (&pta_obstack
);
6957 constraints
.release ();
6959 for (i
= 0; i
< graph
->size
; i
++)
6960 graph
->complex[i
].release ();
6961 free (graph
->complex);
6964 free (graph
->succs
);
6966 free (graph
->pe_rep
);
6967 free (graph
->indirect_cycles
);
6971 free_alloc_pool (variable_info_pool
);
6972 free_alloc_pool (constraint_pool
);
6974 obstack_free (&fake_var_decl_obstack
, NULL
);
6976 delete final_solutions
;
6977 obstack_free (&final_solutions_obstack
, NULL
);
6980 /* Mark "other" loads and stores as belonging to CLIQUE and with
6984 visit_loadstore (gimple
, tree base
, tree ref
, void *clique_
)
6986 unsigned short clique
= (uintptr_t)clique_
;
6987 if (TREE_CODE (base
) == MEM_REF
6988 || TREE_CODE (base
) == TARGET_MEM_REF
)
6990 tree ptr
= TREE_OPERAND (base
, 0);
6991 if (TREE_CODE (ptr
) == SSA_NAME
)
6993 /* ??? We need to make sure 'ptr' doesn't include any of
6994 the restrict tags in its points-to set. */
6998 /* For now let decls through. */
7000 /* Do not overwrite existing cliques (that includes clique, base
7001 pairs we just set). */
7002 if (MR_DEPENDENCE_CLIQUE (base
) == 0)
7004 MR_DEPENDENCE_CLIQUE (base
) = clique
;
7005 MR_DEPENDENCE_BASE (base
) = 0;
7009 /* For plain decl accesses see whether they are accesses to globals
7010 and rewrite them to MEM_REFs with { clique, 0 }. */
7011 if (TREE_CODE (base
) == VAR_DECL
7012 && is_global_var (base
)
7013 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
7018 while (handled_component_p (*basep
))
7019 basep
= &TREE_OPERAND (*basep
, 0);
7020 gcc_assert (TREE_CODE (*basep
) == VAR_DECL
);
7021 tree ptr
= build_fold_addr_expr (*basep
);
7022 tree zero
= build_int_cst (TREE_TYPE (ptr
), 0);
7023 *basep
= build2 (MEM_REF
, TREE_TYPE (*basep
), ptr
, zero
);
7024 MR_DEPENDENCE_CLIQUE (*basep
) = clique
;
7025 MR_DEPENDENCE_BASE (*basep
) = 0;
7031 /* If REF is a MEM_REF then assign a clique, base pair to it, updating
7032 CLIQUE, *RESTRICT_VAR and LAST_RUID. Return whether dependence info
7033 was assigned to REF. */
7036 maybe_set_dependence_info (tree ref
, tree ptr
,
7037 unsigned short &clique
, varinfo_t restrict_var
,
7038 unsigned short &last_ruid
)
7040 while (handled_component_p (ref
))
7041 ref
= TREE_OPERAND (ref
, 0);
7042 if ((TREE_CODE (ref
) == MEM_REF
7043 || TREE_CODE (ref
) == TARGET_MEM_REF
)
7044 && TREE_OPERAND (ref
, 0) == ptr
)
7046 /* Do not overwrite existing cliques. This avoids overwriting dependence
7047 info inlined from a function with restrict parameters inlined
7048 into a function with restrict parameters. This usually means we
7049 prefer to be precise in innermost loops. */
7050 if (MR_DEPENDENCE_CLIQUE (ref
) == 0)
7053 clique
= ++cfun
->last_clique
;
7054 if (restrict_var
->ruid
== 0)
7055 restrict_var
->ruid
= ++last_ruid
;
7056 MR_DEPENDENCE_CLIQUE (ref
) = clique
;
7057 MR_DEPENDENCE_BASE (ref
) = restrict_var
->ruid
;
7064 /* Compute the set of independend memory references based on restrict
7065 tags and their conservative propagation to the points-to sets. */
7068 compute_dependence_clique (void)
7070 unsigned short clique
= 0;
7071 unsigned short last_ruid
= 0;
7072 for (unsigned i
= 0; i
< num_ssa_names
; ++i
)
7074 tree ptr
= ssa_name (i
);
7075 if (!ptr
|| !POINTER_TYPE_P (TREE_TYPE (ptr
)))
7078 /* Avoid all this when ptr is not dereferenced? */
7080 if (SSA_NAME_IS_DEFAULT_DEF (ptr
)
7081 && (TREE_CODE (SSA_NAME_VAR (ptr
)) == PARM_DECL
7082 || TREE_CODE (SSA_NAME_VAR (ptr
)) == RESULT_DECL
))
7083 p
= SSA_NAME_VAR (ptr
);
7084 varinfo_t vi
= lookup_vi_for_tree (p
);
7087 vi
= get_varinfo (find (vi
->id
));
7090 varinfo_t restrict_var
= NULL
;
7091 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, j
, bi
)
7093 varinfo_t oi
= get_varinfo (j
);
7094 if (oi
->is_restrict_var
)
7098 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7100 fprintf (dump_file
, "found restrict pointed-to "
7102 print_generic_expr (dump_file
, ptr
, 0);
7103 fprintf (dump_file
, " but not exclusively\n");
7105 restrict_var
= NULL
;
7110 /* NULL is the only other valid points-to entry. */
7111 else if (oi
->id
!= nothing_id
)
7113 restrict_var
= NULL
;
7117 /* Ok, found that ptr must(!) point to a single(!) restrict
7119 /* ??? PTA isn't really a proper propagation engine to compute
7121 ??? We could handle merging of two restricts by unifying them. */
7124 /* Now look at possible dereferences of ptr. */
7125 imm_use_iterator ui
;
7127 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, ptr
)
7129 /* ??? Calls and asms. */
7130 if (!gimple_assign_single_p (use_stmt
))
7132 maybe_set_dependence_info (gimple_assign_lhs (use_stmt
), ptr
,
7133 clique
, restrict_var
, last_ruid
);
7134 maybe_set_dependence_info (gimple_assign_rhs1 (use_stmt
), ptr
,
7135 clique
, restrict_var
, last_ruid
);
7143 /* Assign the BASE id zero to all accesses not based on a restrict
7144 pointer. That way they get disabiguated against restrict
7145 accesses but not against each other. */
7146 /* ??? For restricts derived from globals (thus not incoming
7147 parameters) we can't restrict scoping properly thus the following
7148 is too aggressive there. For now we have excluded those globals from
7149 getting into the MR_DEPENDENCE machinery. */
7151 FOR_EACH_BB_FN (bb
, cfun
)
7152 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
7153 !gsi_end_p (gsi
); gsi_next (&gsi
))
7155 gimple stmt
= gsi_stmt (gsi
);
7156 walk_stmt_load_store_ops (stmt
, (void *)(uintptr_t)clique
,
7157 visit_loadstore
, visit_loadstore
);
7161 /* Compute points-to information for every SSA_NAME pointer in the
7162 current function and compute the transitive closure of escaped
7163 variables to re-initialize the call-clobber states of local variables. */
7166 compute_may_aliases (void)
7168 if (cfun
->gimple_df
->ipa_pta
)
7172 fprintf (dump_file
, "\nNot re-computing points-to information "
7173 "because IPA points-to information is available.\n\n");
7175 /* But still dump what we have remaining it. */
7176 dump_alias_info (dump_file
);
7182 /* For each pointer P_i, determine the sets of variables that P_i may
7183 point-to. Compute the reachability set of escaped and call-used
7185 compute_points_to_sets ();
7187 /* Debugging dumps. */
7189 dump_alias_info (dump_file
);
7191 /* Compute restrict-based memory disambiguations. */
7192 compute_dependence_clique ();
7194 /* Deallocate memory used by aliasing data structures and the internal
7195 points-to solution. */
7196 delete_points_to_sets ();
7198 gcc_assert (!need_ssa_update_p (cfun
));
7203 /* A dummy pass to cause points-to information to be computed via
7204 TODO_rebuild_alias. */
7208 const pass_data pass_data_build_alias
=
7210 GIMPLE_PASS
, /* type */
7212 OPTGROUP_NONE
, /* optinfo_flags */
7213 TV_NONE
, /* tv_id */
7214 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7215 0, /* properties_provided */
7216 0, /* properties_destroyed */
7217 0, /* todo_flags_start */
7218 TODO_rebuild_alias
, /* todo_flags_finish */
7221 class pass_build_alias
: public gimple_opt_pass
7224 pass_build_alias (gcc::context
*ctxt
)
7225 : gimple_opt_pass (pass_data_build_alias
, ctxt
)
7228 /* opt_pass methods: */
7229 virtual bool gate (function
*) { return flag_tree_pta
; }
7231 }; // class pass_build_alias
7236 make_pass_build_alias (gcc::context
*ctxt
)
7238 return new pass_build_alias (ctxt
);
7241 /* A dummy pass to cause points-to information to be computed via
7242 TODO_rebuild_alias. */
7246 const pass_data pass_data_build_ealias
=
7248 GIMPLE_PASS
, /* type */
7249 "ealias", /* name */
7250 OPTGROUP_NONE
, /* optinfo_flags */
7251 TV_NONE
, /* tv_id */
7252 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7253 0, /* properties_provided */
7254 0, /* properties_destroyed */
7255 0, /* todo_flags_start */
7256 TODO_rebuild_alias
, /* todo_flags_finish */
7259 class pass_build_ealias
: public gimple_opt_pass
7262 pass_build_ealias (gcc::context
*ctxt
)
7263 : gimple_opt_pass (pass_data_build_ealias
, ctxt
)
7266 /* opt_pass methods: */
7267 virtual bool gate (function
*) { return flag_tree_pta
; }
7269 }; // class pass_build_ealias
7274 make_pass_build_ealias (gcc::context
*ctxt
)
7276 return new pass_build_ealias (ctxt
);
7280 /* IPA PTA solutions for ESCAPED. */
7281 struct pt_solution ipa_escaped_pt
7282 = { true, false, false, false, false, false, false, false, NULL
};
7284 /* Associate node with varinfo DATA. Worker for
7285 cgraph_for_node_and_aliases. */
7287 associate_varinfo_to_alias (struct cgraph_node
*node
, void *data
)
7289 if ((node
->alias
|| node
->thunk
.thunk_p
)
7291 insert_vi_for_tree (node
->decl
, (varinfo_t
)data
);
7295 /* Execute the driver for IPA PTA. */
7297 ipa_pta_execute (void)
7299 struct cgraph_node
*node
;
7307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7309 symtab_node::dump_table (dump_file
);
7310 fprintf (dump_file
, "\n");
7313 /* Build the constraints. */
7314 FOR_EACH_DEFINED_FUNCTION (node
)
7317 /* Nodes without a body are not interesting. Especially do not
7318 visit clones at this point for now - we get duplicate decls
7319 there for inline clones at least. */
7320 if (!node
->has_gimple_body_p () || node
->global
.inlined_to
)
7324 gcc_assert (!node
->clone_of
);
7326 vi
= create_function_info_for (node
->decl
,
7327 alias_get_name (node
->decl
));
7328 node
->call_for_symbol_thunks_and_aliases
7329 (associate_varinfo_to_alias
, vi
, true);
7332 /* Create constraints for global variables and their initializers. */
7333 FOR_EACH_VARIABLE (var
)
7335 if (var
->alias
&& var
->analyzed
)
7338 get_vi_for_tree (var
->decl
);
7344 "Generating constraints for global initializers\n\n");
7345 dump_constraints (dump_file
, 0);
7346 fprintf (dump_file
, "\n");
7348 from
= constraints
.length ();
7350 FOR_EACH_DEFINED_FUNCTION (node
)
7352 struct function
*func
;
7355 /* Nodes without a body are not interesting. */
7356 if (!node
->has_gimple_body_p () || node
->clone_of
)
7362 "Generating constraints for %s", node
->name ());
7363 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
7364 fprintf (dump_file
, " (%s)",
7366 (DECL_ASSEMBLER_NAME (node
->decl
)));
7367 fprintf (dump_file
, "\n");
7370 func
= DECL_STRUCT_FUNCTION (node
->decl
);
7371 gcc_assert (cfun
== NULL
);
7373 /* For externally visible or attribute used annotated functions use
7374 local constraints for their arguments.
7375 For local functions we see all callers and thus do not need initial
7376 constraints for parameters. */
7377 if (node
->used_from_other_partition
7378 || node
->externally_visible
7379 || node
->force_output
)
7381 intra_create_variable_infos (func
);
7383 /* We also need to make function return values escape. Nothing
7384 escapes by returning from main though. */
7385 if (!MAIN_NAME_P (DECL_NAME (node
->decl
)))
7388 fi
= lookup_vi_for_tree (node
->decl
);
7389 rvi
= first_vi_for_offset (fi
, fi_result
);
7390 if (rvi
&& rvi
->offset
== fi_result
)
7392 struct constraint_expr includes
;
7393 struct constraint_expr var
;
7394 includes
.var
= escaped_id
;
7395 includes
.offset
= 0;
7396 includes
.type
= SCALAR
;
7400 process_constraint (new_constraint (includes
, var
));
7405 /* Build constriants for the function body. */
7406 FOR_EACH_BB_FN (bb
, func
)
7408 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7411 gphi
*phi
= gsi
.phi ();
7413 if (! virtual_operand_p (gimple_phi_result (phi
)))
7414 find_func_aliases (func
, phi
);
7417 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
7420 gimple stmt
= gsi_stmt (gsi
);
7422 find_func_aliases (func
, stmt
);
7423 find_func_clobbers (func
, stmt
);
7429 fprintf (dump_file
, "\n");
7430 dump_constraints (dump_file
, from
);
7431 fprintf (dump_file
, "\n");
7433 from
= constraints
.length ();
7436 /* From the constraints compute the points-to sets. */
7437 solve_constraints ();
7439 /* Compute the global points-to sets for ESCAPED.
7440 ??? Note that the computed escape set is not correct
7441 for the whole unit as we fail to consider graph edges to
7442 externally visible functions. */
7443 ipa_escaped_pt
= find_what_var_points_to (get_varinfo (escaped_id
));
7445 /* Make sure the ESCAPED solution (which is used as placeholder in
7446 other solutions) does not reference itself. This simplifies
7447 points-to solution queries. */
7448 ipa_escaped_pt
.ipa_escaped
= 0;
7450 /* Assign the points-to sets to the SSA names in the unit. */
7451 FOR_EACH_DEFINED_FUNCTION (node
)
7454 struct function
*fn
;
7458 /* Nodes without a body are not interesting. */
7459 if (!node
->has_gimple_body_p () || node
->clone_of
)
7462 fn
= DECL_STRUCT_FUNCTION (node
->decl
);
7464 /* Compute the points-to sets for pointer SSA_NAMEs. */
7465 FOR_EACH_VEC_ELT (*fn
->gimple_df
->ssa_names
, i
, ptr
)
7468 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
7469 find_what_p_points_to (ptr
);
7472 /* Compute the call-use and call-clobber sets for indirect calls
7473 and calls to external functions. */
7474 FOR_EACH_BB_FN (bb
, fn
)
7476 gimple_stmt_iterator gsi
;
7478 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
7481 struct pt_solution
*pt
;
7485 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
7489 /* Handle direct calls to functions with body. */
7490 decl
= gimple_call_fndecl (stmt
);
7492 && (fi
= lookup_vi_for_tree (decl
))
7495 *gimple_call_clobber_set (stmt
)
7496 = find_what_var_points_to
7497 (first_vi_for_offset (fi
, fi_clobbers
));
7498 *gimple_call_use_set (stmt
)
7499 = find_what_var_points_to
7500 (first_vi_for_offset (fi
, fi_uses
));
7502 /* Handle direct calls to external functions. */
7505 pt
= gimple_call_use_set (stmt
);
7506 if (gimple_call_flags (stmt
) & ECF_CONST
)
7507 memset (pt
, 0, sizeof (struct pt_solution
));
7508 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
7510 *pt
= find_what_var_points_to (vi
);
7511 /* Escaped (and thus nonlocal) variables are always
7512 implicitly used by calls. */
7513 /* ??? ESCAPED can be empty even though NONLOCAL
7516 pt
->ipa_escaped
= 1;
7520 /* If there is nothing special about this call then
7521 we have made everything that is used also escape. */
7522 *pt
= ipa_escaped_pt
;
7526 pt
= gimple_call_clobber_set (stmt
);
7527 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
7528 memset (pt
, 0, sizeof (struct pt_solution
));
7529 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
7531 *pt
= find_what_var_points_to (vi
);
7532 /* Escaped (and thus nonlocal) variables are always
7533 implicitly clobbered by calls. */
7534 /* ??? ESCAPED can be empty even though NONLOCAL
7537 pt
->ipa_escaped
= 1;
7541 /* If there is nothing special about this call then
7542 we have made everything that is used also escape. */
7543 *pt
= ipa_escaped_pt
;
7547 /* Handle indirect calls. */
7549 && (fi
= get_fi_for_callee (stmt
)))
7551 /* We need to accumulate all clobbers/uses of all possible
7553 fi
= get_varinfo (find (fi
->id
));
7554 /* If we cannot constrain the set of functions we'll end up
7555 calling we end up using/clobbering everything. */
7556 if (bitmap_bit_p (fi
->solution
, anything_id
)
7557 || bitmap_bit_p (fi
->solution
, nonlocal_id
)
7558 || bitmap_bit_p (fi
->solution
, escaped_id
))
7560 pt_solution_reset (gimple_call_clobber_set (stmt
));
7561 pt_solution_reset (gimple_call_use_set (stmt
));
7567 struct pt_solution
*uses
, *clobbers
;
7569 uses
= gimple_call_use_set (stmt
);
7570 clobbers
= gimple_call_clobber_set (stmt
);
7571 memset (uses
, 0, sizeof (struct pt_solution
));
7572 memset (clobbers
, 0, sizeof (struct pt_solution
));
7573 EXECUTE_IF_SET_IN_BITMAP (fi
->solution
, 0, i
, bi
)
7575 struct pt_solution sol
;
7577 vi
= get_varinfo (i
);
7578 if (!vi
->is_fn_info
)
7580 /* ??? We could be more precise here? */
7582 uses
->ipa_escaped
= 1;
7583 clobbers
->nonlocal
= 1;
7584 clobbers
->ipa_escaped
= 1;
7588 if (!uses
->anything
)
7590 sol
= find_what_var_points_to
7591 (first_vi_for_offset (vi
, fi_uses
));
7592 pt_solution_ior_into (uses
, &sol
);
7594 if (!clobbers
->anything
)
7596 sol
= find_what_var_points_to
7597 (first_vi_for_offset (vi
, fi_clobbers
));
7598 pt_solution_ior_into (clobbers
, &sol
);
7606 fn
->gimple_df
->ipa_pta
= true;
7609 delete_points_to_sets ();
7618 const pass_data pass_data_ipa_pta
=
7620 SIMPLE_IPA_PASS
, /* type */
7622 OPTGROUP_NONE
, /* optinfo_flags */
7623 TV_IPA_PTA
, /* tv_id */
7624 0, /* properties_required */
7625 0, /* properties_provided */
7626 0, /* properties_destroyed */
7627 0, /* todo_flags_start */
7628 0, /* todo_flags_finish */
7631 class pass_ipa_pta
: public simple_ipa_opt_pass
7634 pass_ipa_pta (gcc::context
*ctxt
)
7635 : simple_ipa_opt_pass (pass_data_ipa_pta
, ctxt
)
7638 /* opt_pass methods: */
7639 virtual bool gate (function
*)
7643 /* Don't bother doing anything if the program has errors. */
7647 virtual unsigned int execute (function
*) { return ipa_pta_execute (); }
7649 }; // class pass_ipa_pta
7653 simple_ipa_opt_pass
*
7654 make_pass_ipa_pta (gcc::context
*ctxt
)
7656 return new pass_ipa_pta (ctxt
);