1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dberlin@dberlin.org>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or
11 (at your option) any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
30 #include "basic-block.h"
33 #include "tree-flow.h"
34 #include "tree-inline.h"
35 #include "diagnostic-core.h"
40 #include "tree-pass.h"
42 #include "alloc-pool.h"
43 #include "splay-tree.h"
47 #include "pointer-set.h"
49 /* The idea behind this analyzer is to generate set constraints from the
50 program, then solve the resulting constraints in order to generate the
53 Set constraints are a way of modeling program analysis problems that
54 involve sets. They consist of an inclusion constraint language,
55 describing the variables (each variable is a set) and operations that
56 are involved on the variables, and a set of rules that derive facts
57 from these operations. To solve a system of set constraints, you derive
58 all possible facts under the rules, which gives you the correct sets
61 See "Efficient Field-sensitive pointer analysis for C" by "David
62 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
63 http://citeseer.ist.psu.edu/pearce04efficient.html
65 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
66 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
67 http://citeseer.ist.psu.edu/heintze01ultrafast.html
69 There are three types of real constraint expressions, DEREF,
70 ADDRESSOF, and SCALAR. Each constraint expression consists
71 of a constraint type, a variable, and an offset.
73 SCALAR is a constraint expression type used to represent x, whether
74 it appears on the LHS or the RHS of a statement.
75 DEREF is a constraint expression type used to represent *x, whether
76 it appears on the LHS or the RHS of a statement.
77 ADDRESSOF is a constraint expression used to represent &x, whether
78 it appears on the LHS or the RHS of a statement.
80 Each pointer variable in the program is assigned an integer id, and
81 each field of a structure variable is assigned an integer id as well.
83 Structure variables are linked to their list of fields through a "next
84 field" in each variable that points to the next field in offset
86 Each variable for a structure field has
88 1. "size", that tells the size in bits of that field.
89 2. "fullsize, that tells the size in bits of the entire structure.
90 3. "offset", that tells the offset in bits from the beginning of the
91 structure to this field.
103 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
104 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
105 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
108 In order to solve the system of set constraints, the following is
111 1. Each constraint variable x has a solution set associated with it,
114 2. Constraints are separated into direct, copy, and complex.
115 Direct constraints are ADDRESSOF constraints that require no extra
116 processing, such as P = &Q
117 Copy constraints are those of the form P = Q.
118 Complex constraints are all the constraints involving dereferences
119 and offsets (including offsetted copies).
121 3. All direct constraints of the form P = &Q are processed, such
122 that Q is added to Sol(P)
124 4. All complex constraints for a given constraint variable are stored in a
125 linked list attached to that variable's node.
127 5. A directed graph is built out of the copy constraints. Each
128 constraint variable is a node in the graph, and an edge from
129 Q to P is added for each copy constraint of the form P = Q
131 6. The graph is then walked, and solution sets are
132 propagated along the copy edges, such that an edge from Q to P
133 causes Sol(P) <- Sol(P) union Sol(Q).
135 7. As we visit each node, all complex constraints associated with
136 that node are processed by adding appropriate copy edges to the graph, or the
137 appropriate variables to the solution set.
139 8. The process of walking the graph is iterated until no solution
142 Prior to walking the graph in steps 6 and 7, We perform static
143 cycle elimination on the constraint graph, as well
144 as off-line variable substitution.
146 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
147 on and turned into anything), but isn't. You can just see what offset
148 inside the pointed-to struct it's going to access.
150 TODO: Constant bounded arrays can be handled as if they were structs of the
151 same number of elements.
153 TODO: Modeling heap and incoming pointers becomes much better if we
154 add fields to them as we discover them, which we could do.
156 TODO: We could handle unions, but to be honest, it's probably not
157 worth the pain or slowdown. */
159 /* IPA-PTA optimizations possible.
161 When the indirect function called is ANYTHING we can add disambiguation
162 based on the function signatures (or simply the parameter count which
163 is the varinfo size). We also do not need to consider functions that
164 do not have their address taken.
166 The is_global_var bit which marks escape points is overly conservative
167 in IPA mode. Split it to is_escape_point and is_global_var - only
168 externally visible globals are escape points in IPA mode. This is
169 also needed to fix the pt_solution_includes_global predicate
170 (and thus ptr_deref_may_alias_global_p).
172 The way we introduce DECL_PT_UID to avoid fixing up all points-to
173 sets in the translation unit when we copy a DECL during inlining
174 pessimizes precision. The advantage is that the DECL_PT_UID keeps
175 compile-time and memory usage overhead low - the points-to sets
176 do not grow or get unshared as they would during a fixup phase.
177 An alternative solution is to delay IPA PTA until after all
178 inlining transformations have been applied.
180 The way we propagate clobber/use information isn't optimized.
181 It should use a new complex constraint that properly filters
182 out local variables of the callee (though that would make
183 the sets invalid after inlining). OTOH we might as well
184 admit defeat to WHOPR and simply do all the clobber/use analysis
185 and propagation after PTA finished but before we threw away
186 points-to information for memory variables. WHOPR and PTA
187 do not play along well anyway - the whole constraint solving
188 would need to be done in WPA phase and it will be very interesting
189 to apply the results to local SSA names during LTRANS phase.
191 We probably should compute a per-function unit-ESCAPE solution
192 propagating it simply like the clobber / uses solutions. The
193 solution can go alongside the non-IPA espaced solution and be
194 used to query which vars escape the unit through a function.
196 We never put function decls in points-to sets so we do not
197 keep the set of called functions for indirect calls.
199 And probably more. */
201 static bool use_field_sensitive
= true;
202 static int in_ipa_mode
= 0;
204 /* Used for predecessor bitmaps. */
205 static bitmap_obstack predbitmap_obstack
;
207 /* Used for points-to sets. */
208 static bitmap_obstack pta_obstack
;
210 /* Used for oldsolution members of variables. */
211 static bitmap_obstack oldpta_obstack
;
213 /* Used for per-solver-iteration bitmaps. */
214 static bitmap_obstack iteration_obstack
;
216 static unsigned int create_variable_info_for (tree
, const char *);
217 typedef struct constraint_graph
*constraint_graph_t
;
218 static void unify_nodes (constraint_graph_t
, unsigned int, unsigned int, bool);
221 typedef struct constraint
*constraint_t
;
223 DEF_VEC_P(constraint_t
);
224 DEF_VEC_ALLOC_P(constraint_t
,heap
);
226 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
228 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
230 static struct constraint_stats
232 unsigned int total_vars
;
233 unsigned int nonpointer_vars
;
234 unsigned int unified_vars_static
;
235 unsigned int unified_vars_dynamic
;
236 unsigned int iterations
;
237 unsigned int num_edges
;
238 unsigned int num_implicit_edges
;
239 unsigned int points_to_sets_created
;
244 /* ID of this variable */
247 /* True if this is a variable created by the constraint analysis, such as
248 heap variables and constraints we had to break up. */
249 unsigned int is_artificial_var
: 1;
251 /* True if this is a special variable whose solution set should not be
253 unsigned int is_special_var
: 1;
255 /* True for variables whose size is not known or variable. */
256 unsigned int is_unknown_size_var
: 1;
258 /* True for (sub-)fields that represent a whole variable. */
259 unsigned int is_full_var
: 1;
261 /* True if this is a heap variable. */
262 unsigned int is_heap_var
: 1;
264 /* True if this is a variable tracking a restrict pointer source. */
265 unsigned int is_restrict_var
: 1;
267 /* True if this field may contain pointers. */
268 unsigned int may_have_pointers
: 1;
270 /* True if this field has only restrict qualified pointers. */
271 unsigned int only_restrict_pointers
: 1;
273 /* True if this represents a global variable. */
274 unsigned int is_global_var
: 1;
276 /* True if this represents a IPA function info. */
277 unsigned int is_fn_info
: 1;
279 /* A link to the variable for the next field in this structure. */
280 struct variable_info
*next
;
282 /* Offset of this variable, in bits, from the base variable */
283 unsigned HOST_WIDE_INT offset
;
285 /* Size of the variable, in bits. */
286 unsigned HOST_WIDE_INT size
;
288 /* Full size of the base variable, in bits. */
289 unsigned HOST_WIDE_INT fullsize
;
291 /* Name of this variable */
294 /* Tree that this variable is associated with. */
297 /* Points-to set for this variable. */
300 /* Old points-to set for this variable. */
303 typedef struct variable_info
*varinfo_t
;
305 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
306 static varinfo_t
first_or_preceding_vi_for_offset (varinfo_t
,
307 unsigned HOST_WIDE_INT
);
308 static varinfo_t
lookup_vi_for_tree (tree
);
310 /* Pool of variable info structures. */
311 static alloc_pool variable_info_pool
;
313 DEF_VEC_P(varinfo_t
);
315 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
317 /* Table of variable info structures for constraint variables.
318 Indexed directly by variable info id. */
319 static VEC(varinfo_t
,heap
) *varmap
;
321 /* Return the varmap element N */
323 static inline varinfo_t
324 get_varinfo (unsigned int n
)
326 return VEC_index (varinfo_t
, varmap
, n
);
329 /* Static IDs for the special variables. */
330 enum { nothing_id
= 0, anything_id
= 1, readonly_id
= 2,
331 escaped_id
= 3, nonlocal_id
= 4,
332 storedanything_id
= 5, integer_id
= 6 };
334 /* Return a new variable info structure consisting for a variable
335 named NAME, and using constraint graph node NODE. Append it
336 to the vector of variable info structures. */
339 new_var_info (tree t
, const char *name
)
341 unsigned index
= VEC_length (varinfo_t
, varmap
);
342 varinfo_t ret
= (varinfo_t
) pool_alloc (variable_info_pool
);
347 /* Vars without decl are artificial and do not have sub-variables. */
348 ret
->is_artificial_var
= (t
== NULL_TREE
);
349 ret
->is_special_var
= false;
350 ret
->is_unknown_size_var
= false;
351 ret
->is_full_var
= (t
== NULL_TREE
);
352 ret
->is_heap_var
= false;
353 ret
->is_restrict_var
= false;
354 ret
->may_have_pointers
= true;
355 ret
->only_restrict_pointers
= false;
356 ret
->is_global_var
= (t
== NULL_TREE
);
357 ret
->is_fn_info
= false;
359 ret
->is_global_var
= (is_global_var (t
)
360 /* We have to treat even local register variables
362 || (TREE_CODE (t
) == VAR_DECL
363 && DECL_HARD_REGISTER (t
)));
364 ret
->solution
= BITMAP_ALLOC (&pta_obstack
);
365 ret
->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
370 VEC_safe_push (varinfo_t
, heap
, varmap
, ret
);
376 /* A map mapping call statements to per-stmt variables for uses
377 and clobbers specific to the call. */
378 struct pointer_map_t
*call_stmt_vars
;
380 /* Lookup or create the variable for the call statement CALL. */
383 get_call_vi (gimple call
)
388 slot_p
= pointer_map_insert (call_stmt_vars
, call
);
390 return (varinfo_t
) *slot_p
;
392 vi
= new_var_info (NULL_TREE
, "CALLUSED");
396 vi
->is_full_var
= true;
398 vi
->next
= vi2
= new_var_info (NULL_TREE
, "CALLCLOBBERED");
402 vi2
->is_full_var
= true;
404 *slot_p
= (void *) vi
;
408 /* Lookup the variable for the call statement CALL representing
409 the uses. Returns NULL if there is nothing special about this call. */
412 lookup_call_use_vi (gimple call
)
416 slot_p
= pointer_map_contains (call_stmt_vars
, call
);
418 return (varinfo_t
) *slot_p
;
423 /* Lookup the variable for the call statement CALL representing
424 the clobbers. Returns NULL if there is nothing special about this call. */
427 lookup_call_clobber_vi (gimple call
)
429 varinfo_t uses
= lookup_call_use_vi (call
);
436 /* Lookup or create the variable for the call statement CALL representing
440 get_call_use_vi (gimple call
)
442 return get_call_vi (call
);
445 /* Lookup or create the variable for the call statement CALL representing
448 static varinfo_t ATTRIBUTE_UNUSED
449 get_call_clobber_vi (gimple call
)
451 return get_call_vi (call
)->next
;
455 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
457 /* An expression that appears in a constraint. */
459 struct constraint_expr
461 /* Constraint type. */
462 constraint_expr_type type
;
464 /* Variable we are referring to in the constraint. */
467 /* Offset, in bits, of this constraint from the beginning of
468 variables it ends up referring to.
470 IOW, in a deref constraint, we would deref, get the result set,
471 then add OFFSET to each member. */
472 HOST_WIDE_INT offset
;
475 /* Use 0x8000... as special unknown offset. */
476 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
478 typedef struct constraint_expr ce_s
;
480 DEF_VEC_ALLOC_O(ce_s
, heap
);
481 static void get_constraint_for_1 (tree
, VEC(ce_s
, heap
) **, bool, bool);
482 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
483 static void get_constraint_for_rhs (tree
, VEC(ce_s
, heap
) **);
484 static void do_deref (VEC (ce_s
, heap
) **);
486 /* Our set constraints are made up of two constraint expressions, one
489 As described in the introduction, our set constraints each represent an
490 operation between set valued variables.
494 struct constraint_expr lhs
;
495 struct constraint_expr rhs
;
498 /* List of constraints that we use to build the constraint graph from. */
500 static VEC(constraint_t
,heap
) *constraints
;
501 static alloc_pool constraint_pool
;
503 /* The constraint graph is represented as an array of bitmaps
504 containing successor nodes. */
506 struct constraint_graph
508 /* Size of this graph, which may be different than the number of
509 nodes in the variable map. */
512 /* Explicit successors of each node. */
515 /* Implicit predecessors of each node (Used for variable
517 bitmap
*implicit_preds
;
519 /* Explicit predecessors of each node (Used for variable substitution). */
522 /* Indirect cycle representatives, or -1 if the node has no indirect
524 int *indirect_cycles
;
526 /* Representative node for a node. rep[a] == a unless the node has
530 /* Equivalence class representative for a label. This is used for
531 variable substitution. */
534 /* Pointer equivalence label for a node. All nodes with the same
535 pointer equivalence label can be unified together at some point
536 (either during constraint optimization or after the constraint
540 /* Pointer equivalence representative for a label. This is used to
541 handle nodes that are pointer equivalent but not location
542 equivalent. We can unite these once the addressof constraints
543 are transformed into initial points-to sets. */
546 /* Pointer equivalence label for each node, used during variable
548 unsigned int *pointer_label
;
550 /* Location equivalence label for each node, used during location
551 equivalence finding. */
552 unsigned int *loc_label
;
554 /* Pointed-by set for each node, used during location equivalence
555 finding. This is pointed-by rather than pointed-to, because it
556 is constructed using the predecessor graph. */
559 /* Points to sets for pointer equivalence. This is *not* the actual
560 points-to sets for nodes. */
563 /* Bitmap of nodes where the bit is set if the node is a direct
564 node. Used for variable substitution. */
565 sbitmap direct_nodes
;
567 /* Bitmap of nodes where the bit is set if the node is address
568 taken. Used for variable substitution. */
569 bitmap address_taken
;
571 /* Vector of complex constraints for each graph node. Complex
572 constraints are those involving dereferences or offsets that are
574 VEC(constraint_t
,heap
) **complex;
577 static constraint_graph_t graph
;
579 /* During variable substitution and the offline version of indirect
580 cycle finding, we create nodes to represent dereferences and
581 address taken constraints. These represent where these start and
583 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
584 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
586 /* Return the representative node for NODE, if NODE has been unioned
588 This function performs path compression along the way to finding
589 the representative. */
592 find (unsigned int node
)
594 gcc_assert (node
< graph
->size
);
595 if (graph
->rep
[node
] != node
)
596 return graph
->rep
[node
] = find (graph
->rep
[node
]);
600 /* Union the TO and FROM nodes to the TO nodes.
601 Note that at some point in the future, we may want to do
602 union-by-rank, in which case we are going to have to return the
603 node we unified to. */
606 unite (unsigned int to
, unsigned int from
)
608 gcc_assert (to
< graph
->size
&& from
< graph
->size
);
609 if (to
!= from
&& graph
->rep
[from
] != to
)
611 graph
->rep
[from
] = to
;
617 /* Create a new constraint consisting of LHS and RHS expressions. */
620 new_constraint (const struct constraint_expr lhs
,
621 const struct constraint_expr rhs
)
623 constraint_t ret
= (constraint_t
) pool_alloc (constraint_pool
);
629 /* Print out constraint C to FILE. */
632 dump_constraint (FILE *file
, constraint_t c
)
634 if (c
->lhs
.type
== ADDRESSOF
)
636 else if (c
->lhs
.type
== DEREF
)
638 fprintf (file
, "%s", get_varinfo (c
->lhs
.var
)->name
);
639 if (c
->lhs
.offset
== UNKNOWN_OFFSET
)
640 fprintf (file
, " + UNKNOWN");
641 else if (c
->lhs
.offset
!= 0)
642 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
643 fprintf (file
, " = ");
644 if (c
->rhs
.type
== ADDRESSOF
)
646 else if (c
->rhs
.type
== DEREF
)
648 fprintf (file
, "%s", get_varinfo (c
->rhs
.var
)->name
);
649 if (c
->rhs
.offset
== UNKNOWN_OFFSET
)
650 fprintf (file
, " + UNKNOWN");
651 else if (c
->rhs
.offset
!= 0)
652 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
656 void debug_constraint (constraint_t
);
657 void debug_constraints (void);
658 void debug_constraint_graph (void);
659 void debug_solution_for_var (unsigned int);
660 void debug_sa_points_to_info (void);
662 /* Print out constraint C to stderr. */
665 debug_constraint (constraint_t c
)
667 dump_constraint (stderr
, c
);
668 fprintf (stderr
, "\n");
671 /* Print out all constraints to FILE */
674 dump_constraints (FILE *file
, int from
)
678 for (i
= from
; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
681 dump_constraint (file
, c
);
682 fprintf (file
, "\n");
686 /* Print out all constraints to stderr. */
689 debug_constraints (void)
691 dump_constraints (stderr
, 0);
694 /* Print the constraint graph in dot format. */
697 dump_constraint_graph (FILE *file
)
701 /* Only print the graph if it has already been initialized: */
705 /* Prints the header of the dot file: */
706 fprintf (file
, "strict digraph {\n");
707 fprintf (file
, " node [\n shape = box\n ]\n");
708 fprintf (file
, " edge [\n fontsize = \"12\"\n ]\n");
709 fprintf (file
, "\n // List of nodes and complex constraints in "
710 "the constraint graph:\n");
712 /* The next lines print the nodes in the graph together with the
713 complex constraints attached to them. */
714 for (i
= 0; i
< graph
->size
; i
++)
718 if (i
< FIRST_REF_NODE
)
719 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
721 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
722 if (graph
->complex[i
])
726 fprintf (file
, " [label=\"\\N\\n");
727 for (j
= 0; VEC_iterate (constraint_t
, graph
->complex[i
], j
, c
); ++j
)
729 dump_constraint (file
, c
);
730 fprintf (file
, "\\l");
732 fprintf (file
, "\"]");
734 fprintf (file
, ";\n");
737 /* Go over the edges. */
738 fprintf (file
, "\n // Edges in the constraint graph:\n");
739 for (i
= 0; i
< graph
->size
; i
++)
745 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
], 0, j
, bi
)
747 unsigned to
= find (j
);
750 if (i
< FIRST_REF_NODE
)
751 fprintf (file
, "\"%s\"", get_varinfo (i
)->name
);
753 fprintf (file
, "\"*%s\"", get_varinfo (i
- FIRST_REF_NODE
)->name
);
754 fprintf (file
, " -> ");
755 if (to
< FIRST_REF_NODE
)
756 fprintf (file
, "\"%s\"", get_varinfo (to
)->name
);
758 fprintf (file
, "\"*%s\"", get_varinfo (to
- FIRST_REF_NODE
)->name
);
759 fprintf (file
, ";\n");
763 /* Prints the tail of the dot file. */
764 fprintf (file
, "}\n");
767 /* Print out the constraint graph to stderr. */
770 debug_constraint_graph (void)
772 dump_constraint_graph (stderr
);
777 The solver is a simple worklist solver, that works on the following
780 sbitmap changed_nodes = all zeroes;
782 For each node that is not already collapsed:
784 set bit in changed nodes
786 while (changed_count > 0)
788 compute topological ordering for constraint graph
790 find and collapse cycles in the constraint graph (updating
791 changed if necessary)
793 for each node (n) in the graph in topological order:
796 Process each complex constraint associated with the node,
797 updating changed if necessary.
799 For each outgoing edge from n, propagate the solution from n to
800 the destination of the edge, updating changed as necessary.
804 /* Return true if two constraint expressions A and B are equal. */
807 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
809 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
812 /* Return true if constraint expression A is less than constraint expression
813 B. This is just arbitrary, but consistent, in order to give them an
817 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
819 if (a
.type
== b
.type
)
822 return a
.offset
< b
.offset
;
824 return a
.var
< b
.var
;
827 return a
.type
< b
.type
;
830 /* Return true if constraint A is less than constraint B. This is just
831 arbitrary, but consistent, in order to give them an ordering. */
834 constraint_less (const constraint_t a
, const constraint_t b
)
836 if (constraint_expr_less (a
->lhs
, b
->lhs
))
838 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
841 return constraint_expr_less (a
->rhs
, b
->rhs
);
844 /* Return true if two constraints A and B are equal. */
847 constraint_equal (struct constraint a
, struct constraint b
)
849 return constraint_expr_equal (a
.lhs
, b
.lhs
)
850 && constraint_expr_equal (a
.rhs
, b
.rhs
);
854 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
857 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
858 struct constraint lookfor
)
866 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
867 if (place
>= VEC_length (constraint_t
, vec
))
869 found
= VEC_index (constraint_t
, vec
, place
);
870 if (!constraint_equal (*found
, lookfor
))
875 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
878 constraint_set_union (VEC(constraint_t
,heap
) **to
,
879 VEC(constraint_t
,heap
) **from
)
884 FOR_EACH_VEC_ELT (constraint_t
, *from
, i
, c
)
886 if (constraint_vec_find (*to
, *c
) == NULL
)
888 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
890 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
895 /* Expands the solution in SET to all sub-fields of variables included.
896 Union the expanded result into RESULT. */
899 solution_set_expand (bitmap result
, bitmap set
)
905 /* In a first pass record all variables we need to add all
906 sub-fields off. This avoids quadratic behavior. */
907 EXECUTE_IF_SET_IN_BITMAP (set
, 0, j
, bi
)
909 varinfo_t v
= get_varinfo (j
);
910 if (v
->is_artificial_var
913 v
= lookup_vi_for_tree (v
->decl
);
915 vars
= BITMAP_ALLOC (NULL
);
916 bitmap_set_bit (vars
, v
->id
);
919 /* In the second pass now do the addition to the solution and
920 to speed up solving add it to the delta as well. */
923 EXECUTE_IF_SET_IN_BITMAP (vars
, 0, j
, bi
)
925 varinfo_t v
= get_varinfo (j
);
926 for (; v
!= NULL
; v
= v
->next
)
927 bitmap_set_bit (result
, v
->id
);
933 /* Take a solution set SET, add OFFSET to each member of the set, and
934 overwrite SET with the result when done. */
937 solution_set_add (bitmap set
, HOST_WIDE_INT offset
)
939 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
943 /* If the offset is unknown we have to expand the solution to
945 if (offset
== UNKNOWN_OFFSET
)
947 solution_set_expand (set
, set
);
951 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
953 varinfo_t vi
= get_varinfo (i
);
955 /* If this is a variable with just one field just set its bit
957 if (vi
->is_artificial_var
958 || vi
->is_unknown_size_var
960 bitmap_set_bit (result
, i
);
963 unsigned HOST_WIDE_INT fieldoffset
= vi
->offset
+ offset
;
965 /* If the offset makes the pointer point to before the
966 variable use offset zero for the field lookup. */
968 && fieldoffset
> vi
->offset
)
972 vi
= first_or_preceding_vi_for_offset (vi
, fieldoffset
);
974 bitmap_set_bit (result
, vi
->id
);
975 /* If the result is not exactly at fieldoffset include the next
976 field as well. See get_constraint_for_ptr_offset for more
978 if (vi
->offset
!= fieldoffset
980 bitmap_set_bit (result
, vi
->next
->id
);
984 bitmap_copy (set
, result
);
985 BITMAP_FREE (result
);
988 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
992 set_union_with_increment (bitmap to
, bitmap from
, HOST_WIDE_INT inc
)
995 return bitmap_ior_into (to
, from
);
1001 tmp
= BITMAP_ALLOC (&iteration_obstack
);
1002 bitmap_copy (tmp
, from
);
1003 solution_set_add (tmp
, inc
);
1004 res
= bitmap_ior_into (to
, tmp
);
1010 /* Insert constraint C into the list of complex constraints for graph
1014 insert_into_complex (constraint_graph_t graph
,
1015 unsigned int var
, constraint_t c
)
1017 VEC (constraint_t
, heap
) *complex = graph
->complex[var
];
1018 unsigned int place
= VEC_lower_bound (constraint_t
, complex, c
,
1021 /* Only insert constraints that do not already exist. */
1022 if (place
>= VEC_length (constraint_t
, complex)
1023 || !constraint_equal (*c
, *VEC_index (constraint_t
, complex, place
)))
1024 VEC_safe_insert (constraint_t
, heap
, graph
->complex[var
], place
, c
);
1028 /* Condense two variable nodes into a single variable node, by moving
1029 all associated info from SRC to TO. */
1032 merge_node_constraints (constraint_graph_t graph
, unsigned int to
,
1038 gcc_assert (find (from
) == to
);
1040 /* Move all complex constraints from src node into to node */
1041 FOR_EACH_VEC_ELT (constraint_t
, graph
->complex[from
], i
, c
)
1043 /* In complex constraints for node src, we may have either
1044 a = *src, and *src = a, or an offseted constraint which are
1045 always added to the rhs node's constraints. */
1047 if (c
->rhs
.type
== DEREF
)
1049 else if (c
->lhs
.type
== DEREF
)
1054 constraint_set_union (&graph
->complex[to
], &graph
->complex[from
]);
1055 VEC_free (constraint_t
, heap
, graph
->complex[from
]);
1056 graph
->complex[from
] = NULL
;
1060 /* Remove edges involving NODE from GRAPH. */
1063 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
1065 if (graph
->succs
[node
])
1066 BITMAP_FREE (graph
->succs
[node
]);
1069 /* Merge GRAPH nodes FROM and TO into node TO. */
1072 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1075 if (graph
->indirect_cycles
[from
] != -1)
1077 /* If we have indirect cycles with the from node, and we have
1078 none on the to node, the to node has indirect cycles from the
1079 from node now that they are unified.
1080 If indirect cycles exist on both, unify the nodes that they
1081 are in a cycle with, since we know they are in a cycle with
1083 if (graph
->indirect_cycles
[to
] == -1)
1084 graph
->indirect_cycles
[to
] = graph
->indirect_cycles
[from
];
1087 /* Merge all the successor edges. */
1088 if (graph
->succs
[from
])
1090 if (!graph
->succs
[to
])
1091 graph
->succs
[to
] = BITMAP_ALLOC (&pta_obstack
);
1092 bitmap_ior_into (graph
->succs
[to
],
1093 graph
->succs
[from
]);
1096 clear_edges_for_node (graph
, from
);
1100 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1101 it doesn't exist in the graph already. */
1104 add_implicit_graph_edge (constraint_graph_t graph
, unsigned int to
,
1110 if (!graph
->implicit_preds
[to
])
1111 graph
->implicit_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1113 if (bitmap_set_bit (graph
->implicit_preds
[to
], from
))
1114 stats
.num_implicit_edges
++;
1117 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1118 it doesn't exist in the graph already.
1119 Return false if the edge already existed, true otherwise. */
1122 add_pred_graph_edge (constraint_graph_t graph
, unsigned int to
,
1125 if (!graph
->preds
[to
])
1126 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1127 bitmap_set_bit (graph
->preds
[to
], from
);
1130 /* Add a graph edge to GRAPH, going from FROM to TO if
1131 it doesn't exist in the graph already.
1132 Return false if the edge already existed, true otherwise. */
1135 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1146 if (!graph
->succs
[from
])
1147 graph
->succs
[from
] = BITMAP_ALLOC (&pta_obstack
);
1148 if (bitmap_set_bit (graph
->succs
[from
], to
))
1151 if (to
< FIRST_REF_NODE
&& from
< FIRST_REF_NODE
)
1159 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1162 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
1165 return (graph
->succs
[dest
]
1166 && bitmap_bit_p (graph
->succs
[dest
], src
));
1169 /* Initialize the constraint graph structure to contain SIZE nodes. */
1172 init_graph (unsigned int size
)
1176 graph
= XCNEW (struct constraint_graph
);
1178 graph
->succs
= XCNEWVEC (bitmap
, graph
->size
);
1179 graph
->indirect_cycles
= XNEWVEC (int, graph
->size
);
1180 graph
->rep
= XNEWVEC (unsigned int, graph
->size
);
1181 graph
->complex = XCNEWVEC (VEC(constraint_t
, heap
) *, size
);
1182 graph
->pe
= XCNEWVEC (unsigned int, graph
->size
);
1183 graph
->pe_rep
= XNEWVEC (int, graph
->size
);
1185 for (j
= 0; j
< graph
->size
; j
++)
1188 graph
->pe_rep
[j
] = -1;
1189 graph
->indirect_cycles
[j
] = -1;
1193 /* Build the constraint graph, adding only predecessor edges right now. */
1196 build_pred_graph (void)
1202 graph
->implicit_preds
= XCNEWVEC (bitmap
, graph
->size
);
1203 graph
->preds
= XCNEWVEC (bitmap
, graph
->size
);
1204 graph
->pointer_label
= XCNEWVEC (unsigned int, graph
->size
);
1205 graph
->loc_label
= XCNEWVEC (unsigned int, graph
->size
);
1206 graph
->pointed_by
= XCNEWVEC (bitmap
, graph
->size
);
1207 graph
->points_to
= XCNEWVEC (bitmap
, graph
->size
);
1208 graph
->eq_rep
= XNEWVEC (int, graph
->size
);
1209 graph
->direct_nodes
= sbitmap_alloc (graph
->size
);
1210 graph
->address_taken
= BITMAP_ALLOC (&predbitmap_obstack
);
1211 sbitmap_zero (graph
->direct_nodes
);
1213 for (j
= 0; j
< FIRST_REF_NODE
; j
++)
1215 if (!get_varinfo (j
)->is_special_var
)
1216 SET_BIT (graph
->direct_nodes
, j
);
1219 for (j
= 0; j
< graph
->size
; j
++)
1220 graph
->eq_rep
[j
] = -1;
1222 for (j
= 0; j
< VEC_length (varinfo_t
, varmap
); j
++)
1223 graph
->indirect_cycles
[j
] = -1;
1225 FOR_EACH_VEC_ELT (constraint_t
, constraints
, i
, c
)
1227 struct constraint_expr lhs
= c
->lhs
;
1228 struct constraint_expr rhs
= c
->rhs
;
1229 unsigned int lhsvar
= lhs
.var
;
1230 unsigned int rhsvar
= rhs
.var
;
1232 if (lhs
.type
== DEREF
)
1235 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1236 add_pred_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1238 else if (rhs
.type
== DEREF
)
1241 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1242 add_pred_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1244 RESET_BIT (graph
->direct_nodes
, lhsvar
);
1246 else if (rhs
.type
== ADDRESSOF
)
1251 if (graph
->points_to
[lhsvar
] == NULL
)
1252 graph
->points_to
[lhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1253 bitmap_set_bit (graph
->points_to
[lhsvar
], rhsvar
);
1255 if (graph
->pointed_by
[rhsvar
] == NULL
)
1256 graph
->pointed_by
[rhsvar
] = BITMAP_ALLOC (&predbitmap_obstack
);
1257 bitmap_set_bit (graph
->pointed_by
[rhsvar
], lhsvar
);
1259 /* Implicitly, *x = y */
1260 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1262 /* All related variables are no longer direct nodes. */
1263 RESET_BIT (graph
->direct_nodes
, rhsvar
);
1264 v
= get_varinfo (rhsvar
);
1265 if (!v
->is_full_var
)
1267 v
= lookup_vi_for_tree (v
->decl
);
1270 RESET_BIT (graph
->direct_nodes
, v
->id
);
1275 bitmap_set_bit (graph
->address_taken
, rhsvar
);
1277 else if (lhsvar
> anything_id
1278 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1281 add_pred_graph_edge (graph
, lhsvar
, rhsvar
);
1282 /* Implicitly, *x = *y */
1283 add_implicit_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
,
1284 FIRST_REF_NODE
+ rhsvar
);
1286 else if (lhs
.offset
!= 0 || rhs
.offset
!= 0)
1288 if (rhs
.offset
!= 0)
1289 RESET_BIT (graph
->direct_nodes
, lhs
.var
);
1290 else if (lhs
.offset
!= 0)
1291 RESET_BIT (graph
->direct_nodes
, rhs
.var
);
1296 /* Build the constraint graph, adding successor edges. */
1299 build_succ_graph (void)
1304 FOR_EACH_VEC_ELT (constraint_t
, constraints
, i
, c
)
1306 struct constraint_expr lhs
;
1307 struct constraint_expr rhs
;
1308 unsigned int lhsvar
;
1309 unsigned int rhsvar
;
1316 lhsvar
= find (lhs
.var
);
1317 rhsvar
= find (rhs
.var
);
1319 if (lhs
.type
== DEREF
)
1321 if (rhs
.offset
== 0 && lhs
.offset
== 0 && rhs
.type
== SCALAR
)
1322 add_graph_edge (graph
, FIRST_REF_NODE
+ lhsvar
, rhsvar
);
1324 else if (rhs
.type
== DEREF
)
1326 if (rhs
.offset
== 0 && lhs
.offset
== 0 && lhs
.type
== SCALAR
)
1327 add_graph_edge (graph
, lhsvar
, FIRST_REF_NODE
+ rhsvar
);
1329 else if (rhs
.type
== ADDRESSOF
)
1332 gcc_assert (find (rhs
.var
) == rhs
.var
);
1333 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1335 else if (lhsvar
> anything_id
1336 && lhsvar
!= rhsvar
&& lhs
.offset
== 0 && rhs
.offset
== 0)
1338 add_graph_edge (graph
, lhsvar
, rhsvar
);
1342 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1343 receive pointers. */
1344 t
= find (storedanything_id
);
1345 for (i
= integer_id
+ 1; i
< FIRST_REF_NODE
; ++i
)
1347 if (!TEST_BIT (graph
->direct_nodes
, i
)
1348 && get_varinfo (i
)->may_have_pointers
)
1349 add_graph_edge (graph
, find (i
), t
);
1352 /* Everything stored to ANYTHING also potentially escapes. */
1353 add_graph_edge (graph
, find (escaped_id
), t
);
1357 /* Changed variables on the last iteration. */
1358 static bitmap changed
;
1360 /* Strongly Connected Component visitation info. */
1367 unsigned int *node_mapping
;
1369 VEC(unsigned,heap
) *scc_stack
;
1373 /* Recursive routine to find strongly connected components in GRAPH.
1374 SI is the SCC info to store the information in, and N is the id of current
1375 graph node we are processing.
1377 This is Tarjan's strongly connected component finding algorithm, as
1378 modified by Nuutila to keep only non-root nodes on the stack.
1379 The algorithm can be found in "On finding the strongly connected
1380 connected components in a directed graph" by Esko Nuutila and Eljas
1381 Soisalon-Soininen, in Information Processing Letters volume 49,
1382 number 1, pages 9-14. */
1385 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1389 unsigned int my_dfs
;
1391 SET_BIT (si
->visited
, n
);
1392 si
->dfs
[n
] = si
->current_index
++;
1393 my_dfs
= si
->dfs
[n
];
1395 /* Visit all the successors. */
1396 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
1400 if (i
> LAST_REF_NODE
)
1404 if (TEST_BIT (si
->deleted
, w
))
1407 if (!TEST_BIT (si
->visited
, w
))
1408 scc_visit (graph
, si
, w
);
1410 unsigned int t
= find (w
);
1411 unsigned int nnode
= find (n
);
1412 gcc_assert (nnode
== n
);
1414 if (si
->dfs
[t
] < si
->dfs
[nnode
])
1415 si
->dfs
[n
] = si
->dfs
[t
];
1419 /* See if any components have been identified. */
1420 if (si
->dfs
[n
] == my_dfs
)
1422 if (VEC_length (unsigned, si
->scc_stack
) > 0
1423 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1425 bitmap scc
= BITMAP_ALLOC (NULL
);
1426 unsigned int lowest_node
;
1429 bitmap_set_bit (scc
, n
);
1431 while (VEC_length (unsigned, si
->scc_stack
) != 0
1432 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
1434 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1436 bitmap_set_bit (scc
, w
);
1439 lowest_node
= bitmap_first_set_bit (scc
);
1440 gcc_assert (lowest_node
< FIRST_REF_NODE
);
1442 /* Collapse the SCC nodes into a single node, and mark the
1444 EXECUTE_IF_SET_IN_BITMAP (scc
, 0, i
, bi
)
1446 if (i
< FIRST_REF_NODE
)
1448 if (unite (lowest_node
, i
))
1449 unify_nodes (graph
, lowest_node
, i
, false);
1453 unite (lowest_node
, i
);
1454 graph
->indirect_cycles
[i
- FIRST_REF_NODE
] = lowest_node
;
1458 SET_BIT (si
->deleted
, n
);
1461 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1464 /* Unify node FROM into node TO, updating the changed count if
1465 necessary when UPDATE_CHANGED is true. */
1468 unify_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1469 bool update_changed
)
1472 gcc_assert (to
!= from
&& find (to
) == to
);
1473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1474 fprintf (dump_file
, "Unifying %s to %s\n",
1475 get_varinfo (from
)->name
,
1476 get_varinfo (to
)->name
);
1479 stats
.unified_vars_dynamic
++;
1481 stats
.unified_vars_static
++;
1483 merge_graph_nodes (graph
, to
, from
);
1484 merge_node_constraints (graph
, to
, from
);
1486 /* Mark TO as changed if FROM was changed. If TO was already marked
1487 as changed, decrease the changed count. */
1490 && bitmap_bit_p (changed
, from
))
1492 bitmap_clear_bit (changed
, from
);
1493 bitmap_set_bit (changed
, to
);
1495 if (get_varinfo (from
)->solution
)
1497 /* If the solution changes because of the merging, we need to mark
1498 the variable as changed. */
1499 if (bitmap_ior_into (get_varinfo (to
)->solution
,
1500 get_varinfo (from
)->solution
))
1503 bitmap_set_bit (changed
, to
);
1506 BITMAP_FREE (get_varinfo (from
)->solution
);
1507 BITMAP_FREE (get_varinfo (from
)->oldsolution
);
1509 if (stats
.iterations
> 0)
1511 BITMAP_FREE (get_varinfo (to
)->oldsolution
);
1512 get_varinfo (to
)->oldsolution
= BITMAP_ALLOC (&oldpta_obstack
);
1515 if (valid_graph_edge (graph
, to
, to
))
1517 if (graph
->succs
[to
])
1518 bitmap_clear_bit (graph
->succs
[to
], to
);
1522 /* Information needed to compute the topological ordering of a graph. */
1526 /* sbitmap of visited nodes. */
1528 /* Array that stores the topological order of the graph, *in
1530 VEC(unsigned,heap
) *topo_order
;
1534 /* Initialize and return a topological info structure. */
1536 static struct topo_info
*
1537 init_topo_info (void)
1539 size_t size
= graph
->size
;
1540 struct topo_info
*ti
= XNEW (struct topo_info
);
1541 ti
->visited
= sbitmap_alloc (size
);
1542 sbitmap_zero (ti
->visited
);
1543 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1548 /* Free the topological sort info pointed to by TI. */
1551 free_topo_info (struct topo_info
*ti
)
1553 sbitmap_free (ti
->visited
);
1554 VEC_free (unsigned, heap
, ti
->topo_order
);
1558 /* Visit the graph in topological order, and store the order in the
1559 topo_info structure. */
1562 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1568 SET_BIT (ti
->visited
, n
);
1570 if (graph
->succs
[n
])
1571 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[n
], 0, j
, bi
)
1573 if (!TEST_BIT (ti
->visited
, j
))
1574 topo_visit (graph
, ti
, j
);
1577 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1580 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1581 starting solution for y. */
1584 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1587 unsigned int lhs
= c
->lhs
.var
;
1589 bitmap sol
= get_varinfo (lhs
)->solution
;
1592 HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1594 /* Our IL does not allow this. */
1595 gcc_assert (c
->lhs
.offset
== 0);
1597 /* If the solution of Y contains anything it is good enough to transfer
1599 if (bitmap_bit_p (delta
, anything_id
))
1601 flag
|= bitmap_set_bit (sol
, anything_id
);
1605 /* If we do not know at with offset the rhs is dereferenced compute
1606 the reachability set of DELTA, conservatively assuming it is
1607 dereferenced at all valid offsets. */
1608 if (roffset
== UNKNOWN_OFFSET
)
1610 solution_set_expand (delta
, delta
);
1611 /* No further offset processing is necessary. */
1615 /* For each variable j in delta (Sol(y)), add
1616 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1617 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1619 varinfo_t v
= get_varinfo (j
);
1620 HOST_WIDE_INT fieldoffset
= v
->offset
+ roffset
;
1624 fieldoffset
= v
->offset
;
1625 else if (roffset
!= 0)
1626 v
= first_vi_for_offset (v
, fieldoffset
);
1627 /* If the access is outside of the variable we can ignore it. */
1635 /* Adding edges from the special vars is pointless.
1636 They don't have sets that can change. */
1637 if (get_varinfo (t
)->is_special_var
)
1638 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1639 /* Merging the solution from ESCAPED needlessly increases
1640 the set. Use ESCAPED as representative instead. */
1641 else if (v
->id
== escaped_id
)
1642 flag
|= bitmap_set_bit (sol
, escaped_id
);
1643 else if (v
->may_have_pointers
1644 && add_graph_edge (graph
, lhs
, t
))
1645 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1647 /* If the variable is not exactly at the requested offset
1648 we have to include the next one. */
1649 if (v
->offset
== (unsigned HOST_WIDE_INT
)fieldoffset
1654 fieldoffset
= v
->offset
;
1660 /* If the LHS solution changed, mark the var as changed. */
1663 get_varinfo (lhs
)->solution
= sol
;
1664 bitmap_set_bit (changed
, lhs
);
1668 /* Process a constraint C that represents *(x + off) = y using DELTA
1669 as the starting solution for x. */
1672 do_ds_constraint (constraint_t c
, bitmap delta
)
1674 unsigned int rhs
= c
->rhs
.var
;
1675 bitmap sol
= get_varinfo (rhs
)->solution
;
1678 HOST_WIDE_INT loff
= c
->lhs
.offset
;
1679 bool escaped_p
= false;
1681 /* Our IL does not allow this. */
1682 gcc_assert (c
->rhs
.offset
== 0);
1684 /* If the solution of y contains ANYTHING simply use the ANYTHING
1685 solution. This avoids needlessly increasing the points-to sets. */
1686 if (bitmap_bit_p (sol
, anything_id
))
1687 sol
= get_varinfo (find (anything_id
))->solution
;
1689 /* If the solution for x contains ANYTHING we have to merge the
1690 solution of y into all pointer variables which we do via
1692 if (bitmap_bit_p (delta
, anything_id
))
1694 unsigned t
= find (storedanything_id
);
1695 if (add_graph_edge (graph
, t
, rhs
))
1697 if (bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1698 bitmap_set_bit (changed
, t
);
1703 /* If we do not know at with offset the rhs is dereferenced compute
1704 the reachability set of DELTA, conservatively assuming it is
1705 dereferenced at all valid offsets. */
1706 if (loff
== UNKNOWN_OFFSET
)
1708 solution_set_expand (delta
, delta
);
1712 /* For each member j of delta (Sol(x)), add an edge from y to j and
1713 union Sol(y) into Sol(j) */
1714 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1716 varinfo_t v
= get_varinfo (j
);
1718 HOST_WIDE_INT fieldoffset
= v
->offset
+ loff
;
1721 fieldoffset
= v
->offset
;
1723 v
= first_vi_for_offset (v
, fieldoffset
);
1724 /* If the access is outside of the variable we can ignore it. */
1730 if (v
->may_have_pointers
)
1732 /* If v is a global variable then this is an escape point. */
1733 if (v
->is_global_var
1736 t
= find (escaped_id
);
1737 if (add_graph_edge (graph
, t
, rhs
)
1738 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1739 bitmap_set_bit (changed
, t
);
1740 /* Enough to let rhs escape once. */
1744 if (v
->is_special_var
)
1748 if (add_graph_edge (graph
, t
, rhs
)
1749 && bitmap_ior_into (get_varinfo (t
)->solution
, sol
))
1750 bitmap_set_bit (changed
, t
);
1753 /* If the variable is not exactly at the requested offset
1754 we have to include the next one. */
1755 if (v
->offset
== (unsigned HOST_WIDE_INT
)fieldoffset
1760 fieldoffset
= v
->offset
;
1766 /* Handle a non-simple (simple meaning requires no iteration),
1767 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1770 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1772 if (c
->lhs
.type
== DEREF
)
1774 if (c
->rhs
.type
== ADDRESSOF
)
1781 do_ds_constraint (c
, delta
);
1784 else if (c
->rhs
.type
== DEREF
)
1787 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1788 do_sd_constraint (graph
, c
, delta
);
1796 gcc_assert (c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
);
1797 solution
= get_varinfo (c
->rhs
.var
)->solution
;
1798 tmp
= get_varinfo (c
->lhs
.var
)->solution
;
1800 flag
= set_union_with_increment (tmp
, solution
, c
->rhs
.offset
);
1804 get_varinfo (c
->lhs
.var
)->solution
= tmp
;
1805 bitmap_set_bit (changed
, c
->lhs
.var
);
1810 /* Initialize and return a new SCC info structure. */
1812 static struct scc_info
*
1813 init_scc_info (size_t size
)
1815 struct scc_info
*si
= XNEW (struct scc_info
);
1818 si
->current_index
= 0;
1819 si
->visited
= sbitmap_alloc (size
);
1820 sbitmap_zero (si
->visited
);
1821 si
->deleted
= sbitmap_alloc (size
);
1822 sbitmap_zero (si
->deleted
);
1823 si
->node_mapping
= XNEWVEC (unsigned int, size
);
1824 si
->dfs
= XCNEWVEC (unsigned int, size
);
1826 for (i
= 0; i
< size
; i
++)
1827 si
->node_mapping
[i
] = i
;
1829 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1833 /* Free an SCC info structure pointed to by SI */
1836 free_scc_info (struct scc_info
*si
)
1838 sbitmap_free (si
->visited
);
1839 sbitmap_free (si
->deleted
);
1840 free (si
->node_mapping
);
1842 VEC_free (unsigned, heap
, si
->scc_stack
);
1847 /* Find indirect cycles in GRAPH that occur, using strongly connected
1848 components, and note them in the indirect cycles map.
1850 This technique comes from Ben Hardekopf and Calvin Lin,
1851 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1852 Lines of Code", submitted to PLDI 2007. */
1855 find_indirect_cycles (constraint_graph_t graph
)
1858 unsigned int size
= graph
->size
;
1859 struct scc_info
*si
= init_scc_info (size
);
1861 for (i
= 0; i
< MIN (LAST_REF_NODE
, size
); i
++ )
1862 if (!TEST_BIT (si
->visited
, i
) && find (i
) == i
)
1863 scc_visit (graph
, si
, i
);
1868 /* Compute a topological ordering for GRAPH, and store the result in the
1869 topo_info structure TI. */
1872 compute_topo_order (constraint_graph_t graph
,
1873 struct topo_info
*ti
)
1876 unsigned int size
= graph
->size
;
1878 for (i
= 0; i
!= size
; ++i
)
1879 if (!TEST_BIT (ti
->visited
, i
) && find (i
) == i
)
1880 topo_visit (graph
, ti
, i
);
1883 /* Structure used to for hash value numbering of pointer equivalence
1886 typedef struct equiv_class_label
1889 unsigned int equivalence_class
;
1891 } *equiv_class_label_t
;
1892 typedef const struct equiv_class_label
*const_equiv_class_label_t
;
1894 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1896 static htab_t pointer_equiv_class_table
;
1898 /* A hashtable for mapping a bitmap of labels->location equivalence
1900 static htab_t location_equiv_class_table
;
1902 /* Hash function for a equiv_class_label_t */
1905 equiv_class_label_hash (const void *p
)
1907 const_equiv_class_label_t
const ecl
= (const_equiv_class_label_t
) p
;
1908 return ecl
->hashcode
;
1911 /* Equality function for two equiv_class_label_t's. */
1914 equiv_class_label_eq (const void *p1
, const void *p2
)
1916 const_equiv_class_label_t
const eql1
= (const_equiv_class_label_t
) p1
;
1917 const_equiv_class_label_t
const eql2
= (const_equiv_class_label_t
) p2
;
1918 return (eql1
->hashcode
== eql2
->hashcode
1919 && bitmap_equal_p (eql1
->labels
, eql2
->labels
));
1922 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1926 equiv_class_lookup (htab_t table
, bitmap labels
)
1929 struct equiv_class_label ecl
;
1931 ecl
.labels
= labels
;
1932 ecl
.hashcode
= bitmap_hash (labels
);
1934 slot
= htab_find_slot_with_hash (table
, &ecl
,
1935 ecl
.hashcode
, NO_INSERT
);
1939 return ((equiv_class_label_t
) *slot
)->equivalence_class
;
1943 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1947 equiv_class_add (htab_t table
, unsigned int equivalence_class
,
1951 equiv_class_label_t ecl
= XNEW (struct equiv_class_label
);
1953 ecl
->labels
= labels
;
1954 ecl
->equivalence_class
= equivalence_class
;
1955 ecl
->hashcode
= bitmap_hash (labels
);
1957 slot
= htab_find_slot_with_hash (table
, ecl
,
1958 ecl
->hashcode
, INSERT
);
1959 gcc_assert (!*slot
);
1960 *slot
= (void *) ecl
;
1963 /* Perform offline variable substitution.
1965 This is a worst case quadratic time way of identifying variables
1966 that must have equivalent points-to sets, including those caused by
1967 static cycles, and single entry subgraphs, in the constraint graph.
1969 The technique is described in "Exploiting Pointer and Location
1970 Equivalence to Optimize Pointer Analysis. In the 14th International
1971 Static Analysis Symposium (SAS), August 2007." It is known as the
1972 "HU" algorithm, and is equivalent to value numbering the collapsed
1973 constraint graph including evaluating unions.
1975 The general method of finding equivalence classes is as follows:
1976 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1977 Initialize all non-REF nodes to be direct nodes.
1978 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1980 For each constraint containing the dereference, we also do the same
1983 We then compute SCC's in the graph and unify nodes in the same SCC,
1986 For each non-collapsed node x:
1987 Visit all unvisited explicit incoming edges.
1988 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1990 Lookup the equivalence class for pts(x).
1991 If we found one, equivalence_class(x) = found class.
1992 Otherwise, equivalence_class(x) = new class, and new_class is
1993 added to the lookup table.
1995 All direct nodes with the same equivalence class can be replaced
1996 with a single representative node.
1997 All unlabeled nodes (label == 0) are not pointers and all edges
1998 involving them can be eliminated.
1999 We perform these optimizations during rewrite_constraints
2001 In addition to pointer equivalence class finding, we also perform
2002 location equivalence class finding. This is the set of variables
2003 that always appear together in points-to sets. We use this to
2004 compress the size of the points-to sets. */
2006 /* Current maximum pointer equivalence class id. */
2007 static int pointer_equiv_class
;
2009 /* Current maximum location equivalence class id. */
2010 static int location_equiv_class
;
2012 /* Recursive routine to find strongly connected components in GRAPH,
2013 and label it's nodes with DFS numbers. */
2016 condense_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2020 unsigned int my_dfs
;
2022 gcc_assert (si
->node_mapping
[n
] == n
);
2023 SET_BIT (si
->visited
, n
);
2024 si
->dfs
[n
] = si
->current_index
++;
2025 my_dfs
= si
->dfs
[n
];
2027 /* Visit all the successors. */
2028 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2030 unsigned int w
= si
->node_mapping
[i
];
2032 if (TEST_BIT (si
->deleted
, w
))
2035 if (!TEST_BIT (si
->visited
, w
))
2036 condense_visit (graph
, si
, w
);
2038 unsigned int t
= si
->node_mapping
[w
];
2039 unsigned int nnode
= si
->node_mapping
[n
];
2040 gcc_assert (nnode
== n
);
2042 if (si
->dfs
[t
] < si
->dfs
[nnode
])
2043 si
->dfs
[n
] = si
->dfs
[t
];
2047 /* Visit all the implicit predecessors. */
2048 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->implicit_preds
[n
], 0, i
, bi
)
2050 unsigned int w
= si
->node_mapping
[i
];
2052 if (TEST_BIT (si
->deleted
, w
))
2055 if (!TEST_BIT (si
->visited
, w
))
2056 condense_visit (graph
, si
, w
);
2058 unsigned int t
= si
->node_mapping
[w
];
2059 unsigned int nnode
= si
->node_mapping
[n
];
2060 gcc_assert (nnode
== n
);
2062 if (si
->dfs
[t
] < si
->dfs
[nnode
])
2063 si
->dfs
[n
] = si
->dfs
[t
];
2067 /* See if any components have been identified. */
2068 if (si
->dfs
[n
] == my_dfs
)
2070 while (VEC_length (unsigned, si
->scc_stack
) != 0
2071 && si
->dfs
[VEC_last (unsigned, si
->scc_stack
)] >= my_dfs
)
2073 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
2074 si
->node_mapping
[w
] = n
;
2076 if (!TEST_BIT (graph
->direct_nodes
, w
))
2077 RESET_BIT (graph
->direct_nodes
, n
);
2079 /* Unify our nodes. */
2080 if (graph
->preds
[w
])
2082 if (!graph
->preds
[n
])
2083 graph
->preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2084 bitmap_ior_into (graph
->preds
[n
], graph
->preds
[w
]);
2086 if (graph
->implicit_preds
[w
])
2088 if (!graph
->implicit_preds
[n
])
2089 graph
->implicit_preds
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2090 bitmap_ior_into (graph
->implicit_preds
[n
],
2091 graph
->implicit_preds
[w
]);
2093 if (graph
->points_to
[w
])
2095 if (!graph
->points_to
[n
])
2096 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2097 bitmap_ior_into (graph
->points_to
[n
],
2098 graph
->points_to
[w
]);
2101 SET_BIT (si
->deleted
, n
);
2104 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
2107 /* Label pointer equivalences. */
2110 label_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
2114 SET_BIT (si
->visited
, n
);
2116 if (!graph
->points_to
[n
])
2117 graph
->points_to
[n
] = BITMAP_ALLOC (&predbitmap_obstack
);
2119 /* Label and union our incoming edges's points to sets. */
2120 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[n
], 0, i
, bi
)
2122 unsigned int w
= si
->node_mapping
[i
];
2123 if (!TEST_BIT (si
->visited
, w
))
2124 label_visit (graph
, si
, w
);
2126 /* Skip unused edges */
2127 if (w
== n
|| graph
->pointer_label
[w
] == 0)
2130 if (graph
->points_to
[w
])
2131 bitmap_ior_into(graph
->points_to
[n
], graph
->points_to
[w
]);
2133 /* Indirect nodes get fresh variables. */
2134 if (!TEST_BIT (graph
->direct_nodes
, n
))
2135 bitmap_set_bit (graph
->points_to
[n
], FIRST_REF_NODE
+ n
);
2137 if (!bitmap_empty_p (graph
->points_to
[n
]))
2139 unsigned int label
= equiv_class_lookup (pointer_equiv_class_table
,
2140 graph
->points_to
[n
]);
2143 label
= pointer_equiv_class
++;
2144 equiv_class_add (pointer_equiv_class_table
,
2145 label
, graph
->points_to
[n
]);
2147 graph
->pointer_label
[n
] = label
;
2151 /* Perform offline variable substitution, discovering equivalence
2152 classes, and eliminating non-pointer variables. */
2154 static struct scc_info
*
2155 perform_var_substitution (constraint_graph_t graph
)
2158 unsigned int size
= graph
->size
;
2159 struct scc_info
*si
= init_scc_info (size
);
2161 bitmap_obstack_initialize (&iteration_obstack
);
2162 pointer_equiv_class_table
= htab_create (511, equiv_class_label_hash
,
2163 equiv_class_label_eq
, free
);
2164 location_equiv_class_table
= htab_create (511, equiv_class_label_hash
,
2165 equiv_class_label_eq
, free
);
2166 pointer_equiv_class
= 1;
2167 location_equiv_class
= 1;
2169 /* Condense the nodes, which means to find SCC's, count incoming
2170 predecessors, and unite nodes in SCC's. */
2171 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2172 if (!TEST_BIT (si
->visited
, si
->node_mapping
[i
]))
2173 condense_visit (graph
, si
, si
->node_mapping
[i
]);
2175 sbitmap_zero (si
->visited
);
2176 /* Actually the label the nodes for pointer equivalences */
2177 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2178 if (!TEST_BIT (si
->visited
, si
->node_mapping
[i
]))
2179 label_visit (graph
, si
, si
->node_mapping
[i
]);
2181 /* Calculate location equivalence labels. */
2182 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2189 if (!graph
->pointed_by
[i
])
2191 pointed_by
= BITMAP_ALLOC (&iteration_obstack
);
2193 /* Translate the pointed-by mapping for pointer equivalence
2195 EXECUTE_IF_SET_IN_BITMAP (graph
->pointed_by
[i
], 0, j
, bi
)
2197 bitmap_set_bit (pointed_by
,
2198 graph
->pointer_label
[si
->node_mapping
[j
]]);
2200 /* The original pointed_by is now dead. */
2201 BITMAP_FREE (graph
->pointed_by
[i
]);
2203 /* Look up the location equivalence label if one exists, or make
2205 label
= equiv_class_lookup (location_equiv_class_table
,
2209 label
= location_equiv_class
++;
2210 equiv_class_add (location_equiv_class_table
,
2215 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2216 fprintf (dump_file
, "Found location equivalence for node %s\n",
2217 get_varinfo (i
)->name
);
2218 BITMAP_FREE (pointed_by
);
2220 graph
->loc_label
[i
] = label
;
2224 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2225 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2227 bool direct_node
= TEST_BIT (graph
->direct_nodes
, i
);
2229 "Equivalence classes for %s node id %d:%s are pointer: %d"
2231 direct_node
? "Direct node" : "Indirect node", i
,
2232 get_varinfo (i
)->name
,
2233 graph
->pointer_label
[si
->node_mapping
[i
]],
2234 graph
->loc_label
[si
->node_mapping
[i
]]);
2237 /* Quickly eliminate our non-pointer variables. */
2239 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2241 unsigned int node
= si
->node_mapping
[i
];
2243 if (graph
->pointer_label
[node
] == 0)
2245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2247 "%s is a non-pointer variable, eliminating edges.\n",
2248 get_varinfo (node
)->name
);
2249 stats
.nonpointer_vars
++;
2250 clear_edges_for_node (graph
, node
);
2257 /* Free information that was only necessary for variable
2261 free_var_substitution_info (struct scc_info
*si
)
2264 free (graph
->pointer_label
);
2265 free (graph
->loc_label
);
2266 free (graph
->pointed_by
);
2267 free (graph
->points_to
);
2268 free (graph
->eq_rep
);
2269 sbitmap_free (graph
->direct_nodes
);
2270 htab_delete (pointer_equiv_class_table
);
2271 htab_delete (location_equiv_class_table
);
2272 bitmap_obstack_release (&iteration_obstack
);
2275 /* Return an existing node that is equivalent to NODE, which has
2276 equivalence class LABEL, if one exists. Return NODE otherwise. */
2279 find_equivalent_node (constraint_graph_t graph
,
2280 unsigned int node
, unsigned int label
)
2282 /* If the address version of this variable is unused, we can
2283 substitute it for anything else with the same label.
2284 Otherwise, we know the pointers are equivalent, but not the
2285 locations, and we can unite them later. */
2287 if (!bitmap_bit_p (graph
->address_taken
, node
))
2289 gcc_assert (label
< graph
->size
);
2291 if (graph
->eq_rep
[label
] != -1)
2293 /* Unify the two variables since we know they are equivalent. */
2294 if (unite (graph
->eq_rep
[label
], node
))
2295 unify_nodes (graph
, graph
->eq_rep
[label
], node
, false);
2296 return graph
->eq_rep
[label
];
2300 graph
->eq_rep
[label
] = node
;
2301 graph
->pe_rep
[label
] = node
;
2306 gcc_assert (label
< graph
->size
);
2307 graph
->pe
[node
] = label
;
2308 if (graph
->pe_rep
[label
] == -1)
2309 graph
->pe_rep
[label
] = node
;
2315 /* Unite pointer equivalent but not location equivalent nodes in
2316 GRAPH. This may only be performed once variable substitution is
2320 unite_pointer_equivalences (constraint_graph_t graph
)
2324 /* Go through the pointer equivalences and unite them to their
2325 representative, if they aren't already. */
2326 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
2328 unsigned int label
= graph
->pe
[i
];
2331 int label_rep
= graph
->pe_rep
[label
];
2333 if (label_rep
== -1)
2336 label_rep
= find (label_rep
);
2337 if (label_rep
>= 0 && unite (label_rep
, find (i
)))
2338 unify_nodes (graph
, label_rep
, i
, false);
2343 /* Move complex constraints to the GRAPH nodes they belong to. */
2346 move_complex_constraints (constraint_graph_t graph
)
2351 FOR_EACH_VEC_ELT (constraint_t
, constraints
, i
, c
)
2355 struct constraint_expr lhs
= c
->lhs
;
2356 struct constraint_expr rhs
= c
->rhs
;
2358 if (lhs
.type
== DEREF
)
2360 insert_into_complex (graph
, lhs
.var
, c
);
2362 else if (rhs
.type
== DEREF
)
2364 if (!(get_varinfo (lhs
.var
)->is_special_var
))
2365 insert_into_complex (graph
, rhs
.var
, c
);
2367 else if (rhs
.type
!= ADDRESSOF
&& lhs
.var
> anything_id
2368 && (lhs
.offset
!= 0 || rhs
.offset
!= 0))
2370 insert_into_complex (graph
, rhs
.var
, c
);
2377 /* Optimize and rewrite complex constraints while performing
2378 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2379 result of perform_variable_substitution. */
2382 rewrite_constraints (constraint_graph_t graph
,
2383 struct scc_info
*si
)
2389 for (j
= 0; j
< graph
->size
; j
++)
2390 gcc_assert (find (j
) == j
);
2392 FOR_EACH_VEC_ELT (constraint_t
, constraints
, i
, c
)
2394 struct constraint_expr lhs
= c
->lhs
;
2395 struct constraint_expr rhs
= c
->rhs
;
2396 unsigned int lhsvar
= find (lhs
.var
);
2397 unsigned int rhsvar
= find (rhs
.var
);
2398 unsigned int lhsnode
, rhsnode
;
2399 unsigned int lhslabel
, rhslabel
;
2401 lhsnode
= si
->node_mapping
[lhsvar
];
2402 rhsnode
= si
->node_mapping
[rhsvar
];
2403 lhslabel
= graph
->pointer_label
[lhsnode
];
2404 rhslabel
= graph
->pointer_label
[rhsnode
];
2406 /* See if it is really a non-pointer variable, and if so, ignore
2410 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2413 fprintf (dump_file
, "%s is a non-pointer variable,"
2414 "ignoring constraint:",
2415 get_varinfo (lhs
.var
)->name
);
2416 dump_constraint (dump_file
, c
);
2417 fprintf (dump_file
, "\n");
2419 VEC_replace (constraint_t
, constraints
, i
, NULL
);
2425 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2428 fprintf (dump_file
, "%s is a non-pointer variable,"
2429 "ignoring constraint:",
2430 get_varinfo (rhs
.var
)->name
);
2431 dump_constraint (dump_file
, c
);
2432 fprintf (dump_file
, "\n");
2434 VEC_replace (constraint_t
, constraints
, i
, NULL
);
2438 lhsvar
= find_equivalent_node (graph
, lhsvar
, lhslabel
);
2439 rhsvar
= find_equivalent_node (graph
, rhsvar
, rhslabel
);
2440 c
->lhs
.var
= lhsvar
;
2441 c
->rhs
.var
= rhsvar
;
2446 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2447 part of an SCC, false otherwise. */
2450 eliminate_indirect_cycles (unsigned int node
)
2452 if (graph
->indirect_cycles
[node
] != -1
2453 && !bitmap_empty_p (get_varinfo (node
)->solution
))
2456 VEC(unsigned,heap
) *queue
= NULL
;
2458 unsigned int to
= find (graph
->indirect_cycles
[node
]);
2461 /* We can't touch the solution set and call unify_nodes
2462 at the same time, because unify_nodes is going to do
2463 bitmap unions into it. */
2465 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node
)->solution
, 0, i
, bi
)
2467 if (find (i
) == i
&& i
!= to
)
2470 VEC_safe_push (unsigned, heap
, queue
, i
);
2475 VEC_iterate (unsigned, queue
, queuepos
, i
);
2478 unify_nodes (graph
, to
, i
, true);
2480 VEC_free (unsigned, heap
, queue
);
2486 /* Solve the constraint graph GRAPH using our worklist solver.
2487 This is based on the PW* family of solvers from the "Efficient Field
2488 Sensitive Pointer Analysis for C" paper.
2489 It works by iterating over all the graph nodes, processing the complex
2490 constraints and propagating the copy constraints, until everything stops
2491 changed. This corresponds to steps 6-8 in the solving list given above. */
2494 solve_graph (constraint_graph_t graph
)
2496 unsigned int size
= graph
->size
;
2500 changed
= BITMAP_ALLOC (NULL
);
2502 /* Mark all initial non-collapsed nodes as changed. */
2503 for (i
= 0; i
< size
; i
++)
2505 varinfo_t ivi
= get_varinfo (i
);
2506 if (find (i
) == i
&& !bitmap_empty_p (ivi
->solution
)
2507 && ((graph
->succs
[i
] && !bitmap_empty_p (graph
->succs
[i
]))
2508 || VEC_length (constraint_t
, graph
->complex[i
]) > 0))
2509 bitmap_set_bit (changed
, i
);
2512 /* Allocate a bitmap to be used to store the changed bits. */
2513 pts
= BITMAP_ALLOC (&pta_obstack
);
2515 while (!bitmap_empty_p (changed
))
2518 struct topo_info
*ti
= init_topo_info ();
2521 bitmap_obstack_initialize (&iteration_obstack
);
2523 compute_topo_order (graph
, ti
);
2525 while (VEC_length (unsigned, ti
->topo_order
) != 0)
2528 i
= VEC_pop (unsigned, ti
->topo_order
);
2530 /* If this variable is not a representative, skip it. */
2534 /* In certain indirect cycle cases, we may merge this
2535 variable to another. */
2536 if (eliminate_indirect_cycles (i
) && find (i
) != i
)
2539 /* If the node has changed, we need to process the
2540 complex constraints and outgoing edges again. */
2541 if (bitmap_clear_bit (changed
, i
))
2546 VEC(constraint_t
,heap
) *complex = graph
->complex[i
];
2547 bool solution_empty
;
2549 /* Compute the changed set of solution bits. */
2550 bitmap_and_compl (pts
, get_varinfo (i
)->solution
,
2551 get_varinfo (i
)->oldsolution
);
2553 if (bitmap_empty_p (pts
))
2556 bitmap_ior_into (get_varinfo (i
)->oldsolution
, pts
);
2558 solution
= get_varinfo (i
)->solution
;
2559 solution_empty
= bitmap_empty_p (solution
);
2561 /* Process the complex constraints */
2562 FOR_EACH_VEC_ELT (constraint_t
, complex, j
, c
)
2564 /* XXX: This is going to unsort the constraints in
2565 some cases, which will occasionally add duplicate
2566 constraints during unification. This does not
2567 affect correctness. */
2568 c
->lhs
.var
= find (c
->lhs
.var
);
2569 c
->rhs
.var
= find (c
->rhs
.var
);
2571 /* The only complex constraint that can change our
2572 solution to non-empty, given an empty solution,
2573 is a constraint where the lhs side is receiving
2574 some set from elsewhere. */
2575 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
2576 do_complex_constraint (graph
, c
, pts
);
2579 solution_empty
= bitmap_empty_p (solution
);
2581 if (!solution_empty
)
2584 unsigned eff_escaped_id
= find (escaped_id
);
2586 /* Propagate solution to all successors. */
2587 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
2593 unsigned int to
= find (j
);
2594 tmp
= get_varinfo (to
)->solution
;
2597 /* Don't try to propagate to ourselves. */
2601 /* If we propagate from ESCAPED use ESCAPED as
2603 if (i
== eff_escaped_id
)
2604 flag
= bitmap_set_bit (tmp
, escaped_id
);
2606 flag
= set_union_with_increment (tmp
, pts
, 0);
2610 get_varinfo (to
)->solution
= tmp
;
2611 bitmap_set_bit (changed
, to
);
2617 free_topo_info (ti
);
2618 bitmap_obstack_release (&iteration_obstack
);
2622 BITMAP_FREE (changed
);
2623 bitmap_obstack_release (&oldpta_obstack
);
2626 /* Map from trees to variable infos. */
2627 static struct pointer_map_t
*vi_for_tree
;
2630 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2633 insert_vi_for_tree (tree t
, varinfo_t vi
)
2635 void **slot
= pointer_map_insert (vi_for_tree
, t
);
2637 gcc_assert (*slot
== NULL
);
2641 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2642 exist in the map, return NULL, otherwise, return the varinfo we found. */
2645 lookup_vi_for_tree (tree t
)
2647 void **slot
= pointer_map_contains (vi_for_tree
, t
);
2651 return (varinfo_t
) *slot
;
2654 /* Return a printable name for DECL */
2657 alias_get_name (tree decl
)
2661 int num_printed
= 0;
2663 if (DECL_ASSEMBLER_NAME_SET_P (decl
))
2664 res
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
2666 res
= get_name (decl
);
2674 if (TREE_CODE (decl
) == SSA_NAME
)
2676 num_printed
= asprintf (&temp
, "%s_%u",
2677 alias_get_name (SSA_NAME_VAR (decl
)),
2678 SSA_NAME_VERSION (decl
));
2680 else if (DECL_P (decl
))
2682 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2684 if (num_printed
> 0)
2686 res
= ggc_strdup (temp
);
2692 /* Find the variable id for tree T in the map.
2693 If T doesn't exist in the map, create an entry for it and return it. */
2696 get_vi_for_tree (tree t
)
2698 void **slot
= pointer_map_contains (vi_for_tree
, t
);
2700 return get_varinfo (create_variable_info_for (t
, alias_get_name (t
)));
2702 return (varinfo_t
) *slot
;
2705 /* Get a scalar constraint expression for a new temporary variable. */
2707 static struct constraint_expr
2708 new_scalar_tmp_constraint_exp (const char *name
)
2710 struct constraint_expr tmp
;
2713 vi
= new_var_info (NULL_TREE
, name
);
2717 vi
->is_full_var
= 1;
2726 /* Get a constraint expression vector from an SSA_VAR_P node.
2727 If address_p is true, the result will be taken its address of. */
2730 get_constraint_for_ssa_var (tree t
, VEC(ce_s
, heap
) **results
, bool address_p
)
2732 struct constraint_expr cexpr
;
2735 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2736 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
2738 /* For parameters, get at the points-to set for the actual parm
2740 if (TREE_CODE (t
) == SSA_NAME
2741 && (TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2742 || TREE_CODE (SSA_NAME_VAR (t
)) == RESULT_DECL
)
2743 && SSA_NAME_IS_DEFAULT_DEF (t
))
2745 get_constraint_for_ssa_var (SSA_NAME_VAR (t
), results
, address_p
);
2749 vi
= get_vi_for_tree (t
);
2751 cexpr
.type
= SCALAR
;
2753 /* If we determine the result is "anything", and we know this is readonly,
2754 say it points to readonly memory instead. */
2755 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
2758 cexpr
.type
= ADDRESSOF
;
2759 cexpr
.var
= readonly_id
;
2762 /* If we are not taking the address of the constraint expr, add all
2763 sub-fiels of the variable as well. */
2765 && !vi
->is_full_var
)
2767 for (; vi
; vi
= vi
->next
)
2770 VEC_safe_push (ce_s
, heap
, *results
, &cexpr
);
2775 VEC_safe_push (ce_s
, heap
, *results
, &cexpr
);
2778 /* Process constraint T, performing various simplifications and then
2779 adding it to our list of overall constraints. */
2782 process_constraint (constraint_t t
)
2784 struct constraint_expr rhs
= t
->rhs
;
2785 struct constraint_expr lhs
= t
->lhs
;
2787 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
2788 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
2790 /* If we didn't get any useful constraint from the lhs we get
2791 &ANYTHING as fallback from get_constraint_for. Deal with
2792 it here by turning it into *ANYTHING. */
2793 if (lhs
.type
== ADDRESSOF
2794 && lhs
.var
== anything_id
)
2797 /* ADDRESSOF on the lhs is invalid. */
2798 gcc_assert (lhs
.type
!= ADDRESSOF
);
2800 /* We shouldn't add constraints from things that cannot have pointers.
2801 It's not completely trivial to avoid in the callers, so do it here. */
2802 if (rhs
.type
!= ADDRESSOF
2803 && !get_varinfo (rhs
.var
)->may_have_pointers
)
2806 /* Likewise adding to the solution of a non-pointer var isn't useful. */
2807 if (!get_varinfo (lhs
.var
)->may_have_pointers
)
2810 /* This can happen in our IR with things like n->a = *p */
2811 if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
2813 /* Split into tmp = *rhs, *lhs = tmp */
2814 struct constraint_expr tmplhs
;
2815 tmplhs
= new_scalar_tmp_constraint_exp ("doubledereftmp");
2816 process_constraint (new_constraint (tmplhs
, rhs
));
2817 process_constraint (new_constraint (lhs
, tmplhs
));
2819 else if (rhs
.type
== ADDRESSOF
&& lhs
.type
== DEREF
)
2821 /* Split into tmp = &rhs, *lhs = tmp */
2822 struct constraint_expr tmplhs
;
2823 tmplhs
= new_scalar_tmp_constraint_exp ("derefaddrtmp");
2824 process_constraint (new_constraint (tmplhs
, rhs
));
2825 process_constraint (new_constraint (lhs
, tmplhs
));
2829 gcc_assert (rhs
.type
!= ADDRESSOF
|| rhs
.offset
== 0);
2830 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2835 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2838 static HOST_WIDE_INT
2839 bitpos_of_field (const tree fdecl
)
2841 if (!host_integerp (DECL_FIELD_OFFSET (fdecl
), 0)
2842 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl
), 0))
2845 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl
)) * BITS_PER_UNIT
2846 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl
)));
2850 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2851 resulting constraint expressions in *RESULTS. */
2854 get_constraint_for_ptr_offset (tree ptr
, tree offset
,
2855 VEC (ce_s
, heap
) **results
)
2857 struct constraint_expr c
;
2859 HOST_WIDE_INT rhsunitoffset
, rhsoffset
;
2861 /* If we do not do field-sensitive PTA adding offsets to pointers
2862 does not change the points-to solution. */
2863 if (!use_field_sensitive
)
2865 get_constraint_for_rhs (ptr
, results
);
2869 /* If the offset is not a non-negative integer constant that fits
2870 in a HOST_WIDE_INT, we have to fall back to a conservative
2871 solution which includes all sub-fields of all pointed-to
2872 variables of ptr. */
2873 if (offset
== NULL_TREE
2874 || !host_integerp (offset
, 0))
2875 rhsoffset
= UNKNOWN_OFFSET
;
2878 /* Make sure the bit-offset also fits. */
2879 rhsunitoffset
= TREE_INT_CST_LOW (offset
);
2880 rhsoffset
= rhsunitoffset
* BITS_PER_UNIT
;
2881 if (rhsunitoffset
!= rhsoffset
/ BITS_PER_UNIT
)
2882 rhsoffset
= UNKNOWN_OFFSET
;
2885 get_constraint_for_rhs (ptr
, results
);
2889 /* As we are eventually appending to the solution do not use
2890 VEC_iterate here. */
2891 n
= VEC_length (ce_s
, *results
);
2892 for (j
= 0; j
< n
; j
++)
2895 c
= *VEC_index (ce_s
, *results
, j
);
2896 curr
= get_varinfo (c
.var
);
2898 if (c
.type
== ADDRESSOF
2899 /* If this varinfo represents a full variable just use it. */
2900 && curr
->is_full_var
)
2902 else if (c
.type
== ADDRESSOF
2903 /* If we do not know the offset add all subfields. */
2904 && rhsoffset
== UNKNOWN_OFFSET
)
2906 varinfo_t temp
= lookup_vi_for_tree (curr
->decl
);
2909 struct constraint_expr c2
;
2911 c2
.type
= ADDRESSOF
;
2913 if (c2
.var
!= c
.var
)
2914 VEC_safe_push (ce_s
, heap
, *results
, &c2
);
2919 else if (c
.type
== ADDRESSOF
)
2922 unsigned HOST_WIDE_INT offset
= curr
->offset
+ rhsoffset
;
2924 /* Search the sub-field which overlaps with the
2925 pointed-to offset. If the result is outside of the variable
2926 we have to provide a conservative result, as the variable is
2927 still reachable from the resulting pointer (even though it
2928 technically cannot point to anything). The last and first
2929 sub-fields are such conservative results.
2930 ??? If we always had a sub-field for &object + 1 then
2931 we could represent this in a more precise way. */
2933 && curr
->offset
< offset
)
2935 temp
= first_or_preceding_vi_for_offset (curr
, offset
);
2937 /* If the found variable is not exactly at the pointed to
2938 result, we have to include the next variable in the
2939 solution as well. Otherwise two increments by offset / 2
2940 do not result in the same or a conservative superset
2942 if (temp
->offset
!= offset
2943 && temp
->next
!= NULL
)
2945 struct constraint_expr c2
;
2946 c2
.var
= temp
->next
->id
;
2947 c2
.type
= ADDRESSOF
;
2949 VEC_safe_push (ce_s
, heap
, *results
, &c2
);
2955 c
.offset
= rhsoffset
;
2957 VEC_replace (ce_s
, *results
, j
, &c
);
2962 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2963 If address_p is true the result will be taken its address of.
2964 If lhs_p is true then the constraint expression is assumed to be used
2968 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
,
2969 bool address_p
, bool lhs_p
)
2972 HOST_WIDE_INT bitsize
= -1;
2973 HOST_WIDE_INT bitmaxsize
= -1;
2974 HOST_WIDE_INT bitpos
;
2976 struct constraint_expr
*result
;
2978 /* Some people like to do cute things like take the address of
2981 while (handled_component_p (forzero
)
2982 || INDIRECT_REF_P (forzero
)
2983 || TREE_CODE (forzero
) == MEM_REF
)
2984 forzero
= TREE_OPERAND (forzero
, 0);
2986 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
2988 struct constraint_expr temp
;
2991 temp
.var
= integer_id
;
2993 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2997 /* Handle type-punning through unions. If we are extracting a pointer
2998 from a union via a possibly type-punning access that pointer
2999 points to anything, similar to a conversion of an integer to
3005 TREE_CODE (u
) == COMPONENT_REF
|| TREE_CODE (u
) == ARRAY_REF
;
3006 u
= TREE_OPERAND (u
, 0))
3007 if (TREE_CODE (u
) == COMPONENT_REF
3008 && TREE_CODE (TREE_TYPE (TREE_OPERAND (u
, 0))) == UNION_TYPE
)
3010 struct constraint_expr temp
;
3013 temp
.var
= anything_id
;
3014 temp
.type
= ADDRESSOF
;
3015 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
3020 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
3022 /* Pretend to take the address of the base, we'll take care of
3023 adding the required subset of sub-fields below. */
3024 get_constraint_for_1 (t
, results
, true, lhs_p
);
3025 gcc_assert (VEC_length (ce_s
, *results
) == 1);
3026 result
= VEC_last (ce_s
, *results
);
3028 if (result
->type
== SCALAR
3029 && get_varinfo (result
->var
)->is_full_var
)
3030 /* For single-field vars do not bother about the offset. */
3032 else if (result
->type
== SCALAR
)
3034 /* In languages like C, you can access one past the end of an
3035 array. You aren't allowed to dereference it, so we can
3036 ignore this constraint. When we handle pointer subtraction,
3037 we may have to do something cute here. */
3039 if ((unsigned HOST_WIDE_INT
)bitpos
< get_varinfo (result
->var
)->fullsize
3042 /* It's also not true that the constraint will actually start at the
3043 right offset, it may start in some padding. We only care about
3044 setting the constraint to the first actual field it touches, so
3046 struct constraint_expr cexpr
= *result
;
3048 VEC_pop (ce_s
, *results
);
3050 for (curr
= get_varinfo (cexpr
.var
); curr
; curr
= curr
->next
)
3052 if (ranges_overlap_p (curr
->offset
, curr
->size
,
3053 bitpos
, bitmaxsize
))
3055 cexpr
.var
= curr
->id
;
3056 VEC_safe_push (ce_s
, heap
, *results
, &cexpr
);
3061 /* If we are going to take the address of this field then
3062 to be able to compute reachability correctly add at least
3063 the last field of the variable. */
3065 && VEC_length (ce_s
, *results
) == 0)
3067 curr
= get_varinfo (cexpr
.var
);
3068 while (curr
->next
!= NULL
)
3070 cexpr
.var
= curr
->id
;
3071 VEC_safe_push (ce_s
, heap
, *results
, &cexpr
);
3073 else if (VEC_length (ce_s
, *results
) == 0)
3074 /* Assert that we found *some* field there. The user couldn't be
3075 accessing *only* padding. */
3076 /* Still the user could access one past the end of an array
3077 embedded in a struct resulting in accessing *only* padding. */
3078 /* Or accessing only padding via type-punning to a type
3079 that has a filed just in padding space. */
3081 cexpr
.type
= SCALAR
;
3082 cexpr
.var
= anything_id
;
3084 VEC_safe_push (ce_s
, heap
, *results
, &cexpr
);
3087 else if (bitmaxsize
== 0)
3089 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3090 fprintf (dump_file
, "Access to zero-sized part of variable,"
3094 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3095 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
3097 else if (result
->type
== DEREF
)
3099 /* If we do not know exactly where the access goes say so. Note
3100 that only for non-structure accesses we know that we access
3101 at most one subfiled of any variable. */
3103 || bitsize
!= bitmaxsize
3104 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t
))
3105 || result
->offset
== UNKNOWN_OFFSET
)
3106 result
->offset
= UNKNOWN_OFFSET
;
3108 result
->offset
+= bitpos
;
3110 else if (result
->type
== ADDRESSOF
)
3112 /* We can end up here for component references on a
3113 VIEW_CONVERT_EXPR <>(&foobar). */
3114 result
->type
= SCALAR
;
3115 result
->var
= anything_id
;
3123 /* Dereference the constraint expression CONS, and return the result.
3124 DEREF (ADDRESSOF) = SCALAR
3125 DEREF (SCALAR) = DEREF
3126 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3127 This is needed so that we can handle dereferencing DEREF constraints. */
3130 do_deref (VEC (ce_s
, heap
) **constraints
)
3132 struct constraint_expr
*c
;
3135 FOR_EACH_VEC_ELT (ce_s
, *constraints
, i
, c
)
3137 if (c
->type
== SCALAR
)
3139 else if (c
->type
== ADDRESSOF
)
3141 else if (c
->type
== DEREF
)
3143 struct constraint_expr tmplhs
;
3144 tmplhs
= new_scalar_tmp_constraint_exp ("dereftmp");
3145 process_constraint (new_constraint (tmplhs
, *c
));
3146 c
->var
= tmplhs
.var
;
3153 /* Given a tree T, return the constraint expression for taking the
3157 get_constraint_for_address_of (tree t
, VEC (ce_s
, heap
) **results
)
3159 struct constraint_expr
*c
;
3162 get_constraint_for_1 (t
, results
, true, true);
3164 FOR_EACH_VEC_ELT (ce_s
, *results
, i
, c
)
3166 if (c
->type
== DEREF
)
3169 c
->type
= ADDRESSOF
;
3173 /* Given a tree T, return the constraint expression for it. */
3176 get_constraint_for_1 (tree t
, VEC (ce_s
, heap
) **results
, bool address_p
,
3179 struct constraint_expr temp
;
3181 /* x = integer is all glommed to a single variable, which doesn't
3182 point to anything by itself. That is, of course, unless it is an
3183 integer constant being treated as a pointer, in which case, we
3184 will return that this is really the addressof anything. This
3185 happens below, since it will fall into the default case. The only
3186 case we know something about an integer treated like a pointer is
3187 when it is the NULL pointer, and then we just say it points to
3190 Do not do that if -fno-delete-null-pointer-checks though, because
3191 in that case *NULL does not fail, so it _should_ alias *anything.
3192 It is not worth adding a new option or renaming the existing one,
3193 since this case is relatively obscure. */
3194 if ((TREE_CODE (t
) == INTEGER_CST
3195 && integer_zerop (t
))
3196 /* The only valid CONSTRUCTORs in gimple with pointer typed
3197 elements are zero-initializer. But in IPA mode we also
3198 process global initializers, so verify at least. */
3199 || (TREE_CODE (t
) == CONSTRUCTOR
3200 && CONSTRUCTOR_NELTS (t
) == 0))
3202 if (flag_delete_null_pointer_checks
)
3203 temp
.var
= nothing_id
;
3205 temp
.var
= nonlocal_id
;
3206 temp
.type
= ADDRESSOF
;
3208 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
3212 /* String constants are read-only. */
3213 if (TREE_CODE (t
) == STRING_CST
)
3215 temp
.var
= readonly_id
;
3218 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
3222 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
3224 case tcc_expression
:
3226 switch (TREE_CODE (t
))
3229 get_constraint_for_address_of (TREE_OPERAND (t
, 0), results
);
3237 switch (TREE_CODE (t
))
3241 struct constraint_expr cs
;
3243 tree off
= double_int_to_tree (sizetype
, mem_ref_offset (t
));
3244 get_constraint_for_ptr_offset (TREE_OPERAND (t
, 0), off
, results
);
3247 /* If we are not taking the address then make sure to process
3248 all subvariables we might access. */
3249 cs
= *VEC_last (ce_s
, *results
);
3251 || cs
.type
!= SCALAR
)
3254 vi
= get_varinfo (cs
.var
);
3256 if (!vi
->is_full_var
3259 unsigned HOST_WIDE_INT size
;
3260 if (host_integerp (TYPE_SIZE (TREE_TYPE (t
)), 1))
3261 size
= TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (t
)));
3264 for (; curr
; curr
= curr
->next
)
3266 if (curr
->offset
- vi
->offset
< size
)
3269 VEC_safe_push (ce_s
, heap
, *results
, &cs
);
3278 case ARRAY_RANGE_REF
:
3280 get_constraint_for_component_ref (t
, results
, address_p
, lhs_p
);
3282 case VIEW_CONVERT_EXPR
:
3283 get_constraint_for_1 (TREE_OPERAND (t
, 0), results
, address_p
,
3286 /* We are missing handling for TARGET_MEM_REF here. */
3291 case tcc_exceptional
:
3293 switch (TREE_CODE (t
))
3297 get_constraint_for_ssa_var (t
, results
, address_p
);
3304 VEC (ce_s
, heap
) *tmp
= NULL
;
3305 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t
), i
, val
)
3307 struct constraint_expr
*rhsp
;
3309 get_constraint_for_1 (val
, &tmp
, address_p
, lhs_p
);
3310 FOR_EACH_VEC_ELT (ce_s
, tmp
, j
, rhsp
)
3311 VEC_safe_push (ce_s
, heap
, *results
, rhsp
);
3312 VEC_truncate (ce_s
, tmp
, 0);
3314 VEC_free (ce_s
, heap
, tmp
);
3315 /* We do not know whether the constructor was complete,
3316 so technically we have to add &NOTHING or &ANYTHING
3317 like we do for an empty constructor as well. */
3324 case tcc_declaration
:
3326 get_constraint_for_ssa_var (t
, results
, address_p
);
3331 /* We cannot refer to automatic variables through constants. */
3332 temp
.type
= ADDRESSOF
;
3333 temp
.var
= nonlocal_id
;
3335 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
3341 /* The default fallback is a constraint from anything. */
3342 temp
.type
= ADDRESSOF
;
3343 temp
.var
= anything_id
;
3345 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
3348 /* Given a gimple tree T, return the constraint expression vector for it. */
3351 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
3353 gcc_assert (VEC_length (ce_s
, *results
) == 0);
3355 get_constraint_for_1 (t
, results
, false, true);
3358 /* Given a gimple tree T, return the constraint expression vector for it
3359 to be used as the rhs of a constraint. */
3362 get_constraint_for_rhs (tree t
, VEC (ce_s
, heap
) **results
)
3364 gcc_assert (VEC_length (ce_s
, *results
) == 0);
3366 get_constraint_for_1 (t
, results
, false, false);
3370 /* Efficiently generates constraints from all entries in *RHSC to all
3371 entries in *LHSC. */
3374 process_all_all_constraints (VEC (ce_s
, heap
) *lhsc
, VEC (ce_s
, heap
) *rhsc
)
3376 struct constraint_expr
*lhsp
, *rhsp
;
3379 if (VEC_length (ce_s
, lhsc
) <= 1
3380 || VEC_length (ce_s
, rhsc
) <= 1)
3382 FOR_EACH_VEC_ELT (ce_s
, lhsc
, i
, lhsp
)
3383 FOR_EACH_VEC_ELT (ce_s
, rhsc
, j
, rhsp
)
3384 process_constraint (new_constraint (*lhsp
, *rhsp
));
3388 struct constraint_expr tmp
;
3389 tmp
= new_scalar_tmp_constraint_exp ("allalltmp");
3390 FOR_EACH_VEC_ELT (ce_s
, rhsc
, i
, rhsp
)
3391 process_constraint (new_constraint (tmp
, *rhsp
));
3392 FOR_EACH_VEC_ELT (ce_s
, lhsc
, i
, lhsp
)
3393 process_constraint (new_constraint (*lhsp
, tmp
));
3397 /* Handle aggregate copies by expanding into copies of the respective
3398 fields of the structures. */
3401 do_structure_copy (tree lhsop
, tree rhsop
)
3403 struct constraint_expr
*lhsp
, *rhsp
;
3404 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
3407 get_constraint_for (lhsop
, &lhsc
);
3408 get_constraint_for_rhs (rhsop
, &rhsc
);
3409 lhsp
= VEC_index (ce_s
, lhsc
, 0);
3410 rhsp
= VEC_index (ce_s
, rhsc
, 0);
3411 if (lhsp
->type
== DEREF
3412 || (lhsp
->type
== ADDRESSOF
&& lhsp
->var
== anything_id
)
3413 || rhsp
->type
== DEREF
)
3415 if (lhsp
->type
== DEREF
)
3417 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
3418 lhsp
->offset
= UNKNOWN_OFFSET
;
3420 if (rhsp
->type
== DEREF
)
3422 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
3423 rhsp
->offset
= UNKNOWN_OFFSET
;
3425 process_all_all_constraints (lhsc
, rhsc
);
3427 else if (lhsp
->type
== SCALAR
3428 && (rhsp
->type
== SCALAR
3429 || rhsp
->type
== ADDRESSOF
))
3431 HOST_WIDE_INT lhssize
, lhsmaxsize
, lhsoffset
;
3432 HOST_WIDE_INT rhssize
, rhsmaxsize
, rhsoffset
;
3434 get_ref_base_and_extent (lhsop
, &lhsoffset
, &lhssize
, &lhsmaxsize
);
3435 get_ref_base_and_extent (rhsop
, &rhsoffset
, &rhssize
, &rhsmaxsize
);
3436 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
);)
3438 varinfo_t lhsv
, rhsv
;
3439 rhsp
= VEC_index (ce_s
, rhsc
, k
);
3440 lhsv
= get_varinfo (lhsp
->var
);
3441 rhsv
= get_varinfo (rhsp
->var
);
3442 if (lhsv
->may_have_pointers
3443 && (lhsv
->is_full_var
3444 || rhsv
->is_full_var
3445 || ranges_overlap_p (lhsv
->offset
+ rhsoffset
, lhsv
->size
,
3446 rhsv
->offset
+ lhsoffset
, rhsv
->size
)))
3447 process_constraint (new_constraint (*lhsp
, *rhsp
));
3448 if (!rhsv
->is_full_var
3449 && (lhsv
->is_full_var
3450 || (lhsv
->offset
+ rhsoffset
+ lhsv
->size
3451 > rhsv
->offset
+ lhsoffset
+ rhsv
->size
)))
3454 if (k
>= VEC_length (ce_s
, rhsc
))
3464 VEC_free (ce_s
, heap
, lhsc
);
3465 VEC_free (ce_s
, heap
, rhsc
);
3468 /* Create constraints ID = { rhsc }. */
3471 make_constraints_to (unsigned id
, VEC(ce_s
, heap
) *rhsc
)
3473 struct constraint_expr
*c
;
3474 struct constraint_expr includes
;
3478 includes
.offset
= 0;
3479 includes
.type
= SCALAR
;
3481 FOR_EACH_VEC_ELT (ce_s
, rhsc
, j
, c
)
3482 process_constraint (new_constraint (includes
, *c
));
3485 /* Create a constraint ID = OP. */
3488 make_constraint_to (unsigned id
, tree op
)
3490 VEC(ce_s
, heap
) *rhsc
= NULL
;
3491 get_constraint_for_rhs (op
, &rhsc
);
3492 make_constraints_to (id
, rhsc
);
3493 VEC_free (ce_s
, heap
, rhsc
);
3496 /* Create a constraint ID = &FROM. */
3499 make_constraint_from (varinfo_t vi
, int from
)
3501 struct constraint_expr lhs
, rhs
;
3509 rhs
.type
= ADDRESSOF
;
3510 process_constraint (new_constraint (lhs
, rhs
));
3513 /* Create a constraint ID = FROM. */
3516 make_copy_constraint (varinfo_t vi
, int from
)
3518 struct constraint_expr lhs
, rhs
;
3527 process_constraint (new_constraint (lhs
, rhs
));
3530 /* Make constraints necessary to make OP escape. */
3533 make_escape_constraint (tree op
)
3535 make_constraint_to (escaped_id
, op
);
3538 /* Add constraints to that the solution of VI is transitively closed. */
3541 make_transitive_closure_constraints (varinfo_t vi
)
3543 struct constraint_expr lhs
, rhs
;
3552 process_constraint (new_constraint (lhs
, rhs
));
3554 /* VAR = VAR + UNKNOWN; */
3560 rhs
.offset
= UNKNOWN_OFFSET
;
3561 process_constraint (new_constraint (lhs
, rhs
));
3564 /* Temporary storage for fake var decls. */
3565 struct obstack fake_var_decl_obstack
;
3567 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3570 build_fake_var_decl (tree type
)
3572 tree decl
= (tree
) XOBNEW (&fake_var_decl_obstack
, struct tree_var_decl
);
3573 memset (decl
, 0, sizeof (struct tree_var_decl
));
3574 TREE_SET_CODE (decl
, VAR_DECL
);
3575 TREE_TYPE (decl
) = type
;
3576 DECL_UID (decl
) = allocate_decl_uid ();
3577 SET_DECL_PT_UID (decl
, -1);
3578 layout_decl (decl
, 0);
3582 /* Create a new artificial heap variable with NAME.
3583 Return the created variable. */
3586 make_heapvar (const char *name
)
3591 heapvar
= build_fake_var_decl (ptr_type_node
);
3592 DECL_EXTERNAL (heapvar
) = 1;
3594 vi
= new_var_info (heapvar
, name
);
3595 vi
->is_artificial_var
= true;
3596 vi
->is_heap_var
= true;
3597 vi
->is_unknown_size_var
= true;
3601 vi
->is_full_var
= true;
3602 insert_vi_for_tree (heapvar
, vi
);
3607 /* Create a new artificial heap variable with NAME and make a
3608 constraint from it to LHS. Return the created variable. */
3611 make_constraint_from_heapvar (varinfo_t lhs
, const char *name
)
3613 varinfo_t vi
= make_heapvar (name
);
3614 make_constraint_from (lhs
, vi
->id
);
3619 /* Create a new artificial heap variable with NAME and make a
3620 constraint from it to LHS. Set flags according to a tag used
3621 for tracking restrict pointers. */
3624 make_constraint_from_restrict (varinfo_t lhs
, const char *name
)
3627 vi
= make_constraint_from_heapvar (lhs
, name
);
3628 vi
->is_restrict_var
= 1;
3629 vi
->is_global_var
= 0;
3630 vi
->is_special_var
= 1;
3631 vi
->may_have_pointers
= 0;
3634 /* In IPA mode there are varinfos for different aspects of reach
3635 function designator. One for the points-to set of the return
3636 value, one for the variables that are clobbered by the function,
3637 one for its uses and one for each parameter (including a single
3638 glob for remaining variadic arguments). */
3640 enum { fi_clobbers
= 1, fi_uses
= 2,
3641 fi_static_chain
= 3, fi_result
= 4, fi_parm_base
= 5 };
3643 /* Get a constraint for the requested part of a function designator FI
3644 when operating in IPA mode. */
3646 static struct constraint_expr
3647 get_function_part_constraint (varinfo_t fi
, unsigned part
)
3649 struct constraint_expr c
;
3651 gcc_assert (in_ipa_mode
);
3653 if (fi
->id
== anything_id
)
3655 /* ??? We probably should have a ANYFN special variable. */
3656 c
.var
= anything_id
;
3660 else if (TREE_CODE (fi
->decl
) == FUNCTION_DECL
)
3662 varinfo_t ai
= first_vi_for_offset (fi
, part
);
3666 c
.var
= anything_id
;
3680 /* For non-IPA mode, generate constraints necessary for a call on the
3684 handle_rhs_call (gimple stmt
, VEC(ce_s
, heap
) **results
)
3686 struct constraint_expr rhsc
;
3688 bool returns_uses
= false;
3690 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3692 tree arg
= gimple_call_arg (stmt
, i
);
3693 int flags
= gimple_call_arg_flags (stmt
, i
);
3695 /* If the argument is not used we can ignore it. */
3696 if (flags
& EAF_UNUSED
)
3699 /* As we compute ESCAPED context-insensitive we do not gain
3700 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3701 set. The argument would still get clobbered through the
3703 ??? We might get away with less (and more precise) constraints
3704 if using a temporary for transitively closing things. */
3705 if ((flags
& EAF_NOCLOBBER
)
3706 && (flags
& EAF_NOESCAPE
))
3708 varinfo_t uses
= get_call_use_vi (stmt
);
3709 if (!(flags
& EAF_DIRECT
))
3710 make_transitive_closure_constraints (uses
);
3711 make_constraint_to (uses
->id
, arg
);
3712 returns_uses
= true;
3714 else if (flags
& EAF_NOESCAPE
)
3716 varinfo_t uses
= get_call_use_vi (stmt
);
3717 varinfo_t clobbers
= get_call_clobber_vi (stmt
);
3718 if (!(flags
& EAF_DIRECT
))
3720 make_transitive_closure_constraints (uses
);
3721 make_transitive_closure_constraints (clobbers
);
3723 make_constraint_to (uses
->id
, arg
);
3724 make_constraint_to (clobbers
->id
, arg
);
3725 returns_uses
= true;
3728 make_escape_constraint (arg
);
3731 /* If we added to the calls uses solution make sure we account for
3732 pointers to it to be returned. */
3735 rhsc
.var
= get_call_use_vi (stmt
)->id
;
3738 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3741 /* The static chain escapes as well. */
3742 if (gimple_call_chain (stmt
))
3743 make_escape_constraint (gimple_call_chain (stmt
));
3745 /* And if we applied NRV the address of the return slot escapes as well. */
3746 if (gimple_call_return_slot_opt_p (stmt
)
3747 && gimple_call_lhs (stmt
) != NULL_TREE
3748 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt
))))
3750 VEC(ce_s
, heap
) *tmpc
= NULL
;
3751 struct constraint_expr lhsc
, *c
;
3752 get_constraint_for_address_of (gimple_call_lhs (stmt
), &tmpc
);
3753 lhsc
.var
= escaped_id
;
3756 FOR_EACH_VEC_ELT (ce_s
, tmpc
, i
, c
)
3757 process_constraint (new_constraint (lhsc
, *c
));
3758 VEC_free(ce_s
, heap
, tmpc
);
3761 /* Regular functions return nonlocal memory. */
3762 rhsc
.var
= nonlocal_id
;
3765 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3768 /* For non-IPA mode, generate constraints necessary for a call
3769 that returns a pointer and assigns it to LHS. This simply makes
3770 the LHS point to global and escaped variables. */
3773 handle_lhs_call (gimple stmt
, tree lhs
, int flags
, VEC(ce_s
, heap
) *rhsc
,
3776 VEC(ce_s
, heap
) *lhsc
= NULL
;
3778 get_constraint_for (lhs
, &lhsc
);
3779 /* If the store is to a global decl make sure to
3780 add proper escape constraints. */
3781 lhs
= get_base_address (lhs
);
3784 && is_global_var (lhs
))
3786 struct constraint_expr tmpc
;
3787 tmpc
.var
= escaped_id
;
3790 VEC_safe_push (ce_s
, heap
, lhsc
, &tmpc
);
3793 /* If the call returns an argument unmodified override the rhs
3795 flags
= gimple_call_return_flags (stmt
);
3796 if (flags
& ERF_RETURNS_ARG
3797 && (flags
& ERF_RETURN_ARG_MASK
) < gimple_call_num_args (stmt
))
3801 arg
= gimple_call_arg (stmt
, flags
& ERF_RETURN_ARG_MASK
);
3802 get_constraint_for (arg
, &rhsc
);
3803 process_all_all_constraints (lhsc
, rhsc
);
3804 VEC_free (ce_s
, heap
, rhsc
);
3806 else if (flags
& ERF_NOALIAS
)
3809 struct constraint_expr tmpc
;
3811 vi
= make_heapvar ("HEAP");
3812 /* We delay marking allocated storage global until we know if
3814 DECL_EXTERNAL (vi
->decl
) = 0;
3815 vi
->is_global_var
= 0;
3816 /* If this is not a real malloc call assume the memory was
3817 initialized and thus may point to global memory. All
3818 builtin functions with the malloc attribute behave in a sane way. */
3820 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
3821 make_constraint_from (vi
, nonlocal_id
);
3824 tmpc
.type
= ADDRESSOF
;
3825 VEC_safe_push (ce_s
, heap
, rhsc
, &tmpc
);
3828 process_all_all_constraints (lhsc
, rhsc
);
3830 VEC_free (ce_s
, heap
, lhsc
);
3833 /* For non-IPA mode, generate constraints necessary for a call of a
3834 const function that returns a pointer in the statement STMT. */
3837 handle_const_call (gimple stmt
, VEC(ce_s
, heap
) **results
)
3839 struct constraint_expr rhsc
;
3842 /* Treat nested const functions the same as pure functions as far
3843 as the static chain is concerned. */
3844 if (gimple_call_chain (stmt
))
3846 varinfo_t uses
= get_call_use_vi (stmt
);
3847 make_transitive_closure_constraints (uses
);
3848 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
3849 rhsc
.var
= uses
->id
;
3852 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3855 /* May return arguments. */
3856 for (k
= 0; k
< gimple_call_num_args (stmt
); ++k
)
3858 tree arg
= gimple_call_arg (stmt
, k
);
3859 VEC(ce_s
, heap
) *argc
= NULL
;
3861 struct constraint_expr
*argp
;
3862 get_constraint_for_rhs (arg
, &argc
);
3863 FOR_EACH_VEC_ELT (ce_s
, argc
, i
, argp
)
3864 VEC_safe_push (ce_s
, heap
, *results
, argp
);
3865 VEC_free(ce_s
, heap
, argc
);
3868 /* May return addresses of globals. */
3869 rhsc
.var
= nonlocal_id
;
3871 rhsc
.type
= ADDRESSOF
;
3872 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3875 /* For non-IPA mode, generate constraints necessary for a call to a
3876 pure function in statement STMT. */
3879 handle_pure_call (gimple stmt
, VEC(ce_s
, heap
) **results
)
3881 struct constraint_expr rhsc
;
3883 varinfo_t uses
= NULL
;
3885 /* Memory reached from pointer arguments is call-used. */
3886 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3888 tree arg
= gimple_call_arg (stmt
, i
);
3891 uses
= get_call_use_vi (stmt
);
3892 make_transitive_closure_constraints (uses
);
3894 make_constraint_to (uses
->id
, arg
);
3897 /* The static chain is used as well. */
3898 if (gimple_call_chain (stmt
))
3902 uses
= get_call_use_vi (stmt
);
3903 make_transitive_closure_constraints (uses
);
3905 make_constraint_to (uses
->id
, gimple_call_chain (stmt
));
3908 /* Pure functions may return call-used and nonlocal memory. */
3911 rhsc
.var
= uses
->id
;
3914 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3916 rhsc
.var
= nonlocal_id
;
3919 VEC_safe_push (ce_s
, heap
, *results
, &rhsc
);
3923 /* Return the varinfo for the callee of CALL. */
3926 get_fi_for_callee (gimple call
)
3928 tree decl
, fn
= gimple_call_fn (call
);
3930 if (fn
&& TREE_CODE (fn
) == OBJ_TYPE_REF
)
3931 fn
= OBJ_TYPE_REF_EXPR (fn
);
3933 /* If we can directly resolve the function being called, do so.
3934 Otherwise, it must be some sort of indirect expression that
3935 we should still be able to handle. */
3936 decl
= gimple_call_addr_fndecl (fn
);
3938 return get_vi_for_tree (decl
);
3940 /* If the function is anything other than a SSA name pointer we have no
3941 clue and should be getting ANYFN (well, ANYTHING for now). */
3942 if (!fn
|| TREE_CODE (fn
) != SSA_NAME
)
3943 return get_varinfo (anything_id
);
3945 if ((TREE_CODE (SSA_NAME_VAR (fn
)) == PARM_DECL
3946 || TREE_CODE (SSA_NAME_VAR (fn
)) == RESULT_DECL
)
3947 && SSA_NAME_IS_DEFAULT_DEF (fn
))
3948 fn
= SSA_NAME_VAR (fn
);
3950 return get_vi_for_tree (fn
);
3953 /* Create constraints for the builtin call T. Return true if the call
3954 was handled, otherwise false. */
3957 find_func_aliases_for_builtin_call (gimple t
)
3959 tree fndecl
= gimple_call_fndecl (t
);
3960 VEC(ce_s
, heap
) *lhsc
= NULL
;
3961 VEC(ce_s
, heap
) *rhsc
= NULL
;
3964 if (fndecl
!= NULL_TREE
3965 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
3966 /* ??? All builtins that are handled here need to be handled
3967 in the alias-oracle query functions explicitly! */
3968 switch (DECL_FUNCTION_CODE (fndecl
))
3970 /* All the following functions return a pointer to the same object
3971 as their first argument points to. The functions do not add
3972 to the ESCAPED solution. The functions make the first argument
3973 pointed to memory point to what the second argument pointed to
3974 memory points to. */
3975 case BUILT_IN_STRCPY
:
3976 case BUILT_IN_STRNCPY
:
3977 case BUILT_IN_BCOPY
:
3978 case BUILT_IN_MEMCPY
:
3979 case BUILT_IN_MEMMOVE
:
3980 case BUILT_IN_MEMPCPY
:
3981 case BUILT_IN_STPCPY
:
3982 case BUILT_IN_STPNCPY
:
3983 case BUILT_IN_STRCAT
:
3984 case BUILT_IN_STRNCAT
:
3986 tree res
= gimple_call_lhs (t
);
3987 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
3988 == BUILT_IN_BCOPY
? 1 : 0));
3989 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (fndecl
)
3990 == BUILT_IN_BCOPY
? 0 : 1));
3991 if (res
!= NULL_TREE
)
3993 get_constraint_for (res
, &lhsc
);
3994 if (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMPCPY
3995 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPCPY
3996 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_STPNCPY
)
3997 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &rhsc
);
3999 get_constraint_for (dest
, &rhsc
);
4000 process_all_all_constraints (lhsc
, rhsc
);
4001 VEC_free (ce_s
, heap
, lhsc
);
4002 VEC_free (ce_s
, heap
, rhsc
);
4004 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4005 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4008 process_all_all_constraints (lhsc
, rhsc
);
4009 VEC_free (ce_s
, heap
, lhsc
);
4010 VEC_free (ce_s
, heap
, rhsc
);
4013 case BUILT_IN_MEMSET
:
4015 tree res
= gimple_call_lhs (t
);
4016 tree dest
= gimple_call_arg (t
, 0);
4019 struct constraint_expr ac
;
4020 if (res
!= NULL_TREE
)
4022 get_constraint_for (res
, &lhsc
);
4023 get_constraint_for (dest
, &rhsc
);
4024 process_all_all_constraints (lhsc
, rhsc
);
4025 VEC_free (ce_s
, heap
, lhsc
);
4026 VEC_free (ce_s
, heap
, rhsc
);
4028 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4030 if (flag_delete_null_pointer_checks
4031 && integer_zerop (gimple_call_arg (t
, 1)))
4033 ac
.type
= ADDRESSOF
;
4034 ac
.var
= nothing_id
;
4039 ac
.var
= integer_id
;
4042 FOR_EACH_VEC_ELT (ce_s
, lhsc
, i
, lhsp
)
4043 process_constraint (new_constraint (*lhsp
, ac
));
4044 VEC_free (ce_s
, heap
, lhsc
);
4047 /* All the following functions do not return pointers, do not
4048 modify the points-to sets of memory reachable from their
4049 arguments and do not add to the ESCAPED solution. */
4050 case BUILT_IN_SINCOS
:
4051 case BUILT_IN_SINCOSF
:
4052 case BUILT_IN_SINCOSL
:
4053 case BUILT_IN_FREXP
:
4054 case BUILT_IN_FREXPF
:
4055 case BUILT_IN_FREXPL
:
4056 case BUILT_IN_GAMMA_R
:
4057 case BUILT_IN_GAMMAF_R
:
4058 case BUILT_IN_GAMMAL_R
:
4059 case BUILT_IN_LGAMMA_R
:
4060 case BUILT_IN_LGAMMAF_R
:
4061 case BUILT_IN_LGAMMAL_R
:
4063 case BUILT_IN_MODFF
:
4064 case BUILT_IN_MODFL
:
4065 case BUILT_IN_REMQUO
:
4066 case BUILT_IN_REMQUOF
:
4067 case BUILT_IN_REMQUOL
:
4070 /* Trampolines are special - they set up passing the static
4072 case BUILT_IN_INIT_TRAMPOLINE
:
4074 tree tramp
= gimple_call_arg (t
, 0);
4075 tree nfunc
= gimple_call_arg (t
, 1);
4076 tree frame
= gimple_call_arg (t
, 2);
4078 struct constraint_expr lhs
, *rhsp
;
4081 varinfo_t nfi
= NULL
;
4082 gcc_assert (TREE_CODE (nfunc
) == ADDR_EXPR
);
4083 nfi
= lookup_vi_for_tree (TREE_OPERAND (nfunc
, 0));
4086 lhs
= get_function_part_constraint (nfi
, fi_static_chain
);
4087 get_constraint_for (frame
, &rhsc
);
4088 FOR_EACH_VEC_ELT (ce_s
, rhsc
, i
, rhsp
)
4089 process_constraint (new_constraint (lhs
, *rhsp
));
4090 VEC_free (ce_s
, heap
, rhsc
);
4092 /* Make the frame point to the function for
4093 the trampoline adjustment call. */
4094 get_constraint_for (tramp
, &lhsc
);
4096 get_constraint_for (nfunc
, &rhsc
);
4097 process_all_all_constraints (lhsc
, rhsc
);
4098 VEC_free (ce_s
, heap
, rhsc
);
4099 VEC_free (ce_s
, heap
, lhsc
);
4104 /* Else fallthru to generic handling which will let
4105 the frame escape. */
4108 case BUILT_IN_ADJUST_TRAMPOLINE
:
4110 tree tramp
= gimple_call_arg (t
, 0);
4111 tree res
= gimple_call_lhs (t
);
4112 if (in_ipa_mode
&& res
)
4114 get_constraint_for (res
, &lhsc
);
4115 get_constraint_for (tramp
, &rhsc
);
4117 process_all_all_constraints (lhsc
, rhsc
);
4118 VEC_free (ce_s
, heap
, rhsc
);
4119 VEC_free (ce_s
, heap
, lhsc
);
4123 /* Variadic argument handling needs to be handled in IPA
4125 case BUILT_IN_VA_START
:
4129 tree valist
= gimple_call_arg (t
, 0);
4130 struct constraint_expr rhs
, *lhsp
;
4132 /* The va_list gets access to pointers in variadic
4134 fi
= lookup_vi_for_tree (cfun
->decl
);
4135 gcc_assert (fi
!= NULL
);
4136 get_constraint_for (valist
, &lhsc
);
4138 rhs
= get_function_part_constraint (fi
, ~0);
4139 rhs
.type
= ADDRESSOF
;
4140 FOR_EACH_VEC_ELT (ce_s
, lhsc
, i
, lhsp
)
4141 process_constraint (new_constraint (*lhsp
, rhs
));
4142 VEC_free (ce_s
, heap
, lhsc
);
4143 /* va_list is clobbered. */
4144 make_constraint_to (get_call_clobber_vi (t
)->id
, valist
);
4149 /* va_end doesn't have any effect that matters. */
4150 case BUILT_IN_VA_END
:
4152 /* Alternate return. Simply give up for now. */
4153 case BUILT_IN_RETURN
:
4157 || !(fi
= get_vi_for_tree (cfun
->decl
)))
4158 make_constraint_from (get_varinfo (escaped_id
), anything_id
);
4159 else if (in_ipa_mode
4162 struct constraint_expr lhs
, rhs
;
4163 lhs
= get_function_part_constraint (fi
, fi_result
);
4164 rhs
.var
= anything_id
;
4167 process_constraint (new_constraint (lhs
, rhs
));
4171 /* printf-style functions may have hooks to set pointers to
4172 point to somewhere into the generated string. Leave them
4173 for a later excercise... */
4175 /* Fallthru to general call handling. */;
4181 /* Create constraints for the call T. */
4184 find_func_aliases_for_call (gimple t
)
4186 tree fndecl
= gimple_call_fndecl (t
);
4187 VEC(ce_s
, heap
) *lhsc
= NULL
;
4188 VEC(ce_s
, heap
) *rhsc
= NULL
;
4191 if (fndecl
!= NULL_TREE
4192 && DECL_BUILT_IN (fndecl
)
4193 && find_func_aliases_for_builtin_call (t
))
4196 fi
= get_fi_for_callee (t
);
4198 || (fndecl
&& !fi
->is_fn_info
))
4200 VEC(ce_s
, heap
) *rhsc
= NULL
;
4201 int flags
= gimple_call_flags (t
);
4203 /* Const functions can return their arguments and addresses
4204 of global memory but not of escaped memory. */
4205 if (flags
& (ECF_CONST
|ECF_NOVOPS
))
4207 if (gimple_call_lhs (t
))
4208 handle_const_call (t
, &rhsc
);
4210 /* Pure functions can return addresses in and of memory
4211 reachable from their arguments, but they are not an escape
4212 point for reachable memory of their arguments. */
4213 else if (flags
& (ECF_PURE
|ECF_LOOPING_CONST_OR_PURE
))
4214 handle_pure_call (t
, &rhsc
);
4216 handle_rhs_call (t
, &rhsc
);
4217 if (gimple_call_lhs (t
))
4218 handle_lhs_call (t
, gimple_call_lhs (t
), flags
, rhsc
, fndecl
);
4219 VEC_free (ce_s
, heap
, rhsc
);
4226 /* Assign all the passed arguments to the appropriate incoming
4227 parameters of the function. */
4228 for (j
= 0; j
< gimple_call_num_args (t
); j
++)
4230 struct constraint_expr lhs
;
4231 struct constraint_expr
*rhsp
;
4232 tree arg
= gimple_call_arg (t
, j
);
4234 get_constraint_for_rhs (arg
, &rhsc
);
4235 lhs
= get_function_part_constraint (fi
, fi_parm_base
+ j
);
4236 while (VEC_length (ce_s
, rhsc
) != 0)
4238 rhsp
= VEC_last (ce_s
, rhsc
);
4239 process_constraint (new_constraint (lhs
, *rhsp
));
4240 VEC_pop (ce_s
, rhsc
);
4244 /* If we are returning a value, assign it to the result. */
4245 lhsop
= gimple_call_lhs (t
);
4248 struct constraint_expr rhs
;
4249 struct constraint_expr
*lhsp
;
4251 get_constraint_for (lhsop
, &lhsc
);
4252 rhs
= get_function_part_constraint (fi
, fi_result
);
4254 && DECL_RESULT (fndecl
)
4255 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4257 VEC(ce_s
, heap
) *tem
= NULL
;
4258 VEC_safe_push (ce_s
, heap
, tem
, &rhs
);
4260 rhs
= *VEC_index (ce_s
, tem
, 0);
4261 VEC_free(ce_s
, heap
, tem
);
4263 FOR_EACH_VEC_ELT (ce_s
, lhsc
, j
, lhsp
)
4264 process_constraint (new_constraint (*lhsp
, rhs
));
4267 /* If we pass the result decl by reference, honor that. */
4270 && DECL_RESULT (fndecl
)
4271 && DECL_BY_REFERENCE (DECL_RESULT (fndecl
)))
4273 struct constraint_expr lhs
;
4274 struct constraint_expr
*rhsp
;
4276 get_constraint_for_address_of (lhsop
, &rhsc
);
4277 lhs
= get_function_part_constraint (fi
, fi_result
);
4278 FOR_EACH_VEC_ELT (ce_s
, rhsc
, j
, rhsp
)
4279 process_constraint (new_constraint (lhs
, *rhsp
));
4280 VEC_free (ce_s
, heap
, rhsc
);
4283 /* If we use a static chain, pass it along. */
4284 if (gimple_call_chain (t
))
4286 struct constraint_expr lhs
;
4287 struct constraint_expr
*rhsp
;
4289 get_constraint_for (gimple_call_chain (t
), &rhsc
);
4290 lhs
= get_function_part_constraint (fi
, fi_static_chain
);
4291 FOR_EACH_VEC_ELT (ce_s
, rhsc
, j
, rhsp
)
4292 process_constraint (new_constraint (lhs
, *rhsp
));
4297 /* Walk statement T setting up aliasing constraints according to the
4298 references found in T. This function is the main part of the
4299 constraint builder. AI points to auxiliary alias information used
4300 when building alias sets and computing alias grouping heuristics. */
4303 find_func_aliases (gimple origt
)
4306 VEC(ce_s
, heap
) *lhsc
= NULL
;
4307 VEC(ce_s
, heap
) *rhsc
= NULL
;
4308 struct constraint_expr
*c
;
4311 /* Now build constraints expressions. */
4312 if (gimple_code (t
) == GIMPLE_PHI
)
4317 /* For a phi node, assign all the arguments to
4319 get_constraint_for (gimple_phi_result (t
), &lhsc
);
4320 for (i
= 0; i
< gimple_phi_num_args (t
); i
++)
4322 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
4324 STRIP_NOPS (strippedrhs
);
4325 get_constraint_for_rhs (gimple_phi_arg_def (t
, i
), &rhsc
);
4327 FOR_EACH_VEC_ELT (ce_s
, lhsc
, j
, c
)
4329 struct constraint_expr
*c2
;
4330 while (VEC_length (ce_s
, rhsc
) > 0)
4332 c2
= VEC_last (ce_s
, rhsc
);
4333 process_constraint (new_constraint (*c
, *c2
));
4334 VEC_pop (ce_s
, rhsc
);
4339 /* In IPA mode, we need to generate constraints to pass call
4340 arguments through their calls. There are two cases,
4341 either a GIMPLE_CALL returning a value, or just a plain
4342 GIMPLE_CALL when we are not.
4344 In non-ipa mode, we need to generate constraints for each
4345 pointer passed by address. */
4346 else if (is_gimple_call (t
))
4347 find_func_aliases_for_call (t
);
4349 /* Otherwise, just a regular assignment statement. Only care about
4350 operations with pointer result, others are dealt with as escape
4351 points if they have pointer operands. */
4352 else if (is_gimple_assign (t
))
4354 /* Otherwise, just a regular assignment statement. */
4355 tree lhsop
= gimple_assign_lhs (t
);
4356 tree rhsop
= (gimple_num_ops (t
) == 2) ? gimple_assign_rhs1 (t
) : NULL
;
4358 if (rhsop
&& AGGREGATE_TYPE_P (TREE_TYPE (lhsop
)))
4359 do_structure_copy (lhsop
, rhsop
);
4362 enum tree_code code
= gimple_assign_rhs_code (t
);
4364 get_constraint_for (lhsop
, &lhsc
);
4366 if (code
== POINTER_PLUS_EXPR
)
4367 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4368 gimple_assign_rhs2 (t
), &rhsc
);
4369 else if (code
== BIT_AND_EXPR
4370 && TREE_CODE (gimple_assign_rhs2 (t
)) == INTEGER_CST
)
4372 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4373 the pointer. Handle it by offsetting it by UNKNOWN. */
4374 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t
),
4377 else if ((CONVERT_EXPR_CODE_P (code
)
4378 && !(POINTER_TYPE_P (gimple_expr_type (t
))
4379 && !POINTER_TYPE_P (TREE_TYPE (rhsop
))))
4380 || gimple_assign_single_p (t
))
4381 get_constraint_for_rhs (rhsop
, &rhsc
);
4382 else if (truth_value_p (code
))
4383 /* Truth value results are not pointer (parts). Or at least
4384 very very unreasonable obfuscation of a part. */
4388 /* All other operations are merges. */
4389 VEC (ce_s
, heap
) *tmp
= NULL
;
4390 struct constraint_expr
*rhsp
;
4392 get_constraint_for_rhs (gimple_assign_rhs1 (t
), &rhsc
);
4393 for (i
= 2; i
< gimple_num_ops (t
); ++i
)
4395 get_constraint_for_rhs (gimple_op (t
, i
), &tmp
);
4396 FOR_EACH_VEC_ELT (ce_s
, tmp
, j
, rhsp
)
4397 VEC_safe_push (ce_s
, heap
, rhsc
, rhsp
);
4398 VEC_truncate (ce_s
, tmp
, 0);
4400 VEC_free (ce_s
, heap
, tmp
);
4402 process_all_all_constraints (lhsc
, rhsc
);
4404 /* If there is a store to a global variable the rhs escapes. */
4405 if ((lhsop
= get_base_address (lhsop
)) != NULL_TREE
4407 && is_global_var (lhsop
)
4409 || DECL_EXTERNAL (lhsop
) || TREE_PUBLIC (lhsop
)))
4410 make_escape_constraint (rhsop
);
4411 /* If this is a conversion of a non-restrict pointer to a
4412 restrict pointer track it with a new heapvar. */
4413 else if (gimple_assign_cast_p (t
)
4414 && POINTER_TYPE_P (TREE_TYPE (rhsop
))
4415 && POINTER_TYPE_P (TREE_TYPE (lhsop
))
4416 && !TYPE_RESTRICT (TREE_TYPE (rhsop
))
4417 && TYPE_RESTRICT (TREE_TYPE (lhsop
)))
4418 make_constraint_from_restrict (get_vi_for_tree (lhsop
),
4421 /* Handle escapes through return. */
4422 else if (gimple_code (t
) == GIMPLE_RETURN
4423 && gimple_return_retval (t
) != NULL_TREE
)
4427 || !(fi
= get_vi_for_tree (cfun
->decl
)))
4428 make_escape_constraint (gimple_return_retval (t
));
4429 else if (in_ipa_mode
4432 struct constraint_expr lhs
;
4433 struct constraint_expr
*rhsp
;
4436 lhs
= get_function_part_constraint (fi
, fi_result
);
4437 get_constraint_for_rhs (gimple_return_retval (t
), &rhsc
);
4438 FOR_EACH_VEC_ELT (ce_s
, rhsc
, i
, rhsp
)
4439 process_constraint (new_constraint (lhs
, *rhsp
));
4442 /* Handle asms conservatively by adding escape constraints to everything. */
4443 else if (gimple_code (t
) == GIMPLE_ASM
)
4445 unsigned i
, noutputs
;
4446 const char **oconstraints
;
4447 const char *constraint
;
4448 bool allows_mem
, allows_reg
, is_inout
;
4450 noutputs
= gimple_asm_noutputs (t
);
4451 oconstraints
= XALLOCAVEC (const char *, noutputs
);
4453 for (i
= 0; i
< noutputs
; ++i
)
4455 tree link
= gimple_asm_output_op (t
, i
);
4456 tree op
= TREE_VALUE (link
);
4458 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4459 oconstraints
[i
] = constraint
;
4460 parse_output_constraint (&constraint
, i
, 0, 0, &allows_mem
,
4461 &allows_reg
, &is_inout
);
4463 /* A memory constraint makes the address of the operand escape. */
4464 if (!allows_reg
&& allows_mem
)
4465 make_escape_constraint (build_fold_addr_expr (op
));
4467 /* The asm may read global memory, so outputs may point to
4468 any global memory. */
4471 VEC(ce_s
, heap
) *lhsc
= NULL
;
4472 struct constraint_expr rhsc
, *lhsp
;
4474 get_constraint_for (op
, &lhsc
);
4475 rhsc
.var
= nonlocal_id
;
4478 FOR_EACH_VEC_ELT (ce_s
, lhsc
, j
, lhsp
)
4479 process_constraint (new_constraint (*lhsp
, rhsc
));
4480 VEC_free (ce_s
, heap
, lhsc
);
4483 for (i
= 0; i
< gimple_asm_ninputs (t
); ++i
)
4485 tree link
= gimple_asm_input_op (t
, i
);
4486 tree op
= TREE_VALUE (link
);
4488 constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
4490 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0, oconstraints
,
4491 &allows_mem
, &allows_reg
);
4493 /* A memory constraint makes the address of the operand escape. */
4494 if (!allows_reg
&& allows_mem
)
4495 make_escape_constraint (build_fold_addr_expr (op
));
4496 /* Strictly we'd only need the constraint to ESCAPED if
4497 the asm clobbers memory, otherwise using something
4498 along the lines of per-call clobbers/uses would be enough. */
4500 make_escape_constraint (op
);
4504 VEC_free (ce_s
, heap
, rhsc
);
4505 VEC_free (ce_s
, heap
, lhsc
);
4509 /* Create a constraint adding to the clobber set of FI the memory
4510 pointed to by PTR. */
4513 process_ipa_clobber (varinfo_t fi
, tree ptr
)
4515 VEC(ce_s
, heap
) *ptrc
= NULL
;
4516 struct constraint_expr
*c
, lhs
;
4518 get_constraint_for_rhs (ptr
, &ptrc
);
4519 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4520 FOR_EACH_VEC_ELT (ce_s
, ptrc
, i
, c
)
4521 process_constraint (new_constraint (lhs
, *c
));
4522 VEC_free (ce_s
, heap
, ptrc
);
4525 /* Walk statement T setting up clobber and use constraints according to the
4526 references found in T. This function is a main part of the
4527 IPA constraint builder. */
4530 find_func_clobbers (gimple origt
)
4533 VEC(ce_s
, heap
) *lhsc
= NULL
;
4534 VEC(ce_s
, heap
) *rhsc
= NULL
;
4537 /* Add constraints for clobbered/used in IPA mode.
4538 We are not interested in what automatic variables are clobbered
4539 or used as we only use the information in the caller to which
4540 they do not escape. */
4541 gcc_assert (in_ipa_mode
);
4543 /* If the stmt refers to memory in any way it better had a VUSE. */
4544 if (gimple_vuse (t
) == NULL_TREE
)
4547 /* We'd better have function information for the current function. */
4548 fi
= lookup_vi_for_tree (cfun
->decl
);
4549 gcc_assert (fi
!= NULL
);
4551 /* Account for stores in assignments and calls. */
4552 if (gimple_vdef (t
) != NULL_TREE
4553 && gimple_has_lhs (t
))
4555 tree lhs
= gimple_get_lhs (t
);
4557 while (handled_component_p (tem
))
4558 tem
= TREE_OPERAND (tem
, 0);
4560 && !auto_var_in_fn_p (tem
, cfun
->decl
))
4561 || INDIRECT_REF_P (tem
)
4562 || (TREE_CODE (tem
) == MEM_REF
4563 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
4565 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), cfun
->decl
))))
4567 struct constraint_expr lhsc
, *rhsp
;
4569 lhsc
= get_function_part_constraint (fi
, fi_clobbers
);
4570 get_constraint_for_address_of (lhs
, &rhsc
);
4571 FOR_EACH_VEC_ELT (ce_s
, rhsc
, i
, rhsp
)
4572 process_constraint (new_constraint (lhsc
, *rhsp
));
4573 VEC_free (ce_s
, heap
, rhsc
);
4577 /* Account for uses in assigments and returns. */
4578 if (gimple_assign_single_p (t
)
4579 || (gimple_code (t
) == GIMPLE_RETURN
4580 && gimple_return_retval (t
) != NULL_TREE
))
4582 tree rhs
= (gimple_assign_single_p (t
)
4583 ? gimple_assign_rhs1 (t
) : gimple_return_retval (t
));
4585 while (handled_component_p (tem
))
4586 tem
= TREE_OPERAND (tem
, 0);
4588 && !auto_var_in_fn_p (tem
, cfun
->decl
))
4589 || INDIRECT_REF_P (tem
)
4590 || (TREE_CODE (tem
) == MEM_REF
4591 && !(TREE_CODE (TREE_OPERAND (tem
, 0)) == ADDR_EXPR
4593 (TREE_OPERAND (TREE_OPERAND (tem
, 0), 0), cfun
->decl
))))
4595 struct constraint_expr lhs
, *rhsp
;
4597 lhs
= get_function_part_constraint (fi
, fi_uses
);
4598 get_constraint_for_address_of (rhs
, &rhsc
);
4599 FOR_EACH_VEC_ELT (ce_s
, rhsc
, i
, rhsp
)
4600 process_constraint (new_constraint (lhs
, *rhsp
));
4601 VEC_free (ce_s
, heap
, rhsc
);
4605 if (is_gimple_call (t
))
4607 varinfo_t cfi
= NULL
;
4608 tree decl
= gimple_call_fndecl (t
);
4609 struct constraint_expr lhs
, rhs
;
4612 /* For builtins we do not have separate function info. For those
4613 we do not generate escapes for we have to generate clobbers/uses. */
4615 && DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
4616 switch (DECL_FUNCTION_CODE (decl
))
4618 /* The following functions use and clobber memory pointed to
4619 by their arguments. */
4620 case BUILT_IN_STRCPY
:
4621 case BUILT_IN_STRNCPY
:
4622 case BUILT_IN_BCOPY
:
4623 case BUILT_IN_MEMCPY
:
4624 case BUILT_IN_MEMMOVE
:
4625 case BUILT_IN_MEMPCPY
:
4626 case BUILT_IN_STPCPY
:
4627 case BUILT_IN_STPNCPY
:
4628 case BUILT_IN_STRCAT
:
4629 case BUILT_IN_STRNCAT
:
4631 tree dest
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
4632 == BUILT_IN_BCOPY
? 1 : 0));
4633 tree src
= gimple_call_arg (t
, (DECL_FUNCTION_CODE (decl
)
4634 == BUILT_IN_BCOPY
? 0 : 1));
4636 struct constraint_expr
*rhsp
, *lhsp
;
4637 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4638 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4639 FOR_EACH_VEC_ELT (ce_s
, lhsc
, i
, lhsp
)
4640 process_constraint (new_constraint (lhs
, *lhsp
));
4641 VEC_free (ce_s
, heap
, lhsc
);
4642 get_constraint_for_ptr_offset (src
, NULL_TREE
, &rhsc
);
4643 lhs
= get_function_part_constraint (fi
, fi_uses
);
4644 FOR_EACH_VEC_ELT (ce_s
, rhsc
, i
, rhsp
)
4645 process_constraint (new_constraint (lhs
, *rhsp
));
4646 VEC_free (ce_s
, heap
, rhsc
);
4649 /* The following function clobbers memory pointed to by
4651 case BUILT_IN_MEMSET
:
4653 tree dest
= gimple_call_arg (t
, 0);
4656 get_constraint_for_ptr_offset (dest
, NULL_TREE
, &lhsc
);
4657 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4658 FOR_EACH_VEC_ELT (ce_s
, lhsc
, i
, lhsp
)
4659 process_constraint (new_constraint (lhs
, *lhsp
));
4660 VEC_free (ce_s
, heap
, lhsc
);
4663 /* The following functions clobber their second and third
4665 case BUILT_IN_SINCOS
:
4666 case BUILT_IN_SINCOSF
:
4667 case BUILT_IN_SINCOSL
:
4669 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
4670 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
4673 /* The following functions clobber their second argument. */
4674 case BUILT_IN_FREXP
:
4675 case BUILT_IN_FREXPF
:
4676 case BUILT_IN_FREXPL
:
4677 case BUILT_IN_LGAMMA_R
:
4678 case BUILT_IN_LGAMMAF_R
:
4679 case BUILT_IN_LGAMMAL_R
:
4680 case BUILT_IN_GAMMA_R
:
4681 case BUILT_IN_GAMMAF_R
:
4682 case BUILT_IN_GAMMAL_R
:
4684 case BUILT_IN_MODFF
:
4685 case BUILT_IN_MODFL
:
4687 process_ipa_clobber (fi
, gimple_call_arg (t
, 1));
4690 /* The following functions clobber their third argument. */
4691 case BUILT_IN_REMQUO
:
4692 case BUILT_IN_REMQUOF
:
4693 case BUILT_IN_REMQUOL
:
4695 process_ipa_clobber (fi
, gimple_call_arg (t
, 2));
4698 /* The following functions neither read nor clobber memory. */
4701 /* Trampolines are of no interest to us. */
4702 case BUILT_IN_INIT_TRAMPOLINE
:
4703 case BUILT_IN_ADJUST_TRAMPOLINE
:
4705 case BUILT_IN_VA_START
:
4706 case BUILT_IN_VA_END
:
4708 /* printf-style functions may have hooks to set pointers to
4709 point to somewhere into the generated string. Leave them
4710 for a later excercise... */
4712 /* Fallthru to general call handling. */;
4715 /* Parameters passed by value are used. */
4716 lhs
= get_function_part_constraint (fi
, fi_uses
);
4717 for (i
= 0; i
< gimple_call_num_args (t
); i
++)
4719 struct constraint_expr
*rhsp
;
4720 tree arg
= gimple_call_arg (t
, i
);
4722 if (TREE_CODE (arg
) == SSA_NAME
4723 || is_gimple_min_invariant (arg
))
4726 get_constraint_for_address_of (arg
, &rhsc
);
4727 FOR_EACH_VEC_ELT (ce_s
, rhsc
, j
, rhsp
)
4728 process_constraint (new_constraint (lhs
, *rhsp
));
4729 VEC_free (ce_s
, heap
, rhsc
);
4732 /* Build constraints for propagating clobbers/uses along the
4734 cfi
= get_fi_for_callee (t
);
4735 if (cfi
->id
== anything_id
)
4737 if (gimple_vdef (t
))
4738 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
4740 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
4745 /* For callees without function info (that's external functions),
4746 ESCAPED is clobbered and used. */
4747 if (gimple_call_fndecl (t
)
4748 && !cfi
->is_fn_info
)
4752 if (gimple_vdef (t
))
4753 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
4755 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
), escaped_id
);
4757 /* Also honor the call statement use/clobber info. */
4758 if ((vi
= lookup_call_clobber_vi (t
)) != NULL
)
4759 make_copy_constraint (first_vi_for_offset (fi
, fi_clobbers
),
4761 if ((vi
= lookup_call_use_vi (t
)) != NULL
)
4762 make_copy_constraint (first_vi_for_offset (fi
, fi_uses
),
4767 /* Otherwise the caller clobbers and uses what the callee does.
4768 ??? This should use a new complex constraint that filters
4769 local variables of the callee. */
4770 if (gimple_vdef (t
))
4772 lhs
= get_function_part_constraint (fi
, fi_clobbers
);
4773 rhs
= get_function_part_constraint (cfi
, fi_clobbers
);
4774 process_constraint (new_constraint (lhs
, rhs
));
4776 lhs
= get_function_part_constraint (fi
, fi_uses
);
4777 rhs
= get_function_part_constraint (cfi
, fi_uses
);
4778 process_constraint (new_constraint (lhs
, rhs
));
4780 else if (gimple_code (t
) == GIMPLE_ASM
)
4782 /* ??? Ick. We can do better. */
4783 if (gimple_vdef (t
))
4784 make_constraint_from (first_vi_for_offset (fi
, fi_clobbers
),
4786 make_constraint_from (first_vi_for_offset (fi
, fi_uses
),
4790 VEC_free (ce_s
, heap
, rhsc
);
4794 /* Find the first varinfo in the same variable as START that overlaps with
4795 OFFSET. Return NULL if we can't find one. */
4798 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
4800 /* If the offset is outside of the variable, bail out. */
4801 if (offset
>= start
->fullsize
)
4804 /* If we cannot reach offset from start, lookup the first field
4805 and start from there. */
4806 if (start
->offset
> offset
)
4807 start
= lookup_vi_for_tree (start
->decl
);
4811 /* We may not find a variable in the field list with the actual
4812 offset when when we have glommed a structure to a variable.
4813 In that case, however, offset should still be within the size
4815 if (offset
>= start
->offset
4816 && (offset
- start
->offset
) < start
->size
)
4825 /* Find the first varinfo in the same variable as START that overlaps with
4826 OFFSET. If there is no such varinfo the varinfo directly preceding
4827 OFFSET is returned. */
4830 first_or_preceding_vi_for_offset (varinfo_t start
,
4831 unsigned HOST_WIDE_INT offset
)
4833 /* If we cannot reach offset from start, lookup the first field
4834 and start from there. */
4835 if (start
->offset
> offset
)
4836 start
= lookup_vi_for_tree (start
->decl
);
4838 /* We may not find a variable in the field list with the actual
4839 offset when when we have glommed a structure to a variable.
4840 In that case, however, offset should still be within the size
4842 If we got beyond the offset we look for return the field
4843 directly preceding offset which may be the last field. */
4845 && offset
>= start
->offset
4846 && !((offset
- start
->offset
) < start
->size
))
4847 start
= start
->next
;
4853 /* This structure is used during pushing fields onto the fieldstack
4854 to track the offset of the field, since bitpos_of_field gives it
4855 relative to its immediate containing type, and we want it relative
4856 to the ultimate containing object. */
4860 /* Offset from the base of the base containing object to this field. */
4861 HOST_WIDE_INT offset
;
4863 /* Size, in bits, of the field. */
4864 unsigned HOST_WIDE_INT size
;
4866 unsigned has_unknown_size
: 1;
4868 unsigned must_have_pointers
: 1;
4870 unsigned may_have_pointers
: 1;
4872 unsigned only_restrict_pointers
: 1;
4874 typedef struct fieldoff fieldoff_s
;
4876 DEF_VEC_O(fieldoff_s
);
4877 DEF_VEC_ALLOC_O(fieldoff_s
,heap
);
4879 /* qsort comparison function for two fieldoff's PA and PB */
4882 fieldoff_compare (const void *pa
, const void *pb
)
4884 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
4885 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
4886 unsigned HOST_WIDE_INT foasize
, fobsize
;
4888 if (foa
->offset
< fob
->offset
)
4890 else if (foa
->offset
> fob
->offset
)
4893 foasize
= foa
->size
;
4894 fobsize
= fob
->size
;
4895 if (foasize
< fobsize
)
4897 else if (foasize
> fobsize
)
4902 /* Sort a fieldstack according to the field offset and sizes. */
4904 sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
4906 VEC_qsort (fieldoff_s
, fieldstack
, fieldoff_compare
);
4909 /* Return true if V is a tree that we can have subvars for.
4910 Normally, this is any aggregate type. Also complex
4911 types which are not gimple registers can have subvars. */
4914 var_can_have_subvars (const_tree v
)
4916 /* Volatile variables should never have subvars. */
4917 if (TREE_THIS_VOLATILE (v
))
4920 /* Non decls or memory tags can never have subvars. */
4924 /* Aggregates without overlapping fields can have subvars. */
4925 if (TREE_CODE (TREE_TYPE (v
)) == RECORD_TYPE
)
4931 /* Return true if T is a type that does contain pointers. */
4934 type_must_have_pointers (tree type
)
4936 if (POINTER_TYPE_P (type
))
4939 if (TREE_CODE (type
) == ARRAY_TYPE
)
4940 return type_must_have_pointers (TREE_TYPE (type
));
4942 /* A function or method can have pointers as arguments, so track
4943 those separately. */
4944 if (TREE_CODE (type
) == FUNCTION_TYPE
4945 || TREE_CODE (type
) == METHOD_TYPE
)
4952 field_must_have_pointers (tree t
)
4954 return type_must_have_pointers (TREE_TYPE (t
));
4957 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4958 the fields of TYPE onto fieldstack, recording their offsets along
4961 OFFSET is used to keep track of the offset in this entire
4962 structure, rather than just the immediately containing structure.
4963 Returns false if the caller is supposed to handle the field we
4967 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
4968 HOST_WIDE_INT offset
)
4971 bool empty_p
= true;
4973 if (TREE_CODE (type
) != RECORD_TYPE
)
4976 /* If the vector of fields is growing too big, bail out early.
4977 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4979 if (VEC_length (fieldoff_s
, *fieldstack
) > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
4982 for (field
= TYPE_FIELDS (type
); field
; field
= DECL_CHAIN (field
))
4983 if (TREE_CODE (field
) == FIELD_DECL
)
4986 HOST_WIDE_INT foff
= bitpos_of_field (field
);
4988 if (!var_can_have_subvars (field
)
4989 || TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
4990 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
)
4992 else if (!push_fields_onto_fieldstack
4993 (TREE_TYPE (field
), fieldstack
, offset
+ foff
)
4994 && (DECL_SIZE (field
)
4995 && !integer_zerop (DECL_SIZE (field
))))
4996 /* Empty structures may have actual size, like in C++. So
4997 see if we didn't push any subfields and the size is
4998 nonzero, push the field onto the stack. */
5003 fieldoff_s
*pair
= NULL
;
5004 bool has_unknown_size
= false;
5005 bool must_have_pointers_p
;
5007 if (!VEC_empty (fieldoff_s
, *fieldstack
))
5008 pair
= VEC_last (fieldoff_s
, *fieldstack
);
5010 /* If there isn't anything at offset zero, create sth. */
5012 && offset
+ foff
!= 0)
5014 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
5016 pair
->size
= offset
+ foff
;
5017 pair
->has_unknown_size
= false;
5018 pair
->must_have_pointers
= false;
5019 pair
->may_have_pointers
= false;
5020 pair
->only_restrict_pointers
= false;
5023 if (!DECL_SIZE (field
)
5024 || !host_integerp (DECL_SIZE (field
), 1))
5025 has_unknown_size
= true;
5027 /* If adjacent fields do not contain pointers merge them. */
5028 must_have_pointers_p
= field_must_have_pointers (field
);
5030 && !has_unknown_size
5031 && !must_have_pointers_p
5032 && !pair
->must_have_pointers
5033 && !pair
->has_unknown_size
5034 && pair
->offset
+ (HOST_WIDE_INT
)pair
->size
== offset
+ foff
)
5036 pair
->size
+= TREE_INT_CST_LOW (DECL_SIZE (field
));
5040 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
5041 pair
->offset
= offset
+ foff
;
5042 pair
->has_unknown_size
= has_unknown_size
;
5043 if (!has_unknown_size
)
5044 pair
->size
= TREE_INT_CST_LOW (DECL_SIZE (field
));
5047 pair
->must_have_pointers
= must_have_pointers_p
;
5048 pair
->may_have_pointers
= true;
5049 pair
->only_restrict_pointers
5050 = (!has_unknown_size
5051 && POINTER_TYPE_P (TREE_TYPE (field
))
5052 && TYPE_RESTRICT (TREE_TYPE (field
)));
5062 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5063 if it is a varargs function. */
5066 count_num_arguments (tree decl
, bool *is_varargs
)
5068 unsigned int num
= 0;
5071 /* Capture named arguments for K&R functions. They do not
5072 have a prototype and thus no TYPE_ARG_TYPES. */
5073 for (t
= DECL_ARGUMENTS (decl
); t
; t
= DECL_CHAIN (t
))
5076 /* Check if the function has variadic arguments. */
5077 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
)); t
; t
= TREE_CHAIN (t
))
5078 if (TREE_VALUE (t
) == void_type_node
)
5086 /* Creation function node for DECL, using NAME, and return the index
5087 of the variable we've created for the function. */
5090 create_function_info_for (tree decl
, const char *name
)
5092 struct function
*fn
= DECL_STRUCT_FUNCTION (decl
);
5093 varinfo_t vi
, prev_vi
;
5096 bool is_varargs
= false;
5097 unsigned int num_args
= count_num_arguments (decl
, &is_varargs
);
5099 /* Create the variable info. */
5101 vi
= new_var_info (decl
, name
);
5104 vi
->fullsize
= fi_parm_base
+ num_args
;
5106 vi
->may_have_pointers
= false;
5109 insert_vi_for_tree (vi
->decl
, vi
);
5113 /* Create a variable for things the function clobbers and one for
5114 things the function uses. */
5116 varinfo_t clobbervi
, usevi
;
5117 const char *newname
;
5120 asprintf (&tempname
, "%s.clobber", name
);
5121 newname
= ggc_strdup (tempname
);
5124 clobbervi
= new_var_info (NULL
, newname
);
5125 clobbervi
->offset
= fi_clobbers
;
5126 clobbervi
->size
= 1;
5127 clobbervi
->fullsize
= vi
->fullsize
;
5128 clobbervi
->is_full_var
= true;
5129 clobbervi
->is_global_var
= false;
5130 gcc_assert (prev_vi
->offset
< clobbervi
->offset
);
5131 prev_vi
->next
= clobbervi
;
5132 prev_vi
= clobbervi
;
5134 asprintf (&tempname
, "%s.use", name
);
5135 newname
= ggc_strdup (tempname
);
5138 usevi
= new_var_info (NULL
, newname
);
5139 usevi
->offset
= fi_uses
;
5141 usevi
->fullsize
= vi
->fullsize
;
5142 usevi
->is_full_var
= true;
5143 usevi
->is_global_var
= false;
5144 gcc_assert (prev_vi
->offset
< usevi
->offset
);
5145 prev_vi
->next
= usevi
;
5149 /* And one for the static chain. */
5150 if (fn
->static_chain_decl
!= NULL_TREE
)
5153 const char *newname
;
5156 asprintf (&tempname
, "%s.chain", name
);
5157 newname
= ggc_strdup (tempname
);
5160 chainvi
= new_var_info (fn
->static_chain_decl
, newname
);
5161 chainvi
->offset
= fi_static_chain
;
5163 chainvi
->fullsize
= vi
->fullsize
;
5164 chainvi
->is_full_var
= true;
5165 chainvi
->is_global_var
= false;
5166 gcc_assert (prev_vi
->offset
< chainvi
->offset
);
5167 prev_vi
->next
= chainvi
;
5169 insert_vi_for_tree (fn
->static_chain_decl
, chainvi
);
5172 /* Create a variable for the return var. */
5173 if (DECL_RESULT (decl
) != NULL
5174 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
5177 const char *newname
;
5179 tree resultdecl
= decl
;
5181 if (DECL_RESULT (decl
))
5182 resultdecl
= DECL_RESULT (decl
);
5184 asprintf (&tempname
, "%s.result", name
);
5185 newname
= ggc_strdup (tempname
);
5188 resultvi
= new_var_info (resultdecl
, newname
);
5189 resultvi
->offset
= fi_result
;
5191 resultvi
->fullsize
= vi
->fullsize
;
5192 resultvi
->is_full_var
= true;
5193 if (DECL_RESULT (decl
))
5194 resultvi
->may_have_pointers
= true;
5195 gcc_assert (prev_vi
->offset
< resultvi
->offset
);
5196 prev_vi
->next
= resultvi
;
5198 if (DECL_RESULT (decl
))
5199 insert_vi_for_tree (DECL_RESULT (decl
), resultvi
);
5202 /* Set up variables for each argument. */
5203 arg
= DECL_ARGUMENTS (decl
);
5204 for (i
= 0; i
< num_args
; i
++)
5207 const char *newname
;
5209 tree argdecl
= decl
;
5214 asprintf (&tempname
, "%s.arg%d", name
, i
);
5215 newname
= ggc_strdup (tempname
);
5218 argvi
= new_var_info (argdecl
, newname
);
5219 argvi
->offset
= fi_parm_base
+ i
;
5221 argvi
->is_full_var
= true;
5222 argvi
->fullsize
= vi
->fullsize
;
5224 argvi
->may_have_pointers
= true;
5225 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5226 prev_vi
->next
= argvi
;
5230 insert_vi_for_tree (arg
, argvi
);
5231 arg
= DECL_CHAIN (arg
);
5235 /* Add one representative for all further args. */
5239 const char *newname
;
5243 asprintf (&tempname
, "%s.varargs", name
);
5244 newname
= ggc_strdup (tempname
);
5247 /* We need sth that can be pointed to for va_start. */
5248 decl
= build_fake_var_decl (ptr_type_node
);
5250 argvi
= new_var_info (decl
, newname
);
5251 argvi
->offset
= fi_parm_base
+ num_args
;
5253 argvi
->is_full_var
= true;
5254 argvi
->is_heap_var
= true;
5255 argvi
->fullsize
= vi
->fullsize
;
5256 gcc_assert (prev_vi
->offset
< argvi
->offset
);
5257 prev_vi
->next
= argvi
;
5265 /* Return true if FIELDSTACK contains fields that overlap.
5266 FIELDSTACK is assumed to be sorted by offset. */
5269 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
5271 fieldoff_s
*fo
= NULL
;
5273 HOST_WIDE_INT lastoffset
= -1;
5275 FOR_EACH_VEC_ELT (fieldoff_s
, fieldstack
, i
, fo
)
5277 if (fo
->offset
== lastoffset
)
5279 lastoffset
= fo
->offset
;
5284 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5285 This will also create any varinfo structures necessary for fields
5289 create_variable_info_for_1 (tree decl
, const char *name
)
5291 varinfo_t vi
, newvi
;
5292 tree decl_type
= TREE_TYPE (decl
);
5293 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decl_type
);
5294 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
5299 || !host_integerp (declsize
, 1))
5301 vi
= new_var_info (decl
, name
);
5305 vi
->is_unknown_size_var
= true;
5306 vi
->is_full_var
= true;
5307 vi
->may_have_pointers
= true;
5311 /* Collect field information. */
5312 if (use_field_sensitive
5313 && var_can_have_subvars (decl
)
5314 /* ??? Force us to not use subfields for global initializers
5315 in IPA mode. Else we'd have to parse arbitrary initializers. */
5317 && is_global_var (decl
)
5318 && DECL_INITIAL (decl
)))
5320 fieldoff_s
*fo
= NULL
;
5321 bool notokay
= false;
5324 push_fields_onto_fieldstack (decl_type
, &fieldstack
, 0);
5326 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
5327 if (fo
->has_unknown_size
5334 /* We can't sort them if we have a field with a variable sized type,
5335 which will make notokay = true. In that case, we are going to return
5336 without creating varinfos for the fields anyway, so sorting them is a
5340 sort_fieldstack (fieldstack
);
5341 /* Due to some C++ FE issues, like PR 22488, we might end up
5342 what appear to be overlapping fields even though they,
5343 in reality, do not overlap. Until the C++ FE is fixed,
5344 we will simply disable field-sensitivity for these cases. */
5345 notokay
= check_for_overlaps (fieldstack
);
5349 VEC_free (fieldoff_s
, heap
, fieldstack
);
5352 /* If we didn't end up collecting sub-variables create a full
5353 variable for the decl. */
5354 if (VEC_length (fieldoff_s
, fieldstack
) <= 1
5355 || VEC_length (fieldoff_s
, fieldstack
) > MAX_FIELDS_FOR_FIELD_SENSITIVE
)
5357 vi
= new_var_info (decl
, name
);
5359 vi
->may_have_pointers
= true;
5360 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
5361 vi
->size
= vi
->fullsize
;
5362 vi
->is_full_var
= true;
5363 VEC_free (fieldoff_s
, heap
, fieldstack
);
5367 vi
= new_var_info (decl
, name
);
5368 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
5369 for (i
= 0, newvi
= vi
;
5370 VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
5371 ++i
, newvi
= newvi
->next
)
5373 const char *newname
= "NULL";
5378 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
5379 "+" HOST_WIDE_INT_PRINT_DEC
, name
, fo
->offset
, fo
->size
);
5380 newname
= ggc_strdup (tempname
);
5383 newvi
->name
= newname
;
5384 newvi
->offset
= fo
->offset
;
5385 newvi
->size
= fo
->size
;
5386 newvi
->fullsize
= vi
->fullsize
;
5387 newvi
->may_have_pointers
= fo
->may_have_pointers
;
5388 newvi
->only_restrict_pointers
= fo
->only_restrict_pointers
;
5389 if (i
+ 1 < VEC_length (fieldoff_s
, fieldstack
))
5390 newvi
->next
= new_var_info (decl
, name
);
5393 VEC_free (fieldoff_s
, heap
, fieldstack
);
5399 create_variable_info_for (tree decl
, const char *name
)
5401 varinfo_t vi
= create_variable_info_for_1 (decl
, name
);
5402 unsigned int id
= vi
->id
;
5404 insert_vi_for_tree (decl
, vi
);
5406 /* Create initial constraints for globals. */
5407 for (; vi
; vi
= vi
->next
)
5409 if (!vi
->may_have_pointers
5410 || !vi
->is_global_var
)
5413 /* Mark global restrict qualified pointers. */
5414 if ((POINTER_TYPE_P (TREE_TYPE (decl
))
5415 && TYPE_RESTRICT (TREE_TYPE (decl
)))
5416 || vi
->only_restrict_pointers
)
5417 make_constraint_from_restrict (vi
, "GLOBAL_RESTRICT");
5419 /* For escaped variables initialize them from nonlocal. */
5421 || DECL_EXTERNAL (decl
) || TREE_PUBLIC (decl
))
5422 make_copy_constraint (vi
, nonlocal_id
);
5424 /* If this is a global variable with an initializer and we are in
5425 IPA mode generate constraints for it. In non-IPA mode
5426 the initializer from nonlocal is all we need. */
5428 && DECL_INITIAL (decl
))
5430 VEC (ce_s
, heap
) *rhsc
= NULL
;
5431 struct constraint_expr lhs
, *rhsp
;
5433 get_constraint_for_rhs (DECL_INITIAL (decl
), &rhsc
);
5437 FOR_EACH_VEC_ELT (ce_s
, rhsc
, i
, rhsp
)
5438 process_constraint (new_constraint (lhs
, *rhsp
));
5439 /* If this is a variable that escapes from the unit
5440 the initializer escapes as well. */
5441 if (DECL_EXTERNAL (decl
) || TREE_PUBLIC (decl
))
5443 lhs
.var
= escaped_id
;
5446 FOR_EACH_VEC_ELT (ce_s
, rhsc
, i
, rhsp
)
5447 process_constraint (new_constraint (lhs
, *rhsp
));
5449 VEC_free (ce_s
, heap
, rhsc
);
5456 /* Print out the points-to solution for VAR to FILE. */
5459 dump_solution_for_var (FILE *file
, unsigned int var
)
5461 varinfo_t vi
= get_varinfo (var
);
5465 /* Dump the solution for unified vars anyway, this avoids difficulties
5466 in scanning dumps in the testsuite. */
5467 fprintf (file
, "%s = { ", vi
->name
);
5468 vi
= get_varinfo (find (var
));
5469 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
5470 fprintf (file
, "%s ", get_varinfo (i
)->name
);
5471 fprintf (file
, "}");
5473 /* But note when the variable was unified. */
5475 fprintf (file
, " same as %s", vi
->name
);
5477 fprintf (file
, "\n");
5480 /* Print the points-to solution for VAR to stdout. */
5483 debug_solution_for_var (unsigned int var
)
5485 dump_solution_for_var (stdout
, var
);
5488 /* Create varinfo structures for all of the variables in the
5489 function for intraprocedural mode. */
5492 intra_create_variable_infos (void)
5496 /* For each incoming pointer argument arg, create the constraint ARG
5497 = NONLOCAL or a dummy variable if it is a restrict qualified
5498 passed-by-reference argument. */
5499 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= DECL_CHAIN (t
))
5503 /* For restrict qualified pointers to objects passed by
5504 reference build a real representative for the pointed-to object. */
5505 if (DECL_BY_REFERENCE (t
)
5506 && POINTER_TYPE_P (TREE_TYPE (t
))
5507 && TYPE_RESTRICT (TREE_TYPE (t
)))
5509 struct constraint_expr lhsc
, rhsc
;
5511 tree heapvar
= build_fake_var_decl (TREE_TYPE (TREE_TYPE (t
)));
5512 DECL_EXTERNAL (heapvar
) = 1;
5513 vi
= get_varinfo (create_variable_info_for (heapvar
, "PARM_NOALIAS"));
5514 lhsc
.var
= get_vi_for_tree (t
)->id
;
5518 rhsc
.type
= ADDRESSOF
;
5520 process_constraint (new_constraint (lhsc
, rhsc
));
5521 vi
->is_restrict_var
= 1;
5525 for (p
= get_vi_for_tree (t
); p
; p
= p
->next
)
5527 if (p
->may_have_pointers
)
5528 make_constraint_from (p
, nonlocal_id
);
5529 if (p
->only_restrict_pointers
)
5530 make_constraint_from_restrict (p
, "PARM_RESTRICT");
5532 if (POINTER_TYPE_P (TREE_TYPE (t
))
5533 && TYPE_RESTRICT (TREE_TYPE (t
)))
5534 make_constraint_from_restrict (get_vi_for_tree (t
), "PARM_RESTRICT");
5537 /* Add a constraint for a result decl that is passed by reference. */
5538 if (DECL_RESULT (cfun
->decl
)
5539 && DECL_BY_REFERENCE (DECL_RESULT (cfun
->decl
)))
5541 varinfo_t p
, result_vi
= get_vi_for_tree (DECL_RESULT (cfun
->decl
));
5543 for (p
= result_vi
; p
; p
= p
->next
)
5544 make_constraint_from (p
, nonlocal_id
);
5547 /* Add a constraint for the incoming static chain parameter. */
5548 if (cfun
->static_chain_decl
!= NULL_TREE
)
5550 varinfo_t p
, chain_vi
= get_vi_for_tree (cfun
->static_chain_decl
);
5552 for (p
= chain_vi
; p
; p
= p
->next
)
5553 make_constraint_from (p
, nonlocal_id
);
5557 /* Structure used to put solution bitmaps in a hashtable so they can
5558 be shared among variables with the same points-to set. */
5560 typedef struct shared_bitmap_info
5564 } *shared_bitmap_info_t
;
5565 typedef const struct shared_bitmap_info
*const_shared_bitmap_info_t
;
5567 static htab_t shared_bitmap_table
;
5569 /* Hash function for a shared_bitmap_info_t */
5572 shared_bitmap_hash (const void *p
)
5574 const_shared_bitmap_info_t
const bi
= (const_shared_bitmap_info_t
) p
;
5575 return bi
->hashcode
;
5578 /* Equality function for two shared_bitmap_info_t's. */
5581 shared_bitmap_eq (const void *p1
, const void *p2
)
5583 const_shared_bitmap_info_t
const sbi1
= (const_shared_bitmap_info_t
) p1
;
5584 const_shared_bitmap_info_t
const sbi2
= (const_shared_bitmap_info_t
) p2
;
5585 return bitmap_equal_p (sbi1
->pt_vars
, sbi2
->pt_vars
);
5588 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
5589 existing instance if there is one, NULL otherwise. */
5592 shared_bitmap_lookup (bitmap pt_vars
)
5595 struct shared_bitmap_info sbi
;
5597 sbi
.pt_vars
= pt_vars
;
5598 sbi
.hashcode
= bitmap_hash (pt_vars
);
5600 slot
= htab_find_slot_with_hash (shared_bitmap_table
, &sbi
,
5601 sbi
.hashcode
, NO_INSERT
);
5605 return ((shared_bitmap_info_t
) *slot
)->pt_vars
;
5609 /* Add a bitmap to the shared bitmap hashtable. */
5612 shared_bitmap_add (bitmap pt_vars
)
5615 shared_bitmap_info_t sbi
= XNEW (struct shared_bitmap_info
);
5617 sbi
->pt_vars
= pt_vars
;
5618 sbi
->hashcode
= bitmap_hash (pt_vars
);
5620 slot
= htab_find_slot_with_hash (shared_bitmap_table
, sbi
,
5621 sbi
->hashcode
, INSERT
);
5622 gcc_assert (!*slot
);
5623 *slot
= (void *) sbi
;
5627 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
5630 set_uids_in_ptset (bitmap into
, bitmap from
, struct pt_solution
*pt
)
5635 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
5637 varinfo_t vi
= get_varinfo (i
);
5639 /* The only artificial variables that are allowed in a may-alias
5640 set are heap variables. */
5641 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
5644 if (TREE_CODE (vi
->decl
) == VAR_DECL
5645 || TREE_CODE (vi
->decl
) == PARM_DECL
5646 || TREE_CODE (vi
->decl
) == RESULT_DECL
)
5648 /* If we are in IPA mode we will not recompute points-to
5649 sets after inlining so make sure they stay valid. */
5651 && !DECL_PT_UID_SET_P (vi
->decl
))
5652 SET_DECL_PT_UID (vi
->decl
, DECL_UID (vi
->decl
));
5654 /* Add the decl to the points-to set. Note that the points-to
5655 set contains global variables. */
5656 bitmap_set_bit (into
, DECL_PT_UID (vi
->decl
));
5657 if (vi
->is_global_var
)
5658 pt
->vars_contains_global
= true;
5664 /* Compute the points-to solution *PT for the variable VI. */
5667 find_what_var_points_to (varinfo_t orig_vi
, struct pt_solution
*pt
)
5671 bitmap finished_solution
;
5675 memset (pt
, 0, sizeof (struct pt_solution
));
5677 /* This variable may have been collapsed, let's get the real
5679 vi
= get_varinfo (find (orig_vi
->id
));
5681 /* Translate artificial variables into SSA_NAME_PTR_INFO
5683 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
5685 varinfo_t vi
= get_varinfo (i
);
5687 if (vi
->is_artificial_var
)
5689 if (vi
->id
== nothing_id
)
5691 else if (vi
->id
== escaped_id
)
5694 pt
->ipa_escaped
= 1;
5698 else if (vi
->id
== nonlocal_id
)
5700 else if (vi
->is_heap_var
)
5701 /* We represent heapvars in the points-to set properly. */
5703 else if (vi
->id
== readonly_id
)
5706 else if (vi
->id
== anything_id
5707 || vi
->id
== integer_id
)
5710 if (vi
->is_restrict_var
)
5711 pt
->vars_contains_restrict
= true;
5714 /* Instead of doing extra work, simply do not create
5715 elaborate points-to information for pt_anything pointers. */
5717 && (orig_vi
->is_artificial_var
5718 || !pt
->vars_contains_restrict
))
5721 /* Share the final set of variables when possible. */
5722 finished_solution
= BITMAP_GGC_ALLOC ();
5723 stats
.points_to_sets_created
++;
5725 set_uids_in_ptset (finished_solution
, vi
->solution
, pt
);
5726 result
= shared_bitmap_lookup (finished_solution
);
5729 shared_bitmap_add (finished_solution
);
5730 pt
->vars
= finished_solution
;
5735 bitmap_clear (finished_solution
);
5739 /* Given a pointer variable P, fill in its points-to set. */
5742 find_what_p_points_to (tree p
)
5744 struct ptr_info_def
*pi
;
5748 /* For parameters, get at the points-to set for the actual parm
5750 if (TREE_CODE (p
) == SSA_NAME
5751 && (TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
5752 || TREE_CODE (SSA_NAME_VAR (p
)) == RESULT_DECL
)
5753 && SSA_NAME_IS_DEFAULT_DEF (p
))
5754 lookup_p
= SSA_NAME_VAR (p
);
5756 vi
= lookup_vi_for_tree (lookup_p
);
5760 pi
= get_ptr_info (p
);
5761 find_what_var_points_to (vi
, &pi
->pt
);
5765 /* Query statistics for points-to solutions. */
5768 unsigned HOST_WIDE_INT pt_solution_includes_may_alias
;
5769 unsigned HOST_WIDE_INT pt_solution_includes_no_alias
;
5770 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias
;
5771 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias
;
5775 dump_pta_stats (FILE *s
)
5777 fprintf (s
, "\nPTA query stats:\n");
5778 fprintf (s
, " pt_solution_includes: "
5779 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
5780 HOST_WIDE_INT_PRINT_DEC
" queries\n",
5781 pta_stats
.pt_solution_includes_no_alias
,
5782 pta_stats
.pt_solution_includes_no_alias
5783 + pta_stats
.pt_solution_includes_may_alias
);
5784 fprintf (s
, " pt_solutions_intersect: "
5785 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
5786 HOST_WIDE_INT_PRINT_DEC
" queries\n",
5787 pta_stats
.pt_solutions_intersect_no_alias
,
5788 pta_stats
.pt_solutions_intersect_no_alias
5789 + pta_stats
.pt_solutions_intersect_may_alias
);
5793 /* Reset the points-to solution *PT to a conservative default
5794 (point to anything). */
5797 pt_solution_reset (struct pt_solution
*pt
)
5799 memset (pt
, 0, sizeof (struct pt_solution
));
5800 pt
->anything
= true;
5803 /* Set the points-to solution *PT to point only to the variables
5804 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
5805 global variables and VARS_CONTAINS_RESTRICT specifies whether
5806 it contains restrict tag variables. */
5809 pt_solution_set (struct pt_solution
*pt
, bitmap vars
,
5810 bool vars_contains_global
, bool vars_contains_restrict
)
5812 memset (pt
, 0, sizeof (struct pt_solution
));
5814 pt
->vars_contains_global
= vars_contains_global
;
5815 pt
->vars_contains_restrict
= vars_contains_restrict
;
5818 /* Set the points-to solution *PT to point only to the variable VAR. */
5821 pt_solution_set_var (struct pt_solution
*pt
, tree var
)
5823 memset (pt
, 0, sizeof (struct pt_solution
));
5824 pt
->vars
= BITMAP_GGC_ALLOC ();
5825 bitmap_set_bit (pt
->vars
, DECL_PT_UID (var
));
5826 pt
->vars_contains_global
= is_global_var (var
);
5829 /* Computes the union of the points-to solutions *DEST and *SRC and
5830 stores the result in *DEST. This changes the points-to bitmap
5831 of *DEST and thus may not be used if that might be shared.
5832 The points-to bitmap of *SRC and *DEST will not be shared after
5833 this function if they were not before. */
5836 pt_solution_ior_into (struct pt_solution
*dest
, struct pt_solution
*src
)
5838 dest
->anything
|= src
->anything
;
5841 pt_solution_reset (dest
);
5845 dest
->nonlocal
|= src
->nonlocal
;
5846 dest
->escaped
|= src
->escaped
;
5847 dest
->ipa_escaped
|= src
->ipa_escaped
;
5848 dest
->null
|= src
->null
;
5849 dest
->vars_contains_global
|= src
->vars_contains_global
;
5850 dest
->vars_contains_restrict
|= src
->vars_contains_restrict
;
5855 dest
->vars
= BITMAP_GGC_ALLOC ();
5856 bitmap_ior_into (dest
->vars
, src
->vars
);
5859 /* Return true if the points-to solution *PT is empty. */
5862 pt_solution_empty_p (struct pt_solution
*pt
)
5869 && !bitmap_empty_p (pt
->vars
))
5872 /* If the solution includes ESCAPED, check if that is empty. */
5874 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
5877 /* If the solution includes ESCAPED, check if that is empty. */
5879 && !pt_solution_empty_p (&ipa_escaped_pt
))
5885 /* Return true if the points-to solution *PT includes global memory. */
5888 pt_solution_includes_global (struct pt_solution
*pt
)
5892 || pt
->vars_contains_global
)
5896 return pt_solution_includes_global (&cfun
->gimple_df
->escaped
);
5898 if (pt
->ipa_escaped
)
5899 return pt_solution_includes_global (&ipa_escaped_pt
);
5901 /* ??? This predicate is not correct for the IPA-PTA solution
5902 as we do not properly distinguish between unit escape points
5903 and global variables. */
5904 if (cfun
->gimple_df
->ipa_pta
)
5910 /* Return true if the points-to solution *PT includes the variable
5911 declaration DECL. */
5914 pt_solution_includes_1 (struct pt_solution
*pt
, const_tree decl
)
5920 && is_global_var (decl
))
5924 && bitmap_bit_p (pt
->vars
, DECL_PT_UID (decl
)))
5927 /* If the solution includes ESCAPED, check it. */
5929 && pt_solution_includes_1 (&cfun
->gimple_df
->escaped
, decl
))
5932 /* If the solution includes ESCAPED, check it. */
5934 && pt_solution_includes_1 (&ipa_escaped_pt
, decl
))
5941 pt_solution_includes (struct pt_solution
*pt
, const_tree decl
)
5943 bool res
= pt_solution_includes_1 (pt
, decl
);
5945 ++pta_stats
.pt_solution_includes_may_alias
;
5947 ++pta_stats
.pt_solution_includes_no_alias
;
5951 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
5955 pt_solutions_intersect_1 (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
5957 if (pt1
->anything
|| pt2
->anything
)
5960 /* If either points to unknown global memory and the other points to
5961 any global memory they alias. */
5964 || pt2
->vars_contains_global
))
5966 && pt1
->vars_contains_global
))
5969 /* Check the escaped solution if required. */
5970 if ((pt1
->escaped
|| pt2
->escaped
)
5971 && !pt_solution_empty_p (&cfun
->gimple_df
->escaped
))
5973 /* If both point to escaped memory and that solution
5974 is not empty they alias. */
5975 if (pt1
->escaped
&& pt2
->escaped
)
5978 /* If either points to escaped memory see if the escaped solution
5979 intersects with the other. */
5981 && pt_solutions_intersect_1 (&cfun
->gimple_df
->escaped
, pt2
))
5983 && pt_solutions_intersect_1 (&cfun
->gimple_df
->escaped
, pt1
)))
5987 /* Check the escaped solution if required.
5988 ??? Do we need to check the local against the IPA escaped sets? */
5989 if ((pt1
->ipa_escaped
|| pt2
->ipa_escaped
)
5990 && !pt_solution_empty_p (&ipa_escaped_pt
))
5992 /* If both point to escaped memory and that solution
5993 is not empty they alias. */
5994 if (pt1
->ipa_escaped
&& pt2
->ipa_escaped
)
5997 /* If either points to escaped memory see if the escaped solution
5998 intersects with the other. */
5999 if ((pt1
->ipa_escaped
6000 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt2
))
6001 || (pt2
->ipa_escaped
6002 && pt_solutions_intersect_1 (&ipa_escaped_pt
, pt1
)))
6006 /* Now both pointers alias if their points-to solution intersects. */
6009 && bitmap_intersect_p (pt1
->vars
, pt2
->vars
));
6013 pt_solutions_intersect (struct pt_solution
*pt1
, struct pt_solution
*pt2
)
6015 bool res
= pt_solutions_intersect_1 (pt1
, pt2
);
6017 ++pta_stats
.pt_solutions_intersect_may_alias
;
6019 ++pta_stats
.pt_solutions_intersect_no_alias
;
6023 /* Return true if both points-to solutions PT1 and PT2 for two restrict
6024 qualified pointers are possibly based on the same pointer. */
6027 pt_solutions_same_restrict_base (struct pt_solution
*pt1
,
6028 struct pt_solution
*pt2
)
6030 /* If we deal with points-to solutions of two restrict qualified
6031 pointers solely rely on the pointed-to variable bitmap intersection.
6032 For two pointers that are based on each other the bitmaps will
6034 if (pt1
->vars_contains_restrict
6035 && pt2
->vars_contains_restrict
)
6037 gcc_assert (pt1
->vars
&& pt2
->vars
);
6038 return bitmap_intersect_p (pt1
->vars
, pt2
->vars
);
6045 /* Dump points-to information to OUTFILE. */
6048 dump_sa_points_to_info (FILE *outfile
)
6052 fprintf (outfile
, "\nPoints-to sets\n\n");
6054 if (dump_flags
& TDF_STATS
)
6056 fprintf (outfile
, "Stats:\n");
6057 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
6058 fprintf (outfile
, "Non-pointer vars: %d\n",
6059 stats
.nonpointer_vars
);
6060 fprintf (outfile
, "Statically unified vars: %d\n",
6061 stats
.unified_vars_static
);
6062 fprintf (outfile
, "Dynamically unified vars: %d\n",
6063 stats
.unified_vars_dynamic
);
6064 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
6065 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
6066 fprintf (outfile
, "Number of implicit edges: %d\n",
6067 stats
.num_implicit_edges
);
6070 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
6072 varinfo_t vi
= get_varinfo (i
);
6073 if (!vi
->may_have_pointers
)
6075 dump_solution_for_var (outfile
, i
);
6080 /* Debug points-to information to stderr. */
6083 debug_sa_points_to_info (void)
6085 dump_sa_points_to_info (stderr
);
6089 /* Initialize the always-existing constraint variables for NULL
6090 ANYTHING, READONLY, and INTEGER */
6093 init_base_vars (void)
6095 struct constraint_expr lhs
, rhs
;
6096 varinfo_t var_anything
;
6097 varinfo_t var_nothing
;
6098 varinfo_t var_readonly
;
6099 varinfo_t var_escaped
;
6100 varinfo_t var_nonlocal
;
6101 varinfo_t var_storedanything
;
6102 varinfo_t var_integer
;
6104 /* Create the NULL variable, used to represent that a variable points
6106 var_nothing
= new_var_info (NULL_TREE
, "NULL");
6107 gcc_assert (var_nothing
->id
== nothing_id
);
6108 var_nothing
->is_artificial_var
= 1;
6109 var_nothing
->offset
= 0;
6110 var_nothing
->size
= ~0;
6111 var_nothing
->fullsize
= ~0;
6112 var_nothing
->is_special_var
= 1;
6113 var_nothing
->may_have_pointers
= 0;
6114 var_nothing
->is_global_var
= 0;
6116 /* Create the ANYTHING variable, used to represent that a variable
6117 points to some unknown piece of memory. */
6118 var_anything
= new_var_info (NULL_TREE
, "ANYTHING");
6119 gcc_assert (var_anything
->id
== anything_id
);
6120 var_anything
->is_artificial_var
= 1;
6121 var_anything
->size
= ~0;
6122 var_anything
->offset
= 0;
6123 var_anything
->next
= NULL
;
6124 var_anything
->fullsize
= ~0;
6125 var_anything
->is_special_var
= 1;
6127 /* Anything points to anything. This makes deref constraints just
6128 work in the presence of linked list and other p = *p type loops,
6129 by saying that *ANYTHING = ANYTHING. */
6131 lhs
.var
= anything_id
;
6133 rhs
.type
= ADDRESSOF
;
6134 rhs
.var
= anything_id
;
6137 /* This specifically does not use process_constraint because
6138 process_constraint ignores all anything = anything constraints, since all
6139 but this one are redundant. */
6140 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
6142 /* Create the READONLY variable, used to represent that a variable
6143 points to readonly memory. */
6144 var_readonly
= new_var_info (NULL_TREE
, "READONLY");
6145 gcc_assert (var_readonly
->id
== readonly_id
);
6146 var_readonly
->is_artificial_var
= 1;
6147 var_readonly
->offset
= 0;
6148 var_readonly
->size
= ~0;
6149 var_readonly
->fullsize
= ~0;
6150 var_readonly
->next
= NULL
;
6151 var_readonly
->is_special_var
= 1;
6153 /* readonly memory points to anything, in order to make deref
6154 easier. In reality, it points to anything the particular
6155 readonly variable can point to, but we don't track this
6158 lhs
.var
= readonly_id
;
6160 rhs
.type
= ADDRESSOF
;
6161 rhs
.var
= readonly_id
; /* FIXME */
6163 process_constraint (new_constraint (lhs
, rhs
));
6165 /* Create the ESCAPED variable, used to represent the set of escaped
6167 var_escaped
= new_var_info (NULL_TREE
, "ESCAPED");
6168 gcc_assert (var_escaped
->id
== escaped_id
);
6169 var_escaped
->is_artificial_var
= 1;
6170 var_escaped
->offset
= 0;
6171 var_escaped
->size
= ~0;
6172 var_escaped
->fullsize
= ~0;
6173 var_escaped
->is_special_var
= 0;
6175 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6177 var_nonlocal
= new_var_info (NULL_TREE
, "NONLOCAL");
6178 gcc_assert (var_nonlocal
->id
== nonlocal_id
);
6179 var_nonlocal
->is_artificial_var
= 1;
6180 var_nonlocal
->offset
= 0;
6181 var_nonlocal
->size
= ~0;
6182 var_nonlocal
->fullsize
= ~0;
6183 var_nonlocal
->is_special_var
= 1;
6185 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6187 lhs
.var
= escaped_id
;
6190 rhs
.var
= escaped_id
;
6192 process_constraint (new_constraint (lhs
, rhs
));
6194 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6195 whole variable escapes. */
6197 lhs
.var
= escaped_id
;
6200 rhs
.var
= escaped_id
;
6201 rhs
.offset
= UNKNOWN_OFFSET
;
6202 process_constraint (new_constraint (lhs
, rhs
));
6204 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6205 everything pointed to by escaped points to what global memory can
6208 lhs
.var
= escaped_id
;
6211 rhs
.var
= nonlocal_id
;
6213 process_constraint (new_constraint (lhs
, rhs
));
6215 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6216 global memory may point to global memory and escaped memory. */
6218 lhs
.var
= nonlocal_id
;
6220 rhs
.type
= ADDRESSOF
;
6221 rhs
.var
= nonlocal_id
;
6223 process_constraint (new_constraint (lhs
, rhs
));
6224 rhs
.type
= ADDRESSOF
;
6225 rhs
.var
= escaped_id
;
6227 process_constraint (new_constraint (lhs
, rhs
));
6229 /* Create the STOREDANYTHING variable, used to represent the set of
6230 variables stored to *ANYTHING. */
6231 var_storedanything
= new_var_info (NULL_TREE
, "STOREDANYTHING");
6232 gcc_assert (var_storedanything
->id
== storedanything_id
);
6233 var_storedanything
->is_artificial_var
= 1;
6234 var_storedanything
->offset
= 0;
6235 var_storedanything
->size
= ~0;
6236 var_storedanything
->fullsize
= ~0;
6237 var_storedanything
->is_special_var
= 0;
6239 /* Create the INTEGER variable, used to represent that a variable points
6240 to what an INTEGER "points to". */
6241 var_integer
= new_var_info (NULL_TREE
, "INTEGER");
6242 gcc_assert (var_integer
->id
== integer_id
);
6243 var_integer
->is_artificial_var
= 1;
6244 var_integer
->size
= ~0;
6245 var_integer
->fullsize
= ~0;
6246 var_integer
->offset
= 0;
6247 var_integer
->next
= NULL
;
6248 var_integer
->is_special_var
= 1;
6250 /* INTEGER = ANYTHING, because we don't know where a dereference of
6251 a random integer will point to. */
6253 lhs
.var
= integer_id
;
6255 rhs
.type
= ADDRESSOF
;
6256 rhs
.var
= anything_id
;
6258 process_constraint (new_constraint (lhs
, rhs
));
6261 /* Initialize things necessary to perform PTA */
6264 init_alias_vars (void)
6266 use_field_sensitive
= (MAX_FIELDS_FOR_FIELD_SENSITIVE
> 1);
6268 bitmap_obstack_initialize (&pta_obstack
);
6269 bitmap_obstack_initialize (&oldpta_obstack
);
6270 bitmap_obstack_initialize (&predbitmap_obstack
);
6272 constraint_pool
= create_alloc_pool ("Constraint pool",
6273 sizeof (struct constraint
), 30);
6274 variable_info_pool
= create_alloc_pool ("Variable info pool",
6275 sizeof (struct variable_info
), 30);
6276 constraints
= VEC_alloc (constraint_t
, heap
, 8);
6277 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
6278 vi_for_tree
= pointer_map_create ();
6279 call_stmt_vars
= pointer_map_create ();
6281 memset (&stats
, 0, sizeof (stats
));
6282 shared_bitmap_table
= htab_create (511, shared_bitmap_hash
,
6283 shared_bitmap_eq
, free
);
6286 gcc_obstack_init (&fake_var_decl_obstack
);
6289 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6290 predecessor edges. */
6293 remove_preds_and_fake_succs (constraint_graph_t graph
)
6297 /* Clear the implicit ref and address nodes from the successor
6299 for (i
= 0; i
< FIRST_REF_NODE
; i
++)
6301 if (graph
->succs
[i
])
6302 bitmap_clear_range (graph
->succs
[i
], FIRST_REF_NODE
,
6303 FIRST_REF_NODE
* 2);
6306 /* Free the successor list for the non-ref nodes. */
6307 for (i
= FIRST_REF_NODE
; i
< graph
->size
; i
++)
6309 if (graph
->succs
[i
])
6310 BITMAP_FREE (graph
->succs
[i
]);
6313 /* Now reallocate the size of the successor list as, and blow away
6314 the predecessor bitmaps. */
6315 graph
->size
= VEC_length (varinfo_t
, varmap
);
6316 graph
->succs
= XRESIZEVEC (bitmap
, graph
->succs
, graph
->size
);
6318 free (graph
->implicit_preds
);
6319 graph
->implicit_preds
= NULL
;
6320 free (graph
->preds
);
6321 graph
->preds
= NULL
;
6322 bitmap_obstack_release (&predbitmap_obstack
);
6325 /* Solve the constraint set. */
6328 solve_constraints (void)
6330 struct scc_info
*si
;
6334 "\nCollapsing static cycles and doing variable "
6337 init_graph (VEC_length (varinfo_t
, varmap
) * 2);
6340 fprintf (dump_file
, "Building predecessor graph\n");
6341 build_pred_graph ();
6344 fprintf (dump_file
, "Detecting pointer and location "
6346 si
= perform_var_substitution (graph
);
6349 fprintf (dump_file
, "Rewriting constraints and unifying "
6351 rewrite_constraints (graph
, si
);
6353 build_succ_graph ();
6355 free_var_substitution_info (si
);
6357 /* Attach complex constraints to graph nodes. */
6358 move_complex_constraints (graph
);
6361 fprintf (dump_file
, "Uniting pointer but not location equivalent "
6363 unite_pointer_equivalences (graph
);
6366 fprintf (dump_file
, "Finding indirect cycles\n");
6367 find_indirect_cycles (graph
);
6369 /* Implicit nodes and predecessors are no longer necessary at this
6371 remove_preds_and_fake_succs (graph
);
6373 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
6375 fprintf (dump_file
, "\n\n// The constraint graph before solve-graph "
6376 "in dot format:\n");
6377 dump_constraint_graph (dump_file
);
6378 fprintf (dump_file
, "\n\n");
6382 fprintf (dump_file
, "Solving graph\n");
6384 solve_graph (graph
);
6386 if (dump_file
&& (dump_flags
& TDF_GRAPH
))
6388 fprintf (dump_file
, "\n\n// The constraint graph after solve-graph "
6389 "in dot format:\n");
6390 dump_constraint_graph (dump_file
);
6391 fprintf (dump_file
, "\n\n");
6395 dump_sa_points_to_info (dump_file
);
6398 /* Create points-to sets for the current function. See the comments
6399 at the start of the file for an algorithmic overview. */
6402 compute_points_to_sets (void)
6408 timevar_push (TV_TREE_PTA
);
6412 intra_create_variable_infos ();
6414 /* Now walk all statements and build the constraint set. */
6417 gimple_stmt_iterator gsi
;
6419 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6421 gimple phi
= gsi_stmt (gsi
);
6423 if (is_gimple_reg (gimple_phi_result (phi
)))
6424 find_func_aliases (phi
);
6427 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6429 gimple stmt
= gsi_stmt (gsi
);
6431 find_func_aliases (stmt
);
6437 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
6438 dump_constraints (dump_file
, 0);
6441 /* From the constraints compute the points-to sets. */
6442 solve_constraints ();
6444 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
6445 find_what_var_points_to (get_varinfo (escaped_id
),
6446 &cfun
->gimple_df
->escaped
);
6448 /* Make sure the ESCAPED solution (which is used as placeholder in
6449 other solutions) does not reference itself. This simplifies
6450 points-to solution queries. */
6451 cfun
->gimple_df
->escaped
.escaped
= 0;
6453 /* Mark escaped HEAP variables as global. */
6454 FOR_EACH_VEC_ELT (varinfo_t
, varmap
, i
, vi
)
6456 && !vi
->is_restrict_var
6457 && !vi
->is_global_var
)
6458 DECL_EXTERNAL (vi
->decl
) = vi
->is_global_var
6459 = pt_solution_includes (&cfun
->gimple_df
->escaped
, vi
->decl
);
6461 /* Compute the points-to sets for pointer SSA_NAMEs. */
6462 for (i
= 0; i
< num_ssa_names
; ++i
)
6464 tree ptr
= ssa_name (i
);
6466 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
6467 find_what_p_points_to (ptr
);
6470 /* Compute the call-used/clobbered sets. */
6473 gimple_stmt_iterator gsi
;
6475 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6477 gimple stmt
= gsi_stmt (gsi
);
6478 struct pt_solution
*pt
;
6479 if (!is_gimple_call (stmt
))
6482 pt
= gimple_call_use_set (stmt
);
6483 if (gimple_call_flags (stmt
) & ECF_CONST
)
6484 memset (pt
, 0, sizeof (struct pt_solution
));
6485 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
6487 find_what_var_points_to (vi
, pt
);
6488 /* Escaped (and thus nonlocal) variables are always
6489 implicitly used by calls. */
6490 /* ??? ESCAPED can be empty even though NONLOCAL
6497 /* If there is nothing special about this call then
6498 we have made everything that is used also escape. */
6499 *pt
= cfun
->gimple_df
->escaped
;
6503 pt
= gimple_call_clobber_set (stmt
);
6504 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
6505 memset (pt
, 0, sizeof (struct pt_solution
));
6506 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
6508 find_what_var_points_to (vi
, pt
);
6509 /* Escaped (and thus nonlocal) variables are always
6510 implicitly clobbered by calls. */
6511 /* ??? ESCAPED can be empty even though NONLOCAL
6518 /* If there is nothing special about this call then
6519 we have made everything that is used also escape. */
6520 *pt
= cfun
->gimple_df
->escaped
;
6526 timevar_pop (TV_TREE_PTA
);
6530 /* Delete created points-to sets. */
6533 delete_points_to_sets (void)
6537 htab_delete (shared_bitmap_table
);
6538 if (dump_file
&& (dump_flags
& TDF_STATS
))
6539 fprintf (dump_file
, "Points to sets created:%d\n",
6540 stats
.points_to_sets_created
);
6542 pointer_map_destroy (vi_for_tree
);
6543 pointer_map_destroy (call_stmt_vars
);
6544 bitmap_obstack_release (&pta_obstack
);
6545 VEC_free (constraint_t
, heap
, constraints
);
6547 for (i
= 0; i
< graph
->size
; i
++)
6548 VEC_free (constraint_t
, heap
, graph
->complex[i
]);
6549 free (graph
->complex);
6552 free (graph
->succs
);
6554 free (graph
->pe_rep
);
6555 free (graph
->indirect_cycles
);
6558 VEC_free (varinfo_t
, heap
, varmap
);
6559 free_alloc_pool (variable_info_pool
);
6560 free_alloc_pool (constraint_pool
);
6562 obstack_free (&fake_var_decl_obstack
, NULL
);
6566 /* Compute points-to information for every SSA_NAME pointer in the
6567 current function and compute the transitive closure of escaped
6568 variables to re-initialize the call-clobber states of local variables. */
6571 compute_may_aliases (void)
6573 if (cfun
->gimple_df
->ipa_pta
)
6577 fprintf (dump_file
, "\nNot re-computing points-to information "
6578 "because IPA points-to information is available.\n\n");
6580 /* But still dump what we have remaining it. */
6581 dump_alias_info (dump_file
);
6583 if (dump_flags
& TDF_DETAILS
)
6584 dump_referenced_vars (dump_file
);
6590 /* For each pointer P_i, determine the sets of variables that P_i may
6591 point-to. Compute the reachability set of escaped and call-used
6593 compute_points_to_sets ();
6595 /* Debugging dumps. */
6598 dump_alias_info (dump_file
);
6600 if (dump_flags
& TDF_DETAILS
)
6601 dump_referenced_vars (dump_file
);
6604 /* Deallocate memory used by aliasing data structures and the internal
6605 points-to solution. */
6606 delete_points_to_sets ();
6608 gcc_assert (!need_ssa_update_p (cfun
));
6614 gate_tree_pta (void)
6616 return flag_tree_pta
;
6619 /* A dummy pass to cause points-to information to be computed via
6620 TODO_rebuild_alias. */
6622 struct gimple_opt_pass pass_build_alias
=
6627 gate_tree_pta
, /* gate */
6631 0, /* static_pass_number */
6632 TV_NONE
, /* tv_id */
6633 PROP_cfg
| PROP_ssa
, /* properties_required */
6634 0, /* properties_provided */
6635 0, /* properties_destroyed */
6636 0, /* todo_flags_start */
6637 TODO_rebuild_alias
| TODO_dump_func
/* todo_flags_finish */
6641 /* A dummy pass to cause points-to information to be computed via
6642 TODO_rebuild_alias. */
6644 struct gimple_opt_pass pass_build_ealias
=
6648 "ealias", /* name */
6649 gate_tree_pta
, /* gate */
6653 0, /* static_pass_number */
6654 TV_NONE
, /* tv_id */
6655 PROP_cfg
| PROP_ssa
, /* properties_required */
6656 0, /* properties_provided */
6657 0, /* properties_destroyed */
6658 0, /* todo_flags_start */
6659 TODO_rebuild_alias
| TODO_dump_func
/* todo_flags_finish */
6664 /* Return true if we should execute IPA PTA. */
6670 /* Don't bother doing anything if the program has errors. */
6674 /* IPA PTA solutions for ESCAPED. */
6675 struct pt_solution ipa_escaped_pt
6676 = { true, false, false, false, false, false, false, NULL
};
6678 /* Associate node with varinfo DATA. Worker for
6679 cgraph_for_node_and_aliases. */
6681 associate_varinfo_to_alias (struct cgraph_node
*node
, void *data
)
6683 if (node
->alias
|| node
->thunk
.thunk_p
)
6684 insert_vi_for_tree (node
->decl
, (varinfo_t
)data
);
6688 /* Execute the driver for IPA PTA. */
6690 ipa_pta_execute (void)
6692 struct cgraph_node
*node
;
6693 struct varpool_node
*var
;
6700 /* Build the constraints. */
6701 for (node
= cgraph_nodes
; node
; node
= node
->next
)
6704 /* Nodes without a body are not interesting. Especially do not
6705 visit clones at this point for now - we get duplicate decls
6706 there for inline clones at least. */
6707 if (!cgraph_function_with_gimple_body_p (node
)
6711 vi
= create_function_info_for (node
->decl
,
6712 alias_get_name (node
->decl
));
6713 cgraph_for_node_and_aliases (node
, associate_varinfo_to_alias
, vi
, true);
6716 /* Create constraints for global variables and their initializers. */
6717 for (var
= varpool_nodes
; var
; var
= var
->next
)
6719 struct varpool_node
*alias
;
6722 vi
= get_vi_for_tree (var
->decl
);
6724 /* Associate the varinfo node with all aliases. */
6725 for (alias
= var
->extra_name
; alias
; alias
= alias
->next
)
6726 insert_vi_for_tree (alias
->decl
, vi
);
6732 "Generating constraints for global initializers\n\n");
6733 dump_constraints (dump_file
, 0);
6734 fprintf (dump_file
, "\n");
6736 from
= VEC_length (constraint_t
, constraints
);
6738 for (node
= cgraph_nodes
; node
; node
= node
->next
)
6740 struct function
*func
;
6744 /* Nodes without a body are not interesting. */
6745 if (!cgraph_function_with_gimple_body_p (node
)
6752 "Generating constraints for %s", cgraph_node_name (node
));
6753 if (DECL_ASSEMBLER_NAME_SET_P (node
->decl
))
6754 fprintf (dump_file
, " (%s)",
6755 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node
->decl
)));
6756 fprintf (dump_file
, "\n");
6759 func
= DECL_STRUCT_FUNCTION (node
->decl
);
6760 old_func_decl
= current_function_decl
;
6762 current_function_decl
= node
->decl
;
6764 if (node
->local
.externally_visible
)
6766 /* For externally visible functions use local constraints for
6767 their arguments. For local functions we see all callers
6768 and thus do not need initial constraints for parameters. */
6769 intra_create_variable_infos ();
6771 /* We also need to make function return values escape. Nothing
6772 escapes by returning from main though. */
6773 if (!MAIN_NAME_P (DECL_NAME (node
->decl
)))
6776 fi
= lookup_vi_for_tree (node
->decl
);
6777 rvi
= first_vi_for_offset (fi
, fi_result
);
6778 if (rvi
&& rvi
->offset
== fi_result
)
6780 struct constraint_expr includes
;
6781 struct constraint_expr var
;
6782 includes
.var
= escaped_id
;
6783 includes
.offset
= 0;
6784 includes
.type
= SCALAR
;
6788 process_constraint (new_constraint (includes
, var
));
6793 /* Build constriants for the function body. */
6794 FOR_EACH_BB_FN (bb
, func
)
6796 gimple_stmt_iterator gsi
;
6798 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
6801 gimple phi
= gsi_stmt (gsi
);
6803 if (is_gimple_reg (gimple_phi_result (phi
)))
6804 find_func_aliases (phi
);
6807 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6809 gimple stmt
= gsi_stmt (gsi
);
6811 find_func_aliases (stmt
);
6812 find_func_clobbers (stmt
);
6816 current_function_decl
= old_func_decl
;
6821 fprintf (dump_file
, "\n");
6822 dump_constraints (dump_file
, from
);
6823 fprintf (dump_file
, "\n");
6825 from
= VEC_length (constraint_t
, constraints
);
6828 /* From the constraints compute the points-to sets. */
6829 solve_constraints ();
6831 /* Compute the global points-to sets for ESCAPED.
6832 ??? Note that the computed escape set is not correct
6833 for the whole unit as we fail to consider graph edges to
6834 externally visible functions. */
6835 find_what_var_points_to (get_varinfo (escaped_id
), &ipa_escaped_pt
);
6837 /* Make sure the ESCAPED solution (which is used as placeholder in
6838 other solutions) does not reference itself. This simplifies
6839 points-to solution queries. */
6840 ipa_escaped_pt
.ipa_escaped
= 0;
6842 /* Assign the points-to sets to the SSA names in the unit. */
6843 for (node
= cgraph_nodes
; node
; node
= node
->next
)
6846 struct function
*fn
;
6850 struct pt_solution uses
, clobbers
;
6851 struct cgraph_edge
*e
;
6853 /* Nodes without a body are not interesting. */
6854 if (!cgraph_function_with_gimple_body_p (node
)
6858 fn
= DECL_STRUCT_FUNCTION (node
->decl
);
6860 /* Compute the points-to sets for pointer SSA_NAMEs. */
6861 FOR_EACH_VEC_ELT (tree
, fn
->gimple_df
->ssa_names
, i
, ptr
)
6864 && POINTER_TYPE_P (TREE_TYPE (ptr
)))
6865 find_what_p_points_to (ptr
);
6868 /* Compute the call-use and call-clobber sets for all direct calls. */
6869 fi
= lookup_vi_for_tree (node
->decl
);
6870 gcc_assert (fi
->is_fn_info
);
6871 find_what_var_points_to (first_vi_for_offset (fi
, fi_clobbers
),
6873 find_what_var_points_to (first_vi_for_offset (fi
, fi_uses
), &uses
);
6874 for (e
= node
->callers
; e
; e
= e
->next_caller
)
6879 *gimple_call_clobber_set (e
->call_stmt
) = clobbers
;
6880 *gimple_call_use_set (e
->call_stmt
) = uses
;
6883 /* Compute the call-use and call-clobber sets for indirect calls
6884 and calls to external functions. */
6885 FOR_EACH_BB_FN (bb
, fn
)
6887 gimple_stmt_iterator gsi
;
6889 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
6891 gimple stmt
= gsi_stmt (gsi
);
6892 struct pt_solution
*pt
;
6896 if (!is_gimple_call (stmt
))
6899 /* Handle direct calls to external functions. */
6900 decl
= gimple_call_fndecl (stmt
);
6902 && (!(fi
= lookup_vi_for_tree (decl
))
6903 || !fi
->is_fn_info
))
6905 pt
= gimple_call_use_set (stmt
);
6906 if (gimple_call_flags (stmt
) & ECF_CONST
)
6907 memset (pt
, 0, sizeof (struct pt_solution
));
6908 else if ((vi
= lookup_call_use_vi (stmt
)) != NULL
)
6910 find_what_var_points_to (vi
, pt
);
6911 /* Escaped (and thus nonlocal) variables are always
6912 implicitly used by calls. */
6913 /* ??? ESCAPED can be empty even though NONLOCAL
6916 pt
->ipa_escaped
= 1;
6920 /* If there is nothing special about this call then
6921 we have made everything that is used also escape. */
6922 *pt
= ipa_escaped_pt
;
6926 pt
= gimple_call_clobber_set (stmt
);
6927 if (gimple_call_flags (stmt
) & (ECF_CONST
|ECF_PURE
|ECF_NOVOPS
))
6928 memset (pt
, 0, sizeof (struct pt_solution
));
6929 else if ((vi
= lookup_call_clobber_vi (stmt
)) != NULL
)
6931 find_what_var_points_to (vi
, pt
);
6932 /* Escaped (and thus nonlocal) variables are always
6933 implicitly clobbered by calls. */
6934 /* ??? ESCAPED can be empty even though NONLOCAL
6937 pt
->ipa_escaped
= 1;
6941 /* If there is nothing special about this call then
6942 we have made everything that is used also escape. */
6943 *pt
= ipa_escaped_pt
;
6948 /* Handle indirect calls. */
6950 && (fi
= get_fi_for_callee (stmt
)))
6952 /* We need to accumulate all clobbers/uses of all possible
6954 fi
= get_varinfo (find (fi
->id
));
6955 /* If we cannot constrain the set of functions we'll end up
6956 calling we end up using/clobbering everything. */
6957 if (bitmap_bit_p (fi
->solution
, anything_id
)
6958 || bitmap_bit_p (fi
->solution
, nonlocal_id
)
6959 || bitmap_bit_p (fi
->solution
, escaped_id
))
6961 pt_solution_reset (gimple_call_clobber_set (stmt
));
6962 pt_solution_reset (gimple_call_use_set (stmt
));
6968 struct pt_solution
*uses
, *clobbers
;
6970 uses
= gimple_call_use_set (stmt
);
6971 clobbers
= gimple_call_clobber_set (stmt
);
6972 memset (uses
, 0, sizeof (struct pt_solution
));
6973 memset (clobbers
, 0, sizeof (struct pt_solution
));
6974 EXECUTE_IF_SET_IN_BITMAP (fi
->solution
, 0, i
, bi
)
6976 struct pt_solution sol
;
6978 vi
= get_varinfo (i
);
6979 if (!vi
->is_fn_info
)
6981 /* ??? We could be more precise here? */
6983 uses
->ipa_escaped
= 1;
6984 clobbers
->nonlocal
= 1;
6985 clobbers
->ipa_escaped
= 1;
6989 if (!uses
->anything
)
6991 find_what_var_points_to
6992 (first_vi_for_offset (vi
, fi_uses
), &sol
);
6993 pt_solution_ior_into (uses
, &sol
);
6995 if (!clobbers
->anything
)
6997 find_what_var_points_to
6998 (first_vi_for_offset (vi
, fi_clobbers
), &sol
);
6999 pt_solution_ior_into (clobbers
, &sol
);
7007 fn
->gimple_df
->ipa_pta
= true;
7010 delete_points_to_sets ();
7017 struct simple_ipa_opt_pass pass_ipa_pta
=
7022 gate_ipa_pta
, /* gate */
7023 ipa_pta_execute
, /* execute */
7026 0, /* static_pass_number */
7027 TV_IPA_PTA
, /* tv_id */
7028 0, /* properties_required */
7029 0, /* properties_provided */
7030 0, /* properties_destroyed */
7031 0, /* todo_flags_start */
7032 TODO_update_ssa
/* todo_flags_finish */