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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24 #include "coretypes.h"
29 #include "tree-ssa-structalias.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
38 #include "diagnostic.h"
41 #include "tree-flow.h"
42 #include "tree-inline.h"
45 #include "tree-gimple.h"
49 #include "tree-pass.h"
51 #include "alloc-pool.h"
52 #include "splay-tree.h"
54 /* The idea behind this analyzer is to generate set constraints from the
55 program, then solve the resulting constraints in order to generate the
58 Set constraints are a way of modeling program analysis problems that
59 involve sets. They consist of an inclusion constraint language,
60 describing the variables (each variable is a set) and operations that
61 are involved on the variables, and a set of rules that derive facts
62 from these operations. To solve a system of set constraints, you derive
63 all possible facts under the rules, which gives you the correct sets
66 See "Efficient Field-sensitive pointer analysis for C" by "David
67 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
68 http://citeseer.ist.psu.edu/pearce04efficient.html
70 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
71 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
72 http://citeseer.ist.psu.edu/heintze01ultrafast.html
74 There are three types of constraint expressions, DEREF, ADDRESSOF, and
75 SCALAR. Each constraint expression consists of a constraint type,
76 a variable, and an offset.
78 SCALAR is a constraint expression type used to represent x, whether
79 it appears on the LHS or the RHS of a statement.
80 DEREF is a constraint expression type used to represent *x, whether
81 it appears on the LHS or the RHS of a statement.
82 ADDRESSOF is a constraint expression used to represent &x, whether
83 it appears on the LHS or the RHS of a statement.
85 Each pointer variable in the program is assigned an integer id, and
86 each field of a structure variable is assigned an integer id as well.
88 Structure variables are linked to their list of fields through a "next
89 field" in each variable that points to the next field in offset
91 Each variable for a structure field has
93 1. "size", that tells the size in bits of that field.
94 2. "fullsize, that tells the size in bits of the entire structure.
95 3. "offset", that tells the offset in bits from the beginning of the
96 structure to this field.
108 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
109 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
110 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
113 In order to solve the system of set constraints, the following is
116 1. Each constraint variable x has a solution set associated with it,
119 2. Constraints are separated into direct, copy, and complex.
120 Direct constraints are ADDRESSOF constraints that require no extra
121 processing, such as P = &Q
122 Copy constraints are those of the form P = Q.
123 Complex constraints are all the constraints involving dereferences.
125 3. All direct constraints of the form P = &Q are processed, such
126 that Q is added to Sol(P)
128 4. All complex constraints for a given constraint variable are stored in a
129 linked list attached to that variable's node.
131 5. A directed graph is built out of the copy constraints. Each
132 constraint variable is a node in the graph, and an edge from
133 Q to P is added for each copy constraint of the form P = Q
135 6. The graph is then walked, and solution sets are
136 propagated along the copy edges, such that an edge from Q to P
137 causes Sol(P) <- Sol(P) union Sol(Q).
139 7. As we visit each node, all complex constraints associated with
140 that node are processed by adding appropriate copy edges to the graph, or the
141 appropriate variables to the solution set.
143 8. The process of walking the graph is iterated until no solution
146 Prior to walking the graph in steps 6 and 7, We perform static
147 cycle elimination on the constraint graph, as well
148 as off-line variable substitution.
150 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
151 on and turned into anything), but isn't. You can just see what offset
152 inside the pointed-to struct it's going to access.
154 TODO: Constant bounded arrays can be handled as if they were structs of the
155 same number of elements.
157 TODO: Modeling heap and incoming pointers becomes much better if we
158 add fields to them as we discover them, which we could do.
160 TODO: We could handle unions, but to be honest, it's probably not
161 worth the pain or slowdown. */
163 static bool use_field_sensitive
= true;
164 static unsigned int create_variable_info_for (tree
, const char *);
165 static struct constraint_expr
get_constraint_for (tree
);
166 static void build_constraint_graph (void);
168 static bitmap_obstack ptabitmap_obstack
;
169 static bitmap_obstack iteration_obstack
;
170 DEF_VEC_P(constraint_t
);
171 DEF_VEC_ALLOC_P(constraint_t
,gc
);
173 static struct constraint_stats
175 unsigned int total_vars
;
176 unsigned int collapsed_vars
;
177 unsigned int unified_vars_static
;
178 unsigned int unified_vars_dynamic
;
179 unsigned int iterations
;
184 /* ID of this variable */
187 /* Name of this variable */
190 /* Tree that this variable is associated with. */
193 /* Offset of this variable, in bits, from the base variable */
194 unsigned HOST_WIDE_INT offset
;
196 /* Size of the variable, in bits. */
197 unsigned HOST_WIDE_INT size
;
199 /* Full size of the base variable, in bits. */
200 unsigned HOST_WIDE_INT fullsize
;
202 /* A link to the variable for the next field in this structure. */
203 struct variable_info
*next
;
205 /* Node in the graph that represents the constraints and points-to
206 solution for the variable. */
209 /* True if the address of this variable is taken. Needed for
210 variable substitution. */
211 unsigned int address_taken
:1;
213 /* True if this variable is the target of a dereference. Needed for
214 variable substitution. */
215 unsigned int indirect_target
:1;
217 /* True if this is a variable created by the constraint analysis, such as
218 heap variables and constraints we had to break up. */
219 unsigned int is_artificial_var
:1;
221 /* True for variables whose size is not known or variable. */
222 unsigned int is_unknown_size_var
:1;
224 /* True for variables that have unions somewhere in them. */
225 unsigned int has_union
:1;
227 /* Points-to set for this variable. */
230 /* Variable ids represented by this node. */
233 /* Vector of complex constraints for this node. Complex
234 constraints are those involving dereferences. */
235 VEC(constraint_t
,gc
) *complex;
237 typedef struct variable_info
*varinfo_t
;
239 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
241 /* Pool of variable info structures. */
242 static alloc_pool variable_info_pool
;
244 DEF_VEC_P(varinfo_t
);
246 DEF_VEC_ALLOC_P(varinfo_t
, gc
);
248 /* Table of variable info structures for constraint variables. Indexed directly
249 by variable info id. */
250 static VEC(varinfo_t
,gc
) *varmap
;
251 #define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
253 /* Variable that represents the unknown pointer. */
254 static varinfo_t var_anything
;
255 static tree anything_tree
;
256 static unsigned int anything_id
;
258 /* Variable that represents the NULL pointer. */
259 static varinfo_t var_nothing
;
260 static tree nothing_tree
;
261 static unsigned int nothing_id
;
263 /* Variable that represents read only memory. */
264 static varinfo_t var_readonly
;
265 static tree readonly_tree
;
266 static unsigned int readonly_id
;
268 /* Variable that represents integers. This is used for when people do things
270 static varinfo_t var_integer
;
271 static tree integer_tree
;
272 static unsigned int integer_id
;
275 /* Return a new variable info structure consisting for a variable
276 named NAME, and using constraint graph node NODE. */
279 new_var_info (tree t
, unsigned int id
, const char *name
, unsigned int node
)
281 varinfo_t ret
= pool_alloc (variable_info_pool
);
287 ret
->address_taken
= false;
288 ret
->indirect_target
= false;
289 ret
->is_artificial_var
= false;
290 ret
->is_unknown_size_var
= false;
291 ret
->solution
= BITMAP_ALLOC (&ptabitmap_obstack
);
292 bitmap_clear (ret
->solution
);
293 ret
->variables
= BITMAP_ALLOC (&ptabitmap_obstack
);
294 bitmap_clear (ret
->variables
);
300 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
302 /* An expression that appears in a constraint. */
304 struct constraint_expr
306 /* Constraint type. */
307 constraint_expr_type type
;
309 /* Variable we are referring to in the constraint. */
312 /* Offset, in bits, of this constraint from the beginning of
313 variables it ends up referring to.
315 IOW, in a deref constraint, we would deref, get the result set,
316 then add OFFSET to each member. */
317 unsigned HOST_WIDE_INT offset
;
320 static struct constraint_expr
do_deref (struct constraint_expr
);
322 /* Our set constraints are made up of two constraint expressions, one
325 As described in the introduction, our set constraints each represent an
326 operation between set valued variables.
330 struct constraint_expr lhs
;
331 struct constraint_expr rhs
;
334 /* List of constraints that we use to build the constraint graph from. */
336 static VEC(constraint_t
,gc
) *constraints
;
337 static alloc_pool constraint_pool
;
339 /* An edge in the constraint graph. We technically have no use for
340 the src, since it will always be the same node that we are indexing
341 into the pred/succ arrays with, but it's nice for checking
342 purposes. The edges are weighted, with a bit set in weights for
343 each edge from src to dest with that weight. */
345 struct constraint_edge
352 typedef struct constraint_edge
*constraint_edge_t
;
353 static alloc_pool constraint_edge_pool
;
355 /* Return a new constraint edge from SRC to DEST. */
357 static constraint_edge_t
358 new_constraint_edge (unsigned int src
, unsigned int dest
)
360 constraint_edge_t ret
= pool_alloc (constraint_edge_pool
);
367 DEF_VEC_P(constraint_edge_t
);
368 DEF_VEC_ALLOC_P(constraint_edge_t
,gc
);
371 /* The constraint graph is simply a set of adjacency vectors, one per
372 variable. succs[x] is the vector of successors for variable x, and preds[x]
373 is the vector of predecessors for variable x.
374 IOW, all edges are "forward" edges, which is not like our CFG.
376 preds[x]->src == x, and
379 struct constraint_graph
381 VEC(constraint_edge_t
,gc
) **succs
;
382 VEC(constraint_edge_t
,gc
) **preds
;
385 typedef struct constraint_graph
*constraint_graph_t
;
387 static constraint_graph_t graph
;
389 /* Create a new constraint consisting of LHS and RHS expressions. */
392 new_constraint (const struct constraint_expr lhs
,
393 const struct constraint_expr rhs
)
395 constraint_t ret
= pool_alloc (constraint_pool
);
401 /* Print out constraint C to FILE. */
404 dump_constraint (FILE *file
, constraint_t c
)
406 if (c
->lhs
.type
== ADDRESSOF
)
408 else if (c
->lhs
.type
== DEREF
)
410 fprintf (file
, "%s", get_varinfo (c
->lhs
.var
)->name
);
411 if (c
->lhs
.offset
!= 0)
412 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
413 fprintf (file
, " = ");
414 if (c
->rhs
.type
== ADDRESSOF
)
416 else if (c
->rhs
.type
== DEREF
)
418 fprintf (file
, "%s", get_varinfo (c
->rhs
.var
)->name
);
419 if (c
->rhs
.offset
!= 0)
420 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
421 fprintf (file
, "\n");
424 /* Print out constraint C to stderr. */
427 debug_constraint (constraint_t c
)
429 dump_constraint (stderr
, c
);
432 /* Print out all constraints to FILE */
435 dump_constraints (FILE *file
)
439 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
440 dump_constraint (file
, c
);
443 /* Print out all constraints to stderr. */
446 debug_constraints (void)
448 dump_constraints (stderr
);
453 The solver is a simple worklist solver, that works on the following
456 sbitmap changed_nodes = all ones;
457 changed_count = number of nodes;
458 For each node that was already collapsed:
462 while (changed_count > 0)
464 compute topological ordering for constraint graph
466 find and collapse cycles in the constraint graph (updating
467 changed if necessary)
469 for each node (n) in the graph in topological order:
472 Process each complex constraint associated with the node,
473 updating changed if necessary.
475 For each outgoing edge from n, propagate the solution from n to
476 the destination of the edge, updating changed as necessary.
480 /* Return true if two constraint expressions A and B are equal. */
483 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
485 return a
.type
== b
.type
487 && a
.offset
== b
.offset
;
490 /* Return true if constraint expression A is less than constraint expression
491 B. This is just arbitrary, but consistent, in order to give them an
495 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
497 if (a
.type
== b
.type
)
500 return a
.offset
< b
.offset
;
502 return a
.var
< b
.var
;
505 return a
.type
< b
.type
;
508 /* Return true if constraint A is less than constraint B. This is just
509 arbitrary, but consistent, in order to give them an ordering. */
512 constraint_less (const constraint_t a
, const constraint_t b
)
514 if (constraint_expr_less (a
->lhs
, b
->lhs
))
516 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
519 return constraint_expr_less (a
->rhs
, b
->rhs
);
522 /* Return true if two constraints A and B are equal. */
525 constraint_equal (struct constraint a
, struct constraint b
)
527 return constraint_expr_equal (a
.lhs
, b
.lhs
)
528 && constraint_expr_equal (a
.rhs
, b
.rhs
);
532 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
535 constraint_vec_find (VEC(constraint_t
,gc
) *vec
,
536 struct constraint lookfor
)
544 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
545 if (place
>= VEC_length (constraint_t
, vec
))
547 found
= VEC_index (constraint_t
, vec
, place
);
548 if (!constraint_equal (*found
, lookfor
))
553 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
556 constraint_set_union (VEC(constraint_t
,gc
) **to
,
557 VEC(constraint_t
,gc
) **from
)
562 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
564 if (constraint_vec_find (*to
, *c
) == NULL
)
566 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
568 VEC_safe_insert (constraint_t
, gc
, *to
, place
, c
);
573 /* Take a solution set SET, add OFFSET to each member of the set, and
574 overwrite SET with the result when done. */
577 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
579 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
583 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
585 /* If this is a properly sized variable, only add offset if it's
586 less than end. Otherwise, it is globbed to a single
589 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
591 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
592 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
593 bitmap_set_bit (result
, v
->id
);
595 else if (get_varinfo (i
)->is_artificial_var
596 || get_varinfo (i
)->is_unknown_size_var
)
598 bitmap_set_bit (result
, i
);
602 bitmap_copy (set
, result
);
603 BITMAP_FREE (result
);
606 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
610 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
613 return bitmap_ior_into (to
, from
);
619 tmp
= BITMAP_ALLOC (&iteration_obstack
);
620 bitmap_copy (tmp
, from
);
621 solution_set_add (tmp
, inc
);
622 res
= bitmap_ior_into (to
, tmp
);
628 /* Insert constraint C into the list of complex constraints for VAR. */
631 insert_into_complex (unsigned int var
, constraint_t c
)
633 varinfo_t vi
= get_varinfo (var
);
634 unsigned int place
= VEC_lower_bound (constraint_t
, vi
->complex, c
,
636 VEC_safe_insert (constraint_t
, gc
, vi
->complex, place
, c
);
640 /* Compare two constraint edges A and B, return true if they are equal. */
643 constraint_edge_equal (struct constraint_edge a
, struct constraint_edge b
)
645 return a
.src
== b
.src
&& a
.dest
== b
.dest
;
648 /* Compare two constraint edges, return true if A is less than B */
651 constraint_edge_less (const constraint_edge_t a
, const constraint_edge_t b
)
653 if (a
->dest
< b
->dest
)
655 else if (a
->dest
== b
->dest
)
656 return a
->src
< b
->src
;
661 /* Find the constraint edge that matches LOOKFOR, in VEC.
662 Return the edge, if found, NULL otherwise. */
664 static constraint_edge_t
665 constraint_edge_vec_find (VEC(constraint_edge_t
,gc
) *vec
,
666 struct constraint_edge lookfor
)
669 constraint_edge_t edge
;
671 place
= VEC_lower_bound (constraint_edge_t
, vec
, &lookfor
,
672 constraint_edge_less
);
673 edge
= VEC_index (constraint_edge_t
, vec
, place
);
674 if (!constraint_edge_equal (*edge
, lookfor
))
679 /* Condense two variable nodes into a single variable node, by moving
680 all associated info from SRC to TO. */
683 condense_varmap_nodes (unsigned int to
, unsigned int src
)
685 varinfo_t tovi
= get_varinfo (to
);
686 varinfo_t srcvi
= get_varinfo (src
);
691 /* the src node, and all its variables, are now the to node. */
693 EXECUTE_IF_SET_IN_BITMAP (srcvi
->variables
, 0, i
, bi
)
694 get_varinfo (i
)->node
= to
;
696 /* Merge the src node variables and the to node variables. */
697 bitmap_set_bit (tovi
->variables
, src
);
698 bitmap_ior_into (tovi
->variables
, srcvi
->variables
);
699 bitmap_clear (srcvi
->variables
);
701 /* Move all complex constraints from src node into to node */
702 for (i
= 0; VEC_iterate (constraint_t
, srcvi
->complex, i
, c
); i
++)
704 /* In complex constraints for node src, we may have either
705 a = *src, and *src = a. */
707 if (c
->rhs
.type
== DEREF
)
712 constraint_set_union (&tovi
->complex, &srcvi
->complex);
713 srcvi
->complex = NULL
;
716 /* Erase EDGE from GRAPH. This routine only handles self-edges
717 (e.g. an edge from a to a). */
720 erase_graph_self_edge (constraint_graph_t graph
, struct constraint_edge edge
)
722 VEC(constraint_edge_t
,gc
) *predvec
= graph
->preds
[edge
.src
];
723 VEC(constraint_edge_t
,gc
) *succvec
= graph
->succs
[edge
.dest
];
725 gcc_assert (edge
.src
== edge
.dest
);
727 /* Remove from the successors. */
728 place
= VEC_lower_bound (constraint_edge_t
, succvec
, &edge
,
729 constraint_edge_less
);
731 /* Make sure we found the edge. */
732 #ifdef ENABLE_CHECKING
734 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, succvec
, place
);
735 gcc_assert (constraint_edge_equal (*tmp
, edge
));
738 VEC_ordered_remove (constraint_edge_t
, succvec
, place
);
740 /* Remove from the predecessors. */
741 place
= VEC_lower_bound (constraint_edge_t
, predvec
, &edge
,
742 constraint_edge_less
);
744 /* Make sure we found the edge. */
745 #ifdef ENABLE_CHECKING
747 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, predvec
, place
);
748 gcc_assert (constraint_edge_equal (*tmp
, edge
));
751 VEC_ordered_remove (constraint_edge_t
, predvec
, place
);
754 /* Remove edges involving NODE from GRAPH. */
757 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
759 VEC(constraint_edge_t
,gc
) *succvec
= graph
->succs
[node
];
760 VEC(constraint_edge_t
,gc
) *predvec
= graph
->preds
[node
];
764 /* Walk the successors, erase the associated preds. */
765 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
769 struct constraint_edge lookfor
;
770 lookfor
.src
= c
->dest
;
772 place
= VEC_lower_bound (constraint_edge_t
, graph
->preds
[c
->dest
],
773 &lookfor
, constraint_edge_less
);
774 VEC_ordered_remove (constraint_edge_t
, graph
->preds
[c
->dest
], place
);
776 /* Walk the preds, erase the associated succs. */
777 for (i
=0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
781 struct constraint_edge lookfor
;
782 lookfor
.src
= c
->dest
;
784 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[c
->dest
],
785 &lookfor
, constraint_edge_less
);
786 VEC_ordered_remove (constraint_edge_t
, graph
->succs
[c
->dest
], place
);
789 graph
->preds
[node
] = NULL
;
790 graph
->succs
[node
] = NULL
;
793 static bool edge_added
= false;
795 /* Add edge NEWE to the graph. */
798 add_graph_edge (constraint_graph_t graph
, struct constraint_edge newe
)
801 unsigned int src
= newe
.src
;
802 unsigned int dest
= newe
.dest
;
803 VEC(constraint_edge_t
,gc
) *vec
;
805 vec
= graph
->preds
[src
];
806 place
= VEC_lower_bound (constraint_edge_t
, vec
, &newe
,
807 constraint_edge_less
);
808 if (place
== VEC_length (constraint_edge_t
, vec
)
809 || VEC_index (constraint_edge_t
, vec
, place
)->dest
!= dest
)
811 constraint_edge_t edge
= new_constraint_edge (src
, dest
);
814 weightbitmap
= BITMAP_ALLOC (&ptabitmap_obstack
);
815 edge
->weights
= weightbitmap
;
816 VEC_safe_insert (constraint_edge_t
, gc
, graph
->preds
[edge
->src
],
818 edge
= new_constraint_edge (dest
, src
);
819 edge
->weights
= weightbitmap
;
820 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[edge
->src
],
821 edge
, constraint_edge_less
);
822 VEC_safe_insert (constraint_edge_t
, gc
, graph
->succs
[edge
->src
],
832 /* Return the bitmap representing the weights of edge LOOKFOR */
835 get_graph_weights (constraint_graph_t graph
, struct constraint_edge lookfor
)
837 constraint_edge_t edge
;
838 unsigned int src
= lookfor
.src
;
839 VEC(constraint_edge_t
,gc
) *vec
;
840 vec
= graph
->preds
[src
];
841 edge
= constraint_edge_vec_find (vec
, lookfor
);
842 gcc_assert (edge
!= NULL
);
843 return edge
->weights
;
847 /* Merge GRAPH nodes FROM and TO into node TO. */
850 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
853 VEC(constraint_edge_t
,gc
) *succvec
= graph
->succs
[from
];
854 VEC(constraint_edge_t
,gc
) *predvec
= graph
->preds
[from
];
858 /* Merge all the predecessor edges. */
860 for (i
= 0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
862 unsigned int d
= c
->dest
;
863 struct constraint_edge olde
;
864 struct constraint_edge newe
;
871 add_graph_edge (graph
, newe
);
874 temp
= get_graph_weights (graph
, olde
);
875 weights
= get_graph_weights (graph
, newe
);
876 bitmap_ior_into (weights
, temp
);
879 /* Merge all the successor edges. */
880 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
882 unsigned int d
= c
->dest
;
883 struct constraint_edge olde
;
884 struct constraint_edge newe
;
891 add_graph_edge (graph
, newe
);
894 temp
= get_graph_weights (graph
, olde
);
895 weights
= get_graph_weights (graph
, newe
);
896 bitmap_ior_into (weights
, temp
);
898 clear_edges_for_node (graph
, from
);
901 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
902 it doesn't exist in the graph already.
903 Return false if the edge already existed, true otherwise. */
906 int_add_graph_edge (constraint_graph_t graph
, unsigned int to
,
907 unsigned int from
, unsigned HOST_WIDE_INT weight
)
909 if (to
== from
&& weight
== 0)
916 struct constraint_edge edge
;
919 r
= add_graph_edge (graph
, edge
);
920 r
|= !bitmap_bit_p (get_graph_weights (graph
, edge
), weight
);
921 bitmap_set_bit (get_graph_weights (graph
, edge
), weight
);
927 /* Return true if LOOKFOR is an existing graph edge. */
930 valid_graph_edge (constraint_graph_t graph
, struct constraint_edge lookfor
)
932 return constraint_edge_vec_find (graph
->preds
[lookfor
.src
], lookfor
) != NULL
;
936 /* Build the constraint graph. */
939 build_constraint_graph (void)
944 graph
= ggc_alloc (sizeof (struct constraint_graph
));
945 graph
->succs
= ggc_alloc_cleared (VEC_length (varinfo_t
, varmap
) * sizeof (*graph
->succs
));
946 graph
->preds
= ggc_alloc_cleared (VEC_length (varinfo_t
, varmap
) * sizeof (*graph
->preds
));
947 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
949 struct constraint_expr lhs
= c
->lhs
;
950 struct constraint_expr rhs
= c
->rhs
;
951 if (lhs
.type
== DEREF
)
953 /* *x = y or *x = &y (complex) */
954 if (rhs
.type
== ADDRESSOF
|| rhs
.var
> anything_id
)
955 insert_into_complex (lhs
.var
, c
);
957 else if (rhs
.type
== DEREF
)
960 if (lhs
.var
> anything_id
)
961 insert_into_complex (rhs
.var
, c
);
963 else if (rhs
.type
== ADDRESSOF
)
966 bitmap_set_bit (get_varinfo (lhs
.var
)->solution
, rhs
.var
);
968 else if (rhs
.var
> anything_id
&& lhs
.var
> anything_id
)
970 /* Ignore 0 weighted self edges, as they can't possibly contribute
972 if (lhs
.var
!= rhs
.var
|| rhs
.offset
!= 0 || lhs
.offset
!= 0)
975 struct constraint_edge edge
;
979 add_graph_edge (graph
, edge
);
980 bitmap_set_bit (get_graph_weights (graph
, edge
),
987 /* Changed variables on the last iteration. */
988 static unsigned int changed_count
;
989 static sbitmap changed
;
992 DEF_VEC_ALLOC_I(uint
,heap
);
995 /* Strongly Connected Component visitation info. */
1000 sbitmap in_component
;
1002 unsigned int *visited_index
;
1003 VEC(uint
,heap
) *scc_stack
;
1004 VEC(uint
,heap
) *unification_queue
;
1008 /* Recursive routine to find strongly connected components in GRAPH.
1009 SI is the SCC info to store the information in, and N is the id of current
1010 graph node we are processing.
1012 This is Tarjan's strongly connected component finding algorithm, as
1013 modified by Nuutila to keep only non-root nodes on the stack.
1014 The algorithm can be found in "On finding the strongly connected
1015 connected components in a directed graph" by Esko Nuutila and Eljas
1016 Soisalon-Soininen, in Information Processing Letters volume 49,
1017 number 1, pages 9-14. */
1020 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1022 constraint_edge_t c
;
1025 gcc_assert (get_varinfo (n
)->node
== n
);
1026 SET_BIT (si
->visited
, n
);
1027 RESET_BIT (si
->in_component
, n
);
1028 si
->visited_index
[n
] = si
->current_index
++;
1030 /* Visit all the successors. */
1031 for (i
= 0; VEC_iterate (constraint_edge_t
, graph
->succs
[n
], i
, c
); i
++)
1033 /* We only want to find and collapse the zero weight edges. */
1034 if (bitmap_bit_p (c
->weights
, 0))
1036 unsigned int w
= c
->dest
;
1037 if (!TEST_BIT (si
->visited
, w
))
1038 scc_visit (graph
, si
, w
);
1039 if (!TEST_BIT (si
->in_component
, w
))
1041 unsigned int t
= get_varinfo (w
)->node
;
1042 unsigned int nnode
= get_varinfo (n
)->node
;
1043 if (si
->visited_index
[t
] < si
->visited_index
[nnode
])
1044 get_varinfo (n
)->node
= t
;
1049 /* See if any components have been identified. */
1050 if (get_varinfo (n
)->node
== n
)
1052 unsigned int t
= si
->visited_index
[n
];
1053 SET_BIT (si
->in_component
, n
);
1054 while (VEC_length (uint
, si
->scc_stack
) != 0
1055 && t
< si
->visited_index
[VEC_last (uint
, si
->scc_stack
)])
1057 unsigned int w
= VEC_pop (uint
, si
->scc_stack
);
1058 get_varinfo (w
)->node
= n
;
1059 SET_BIT (si
->in_component
, w
);
1060 /* Mark this node for collapsing. */
1061 VEC_safe_push (uint
, heap
, si
->unification_queue
, w
);
1065 VEC_safe_push (uint
, heap
, si
->scc_stack
, n
);
1069 /* Collapse two variables into one variable. */
1072 collapse_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
)
1074 bitmap tosol
, fromsol
;
1075 struct constraint_edge edge
;
1078 condense_varmap_nodes (to
, from
);
1079 tosol
= get_varinfo (to
)->solution
;
1080 fromsol
= get_varinfo (from
)->solution
;
1081 bitmap_ior_into (tosol
, fromsol
);
1082 merge_graph_nodes (graph
, to
, from
);
1085 if (valid_graph_edge (graph
, edge
))
1087 bitmap weights
= get_graph_weights (graph
, edge
);
1088 bitmap_clear_bit (weights
, 0);
1089 if (bitmap_empty_p (weights
))
1090 erase_graph_self_edge (graph
, edge
);
1092 bitmap_clear (fromsol
);
1093 get_varinfo (to
)->address_taken
|= get_varinfo (from
)->address_taken
;
1094 get_varinfo (to
)->indirect_target
|= get_varinfo (from
)->indirect_target
;
1098 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1099 SI is the Strongly Connected Components information structure that tells us
1100 what components to unify.
1101 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1102 count should be updated to reflect the unification. */
1105 process_unification_queue (constraint_graph_t graph
, struct scc_info
*si
,
1106 bool update_changed
)
1109 bitmap tmp
= BITMAP_ALLOC (update_changed
? &iteration_obstack
: NULL
);
1112 /* We proceed as follows:
1114 For each component in the queue (components are delineated by
1115 when current_queue_element->node != next_queue_element->node):
1117 rep = representative node for component
1119 For each node (tounify) to be unified in the component,
1120 merge the solution for tounify into tmp bitmap
1122 clear solution for tounify
1124 merge edges from tounify into rep
1126 merge complex constraints from tounify into rep
1128 update changed count to note that tounify will never change
1131 Merge tmp into solution for rep, marking rep changed if this
1132 changed rep's solution.
1134 Delete any 0 weighted self-edges we now have for rep. */
1135 while (i
!= VEC_length (uint
, si
->unification_queue
))
1137 unsigned int tounify
= VEC_index (uint
, si
->unification_queue
, i
);
1138 unsigned int n
= get_varinfo (tounify
)->node
;
1140 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1141 fprintf (dump_file
, "Unifying %s to %s\n",
1142 get_varinfo (tounify
)->name
,
1143 get_varinfo (n
)->name
);
1145 stats
.unified_vars_dynamic
++;
1147 stats
.unified_vars_static
++;
1148 bitmap_ior_into (tmp
, get_varinfo (tounify
)->solution
);
1149 merge_graph_nodes (graph
, n
, tounify
);
1150 condense_varmap_nodes (n
, tounify
);
1152 if (update_changed
&& TEST_BIT (changed
, tounify
))
1154 RESET_BIT (changed
, tounify
);
1155 if (!TEST_BIT (changed
, n
))
1156 SET_BIT (changed
, n
);
1159 gcc_assert (changed_count
> 0);
1164 bitmap_clear (get_varinfo (tounify
)->solution
);
1167 /* If we've either finished processing the entire queue, or
1168 finished processing all nodes for component n, update the solution for
1170 if (i
== VEC_length (uint
, si
->unification_queue
)
1171 || get_varinfo (VEC_index (uint
, si
->unification_queue
, i
))->node
!= n
)
1173 struct constraint_edge edge
;
1175 /* If the solution changes because of the merging, we need to mark
1176 the variable as changed. */
1177 if (bitmap_ior_into (get_varinfo (n
)->solution
, tmp
))
1179 if (update_changed
&& !TEST_BIT (changed
, n
))
1181 SET_BIT (changed
, n
);
1188 if (valid_graph_edge (graph
, edge
))
1190 bitmap weights
= get_graph_weights (graph
, edge
);
1191 bitmap_clear_bit (weights
, 0);
1192 if (bitmap_empty_p (weights
))
1193 erase_graph_self_edge (graph
, edge
);
1201 /* Information needed to compute the topological ordering of a graph. */
1205 /* sbitmap of visited nodes. */
1207 /* Array that stores the topological order of the graph, *in
1209 VEC(uint
,heap
) *topo_order
;
1213 /* Initialize and return a topological info structure. */
1215 static struct topo_info
*
1216 init_topo_info (void)
1218 size_t size
= VEC_length (varinfo_t
, varmap
);
1219 struct topo_info
*ti
= xmalloc (sizeof (struct topo_info
));
1220 ti
->visited
= sbitmap_alloc (size
);
1221 sbitmap_zero (ti
->visited
);
1222 ti
->topo_order
= VEC_alloc (uint
, heap
, 1);
1227 /* Free the topological sort info pointed to by TI. */
1230 free_topo_info (struct topo_info
*ti
)
1232 sbitmap_free (ti
->visited
);
1233 VEC_free (uint
, heap
, ti
->topo_order
);
1237 /* Visit the graph in topological order, and store the order in the
1238 topo_info structure. */
1241 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1244 VEC(constraint_edge_t
,gc
) *succs
= graph
->succs
[n
];
1245 constraint_edge_t c
;
1247 SET_BIT (ti
->visited
, n
);
1248 for (i
= 0; VEC_iterate (constraint_edge_t
, succs
, i
, c
); i
++)
1250 if (!TEST_BIT (ti
->visited
, c
->dest
))
1251 topo_visit (graph
, ti
, c
->dest
);
1253 VEC_safe_push (uint
, heap
, ti
->topo_order
, n
);
1256 /* Return true if variable N + OFFSET is a legal field of N. */
1259 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1261 varinfo_t ninfo
= get_varinfo (n
);
1263 /* For things we've globbed to single variables, any offset into the
1264 variable acts like the entire variable, so that it becomes offset
1266 if (n
== anything_id
1267 || ninfo
->is_artificial_var
1268 || ninfo
->is_unknown_size_var
)
1273 return n
> anything_id
1274 && (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1277 /* Process a constraint C that represents *x = &y. */
1280 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1281 constraint_t c
, bitmap delta
)
1283 unsigned int rhs
= c
->rhs
.var
;
1284 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1288 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1289 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1291 if (type_safe (j
, &offset
))
1293 /* *x != NULL && *x != ANYTHING*/
1297 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1298 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1300 sol
= get_varinfo (t
)->solution
;
1301 if (!bitmap_bit_p (sol
, rhs
))
1303 bitmap_set_bit (sol
, rhs
);
1304 if (!TEST_BIT (changed
, t
))
1306 SET_BIT (changed
, t
);
1312 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1317 /* Process a constraint C that represents x = *y, using DELTA as the
1318 starting solution. */
1321 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1324 unsigned int lhs
= get_varinfo (c
->lhs
.var
)->node
;
1325 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1327 bitmap sol
= get_varinfo (lhs
)->solution
;
1331 /* For each variable j in delta (Sol(y)), add
1332 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1333 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1335 if (type_safe (j
, &roffset
))
1338 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1341 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1343 if (int_add_graph_edge (graph
, lhs
, t
, 0))
1344 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1347 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1351 /* If the LHS solution changed, mark the var as changed. */
1354 get_varinfo (lhs
)->solution
= sol
;
1355 if (!TEST_BIT (changed
, lhs
))
1357 SET_BIT (changed
, lhs
);
1363 /* Process a constraint C that represents *x = y. */
1366 do_ds_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1368 unsigned int rhs
= get_varinfo (c
->rhs
.var
)->node
;
1369 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1370 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1371 bitmap sol
= get_varinfo (rhs
)->solution
;
1375 /* For each member j of delta (Sol(x)), add an edge from y to j and
1376 union Sol(y) into Sol(j) */
1377 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1379 if (type_safe (j
, &loff
))
1383 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1385 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1387 if (int_add_graph_edge (graph
, t
, rhs
, roff
))
1389 bitmap tmp
= get_varinfo (t
)->solution
;
1390 if (set_union_with_increment (tmp
, sol
, roff
))
1392 get_varinfo (t
)->solution
= tmp
;
1395 sol
= get_varinfo (rhs
)->solution
;
1397 if (!TEST_BIT (changed
, t
))
1399 SET_BIT (changed
, t
);
1406 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1410 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1411 constraint (IE *x = &y, x = *y, and *x = y). */
1414 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1416 if (c
->lhs
.type
== DEREF
)
1418 if (c
->rhs
.type
== ADDRESSOF
)
1421 do_da_constraint (graph
, c
, delta
);
1426 do_ds_constraint (graph
, c
, delta
);
1432 do_sd_constraint (graph
, c
, delta
);
1436 /* Initialize and return a new SCC info structure. */
1438 static struct scc_info
*
1439 init_scc_info (void)
1441 struct scc_info
*si
= xmalloc (sizeof (struct scc_info
));
1442 size_t size
= VEC_length (varinfo_t
, varmap
);
1444 si
->current_index
= 0;
1445 si
->visited
= sbitmap_alloc (size
);
1446 sbitmap_zero (si
->visited
);
1447 si
->in_component
= sbitmap_alloc (size
);
1448 sbitmap_ones (si
->in_component
);
1449 si
->visited_index
= xcalloc (sizeof (unsigned int), size
+ 1);
1450 si
->scc_stack
= VEC_alloc (uint
, heap
, 1);
1451 si
->unification_queue
= VEC_alloc (uint
, heap
, 1);
1455 /* Free an SCC info structure pointed to by SI */
1458 free_scc_info (struct scc_info
*si
)
1460 sbitmap_free (si
->visited
);
1461 sbitmap_free (si
->in_component
);
1462 free (si
->visited_index
);
1463 VEC_free (uint
, heap
, si
->scc_stack
);
1464 VEC_free (uint
, heap
, si
->unification_queue
);
1469 /* Find cycles in GRAPH that occur, using strongly connected components, and
1470 collapse the cycles into a single representative node. if UPDATE_CHANGED
1471 is true, then update the changed sbitmap to note those nodes whose
1472 solutions have changed as a result of collapsing. */
1475 find_and_collapse_graph_cycles (constraint_graph_t graph
, bool update_changed
)
1478 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1479 struct scc_info
*si
= init_scc_info ();
1481 for (i
= 0; i
!= size
; ++i
)
1482 if (!TEST_BIT (si
->visited
, i
) && get_varinfo (i
)->node
== i
)
1483 scc_visit (graph
, si
, i
);
1484 process_unification_queue (graph
, si
, update_changed
);
1488 /* Compute a topological ordering for GRAPH, and store the result in the
1489 topo_info structure TI. */
1492 compute_topo_order (constraint_graph_t graph
,
1493 struct topo_info
*ti
)
1496 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1498 for (i
= 0; i
!= size
; ++i
)
1499 if (!TEST_BIT (ti
->visited
, i
) && get_varinfo (i
)->node
== i
)
1500 topo_visit (graph
, ti
, i
);
1503 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1506 bitmap_other_than_zero_bit_set (bitmap b
)
1511 if (bitmap_empty_p (b
))
1513 EXECUTE_IF_SET_IN_BITMAP (b
, 1, i
, bi
)
1518 /* Perform offline variable substitution.
1520 This is a linear time way of identifying variables that must have
1521 equivalent points-to sets, including those caused by static cycles,
1522 and single entry subgraphs, in the constraint graph.
1524 The technique is described in "Off-line variable substitution for
1525 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1526 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1529 perform_var_substitution (constraint_graph_t graph
)
1531 struct topo_info
*ti
= init_topo_info ();
1533 /* Compute the topological ordering of the graph, then visit each
1534 node in topological order. */
1535 compute_topo_order (graph
, ti
);
1537 while (VEC_length (uint
, ti
->topo_order
) != 0)
1539 unsigned int i
= VEC_pop (uint
, ti
->topo_order
);
1541 varinfo_t vi
= get_varinfo (i
);
1542 bool okay_to_elim
= false;
1543 unsigned int root
= VEC_length (varinfo_t
, varmap
);
1544 VEC(constraint_edge_t
,gc
) *predvec
= graph
->preds
[i
];
1545 constraint_edge_t ce
;
1548 /* We can't eliminate things whose address is taken, or which is
1549 the target of a dereference. */
1550 if (vi
->address_taken
|| vi
->indirect_target
)
1553 /* See if all predecessors of I are ripe for elimination */
1554 for (pred
= 0; VEC_iterate (constraint_edge_t
, predvec
, pred
, ce
); pred
++)
1558 weight
= get_graph_weights (graph
, *ce
);
1560 /* We can't eliminate variables that have non-zero weighted
1561 edges between them. */
1562 if (bitmap_other_than_zero_bit_set (weight
))
1564 okay_to_elim
= false;
1567 w
= get_varinfo (ce
->dest
)->node
;
1569 /* We can't eliminate the node if one of the predecessors is
1570 part of a different strongly connected component. */
1574 okay_to_elim
= true;
1578 okay_to_elim
= false;
1582 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1583 then Solution(i) is a subset of Solution (w), where w is a
1584 predecessor in the graph.
1585 Corollary: If all predecessors of i have the same
1586 points-to set, then i has that same points-to set as
1587 those predecessors. */
1588 tmp
= BITMAP_ALLOC (NULL
);
1589 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1590 get_varinfo (w
)->solution
);
1591 if (!bitmap_empty_p (tmp
))
1593 okay_to_elim
= false;
1600 /* See if the root is different than the original node.
1601 If so, we've found an equivalence. */
1602 if (root
!= get_varinfo (i
)->node
&& okay_to_elim
)
1604 /* Found an equivalence */
1605 get_varinfo (i
)->node
= root
;
1606 collapse_nodes (graph
, root
, i
);
1607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1608 fprintf (dump_file
, "Collapsing %s into %s\n",
1609 get_varinfo (i
)->name
,
1610 get_varinfo (root
)->name
);
1611 stats
.collapsed_vars
++;
1615 free_topo_info (ti
);
1619 /* Solve the constraint graph GRAPH using our worklist solver.
1620 This is based on the PW* family of solvers from the "Efficient Field
1621 Sensitive Pointer Analysis for C" paper.
1622 It works by iterating over all the graph nodes, processing the complex
1623 constraints and propagating the copy constraints, until everything stops
1624 changed. This corresponds to steps 6-8 in the solving list given above. */
1627 solve_graph (constraint_graph_t graph
)
1629 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1632 changed_count
= size
;
1633 changed
= sbitmap_alloc (size
);
1634 sbitmap_ones (changed
);
1636 /* The already collapsed/unreachable nodes will never change, so we
1637 need to account for them in changed_count. */
1638 for (i
= 0; i
< size
; i
++)
1639 if (get_varinfo (i
)->node
!= i
)
1642 while (changed_count
> 0)
1645 struct topo_info
*ti
= init_topo_info ();
1648 bitmap_obstack_initialize (&iteration_obstack
);
1652 /* We already did cycle elimination once, when we did
1653 variable substitution, so we don't need it again for the
1655 if (stats
.iterations
> 1)
1656 find_and_collapse_graph_cycles (graph
, true);
1661 compute_topo_order (graph
, ti
);
1663 while (VEC_length (uint
, ti
->topo_order
) != 0)
1665 i
= VEC_pop (uint
, ti
->topo_order
);
1666 gcc_assert (get_varinfo (i
)->node
== i
);
1668 /* If the node has changed, we need to process the
1669 complex constraints and outgoing edges again. */
1670 if (TEST_BIT (changed
, i
))
1674 constraint_edge_t e
;
1676 VEC(constraint_t
,gc
) *complex = get_varinfo (i
)->complex;
1677 VEC(constraint_edge_t
,gc
) *succs
;
1679 RESET_BIT (changed
, i
);
1682 /* Process the complex constraints */
1683 solution
= get_varinfo (i
)->solution
;
1684 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
1685 do_complex_constraint (graph
, c
, solution
);
1687 /* Propagate solution to all successors. */
1688 succs
= graph
->succs
[i
];
1689 for (j
= 0; VEC_iterate (constraint_edge_t
, succs
, j
, e
); j
++)
1691 bitmap tmp
= get_varinfo (e
->dest
)->solution
;
1694 bitmap weights
= e
->weights
;
1697 gcc_assert (!bitmap_empty_p (weights
));
1698 EXECUTE_IF_SET_IN_BITMAP (weights
, 0, k
, bi
)
1699 flag
|= set_union_with_increment (tmp
, solution
, k
);
1703 get_varinfo (e
->dest
)->solution
= tmp
;
1704 if (!TEST_BIT (changed
, e
->dest
))
1706 SET_BIT (changed
, e
->dest
);
1713 free_topo_info (ti
);
1714 bitmap_obstack_release (&iteration_obstack
);
1717 sbitmap_free (changed
);
1721 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1723 /* Map from trees to variable ids. */
1724 static htab_t id_for_tree
;
1726 typedef struct tree_id
1732 /* Hash a tree id structure. */
1735 tree_id_hash (const void *p
)
1737 const tree_id_t ta
= (tree_id_t
) p
;
1738 return htab_hash_pointer (ta
->t
);
1741 /* Return true if the tree in P1 and the tree in P2 are the same. */
1744 tree_id_eq (const void *p1
, const void *p2
)
1746 const tree_id_t ta1
= (tree_id_t
) p1
;
1747 const tree_id_t ta2
= (tree_id_t
) p2
;
1748 return ta1
->t
== ta2
->t
;
1751 /* Insert ID as the variable id for tree T in the hashtable. */
1754 insert_id_for_tree (tree t
, int id
)
1757 struct tree_id finder
;
1761 slot
= htab_find_slot (id_for_tree
, &finder
, INSERT
);
1762 gcc_assert (*slot
== NULL
);
1763 new_pair
= xmalloc (sizeof (struct tree_id
));
1766 *slot
= (void *)new_pair
;
1769 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1770 exist in the hash table, return false, otherwise, return true and
1771 set *ID to the id we found. */
1774 lookup_id_for_tree (tree t
, unsigned int *id
)
1777 struct tree_id finder
;
1780 pair
= htab_find (id_for_tree
, &finder
);
1787 /* Return a printable name for DECL */
1790 alias_get_name (tree decl
)
1792 const char *res
= get_name (decl
);
1794 int num_printed
= 0;
1800 if (TREE_CODE (decl
) == SSA_NAME
)
1802 num_printed
= asprintf (&temp
, "%s_%u",
1803 alias_get_name (SSA_NAME_VAR (decl
)),
1804 SSA_NAME_VERSION (decl
));
1806 else if (DECL_P (decl
))
1808 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
1810 if (num_printed
> 0)
1812 res
= ggc_strdup (temp
);
1818 /* Find the variable id for tree T in the hashtable.
1819 If T doesn't exist in the hash table, create an entry for it. */
1822 get_id_for_tree (tree t
)
1825 struct tree_id finder
;
1828 pair
= htab_find (id_for_tree
, &finder
);
1830 return create_variable_info_for (t
, alias_get_name (t
));
1835 /* Get a constraint expression from an SSA_VAR_P node. */
1837 static struct constraint_expr
1838 get_constraint_exp_from_ssa_var (tree t
)
1840 struct constraint_expr cexpr
;
1842 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
1844 /* For parameters, get at the points-to set for the actual parm
1846 if (TREE_CODE (t
) == SSA_NAME
1847 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
1848 && default_def (SSA_NAME_VAR (t
)) == t
)
1849 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
1851 cexpr
.type
= SCALAR
;
1853 if (TREE_READONLY (t
))
1855 cexpr
.type
= ADDRESSOF
;
1856 cexpr
.var
= readonly_id
;
1859 cexpr
.var
= get_id_for_tree (t
);
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 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1945 static struct constraint_expr
1946 get_constraint_for_component_ref (tree t
)
1948 struct constraint_expr result
;
1949 HOST_WIDE_INT bitsize
;
1950 HOST_WIDE_INT bitpos
;
1952 enum machine_mode mode
;
1958 result
.type
= SCALAR
;
1961 /* Some people like to do cute things like take the address of
1964 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
1965 forzero
= TREE_OPERAND (forzero
, 0);
1967 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
1970 result
.var
= integer_id
;
1971 result
.type
= SCALAR
;
1975 t
= get_inner_reference (t
, &bitsize
, &bitpos
, &offset
, &mode
,
1976 &unsignedp
, &volatilep
, false);
1977 result
= get_constraint_for (t
);
1979 /* This can also happen due to weird offsetof type macros. */
1980 if (TREE_CODE (t
) != ADDR_EXPR
&& result
.type
== ADDRESSOF
)
1981 result
.type
= SCALAR
;
1983 /* If we know where this goes, then yay. Otherwise, booo. */
1985 if (offset
== NULL
&& bitsize
!= -1)
1987 result
.offset
= bitpos
;
1991 result
.var
= anything_id
;
1995 if (result
.type
== SCALAR
)
1997 /* In languages like C, you can access one past the end of an
1998 array. You aren't allowed to dereference it, so we can
1999 ignore this constraint. When we handle pointer subtraction,
2000 we may have to do something cute here. */
2002 if (result
.offset
< get_varinfo (result
.var
)->fullsize
)
2003 result
.var
= first_vi_for_offset (get_varinfo (result
.var
),
2006 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2007 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2016 /* Dereference the constraint expression CONS, and return the result.
2017 DEREF (ADDRESSOF) = SCALAR
2018 DEREF (SCALAR) = DEREF
2019 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2020 This is needed so that we can handle dereferencing DEREF constraints. */
2022 static struct constraint_expr
2023 do_deref (struct constraint_expr cons
)
2025 if (cons
.type
== SCALAR
)
2030 else if (cons
.type
== ADDRESSOF
)
2035 else if (cons
.type
== DEREF
)
2037 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "derefmp");
2038 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2039 process_constraint (new_constraint (tmplhs
, cons
));
2040 cons
.var
= tmplhs
.var
;
2047 /* Given a tree T, return the constraint expression for it. */
2049 static struct constraint_expr
2050 get_constraint_for (tree t
)
2052 struct constraint_expr temp
;
2054 /* x = integer is all glommed to a single variable, which doesn't
2055 point to anything by itself. That is, of course, unless it is an
2056 integer constant being treated as a pointer, in which case, we
2057 will return that this is really the addressof anything. This
2058 happens below, since it will fall into the default case. The only
2059 case we know something about an integer treated like a pointer is
2060 when it is the NULL pointer, and then we just say it points to
2062 if (TREE_CODE (t
) == INTEGER_CST
2063 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2065 temp
.var
= integer_id
;
2070 else if (TREE_CODE (t
) == INTEGER_CST
2071 && integer_zerop (t
))
2073 temp
.var
= nothing_id
;
2074 temp
.type
= ADDRESSOF
;
2079 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2081 case tcc_expression
:
2083 switch (TREE_CODE (t
))
2087 temp
= get_constraint_for (TREE_OPERAND (t
, 0));
2088 if (temp
.type
== DEREF
)
2091 temp
.type
= ADDRESSOF
;
2097 /* XXX: In interprocedural mode, if we didn't have the
2098 body, we would need to do *each pointer argument =
2100 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2102 tree heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2103 temp
.var
= create_variable_info_for (heapvar
,
2104 alias_get_name (heapvar
));
2106 get_varinfo (temp
.var
)->is_artificial_var
= 1;
2107 temp
.type
= ADDRESSOF
;
2114 temp
.type
= ADDRESSOF
;
2115 temp
.var
= anything_id
;
2123 switch (TREE_CODE (t
))
2127 temp
= get_constraint_for (TREE_OPERAND (t
, 0));
2128 temp
= do_deref (temp
);
2133 temp
= get_constraint_for_component_ref (t
);
2137 temp
.type
= ADDRESSOF
;
2138 temp
.var
= anything_id
;
2146 switch (TREE_CODE (t
))
2150 case NON_LVALUE_EXPR
:
2152 tree op
= TREE_OPERAND (t
, 0);
2154 /* Cast from non-pointer to pointers are bad news for us.
2155 Anything else, we see through */
2156 if (!(POINTER_TYPE_P (TREE_TYPE (t
)) &&
2157 ! POINTER_TYPE_P (TREE_TYPE (op
))))
2158 return get_constraint_for (op
);
2162 temp
.type
= ADDRESSOF
;
2163 temp
.var
= anything_id
;
2169 case tcc_exceptional
:
2171 switch (TREE_CODE (t
))
2174 return get_constraint_for (PHI_RESULT (t
));
2176 return get_constraint_exp_from_ssa_var (t
);
2179 temp
.type
= ADDRESSOF
;
2180 temp
.var
= anything_id
;
2186 case tcc_declaration
:
2187 return get_constraint_exp_from_ssa_var (t
);
2190 temp
.type
= ADDRESSOF
;
2191 temp
.var
= anything_id
;
2199 /* Handle the structure copy case where we have a simple structure copy
2200 between LHS and RHS that is of SIZE (in bits)
2202 For each field of the lhs variable (lhsfield)
2203 For each field of the rhs variable at lhsfield.offset (rhsfield)
2204 add the constraint lhsfield = rhsfield
2208 do_simple_structure_copy (const struct constraint_expr lhs
,
2209 const struct constraint_expr rhs
,
2210 const unsigned HOST_WIDE_INT size
)
2212 varinfo_t p
= get_varinfo (lhs
.var
);
2213 unsigned HOST_WIDE_INT pstart
,last
;
2216 last
= p
->offset
+ size
;
2217 for (; p
&& p
->offset
< last
; p
= p
->next
)
2220 struct constraint_expr templhs
= lhs
;
2221 struct constraint_expr temprhs
= rhs
;
2222 unsigned HOST_WIDE_INT fieldoffset
;
2224 templhs
.var
= p
->id
;
2225 q
= get_varinfo (temprhs
.var
);
2226 fieldoffset
= p
->offset
- pstart
;
2227 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2228 temprhs
.var
= q
->id
;
2229 process_constraint (new_constraint (templhs
, temprhs
));
2234 /* Handle the structure copy case where we have a structure copy between a
2235 aggregate on the LHS and a dereference of a pointer on the RHS
2236 that is of SIZE (in bits)
2238 For each field of the lhs variable (lhsfield)
2239 rhs.offset = lhsfield->offset
2240 add the constraint lhsfield = rhs
2244 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2245 const struct constraint_expr rhs
,
2246 const unsigned HOST_WIDE_INT size
)
2248 varinfo_t p
= get_varinfo (lhs
.var
);
2249 unsigned HOST_WIDE_INT pstart
,last
;
2251 last
= p
->offset
+ size
;
2253 for (; p
&& p
->offset
< last
; p
= p
->next
)
2256 struct constraint_expr templhs
= lhs
;
2257 struct constraint_expr temprhs
= rhs
;
2258 unsigned HOST_WIDE_INT fieldoffset
;
2261 if (templhs
.type
== SCALAR
)
2262 templhs
.var
= p
->id
;
2264 templhs
.offset
= p
->offset
;
2266 q
= get_varinfo (temprhs
.var
);
2267 fieldoffset
= p
->offset
- pstart
;
2268 temprhs
.offset
+= fieldoffset
;
2269 process_constraint (new_constraint (templhs
, temprhs
));
2273 /* Handle the structure copy case where we have a structure copy
2274 between a aggregate on the RHS and a dereference of a pointer on
2275 the LHS that is of SIZE (in bits)
2277 For each field of the rhs variable (rhsfield)
2278 lhs.offset = rhsfield->offset
2279 add the constraint lhs = rhsfield
2283 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2284 const struct constraint_expr rhs
,
2285 const unsigned HOST_WIDE_INT size
)
2287 varinfo_t p
= get_varinfo (rhs
.var
);
2288 unsigned HOST_WIDE_INT pstart
,last
;
2290 last
= p
->offset
+ size
;
2292 for (; p
&& p
->offset
< last
; p
= p
->next
)
2295 struct constraint_expr templhs
= lhs
;
2296 struct constraint_expr temprhs
= rhs
;
2297 unsigned HOST_WIDE_INT fieldoffset
;
2300 if (temprhs
.type
== SCALAR
)
2301 temprhs
.var
= p
->id
;
2303 temprhs
.offset
= p
->offset
;
2305 q
= get_varinfo (templhs
.var
);
2306 fieldoffset
= p
->offset
- pstart
;
2307 templhs
.offset
+= fieldoffset
;
2308 process_constraint (new_constraint (templhs
, temprhs
));
2313 /* Handle aggregate copies by expanding into copies of the respective
2314 fields of the structures. */
2317 do_structure_copy (tree lhsop
, tree rhsop
)
2319 struct constraint_expr lhs
, rhs
, tmp
;
2321 unsigned HOST_WIDE_INT lhssize
;
2322 unsigned HOST_WIDE_INT rhssize
;
2324 lhssize
= TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (lhsop
)));
2325 rhssize
= TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (rhsop
)));
2326 lhs
= get_constraint_for (lhsop
);
2327 rhs
= get_constraint_for (rhsop
);
2329 /* If we have special var = x, swap it around. */
2330 if (lhs
.var
<= integer_id
&& rhs
.var
> integer_id
)
2337 /* If the RHS is a special var, set all the LHS fields to that
2339 if (rhs
.var
<= integer_id
)
2341 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2343 struct constraint_expr templhs
= lhs
;
2344 struct constraint_expr temprhs
= rhs
;
2345 if (templhs
.type
== SCALAR
)
2346 templhs
.var
= p
->id
;
2348 templhs
.offset
+= p
->offset
;
2349 process_constraint (new_constraint (templhs
, temprhs
));
2354 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
2355 do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2356 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2357 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2358 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
2359 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2362 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
2363 tree pointertype
= TREE_TYPE (rhsdecl
);
2364 tree pointedtotype
= TREE_TYPE (pointertype
);
2366 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
2367 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
2368 lhs
= get_constraint_for (tmpvar
);
2369 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2371 lhs
= get_constraint_for (lhsop
);
2372 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2378 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2382 ref_contains_indirect_ref (tree ref
)
2384 while (handled_component_p (ref
))
2386 if (TREE_CODE (ref
) == INDIRECT_REF
)
2388 ref
= TREE_OPERAND (ref
, 0);
2394 /* Tree walker that is the heart of the aliasing infrastructure.
2395 TP is a pointer to the current tree.
2396 WALK_SUBTREES specifies whether to continue traversing subtrees or
2398 Returns NULL_TREE when we should stop.
2400 This function is the main part of the constraint builder. It
2401 walks the trees, calling the appropriate building functions
2402 to process various statements. */
2405 find_func_aliases (tree t
)
2407 struct constraint_expr lhs
, rhs
;
2408 switch (TREE_CODE (t
))
2414 /* Only care about pointers and structures containing
2416 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t
)))
2417 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))))
2419 lhs
= get_constraint_for (PHI_RESULT (t
));
2420 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
2422 rhs
= get_constraint_for (PHI_ARG_DEF (t
, i
));
2423 process_constraint (new_constraint (lhs
, rhs
));
2431 tree lhsop
= TREE_OPERAND (t
, 0);
2432 tree rhsop
= TREE_OPERAND (t
, 1);
2435 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
2436 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop
)))
2438 do_structure_copy (lhsop
, rhsop
);
2442 /* Only care about operations with pointers, structures
2443 containing pointers, dereferences, and call
2445 if (POINTER_TYPE_P (TREE_TYPE (lhsop
))
2446 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
2447 || ref_contains_indirect_ref (lhsop
)
2448 || TREE_CODE (rhsop
) == CALL_EXPR
)
2450 lhs
= get_constraint_for (lhsop
);
2451 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
2453 /* RHS that consist of unary operations,
2454 exceptional types, or bare decls/constants, get
2455 handled directly by get_constraint_for. */
2457 case tcc_declaration
:
2459 case tcc_exceptional
:
2460 case tcc_expression
:
2463 rhs
= get_constraint_for (rhsop
);
2464 process_constraint (new_constraint (lhs
, rhs
));
2468 /* Otherwise, walk each operand. */
2470 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
2472 tree op
= TREE_OPERAND (rhsop
, i
);
2473 rhs
= get_constraint_for (op
);
2474 process_constraint (new_constraint (lhs
, rhs
));
2488 /* Find the first varinfo in the same variable as START that overlaps with
2490 Effectively, walk the chain of fields for the variable START to find the
2491 first field that overlaps with OFFSET.
2492 Abort if we can't find one. */
2495 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
2497 varinfo_t curr
= start
;
2500 /* We may not find a variable in the field list with the actual
2501 offset when when we have glommed a structure to a variable.
2502 In that case, however, offset should still be within the size
2504 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
2513 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2517 insert_into_field_list (varinfo_t base
, varinfo_t field
)
2519 varinfo_t prev
= base
;
2520 varinfo_t curr
= base
->next
;
2531 if (field
->offset
<= curr
->offset
)
2536 field
->next
= prev
->next
;
2541 /* qsort comparison function for two fieldoff's PA and PB */
2544 fieldoff_compare (const void *pa
, const void *pb
)
2546 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
2547 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
2548 HOST_WIDE_INT foasize
, fobsize
;
2550 if (foa
->offset
!= fob
->offset
)
2551 return foa
->offset
- fob
->offset
;
2553 foasize
= TREE_INT_CST_LOW (DECL_SIZE (foa
->field
));
2554 fobsize
= TREE_INT_CST_LOW (DECL_SIZE (fob
->field
));
2555 return foasize
- fobsize
;
2558 /* Sort a fieldstack according to the field offset and sizes. */
2559 void sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
2561 qsort (VEC_address (fieldoff_s
, fieldstack
),
2562 VEC_length (fieldoff_s
, fieldstack
),
2563 sizeof (fieldoff_s
),
2567 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2568 of TYPE onto fieldstack, recording their offsets along the way.
2569 OFFSET is used to keep track of the offset in this entire structure, rather
2570 than just the immediately containing structure. Returns the number
2572 HAS_UNION is set to true if we find a union type as a field of
2576 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
2577 HOST_WIDE_INT offset
, bool *has_union
)
2582 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
2583 if (TREE_CODE (field
) == FIELD_DECL
)
2588 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
2589 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
2592 if (!var_can_have_subvars (field
))
2594 else if (!(push_fields_onto_fieldstack
2595 (TREE_TYPE (field
), fieldstack
,
2596 offset
+ bitpos_of_field (field
), has_union
))
2597 && DECL_SIZE (field
)
2598 && !integer_zerop (DECL_SIZE (field
)))
2599 /* Empty structures may have actual size, like in C++. So
2600 see if we didn't push any subfields and the size is
2601 nonzero, push the field onto the stack */
2608 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
2609 pair
->field
= field
;
2610 pair
->offset
= offset
+ bitpos_of_field (field
);
2619 make_constraint_to_anything (varinfo_t vi
)
2621 struct constraint_expr lhs
, rhs
;
2627 rhs
.var
= anything_id
;
2629 rhs
.type
= ADDRESSOF
;
2630 process_constraint (new_constraint (lhs
, rhs
));
2633 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2634 This will also create any varinfo structures necessary for fields
2638 create_variable_info_for (tree decl
, const char *name
)
2640 unsigned int index
= VEC_length (varinfo_t
, varmap
);
2642 tree
decltype = TREE_TYPE (decl
);
2643 bool notokay
= false;
2646 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
2647 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
2650 hasunion
= TREE_CODE (decltype) == UNION_TYPE
|| TREE_CODE (decltype) == QUAL_UNION_TYPE
;
2651 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
2653 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
2656 VEC_free (fieldoff_s
, heap
, fieldstack
);
2661 /* If this variable already has subvars, just create the variables for the
2662 subvars and we are done.
2663 NOTE: This assumes things haven't generated uses of previously
2664 unused structure fields. */
2665 if (use_field_sensitive
2667 && var_can_have_subvars (decl
)
2669 && (svars
= get_subvars_for_var (decl
)))
2672 varinfo_t base
= NULL
;
2673 unsigned int firstindex
= index
;
2675 for (sv
= svars
; sv
; sv
= sv
->next
)
2677 /* For debugging purposes, this will print the names of the
2678 fields as "<var>.<offset>.<size>"
2679 This is only for debugging purposes. */
2680 #define PRINT_LONG_NAMES
2681 #ifdef PRINT_LONG_NAMES
2683 const char *newname
;
2685 asprintf (&tempname
,
2686 "%s." HOST_WIDE_INT_PRINT_DEC
"." HOST_WIDE_INT_PRINT_DEC
,
2687 alias_get_name (decl
), sv
->offset
, sv
->size
);
2688 newname
= ggc_strdup (tempname
);
2690 vi
= new_var_info (sv
->var
, index
, newname
, index
);
2692 vi
= new_var_info (sv
->var
, index
, alias_get_name (sv
->var
), index
);
2695 vi
->fullsize
= TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2696 vi
->size
= sv
->size
;
2697 vi
->offset
= sv
->offset
;
2701 insert_id_for_tree (decl
, index
);
2705 insert_into_field_list (base
, vi
);
2707 insert_id_for_tree (sv
->var
, index
);
2708 VEC_safe_push (varinfo_t
, gc
, varmap
, vi
);
2710 make_constraint_to_anything (vi
);
2718 /* If the variable doesn't have subvars, we may end up needing to
2719 sort the field list and create fake variables for all the
2721 vi
= new_var_info (decl
, index
, name
, index
);
2724 vi
->has_union
= hasunion
;
2725 if (!TYPE_SIZE (decltype)
2726 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
2727 || TREE_CODE (decltype) == ARRAY_TYPE
2728 || TREE_CODE (decltype) == UNION_TYPE
2729 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
2731 vi
->is_unknown_size_var
= true;
2737 vi
->fullsize
= TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2738 vi
->size
= vi
->fullsize
;
2741 insert_id_for_tree (vi
->decl
, index
);
2742 VEC_safe_push (varinfo_t
, gc
, varmap
, vi
);
2744 make_constraint_to_anything (vi
);
2747 if (use_field_sensitive
2749 && !vi
->is_unknown_size_var
2750 && var_can_have_subvars (decl
))
2752 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
2753 fieldoff_s
*fo
= NULL
;
2757 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
2759 if (!DECL_SIZE (fo
->field
)
2760 || TREE_CODE (DECL_SIZE (fo
->field
)) != INTEGER_CST
2761 || TREE_CODE (TREE_TYPE (fo
->field
)) == ARRAY_TYPE
2769 /* We can't sort them if we have a field with a variable sized type,
2770 which will make notokay = true. In that case, we are going to return
2771 without creating varinfos for the fields anyway, so sorting them is a
2774 sort_fieldstack (fieldstack
);
2776 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
2777 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
2779 if (fo
== NULL
|| notokay
)
2781 vi
->is_unknown_size_var
= 1;
2784 VEC_free (fieldoff_s
, heap
, fieldstack
);
2789 gcc_assert (bitpos_of_field (field
) == 0);
2790 vi
->size
= TREE_INT_CST_LOW (DECL_SIZE (field
));
2791 for (i
= 1; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
2794 const char *newname
;
2798 newindex
= VEC_length (varinfo_t
, varmap
);
2799 asprintf (&tempname
, "%s.%s", vi
->name
, alias_get_name (field
));
2800 newname
= ggc_strdup (tempname
);
2802 newvi
= new_var_info (decl
, newindex
, newname
, newindex
);
2803 newvi
->offset
= fo
->offset
;
2804 newvi
->size
= TREE_INT_CST_LOW (DECL_SIZE (field
));
2805 newvi
->fullsize
= vi
->fullsize
;
2806 insert_into_field_list (vi
, newvi
);
2807 VEC_safe_push (varinfo_t
, gc
, varmap
, newvi
);
2809 make_constraint_to_anything (newvi
);
2813 VEC_free (fieldoff_s
, heap
, fieldstack
);
2818 /* Print out the points-to solution for VAR to FILE. */
2821 dump_solution_for_var (FILE *file
, unsigned int var
)
2823 varinfo_t vi
= get_varinfo (var
);
2827 fprintf (file
, "%s = { ", vi
->name
);
2828 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi
->node
)->solution
, 0, i
, bi
)
2830 fprintf (file
, "%s ", get_varinfo (i
)->name
);
2832 fprintf (file
, "}\n");
2835 /* Print the points-to solution for VAR to stdout. */
2838 debug_solution_for_var (unsigned int var
)
2840 dump_solution_for_var (stdout
, var
);
2844 /* Create varinfo structures for all of the variables in the
2845 function for intraprocedural mode. */
2848 intra_create_variable_infos (void)
2852 /* For each incoming argument arg, ARG = &ANYTHING */
2853 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
2855 struct constraint_expr lhs
;
2856 struct constraint_expr rhs
;
2861 lhs
.var
= create_variable_info_for (t
, alias_get_name (t
));
2863 get_varinfo (lhs
.var
)->is_artificial_var
= true;
2864 rhs
.var
= anything_id
;
2865 rhs
.type
= ADDRESSOF
;
2868 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2870 struct constraint_expr temp
= lhs
;
2872 process_constraint (new_constraint (temp
, rhs
));
2878 /* Set bits in INTO corresponding to the variable uids in solution set
2882 set_uids_in_ptset (bitmap into
, bitmap from
)
2887 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
2889 varinfo_t vi
= get_varinfo (i
);
2891 /* Variables containing unions may need to be converted to their
2892 SFT's, because SFT's can have unions and we cannot. */
2893 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
2895 subvar_t svars
= get_subvars_for_var (vi
->decl
);
2897 for (sv
= svars
; sv
; sv
= sv
->next
)
2898 bitmap_set_bit (into
, var_ann (sv
->var
)->uid
);
2900 /* We may end up with labels in the points-to set because people
2901 take their address, and they are _DECL's. */
2902 else if (TREE_CODE (vi
->decl
) == VAR_DECL
2903 || TREE_CODE (vi
->decl
) == PARM_DECL
)
2904 bitmap_set_bit (into
, var_ann (vi
->decl
)->uid
);
2909 static int have_alias_info
= false;
2911 /* Given a pointer variable P, fill in its points-to set, or return
2912 false if we can't. */
2915 find_what_p_points_to (tree p
)
2917 unsigned int id
= 0;
2918 if (!have_alias_info
)
2920 if (lookup_id_for_tree (p
, &id
))
2922 varinfo_t vi
= get_varinfo (id
);
2924 if (vi
->is_artificial_var
)
2927 /* See if this is a field or a structure */
2928 if (vi
->size
!= vi
->fullsize
)
2930 if (!var_can_have_subvars (vi
->decl
)
2931 || get_subvars_for_var (vi
->decl
) == NULL
)
2933 /* Nothing currently asks about structure fields directly, but when
2934 they do, we need code here to hand back the points-to set. */
2938 struct ptr_info_def
*pi
= get_ptr_info (p
);
2942 /* This variable may have been collapsed, let's get the real
2944 vi
= get_varinfo (vi
->node
);
2946 /* Make sure there aren't any artificial vars in the points to set.
2947 XXX: Note that we need to translate our heap variables to
2949 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
2951 if (get_varinfo (i
)->is_artificial_var
)
2954 pi
->pt_anything
= false;
2956 pi
->pt_vars
= BITMAP_GGC_ALLOC ();
2957 set_uids_in_ptset (pi
->pt_vars
, vi
->solution
);
2965 /* Initialize things necessary to perform PTA */
2968 init_alias_vars (void)
2970 bitmap_obstack_initialize (&ptabitmap_obstack
);
2974 /* Dump points-to information to OUTFILE. */
2977 dump_sa_points_to_info (FILE *outfile
)
2981 fprintf (outfile
, "\nPoints-to information\n\n");
2983 if (dump_flags
& TDF_STATS
)
2985 fprintf (outfile
, "Stats:\n");
2986 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
2987 fprintf (outfile
, "Statically unified vars: %d\n",
2988 stats
.unified_vars_static
);
2989 fprintf (outfile
, "Collapsed vars: %d\n", stats
.collapsed_vars
);
2990 fprintf (outfile
, "Dynamically unified vars: %d\n",
2991 stats
.unified_vars_dynamic
);
2992 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
2995 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
2996 dump_solution_for_var (outfile
, i
);
3000 /* Debug points-to information to stderr. */
3003 debug_sa_points_to_info (void)
3005 dump_sa_points_to_info (stderr
);
3009 /* Initialize the always-existing constraint variables for NULL
3010 ANYTHING, READONLY, and INTEGER */
3013 init_base_vars (void)
3015 struct constraint_expr lhs
, rhs
;
3017 /* Create the NULL variable, used to represent that a variable points
3019 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
3020 var_nothing
= new_var_info (nothing_tree
, 0, "NULL", 0);
3021 insert_id_for_tree (nothing_tree
, 0);
3022 var_nothing
->is_artificial_var
= 1;
3023 var_nothing
->offset
= 0;
3024 var_nothing
->size
= ~0;
3025 var_nothing
->fullsize
= ~0;
3027 VEC_safe_push (varinfo_t
, gc
, varmap
, var_nothing
);
3029 /* Create the ANYTHING variable, used to represent that a variable
3030 points to some unknown piece of memory. */
3031 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
3032 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING", 1);
3033 insert_id_for_tree (anything_tree
, 1);
3034 var_anything
->is_artificial_var
= 1;
3035 var_anything
->size
= ~0;
3036 var_anything
->offset
= 0;
3037 var_anything
->next
= NULL
;
3038 var_anything
->fullsize
= ~0;
3041 /* Anything points to anything. This makes deref constraints just
3042 work in the presence of linked list and other p = *p type loops,
3043 by saying that *ANYTHING = ANYTHING. */
3044 VEC_safe_push (varinfo_t
, gc
, varmap
, var_anything
);
3046 lhs
.var
= anything_id
;
3048 rhs
.type
= ADDRESSOF
;
3049 rhs
.var
= anything_id
;
3051 var_anything
->address_taken
= true;
3052 process_constraint (new_constraint (lhs
, rhs
));
3055 /* Create the READONLY variable, used to represent that a variable
3056 points to readonly memory. */
3057 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
3058 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY", 2);
3059 var_readonly
->is_artificial_var
= 1;
3060 var_readonly
->offset
= 0;
3061 var_readonly
->size
= ~0;
3062 var_readonly
->fullsize
= ~0;
3063 var_readonly
->next
= NULL
;
3064 insert_id_for_tree (readonly_tree
, 2);
3066 VEC_safe_push (varinfo_t
, gc
, varmap
, var_readonly
);
3068 /* readonly memory points to anything, in order to make deref
3069 easier. In reality, it points to anything the particular
3070 readonly variable can point to, but we don't track this
3073 lhs
.var
= readonly_id
;
3075 rhs
.type
= ADDRESSOF
;
3076 rhs
.var
= anything_id
;
3078 var_readonly
->address_taken
= true;
3080 process_constraint (new_constraint (lhs
, rhs
));
3082 /* Create the INTEGER variable, used to represent that a variable points
3084 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
3085 var_integer
= new_var_info (integer_tree
, 3, "INTEGER", 3);
3086 insert_id_for_tree (integer_tree
, 3);
3087 var_integer
->is_artificial_var
= 1;
3088 var_integer
->size
= ~0;
3089 var_integer
->fullsize
= ~0;
3090 var_integer
->offset
= 0;
3091 var_integer
->next
= NULL
;
3093 VEC_safe_push (varinfo_t
, gc
, varmap
, var_integer
);
3097 /* Create points-to sets for the current function. See the comments
3098 at the start of the file for an algorithmic overview. */
3101 create_alias_vars (void)
3108 constraint_pool
= create_alloc_pool ("Constraint pool",
3109 sizeof (struct constraint
), 30);
3110 variable_info_pool
= create_alloc_pool ("Variable info pool",
3111 sizeof (struct variable_info
), 30);
3112 constraint_edge_pool
= create_alloc_pool ("Constraint edges",
3113 sizeof (struct constraint_edge
), 30);
3115 constraints
= VEC_alloc (constraint_t
, gc
, 8);
3116 varmap
= VEC_alloc (varinfo_t
, gc
, 8);
3117 id_for_tree
= htab_create (10, tree_id_hash
, tree_id_eq
, free
);
3118 memset (&stats
, 0, sizeof (stats
));
3122 intra_create_variable_infos ();
3124 /* Now walk all statements and derive aliases. */
3127 block_stmt_iterator bsi
;
3130 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
3131 if (is_gimple_reg (PHI_RESULT (phi
)))
3132 find_func_aliases (phi
);
3134 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3135 find_func_aliases (bsi_stmt (bsi
));
3138 build_constraint_graph ();
3142 fprintf (dump_file
, "Constraints:\n");
3143 dump_constraints (dump_file
);
3147 fprintf (dump_file
, "Collapsing static cycles and doing variable substitution:\n");
3149 find_and_collapse_graph_cycles (graph
, false);
3150 perform_var_substitution (graph
);
3153 fprintf (dump_file
, "Solving graph:\n");
3155 solve_graph (graph
);
3158 dump_sa_points_to_info (dump_file
);
3160 have_alias_info
= true;
3163 struct tree_opt_pass pass_build_pta
=
3167 create_alias_vars
, /* execute */
3170 0, /* static_pass_number */
3171 TV_TREE_PTA
, /* tv_id */
3172 PROP_cfg
, /* properties_required */
3173 PROP_pta
, /* properties_provided */
3174 0, /* properties_destroyed */
3175 0, /* todo_flags_start */
3176 0, /* todo_flags_finish */
3181 /* Delete created points-to sets. */
3184 delete_alias_vars (void)
3186 htab_delete (id_for_tree
);
3187 free_alloc_pool (variable_info_pool
);
3188 free_alloc_pool (constraint_pool
);
3189 free_alloc_pool (constraint_edge_pool
);
3190 bitmap_obstack_release (&ptabitmap_obstack
);
3191 have_alias_info
= false;
3194 struct tree_opt_pass pass_del_pta
=
3198 delete_alias_vars
, /* execute */
3201 0, /* static_pass_number */
3202 TV_TREE_PTA
, /* tv_id */
3203 PROP_pta
, /* properties_required */
3204 0, /* properties_provided */
3205 PROP_pta
, /* properties_destroyed */
3206 0, /* todo_flags_start */
3207 0, /* todo_flags_finish */