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"
29 #include "tree-ssa-structalias.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
37 #include "diagnostic.h"
40 #include "tree-flow.h"
41 #include "tree-inline.h"
44 #include "tree-gimple.h"
48 #include "tree-pass.h"
50 #include "alloc-pool.h"
51 #include "splay-tree.h"
53 /* The idea behind this analyzer is to generate set constraints from the
54 program, then solve the resulting constraints in order to generate the
57 Set constraints are a way of modeling program analysis problems that
58 involve sets. They consist of an inclusion constraint language,
59 describing the variables (each variable is a set) and operations that
60 are involved on the variables, and a set of rules that derive facts
61 from these operations. To solve a system of set constraints, you derive
62 all possible facts under the rules, which gives you the correct sets
65 See "Efficient Field-sensitive pointer analysis for C" by "David
66 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
67 http://citeseer.ist.psu.edu/pearce04efficient.html
69 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
70 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
71 http://citeseer.ist.psu.edu/heintze01ultrafast.html
73 There are three types of constraint expressions, DEREF, ADDRESSOF, and
74 SCALAR. Each constraint expression consists of a constraint type,
75 a variable, and an offset.
77 SCALAR is a constraint expression type used to represent x, whether
78 it appears on the LHS or the RHS of a statement.
79 DEREF is a constraint expression type used to represent *x, whether
80 it appears on the LHS or the RHS of a statement.
81 ADDRESSOF is a constraint expression used to represent &x, whether
82 it appears on the LHS or the RHS of a statement.
84 Each pointer variable in the program is assigned an integer id, and
85 each field of a structure variable is assigned an integer id as well.
87 Structure variables are linked to their list of fields through a "next
88 field" in each variable that points to the next field in offset
90 Each variable for a structure field has
92 1. "size", that tells the size in bits of that field.
93 2. "fullsize, that tells the size in bits of the entire structure.
94 3. "offset", that tells the offset in bits from the beginning of the
95 structure to this field.
107 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
108 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
109 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112 In order to solve the system of set constraints, the following is
115 1. Each constraint variable x has a solution set associated with it,
118 2. Constraints are separated into direct, copy, and complex.
119 Direct constraints are ADDRESSOF constraints that require no extra
120 processing, such as P = &Q
121 Copy constraints are those of the form P = Q.
122 Complex constraints are all the constraints involving dereferences.
124 3. All direct constraints of the form P = &Q are processed, such
125 that Q is added to Sol(P)
127 4. All complex constraints for a given constraint variable are stored in a
128 linked list attached to that variable's node.
130 5. A directed graph is built out of the copy constraints. Each
131 constraint variable is a node in the graph, and an edge from
132 Q to P is added for each copy constraint of the form P = Q
134 6. The graph is then walked, and solution sets are
135 propagated along the copy edges, such that an edge from Q to P
136 causes Sol(P) <- Sol(P) union Sol(Q).
138 7. As we visit each node, all complex constraints associated with
139 that node are processed by adding appropriate copy edges to the graph, or the
140 appropriate variables to the solution set.
142 8. The process of walking the graph is iterated until no solution
145 Prior to walking the graph in steps 6 and 7, We perform static
146 cycle elimination on the constraint graph, as well
147 as off-line variable substitution.
149 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
150 on and turned into anything), but isn't. You can just see what offset
151 inside the pointed-to struct it's going to access.
153 TODO: Constant bounded arrays can be handled as if they were structs of the
154 same number of elements.
156 TODO: Modeling heap and incoming pointers becomes much better if we
157 add fields to them as we discover them, which we could do.
159 TODO: We could handle unions, but to be honest, it's probably not
160 worth the pain or slowdown. */
162 static bool use_field_sensitive
= true;
163 static unsigned int create_variable_info_for (tree
, const char *);
164 static struct constraint_expr
get_constraint_for (tree
);
165 static void build_constraint_graph (void);
167 static bitmap_obstack ptabitmap_obstack
;
168 static bitmap_obstack iteration_obstack
;
169 DEF_VEC_P(constraint_t
);
170 DEF_VEC_ALLOC_P(constraint_t
,gc
);
172 static struct constraint_stats
174 unsigned int total_vars
;
175 unsigned int collapsed_vars
;
176 unsigned int unified_vars_static
;
177 unsigned int unified_vars_dynamic
;
178 unsigned int iterations
;
183 /* ID of this variable */
186 /* Name of this variable */
189 /* Tree that this variable is associated with. */
192 /* Offset of this variable, in bits, from the base variable */
193 unsigned HOST_WIDE_INT offset
;
195 /* Size of the variable, in bits. */
196 unsigned HOST_WIDE_INT size
;
198 /* Full size of the base variable, in bits. */
199 unsigned HOST_WIDE_INT fullsize
;
201 /* A link to the variable for the next field in this structure. */
202 struct variable_info
*next
;
204 /* Node in the graph that represents the constraints and points-to
205 solution for the variable. */
208 /* True if the address of this variable is taken. Needed for
209 variable substitution. */
210 unsigned int address_taken
:1;
212 /* True if this variable is the target of a dereference. Needed for
213 variable substitution. */
214 unsigned int indirect_target
:1;
216 /* True if this is a variable created by the constraint analysis, such as
217 heap variables and constraints we had to break up. */
218 unsigned int is_artificial_var
:1;
220 /* True for variables whose size is not known or variable. */
221 unsigned int is_unknown_size_var
:1;
223 /* True for variables that have unions somewhere in them. */
224 unsigned int has_union
:1;
226 /* Points-to set for this variable. */
229 /* Variable ids represented by this node. */
232 /* Vector of complex constraints for this node. Complex
233 constraints are those involving dereferences. */
234 VEC(constraint_t
,gc
) *complex;
236 typedef struct variable_info
*varinfo_t
;
238 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
240 /* Pool of variable info structures. */
241 static alloc_pool variable_info_pool
;
243 DEF_VEC_P(varinfo_t
);
245 DEF_VEC_ALLOC_P(varinfo_t
, gc
);
247 /* Table of variable info structures for constraint variables. Indexed directly
248 by variable info id. */
249 static VEC(varinfo_t
,gc
) *varmap
;
250 #define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
252 /* Variable that represents the unknown pointer. */
253 static varinfo_t var_anything
;
254 static tree anything_tree
;
255 static unsigned int anything_id
;
257 /* Variable that represents the NULL pointer. */
258 static varinfo_t var_nothing
;
259 static tree nothing_tree
;
260 static unsigned int nothing_id
;
262 /* Variable that represents read only memory. */
263 static varinfo_t var_readonly
;
264 static tree readonly_tree
;
265 static unsigned int readonly_id
;
267 /* Variable that represents integers. This is used for when people do things
269 static varinfo_t var_integer
;
270 static tree integer_tree
;
271 static unsigned int integer_id
;
274 /* Return a new variable info structure consisting for a variable
275 named NAME, and using constraint graph node NODE. */
278 new_var_info (tree t
, unsigned int id
, const char *name
, unsigned int node
)
280 varinfo_t ret
= pool_alloc (variable_info_pool
);
286 ret
->address_taken
= false;
287 ret
->indirect_target
= false;
288 ret
->is_artificial_var
= false;
289 ret
->is_unknown_size_var
= false;
290 ret
->solution
= BITMAP_ALLOC (&ptabitmap_obstack
);
291 bitmap_clear (ret
->solution
);
292 ret
->variables
= BITMAP_ALLOC (&ptabitmap_obstack
);
293 bitmap_clear (ret
->variables
);
299 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
301 /* An expression that appears in a constraint. */
303 struct constraint_expr
305 /* Constraint type. */
306 constraint_expr_type type
;
308 /* Variable we are referring to in the constraint. */
311 /* Offset, in bits, of this constraint from the beginning of
312 variables it ends up referring to.
314 IOW, in a deref constraint, we would deref, get the result set,
315 then add OFFSET to each member. */
316 unsigned HOST_WIDE_INT offset
;
319 static struct constraint_expr
do_deref (struct constraint_expr
);
321 /* Our set constraints are made up of two constraint expressions, one
324 As described in the introduction, our set constraints each represent an
325 operation between set valued variables.
329 struct constraint_expr lhs
;
330 struct constraint_expr rhs
;
333 /* List of constraints that we use to build the constraint graph from. */
335 static VEC(constraint_t
,gc
) *constraints
;
336 static alloc_pool constraint_pool
;
338 /* An edge in the constraint graph. We technically have no use for
339 the src, since it will always be the same node that we are indexing
340 into the pred/succ arrays with, but it's nice for checking
341 purposes. The edges are weighted, with a bit set in weights for
342 each edge from src to dest with that weight. */
344 struct constraint_edge
351 typedef struct constraint_edge
*constraint_edge_t
;
352 static alloc_pool constraint_edge_pool
;
354 /* Return a new constraint edge from SRC to DEST. */
356 static constraint_edge_t
357 new_constraint_edge (unsigned int src
, unsigned int dest
)
359 constraint_edge_t ret
= pool_alloc (constraint_edge_pool
);
366 DEF_VEC_P(constraint_edge_t
);
367 DEF_VEC_ALLOC_P(constraint_edge_t
,gc
);
370 /* The constraint graph is simply a set of adjacency vectors, one per
371 variable. succs[x] is the vector of successors for variable x, and preds[x]
372 is the vector of predecessors for variable x.
373 IOW, all edges are "forward" edges, which is not like our CFG.
375 preds[x]->src == x, and
378 struct constraint_graph
380 VEC(constraint_edge_t
,gc
) **succs
;
381 VEC(constraint_edge_t
,gc
) **preds
;
384 typedef struct constraint_graph
*constraint_graph_t
;
386 static constraint_graph_t graph
;
388 /* Create a new constraint consisting of LHS and RHS expressions. */
391 new_constraint (const struct constraint_expr lhs
,
392 const struct constraint_expr rhs
)
394 constraint_t ret
= pool_alloc (constraint_pool
);
400 /* Print out constraint C to FILE. */
403 dump_constraint (FILE *file
, constraint_t c
)
405 if (c
->lhs
.type
== ADDRESSOF
)
407 else if (c
->lhs
.type
== DEREF
)
409 fprintf (file
, "%s", get_varinfo (c
->lhs
.var
)->name
);
410 if (c
->lhs
.offset
!= 0)
411 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
412 fprintf (file
, " = ");
413 if (c
->rhs
.type
== ADDRESSOF
)
415 else if (c
->rhs
.type
== DEREF
)
417 fprintf (file
, "%s", get_varinfo (c
->rhs
.var
)->name
);
418 if (c
->rhs
.offset
!= 0)
419 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
420 fprintf (file
, "\n");
423 /* Print out constraint C to stderr. */
426 debug_constraint (constraint_t c
)
428 dump_constraint (stderr
, c
);
431 /* Print out all constraints to FILE */
434 dump_constraints (FILE *file
)
438 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
439 dump_constraint (file
, c
);
442 /* Print out all constraints to stderr. */
445 debug_constraints (void)
447 dump_constraints (stderr
);
452 The solver is a simple worklist solver, that works on the following
455 sbitmap changed_nodes = all ones;
456 changed_count = number of nodes;
457 For each node that was already collapsed:
461 while (changed_count > 0)
463 compute topological ordering for constraint graph
465 find and collapse cycles in the constraint graph (updating
466 changed if necessary)
468 for each node (n) in the graph in topological order:
471 Process each complex constraint associated with the node,
472 updating changed if necessary.
474 For each outgoing edge from n, propagate the solution from n to
475 the destination of the edge, updating changed as necessary.
479 /* Return true if two constraint expressions A and B are equal. */
482 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
484 return a
.type
== b
.type
486 && a
.offset
== b
.offset
;
489 /* Return true if constraint expression A is less than constraint expression
490 B. This is just arbitrary, but consistent, in order to give them an
494 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
496 if (a
.type
== b
.type
)
499 return a
.offset
< b
.offset
;
501 return a
.var
< b
.var
;
504 return a
.type
< b
.type
;
507 /* Return true if constraint A is less than constraint B. This is just
508 arbitrary, but consistent, in order to give them an ordering. */
511 constraint_less (const constraint_t a
, const constraint_t b
)
513 if (constraint_expr_less (a
->lhs
, b
->lhs
))
515 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
518 return constraint_expr_less (a
->rhs
, b
->rhs
);
521 /* Return true if two constraints A and B are equal. */
524 constraint_equal (struct constraint a
, struct constraint b
)
526 return constraint_expr_equal (a
.lhs
, b
.lhs
)
527 && constraint_expr_equal (a
.rhs
, b
.rhs
);
531 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
534 constraint_vec_find (VEC(constraint_t
,gc
) *vec
,
535 struct constraint lookfor
)
543 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
544 if (place
>= VEC_length (constraint_t
, vec
))
546 found
= VEC_index (constraint_t
, vec
, place
);
547 if (!constraint_equal (*found
, lookfor
))
552 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
555 constraint_set_union (VEC(constraint_t
,gc
) **to
,
556 VEC(constraint_t
,gc
) **from
)
561 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
563 if (constraint_vec_find (*to
, *c
) == NULL
)
565 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
567 VEC_safe_insert (constraint_t
, gc
, *to
, place
, c
);
572 /* Take a solution set SET, add OFFSET to each member of the set, and
573 overwrite SET with the result when done. */
576 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
578 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
582 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
584 /* If this is a properly sized variable, only add offset if it's
585 less than end. Otherwise, it is globbed to a single
588 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
590 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
591 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
592 bitmap_set_bit (result
, v
->id
);
594 else if (get_varinfo (i
)->is_artificial_var
595 || get_varinfo (i
)->is_unknown_size_var
)
597 bitmap_set_bit (result
, i
);
601 bitmap_copy (set
, result
);
602 BITMAP_FREE (result
);
605 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
609 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
612 return bitmap_ior_into (to
, from
);
618 tmp
= BITMAP_ALLOC (&iteration_obstack
);
619 bitmap_copy (tmp
, from
);
620 solution_set_add (tmp
, inc
);
621 res
= bitmap_ior_into (to
, tmp
);
627 /* Insert constraint C into the list of complex constraints for VAR. */
630 insert_into_complex (unsigned int var
, constraint_t c
)
632 varinfo_t vi
= get_varinfo (var
);
633 unsigned int place
= VEC_lower_bound (constraint_t
, vi
->complex, c
,
635 VEC_safe_insert (constraint_t
, gc
, vi
->complex, place
, c
);
639 /* Compare two constraint edges A and B, return true if they are equal. */
642 constraint_edge_equal (struct constraint_edge a
, struct constraint_edge b
)
644 return a
.src
== b
.src
&& a
.dest
== b
.dest
;
647 /* Compare two constraint edges, return true if A is less than B */
650 constraint_edge_less (const constraint_edge_t a
, const constraint_edge_t b
)
652 if (a
->dest
< b
->dest
)
654 else if (a
->dest
== b
->dest
)
655 return a
->src
< b
->src
;
660 /* Find the constraint edge that matches LOOKFOR, in VEC.
661 Return the edge, if found, NULL otherwise. */
663 static constraint_edge_t
664 constraint_edge_vec_find (VEC(constraint_edge_t
,gc
) *vec
,
665 struct constraint_edge lookfor
)
668 constraint_edge_t edge
;
670 place
= VEC_lower_bound (constraint_edge_t
, vec
, &lookfor
,
671 constraint_edge_less
);
672 edge
= VEC_index (constraint_edge_t
, vec
, place
);
673 if (!constraint_edge_equal (*edge
, lookfor
))
678 /* Condense two variable nodes into a single variable node, by moving
679 all associated info from SRC to TO. */
682 condense_varmap_nodes (unsigned int to
, unsigned int src
)
684 varinfo_t tovi
= get_varinfo (to
);
685 varinfo_t srcvi
= get_varinfo (src
);
690 /* the src node, and all its variables, are now the to node. */
692 EXECUTE_IF_SET_IN_BITMAP (srcvi
->variables
, 0, i
, bi
)
693 get_varinfo (i
)->node
= to
;
695 /* Merge the src node variables and the to node variables. */
696 bitmap_set_bit (tovi
->variables
, src
);
697 bitmap_ior_into (tovi
->variables
, srcvi
->variables
);
698 bitmap_clear (srcvi
->variables
);
700 /* Move all complex constraints from src node into to node */
701 for (i
= 0; VEC_iterate (constraint_t
, srcvi
->complex, i
, c
); i
++)
703 /* In complex constraints for node src, we may have either
704 a = *src, and *src = a. */
706 if (c
->rhs
.type
== DEREF
)
711 constraint_set_union (&tovi
->complex, &srcvi
->complex);
712 srcvi
->complex = NULL
;
715 /* Erase EDGE from GRAPH. This routine only handles self-edges
716 (e.g. an edge from a to a). */
719 erase_graph_self_edge (constraint_graph_t graph
, struct constraint_edge edge
)
721 VEC(constraint_edge_t
,gc
) *predvec
= graph
->preds
[edge
.src
];
722 VEC(constraint_edge_t
,gc
) *succvec
= graph
->succs
[edge
.dest
];
724 gcc_assert (edge
.src
== edge
.dest
);
726 /* Remove from the successors. */
727 place
= VEC_lower_bound (constraint_edge_t
, succvec
, &edge
,
728 constraint_edge_less
);
730 /* Make sure we found the edge. */
731 #ifdef ENABLE_CHECKING
733 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, succvec
, place
);
734 gcc_assert (constraint_edge_equal (*tmp
, edge
));
737 VEC_ordered_remove (constraint_edge_t
, succvec
, place
);
739 /* Remove from the predecessors. */
740 place
= VEC_lower_bound (constraint_edge_t
, predvec
, &edge
,
741 constraint_edge_less
);
743 /* Make sure we found the edge. */
744 #ifdef ENABLE_CHECKING
746 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, predvec
, place
);
747 gcc_assert (constraint_edge_equal (*tmp
, edge
));
750 VEC_ordered_remove (constraint_edge_t
, predvec
, place
);
753 /* Remove edges involving NODE from GRAPH. */
756 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
758 VEC(constraint_edge_t
,gc
) *succvec
= graph
->succs
[node
];
759 VEC(constraint_edge_t
,gc
) *predvec
= graph
->preds
[node
];
763 /* Walk the successors, erase the associated preds. */
764 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
768 struct constraint_edge lookfor
;
769 lookfor
.src
= c
->dest
;
771 place
= VEC_lower_bound (constraint_edge_t
, graph
->preds
[c
->dest
],
772 &lookfor
, constraint_edge_less
);
773 VEC_ordered_remove (constraint_edge_t
, graph
->preds
[c
->dest
], place
);
775 /* Walk the preds, erase the associated succs. */
776 for (i
=0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
780 struct constraint_edge lookfor
;
781 lookfor
.src
= c
->dest
;
783 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[c
->dest
],
784 &lookfor
, constraint_edge_less
);
785 VEC_ordered_remove (constraint_edge_t
, graph
->succs
[c
->dest
], place
);
788 graph
->preds
[node
] = NULL
;
789 graph
->succs
[node
] = NULL
;
792 static bool edge_added
= false;
794 /* Add edge NEWE to the graph. */
797 add_graph_edge (constraint_graph_t graph
, struct constraint_edge newe
)
800 unsigned int src
= newe
.src
;
801 unsigned int dest
= newe
.dest
;
802 VEC(constraint_edge_t
,gc
) *vec
;
804 vec
= graph
->preds
[src
];
805 place
= VEC_lower_bound (constraint_edge_t
, vec
, &newe
,
806 constraint_edge_less
);
807 if (place
== VEC_length (constraint_edge_t
, vec
)
808 || VEC_index (constraint_edge_t
, vec
, place
)->dest
!= dest
)
810 constraint_edge_t edge
= new_constraint_edge (src
, dest
);
813 weightbitmap
= BITMAP_ALLOC (&ptabitmap_obstack
);
814 edge
->weights
= weightbitmap
;
815 VEC_safe_insert (constraint_edge_t
, gc
, graph
->preds
[edge
->src
],
817 edge
= new_constraint_edge (dest
, src
);
818 edge
->weights
= weightbitmap
;
819 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[edge
->src
],
820 edge
, constraint_edge_less
);
821 VEC_safe_insert (constraint_edge_t
, gc
, graph
->succs
[edge
->src
],
831 /* Return the bitmap representing the weights of edge LOOKFOR */
834 get_graph_weights (constraint_graph_t graph
, struct constraint_edge lookfor
)
836 constraint_edge_t edge
;
837 unsigned int src
= lookfor
.src
;
838 VEC(constraint_edge_t
,gc
) *vec
;
839 vec
= graph
->preds
[src
];
840 edge
= constraint_edge_vec_find (vec
, lookfor
);
841 gcc_assert (edge
!= NULL
);
842 return edge
->weights
;
846 /* Merge GRAPH nodes FROM and TO into node TO. */
849 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
852 VEC(constraint_edge_t
,gc
) *succvec
= graph
->succs
[from
];
853 VEC(constraint_edge_t
,gc
) *predvec
= graph
->preds
[from
];
857 /* Merge all the predecessor edges. */
859 for (i
= 0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
861 unsigned int d
= c
->dest
;
862 struct constraint_edge olde
;
863 struct constraint_edge newe
;
870 add_graph_edge (graph
, newe
);
873 temp
= get_graph_weights (graph
, olde
);
874 weights
= get_graph_weights (graph
, newe
);
875 bitmap_ior_into (weights
, temp
);
878 /* Merge all the successor edges. */
879 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
881 unsigned int d
= c
->dest
;
882 struct constraint_edge olde
;
883 struct constraint_edge newe
;
890 add_graph_edge (graph
, newe
);
893 temp
= get_graph_weights (graph
, olde
);
894 weights
= get_graph_weights (graph
, newe
);
895 bitmap_ior_into (weights
, temp
);
897 clear_edges_for_node (graph
, from
);
900 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
901 it doesn't exist in the graph already.
902 Return false if the edge already existed, true otherwise. */
905 int_add_graph_edge (constraint_graph_t graph
, unsigned int to
,
906 unsigned int from
, unsigned HOST_WIDE_INT weight
)
908 if (to
== from
&& weight
== 0)
915 struct constraint_edge edge
;
918 r
= add_graph_edge (graph
, edge
);
919 r
|= !bitmap_bit_p (get_graph_weights (graph
, edge
), weight
);
920 bitmap_set_bit (get_graph_weights (graph
, edge
), weight
);
926 /* Return true if LOOKFOR is an existing graph edge. */
929 valid_graph_edge (constraint_graph_t graph
, struct constraint_edge lookfor
)
931 return constraint_edge_vec_find (graph
->preds
[lookfor
.src
], lookfor
) != NULL
;
935 /* Build the constraint graph. */
938 build_constraint_graph (void)
943 graph
= ggc_alloc (sizeof (struct constraint_graph
));
944 graph
->succs
= ggc_alloc_cleared (VEC_length (varinfo_t
, varmap
) * sizeof (*graph
->succs
));
945 graph
->preds
= ggc_alloc_cleared (VEC_length (varinfo_t
, varmap
) * sizeof (*graph
->preds
));
946 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
948 struct constraint_expr lhs
= c
->lhs
;
949 struct constraint_expr rhs
= c
->rhs
;
950 if (lhs
.type
== DEREF
)
952 /* *x = y or *x = &y (complex) */
953 if (rhs
.type
== ADDRESSOF
|| rhs
.var
> anything_id
)
954 insert_into_complex (lhs
.var
, c
);
956 else if (rhs
.type
== DEREF
)
959 if (lhs
.var
> anything_id
)
960 insert_into_complex (rhs
.var
, c
);
962 else if (rhs
.type
== ADDRESSOF
)
965 bitmap_set_bit (get_varinfo (lhs
.var
)->solution
, rhs
.var
);
967 else if (rhs
.var
> anything_id
&& lhs
.var
> anything_id
)
969 /* Ignore 0 weighted self edges, as they can't possibly contribute
971 if (lhs
.var
!= rhs
.var
|| rhs
.offset
!= 0 || lhs
.offset
!= 0)
974 struct constraint_edge edge
;
978 add_graph_edge (graph
, edge
);
979 bitmap_set_bit (get_graph_weights (graph
, edge
),
986 /* Changed variables on the last iteration. */
987 static unsigned int changed_count
;
988 static sbitmap changed
;
991 DEF_VEC_ALLOC_I(unsigned,heap
);
994 /* Strongly Connected Component visitation info. */
999 sbitmap in_component
;
1001 unsigned int *visited_index
;
1002 VEC(unsigned,heap
) *scc_stack
;
1003 VEC(unsigned,heap
) *unification_queue
;
1007 /* Recursive routine to find strongly connected components in GRAPH.
1008 SI is the SCC info to store the information in, and N is the id of current
1009 graph node we are processing.
1011 This is Tarjan's strongly connected component finding algorithm, as
1012 modified by Nuutila to keep only non-root nodes on the stack.
1013 The algorithm can be found in "On finding the strongly connected
1014 connected components in a directed graph" by Esko Nuutila and Eljas
1015 Soisalon-Soininen, in Information Processing Letters volume 49,
1016 number 1, pages 9-14. */
1019 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1021 constraint_edge_t c
;
1024 gcc_assert (get_varinfo (n
)->node
== n
);
1025 SET_BIT (si
->visited
, n
);
1026 RESET_BIT (si
->in_component
, n
);
1027 si
->visited_index
[n
] = si
->current_index
++;
1029 /* Visit all the successors. */
1030 for (i
= 0; VEC_iterate (constraint_edge_t
, graph
->succs
[n
], i
, c
); i
++)
1032 /* We only want to find and collapse the zero weight edges. */
1033 if (bitmap_bit_p (c
->weights
, 0))
1035 unsigned int w
= c
->dest
;
1036 if (!TEST_BIT (si
->visited
, w
))
1037 scc_visit (graph
, si
, w
);
1038 if (!TEST_BIT (si
->in_component
, w
))
1040 unsigned int t
= get_varinfo (w
)->node
;
1041 unsigned int nnode
= get_varinfo (n
)->node
;
1042 if (si
->visited_index
[t
] < si
->visited_index
[nnode
])
1043 get_varinfo (n
)->node
= t
;
1048 /* See if any components have been identified. */
1049 if (get_varinfo (n
)->node
== n
)
1051 unsigned int t
= si
->visited_index
[n
];
1052 SET_BIT (si
->in_component
, n
);
1053 while (VEC_length (unsigned, si
->scc_stack
) != 0
1054 && t
< si
->visited_index
[VEC_last (unsigned, si
->scc_stack
)])
1056 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1057 get_varinfo (w
)->node
= n
;
1058 SET_BIT (si
->in_component
, w
);
1059 /* Mark this node for collapsing. */
1060 VEC_safe_push (unsigned, heap
, si
->unification_queue
, w
);
1064 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1068 /* Collapse two variables into one variable. */
1071 collapse_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
)
1073 bitmap tosol
, fromsol
;
1074 struct constraint_edge edge
;
1077 condense_varmap_nodes (to
, from
);
1078 tosol
= get_varinfo (to
)->solution
;
1079 fromsol
= get_varinfo (from
)->solution
;
1080 bitmap_ior_into (tosol
, fromsol
);
1081 merge_graph_nodes (graph
, to
, from
);
1084 if (valid_graph_edge (graph
, edge
))
1086 bitmap weights
= get_graph_weights (graph
, edge
);
1087 bitmap_clear_bit (weights
, 0);
1088 if (bitmap_empty_p (weights
))
1089 erase_graph_self_edge (graph
, edge
);
1091 bitmap_clear (fromsol
);
1092 get_varinfo (to
)->address_taken
|= get_varinfo (from
)->address_taken
;
1093 get_varinfo (to
)->indirect_target
|= get_varinfo (from
)->indirect_target
;
1097 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1098 SI is the Strongly Connected Components information structure that tells us
1099 what components to unify.
1100 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1101 count should be updated to reflect the unification. */
1104 process_unification_queue (constraint_graph_t graph
, struct scc_info
*si
,
1105 bool update_changed
)
1108 bitmap tmp
= BITMAP_ALLOC (update_changed
? &iteration_obstack
: NULL
);
1111 /* We proceed as follows:
1113 For each component in the queue (components are delineated by
1114 when current_queue_element->node != next_queue_element->node):
1116 rep = representative node for component
1118 For each node (tounify) to be unified in the component,
1119 merge the solution for tounify into tmp bitmap
1121 clear solution for tounify
1123 merge edges from tounify into rep
1125 merge complex constraints from tounify into rep
1127 update changed count to note that tounify will never change
1130 Merge tmp into solution for rep, marking rep changed if this
1131 changed rep's solution.
1133 Delete any 0 weighted self-edges we now have for rep. */
1134 while (i
!= VEC_length (unsigned, si
->unification_queue
))
1136 unsigned int tounify
= VEC_index (unsigned, si
->unification_queue
, i
);
1137 unsigned int n
= get_varinfo (tounify
)->node
;
1139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1140 fprintf (dump_file
, "Unifying %s to %s\n",
1141 get_varinfo (tounify
)->name
,
1142 get_varinfo (n
)->name
);
1144 stats
.unified_vars_dynamic
++;
1146 stats
.unified_vars_static
++;
1147 bitmap_ior_into (tmp
, get_varinfo (tounify
)->solution
);
1148 merge_graph_nodes (graph
, n
, tounify
);
1149 condense_varmap_nodes (n
, tounify
);
1151 if (update_changed
&& TEST_BIT (changed
, tounify
))
1153 RESET_BIT (changed
, tounify
);
1154 if (!TEST_BIT (changed
, n
))
1155 SET_BIT (changed
, n
);
1158 gcc_assert (changed_count
> 0);
1163 bitmap_clear (get_varinfo (tounify
)->solution
);
1166 /* If we've either finished processing the entire queue, or
1167 finished processing all nodes for component n, update the solution for
1169 if (i
== VEC_length (unsigned, si
->unification_queue
)
1170 || get_varinfo (VEC_index (unsigned, si
->unification_queue
, i
))->node
!= n
)
1172 struct constraint_edge edge
;
1174 /* If the solution changes because of the merging, we need to mark
1175 the variable as changed. */
1176 if (bitmap_ior_into (get_varinfo (n
)->solution
, tmp
))
1178 if (update_changed
&& !TEST_BIT (changed
, n
))
1180 SET_BIT (changed
, n
);
1187 if (valid_graph_edge (graph
, edge
))
1189 bitmap weights
= get_graph_weights (graph
, edge
);
1190 bitmap_clear_bit (weights
, 0);
1191 if (bitmap_empty_p (weights
))
1192 erase_graph_self_edge (graph
, edge
);
1200 /* Information needed to compute the topological ordering of a graph. */
1204 /* sbitmap of visited nodes. */
1206 /* Array that stores the topological order of the graph, *in
1208 VEC(unsigned,heap
) *topo_order
;
1212 /* Initialize and return a topological info structure. */
1214 static struct topo_info
*
1215 init_topo_info (void)
1217 size_t size
= VEC_length (varinfo_t
, varmap
);
1218 struct topo_info
*ti
= xmalloc (sizeof (struct topo_info
));
1219 ti
->visited
= sbitmap_alloc (size
);
1220 sbitmap_zero (ti
->visited
);
1221 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1226 /* Free the topological sort info pointed to by TI. */
1229 free_topo_info (struct topo_info
*ti
)
1231 sbitmap_free (ti
->visited
);
1232 VEC_free (unsigned, heap
, ti
->topo_order
);
1236 /* Visit the graph in topological order, and store the order in the
1237 topo_info structure. */
1240 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1243 VEC(constraint_edge_t
,gc
) *succs
= graph
->succs
[n
];
1244 constraint_edge_t c
;
1246 SET_BIT (ti
->visited
, n
);
1247 for (i
= 0; VEC_iterate (constraint_edge_t
, succs
, i
, c
); i
++)
1249 if (!TEST_BIT (ti
->visited
, c
->dest
))
1250 topo_visit (graph
, ti
, c
->dest
);
1252 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1255 /* Return true if variable N + OFFSET is a legal field of N. */
1258 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1260 varinfo_t ninfo
= get_varinfo (n
);
1262 /* For things we've globbed to single variables, any offset into the
1263 variable acts like the entire variable, so that it becomes offset
1265 if (n
== anything_id
1266 || ninfo
->is_artificial_var
1267 || ninfo
->is_unknown_size_var
)
1272 return n
> anything_id
1273 && (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1276 /* Process a constraint C that represents *x = &y. */
1279 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1280 constraint_t c
, bitmap delta
)
1282 unsigned int rhs
= c
->rhs
.var
;
1283 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1287 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1288 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1290 if (type_safe (j
, &offset
))
1292 /* *x != NULL && *x != ANYTHING*/
1296 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1297 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1299 sol
= get_varinfo (t
)->solution
;
1300 if (!bitmap_bit_p (sol
, rhs
))
1302 bitmap_set_bit (sol
, rhs
);
1303 if (!TEST_BIT (changed
, t
))
1305 SET_BIT (changed
, t
);
1311 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1316 /* Process a constraint C that represents x = *y, using DELTA as the
1317 starting solution. */
1320 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1323 unsigned int lhs
= get_varinfo (c
->lhs
.var
)->node
;
1324 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1326 bitmap sol
= get_varinfo (lhs
)->solution
;
1330 /* For each variable j in delta (Sol(y)), add
1331 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1332 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1334 if (type_safe (j
, &roffset
))
1337 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1340 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1342 if (int_add_graph_edge (graph
, lhs
, t
, 0))
1343 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1346 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1350 /* If the LHS solution changed, mark the var as changed. */
1353 get_varinfo (lhs
)->solution
= sol
;
1354 if (!TEST_BIT (changed
, lhs
))
1356 SET_BIT (changed
, lhs
);
1362 /* Process a constraint C that represents *x = y. */
1365 do_ds_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1367 unsigned int rhs
= get_varinfo (c
->rhs
.var
)->node
;
1368 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1369 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1370 bitmap sol
= get_varinfo (rhs
)->solution
;
1374 /* For each member j of delta (Sol(x)), add an edge from y to j and
1375 union Sol(y) into Sol(j) */
1376 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1378 if (type_safe (j
, &loff
))
1382 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1384 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1386 if (int_add_graph_edge (graph
, t
, rhs
, roff
))
1388 bitmap tmp
= get_varinfo (t
)->solution
;
1389 if (set_union_with_increment (tmp
, sol
, roff
))
1391 get_varinfo (t
)->solution
= tmp
;
1394 sol
= get_varinfo (rhs
)->solution
;
1396 if (!TEST_BIT (changed
, t
))
1398 SET_BIT (changed
, t
);
1405 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1409 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1410 constraint (IE *x = &y, x = *y, and *x = y). */
1413 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1415 if (c
->lhs
.type
== DEREF
)
1417 if (c
->rhs
.type
== ADDRESSOF
)
1420 do_da_constraint (graph
, c
, delta
);
1425 do_ds_constraint (graph
, c
, delta
);
1431 do_sd_constraint (graph
, c
, delta
);
1435 /* Initialize and return a new SCC info structure. */
1437 static struct scc_info
*
1438 init_scc_info (void)
1440 struct scc_info
*si
= xmalloc (sizeof (struct scc_info
));
1441 size_t size
= VEC_length (varinfo_t
, varmap
);
1443 si
->current_index
= 0;
1444 si
->visited
= sbitmap_alloc (size
);
1445 sbitmap_zero (si
->visited
);
1446 si
->in_component
= sbitmap_alloc (size
);
1447 sbitmap_ones (si
->in_component
);
1448 si
->visited_index
= xcalloc (sizeof (unsigned int), size
+ 1);
1449 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1450 si
->unification_queue
= VEC_alloc (unsigned, heap
, 1);
1454 /* Free an SCC info structure pointed to by SI */
1457 free_scc_info (struct scc_info
*si
)
1459 sbitmap_free (si
->visited
);
1460 sbitmap_free (si
->in_component
);
1461 free (si
->visited_index
);
1462 VEC_free (unsigned, heap
, si
->scc_stack
);
1463 VEC_free (unsigned, heap
, si
->unification_queue
);
1468 /* Find cycles in GRAPH that occur, using strongly connected components, and
1469 collapse the cycles into a single representative node. if UPDATE_CHANGED
1470 is true, then update the changed sbitmap to note those nodes whose
1471 solutions have changed as a result of collapsing. */
1474 find_and_collapse_graph_cycles (constraint_graph_t graph
, bool update_changed
)
1477 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1478 struct scc_info
*si
= init_scc_info ();
1480 for (i
= 0; i
!= size
; ++i
)
1481 if (!TEST_BIT (si
->visited
, i
) && get_varinfo (i
)->node
== i
)
1482 scc_visit (graph
, si
, i
);
1483 process_unification_queue (graph
, si
, update_changed
);
1487 /* Compute a topological ordering for GRAPH, and store the result in the
1488 topo_info structure TI. */
1491 compute_topo_order (constraint_graph_t graph
,
1492 struct topo_info
*ti
)
1495 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1497 for (i
= 0; i
!= size
; ++i
)
1498 if (!TEST_BIT (ti
->visited
, i
) && get_varinfo (i
)->node
== i
)
1499 topo_visit (graph
, ti
, i
);
1502 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1505 bitmap_other_than_zero_bit_set (bitmap b
)
1510 if (bitmap_empty_p (b
))
1512 EXECUTE_IF_SET_IN_BITMAP (b
, 1, i
, bi
)
1517 /* Perform offline variable substitution.
1519 This is a linear time way of identifying variables that must have
1520 equivalent points-to sets, including those caused by static cycles,
1521 and single entry subgraphs, in the constraint graph.
1523 The technique is described in "Off-line variable substitution for
1524 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1525 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1528 perform_var_substitution (constraint_graph_t graph
)
1530 struct topo_info
*ti
= init_topo_info ();
1532 /* Compute the topological ordering of the graph, then visit each
1533 node in topological order. */
1534 compute_topo_order (graph
, ti
);
1536 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1538 unsigned int i
= VEC_pop (unsigned, ti
->topo_order
);
1540 varinfo_t vi
= get_varinfo (i
);
1541 bool okay_to_elim
= false;
1542 unsigned int root
= VEC_length (varinfo_t
, varmap
);
1543 VEC(constraint_edge_t
,gc
) *predvec
= graph
->preds
[i
];
1544 constraint_edge_t ce
;
1547 /* We can't eliminate things whose address is taken, or which is
1548 the target of a dereference. */
1549 if (vi
->address_taken
|| vi
->indirect_target
)
1552 /* See if all predecessors of I are ripe for elimination */
1553 for (pred
= 0; VEC_iterate (constraint_edge_t
, predvec
, pred
, ce
); pred
++)
1557 weight
= get_graph_weights (graph
, *ce
);
1559 /* We can't eliminate variables that have non-zero weighted
1560 edges between them. */
1561 if (bitmap_other_than_zero_bit_set (weight
))
1563 okay_to_elim
= false;
1566 w
= get_varinfo (ce
->dest
)->node
;
1568 /* We can't eliminate the node if one of the predecessors is
1569 part of a different strongly connected component. */
1573 okay_to_elim
= true;
1577 okay_to_elim
= false;
1581 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1582 then Solution(i) is a subset of Solution (w), where w is a
1583 predecessor in the graph.
1584 Corollary: If all predecessors of i have the same
1585 points-to set, then i has that same points-to set as
1586 those predecessors. */
1587 tmp
= BITMAP_ALLOC (NULL
);
1588 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1589 get_varinfo (w
)->solution
);
1590 if (!bitmap_empty_p (tmp
))
1592 okay_to_elim
= false;
1599 /* See if the root is different than the original node.
1600 If so, we've found an equivalence. */
1601 if (root
!= get_varinfo (i
)->node
&& okay_to_elim
)
1603 /* Found an equivalence */
1604 get_varinfo (i
)->node
= root
;
1605 collapse_nodes (graph
, root
, i
);
1606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1607 fprintf (dump_file
, "Collapsing %s into %s\n",
1608 get_varinfo (i
)->name
,
1609 get_varinfo (root
)->name
);
1610 stats
.collapsed_vars
++;
1614 free_topo_info (ti
);
1618 /* Solve the constraint graph GRAPH using our worklist solver.
1619 This is based on the PW* family of solvers from the "Efficient Field
1620 Sensitive Pointer Analysis for C" paper.
1621 It works by iterating over all the graph nodes, processing the complex
1622 constraints and propagating the copy constraints, until everything stops
1623 changed. This corresponds to steps 6-8 in the solving list given above. */
1626 solve_graph (constraint_graph_t graph
)
1628 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1631 changed_count
= size
;
1632 changed
= sbitmap_alloc (size
);
1633 sbitmap_ones (changed
);
1635 /* The already collapsed/unreachable nodes will never change, so we
1636 need to account for them in changed_count. */
1637 for (i
= 0; i
< size
; i
++)
1638 if (get_varinfo (i
)->node
!= i
)
1641 while (changed_count
> 0)
1644 struct topo_info
*ti
= init_topo_info ();
1647 bitmap_obstack_initialize (&iteration_obstack
);
1651 /* We already did cycle elimination once, when we did
1652 variable substitution, so we don't need it again for the
1654 if (stats
.iterations
> 1)
1655 find_and_collapse_graph_cycles (graph
, true);
1660 compute_topo_order (graph
, ti
);
1662 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1664 i
= VEC_pop (unsigned, ti
->topo_order
);
1665 gcc_assert (get_varinfo (i
)->node
== i
);
1667 /* If the node has changed, we need to process the
1668 complex constraints and outgoing edges again. */
1669 if (TEST_BIT (changed
, i
))
1673 constraint_edge_t e
;
1675 VEC(constraint_t
,gc
) *complex = get_varinfo (i
)->complex;
1676 VEC(constraint_edge_t
,gc
) *succs
;
1678 RESET_BIT (changed
, i
);
1681 /* Process the complex constraints */
1682 solution
= get_varinfo (i
)->solution
;
1683 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
1684 do_complex_constraint (graph
, c
, solution
);
1686 /* Propagate solution to all successors. */
1687 succs
= graph
->succs
[i
];
1688 for (j
= 0; VEC_iterate (constraint_edge_t
, succs
, j
, e
); j
++)
1690 bitmap tmp
= get_varinfo (e
->dest
)->solution
;
1693 bitmap weights
= e
->weights
;
1696 gcc_assert (!bitmap_empty_p (weights
));
1697 EXECUTE_IF_SET_IN_BITMAP (weights
, 0, k
, bi
)
1698 flag
|= set_union_with_increment (tmp
, solution
, k
);
1702 get_varinfo (e
->dest
)->solution
= tmp
;
1703 if (!TEST_BIT (changed
, e
->dest
))
1705 SET_BIT (changed
, e
->dest
);
1712 free_topo_info (ti
);
1713 bitmap_obstack_release (&iteration_obstack
);
1716 sbitmap_free (changed
);
1720 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1722 /* Map from trees to variable ids. */
1723 static htab_t id_for_tree
;
1725 typedef struct tree_id
1731 /* Hash a tree id structure. */
1734 tree_id_hash (const void *p
)
1736 const tree_id_t ta
= (tree_id_t
) p
;
1737 return htab_hash_pointer (ta
->t
);
1740 /* Return true if the tree in P1 and the tree in P2 are the same. */
1743 tree_id_eq (const void *p1
, const void *p2
)
1745 const tree_id_t ta1
= (tree_id_t
) p1
;
1746 const tree_id_t ta2
= (tree_id_t
) p2
;
1747 return ta1
->t
== ta2
->t
;
1750 /* Insert ID as the variable id for tree T in the hashtable. */
1753 insert_id_for_tree (tree t
, int id
)
1756 struct tree_id finder
;
1760 slot
= htab_find_slot (id_for_tree
, &finder
, INSERT
);
1761 gcc_assert (*slot
== NULL
);
1762 new_pair
= xmalloc (sizeof (struct tree_id
));
1765 *slot
= (void *)new_pair
;
1768 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1769 exist in the hash table, return false, otherwise, return true and
1770 set *ID to the id we found. */
1773 lookup_id_for_tree (tree t
, unsigned int *id
)
1776 struct tree_id finder
;
1779 pair
= htab_find (id_for_tree
, &finder
);
1786 /* Return a printable name for DECL */
1789 alias_get_name (tree decl
)
1791 const char *res
= get_name (decl
);
1793 int num_printed
= 0;
1799 if (TREE_CODE (decl
) == SSA_NAME
)
1801 num_printed
= asprintf (&temp
, "%s_%u",
1802 alias_get_name (SSA_NAME_VAR (decl
)),
1803 SSA_NAME_VERSION (decl
));
1805 else if (DECL_P (decl
))
1807 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
1809 if (num_printed
> 0)
1811 res
= ggc_strdup (temp
);
1817 /* Find the variable id for tree T in the hashtable.
1818 If T doesn't exist in the hash table, create an entry for it. */
1821 get_id_for_tree (tree t
)
1824 struct tree_id finder
;
1827 pair
= htab_find (id_for_tree
, &finder
);
1829 return create_variable_info_for (t
, alias_get_name (t
));
1834 /* Get a constraint expression from an SSA_VAR_P node. */
1836 static struct constraint_expr
1837 get_constraint_exp_from_ssa_var (tree t
)
1839 struct constraint_expr cexpr
;
1841 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
1843 /* For parameters, get at the points-to set for the actual parm
1845 if (TREE_CODE (t
) == SSA_NAME
1846 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
1847 && default_def (SSA_NAME_VAR (t
)) == t
)
1848 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
1850 cexpr
.type
= SCALAR
;
1852 cexpr
.var
= get_id_for_tree (t
);
1853 /* If we determine the result is "anything", and we know this is readonly,
1854 say it points to readonly memory instead. */
1855 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
1857 cexpr
.type
= ADDRESSOF
;
1858 cexpr
.var
= readonly_id
;
1865 /* Process a completed constraint T, and add it to the constraint
1869 process_constraint (constraint_t t
)
1871 struct constraint_expr rhs
= t
->rhs
;
1872 struct constraint_expr lhs
= t
->lhs
;
1874 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
1875 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
1877 /* ANYTHING == ANYTHING is pointless. */
1878 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
1881 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1882 else if (lhs
.var
== anything_id
&& lhs
.type
== ADDRESSOF
)
1887 process_constraint (t
);
1889 /* This can happen in our IR with things like n->a = *p */
1890 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
1892 /* Split into tmp = *rhs, *lhs = tmp */
1893 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
1894 tree pointertype
= TREE_TYPE (rhsdecl
);
1895 tree pointedtotype
= TREE_TYPE (pointertype
);
1896 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
1897 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
1899 /* If this is an aggregate of known size, we should have passed
1900 this off to do_structure_copy, and it should have broken it
1902 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
1903 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
1905 process_constraint (new_constraint (tmplhs
, rhs
));
1906 process_constraint (new_constraint (lhs
, tmplhs
));
1908 else if (rhs
.type
== ADDRESSOF
)
1911 gcc_assert (rhs
.offset
== 0);
1913 for (vi
= get_varinfo (rhs
.var
); vi
!= NULL
; vi
= vi
->next
)
1914 vi
->address_taken
= true;
1916 VEC_safe_push (constraint_t
, gc
, constraints
, t
);
1920 if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
1921 get_varinfo (lhs
.var
)->indirect_target
= true;
1922 VEC_safe_push (constraint_t
, gc
, constraints
, t
);
1927 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1930 static unsigned HOST_WIDE_INT
1931 bitpos_of_field (const tree fdecl
)
1934 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
1935 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
1938 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
1939 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
1943 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1944 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1947 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
1948 const unsigned HOST_WIDE_INT fieldsize
,
1949 const unsigned HOST_WIDE_INT accesspos
,
1950 const unsigned HOST_WIDE_INT accesssize
)
1952 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
1954 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
1956 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
1962 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1964 static struct constraint_expr
1965 get_constraint_for_component_ref (tree t
)
1967 struct constraint_expr result
;
1968 HOST_WIDE_INT bitsize
;
1969 HOST_WIDE_INT bitpos
;
1971 enum machine_mode mode
;
1977 result
.type
= SCALAR
;
1980 /* Some people like to do cute things like take the address of
1983 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
1984 forzero
= TREE_OPERAND (forzero
, 0);
1986 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
1989 result
.var
= integer_id
;
1990 result
.type
= SCALAR
;
1994 t
= get_inner_reference (t
, &bitsize
, &bitpos
, &offset
, &mode
,
1995 &unsignedp
, &volatilep
, false);
1996 result
= get_constraint_for (t
);
1998 /* This can also happen due to weird offsetof type macros. */
1999 if (TREE_CODE (t
) != ADDR_EXPR
&& result
.type
== ADDRESSOF
)
2000 result
.type
= SCALAR
;
2002 /* If we know where this goes, then yay. Otherwise, booo. */
2004 if (offset
== NULL
&& bitsize
!= -1)
2006 result
.offset
= bitpos
;
2010 result
.var
= anything_id
;
2014 if (result
.type
== SCALAR
)
2016 /* In languages like C, you can access one past the end of an
2017 array. You aren't allowed to dereference it, so we can
2018 ignore this constraint. When we handle pointer subtraction,
2019 we may have to do something cute here. */
2021 if (result
.offset
< get_varinfo (result
.var
)->fullsize
)
2023 /* It's also not true that the constraint will actually start at the
2024 right offset, it may start in some padding. We only care about
2025 setting the constraint to the first actual field it touches, so
2028 for (curr
= get_varinfo (result
.var
); curr
; curr
= curr
->next
)
2030 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2031 result
.offset
, bitsize
))
2033 result
.var
= curr
->id
;
2038 /* assert that we found *some* field there. The user couldn't be
2039 accessing *only* padding. */
2044 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2045 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2054 /* Dereference the constraint expression CONS, and return the result.
2055 DEREF (ADDRESSOF) = SCALAR
2056 DEREF (SCALAR) = DEREF
2057 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2058 This is needed so that we can handle dereferencing DEREF constraints. */
2060 static struct constraint_expr
2061 do_deref (struct constraint_expr cons
)
2063 if (cons
.type
== SCALAR
)
2068 else if (cons
.type
== ADDRESSOF
)
2073 else if (cons
.type
== DEREF
)
2075 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "derefmp");
2076 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2077 process_constraint (new_constraint (tmplhs
, cons
));
2078 cons
.var
= tmplhs
.var
;
2085 /* Given a tree T, return the constraint expression for it. */
2087 static struct constraint_expr
2088 get_constraint_for (tree t
)
2090 struct constraint_expr temp
;
2092 /* x = integer is all glommed to a single variable, which doesn't
2093 point to anything by itself. That is, of course, unless it is an
2094 integer constant being treated as a pointer, in which case, we
2095 will return that this is really the addressof anything. This
2096 happens below, since it will fall into the default case. The only
2097 case we know something about an integer treated like a pointer is
2098 when it is the NULL pointer, and then we just say it points to
2100 if (TREE_CODE (t
) == INTEGER_CST
2101 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2103 temp
.var
= integer_id
;
2108 else if (TREE_CODE (t
) == INTEGER_CST
2109 && integer_zerop (t
))
2111 temp
.var
= nothing_id
;
2112 temp
.type
= ADDRESSOF
;
2117 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2119 case tcc_expression
:
2121 switch (TREE_CODE (t
))
2125 temp
= get_constraint_for (TREE_OPERAND (t
, 0));
2126 if (temp
.type
== DEREF
)
2129 temp
.type
= ADDRESSOF
;
2135 /* XXX: In interprocedural mode, if we didn't have the
2136 body, we would need to do *each pointer argument =
2138 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2140 tree heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2141 temp
.var
= create_variable_info_for (heapvar
,
2142 alias_get_name (heapvar
));
2144 get_varinfo (temp
.var
)->is_artificial_var
= 1;
2145 temp
.type
= ADDRESSOF
;
2152 temp
.type
= ADDRESSOF
;
2153 temp
.var
= anything_id
;
2161 switch (TREE_CODE (t
))
2165 temp
= get_constraint_for (TREE_OPERAND (t
, 0));
2166 temp
= do_deref (temp
);
2171 temp
= get_constraint_for_component_ref (t
);
2175 temp
.type
= ADDRESSOF
;
2176 temp
.var
= anything_id
;
2184 switch (TREE_CODE (t
))
2188 case NON_LVALUE_EXPR
:
2190 tree op
= TREE_OPERAND (t
, 0);
2192 /* Cast from non-pointer to pointers are bad news for us.
2193 Anything else, we see through */
2194 if (!(POINTER_TYPE_P (TREE_TYPE (t
)) &&
2195 ! POINTER_TYPE_P (TREE_TYPE (op
))))
2196 return get_constraint_for (op
);
2200 temp
.type
= ADDRESSOF
;
2201 temp
.var
= anything_id
;
2207 case tcc_exceptional
:
2209 switch (TREE_CODE (t
))
2212 return get_constraint_for (PHI_RESULT (t
));
2214 return get_constraint_exp_from_ssa_var (t
);
2217 temp
.type
= ADDRESSOF
;
2218 temp
.var
= anything_id
;
2224 case tcc_declaration
:
2225 return get_constraint_exp_from_ssa_var (t
);
2228 temp
.type
= ADDRESSOF
;
2229 temp
.var
= anything_id
;
2237 /* Handle the structure copy case where we have a simple structure copy
2238 between LHS and RHS that is of SIZE (in bits)
2240 For each field of the lhs variable (lhsfield)
2241 For each field of the rhs variable at lhsfield.offset (rhsfield)
2242 add the constraint lhsfield = rhsfield
2246 do_simple_structure_copy (const struct constraint_expr lhs
,
2247 const struct constraint_expr rhs
,
2248 const unsigned HOST_WIDE_INT size
)
2250 varinfo_t p
= get_varinfo (lhs
.var
);
2251 unsigned HOST_WIDE_INT pstart
, last
;
2253 last
= p
->offset
+ size
;
2254 for (; p
&& p
->offset
< last
; p
= p
->next
)
2257 struct constraint_expr templhs
= lhs
;
2258 struct constraint_expr temprhs
= rhs
;
2259 unsigned HOST_WIDE_INT fieldoffset
;
2261 templhs
.var
= p
->id
;
2262 q
= get_varinfo (temprhs
.var
);
2263 fieldoffset
= p
->offset
- pstart
;
2264 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2265 temprhs
.var
= q
->id
;
2266 process_constraint (new_constraint (templhs
, temprhs
));
2271 /* Handle the structure copy case where we have a structure copy between a
2272 aggregate on the LHS and a dereference of a pointer on the RHS
2273 that is of SIZE (in bits)
2275 For each field of the lhs variable (lhsfield)
2276 rhs.offset = lhsfield->offset
2277 add the constraint lhsfield = rhs
2281 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2282 const struct constraint_expr rhs
,
2283 const unsigned HOST_WIDE_INT size
)
2285 varinfo_t p
= get_varinfo (lhs
.var
);
2286 unsigned HOST_WIDE_INT pstart
,last
;
2288 last
= p
->offset
+ size
;
2290 for (; p
&& p
->offset
< last
; p
= p
->next
)
2293 struct constraint_expr templhs
= lhs
;
2294 struct constraint_expr temprhs
= rhs
;
2295 unsigned HOST_WIDE_INT fieldoffset
;
2298 if (templhs
.type
== SCALAR
)
2299 templhs
.var
= p
->id
;
2301 templhs
.offset
= p
->offset
;
2303 q
= get_varinfo (temprhs
.var
);
2304 fieldoffset
= p
->offset
- pstart
;
2305 temprhs
.offset
+= fieldoffset
;
2306 process_constraint (new_constraint (templhs
, temprhs
));
2310 /* Handle the structure copy case where we have a structure copy
2311 between a aggregate on the RHS and a dereference of a pointer on
2312 the LHS that is of SIZE (in bits)
2314 For each field of the rhs variable (rhsfield)
2315 lhs.offset = rhsfield->offset
2316 add the constraint lhs = rhsfield
2320 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2321 const struct constraint_expr rhs
,
2322 const unsigned HOST_WIDE_INT size
)
2324 varinfo_t p
= get_varinfo (rhs
.var
);
2325 unsigned HOST_WIDE_INT pstart
,last
;
2327 last
= p
->offset
+ size
;
2329 for (; p
&& p
->offset
< last
; p
= p
->next
)
2332 struct constraint_expr templhs
= lhs
;
2333 struct constraint_expr temprhs
= rhs
;
2334 unsigned HOST_WIDE_INT fieldoffset
;
2337 if (temprhs
.type
== SCALAR
)
2338 temprhs
.var
= p
->id
;
2340 temprhs
.offset
= p
->offset
;
2342 q
= get_varinfo (templhs
.var
);
2343 fieldoffset
= p
->offset
- pstart
;
2344 templhs
.offset
+= fieldoffset
;
2345 process_constraint (new_constraint (templhs
, temprhs
));
2350 /* Handle aggregate copies by expanding into copies of the respective
2351 fields of the structures. */
2354 do_structure_copy (tree lhsop
, tree rhsop
)
2356 struct constraint_expr lhs
, rhs
, tmp
;
2358 unsigned HOST_WIDE_INT lhssize
;
2359 unsigned HOST_WIDE_INT rhssize
;
2361 lhs
= get_constraint_for (lhsop
);
2362 rhs
= get_constraint_for (rhsop
);
2364 /* If we have special var = x, swap it around. */
2365 if (lhs
.var
<= integer_id
&& rhs
.var
> integer_id
)
2372 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2373 possible it's something we could handle. However, most cases falling
2374 into this are dealing with transparent unions, which are slightly
2376 if (rhs
.type
== ADDRESSOF
&& rhs
.var
> integer_id
)
2378 rhs
.type
= ADDRESSOF
;
2379 rhs
.var
= anything_id
;
2382 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2383 that special var. */
2384 if (rhs
.var
<= integer_id
)
2386 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2388 struct constraint_expr templhs
= lhs
;
2389 struct constraint_expr temprhs
= rhs
;
2390 if (templhs
.type
== SCALAR
)
2391 templhs
.var
= p
->id
;
2393 templhs
.offset
+= p
->offset
;
2394 process_constraint (new_constraint (templhs
, temprhs
));
2399 tree rhstype
= TREE_TYPE (rhsop
);
2400 tree lhstype
= TREE_TYPE (lhsop
);
2401 tree rhstypesize
= TYPE_SIZE (rhstype
);
2402 tree lhstypesize
= TYPE_SIZE (lhstype
);
2404 /* If we have a variably sized types on the rhs or lhs, and a deref
2405 constraint, add the constraint, lhsconstraint = &ANYTHING.
2406 This is conservatively correct because either the lhs is an unknown
2407 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2408 constraint, and every variable it can point to must be unknown sized
2409 anyway, so we don't need to worry about fields at all. */
2410 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
2411 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
2413 rhs
.var
= anything_id
;
2414 rhs
.type
= ADDRESSOF
;
2416 process_constraint (new_constraint (lhs
, rhs
));
2420 /* The size only really matters insofar as we don't set more or less of
2421 the variable. If we hit an unknown size var, the size should be the
2422 whole darn thing. */
2423 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
2426 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
2428 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
2431 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
2434 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
2435 do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2436 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2437 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2438 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
2439 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2442 tree pointedtotype
= lhstype
;
2445 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
2446 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
2447 do_structure_copy (tmpvar
, rhsop
);
2448 do_structure_copy (lhsop
, tmpvar
);
2454 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2458 ref_contains_indirect_ref (tree ref
)
2460 while (handled_component_p (ref
))
2462 if (TREE_CODE (ref
) == INDIRECT_REF
)
2464 ref
= TREE_OPERAND (ref
, 0);
2470 /* Tree walker that is the heart of the aliasing infrastructure.
2471 TP is a pointer to the current tree.
2472 WALK_SUBTREES specifies whether to continue traversing subtrees or
2474 Returns NULL_TREE when we should stop.
2476 This function is the main part of the constraint builder. It
2477 walks the trees, calling the appropriate building functions
2478 to process various statements. */
2481 find_func_aliases (tree t
)
2483 struct constraint_expr lhs
, rhs
;
2484 switch (TREE_CODE (t
))
2490 /* Only care about pointers and structures containing
2492 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t
)))
2493 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))))
2495 lhs
= get_constraint_for (PHI_RESULT (t
));
2496 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
2498 rhs
= get_constraint_for (PHI_ARG_DEF (t
, i
));
2499 process_constraint (new_constraint (lhs
, rhs
));
2507 tree lhsop
= TREE_OPERAND (t
, 0);
2508 tree rhsop
= TREE_OPERAND (t
, 1);
2511 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
2512 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop
)))
2514 do_structure_copy (lhsop
, rhsop
);
2518 /* Only care about operations with pointers, structures
2519 containing pointers, dereferences, and call
2521 if (POINTER_TYPE_P (TREE_TYPE (lhsop
))
2522 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
2523 || ref_contains_indirect_ref (lhsop
)
2524 || TREE_CODE (rhsop
) == CALL_EXPR
)
2526 lhs
= get_constraint_for (lhsop
);
2527 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
2529 /* RHS that consist of unary operations,
2530 exceptional types, or bare decls/constants, get
2531 handled directly by get_constraint_for. */
2533 case tcc_declaration
:
2535 case tcc_exceptional
:
2536 case tcc_expression
:
2539 rhs
= get_constraint_for (rhsop
);
2540 process_constraint (new_constraint (lhs
, rhs
));
2544 /* Otherwise, walk each operand. */
2546 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
2548 tree op
= TREE_OPERAND (rhsop
, i
);
2549 rhs
= get_constraint_for (op
);
2550 process_constraint (new_constraint (lhs
, rhs
));
2564 /* Find the first varinfo in the same variable as START that overlaps with
2566 Effectively, walk the chain of fields for the variable START to find the
2567 first field that overlaps with OFFSET.
2568 Abort if we can't find one. */
2571 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
2573 varinfo_t curr
= start
;
2576 /* We may not find a variable in the field list with the actual
2577 offset when when we have glommed a structure to a variable.
2578 In that case, however, offset should still be within the size
2580 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
2589 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2593 insert_into_field_list (varinfo_t base
, varinfo_t field
)
2595 varinfo_t prev
= base
;
2596 varinfo_t curr
= base
->next
;
2607 if (field
->offset
<= curr
->offset
)
2612 field
->next
= prev
->next
;
2617 /* qsort comparison function for two fieldoff's PA and PB */
2620 fieldoff_compare (const void *pa
, const void *pb
)
2622 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
2623 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
2624 HOST_WIDE_INT foasize
, fobsize
;
2626 if (foa
->offset
!= fob
->offset
)
2627 return foa
->offset
- fob
->offset
;
2629 foasize
= TREE_INT_CST_LOW (DECL_SIZE (foa
->field
));
2630 fobsize
= TREE_INT_CST_LOW (DECL_SIZE (fob
->field
));
2631 return foasize
- fobsize
;
2634 /* Sort a fieldstack according to the field offset and sizes. */
2635 void sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
2637 qsort (VEC_address (fieldoff_s
, fieldstack
),
2638 VEC_length (fieldoff_s
, fieldstack
),
2639 sizeof (fieldoff_s
),
2643 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2644 of TYPE onto fieldstack, recording their offsets along the way.
2645 OFFSET is used to keep track of the offset in this entire structure, rather
2646 than just the immediately containing structure. Returns the number
2648 HAS_UNION is set to true if we find a union type as a field of
2652 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
2653 HOST_WIDE_INT offset
, bool *has_union
)
2658 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
2659 if (TREE_CODE (field
) == FIELD_DECL
)
2664 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
2665 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
2668 if (!var_can_have_subvars (field
))
2670 else if (!(push_fields_onto_fieldstack
2671 (TREE_TYPE (field
), fieldstack
,
2672 offset
+ bitpos_of_field (field
), has_union
))
2673 && DECL_SIZE (field
)
2674 && !integer_zerop (DECL_SIZE (field
)))
2675 /* Empty structures may have actual size, like in C++. So
2676 see if we didn't push any subfields and the size is
2677 nonzero, push the field onto the stack */
2684 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
2685 pair
->field
= field
;
2686 pair
->offset
= offset
+ bitpos_of_field (field
);
2695 make_constraint_to_anything (varinfo_t vi
)
2697 struct constraint_expr lhs
, rhs
;
2703 rhs
.var
= anything_id
;
2705 rhs
.type
= ADDRESSOF
;
2706 process_constraint (new_constraint (lhs
, rhs
));
2709 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2710 This will also create any varinfo structures necessary for fields
2714 create_variable_info_for (tree decl
, const char *name
)
2716 unsigned int index
= VEC_length (varinfo_t
, varmap
);
2718 tree
decltype = TREE_TYPE (decl
);
2719 bool notokay
= false;
2722 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
2723 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
2726 hasunion
= TREE_CODE (decltype) == UNION_TYPE
|| TREE_CODE (decltype) == QUAL_UNION_TYPE
;
2727 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
2729 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
2732 VEC_free (fieldoff_s
, heap
, fieldstack
);
2737 /* If this variable already has subvars, just create the variables for the
2738 subvars and we are done.
2739 NOTE: This assumes things haven't generated uses of previously
2740 unused structure fields. */
2741 if (use_field_sensitive
2743 && var_can_have_subvars (decl
)
2745 && (svars
= get_subvars_for_var (decl
)))
2748 varinfo_t base
= NULL
;
2749 unsigned int firstindex
= index
;
2751 for (sv
= svars
; sv
; sv
= sv
->next
)
2753 /* For debugging purposes, this will print the names of the
2754 fields as "<var>.<offset>.<size>"
2755 This is only for debugging purposes. */
2756 #define PRINT_LONG_NAMES
2757 #ifdef PRINT_LONG_NAMES
2759 const char *newname
;
2761 asprintf (&tempname
,
2762 "%s." HOST_WIDE_INT_PRINT_DEC
"." HOST_WIDE_INT_PRINT_DEC
,
2763 alias_get_name (decl
), sv
->offset
, sv
->size
);
2764 newname
= ggc_strdup (tempname
);
2766 vi
= new_var_info (sv
->var
, index
, newname
, index
);
2768 vi
= new_var_info (sv
->var
, index
, alias_get_name (sv
->var
), index
);
2771 vi
->fullsize
= TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2772 vi
->size
= sv
->size
;
2773 vi
->offset
= sv
->offset
;
2777 insert_id_for_tree (decl
, index
);
2781 insert_into_field_list (base
, vi
);
2783 insert_id_for_tree (sv
->var
, index
);
2784 VEC_safe_push (varinfo_t
, gc
, varmap
, vi
);
2786 make_constraint_to_anything (vi
);
2794 /* If the variable doesn't have subvars, we may end up needing to
2795 sort the field list and create fake variables for all the
2797 vi
= new_var_info (decl
, index
, name
, index
);
2800 vi
->has_union
= hasunion
;
2801 if (!TYPE_SIZE (decltype)
2802 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
2803 || TREE_CODE (decltype) == ARRAY_TYPE
2804 || TREE_CODE (decltype) == UNION_TYPE
2805 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
2807 vi
->is_unknown_size_var
= true;
2813 vi
->fullsize
= TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2814 vi
->size
= vi
->fullsize
;
2817 insert_id_for_tree (vi
->decl
, index
);
2818 VEC_safe_push (varinfo_t
, gc
, varmap
, vi
);
2820 make_constraint_to_anything (vi
);
2823 if (use_field_sensitive
2825 && !vi
->is_unknown_size_var
2826 && var_can_have_subvars (decl
))
2828 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
2829 fieldoff_s
*fo
= NULL
;
2833 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
2835 if (!DECL_SIZE (fo
->field
)
2836 || TREE_CODE (DECL_SIZE (fo
->field
)) != INTEGER_CST
2837 || TREE_CODE (TREE_TYPE (fo
->field
)) == ARRAY_TYPE
2845 /* We can't sort them if we have a field with a variable sized type,
2846 which will make notokay = true. In that case, we are going to return
2847 without creating varinfos for the fields anyway, so sorting them is a
2850 sort_fieldstack (fieldstack
);
2852 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
2853 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
2855 if (fo
== NULL
|| notokay
)
2857 vi
->is_unknown_size_var
= 1;
2860 VEC_free (fieldoff_s
, heap
, fieldstack
);
2865 vi
->size
= TREE_INT_CST_LOW (DECL_SIZE (field
));
2866 for (i
= 1; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
2869 const char *newname
;
2873 newindex
= VEC_length (varinfo_t
, varmap
);
2874 asprintf (&tempname
, "%s.%s", vi
->name
, alias_get_name (field
));
2875 newname
= ggc_strdup (tempname
);
2877 newvi
= new_var_info (decl
, newindex
, newname
, newindex
);
2878 newvi
->offset
= fo
->offset
;
2879 newvi
->size
= TREE_INT_CST_LOW (DECL_SIZE (field
));
2880 newvi
->fullsize
= vi
->fullsize
;
2881 insert_into_field_list (vi
, newvi
);
2882 VEC_safe_push (varinfo_t
, gc
, varmap
, newvi
);
2884 make_constraint_to_anything (newvi
);
2888 VEC_free (fieldoff_s
, heap
, fieldstack
);
2893 /* Print out the points-to solution for VAR to FILE. */
2896 dump_solution_for_var (FILE *file
, unsigned int var
)
2898 varinfo_t vi
= get_varinfo (var
);
2902 fprintf (file
, "%s = { ", vi
->name
);
2903 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi
->node
)->solution
, 0, i
, bi
)
2905 fprintf (file
, "%s ", get_varinfo (i
)->name
);
2907 fprintf (file
, "}\n");
2910 /* Print the points-to solution for VAR to stdout. */
2913 debug_solution_for_var (unsigned int var
)
2915 dump_solution_for_var (stdout
, var
);
2919 /* Create varinfo structures for all of the variables in the
2920 function for intraprocedural mode. */
2923 intra_create_variable_infos (void)
2927 /* For each incoming argument arg, ARG = &ANYTHING */
2928 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
2930 struct constraint_expr lhs
;
2931 struct constraint_expr rhs
;
2936 lhs
.var
= create_variable_info_for (t
, alias_get_name (t
));
2938 get_varinfo (lhs
.var
)->is_artificial_var
= true;
2939 rhs
.var
= anything_id
;
2940 rhs
.type
= ADDRESSOF
;
2943 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2945 struct constraint_expr temp
= lhs
;
2947 process_constraint (new_constraint (temp
, rhs
));
2953 /* Set bits in INTO corresponding to the variable uids in solution set
2957 set_uids_in_ptset (bitmap into
, bitmap from
)
2962 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
2964 varinfo_t vi
= get_varinfo (i
);
2966 /* Variables containing unions may need to be converted to their
2967 SFT's, because SFT's can have unions and we cannot. */
2968 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
2970 subvar_t svars
= get_subvars_for_var (vi
->decl
);
2972 for (sv
= svars
; sv
; sv
= sv
->next
)
2973 bitmap_set_bit (into
, DECL_UID (sv
->var
));
2975 /* We may end up with labels in the points-to set because people
2976 take their address, and they are _DECL's. */
2977 else if (TREE_CODE (vi
->decl
) == VAR_DECL
2978 || TREE_CODE (vi
->decl
) == PARM_DECL
)
2979 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
2984 static int have_alias_info
= false;
2986 /* Given a pointer variable P, fill in its points-to set, or return
2987 false if we can't. */
2990 find_what_p_points_to (tree p
)
2992 unsigned int id
= 0;
2993 if (!have_alias_info
)
2995 if (lookup_id_for_tree (p
, &id
))
2997 varinfo_t vi
= get_varinfo (id
);
2999 if (vi
->is_artificial_var
)
3002 /* See if this is a field or a structure */
3003 if (vi
->size
!= vi
->fullsize
)
3005 if (!var_can_have_subvars (vi
->decl
)
3006 || get_subvars_for_var (vi
->decl
) == NULL
)
3008 /* Nothing currently asks about structure fields directly, but when
3009 they do, we need code here to hand back the points-to set. */
3013 struct ptr_info_def
*pi
= get_ptr_info (p
);
3017 /* This variable may have been collapsed, let's get the real
3019 vi
= get_varinfo (vi
->node
);
3021 /* Make sure there aren't any artificial vars in the points to set.
3022 XXX: Note that we need to translate our heap variables to
3024 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
3026 if (get_varinfo (i
)->is_artificial_var
)
3029 pi
->pt_anything
= false;
3031 pi
->pt_vars
= BITMAP_GGC_ALLOC ();
3032 set_uids_in_ptset (pi
->pt_vars
, vi
->solution
);
3040 /* Initialize things necessary to perform PTA */
3043 init_alias_vars (void)
3045 bitmap_obstack_initialize (&ptabitmap_obstack
);
3049 /* Dump points-to information to OUTFILE. */
3052 dump_sa_points_to_info (FILE *outfile
)
3056 fprintf (outfile
, "\nPoints-to information\n\n");
3058 if (dump_flags
& TDF_STATS
)
3060 fprintf (outfile
, "Stats:\n");
3061 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
3062 fprintf (outfile
, "Statically unified vars: %d\n",
3063 stats
.unified_vars_static
);
3064 fprintf (outfile
, "Collapsed vars: %d\n", stats
.collapsed_vars
);
3065 fprintf (outfile
, "Dynamically unified vars: %d\n",
3066 stats
.unified_vars_dynamic
);
3067 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
3070 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
3071 dump_solution_for_var (outfile
, i
);
3075 /* Debug points-to information to stderr. */
3078 debug_sa_points_to_info (void)
3080 dump_sa_points_to_info (stderr
);
3084 /* Initialize the always-existing constraint variables for NULL
3085 ANYTHING, READONLY, and INTEGER */
3088 init_base_vars (void)
3090 struct constraint_expr lhs
, rhs
;
3092 /* Create the NULL variable, used to represent that a variable points
3094 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
3095 var_nothing
= new_var_info (nothing_tree
, 0, "NULL", 0);
3096 insert_id_for_tree (nothing_tree
, 0);
3097 var_nothing
->is_artificial_var
= 1;
3098 var_nothing
->offset
= 0;
3099 var_nothing
->size
= ~0;
3100 var_nothing
->fullsize
= ~0;
3102 VEC_safe_push (varinfo_t
, gc
, varmap
, var_nothing
);
3104 /* Create the ANYTHING variable, used to represent that a variable
3105 points to some unknown piece of memory. */
3106 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
3107 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING", 1);
3108 insert_id_for_tree (anything_tree
, 1);
3109 var_anything
->is_artificial_var
= 1;
3110 var_anything
->size
= ~0;
3111 var_anything
->offset
= 0;
3112 var_anything
->next
= NULL
;
3113 var_anything
->fullsize
= ~0;
3116 /* Anything points to anything. This makes deref constraints just
3117 work in the presence of linked list and other p = *p type loops,
3118 by saying that *ANYTHING = ANYTHING. */
3119 VEC_safe_push (varinfo_t
, gc
, varmap
, var_anything
);
3121 lhs
.var
= anything_id
;
3123 rhs
.type
= ADDRESSOF
;
3124 rhs
.var
= anything_id
;
3126 var_anything
->address_taken
= true;
3127 /* This specifically does not use process_constraint because
3128 process_constraint ignores all anything = anything constraints, since all
3129 but this one are redundant. */
3130 VEC_safe_push (constraint_t
, gc
, constraints
, new_constraint (lhs
, rhs
));
3132 /* Create the READONLY variable, used to represent that a variable
3133 points to readonly memory. */
3134 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
3135 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY", 2);
3136 var_readonly
->is_artificial_var
= 1;
3137 var_readonly
->offset
= 0;
3138 var_readonly
->size
= ~0;
3139 var_readonly
->fullsize
= ~0;
3140 var_readonly
->next
= NULL
;
3141 insert_id_for_tree (readonly_tree
, 2);
3143 VEC_safe_push (varinfo_t
, gc
, varmap
, var_readonly
);
3145 /* readonly memory points to anything, in order to make deref
3146 easier. In reality, it points to anything the particular
3147 readonly variable can point to, but we don't track this
3150 lhs
.var
= readonly_id
;
3152 rhs
.type
= ADDRESSOF
;
3153 rhs
.var
= anything_id
;
3156 process_constraint (new_constraint (lhs
, rhs
));
3158 /* Create the INTEGER variable, used to represent that a variable points
3160 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
3161 var_integer
= new_var_info (integer_tree
, 3, "INTEGER", 3);
3162 insert_id_for_tree (integer_tree
, 3);
3163 var_integer
->is_artificial_var
= 1;
3164 var_integer
->size
= ~0;
3165 var_integer
->fullsize
= ~0;
3166 var_integer
->offset
= 0;
3167 var_integer
->next
= NULL
;
3169 VEC_safe_push (varinfo_t
, gc
, varmap
, var_integer
);
3171 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3172 integer will point to. */
3174 lhs
.var
= integer_id
;
3176 rhs
.type
= ADDRESSOF
;
3177 rhs
.var
= anything_id
;
3179 process_constraint (new_constraint (lhs
, rhs
));
3183 /* Create points-to sets for the current function. See the comments
3184 at the start of the file for an algorithmic overview. */
3187 create_alias_vars (void)
3193 constraint_pool
= create_alloc_pool ("Constraint pool",
3194 sizeof (struct constraint
), 30);
3195 variable_info_pool
= create_alloc_pool ("Variable info pool",
3196 sizeof (struct variable_info
), 30);
3197 constraint_edge_pool
= create_alloc_pool ("Constraint edges",
3198 sizeof (struct constraint_edge
), 30);
3200 constraints
= VEC_alloc (constraint_t
, gc
, 8);
3201 varmap
= VEC_alloc (varinfo_t
, gc
, 8);
3202 id_for_tree
= htab_create (10, tree_id_hash
, tree_id_eq
, free
);
3203 memset (&stats
, 0, sizeof (stats
));
3207 intra_create_variable_infos ();
3209 /* Now walk all statements and derive aliases. */
3212 block_stmt_iterator bsi
;
3215 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
3216 if (is_gimple_reg (PHI_RESULT (phi
)))
3217 find_func_aliases (phi
);
3219 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3220 find_func_aliases (bsi_stmt (bsi
));
3223 build_constraint_graph ();
3227 fprintf (dump_file
, "Constraints:\n");
3228 dump_constraints (dump_file
);
3232 fprintf (dump_file
, "Collapsing static cycles and doing variable substitution:\n");
3234 find_and_collapse_graph_cycles (graph
, false);
3235 perform_var_substitution (graph
);
3238 fprintf (dump_file
, "Solving graph:\n");
3240 solve_graph (graph
);
3243 dump_sa_points_to_info (dump_file
);
3245 have_alias_info
= true;
3248 struct tree_opt_pass pass_build_pta
=
3252 create_alias_vars
, /* execute */
3255 0, /* static_pass_number */
3256 TV_TREE_PTA
, /* tv_id */
3257 PROP_cfg
, /* properties_required */
3258 PROP_pta
, /* properties_provided */
3259 0, /* properties_destroyed */
3260 0, /* todo_flags_start */
3261 0, /* todo_flags_finish */
3266 /* Delete created points-to sets. */
3269 delete_alias_vars (void)
3271 htab_delete (id_for_tree
);
3272 free_alloc_pool (variable_info_pool
);
3273 free_alloc_pool (constraint_pool
);
3274 free_alloc_pool (constraint_edge_pool
);
3275 bitmap_obstack_release (&ptabitmap_obstack
);
3276 have_alias_info
= false;
3279 struct tree_opt_pass pass_del_pta
=
3283 delete_alias_vars
, /* execute */
3286 0, /* static_pass_number */
3287 TV_TREE_PTA
, /* tv_id */
3288 PROP_pta
, /* properties_required */
3289 0, /* properties_provided */
3290 PROP_pta
, /* properties_destroyed */
3291 0, /* todo_flags_start */
3292 0, /* todo_flags_finish */