1 /* Tree based points-to analysis
2 Copyright (C) 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
43 #include "tree-gimple.h"
47 #include "tree-pass.h"
49 #include "alloc-pool.h"
50 #include "splay-tree.h"
52 #include "tree-ssa-structalias.h"
55 /* The idea behind this analyzer is to generate set constraints from the
56 program, then solve the resulting constraints in order to generate the
59 Set constraints are a way of modeling program analysis problems that
60 involve sets. They consist of an inclusion constraint language,
61 describing the variables (each variable is a set) and operations that
62 are involved on the variables, and a set of rules that derive facts
63 from these operations. To solve a system of set constraints, you derive
64 all possible facts under the rules, which gives you the correct sets
67 See "Efficient Field-sensitive pointer analysis for C" by "David
68 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
69 http://citeseer.ist.psu.edu/pearce04efficient.html
71 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
72 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
73 http://citeseer.ist.psu.edu/heintze01ultrafast.html
75 There are three types of constraint expressions, DEREF, ADDRESSOF, and
76 SCALAR. Each constraint expression consists of a constraint type,
77 a variable, and an offset.
79 SCALAR is a constraint expression type used to represent x, whether
80 it appears on the LHS or the RHS of a statement.
81 DEREF is a constraint expression type used to represent *x, whether
82 it appears on the LHS or the RHS of a statement.
83 ADDRESSOF is a constraint expression used to represent &x, whether
84 it appears on the LHS or the RHS of a statement.
86 Each pointer variable in the program is assigned an integer id, and
87 each field of a structure variable is assigned an integer id as well.
89 Structure variables are linked to their list of fields through a "next
90 field" in each variable that points to the next field in offset
92 Each variable for a structure field has
94 1. "size", that tells the size in bits of that field.
95 2. "fullsize, that tells the size in bits of the entire structure.
96 3. "offset", that tells the offset in bits from the beginning of the
97 structure to this field.
109 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
110 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
111 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
114 In order to solve the system of set constraints, the following is
117 1. Each constraint variable x has a solution set associated with it,
120 2. Constraints are separated into direct, copy, and complex.
121 Direct constraints are ADDRESSOF constraints that require no extra
122 processing, such as P = &Q
123 Copy constraints are those of the form P = Q.
124 Complex constraints are all the constraints involving dereferences.
126 3. All direct constraints of the form P = &Q are processed, such
127 that Q is added to Sol(P)
129 4. All complex constraints for a given constraint variable are stored in a
130 linked list attached to that variable's node.
132 5. A directed graph is built out of the copy constraints. Each
133 constraint variable is a node in the graph, and an edge from
134 Q to P is added for each copy constraint of the form P = Q
136 6. The graph is then walked, and solution sets are
137 propagated along the copy edges, such that an edge from Q to P
138 causes Sol(P) <- Sol(P) union Sol(Q).
140 7. As we visit each node, all complex constraints associated with
141 that node are processed by adding appropriate copy edges to the graph, or the
142 appropriate variables to the solution set.
144 8. The process of walking the graph is iterated until no solution
147 Prior to walking the graph in steps 6 and 7, We perform static
148 cycle elimination on the constraint graph, as well
149 as off-line variable substitution.
151 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
152 on and turned into anything), but isn't. You can just see what offset
153 inside the pointed-to struct it's going to access.
155 TODO: Constant bounded arrays can be handled as if they were structs of the
156 same number of elements.
158 TODO: Modeling heap and incoming pointers becomes much better if we
159 add fields to them as we discover them, which we could do.
161 TODO: We could handle unions, but to be honest, it's probably not
162 worth the pain or slowdown. */
164 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map
)))
165 htab_t heapvar_for_stmt
;
166 static bool use_field_sensitive
= true;
167 static int in_ipa_mode
= 0;
168 static bitmap_obstack predbitmap_obstack
;
169 static bitmap_obstack ptabitmap_obstack
;
170 static bitmap_obstack iteration_obstack
;
172 static unsigned int create_variable_info_for (tree
, const char *);
173 static void build_constraint_graph (void);
175 DEF_VEC_P(constraint_t
);
176 DEF_VEC_ALLOC_P(constraint_t
,heap
);
178 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
180 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
182 static struct constraint_stats
184 unsigned int total_vars
;
185 unsigned int collapsed_vars
;
186 unsigned int unified_vars_static
;
187 unsigned int unified_vars_dynamic
;
188 unsigned int iterations
;
189 unsigned int num_edges
;
194 /* ID of this variable */
197 /* Name of this variable */
200 /* Tree that this variable is associated with. */
203 /* Offset of this variable, in bits, from the base variable */
204 unsigned HOST_WIDE_INT offset
;
206 /* Size of the variable, in bits. */
207 unsigned HOST_WIDE_INT size
;
209 /* Full size of the base variable, in bits. */
210 unsigned HOST_WIDE_INT fullsize
;
212 /* A link to the variable for the next field in this structure. */
213 struct variable_info
*next
;
215 /* Node in the graph that represents the constraints and points-to
216 solution for the variable. */
219 /* True if the address of this variable is taken. Needed for
220 variable substitution. */
221 unsigned int address_taken
:1;
223 /* True if this variable is the target of a dereference. Needed for
224 variable substitution. */
225 unsigned int indirect_target
:1;
227 /* True if this is a variable created by the constraint analysis, such as
228 heap variables and constraints we had to break up. */
229 unsigned int is_artificial_var
:1;
231 /* True if this is a special variable whose solution set should not be
233 unsigned int is_special_var
:1;
235 /* True for variables whose size is not known or variable. */
236 unsigned int is_unknown_size_var
:1;
238 /* True for variables that have unions somewhere in them. */
239 unsigned int has_union
:1;
241 /* True if this is a heap variable. */
242 unsigned int is_heap_var
:1;
244 /* Points-to set for this variable. */
247 /* Variable ids represented by this node. */
250 /* Vector of complex constraints for this node. Complex
251 constraints are those involving dereferences. */
252 VEC(constraint_t
,heap
) *complex;
254 /* Variable id this was collapsed to due to type unsafety.
255 This should be unused completely after build_constraint_graph, or
256 something is broken. */
257 struct variable_info
*collapsed_to
;
259 typedef struct variable_info
*varinfo_t
;
261 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
263 /* Pool of variable info structures. */
264 static alloc_pool variable_info_pool
;
266 DEF_VEC_P(varinfo_t
);
268 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
270 /* Table of variable info structures for constraint variables. Indexed directly
271 by variable info id. */
272 static VEC(varinfo_t
,heap
) *varmap
;
274 /* Return the varmap element N */
276 static inline varinfo_t
277 get_varinfo (unsigned int n
)
279 return VEC_index(varinfo_t
, varmap
, n
);
282 /* Return the varmap element N, following the collapsed_to link. */
284 static inline varinfo_t
285 get_varinfo_fc (unsigned int n
)
287 varinfo_t v
= VEC_index(varinfo_t
, varmap
, n
);
290 return v
->collapsed_to
;
294 /* Variable that represents the unknown pointer. */
295 static varinfo_t var_anything
;
296 static tree anything_tree
;
297 static unsigned int anything_id
;
299 /* Variable that represents the NULL pointer. */
300 static varinfo_t var_nothing
;
301 static tree nothing_tree
;
302 static unsigned int nothing_id
;
304 /* Variable that represents read only memory. */
305 static varinfo_t var_readonly
;
306 static tree readonly_tree
;
307 static unsigned int readonly_id
;
309 /* Variable that represents integers. This is used for when people do things
311 static varinfo_t var_integer
;
312 static tree integer_tree
;
313 static unsigned int integer_id
;
316 /* Lookup a heap var for FROM, and return it if we find one. */
319 heapvar_lookup (tree from
)
321 struct tree_map
*h
, in
;
324 h
= htab_find_with_hash (heapvar_for_stmt
, &in
, htab_hash_pointer (from
));
330 /* Insert a mapping FROM->TO in the heap var for statement
334 heapvar_insert (tree from
, tree to
)
339 h
= ggc_alloc (sizeof (struct tree_map
));
340 h
->hash
= htab_hash_pointer (from
);
343 loc
= htab_find_slot_with_hash (heapvar_for_stmt
, h
, h
->hash
, INSERT
);
344 *(struct tree_map
**) loc
= h
;
347 /* Return a new variable info structure consisting for a variable
348 named NAME, and using constraint graph node NODE. */
351 new_var_info (tree t
, unsigned int id
, const char *name
, unsigned int node
)
353 varinfo_t ret
= pool_alloc (variable_info_pool
);
359 ret
->address_taken
= false;
360 ret
->indirect_target
= false;
361 ret
->is_artificial_var
= false;
362 ret
->is_heap_var
= false;
363 ret
->is_special_var
= false;
364 ret
->is_unknown_size_var
= false;
365 ret
->has_union
= false;
366 ret
->solution
= BITMAP_ALLOC (&ptabitmap_obstack
);
367 ret
->variables
= BITMAP_ALLOC (&ptabitmap_obstack
);
370 ret
->collapsed_to
= NULL
;
374 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
376 /* An expression that appears in a constraint. */
378 struct constraint_expr
380 /* Constraint type. */
381 constraint_expr_type type
;
383 /* Variable we are referring to in the constraint. */
386 /* Offset, in bits, of this constraint from the beginning of
387 variables it ends up referring to.
389 IOW, in a deref constraint, we would deref, get the result set,
390 then add OFFSET to each member. */
391 unsigned HOST_WIDE_INT offset
;
394 typedef struct constraint_expr ce_s
;
396 DEF_VEC_ALLOC_O(ce_s
, heap
);
397 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
398 static void do_deref (VEC (ce_s
, heap
) **);
400 /* Our set constraints are made up of two constraint expressions, one
403 As described in the introduction, our set constraints each represent an
404 operation between set valued variables.
408 struct constraint_expr lhs
;
409 struct constraint_expr rhs
;
412 /* List of constraints that we use to build the constraint graph from. */
414 static VEC(constraint_t
,heap
) *constraints
;
415 static alloc_pool constraint_pool
;
417 /* An edge in the weighted constraint graph. The edges are weighted,
418 with a bit set in weights meaning their is an edge with that
420 We don't keep the src in the edge, because we always know what it
423 struct constraint_edge
429 typedef struct constraint_edge
*constraint_edge_t
;
430 static alloc_pool constraint_edge_pool
;
432 /* Return a new constraint edge from SRC to DEST. */
434 static constraint_edge_t
435 new_constraint_edge (unsigned int dest
)
437 constraint_edge_t ret
= pool_alloc (constraint_edge_pool
);
443 DEF_VEC_P(constraint_edge_t
);
444 DEF_VEC_ALLOC_P(constraint_edge_t
,heap
);
447 /* The constraint graph is represented internally in two different
448 ways. The overwhelming majority of edges in the constraint graph
449 are zero weigh edges, and thus, using a vector of contrainst_edge_t
450 is a waste of time and memory, since they have no weights. We
451 simply use a bitmap to store the preds and succs for each node.
452 The weighted edges are stored as a set of adjacency vectors, one
453 per variable. succs[x] is the vector of successors for variable x,
454 and preds[x] is the vector of predecessors for variable x. IOW,
455 all edges are "forward" edges, which is not like our CFG. So
456 remember that preds[x]->src == x, and succs[x]->src == x. */
458 struct constraint_graph
460 bitmap
*zero_weight_succs
;
461 bitmap
*zero_weight_preds
;
462 VEC(constraint_edge_t
,heap
) **succs
;
463 VEC(constraint_edge_t
,heap
) **preds
;
466 typedef struct constraint_graph
*constraint_graph_t
;
468 static constraint_graph_t graph
;
470 /* Create a new constraint consisting of LHS and RHS expressions. */
473 new_constraint (const struct constraint_expr lhs
,
474 const struct constraint_expr rhs
)
476 constraint_t ret
= pool_alloc (constraint_pool
);
482 /* Print out constraint C to FILE. */
485 dump_constraint (FILE *file
, constraint_t c
)
487 if (c
->lhs
.type
== ADDRESSOF
)
489 else if (c
->lhs
.type
== DEREF
)
491 fprintf (file
, "%s", get_varinfo_fc (c
->lhs
.var
)->name
);
492 if (c
->lhs
.offset
!= 0)
493 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
494 fprintf (file
, " = ");
495 if (c
->rhs
.type
== ADDRESSOF
)
497 else if (c
->rhs
.type
== DEREF
)
499 fprintf (file
, "%s", get_varinfo_fc (c
->rhs
.var
)->name
);
500 if (c
->rhs
.offset
!= 0)
501 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
502 fprintf (file
, "\n");
505 /* Print out constraint C to stderr. */
508 debug_constraint (constraint_t c
)
510 dump_constraint (stderr
, c
);
513 /* Print out all constraints to FILE */
516 dump_constraints (FILE *file
)
520 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
521 dump_constraint (file
, c
);
524 /* Print out all constraints to stderr. */
527 debug_constraints (void)
529 dump_constraints (stderr
);
534 The solver is a simple worklist solver, that works on the following
537 sbitmap changed_nodes = all ones;
538 changed_count = number of nodes;
539 For each node that was already collapsed:
542 while (changed_count > 0)
544 compute topological ordering for constraint graph
546 find and collapse cycles in the constraint graph (updating
547 changed if necessary)
549 for each node (n) in the graph in topological order:
552 Process each complex constraint associated with the node,
553 updating changed if necessary.
555 For each outgoing edge from n, propagate the solution from n to
556 the destination of the edge, updating changed as necessary.
560 /* Return true if two constraint expressions A and B are equal. */
563 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
565 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
568 /* Return true if constraint expression A is less than constraint expression
569 B. This is just arbitrary, but consistent, in order to give them an
573 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
575 if (a
.type
== b
.type
)
578 return a
.offset
< b
.offset
;
580 return a
.var
< b
.var
;
583 return a
.type
< b
.type
;
586 /* Return true if constraint A is less than constraint B. This is just
587 arbitrary, but consistent, in order to give them an ordering. */
590 constraint_less (const constraint_t a
, const constraint_t b
)
592 if (constraint_expr_less (a
->lhs
, b
->lhs
))
594 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
597 return constraint_expr_less (a
->rhs
, b
->rhs
);
600 /* Return true if two constraints A and B are equal. */
603 constraint_equal (struct constraint a
, struct constraint b
)
605 return constraint_expr_equal (a
.lhs
, b
.lhs
)
606 && constraint_expr_equal (a
.rhs
, b
.rhs
);
610 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
613 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
614 struct constraint lookfor
)
622 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
623 if (place
>= VEC_length (constraint_t
, vec
))
625 found
= VEC_index (constraint_t
, vec
, place
);
626 if (!constraint_equal (*found
, lookfor
))
631 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
634 constraint_set_union (VEC(constraint_t
,heap
) **to
,
635 VEC(constraint_t
,heap
) **from
)
640 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
642 if (constraint_vec_find (*to
, *c
) == NULL
)
644 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
646 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
651 /* Take a solution set SET, add OFFSET to each member of the set, and
652 overwrite SET with the result when done. */
655 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
657 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
661 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
663 /* If this is a properly sized variable, only add offset if it's
664 less than end. Otherwise, it is globbed to a single
667 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
669 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
670 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
673 bitmap_set_bit (result
, v
->id
);
675 else if (get_varinfo (i
)->is_artificial_var
676 || get_varinfo (i
)->has_union
677 || get_varinfo (i
)->is_unknown_size_var
)
679 bitmap_set_bit (result
, i
);
683 bitmap_copy (set
, result
);
684 BITMAP_FREE (result
);
687 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
691 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
694 return bitmap_ior_into (to
, from
);
700 tmp
= BITMAP_ALLOC (&iteration_obstack
);
701 bitmap_copy (tmp
, from
);
702 solution_set_add (tmp
, inc
);
703 res
= bitmap_ior_into (to
, tmp
);
709 /* Insert constraint C into the list of complex constraints for VAR. */
712 insert_into_complex (unsigned int var
, constraint_t c
)
714 varinfo_t vi
= get_varinfo (var
);
715 unsigned int place
= VEC_lower_bound (constraint_t
, vi
->complex, c
,
717 VEC_safe_insert (constraint_t
, heap
, vi
->complex, place
, c
);
721 /* Compare two constraint edges A and B, return true if they are equal. */
724 constraint_edge_equal (struct constraint_edge a
, struct constraint_edge b
)
726 return a
.dest
== b
.dest
;
729 /* Compare two constraint edges, return true if A is less than B */
732 constraint_edge_less (const constraint_edge_t a
, const constraint_edge_t b
)
734 if (a
->dest
< b
->dest
)
739 /* Find the constraint edge that matches LOOKFOR, in VEC.
740 Return the edge, if found, NULL otherwise. */
742 static constraint_edge_t
743 constraint_edge_vec_find (VEC(constraint_edge_t
,heap
) *vec
,
744 struct constraint_edge lookfor
)
747 constraint_edge_t edge
= NULL
;
749 place
= VEC_lower_bound (constraint_edge_t
, vec
, &lookfor
,
750 constraint_edge_less
);
751 if (place
>= VEC_length (constraint_edge_t
, vec
))
753 edge
= VEC_index (constraint_edge_t
, vec
, place
);
754 if (!constraint_edge_equal (*edge
, lookfor
))
759 /* Condense two variable nodes into a single variable node, by moving
760 all associated info from SRC to TO. */
763 condense_varmap_nodes (unsigned int to
, unsigned int src
)
765 varinfo_t tovi
= get_varinfo (to
);
766 varinfo_t srcvi
= get_varinfo (src
);
771 /* the src node, and all its variables, are now the to node. */
773 EXECUTE_IF_SET_IN_BITMAP (srcvi
->variables
, 0, i
, bi
)
774 get_varinfo (i
)->node
= to
;
776 /* Merge the src node variables and the to node variables. */
777 bitmap_set_bit (tovi
->variables
, src
);
778 bitmap_ior_into (tovi
->variables
, srcvi
->variables
);
779 bitmap_clear (srcvi
->variables
);
781 /* Move all complex constraints from src node into to node */
782 for (i
= 0; VEC_iterate (constraint_t
, srcvi
->complex, i
, c
); i
++)
784 /* In complex constraints for node src, we may have either
785 a = *src, and *src = a. */
787 if (c
->rhs
.type
== DEREF
)
792 constraint_set_union (&tovi
->complex, &srcvi
->complex);
793 VEC_free (constraint_t
, heap
, srcvi
->complex);
794 srcvi
->complex = NULL
;
797 /* Erase an edge from SRC to SRC from GRAPH. This routine only
798 handles self-edges (e.g. an edge from a to a). */
801 erase_graph_self_edge (constraint_graph_t graph
, unsigned int src
)
803 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[src
];
804 VEC(constraint_edge_t
,heap
) *succvec
= graph
->succs
[src
];
805 struct constraint_edge edge
;
810 /* Remove from the successors. */
811 place
= VEC_lower_bound (constraint_edge_t
, succvec
, &edge
,
812 constraint_edge_less
);
814 /* Make sure we found the edge. */
815 #ifdef ENABLE_CHECKING
817 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, succvec
, place
);
818 gcc_assert (constraint_edge_equal (*tmp
, edge
));
821 VEC_ordered_remove (constraint_edge_t
, succvec
, place
);
823 /* Remove from the predecessors. */
824 place
= VEC_lower_bound (constraint_edge_t
, predvec
, &edge
,
825 constraint_edge_less
);
827 /* Make sure we found the edge. */
828 #ifdef ENABLE_CHECKING
830 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, predvec
, place
);
831 gcc_assert (constraint_edge_equal (*tmp
, edge
));
834 VEC_ordered_remove (constraint_edge_t
, predvec
, place
);
837 /* Remove edges involving NODE from GRAPH. */
840 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
842 VEC(constraint_edge_t
,heap
) *succvec
= graph
->succs
[node
];
843 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[node
];
846 constraint_edge_t c
= NULL
;
849 /* Walk the successors, erase the associated preds. */
851 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[node
], 0, j
, bi
)
853 bitmap_clear_bit (graph
->zero_weight_preds
[j
], node
);
855 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
859 struct constraint_edge lookfor
;
860 constraint_edge_t result
;
863 place
= VEC_lower_bound (constraint_edge_t
, graph
->preds
[c
->dest
],
864 &lookfor
, constraint_edge_less
);
865 result
= VEC_ordered_remove (constraint_edge_t
,
866 graph
->preds
[c
->dest
], place
);
867 pool_free (constraint_edge_pool
, result
);
870 /* Walk the preds, erase the associated succs. */
872 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_preds
[node
], 0, j
, bi
)
874 bitmap_clear_bit (graph
->zero_weight_succs
[j
], node
);
876 for (i
=0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
880 struct constraint_edge lookfor
;
881 constraint_edge_t result
;
884 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[c
->dest
],
885 &lookfor
, constraint_edge_less
);
886 result
= VEC_ordered_remove (constraint_edge_t
,
887 graph
->succs
[c
->dest
], place
);
888 pool_free (constraint_edge_pool
, result
);
892 if (graph
->zero_weight_preds
[node
])
894 BITMAP_FREE (graph
->zero_weight_preds
[node
]);
895 graph
->zero_weight_preds
[node
] = NULL
;
898 if (graph
->zero_weight_succs
[node
])
900 BITMAP_FREE (graph
->zero_weight_succs
[node
]);
901 graph
->zero_weight_succs
[node
] = NULL
;
904 VEC_free (constraint_edge_t
, heap
, graph
->preds
[node
]);
905 VEC_free (constraint_edge_t
, heap
, graph
->succs
[node
]);
906 graph
->preds
[node
] = NULL
;
907 graph
->succs
[node
] = NULL
;
910 static bool edge_added
= false;
912 /* Add edge (src, dest) to the graph. */
915 add_graph_edge (constraint_graph_t graph
, unsigned int src
, unsigned int dest
)
918 VEC(constraint_edge_t
,heap
) *vec
;
919 struct constraint_edge newe
;
922 vec
= graph
->preds
[src
];
923 place
= VEC_lower_bound (constraint_edge_t
, vec
, &newe
,
924 constraint_edge_less
);
925 if (place
== VEC_length (constraint_edge_t
, vec
)
926 || VEC_index (constraint_edge_t
, vec
, place
)->dest
!= dest
)
928 constraint_edge_t edge
= new_constraint_edge (dest
);
930 VEC_safe_insert (constraint_edge_t
, heap
, graph
->preds
[src
],
932 edge
= new_constraint_edge (src
);
934 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[dest
],
935 edge
, constraint_edge_less
);
936 VEC_safe_insert (constraint_edge_t
, heap
, graph
->succs
[dest
],
947 /* Return the bitmap representing the weights of edge (SRC, DEST). */
950 get_graph_weights (constraint_graph_t graph
, unsigned int src
,
953 constraint_edge_t edge
;
954 VEC(constraint_edge_t
,heap
) *vec
;
955 struct constraint_edge lookfor
;
959 vec
= graph
->preds
[src
];
960 edge
= constraint_edge_vec_find (vec
, lookfor
);
961 gcc_assert (edge
!= NULL
);
962 return &edge
->weights
;
965 /* Allocate graph weight bitmap for the edges associated with SRC and
966 DEST in GRAPH. Both the pred and the succ edges share a single
967 bitmap, so we need to set both edges to that bitmap. */
970 allocate_graph_weights (constraint_graph_t graph
, unsigned int src
,
974 constraint_edge_t edge
;
975 VEC(constraint_edge_t
,heap
) *vec
;
976 struct constraint_edge lookfor
;
978 result
= BITMAP_ALLOC (&ptabitmap_obstack
);
980 /* Set the pred weight. */
982 vec
= graph
->preds
[src
];
983 edge
= constraint_edge_vec_find (vec
, lookfor
);
984 gcc_assert (edge
!= NULL
);
985 edge
->weights
= result
;
987 /* Set the succ weight. */
989 vec
= graph
->succs
[dest
];
990 edge
= constraint_edge_vec_find (vec
, lookfor
);
991 gcc_assert (edge
!= NULL
);
992 edge
->weights
= result
;
998 /* Merge GRAPH nodes FROM and TO into node TO. */
1001 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1004 VEC(constraint_edge_t
,heap
) *succvec
= graph
->succs
[from
];
1005 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[from
];
1007 constraint_edge_t c
;
1011 /* Merge all the zero weighted predecessor edges. */
1012 if (graph
->zero_weight_preds
[from
])
1014 if (!graph
->zero_weight_preds
[to
])
1015 graph
->zero_weight_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1017 EXECUTE_IF_SET_IN_BITMAP (graph
->zero_weight_preds
[from
], 0, j
, bi
)
1021 bitmap_clear_bit (graph
->zero_weight_succs
[j
], from
);
1022 bitmap_set_bit (graph
->zero_weight_succs
[j
], to
);
1025 bitmap_ior_into (graph
->zero_weight_preds
[to
],
1026 graph
->zero_weight_preds
[from
]);
1029 /* Merge all the zero weighted successor edges. */
1030 if (graph
->zero_weight_succs
[from
])
1032 if (!graph
->zero_weight_succs
[to
])
1033 graph
->zero_weight_succs
[to
] = BITMAP_ALLOC (&ptabitmap_obstack
);
1034 EXECUTE_IF_SET_IN_BITMAP (graph
->zero_weight_succs
[from
], 0, j
, bi
)
1036 bitmap_clear_bit (graph
->zero_weight_preds
[j
], from
);
1037 bitmap_set_bit (graph
->zero_weight_preds
[j
], to
);
1039 bitmap_ior_into (graph
->zero_weight_succs
[to
],
1040 graph
->zero_weight_succs
[from
]);
1043 /* Merge all the nonzero weighted predecessor edges. */
1044 for (i
= 0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
1046 unsigned int d
= c
->dest
;
1050 if (c
->dest
== from
)
1053 add_graph_edge (graph
, to
, d
);
1055 temp
= *(get_graph_weights (graph
, from
, c
->dest
));
1058 weights
= get_graph_weights (graph
, to
, d
);
1060 *weights
= allocate_graph_weights (graph
, to
, d
);
1062 bitmap_ior_into (*weights
, temp
);
1067 /* Merge all the nonzero weighted successor edges. */
1068 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
1070 unsigned int d
= c
->dest
;
1074 if (c
->dest
== from
)
1077 add_graph_edge (graph
, d
, to
);
1079 temp
= *(get_graph_weights (graph
, c
->dest
, from
));
1082 weights
= get_graph_weights (graph
, d
, to
);
1084 *weights
= allocate_graph_weights (graph
, d
, to
);
1085 bitmap_ior_into (*weights
, temp
);
1088 clear_edges_for_node (graph
, from
);
1091 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
1092 it doesn't exist in the graph already.
1093 Return false if the edge already existed, true otherwise. */
1096 int_add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1097 unsigned int from
, unsigned HOST_WIDE_INT weight
)
1099 if (to
== from
&& weight
== 0)
1109 if (!graph
->zero_weight_preds
[to
])
1110 graph
->zero_weight_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1111 if (!graph
->zero_weight_succs
[from
])
1112 graph
->zero_weight_succs
[from
] = BITMAP_ALLOC (&ptabitmap_obstack
);
1113 if (!bitmap_bit_p (graph
->zero_weight_succs
[from
], to
))
1118 bitmap_set_bit (graph
->zero_weight_preds
[to
], from
);
1119 bitmap_set_bit (graph
->zero_weight_succs
[from
], to
);
1126 r
= add_graph_edge (graph
, to
, from
);
1127 weights
= get_graph_weights (graph
, to
, from
);
1132 *weights
= allocate_graph_weights (graph
, to
, from
);
1133 bitmap_set_bit (*weights
, weight
);
1137 r
|= !bitmap_bit_p (*weights
, weight
);
1138 bitmap_set_bit (*weights
, weight
);
1147 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1150 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
1153 struct constraint_edge lookfor
;
1156 return (graph
->zero_weight_succs
[dest
]
1157 && bitmap_bit_p (graph
->zero_weight_succs
[dest
], src
))
1158 || constraint_edge_vec_find (graph
->succs
[dest
], lookfor
) != NULL
;
1161 /* Return true if {DEST, SRC} is an existing weighted graph edge (IE has
1162 a weight other than 0) in GRAPH. */
1164 valid_weighted_graph_edge (constraint_graph_t graph
, unsigned int src
,
1167 struct constraint_edge lookfor
;
1170 return graph
->preds
[src
]
1171 && constraint_edge_vec_find (graph
->succs
[dest
], lookfor
) != NULL
;
1175 /* Build the constraint graph. */
1178 build_constraint_graph (void)
1183 graph
= XNEW (struct constraint_graph
);
1184 graph
->succs
= XCNEWVEC (VEC(constraint_edge_t
,heap
) *, VEC_length (varinfo_t
, varmap
) + 1);
1185 graph
->preds
= XCNEWVEC (VEC(constraint_edge_t
,heap
) *, VEC_length (varinfo_t
, varmap
) + 1);
1186 graph
->zero_weight_succs
= XCNEWVEC (bitmap
, VEC_length (varinfo_t
, varmap
) + 1);
1187 graph
->zero_weight_preds
= XCNEWVEC (bitmap
, VEC_length (varinfo_t
, varmap
) + 1);
1189 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1191 struct constraint_expr lhs
= c
->lhs
;
1192 struct constraint_expr rhs
= c
->rhs
;
1193 unsigned int lhsvar
= get_varinfo_fc (lhs
.var
)->id
;
1194 unsigned int rhsvar
= get_varinfo_fc (rhs
.var
)->id
;
1196 if (lhs
.type
== DEREF
)
1198 /* *x = y or *x = &y (complex) */
1199 if (rhs
.type
== ADDRESSOF
|| rhsvar
> anything_id
)
1200 insert_into_complex (lhsvar
, c
);
1202 else if (rhs
.type
== DEREF
)
1204 /* !special var= *y */
1205 if (!(get_varinfo (lhsvar
)->is_special_var
))
1206 insert_into_complex (rhsvar
, c
);
1208 else if (rhs
.type
== ADDRESSOF
)
1211 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1213 else if (lhsvar
> anything_id
)
1215 /* Ignore 0 weighted self edges, as they can't possibly contribute
1217 if (lhsvar
!= rhsvar
|| rhs
.offset
!= 0 || lhs
.offset
!= 0)
1219 /* x = y (simple) */
1220 int_add_graph_edge (graph
, lhs
.var
, rhs
.var
, rhs
.offset
);
1228 /* Changed variables on the last iteration. */
1229 static unsigned int changed_count
;
1230 static sbitmap changed
;
1232 DEF_VEC_I(unsigned);
1233 DEF_VEC_ALLOC_I(unsigned,heap
);
1236 /* Strongly Connected Component visitation info. */
1241 sbitmap in_component
;
1243 unsigned int *visited_index
;
1244 VEC(unsigned,heap
) *scc_stack
;
1245 VEC(unsigned,heap
) *unification_queue
;
1249 /* Recursive routine to find strongly connected components in GRAPH.
1250 SI is the SCC info to store the information in, and N is the id of current
1251 graph node we are processing.
1253 This is Tarjan's strongly connected component finding algorithm, as
1254 modified by Nuutila to keep only non-root nodes on the stack.
1255 The algorithm can be found in "On finding the strongly connected
1256 connected components in a directed graph" by Esko Nuutila and Eljas
1257 Soisalon-Soininen, in Information Processing Letters volume 49,
1258 number 1, pages 9-14. */
1261 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1266 gcc_assert (get_varinfo (n
)->node
== n
);
1267 SET_BIT (si
->visited
, n
);
1268 RESET_BIT (si
->in_component
, n
);
1269 si
->visited_index
[n
] = si
->current_index
++;
1271 /* Visit all the successors. */
1272 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[n
], 0, i
, bi
)
1275 if (!TEST_BIT (si
->visited
, w
))
1276 scc_visit (graph
, si
, w
);
1277 if (!TEST_BIT (si
->in_component
, w
))
1279 unsigned int t
= get_varinfo (w
)->node
;
1280 unsigned int nnode
= get_varinfo (n
)->node
;
1281 if (si
->visited_index
[t
] < si
->visited_index
[nnode
])
1282 get_varinfo (n
)->node
= t
;
1286 /* See if any components have been identified. */
1287 if (get_varinfo (n
)->node
== n
)
1289 unsigned int t
= si
->visited_index
[n
];
1290 SET_BIT (si
->in_component
, n
);
1291 while (VEC_length (unsigned, si
->scc_stack
) != 0
1292 && t
< si
->visited_index
[VEC_last (unsigned, si
->scc_stack
)])
1294 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1295 get_varinfo (w
)->node
= n
;
1296 SET_BIT (si
->in_component
, w
);
1297 /* Mark this node for collapsing. */
1298 VEC_safe_push (unsigned, heap
, si
->unification_queue
, w
);
1302 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1306 /* Collapse two variables into one variable. */
1309 collapse_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
)
1311 bitmap tosol
, fromsol
;
1313 condense_varmap_nodes (to
, from
);
1314 tosol
= get_varinfo (to
)->solution
;
1315 fromsol
= get_varinfo (from
)->solution
;
1316 bitmap_ior_into (tosol
, fromsol
);
1317 merge_graph_nodes (graph
, to
, from
);
1319 if (valid_graph_edge (graph
, to
, to
))
1321 if (graph
->zero_weight_preds
[to
])
1323 bitmap_clear_bit (graph
->zero_weight_preds
[to
], to
);
1324 bitmap_clear_bit (graph
->zero_weight_succs
[to
], to
);
1326 if (valid_weighted_graph_edge (graph
, to
, to
))
1328 bitmap weights
= *(get_graph_weights (graph
, to
, to
));
1329 if (!weights
|| bitmap_empty_p (weights
))
1330 erase_graph_self_edge (graph
, to
);
1333 BITMAP_FREE (fromsol
);
1334 get_varinfo (to
)->address_taken
|= get_varinfo (from
)->address_taken
;
1335 get_varinfo (to
)->indirect_target
|= get_varinfo (from
)->indirect_target
;
1339 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1340 SI is the Strongly Connected Components information structure that tells us
1341 what components to unify.
1342 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1343 count should be updated to reflect the unification. */
1346 process_unification_queue (constraint_graph_t graph
, struct scc_info
*si
,
1347 bool update_changed
)
1350 bitmap tmp
= BITMAP_ALLOC (update_changed
? &iteration_obstack
: NULL
);
1353 /* We proceed as follows:
1355 For each component in the queue (components are delineated by
1356 when current_queue_element->node != next_queue_element->node):
1358 rep = representative node for component
1360 For each node (tounify) to be unified in the component,
1361 merge the solution for tounify into tmp bitmap
1363 clear solution for tounify
1365 merge edges from tounify into rep
1367 merge complex constraints from tounify into rep
1369 update changed count to note that tounify will never change
1372 Merge tmp into solution for rep, marking rep changed if this
1373 changed rep's solution.
1375 Delete any 0 weighted self-edges we now have for rep. */
1376 while (i
!= VEC_length (unsigned, si
->unification_queue
))
1378 unsigned int tounify
= VEC_index (unsigned, si
->unification_queue
, i
);
1379 unsigned int n
= get_varinfo (tounify
)->node
;
1381 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1382 fprintf (dump_file
, "Unifying %s to %s\n",
1383 get_varinfo (tounify
)->name
,
1384 get_varinfo (n
)->name
);
1386 stats
.unified_vars_dynamic
++;
1388 stats
.unified_vars_static
++;
1389 bitmap_ior_into (tmp
, get_varinfo (tounify
)->solution
);
1390 merge_graph_nodes (graph
, n
, tounify
);
1391 condense_varmap_nodes (n
, tounify
);
1393 if (update_changed
&& TEST_BIT (changed
, tounify
))
1395 RESET_BIT (changed
, tounify
);
1396 if (!TEST_BIT (changed
, n
))
1397 SET_BIT (changed
, n
);
1400 gcc_assert (changed_count
> 0);
1405 bitmap_clear (get_varinfo (tounify
)->solution
);
1408 /* If we've either finished processing the entire queue, or
1409 finished processing all nodes for component n, update the solution for
1411 if (i
== VEC_length (unsigned, si
->unification_queue
)
1412 || get_varinfo (VEC_index (unsigned, si
->unification_queue
, i
))->node
!= n
)
1414 /* If the solution changes because of the merging, we need to mark
1415 the variable as changed. */
1416 if (bitmap_ior_into (get_varinfo (n
)->solution
, tmp
))
1418 if (update_changed
&& !TEST_BIT (changed
, n
))
1420 SET_BIT (changed
, n
);
1426 if (valid_graph_edge (graph
, n
, n
))
1428 if (graph
->zero_weight_succs
[n
])
1430 if (graph
->zero_weight_preds
[n
])
1431 bitmap_clear_bit (graph
->zero_weight_preds
[n
], n
);
1432 bitmap_clear_bit (graph
->zero_weight_succs
[n
], n
);
1434 if (valid_weighted_graph_edge (graph
, n
, n
))
1436 bitmap weights
= *(get_graph_weights (graph
, n
, n
));
1437 if (!weights
|| bitmap_empty_p (weights
))
1438 erase_graph_self_edge (graph
, n
);
1447 /* Information needed to compute the topological ordering of a graph. */
1451 /* sbitmap of visited nodes. */
1453 /* Array that stores the topological order of the graph, *in
1455 VEC(unsigned,heap
) *topo_order
;
1459 /* Initialize and return a topological info structure. */
1461 static struct topo_info
*
1462 init_topo_info (void)
1464 size_t size
= VEC_length (varinfo_t
, varmap
);
1465 struct topo_info
*ti
= XNEW (struct topo_info
);
1466 ti
->visited
= sbitmap_alloc (size
);
1467 sbitmap_zero (ti
->visited
);
1468 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1473 /* Free the topological sort info pointed to by TI. */
1476 free_topo_info (struct topo_info
*ti
)
1478 sbitmap_free (ti
->visited
);
1479 VEC_free (unsigned, heap
, ti
->topo_order
);
1483 /* Visit the graph in topological order, and store the order in the
1484 topo_info structure. */
1487 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1490 VEC(constraint_edge_t
,heap
) *succs
= graph
->succs
[n
];
1493 constraint_edge_t c
;
1497 SET_BIT (ti
->visited
, n
);
1498 if (VEC_length (constraint_edge_t
, succs
) != 0)
1500 temp
= BITMAP_ALLOC (&iteration_obstack
);
1501 if (graph
->zero_weight_succs
[n
])
1502 bitmap_ior_into (temp
, graph
->zero_weight_succs
[n
]);
1503 for (i
= 0; VEC_iterate (constraint_edge_t
, succs
, i
, c
); i
++)
1504 bitmap_set_bit (temp
, c
->dest
);
1507 temp
= graph
->zero_weight_succs
[n
];
1510 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, j
, bi
)
1512 if (!TEST_BIT (ti
->visited
, j
))
1513 topo_visit (graph
, ti
, j
);
1515 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1518 /* Return true if variable N + OFFSET is a legal field of N. */
1521 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1523 varinfo_t ninfo
= get_varinfo (n
);
1525 /* For things we've globbed to single variables, any offset into the
1526 variable acts like the entire variable, so that it becomes offset
1528 if (ninfo
->is_special_var
1529 || ninfo
->is_artificial_var
1530 || ninfo
->is_unknown_size_var
)
1535 return (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1538 /* Process a constraint C that represents *x = &y. */
1541 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1542 constraint_t c
, bitmap delta
)
1544 unsigned int rhs
= c
->rhs
.var
;
1548 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1549 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1551 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1552 if (type_safe (j
, &offset
) && !(get_varinfo (j
)->is_special_var
))
1554 /* *x != NULL && *x != ANYTHING*/
1558 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1560 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1564 sol
= get_varinfo (t
)->solution
;
1565 if (!bitmap_bit_p (sol
, rhs
))
1567 bitmap_set_bit (sol
, rhs
);
1568 if (!TEST_BIT (changed
, t
))
1570 SET_BIT (changed
, t
);
1575 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1576 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1581 /* Process a constraint C that represents x = *y, using DELTA as the
1582 starting solution. */
1585 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1588 unsigned int lhs
= get_varinfo (c
->lhs
.var
)->node
;
1590 bitmap sol
= get_varinfo (lhs
)->solution
;
1594 if (bitmap_bit_p (delta
, anything_id
))
1596 flag
= !bitmap_bit_p (sol
, anything_id
);
1598 bitmap_set_bit (sol
, anything_id
);
1601 /* For each variable j in delta (Sol(y)), add
1602 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1603 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1605 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1606 if (type_safe (j
, &roffset
))
1609 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1612 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1617 /* Adding edges from the special vars is pointless.
1618 They don't have sets that can change. */
1619 if (get_varinfo (t
) ->is_special_var
)
1620 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1621 else if (int_add_graph_edge (graph
, lhs
, t
, 0))
1622 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1624 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1625 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1630 /* If the LHS solution changed, mark the var as changed. */
1633 get_varinfo (lhs
)->solution
= sol
;
1634 if (!TEST_BIT (changed
, lhs
))
1636 SET_BIT (changed
, lhs
);
1642 /* Process a constraint C that represents *x = y. */
1645 do_ds_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1647 unsigned int rhs
= get_varinfo (c
->rhs
.var
)->node
;
1648 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1649 bitmap sol
= get_varinfo (rhs
)->solution
;
1653 if (bitmap_bit_p (sol
, anything_id
))
1655 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1657 varinfo_t jvi
= get_varinfo (j
);
1659 unsigned int loff
= c
->lhs
.offset
;
1660 unsigned HOST_WIDE_INT fieldoffset
= jvi
->offset
+ loff
;
1663 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1668 if (!bitmap_bit_p (get_varinfo (t
)->solution
, anything_id
))
1670 bitmap_set_bit (get_varinfo (t
)->solution
, anything_id
);
1671 if (!TEST_BIT (changed
, t
))
1673 SET_BIT (changed
, t
);
1681 /* For each member j of delta (Sol(x)), add an edge from y to j and
1682 union Sol(y) into Sol(j) */
1683 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1685 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1686 if (type_safe (j
, &loff
) && !(get_varinfo(j
)->is_special_var
))
1690 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1692 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1696 if (int_add_graph_edge (graph
, t
, rhs
, roff
))
1698 bitmap tmp
= get_varinfo (t
)->solution
;
1699 if (set_union_with_increment (tmp
, sol
, roff
))
1701 get_varinfo (t
)->solution
= tmp
;
1703 sol
= get_varinfo (rhs
)->solution
;
1704 if (!TEST_BIT (changed
, t
))
1706 SET_BIT (changed
, t
);
1712 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1713 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1717 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1718 constraint (IE *x = &y, x = *y, and *x = y). */
1721 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1723 if (c
->lhs
.type
== DEREF
)
1725 if (c
->rhs
.type
== ADDRESSOF
)
1728 do_da_constraint (graph
, c
, delta
);
1733 do_ds_constraint (graph
, c
, delta
);
1739 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1740 do_sd_constraint (graph
, c
, delta
);
1744 /* Initialize and return a new SCC info structure. */
1746 static struct scc_info
*
1747 init_scc_info (void)
1749 struct scc_info
*si
= XNEW (struct scc_info
);
1750 size_t size
= VEC_length (varinfo_t
, varmap
);
1752 si
->current_index
= 0;
1753 si
->visited
= sbitmap_alloc (size
);
1754 sbitmap_zero (si
->visited
);
1755 si
->in_component
= sbitmap_alloc (size
);
1756 sbitmap_ones (si
->in_component
);
1757 si
->visited_index
= XCNEWVEC (unsigned int, size
+ 1);
1758 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1759 si
->unification_queue
= VEC_alloc (unsigned, heap
, 1);
1763 /* Free an SCC info structure pointed to by SI */
1766 free_scc_info (struct scc_info
*si
)
1768 sbitmap_free (si
->visited
);
1769 sbitmap_free (si
->in_component
);
1770 free (si
->visited_index
);
1771 VEC_free (unsigned, heap
, si
->scc_stack
);
1772 VEC_free (unsigned, heap
, si
->unification_queue
);
1777 /* Find cycles in GRAPH that occur, using strongly connected components, and
1778 collapse the cycles into a single representative node. if UPDATE_CHANGED
1779 is true, then update the changed sbitmap to note those nodes whose
1780 solutions have changed as a result of collapsing. */
1783 find_and_collapse_graph_cycles (constraint_graph_t graph
, bool update_changed
)
1786 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1787 struct scc_info
*si
= init_scc_info ();
1789 for (i
= 0; i
!= size
; ++i
)
1790 if (!TEST_BIT (si
->visited
, i
) && get_varinfo (i
)->node
== i
)
1791 scc_visit (graph
, si
, i
);
1793 process_unification_queue (graph
, si
, update_changed
);
1797 /* Compute a topological ordering for GRAPH, and store the result in the
1798 topo_info structure TI. */
1801 compute_topo_order (constraint_graph_t graph
,
1802 struct topo_info
*ti
)
1805 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1807 for (i
= 0; i
!= size
; ++i
)
1808 if (!TEST_BIT (ti
->visited
, i
) && get_varinfo (i
)->node
== i
)
1809 topo_visit (graph
, ti
, i
);
1812 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1815 bitmap_other_than_zero_bit_set (bitmap b
)
1820 if (bitmap_empty_p (b
))
1822 EXECUTE_IF_SET_IN_BITMAP (b
, 1, i
, bi
)
1827 /* Perform offline variable substitution.
1829 This is a linear time way of identifying variables that must have
1830 equivalent points-to sets, including those caused by static cycles,
1831 and single entry subgraphs, in the constraint graph.
1833 The technique is described in "Off-line variable substitution for
1834 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1835 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1838 perform_var_substitution (constraint_graph_t graph
)
1840 struct topo_info
*ti
= init_topo_info ();
1842 bitmap_obstack_initialize (&iteration_obstack
);
1843 /* Compute the topological ordering of the graph, then visit each
1844 node in topological order. */
1845 compute_topo_order (graph
, ti
);
1847 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1849 unsigned int i
= VEC_pop (unsigned, ti
->topo_order
);
1851 varinfo_t vi
= get_varinfo (i
);
1852 bool okay_to_elim
= false;
1853 unsigned int root
= VEC_length (varinfo_t
, varmap
);
1854 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[i
];
1855 constraint_edge_t ce
= NULL
;
1860 /* We can't eliminate things whose address is taken, or which is
1861 the target of a dereference. */
1862 if (vi
->address_taken
|| vi
->indirect_target
)
1865 /* See if all predecessors of I are ripe for elimination */
1866 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_preds
[i
], 0, k
, bi
)
1869 w
= get_varinfo (k
)->node
;
1871 /* We can't eliminate the node if one of the predecessors is
1872 part of a different strongly connected component. */
1876 okay_to_elim
= true;
1880 okay_to_elim
= false;
1884 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1885 then Solution(i) is a subset of Solution (w), where w is a
1886 predecessor in the graph.
1887 Corollary: If all predecessors of i have the same
1888 points-to set, then i has that same points-to set as
1889 those predecessors. */
1890 tmp
= BITMAP_ALLOC (NULL
);
1891 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1892 get_varinfo (w
)->solution
);
1893 if (!bitmap_empty_p (tmp
))
1895 okay_to_elim
= false;
1904 VEC_iterate (constraint_edge_t
, predvec
, pred
, ce
);
1909 weight
= *(get_graph_weights (graph
, i
, ce
->dest
));
1911 /* We can't eliminate variables that have nonzero weighted
1912 edges between them. */
1913 if (weight
&& bitmap_other_than_zero_bit_set (weight
))
1915 okay_to_elim
= false;
1918 w
= get_varinfo (ce
->dest
)->node
;
1920 /* We can't eliminate the node if one of the predecessors is
1921 part of a different strongly connected component. */
1925 okay_to_elim
= true;
1929 okay_to_elim
= false;
1933 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1934 then Solution(i) is a subset of Solution (w), where w is a
1935 predecessor in the graph.
1936 Corollary: If all predecessors of i have the same
1937 points-to set, then i has that same points-to set as
1938 those predecessors. */
1939 tmp
= BITMAP_ALLOC (NULL
);
1940 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1941 get_varinfo (w
)->solution
);
1942 if (!bitmap_empty_p (tmp
))
1944 okay_to_elim
= false;
1951 /* See if the root is different than the original node.
1952 If so, we've found an equivalence. */
1953 if (root
!= get_varinfo (i
)->node
&& okay_to_elim
)
1955 /* Found an equivalence */
1956 get_varinfo (i
)->node
= root
;
1957 collapse_nodes (graph
, root
, i
);
1958 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1959 fprintf (dump_file
, "Collapsing %s into %s\n",
1960 get_varinfo (i
)->name
,
1961 get_varinfo (root
)->name
);
1962 stats
.collapsed_vars
++;
1966 bitmap_obstack_release (&iteration_obstack
);
1967 free_topo_info (ti
);
1970 /* Solve the constraint graph GRAPH using our worklist solver.
1971 This is based on the PW* family of solvers from the "Efficient Field
1972 Sensitive Pointer Analysis for C" paper.
1973 It works by iterating over all the graph nodes, processing the complex
1974 constraints and propagating the copy constraints, until everything stops
1975 changed. This corresponds to steps 6-8 in the solving list given above. */
1978 solve_graph (constraint_graph_t graph
)
1980 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1983 changed_count
= size
;
1984 changed
= sbitmap_alloc (size
);
1985 sbitmap_ones (changed
);
1987 /* The already collapsed/unreachable nodes will never change, so we
1988 need to account for them in changed_count. */
1989 for (i
= 0; i
< size
; i
++)
1990 if (get_varinfo (i
)->node
!= i
)
1993 while (changed_count
> 0)
1996 struct topo_info
*ti
= init_topo_info ();
1999 bitmap_obstack_initialize (&iteration_obstack
);
2003 /* We already did cycle elimination once, when we did
2004 variable substitution, so we don't need it again for the
2006 if (stats
.iterations
> 1)
2007 find_and_collapse_graph_cycles (graph
, true);
2012 compute_topo_order (graph
, ti
);
2014 while (VEC_length (unsigned, ti
->topo_order
) != 0)
2016 i
= VEC_pop (unsigned, ti
->topo_order
);
2017 gcc_assert (get_varinfo (i
)->node
== i
);
2019 /* If the node has changed, we need to process the
2020 complex constraints and outgoing edges again. */
2021 if (TEST_BIT (changed
, i
))
2025 constraint_edge_t e
= NULL
;
2028 VEC(constraint_t
,heap
) *complex = get_varinfo (i
)->complex;
2029 VEC(constraint_edge_t
,heap
) *succs
;
2031 RESET_BIT (changed
, i
);
2034 /* Process the complex constraints */
2035 solution
= get_varinfo (i
)->solution
;
2036 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
2037 do_complex_constraint (graph
, c
, solution
);
2039 /* Propagate solution to all successors. */
2040 succs
= graph
->succs
[i
];
2042 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[i
], 0, j
, bi
)
2044 bitmap tmp
= get_varinfo (j
)->solution
;
2047 flag
= set_union_with_increment (tmp
, solution
, 0);
2051 get_varinfo (j
)->solution
= tmp
;
2052 if (!TEST_BIT (changed
, j
))
2054 SET_BIT (changed
, j
);
2059 for (j
= 0; VEC_iterate (constraint_edge_t
, succs
, j
, e
); j
++)
2061 bitmap tmp
= get_varinfo (e
->dest
)->solution
;
2064 bitmap weights
= e
->weights
;
2067 gcc_assert (weights
&& !bitmap_empty_p (weights
));
2068 EXECUTE_IF_SET_IN_BITMAP (weights
, 0, k
, bi
)
2069 flag
|= set_union_with_increment (tmp
, solution
, k
);
2073 get_varinfo (e
->dest
)->solution
= tmp
;
2074 if (!TEST_BIT (changed
, e
->dest
))
2076 SET_BIT (changed
, e
->dest
);
2083 free_topo_info (ti
);
2084 bitmap_obstack_release (&iteration_obstack
);
2087 sbitmap_free (changed
);
2091 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2093 /* Map from trees to variable ids. */
2094 static htab_t id_for_tree
;
2096 typedef struct tree_id
2102 /* Hash a tree id structure. */
2105 tree_id_hash (const void *p
)
2107 const tree_id_t ta
= (tree_id_t
) p
;
2108 return htab_hash_pointer (ta
->t
);
2111 /* Return true if the tree in P1 and the tree in P2 are the same. */
2114 tree_id_eq (const void *p1
, const void *p2
)
2116 const tree_id_t ta1
= (tree_id_t
) p1
;
2117 const tree_id_t ta2
= (tree_id_t
) p2
;
2118 return ta1
->t
== ta2
->t
;
2121 /* Insert ID as the variable id for tree T in the hashtable. */
2124 insert_id_for_tree (tree t
, int id
)
2127 struct tree_id finder
;
2131 slot
= htab_find_slot (id_for_tree
, &finder
, INSERT
);
2132 gcc_assert (*slot
== NULL
);
2133 new_pair
= XNEW (struct tree_id
);
2136 *slot
= (void *)new_pair
;
2139 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
2140 exist in the hash table, return false, otherwise, return true and
2141 set *ID to the id we found. */
2144 lookup_id_for_tree (tree t
, unsigned int *id
)
2147 struct tree_id finder
;
2150 pair
= htab_find (id_for_tree
, &finder
);
2157 /* Return a printable name for DECL */
2160 alias_get_name (tree decl
)
2162 const char *res
= get_name (decl
);
2164 int num_printed
= 0;
2170 if (TREE_CODE (decl
) == SSA_NAME
)
2172 num_printed
= asprintf (&temp
, "%s_%u",
2173 alias_get_name (SSA_NAME_VAR (decl
)),
2174 SSA_NAME_VERSION (decl
));
2176 else if (DECL_P (decl
))
2178 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2180 if (num_printed
> 0)
2182 res
= ggc_strdup (temp
);
2188 /* Find the variable id for tree T in the hashtable.
2189 If T doesn't exist in the hash table, create an entry for it. */
2192 get_id_for_tree (tree t
)
2195 struct tree_id finder
;
2198 pair
= htab_find (id_for_tree
, &finder
);
2200 return create_variable_info_for (t
, alias_get_name (t
));
2205 /* Get a constraint expression from an SSA_VAR_P node. */
2207 static struct constraint_expr
2208 get_constraint_exp_from_ssa_var (tree t
)
2210 struct constraint_expr cexpr
;
2212 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
2214 /* For parameters, get at the points-to set for the actual parm
2216 if (TREE_CODE (t
) == SSA_NAME
2217 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2218 && default_def (SSA_NAME_VAR (t
)) == t
)
2219 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
2221 cexpr
.type
= SCALAR
;
2223 cexpr
.var
= get_id_for_tree (t
);
2224 /* If we determine the result is "anything", and we know this is readonly,
2225 say it points to readonly memory instead. */
2226 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
2228 cexpr
.type
= ADDRESSOF
;
2229 cexpr
.var
= readonly_id
;
2236 /* Process a completed constraint T, and add it to the constraint
2240 process_constraint (constraint_t t
)
2242 struct constraint_expr rhs
= t
->rhs
;
2243 struct constraint_expr lhs
= t
->lhs
;
2245 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
2246 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
2248 /* ANYTHING == ANYTHING is pointless. */
2249 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
2252 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2253 else if (lhs
.var
== anything_id
&& lhs
.type
== ADDRESSOF
)
2258 process_constraint (t
);
2260 /* This can happen in our IR with things like n->a = *p */
2261 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
2263 /* Split into tmp = *rhs, *lhs = tmp */
2264 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
2265 tree pointertype
= TREE_TYPE (rhsdecl
);
2266 tree pointedtotype
= TREE_TYPE (pointertype
);
2267 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
2268 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2270 /* If this is an aggregate of known size, we should have passed
2271 this off to do_structure_copy, and it should have broken it
2273 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
2274 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
2276 process_constraint (new_constraint (tmplhs
, rhs
));
2277 process_constraint (new_constraint (lhs
, tmplhs
));
2279 else if (rhs
.type
== ADDRESSOF
)
2282 gcc_assert (rhs
.offset
== 0);
2284 for (vi
= get_varinfo (rhs
.var
); vi
!= NULL
; vi
= vi
->next
)
2285 vi
->address_taken
= true;
2287 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2291 if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2292 get_varinfo (lhs
.var
)->indirect_target
= true;
2293 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2298 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2301 static unsigned HOST_WIDE_INT
2302 bitpos_of_field (const tree fdecl
)
2305 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
2306 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
2309 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
2310 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
2314 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2315 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2318 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
2319 const unsigned HOST_WIDE_INT fieldsize
,
2320 const unsigned HOST_WIDE_INT accesspos
,
2321 const unsigned HOST_WIDE_INT accesssize
)
2323 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
2325 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
2327 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
2333 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2336 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
)
2339 HOST_WIDE_INT bitsize
= -1;
2340 HOST_WIDE_INT bitmaxsize
= -1;
2341 HOST_WIDE_INT bitpos
;
2343 struct constraint_expr
*result
;
2344 unsigned int beforelength
= VEC_length (ce_s
, *results
);
2346 /* Some people like to do cute things like take the address of
2349 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
2350 forzero
= TREE_OPERAND (forzero
, 0);
2352 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
2354 struct constraint_expr temp
;
2357 temp
.var
= integer_id
;
2359 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2363 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
2364 get_constraint_for (t
, results
);
2365 result
= VEC_last (ce_s
, *results
);
2366 result
->offset
= bitpos
;
2368 gcc_assert (beforelength
+ 1 == VEC_length (ce_s
, *results
));
2370 /* This can also happen due to weird offsetof type macros. */
2371 if (TREE_CODE (t
) != ADDR_EXPR
&& result
->type
== ADDRESSOF
)
2372 result
->type
= SCALAR
;
2374 if (result
->type
== SCALAR
)
2376 /* In languages like C, you can access one past the end of an
2377 array. You aren't allowed to dereference it, so we can
2378 ignore this constraint. When we handle pointer subtraction,
2379 we may have to do something cute here. */
2381 if (result
->offset
< get_varinfo (result
->var
)->fullsize
2384 /* It's also not true that the constraint will actually start at the
2385 right offset, it may start in some padding. We only care about
2386 setting the constraint to the first actual field it touches, so
2389 for (curr
= get_varinfo (result
->var
); curr
; curr
= curr
->next
)
2391 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2392 result
->offset
, bitmaxsize
))
2394 result
->var
= curr
->id
;
2398 /* assert that we found *some* field there. The user couldn't be
2399 accessing *only* padding. */
2400 /* Still the user could access one past the end of an array
2401 embedded in a struct resulting in accessing *only* padding. */
2402 gcc_assert (curr
|| ref_contains_array_ref (orig_t
));
2404 else if (bitmaxsize
== 0)
2406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2407 fprintf (dump_file
, "Access to zero-sized part of variable,"
2411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2412 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2419 /* Dereference the constraint expression CONS, and return the result.
2420 DEREF (ADDRESSOF) = SCALAR
2421 DEREF (SCALAR) = DEREF
2422 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2423 This is needed so that we can handle dereferencing DEREF constraints. */
2426 do_deref (VEC (ce_s
, heap
) **constraints
)
2428 struct constraint_expr
*c
;
2430 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
2432 if (c
->type
== SCALAR
)
2434 else if (c
->type
== ADDRESSOF
)
2436 else if (c
->type
== DEREF
)
2438 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "dereftmp");
2439 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2440 process_constraint (new_constraint (tmplhs
, *c
));
2441 c
->var
= tmplhs
.var
;
2449 /* Given a tree T, return the constraint expression for it. */
2452 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
2454 struct constraint_expr temp
;
2456 /* x = integer is all glommed to a single variable, which doesn't
2457 point to anything by itself. That is, of course, unless it is an
2458 integer constant being treated as a pointer, in which case, we
2459 will return that this is really the addressof anything. This
2460 happens below, since it will fall into the default case. The only
2461 case we know something about an integer treated like a pointer is
2462 when it is the NULL pointer, and then we just say it points to
2464 if (TREE_CODE (t
) == INTEGER_CST
2465 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2467 temp
.var
= integer_id
;
2470 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2473 else if (TREE_CODE (t
) == INTEGER_CST
2474 && integer_zerop (t
))
2476 temp
.var
= nothing_id
;
2477 temp
.type
= ADDRESSOF
;
2479 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2483 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2485 case tcc_expression
:
2487 switch (TREE_CODE (t
))
2491 struct constraint_expr
*c
;
2493 tree exp
= TREE_OPERAND (t
, 0);
2494 tree pttype
= TREE_TYPE (TREE_TYPE (t
));
2496 get_constraint_for (exp
, results
);
2497 /* Make sure we capture constraints to all elements
2499 if ((handled_component_p (exp
)
2500 && ref_contains_array_ref (exp
))
2501 || TREE_CODE (TREE_TYPE (exp
)) == ARRAY_TYPE
)
2503 struct constraint_expr
*origrhs
;
2505 struct constraint_expr tmp
;
2507 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2508 origrhs
= VEC_last (ce_s
, *results
);
2510 VEC_pop (ce_s
, *results
);
2511 origvar
= get_varinfo (origrhs
->var
);
2512 for (; origvar
; origvar
= origvar
->next
)
2514 tmp
.var
= origvar
->id
;
2515 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2518 else if (VEC_length (ce_s
, *results
) == 1
2519 && (AGGREGATE_TYPE_P (pttype
)
2520 || TREE_CODE (pttype
) == COMPLEX_TYPE
))
2522 struct constraint_expr
*origrhs
;
2524 struct constraint_expr tmp
;
2526 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2527 origrhs
= VEC_last (ce_s
, *results
);
2529 VEC_pop (ce_s
, *results
);
2530 origvar
= get_varinfo (origrhs
->var
);
2531 for (; origvar
; origvar
= origvar
->next
)
2533 tmp
.var
= origvar
->id
;
2534 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2538 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
2540 if (c
->type
== DEREF
)
2543 c
->type
= ADDRESSOF
;
2550 /* XXX: In interprocedural mode, if we didn't have the
2551 body, we would need to do *each pointer argument =
2553 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2556 tree heapvar
= heapvar_lookup (t
);
2558 if (heapvar
== NULL
)
2560 heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2561 DECL_EXTERNAL (heapvar
) = 1;
2562 if (referenced_vars
)
2563 add_referenced_var (heapvar
);
2564 heapvar_insert (t
, heapvar
);
2567 temp
.var
= create_variable_info_for (heapvar
,
2568 alias_get_name (heapvar
));
2570 vi
= get_varinfo (temp
.var
);
2571 vi
->is_artificial_var
= 1;
2572 vi
->is_heap_var
= 1;
2573 temp
.type
= ADDRESSOF
;
2575 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2581 temp
.type
= ADDRESSOF
;
2582 temp
.var
= anything_id
;
2584 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2591 switch (TREE_CODE (t
))
2595 get_constraint_for (TREE_OPERAND (t
, 0), results
);
2600 case ARRAY_RANGE_REF
:
2602 get_constraint_for_component_ref (t
, results
);
2606 temp
.type
= ADDRESSOF
;
2607 temp
.var
= anything_id
;
2609 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2616 switch (TREE_CODE (t
))
2620 case NON_LVALUE_EXPR
:
2622 tree op
= TREE_OPERAND (t
, 0);
2624 /* Cast from non-pointer to pointers are bad news for us.
2625 Anything else, we see through */
2626 if (!(POINTER_TYPE_P (TREE_TYPE (t
))
2627 && ! POINTER_TYPE_P (TREE_TYPE (op
))))
2629 get_constraint_for (op
, results
);
2637 temp
.type
= ADDRESSOF
;
2638 temp
.var
= anything_id
;
2640 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2645 case tcc_exceptional
:
2647 switch (TREE_CODE (t
))
2651 get_constraint_for (PHI_RESULT (t
), results
);
2657 struct constraint_expr temp
;
2658 temp
= get_constraint_exp_from_ssa_var (t
);
2659 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2665 temp
.type
= ADDRESSOF
;
2666 temp
.var
= anything_id
;
2668 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2673 case tcc_declaration
:
2675 struct constraint_expr temp
;
2676 temp
= get_constraint_exp_from_ssa_var (t
);
2677 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2682 temp
.type
= ADDRESSOF
;
2683 temp
.var
= anything_id
;
2685 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2692 /* Handle the structure copy case where we have a simple structure copy
2693 between LHS and RHS that is of SIZE (in bits)
2695 For each field of the lhs variable (lhsfield)
2696 For each field of the rhs variable at lhsfield.offset (rhsfield)
2697 add the constraint lhsfield = rhsfield
2699 If we fail due to some kind of type unsafety or other thing we
2700 can't handle, return false. We expect the caller to collapse the
2701 variable in that case. */
2704 do_simple_structure_copy (const struct constraint_expr lhs
,
2705 const struct constraint_expr rhs
,
2706 const unsigned HOST_WIDE_INT size
)
2708 varinfo_t p
= get_varinfo (lhs
.var
);
2709 unsigned HOST_WIDE_INT pstart
, last
;
2711 last
= p
->offset
+ size
;
2712 for (; p
&& p
->offset
< last
; p
= p
->next
)
2715 struct constraint_expr templhs
= lhs
;
2716 struct constraint_expr temprhs
= rhs
;
2717 unsigned HOST_WIDE_INT fieldoffset
;
2719 templhs
.var
= p
->id
;
2720 q
= get_varinfo (temprhs
.var
);
2721 fieldoffset
= p
->offset
- pstart
;
2722 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2725 temprhs
.var
= q
->id
;
2726 process_constraint (new_constraint (templhs
, temprhs
));
2732 /* Handle the structure copy case where we have a structure copy between a
2733 aggregate on the LHS and a dereference of a pointer on the RHS
2734 that is of SIZE (in bits)
2736 For each field of the lhs variable (lhsfield)
2737 rhs.offset = lhsfield->offset
2738 add the constraint lhsfield = rhs
2742 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2743 const struct constraint_expr rhs
,
2744 const unsigned HOST_WIDE_INT size
)
2746 varinfo_t p
= get_varinfo (lhs
.var
);
2747 unsigned HOST_WIDE_INT pstart
,last
;
2749 last
= p
->offset
+ size
;
2751 for (; p
&& p
->offset
< last
; p
= p
->next
)
2754 struct constraint_expr templhs
= lhs
;
2755 struct constraint_expr temprhs
= rhs
;
2756 unsigned HOST_WIDE_INT fieldoffset
;
2759 if (templhs
.type
== SCALAR
)
2760 templhs
.var
= p
->id
;
2762 templhs
.offset
= p
->offset
;
2764 q
= get_varinfo (temprhs
.var
);
2765 fieldoffset
= p
->offset
- pstart
;
2766 temprhs
.offset
+= fieldoffset
;
2767 process_constraint (new_constraint (templhs
, temprhs
));
2771 /* Handle the structure copy case where we have a structure copy
2772 between a aggregate on the RHS and a dereference of a pointer on
2773 the LHS that is of SIZE (in bits)
2775 For each field of the rhs variable (rhsfield)
2776 lhs.offset = rhsfield->offset
2777 add the constraint lhs = rhsfield
2781 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2782 const struct constraint_expr rhs
,
2783 const unsigned HOST_WIDE_INT size
)
2785 varinfo_t p
= get_varinfo (rhs
.var
);
2786 unsigned HOST_WIDE_INT pstart
,last
;
2788 last
= p
->offset
+ size
;
2790 for (; p
&& p
->offset
< last
; p
= p
->next
)
2793 struct constraint_expr templhs
= lhs
;
2794 struct constraint_expr temprhs
= rhs
;
2795 unsigned HOST_WIDE_INT fieldoffset
;
2798 if (temprhs
.type
== SCALAR
)
2799 temprhs
.var
= p
->id
;
2801 temprhs
.offset
= p
->offset
;
2803 q
= get_varinfo (templhs
.var
);
2804 fieldoffset
= p
->offset
- pstart
;
2805 templhs
.offset
+= fieldoffset
;
2806 process_constraint (new_constraint (templhs
, temprhs
));
2810 /* Sometimes, frontends like to give us bad type information. This
2811 function will collapse all the fields from VAR to the end of VAR,
2812 into VAR, so that we treat those fields as a single variable.
2813 We return the variable they were collapsed into. */
2816 collapse_rest_of_var (unsigned int var
)
2818 varinfo_t currvar
= get_varinfo (var
);
2821 for (field
= currvar
->next
; field
; field
= field
->next
)
2824 fprintf (dump_file
, "Type safety: Collapsing var %s into %s\n",
2825 field
->name
, currvar
->name
);
2827 gcc_assert (!field
->collapsed_to
);
2828 field
->collapsed_to
= currvar
;
2831 currvar
->next
= NULL
;
2832 currvar
->size
= currvar
->fullsize
- currvar
->offset
;
2837 /* Handle aggregate copies by expanding into copies of the respective
2838 fields of the structures. */
2841 do_structure_copy (tree lhsop
, tree rhsop
)
2843 struct constraint_expr lhs
, rhs
, tmp
;
2844 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
2846 unsigned HOST_WIDE_INT lhssize
;
2847 unsigned HOST_WIDE_INT rhssize
;
2849 get_constraint_for (lhsop
, &lhsc
);
2850 get_constraint_for (rhsop
, &rhsc
);
2851 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
2852 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
2853 lhs
= *(VEC_last (ce_s
, lhsc
));
2854 rhs
= *(VEC_last (ce_s
, rhsc
));
2856 VEC_free (ce_s
, heap
, lhsc
);
2857 VEC_free (ce_s
, heap
, rhsc
);
2859 /* If we have special var = x, swap it around. */
2860 if (lhs
.var
<= integer_id
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2867 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2868 possible it's something we could handle. However, most cases falling
2869 into this are dealing with transparent unions, which are slightly
2871 if (rhs
.type
== ADDRESSOF
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2873 rhs
.type
= ADDRESSOF
;
2874 rhs
.var
= anything_id
;
2877 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2878 that special var. */
2879 if (rhs
.var
<= integer_id
)
2881 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2883 struct constraint_expr templhs
= lhs
;
2884 struct constraint_expr temprhs
= rhs
;
2886 if (templhs
.type
== SCALAR
)
2887 templhs
.var
= p
->id
;
2889 templhs
.offset
+= p
->offset
;
2890 process_constraint (new_constraint (templhs
, temprhs
));
2895 tree rhstype
= TREE_TYPE (rhsop
);
2896 tree lhstype
= TREE_TYPE (lhsop
);
2900 lhstypesize
= DECL_P (lhsop
) ? DECL_SIZE (lhsop
) : TYPE_SIZE (lhstype
);
2901 rhstypesize
= DECL_P (rhsop
) ? DECL_SIZE (rhsop
) : TYPE_SIZE (rhstype
);
2903 /* If we have a variably sized types on the rhs or lhs, and a deref
2904 constraint, add the constraint, lhsconstraint = &ANYTHING.
2905 This is conservatively correct because either the lhs is an unknown
2906 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2907 constraint, and every variable it can point to must be unknown sized
2908 anyway, so we don't need to worry about fields at all. */
2909 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
2910 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
2912 rhs
.var
= anything_id
;
2913 rhs
.type
= ADDRESSOF
;
2915 process_constraint (new_constraint (lhs
, rhs
));
2919 /* The size only really matters insofar as we don't set more or less of
2920 the variable. If we hit an unknown size var, the size should be the
2921 whole darn thing. */
2922 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
2925 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
2927 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
2930 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
2933 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
2935 if (!do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
)))
2937 lhs
.var
= collapse_rest_of_var (lhs
.var
);
2938 rhs
.var
= collapse_rest_of_var (rhs
.var
);
2943 process_constraint (new_constraint (lhs
, rhs
));
2946 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2947 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2948 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
2949 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2952 tree pointedtotype
= lhstype
;
2955 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
2956 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
2957 do_structure_copy (tmpvar
, rhsop
);
2958 do_structure_copy (lhsop
, tmpvar
);
2963 /* Update related alias information kept in AI. This is used when
2964 building name tags, alias sets and deciding grouping heuristics.
2965 STMT is the statement to process. This function also updates
2966 ADDRESSABLE_VARS. */
2969 update_alias_info (tree stmt
, struct alias_info
*ai
)
2972 use_operand_p use_p
;
2974 enum escape_type stmt_escape_type
= is_escape_site (stmt
, ai
);
2977 /* Mark all the variables whose address are taken by the statement. */
2978 addr_taken
= addresses_taken (stmt
);
2981 bitmap_ior_into (addressable_vars
, addr_taken
);
2983 /* If STMT is an escape point, all the addresses taken by it are
2985 if (stmt_escape_type
!= NO_ESCAPE
)
2990 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
2992 tree rvar
= referenced_var (i
);
2993 if (!unmodifiable_var_p (rvar
))
2994 mark_call_clobbered (rvar
, stmt_escape_type
);
2999 /* Process each operand use. If an operand may be aliased, keep
3000 track of how many times it's being used. For pointers, determine
3001 whether they are dereferenced by the statement, or whether their
3002 value escapes, etc. */
3003 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
3007 struct ptr_info_def
*pi
;
3008 bool is_store
, is_potential_deref
;
3009 unsigned num_uses
, num_derefs
;
3011 op
= USE_FROM_PTR (use_p
);
3013 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3014 to the set of addressable variables. */
3015 if (TREE_CODE (op
) == ADDR_EXPR
)
3017 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
);
3019 /* PHI nodes don't have annotations for pinning the set
3020 of addresses taken, so we collect them here.
3022 FIXME, should we allow PHI nodes to have annotations
3023 so that they can be treated like regular statements?
3024 Currently, they are treated as second-class
3026 add_to_addressable_set (TREE_OPERAND (op
, 0), &addressable_vars
);
3030 /* Ignore constants. */
3031 if (TREE_CODE (op
) != SSA_NAME
)
3034 var
= SSA_NAME_VAR (op
);
3035 v_ann
= var_ann (var
);
3037 /* The base variable of an ssa name must be a GIMPLE register, and thus
3038 it cannot be aliased. */
3039 gcc_assert (!may_be_aliased (var
));
3041 /* We are only interested in pointers. */
3042 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
3045 pi
= get_ptr_info (op
);
3047 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3048 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
)))
3050 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
));
3051 VEC_safe_push (tree
, heap
, ai
->processed_ptrs
, op
);
3054 /* If STMT is a PHI node, then it will not have pointer
3055 dereferences and it will not be an escape point. */
3056 if (TREE_CODE (stmt
) == PHI_NODE
)
3059 /* Determine whether OP is a dereferenced pointer, and if STMT
3060 is an escape point, whether OP escapes. */
3061 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
3063 /* Handle a corner case involving address expressions of the
3064 form '&PTR->FLD'. The problem with these expressions is that
3065 they do not represent a dereference of PTR. However, if some
3066 other transformation propagates them into an INDIRECT_REF
3067 expression, we end up with '*(&PTR->FLD)' which is folded
3070 So, if the original code had no other dereferences of PTR,
3071 the aliaser will not create memory tags for it, and when
3072 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3073 memory operations will receive no V_MAY_DEF/VUSE operands.
3075 One solution would be to have count_uses_and_derefs consider
3076 &PTR->FLD a dereference of PTR. But that is wrong, since it
3077 is not really a dereference but an offset calculation.
3079 What we do here is to recognize these special ADDR_EXPR
3080 nodes. Since these expressions are never GIMPLE values (they
3081 are not GIMPLE invariants), they can only appear on the RHS
3082 of an assignment and their base address is always an
3083 INDIRECT_REF expression. */
3084 is_potential_deref
= false;
3085 if (TREE_CODE (stmt
) == MODIFY_EXPR
3086 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ADDR_EXPR
3087 && !is_gimple_val (TREE_OPERAND (stmt
, 1)))
3089 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3090 this represents a potential dereference of PTR. */
3091 tree rhs
= TREE_OPERAND (stmt
, 1);
3092 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
3093 if (TREE_CODE (base
) == INDIRECT_REF
3094 && TREE_OPERAND (base
, 0) == op
)
3095 is_potential_deref
= true;
3098 if (num_derefs
> 0 || is_potential_deref
)
3100 /* Mark OP as dereferenced. In a subsequent pass,
3101 dereferenced pointers that point to a set of
3102 variables will be assigned a name tag to alias
3103 all the variables OP points to. */
3104 pi
->is_dereferenced
= 1;
3106 /* Keep track of how many time we've dereferenced each
3108 NUM_REFERENCES_INC (v_ann
);
3110 /* If this is a store operation, mark OP as being
3111 dereferenced to store, otherwise mark it as being
3112 dereferenced to load. */
3114 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
3116 bitmap_set_bit (ai
->dereferenced_ptrs_load
, DECL_UID (var
));
3119 if (stmt_escape_type
!= NO_ESCAPE
&& num_derefs
< num_uses
)
3121 /* If STMT is an escape point and STMT contains at
3122 least one direct use of OP, then the value of OP
3123 escapes and so the pointed-to variables need to
3124 be marked call-clobbered. */
3125 pi
->value_escapes_p
= 1;
3126 pi
->escape_mask
|= stmt_escape_type
;
3128 /* If the statement makes a function call, assume
3129 that pointer OP will be dereferenced in a store
3130 operation inside the called function. */
3131 if (get_call_expr_in (stmt
))
3133 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
3134 pi
->is_dereferenced
= 1;
3139 if (TREE_CODE (stmt
) == PHI_NODE
)
3142 /* Update reference counter for definitions to any
3143 potentially aliased variable. This is used in the alias
3144 grouping heuristics. */
3145 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3147 tree var
= SSA_NAME_VAR (op
);
3148 var_ann_t ann
= var_ann (var
);
3149 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
3150 if (may_be_aliased (var
))
3151 NUM_REFERENCES_INC (ann
);
3155 /* Mark variables in V_MAY_DEF operands as being written to. */
3156 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
3158 tree var
= DECL_P (op
) ? op
: SSA_NAME_VAR (op
);
3159 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
3164 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3165 Expressions of the type PTR + CST can be handled in two ways:
3167 1- If the constraint for PTR is ADDRESSOF for a non-structure
3168 variable, then we can use it directly because adding or
3169 subtracting a constant may not alter the original ADDRESSOF
3170 constraint (i.e., pointer arithmetic may not legally go outside
3171 an object's boundaries).
3173 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3174 then if CST is a compile-time constant that can be used as an
3175 offset, we can determine which sub-variable will be pointed-to
3178 Return true if the expression is handled. For any other kind of
3179 expression, return false so that each operand can be added as a
3180 separate constraint by the caller. */
3183 handle_ptr_arith (VEC (ce_s
, heap
) *lhsc
, tree expr
)
3186 struct constraint_expr
*c
, *c2
;
3189 VEC (ce_s
, heap
) *temp
= NULL
;
3190 unsigned int rhsoffset
= 0;
3192 if (TREE_CODE (expr
) != PLUS_EXPR
3193 && TREE_CODE (expr
) != MINUS_EXPR
)
3196 op0
= TREE_OPERAND (expr
, 0);
3197 op1
= TREE_OPERAND (expr
, 1);
3199 get_constraint_for (op0
, &temp
);
3200 if (POINTER_TYPE_P (TREE_TYPE (op0
))
3201 && TREE_CODE (op1
) == INTEGER_CST
3202 && TREE_CODE (expr
) == PLUS_EXPR
)
3204 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
3208 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
3209 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
3211 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
3213 varinfo_t temp
= get_varinfo (c2
->var
);
3215 /* An access one after the end of an array is valid,
3216 so simply punt on accesses we cannot resolve. */
3217 temp
= first_vi_for_offset (temp
, rhsoffset
);
3224 c2
->offset
= rhsoffset
;
3225 process_constraint (new_constraint (*c
, *c2
));
3228 VEC_free (ce_s
, heap
, temp
);
3234 /* Walk statement T setting up aliasing constraints according to the
3235 references found in T. This function is the main part of the
3236 constraint builder. AI points to auxiliary alias information used
3237 when building alias sets and computing alias grouping heuristics. */
3240 find_func_aliases (tree origt
)
3243 VEC(ce_s
, heap
) *lhsc
= NULL
;
3244 VEC(ce_s
, heap
) *rhsc
= NULL
;
3245 struct constraint_expr
*c
;
3247 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
3248 t
= TREE_OPERAND (t
, 0);
3250 /* Now build constraints expressions. */
3251 if (TREE_CODE (t
) == PHI_NODE
)
3253 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))));
3255 /* Only care about pointers and structures containing
3257 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t
)))
3258 || TREE_CODE (TREE_TYPE (PHI_RESULT (t
))) == COMPLEX_TYPE
)
3263 /* For a phi node, assign all the arguments to
3265 get_constraint_for (PHI_RESULT (t
), &lhsc
);
3266 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
3269 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
3271 STRIP_NOPS (strippedrhs
);
3272 rhstype
= TREE_TYPE (strippedrhs
);
3273 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
3275 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3277 struct constraint_expr
*c2
;
3278 while (VEC_length (ce_s
, rhsc
) > 0)
3280 c2
= VEC_last (ce_s
, rhsc
);
3281 process_constraint (new_constraint (*c
, *c2
));
3282 VEC_pop (ce_s
, rhsc
);
3288 /* In IPA mode, we need to generate constraints to pass call
3289 arguments through their calls. There are two case, either a
3290 modify_expr when we are returning a value, or just a plain
3291 call_expr when we are not. */
3292 else if (in_ipa_mode
3293 && ((TREE_CODE (t
) == MODIFY_EXPR
3294 && TREE_CODE (TREE_OPERAND (t
, 1)) == CALL_EXPR
3295 && !(call_expr_flags (TREE_OPERAND (t
, 1))
3296 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
3297 || (TREE_CODE (t
) == CALL_EXPR
3298 && !(call_expr_flags (t
)
3299 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
3308 if (TREE_CODE (t
) == MODIFY_EXPR
)
3310 lhsop
= TREE_OPERAND (t
, 0);
3311 rhsop
= TREE_OPERAND (t
, 1);
3318 decl
= get_callee_fndecl (rhsop
);
3320 /* If we can directly resolve the function being called, do so.
3321 Otherwise, it must be some sort of indirect expression that
3322 we should still be able to handle. */
3325 varid
= get_id_for_tree (decl
);
3329 decl
= TREE_OPERAND (rhsop
, 0);
3330 varid
= get_id_for_tree (decl
);
3333 /* Assign all the passed arguments to the appropriate incoming
3334 parameters of the function. */
3335 fi
= get_varinfo (varid
);
3336 arglist
= TREE_OPERAND (rhsop
, 1);
3338 for (;arglist
; arglist
= TREE_CHAIN (arglist
))
3340 tree arg
= TREE_VALUE (arglist
);
3341 struct constraint_expr lhs
;
3342 struct constraint_expr
*rhsp
;
3344 get_constraint_for (arg
, &rhsc
);
3345 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3354 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3357 while (VEC_length (ce_s
, rhsc
) != 0)
3359 rhsp
= VEC_last (ce_s
, rhsc
);
3360 process_constraint (new_constraint (lhs
, *rhsp
));
3361 VEC_pop (ce_s
, rhsc
);
3365 /* If we are returning a value, assign it to the result. */
3368 struct constraint_expr rhs
;
3369 struct constraint_expr
*lhsp
;
3372 get_constraint_for (lhsop
, &lhsc
);
3373 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3382 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3385 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3386 process_constraint (new_constraint (*lhsp
, rhs
));
3389 /* Otherwise, just a regular assignment statement. */
3390 else if (TREE_CODE (t
) == MODIFY_EXPR
)
3392 tree lhsop
= TREE_OPERAND (t
, 0);
3393 tree rhsop
= TREE_OPERAND (t
, 1);
3396 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3397 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
)
3398 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop
))
3399 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
))
3401 do_structure_copy (lhsop
, rhsop
);
3405 /* Only care about operations with pointers, structures
3406 containing pointers, dereferences, and call expressions. */
3407 if (POINTER_TYPE_P (TREE_TYPE (lhsop
))
3408 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3409 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
3410 || TREE_CODE (rhsop
) == CALL_EXPR
)
3412 get_constraint_for (lhsop
, &lhsc
);
3413 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3415 /* RHS that consist of unary operations,
3416 exceptional types, or bare decls/constants, get
3417 handled directly by get_constraint_for. */
3419 case tcc_declaration
:
3421 case tcc_exceptional
:
3422 case tcc_expression
:
3427 get_constraint_for (rhsop
, &rhsc
);
3428 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3430 struct constraint_expr
*c2
;
3433 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3434 process_constraint (new_constraint (*c
, *c2
));
3442 /* For pointer arithmetic of the form
3443 PTR + CST, we can simply use PTR's
3444 constraint because pointer arithmetic is
3445 not allowed to go out of bounds. */
3446 if (handle_ptr_arith (lhsc
, rhsop
))
3451 /* Otherwise, walk each operand. Notice that we
3452 can't use the operand interface because we need
3453 to process expressions other than simple operands
3454 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3456 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
3458 tree op
= TREE_OPERAND (rhsop
, i
);
3461 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3462 get_constraint_for (op
, &rhsc
);
3463 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3465 struct constraint_expr
*c2
;
3466 while (VEC_length (ce_s
, rhsc
) > 0)
3468 c2
= VEC_last (ce_s
, rhsc
);
3469 process_constraint (new_constraint (*c
, *c2
));
3470 VEC_pop (ce_s
, rhsc
);
3479 /* After promoting variables and computing aliasing we will
3480 need to re-scan most statements. FIXME: Try to minimize the
3481 number of statements re-scanned. It's not really necessary to
3482 re-scan *all* statements. */
3483 mark_stmt_modified (origt
);
3484 VEC_free (ce_s
, heap
, rhsc
);
3485 VEC_free (ce_s
, heap
, lhsc
);
3489 /* Find the first varinfo in the same variable as START that overlaps with
3491 Effectively, walk the chain of fields for the variable START to find the
3492 first field that overlaps with OFFSET.
3493 Return NULL if we can't find one. */
3496 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3498 varinfo_t curr
= start
;
3501 /* We may not find a variable in the field list with the actual
3502 offset when when we have glommed a structure to a variable.
3503 In that case, however, offset should still be within the size
3505 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3513 /* Insert the varinfo FIELD into the field list for BASE, at the front
3517 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3519 varinfo_t prev
= base
;
3520 varinfo_t curr
= base
->next
;
3526 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3530 insert_into_field_list_sorted (varinfo_t base
, varinfo_t field
)
3532 varinfo_t prev
= base
;
3533 varinfo_t curr
= base
->next
;
3544 if (field
->offset
<= curr
->offset
)
3549 field
->next
= prev
->next
;
3554 /* qsort comparison function for two fieldoff's PA and PB */
3557 fieldoff_compare (const void *pa
, const void *pb
)
3559 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3560 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3561 HOST_WIDE_INT foasize
, fobsize
;
3563 if (foa
->offset
!= fob
->offset
)
3564 return foa
->offset
- fob
->offset
;
3566 foasize
= TREE_INT_CST_LOW (foa
->size
);
3567 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3568 return foasize
- fobsize
;
3571 /* Sort a fieldstack according to the field offset and sizes. */
3572 void sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3574 qsort (VEC_address (fieldoff_s
, fieldstack
),
3575 VEC_length (fieldoff_s
, fieldstack
),
3576 sizeof (fieldoff_s
),
3580 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3581 of TYPE onto fieldstack, recording their offsets along the way.
3582 OFFSET is used to keep track of the offset in this entire structure, rather
3583 than just the immediately containing structure. Returns the number
3585 HAS_UNION is set to true if we find a union type as a field of
3589 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3590 HOST_WIDE_INT offset
, bool *has_union
)
3595 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3597 fieldoff_s
*real_part
, *img_part
;
3598 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3599 real_part
->type
= TREE_TYPE (type
);
3600 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3601 real_part
->offset
= offset
;
3602 real_part
->decl
= NULL_TREE
;
3604 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3605 img_part
->type
= TREE_TYPE (type
);
3606 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3607 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3608 img_part
->decl
= NULL_TREE
;
3613 if (TREE_CODE (type
) == ARRAY_TYPE
)
3615 tree sz
= TYPE_SIZE (type
);
3616 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3621 || ! host_integerp (sz
, 1)
3622 || TREE_INT_CST_LOW (sz
) == 0
3624 || ! host_integerp (elsz
, 1)
3625 || TREE_INT_CST_LOW (elsz
) == 0)
3628 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3629 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3632 for (i
= 0; i
< nr
; ++i
)
3638 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3639 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3642 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3644 else if (!(pushed
= push_fields_onto_fieldstack
3645 (TREE_TYPE (type
), fieldstack
,
3646 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
)))
3647 /* Empty structures may have actual size, like in C++. So
3648 see if we didn't push any subfields and the size is
3649 nonzero, push the field onto the stack */
3656 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3657 pair
->type
= TREE_TYPE (type
);
3659 pair
->decl
= NULL_TREE
;
3660 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3670 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3671 if (TREE_CODE (field
) == FIELD_DECL
)
3677 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3678 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3681 if (!var_can_have_subvars (field
))
3683 else if (!(pushed
= push_fields_onto_fieldstack
3684 (TREE_TYPE (field
), fieldstack
,
3685 offset
+ bitpos_of_field (field
), has_union
))
3686 && DECL_SIZE (field
)
3687 && !integer_zerop (DECL_SIZE (field
)))
3688 /* Empty structures may have actual size, like in C++. So
3689 see if we didn't push any subfields and the size is
3690 nonzero, push the field onto the stack */
3697 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3698 pair
->type
= TREE_TYPE (field
);
3699 pair
->size
= DECL_SIZE (field
);
3701 pair
->offset
= offset
+ bitpos_of_field (field
);
3712 make_constraint_to_anything (varinfo_t vi
)
3714 struct constraint_expr lhs
, rhs
;
3720 rhs
.var
= anything_id
;
3722 rhs
.type
= ADDRESSOF
;
3723 process_constraint (new_constraint (lhs
, rhs
));
3726 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3727 if it is a varargs function. */
3730 count_num_arguments (tree decl
, bool *is_varargs
)
3735 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3739 if (TREE_VALUE (t
) == void_type_node
)
3749 /* Creation function node for DECL, using NAME, and return the index
3750 of the variable we've created for the function. */
3753 create_function_info_for (tree decl
, const char *name
)
3755 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3759 bool is_varargs
= false;
3761 /* Create the variable info. */
3763 vi
= new_var_info (decl
, index
, name
, index
);
3768 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3769 insert_id_for_tree (vi
->decl
, index
);
3770 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3774 /* If it's varargs, we don't know how many arguments it has, so we
3781 vi
->is_unknown_size_var
= true;
3786 arg
= DECL_ARGUMENTS (decl
);
3788 /* Set up variables for each argument. */
3789 for (i
= 1; i
< vi
->fullsize
; i
++)
3792 const char *newname
;
3794 unsigned int newindex
;
3795 tree argdecl
= decl
;
3800 newindex
= VEC_length (varinfo_t
, varmap
);
3801 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3802 newname
= ggc_strdup (tempname
);
3805 argvi
= new_var_info (argdecl
, newindex
,newname
, newindex
);
3806 argvi
->decl
= argdecl
;
3807 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3810 argvi
->fullsize
= vi
->fullsize
;
3811 argvi
->has_union
= false;
3812 insert_into_field_list_sorted (vi
, argvi
);
3813 stats
.total_vars
++;
3816 insert_id_for_tree (arg
, newindex
);
3817 arg
= TREE_CHAIN (arg
);
3821 /* Create a variable for the return var. */
3822 if (DECL_RESULT (decl
) != NULL
3823 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3826 const char *newname
;
3828 unsigned int newindex
;
3829 tree resultdecl
= decl
;
3833 if (DECL_RESULT (decl
))
3834 resultdecl
= DECL_RESULT (decl
);
3836 newindex
= VEC_length (varinfo_t
, varmap
);
3837 asprintf (&tempname
, "%s.result", name
);
3838 newname
= ggc_strdup (tempname
);
3841 resultvi
= new_var_info (resultdecl
, newindex
, newname
, newindex
);
3842 resultvi
->decl
= resultdecl
;
3843 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3844 resultvi
->offset
= i
;
3846 resultvi
->fullsize
= vi
->fullsize
;
3847 resultvi
->has_union
= false;
3848 insert_into_field_list_sorted (vi
, resultvi
);
3849 stats
.total_vars
++;
3850 if (DECL_RESULT (decl
))
3851 insert_id_for_tree (DECL_RESULT (decl
), newindex
);
3857 /* Return true if FIELDSTACK contains fields that overlap.
3858 FIELDSTACK is assumed to be sorted by offset. */
3861 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3863 fieldoff_s
*fo
= NULL
;
3865 HOST_WIDE_INT lastoffset
= -1;
3867 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3869 if (fo
->offset
== lastoffset
)
3871 lastoffset
= fo
->offset
;
3875 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3876 This will also create any varinfo structures necessary for fields
3880 create_variable_info_for (tree decl
, const char *name
)
3882 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3884 tree
decltype = TREE_TYPE (decl
);
3885 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
3886 bool notokay
= false;
3888 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
3889 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
3891 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
3892 return create_function_info_for (decl
, name
);
3894 hasunion
= TREE_CODE (decltype) == UNION_TYPE
3895 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
3896 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
3898 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
3901 VEC_free (fieldoff_s
, heap
, fieldstack
);
3907 /* If the variable doesn't have subvars, we may end up needing to
3908 sort the field list and create fake variables for all the
3910 vi
= new_var_info (decl
, index
, name
, index
);
3913 vi
->has_union
= hasunion
;
3915 || TREE_CODE (declsize
) != INTEGER_CST
3916 || TREE_CODE (decltype) == UNION_TYPE
3917 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
3919 vi
->is_unknown_size_var
= true;
3925 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
3926 vi
->size
= vi
->fullsize
;
3929 insert_id_for_tree (vi
->decl
, index
);
3930 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3931 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3932 make_constraint_to_anything (vi
);
3935 if (use_field_sensitive
3937 && !vi
->is_unknown_size_var
3938 && var_can_have_subvars (decl
)
3939 && VEC_length (fieldoff_s
, fieldstack
) <= MAX_FIELDS_FOR_FIELD_SENSITIVE
)
3941 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
3942 fieldoff_s
*fo
= NULL
;
3945 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3948 || TREE_CODE (fo
->size
) != INTEGER_CST
3956 /* We can't sort them if we have a field with a variable sized type,
3957 which will make notokay = true. In that case, we are going to return
3958 without creating varinfos for the fields anyway, so sorting them is a
3962 sort_fieldstack (fieldstack
);
3963 /* Due to some C++ FE issues, like PR 22488, we might end up
3964 what appear to be overlapping fields even though they,
3965 in reality, do not overlap. Until the C++ FE is fixed,
3966 we will simply disable field-sensitivity for these cases. */
3967 notokay
= check_for_overlaps (fieldstack
);
3971 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
3972 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
3974 if (fo
== NULL
|| notokay
)
3976 vi
->is_unknown_size_var
= 1;
3979 VEC_free (fieldoff_s
, heap
, fieldstack
);
3983 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
3984 vi
->offset
= fo
->offset
;
3985 for (i
= VEC_length (fieldoff_s
, fieldstack
) - 1;
3986 i
>= 1 && VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
3990 const char *newname
;
3993 newindex
= VEC_length (varinfo_t
, varmap
);
3995 asprintf (&tempname
, "%s.%s", vi
->name
, alias_get_name (fo
->decl
));
3997 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
, vi
->name
, fo
->offset
);
3998 newname
= ggc_strdup (tempname
);
4000 newvi
= new_var_info (decl
, newindex
, newname
, newindex
);
4001 newvi
->offset
= fo
->offset
;
4002 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
4003 newvi
->fullsize
= vi
->fullsize
;
4004 insert_into_field_list (vi
, newvi
);
4005 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
4006 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
4007 make_constraint_to_anything (newvi
);
4011 VEC_free (fieldoff_s
, heap
, fieldstack
);
4016 /* Print out the points-to solution for VAR to FILE. */
4019 dump_solution_for_var (FILE *file
, unsigned int var
)
4021 varinfo_t vi
= get_varinfo (var
);
4025 fprintf (file
, "%s = { ", vi
->name
);
4026 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi
->node
)->solution
, 0, i
, bi
)
4028 fprintf (file
, "%s ", get_varinfo (i
)->name
);
4030 fprintf (file
, "}\n");
4033 /* Print the points-to solution for VAR to stdout. */
4036 debug_solution_for_var (unsigned int var
)
4038 dump_solution_for_var (stdout
, var
);
4042 /* Create varinfo structures for all of the variables in the
4043 function for intraprocedural mode. */
4046 intra_create_variable_infos (void)
4050 /* For each incoming argument arg, ARG = &ANYTHING or a dummy variable if
4051 flag_argument_noalias > 2. */
4052 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
4054 struct constraint_expr lhs
;
4059 lhs
.var
= create_variable_info_for (t
, alias_get_name (t
));
4061 /* With flag_argument_noalias greater than two means that the incoming
4062 argument cannot alias anything except for itself so create a HEAP
4064 if (POINTER_TYPE_P (TREE_TYPE (t
))
4065 && flag_argument_noalias
> 2)
4068 struct constraint_expr rhs
;
4069 tree heapvar
= heapvar_lookup (t
);
4071 if (heapvar
== NULL_TREE
)
4073 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)),
4075 DECL_EXTERNAL (heapvar
) = 1;
4076 if (referenced_vars
)
4077 add_referenced_var (heapvar
);
4078 heapvar_insert (t
, heapvar
);
4080 id
= create_variable_info_for (heapvar
,
4081 alias_get_name (heapvar
));
4082 vi
= get_varinfo (id
);
4083 vi
->is_artificial_var
= 1;
4084 vi
->is_heap_var
= 1;
4086 rhs
.type
= ADDRESSOF
;
4088 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4090 struct constraint_expr temp
= lhs
;
4092 process_constraint (new_constraint (temp
, rhs
));
4096 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4097 make_constraint_to_anything (p
);
4101 /* Set bits in INTO corresponding to the variable uids in solution set
4105 set_uids_in_ptset (bitmap into
, bitmap from
)
4111 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
4113 varinfo_t vi
= get_varinfo (i
);
4115 /* The only artificial variables that are allowed in a may-alias
4116 set are heap variables. */
4117 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
4120 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
4122 /* Variables containing unions may need to be converted to
4123 their SFT's, because SFT's can have unions and we cannot. */
4124 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
4125 bitmap_set_bit (into
, DECL_UID (sv
->var
));
4127 else if (TREE_CODE (vi
->decl
) == VAR_DECL
4128 || TREE_CODE (vi
->decl
) == PARM_DECL
)
4130 if (var_can_have_subvars (vi
->decl
)
4131 && get_subvars_for_var (vi
->decl
))
4133 /* If VI->DECL is an aggregate for which we created
4134 SFTs, add the SFT corresponding to VI->OFFSET. */
4135 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
4137 bitmap_set_bit (into
, DECL_UID (sft
));
4141 /* Otherwise, just add VI->DECL to the alias set. */
4142 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4149 static bool have_alias_info
= false;
4151 /* Given a pointer variable P, fill in its points-to set, or return
4152 false if we can't. */
4155 find_what_p_points_to (tree p
)
4157 unsigned int id
= 0;
4160 if (!have_alias_info
)
4163 /* For parameters, get at the points-to set for the actual parm
4165 if (TREE_CODE (p
) == SSA_NAME
4166 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
4167 && default_def (SSA_NAME_VAR (p
)) == p
)
4168 lookup_p
= SSA_NAME_VAR (p
);
4170 if (lookup_id_for_tree (lookup_p
, &id
))
4172 varinfo_t vi
= get_varinfo (id
);
4174 if (vi
->is_artificial_var
)
4177 /* See if this is a field or a structure. */
4178 if (vi
->size
!= vi
->fullsize
)
4180 /* Nothing currently asks about structure fields directly,
4181 but when they do, we need code here to hand back the
4183 if (!var_can_have_subvars (vi
->decl
)
4184 || get_subvars_for_var (vi
->decl
) == NULL
)
4189 struct ptr_info_def
*pi
= get_ptr_info (p
);
4193 /* This variable may have been collapsed, let's get the real
4195 vi
= get_varinfo (vi
->node
);
4197 /* Translate artificial variables into SSA_NAME_PTR_INFO
4199 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4201 varinfo_t vi
= get_varinfo (i
);
4203 if (vi
->is_artificial_var
)
4205 /* FIXME. READONLY should be handled better so that
4206 flow insensitive aliasing can disregard writable
4208 if (vi
->id
== nothing_id
)
4210 else if (vi
->id
== anything_id
)
4211 pi
->pt_anything
= 1;
4212 else if (vi
->id
== readonly_id
)
4213 pi
->pt_anything
= 1;
4214 else if (vi
->id
== integer_id
)
4215 pi
->pt_anything
= 1;
4216 else if (vi
->is_heap_var
)
4217 pi
->pt_global_mem
= 1;
4221 if (pi
->pt_anything
)
4225 pi
->pt_vars
= BITMAP_GGC_ALLOC ();
4227 set_uids_in_ptset (pi
->pt_vars
, vi
->solution
);
4229 if (bitmap_empty_p (pi
->pt_vars
))
4241 /* Dump points-to information to OUTFILE. */
4244 dump_sa_points_to_info (FILE *outfile
)
4248 fprintf (outfile
, "\nPoints-to sets\n\n");
4250 if (dump_flags
& TDF_STATS
)
4252 fprintf (outfile
, "Stats:\n");
4253 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4254 fprintf (outfile
, "Statically unified vars: %d\n",
4255 stats
.unified_vars_static
);
4256 fprintf (outfile
, "Collapsed vars: %d\n", stats
.collapsed_vars
);
4257 fprintf (outfile
, "Dynamically unified vars: %d\n",
4258 stats
.unified_vars_dynamic
);
4259 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4260 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4263 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4264 dump_solution_for_var (outfile
, i
);
4268 /* Debug points-to information to stderr. */
4271 debug_sa_points_to_info (void)
4273 dump_sa_points_to_info (stderr
);
4277 /* Initialize the always-existing constraint variables for NULL
4278 ANYTHING, READONLY, and INTEGER */
4281 init_base_vars (void)
4283 struct constraint_expr lhs
, rhs
;
4285 /* Create the NULL variable, used to represent that a variable points
4287 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4288 var_nothing
= new_var_info (nothing_tree
, 0, "NULL", 0);
4289 insert_id_for_tree (nothing_tree
, 0);
4290 var_nothing
->is_artificial_var
= 1;
4291 var_nothing
->offset
= 0;
4292 var_nothing
->size
= ~0;
4293 var_nothing
->fullsize
= ~0;
4294 var_nothing
->is_special_var
= 1;
4296 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4298 /* Create the ANYTHING variable, used to represent that a variable
4299 points to some unknown piece of memory. */
4300 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4301 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING", 1);
4302 insert_id_for_tree (anything_tree
, 1);
4303 var_anything
->is_artificial_var
= 1;
4304 var_anything
->size
= ~0;
4305 var_anything
->offset
= 0;
4306 var_anything
->next
= NULL
;
4307 var_anything
->fullsize
= ~0;
4308 var_anything
->is_special_var
= 1;
4311 /* Anything points to anything. This makes deref constraints just
4312 work in the presence of linked list and other p = *p type loops,
4313 by saying that *ANYTHING = ANYTHING. */
4314 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4316 lhs
.var
= anything_id
;
4318 rhs
.type
= ADDRESSOF
;
4319 rhs
.var
= anything_id
;
4321 var_anything
->address_taken
= true;
4323 /* This specifically does not use process_constraint because
4324 process_constraint ignores all anything = anything constraints, since all
4325 but this one are redundant. */
4326 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4328 /* Create the READONLY variable, used to represent that a variable
4329 points to readonly memory. */
4330 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4331 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY", 2);
4332 var_readonly
->is_artificial_var
= 1;
4333 var_readonly
->offset
= 0;
4334 var_readonly
->size
= ~0;
4335 var_readonly
->fullsize
= ~0;
4336 var_readonly
->next
= NULL
;
4337 var_readonly
->is_special_var
= 1;
4338 insert_id_for_tree (readonly_tree
, 2);
4340 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4342 /* readonly memory points to anything, in order to make deref
4343 easier. In reality, it points to anything the particular
4344 readonly variable can point to, but we don't track this
4347 lhs
.var
= readonly_id
;
4349 rhs
.type
= ADDRESSOF
;
4350 rhs
.var
= anything_id
;
4353 process_constraint (new_constraint (lhs
, rhs
));
4355 /* Create the INTEGER variable, used to represent that a variable points
4357 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4358 var_integer
= new_var_info (integer_tree
, 3, "INTEGER", 3);
4359 insert_id_for_tree (integer_tree
, 3);
4360 var_integer
->is_artificial_var
= 1;
4361 var_integer
->size
= ~0;
4362 var_integer
->fullsize
= ~0;
4363 var_integer
->offset
= 0;
4364 var_integer
->next
= NULL
;
4365 var_integer
->is_special_var
= 1;
4367 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4369 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
4370 integer will point to. */
4372 lhs
.var
= integer_id
;
4374 rhs
.type
= ADDRESSOF
;
4375 rhs
.var
= anything_id
;
4377 process_constraint (new_constraint (lhs
, rhs
));
4380 /* Return true if we actually need to solve the constraint graph in order to
4381 get our points-to sets. This is false when, for example, no addresses are
4382 taken other than special vars, or all points-to sets with members already
4383 contain the anything variable and there are no predecessors for other
4387 need_to_solve (void)
4391 bool found_address_taken
= false;
4392 bool found_non_anything
= false;
4394 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4396 if (v
->is_special_var
)
4399 if (v
->address_taken
)
4400 found_address_taken
= true;
4403 && !bitmap_empty_p (v
->solution
)
4404 && !bitmap_bit_p (v
->solution
, anything_id
))
4405 found_non_anything
= true;
4406 else if (bitmap_empty_p (v
->solution
)
4407 && (VEC_length (constraint_edge_t
, graph
->preds
[v
->id
]) != 0
4408 || (graph
->zero_weight_preds
[v
->id
] && !bitmap_empty_p (graph
->zero_weight_preds
[v
->id
]))))
4409 found_non_anything
= true;
4411 if (found_address_taken
&& found_non_anything
)
4418 /* Initialize things necessary to perform PTA */
4421 init_alias_vars (void)
4423 bitmap_obstack_initialize (&ptabitmap_obstack
);
4424 bitmap_obstack_initialize (&predbitmap_obstack
);
4426 constraint_pool
= create_alloc_pool ("Constraint pool",
4427 sizeof (struct constraint
), 30);
4428 variable_info_pool
= create_alloc_pool ("Variable info pool",
4429 sizeof (struct variable_info
), 30);
4430 constraint_edge_pool
= create_alloc_pool ("Constraint edges",
4431 sizeof (struct constraint_edge
), 30);
4433 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4434 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4435 id_for_tree
= htab_create (10, tree_id_hash
, tree_id_eq
, free
);
4436 memset (&stats
, 0, sizeof (stats
));
4442 /* Create points-to sets for the current function. See the comments
4443 at the start of the file for an algorithmic overview. */
4446 compute_points_to_sets (struct alias_info
*ai
)
4450 timevar_push (TV_TREE_PTA
);
4454 intra_create_variable_infos ();
4456 /* Now walk all statements and derive aliases. */
4459 block_stmt_iterator bsi
;
4462 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4464 if (is_gimple_reg (PHI_RESULT (phi
)))
4466 find_func_aliases (phi
);
4467 /* Update various related attributes like escaped
4468 addresses, pointer dereferences for loads and stores.
4469 This is used when creating name tags and alias
4471 update_alias_info (phi
, ai
);
4475 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4477 tree stmt
= bsi_stmt (bsi
);
4478 find_func_aliases (stmt
);
4479 /* Update various related attributes like escaped
4480 addresses, pointer dereferences for loads and stores.
4481 This is used when creating name tags and alias
4483 update_alias_info (stmt
, ai
);
4487 build_constraint_graph ();
4491 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4492 dump_constraints (dump_file
);
4495 if (1 || need_to_solve ())
4499 "\nCollapsing static cycles and doing variable "
4502 find_and_collapse_graph_cycles (graph
, false);
4503 perform_var_substitution (graph
);
4506 fprintf (dump_file
, "\nSolving graph:\n");
4508 solve_graph (graph
);
4512 dump_sa_points_to_info (dump_file
);
4514 have_alias_info
= true;
4516 timevar_pop (TV_TREE_PTA
);
4520 /* Delete created points-to sets. */
4523 delete_points_to_sets (void)
4528 htab_delete (id_for_tree
);
4529 bitmap_obstack_release (&ptabitmap_obstack
);
4530 bitmap_obstack_release (&predbitmap_obstack
);
4531 VEC_free (constraint_t
, heap
, constraints
);
4533 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4535 VEC_free (constraint_edge_t
, heap
, graph
->succs
[i
]);
4536 VEC_free (constraint_edge_t
, heap
, graph
->preds
[i
]);
4537 VEC_free (constraint_t
, heap
, v
->complex);
4539 free (graph
->zero_weight_preds
);
4540 free (graph
->zero_weight_succs
);
4541 free (graph
->succs
);
4542 free (graph
->preds
);
4545 VEC_free (varinfo_t
, heap
, varmap
);
4546 free_alloc_pool (variable_info_pool
);
4547 free_alloc_pool (constraint_pool
);
4548 free_alloc_pool (constraint_edge_pool
);
4550 have_alias_info
= false;
4553 /* Return true if we should execute IPA PTA. */
4557 return (flag_unit_at_a_time
!= 0
4559 /* Don't bother doing anything if the program has errors. */
4560 && !(errorcount
|| sorrycount
));
4563 /* Execute the driver for IPA PTA. */
4565 ipa_pta_execute (void)
4567 struct cgraph_node
*node
;
4569 init_alias_heapvars ();
4572 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4574 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
4578 varid
= create_function_info_for (node
->decl
,
4579 cgraph_node_name (node
));
4580 if (node
->local
.externally_visible
)
4582 varinfo_t fi
= get_varinfo (varid
);
4583 for (; fi
; fi
= fi
->next
)
4584 make_constraint_to_anything (fi
);
4588 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4590 if (node
->analyzed
&& cgraph_is_master_clone (node
))
4592 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
4594 tree old_func_decl
= current_function_decl
;
4597 "Generating constraints for %s\n",
4598 cgraph_node_name (node
));
4600 current_function_decl
= node
->decl
;
4602 FOR_EACH_BB_FN (bb
, cfun
)
4604 block_stmt_iterator bsi
;
4607 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4609 if (is_gimple_reg (PHI_RESULT (phi
)))
4611 find_func_aliases (phi
);
4615 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4617 tree stmt
= bsi_stmt (bsi
);
4618 find_func_aliases (stmt
);
4621 current_function_decl
= old_func_decl
;
4626 /* Make point to anything. */
4630 build_constraint_graph ();
4634 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4635 dump_constraints (dump_file
);
4638 if (need_to_solve ())
4642 "\nCollapsing static cycles and doing variable "
4645 find_and_collapse_graph_cycles (graph
, false);
4646 perform_var_substitution (graph
);
4649 fprintf (dump_file
, "\nSolving graph:\n");
4651 solve_graph (graph
);
4655 dump_sa_points_to_info (dump_file
);
4657 delete_alias_heapvars ();
4658 delete_points_to_sets ();
4662 struct tree_opt_pass pass_ipa_pta
=
4665 gate_ipa_pta
, /* gate */
4666 ipa_pta_execute
, /* execute */
4669 0, /* static_pass_number */
4670 TV_IPA_PTA
, /* tv_id */
4671 0, /* properties_required */
4672 0, /* properties_provided */
4673 0, /* properties_destroyed */
4674 0, /* todo_flags_start */
4675 0, /* todo_flags_finish */
4679 /* Initialize the heapvar for statement mapping. */
4681 init_alias_heapvars (void)
4683 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
, NULL
);
4687 delete_alias_heapvars (void)
4689 htab_delete (heapvar_for_stmt
);
4693 #include "gt-tree-ssa-structalias.h"