1 /* Tree based points-to analysis
2 Copyright (C) 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
43 #include "tree-gimple.h"
47 #include "tree-pass.h"
49 #include "alloc-pool.h"
50 #include "splay-tree.h"
52 #include "tree-ssa-structalias.h"
55 /* The idea behind this analyzer is to generate set constraints from the
56 program, then solve the resulting constraints in order to generate the
59 Set constraints are a way of modeling program analysis problems that
60 involve sets. They consist of an inclusion constraint language,
61 describing the variables (each variable is a set) and operations that
62 are involved on the variables, and a set of rules that derive facts
63 from these operations. To solve a system of set constraints, you derive
64 all possible facts under the rules, which gives you the correct sets
67 See "Efficient Field-sensitive pointer analysis for C" by "David
68 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
69 http://citeseer.ist.psu.edu/pearce04efficient.html
71 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
72 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
73 http://citeseer.ist.psu.edu/heintze01ultrafast.html
75 There are three types of constraint expressions, DEREF, ADDRESSOF, and
76 SCALAR. Each constraint expression consists of a constraint type,
77 a variable, and an offset.
79 SCALAR is a constraint expression type used to represent x, whether
80 it appears on the LHS or the RHS of a statement.
81 DEREF is a constraint expression type used to represent *x, whether
82 it appears on the LHS or the RHS of a statement.
83 ADDRESSOF is a constraint expression used to represent &x, whether
84 it appears on the LHS or the RHS of a statement.
86 Each pointer variable in the program is assigned an integer id, and
87 each field of a structure variable is assigned an integer id as well.
89 Structure variables are linked to their list of fields through a "next
90 field" in each variable that points to the next field in offset
92 Each variable for a structure field has
94 1. "size", that tells the size in bits of that field.
95 2. "fullsize, that tells the size in bits of the entire structure.
96 3. "offset", that tells the offset in bits from the beginning of the
97 structure to this field.
109 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
110 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
111 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
114 In order to solve the system of set constraints, the following is
117 1. Each constraint variable x has a solution set associated with it,
120 2. Constraints are separated into direct, copy, and complex.
121 Direct constraints are ADDRESSOF constraints that require no extra
122 processing, such as P = &Q
123 Copy constraints are those of the form P = Q.
124 Complex constraints are all the constraints involving dereferences.
126 3. All direct constraints of the form P = &Q are processed, such
127 that Q is added to Sol(P)
129 4. All complex constraints for a given constraint variable are stored in a
130 linked list attached to that variable's node.
132 5. A directed graph is built out of the copy constraints. Each
133 constraint variable is a node in the graph, and an edge from
134 Q to P is added for each copy constraint of the form P = Q
136 6. The graph is then walked, and solution sets are
137 propagated along the copy edges, such that an edge from Q to P
138 causes Sol(P) <- Sol(P) union Sol(Q).
140 7. As we visit each node, all complex constraints associated with
141 that node are processed by adding appropriate copy edges to the graph, or the
142 appropriate variables to the solution set.
144 8. The process of walking the graph is iterated until no solution
147 Prior to walking the graph in steps 6 and 7, We perform static
148 cycle elimination on the constraint graph, as well
149 as off-line variable substitution.
151 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
152 on and turned into anything), but isn't. You can just see what offset
153 inside the pointed-to struct it's going to access.
155 TODO: Constant bounded arrays can be handled as if they were structs of the
156 same number of elements.
158 TODO: Modeling heap and incoming pointers becomes much better if we
159 add fields to them as we discover them, which we could do.
161 TODO: We could handle unions, but to be honest, it's probably not
162 worth the pain or slowdown. */
164 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map
)))
165 htab_t heapvar_for_stmt
;
166 static bool use_field_sensitive
= true;
167 static int in_ipa_mode
= 0;
168 static bitmap_obstack predbitmap_obstack
;
169 static bitmap_obstack ptabitmap_obstack
;
170 static bitmap_obstack iteration_obstack
;
172 static unsigned int create_variable_info_for (tree
, const char *);
173 static void build_constraint_graph (void);
175 DEF_VEC_P(constraint_t
);
176 DEF_VEC_ALLOC_P(constraint_t
,heap
);
178 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
180 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
182 static struct constraint_stats
184 unsigned int total_vars
;
185 unsigned int collapsed_vars
;
186 unsigned int unified_vars_static
;
187 unsigned int unified_vars_dynamic
;
188 unsigned int iterations
;
189 unsigned int num_edges
;
194 /* ID of this variable */
197 /* Name of this variable */
200 /* Tree that this variable is associated with. */
203 /* Offset of this variable, in bits, from the base variable */
204 unsigned HOST_WIDE_INT offset
;
206 /* Size of the variable, in bits. */
207 unsigned HOST_WIDE_INT size
;
209 /* Full size of the base variable, in bits. */
210 unsigned HOST_WIDE_INT fullsize
;
212 /* A link to the variable for the next field in this structure. */
213 struct variable_info
*next
;
215 /* Node in the graph that represents the constraints and points-to
216 solution for the variable. */
219 /* True if the address of this variable is taken. Needed for
220 variable substitution. */
221 unsigned int address_taken
:1;
223 /* True if this variable is the target of a dereference. Needed for
224 variable substitution. */
225 unsigned int indirect_target
:1;
227 /* True if this is a variable created by the constraint analysis, such as
228 heap variables and constraints we had to break up. */
229 unsigned int is_artificial_var
:1;
231 /* True if this is a special variable whose solution set should not be
233 unsigned int is_special_var
:1;
235 /* True for variables whose size is not known or variable. */
236 unsigned int is_unknown_size_var
:1;
238 /* True for variables that have unions somewhere in them. */
239 unsigned int has_union
:1;
241 /* True if this is a heap variable. */
242 unsigned int is_heap_var
:1;
244 /* Points-to set for this variable. */
247 /* Variable ids represented by this node. */
250 /* Vector of complex constraints for this node. Complex
251 constraints are those involving dereferences. */
252 VEC(constraint_t
,heap
) *complex;
254 /* Variable id this was collapsed to due to type unsafety.
255 This should be unused completely after build_constraint_graph, or
256 something is broken. */
257 struct variable_info
*collapsed_to
;
259 typedef struct variable_info
*varinfo_t
;
261 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
263 /* Pool of variable info structures. */
264 static alloc_pool variable_info_pool
;
266 DEF_VEC_P(varinfo_t
);
268 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
270 /* Table of variable info structures for constraint variables. Indexed directly
271 by variable info id. */
272 static VEC(varinfo_t
,heap
) *varmap
;
274 /* Return the varmap element N */
276 static inline varinfo_t
277 get_varinfo (unsigned int n
)
279 return VEC_index(varinfo_t
, varmap
, n
);
282 /* Return the varmap element N, following the collapsed_to link. */
284 static inline varinfo_t
285 get_varinfo_fc (unsigned int n
)
287 varinfo_t v
= VEC_index(varinfo_t
, varmap
, n
);
290 return v
->collapsed_to
;
294 /* Variable that represents the unknown pointer. */
295 static varinfo_t var_anything
;
296 static tree anything_tree
;
297 static unsigned int anything_id
;
299 /* Variable that represents the NULL pointer. */
300 static varinfo_t var_nothing
;
301 static tree nothing_tree
;
302 static unsigned int nothing_id
;
304 /* Variable that represents read only memory. */
305 static varinfo_t var_readonly
;
306 static tree readonly_tree
;
307 static unsigned int readonly_id
;
309 /* Variable that represents integers. This is used for when people do things
311 static varinfo_t var_integer
;
312 static tree integer_tree
;
313 static unsigned int integer_id
;
316 /* Lookup a heap var for FROM, and return it if we find one. */
319 heapvar_lookup (tree from
)
321 struct tree_map
*h
, in
;
324 h
= htab_find_with_hash (heapvar_for_stmt
, &in
, htab_hash_pointer (from
));
330 /* Insert a mapping FROM->TO in the heap var for statement
334 heapvar_insert (tree from
, tree to
)
339 h
= ggc_alloc (sizeof (struct tree_map
));
340 h
->hash
= htab_hash_pointer (from
);
343 loc
= htab_find_slot_with_hash (heapvar_for_stmt
, h
, h
->hash
, INSERT
);
344 *(struct tree_map
**) loc
= h
;
347 /* Return a new variable info structure consisting for a variable
348 named NAME, and using constraint graph node NODE. */
351 new_var_info (tree t
, unsigned int id
, const char *name
, unsigned int node
)
353 varinfo_t ret
= pool_alloc (variable_info_pool
);
359 ret
->address_taken
= false;
360 ret
->indirect_target
= false;
361 ret
->is_artificial_var
= false;
362 ret
->is_heap_var
= false;
363 ret
->is_special_var
= false;
364 ret
->is_unknown_size_var
= false;
365 ret
->has_union
= false;
366 ret
->solution
= BITMAP_ALLOC (&ptabitmap_obstack
);
367 ret
->variables
= BITMAP_ALLOC (&ptabitmap_obstack
);
370 ret
->collapsed_to
= NULL
;
374 typedef enum {SCALAR
, DEREF
, ADDRESSOF
} constraint_expr_type
;
376 /* An expression that appears in a constraint. */
378 struct constraint_expr
380 /* Constraint type. */
381 constraint_expr_type type
;
383 /* Variable we are referring to in the constraint. */
386 /* Offset, in bits, of this constraint from the beginning of
387 variables it ends up referring to.
389 IOW, in a deref constraint, we would deref, get the result set,
390 then add OFFSET to each member. */
391 unsigned HOST_WIDE_INT offset
;
394 typedef struct constraint_expr ce_s
;
396 DEF_VEC_ALLOC_O(ce_s
, heap
);
397 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
398 static void do_deref (VEC (ce_s
, heap
) **);
400 /* Our set constraints are made up of two constraint expressions, one
403 As described in the introduction, our set constraints each represent an
404 operation between set valued variables.
408 struct constraint_expr lhs
;
409 struct constraint_expr rhs
;
412 /* List of constraints that we use to build the constraint graph from. */
414 static VEC(constraint_t
,heap
) *constraints
;
415 static alloc_pool constraint_pool
;
417 /* An edge in the weighted constraint graph. The edges are weighted,
418 with a bit set in weights meaning their is an edge with that
420 We don't keep the src in the edge, because we always know what it
423 struct constraint_edge
429 typedef struct constraint_edge
*constraint_edge_t
;
430 static alloc_pool constraint_edge_pool
;
432 /* Return a new constraint edge from SRC to DEST. */
434 static constraint_edge_t
435 new_constraint_edge (unsigned int dest
)
437 constraint_edge_t ret
= pool_alloc (constraint_edge_pool
);
443 DEF_VEC_P(constraint_edge_t
);
444 DEF_VEC_ALLOC_P(constraint_edge_t
,heap
);
447 /* The constraint graph is represented internally in two different
448 ways. The overwhelming majority of edges in the constraint graph
449 are zero weigh edges, and thus, using a vector of contrainst_edge_t
450 is a waste of time and memory, since they have no weights. We
451 simply use a bitmap to store the preds and succs for each node.
452 The weighted edges are stored as a set of adjacency vectors, one
453 per variable. succs[x] is the vector of successors for variable x,
454 and preds[x] is the vector of predecessors for variable x. IOW,
455 all edges are "forward" edges, which is not like our CFG. So
456 remember that preds[x]->src == x, and succs[x]->src == x. */
458 struct constraint_graph
460 bitmap
*zero_weight_succs
;
461 bitmap
*zero_weight_preds
;
462 VEC(constraint_edge_t
,heap
) **succs
;
463 VEC(constraint_edge_t
,heap
) **preds
;
466 typedef struct constraint_graph
*constraint_graph_t
;
468 static constraint_graph_t graph
;
470 /* Create a new constraint consisting of LHS and RHS expressions. */
473 new_constraint (const struct constraint_expr lhs
,
474 const struct constraint_expr rhs
)
476 constraint_t ret
= pool_alloc (constraint_pool
);
482 /* Print out constraint C to FILE. */
485 dump_constraint (FILE *file
, constraint_t c
)
487 if (c
->lhs
.type
== ADDRESSOF
)
489 else if (c
->lhs
.type
== DEREF
)
491 fprintf (file
, "%s", get_varinfo_fc (c
->lhs
.var
)->name
);
492 if (c
->lhs
.offset
!= 0)
493 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
494 fprintf (file
, " = ");
495 if (c
->rhs
.type
== ADDRESSOF
)
497 else if (c
->rhs
.type
== DEREF
)
499 fprintf (file
, "%s", get_varinfo_fc (c
->rhs
.var
)->name
);
500 if (c
->rhs
.offset
!= 0)
501 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
502 fprintf (file
, "\n");
505 /* Print out constraint C to stderr. */
508 debug_constraint (constraint_t c
)
510 dump_constraint (stderr
, c
);
513 /* Print out all constraints to FILE */
516 dump_constraints (FILE *file
)
520 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
521 dump_constraint (file
, c
);
524 /* Print out all constraints to stderr. */
527 debug_constraints (void)
529 dump_constraints (stderr
);
534 The solver is a simple worklist solver, that works on the following
537 sbitmap changed_nodes = all ones;
538 changed_count = number of nodes;
539 For each node that was already collapsed:
542 while (changed_count > 0)
544 compute topological ordering for constraint graph
546 find and collapse cycles in the constraint graph (updating
547 changed if necessary)
549 for each node (n) in the graph in topological order:
552 Process each complex constraint associated with the node,
553 updating changed if necessary.
555 For each outgoing edge from n, propagate the solution from n to
556 the destination of the edge, updating changed as necessary.
560 /* Return true if two constraint expressions A and B are equal. */
563 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
565 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
568 /* Return true if constraint expression A is less than constraint expression
569 B. This is just arbitrary, but consistent, in order to give them an
573 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
575 if (a
.type
== b
.type
)
578 return a
.offset
< b
.offset
;
580 return a
.var
< b
.var
;
583 return a
.type
< b
.type
;
586 /* Return true if constraint A is less than constraint B. This is just
587 arbitrary, but consistent, in order to give them an ordering. */
590 constraint_less (const constraint_t a
, const constraint_t b
)
592 if (constraint_expr_less (a
->lhs
, b
->lhs
))
594 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
597 return constraint_expr_less (a
->rhs
, b
->rhs
);
600 /* Return true if two constraints A and B are equal. */
603 constraint_equal (struct constraint a
, struct constraint b
)
605 return constraint_expr_equal (a
.lhs
, b
.lhs
)
606 && constraint_expr_equal (a
.rhs
, b
.rhs
);
610 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
613 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
614 struct constraint lookfor
)
622 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
623 if (place
>= VEC_length (constraint_t
, vec
))
625 found
= VEC_index (constraint_t
, vec
, place
);
626 if (!constraint_equal (*found
, lookfor
))
631 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
634 constraint_set_union (VEC(constraint_t
,heap
) **to
,
635 VEC(constraint_t
,heap
) **from
)
640 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
642 if (constraint_vec_find (*to
, *c
) == NULL
)
644 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
646 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
651 /* Take a solution set SET, add OFFSET to each member of the set, and
652 overwrite SET with the result when done. */
655 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
657 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
661 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
663 /* If this is a properly sized variable, only add offset if it's
664 less than end. Otherwise, it is globbed to a single
667 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
669 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
670 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
673 bitmap_set_bit (result
, v
->id
);
675 else if (get_varinfo (i
)->is_artificial_var
676 || get_varinfo (i
)->has_union
677 || get_varinfo (i
)->is_unknown_size_var
)
679 bitmap_set_bit (result
, i
);
683 bitmap_copy (set
, result
);
684 BITMAP_FREE (result
);
687 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
691 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
694 return bitmap_ior_into (to
, from
);
700 tmp
= BITMAP_ALLOC (&iteration_obstack
);
701 bitmap_copy (tmp
, from
);
702 solution_set_add (tmp
, inc
);
703 res
= bitmap_ior_into (to
, tmp
);
709 /* Insert constraint C into the list of complex constraints for VAR. */
712 insert_into_complex (unsigned int var
, constraint_t c
)
714 varinfo_t vi
= get_varinfo (var
);
715 unsigned int place
= VEC_lower_bound (constraint_t
, vi
->complex, c
,
717 VEC_safe_insert (constraint_t
, heap
, vi
->complex, place
, c
);
721 /* Compare two constraint edges A and B, return true if they are equal. */
724 constraint_edge_equal (struct constraint_edge a
, struct constraint_edge b
)
726 return a
.dest
== b
.dest
;
729 /* Compare two constraint edges, return true if A is less than B */
732 constraint_edge_less (const constraint_edge_t a
, const constraint_edge_t b
)
734 if (a
->dest
< b
->dest
)
739 /* Find the constraint edge that matches LOOKFOR, in VEC.
740 Return the edge, if found, NULL otherwise. */
742 static constraint_edge_t
743 constraint_edge_vec_find (VEC(constraint_edge_t
,heap
) *vec
,
744 struct constraint_edge lookfor
)
747 constraint_edge_t edge
= NULL
;
749 place
= VEC_lower_bound (constraint_edge_t
, vec
, &lookfor
,
750 constraint_edge_less
);
751 if (place
>= VEC_length (constraint_edge_t
, vec
))
753 edge
= VEC_index (constraint_edge_t
, vec
, place
);
754 if (!constraint_edge_equal (*edge
, lookfor
))
759 /* Condense two variable nodes into a single variable node, by moving
760 all associated info from SRC to TO. */
763 condense_varmap_nodes (unsigned int to
, unsigned int src
)
765 varinfo_t tovi
= get_varinfo (to
);
766 varinfo_t srcvi
= get_varinfo (src
);
771 /* the src node, and all its variables, are now the to node. */
773 EXECUTE_IF_SET_IN_BITMAP (srcvi
->variables
, 0, i
, bi
)
774 get_varinfo (i
)->node
= to
;
776 /* Merge the src node variables and the to node variables. */
777 bitmap_set_bit (tovi
->variables
, src
);
778 bitmap_ior_into (tovi
->variables
, srcvi
->variables
);
779 bitmap_clear (srcvi
->variables
);
781 /* Move all complex constraints from src node into to node */
782 for (i
= 0; VEC_iterate (constraint_t
, srcvi
->complex, i
, c
); i
++)
784 /* In complex constraints for node src, we may have either
785 a = *src, and *src = a. */
787 if (c
->rhs
.type
== DEREF
)
792 constraint_set_union (&tovi
->complex, &srcvi
->complex);
793 VEC_free (constraint_t
, heap
, srcvi
->complex);
794 srcvi
->complex = NULL
;
797 /* Erase an edge from SRC to SRC from GRAPH. This routine only
798 handles self-edges (e.g. an edge from a to a). */
801 erase_graph_self_edge (constraint_graph_t graph
, unsigned int src
)
803 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[src
];
804 VEC(constraint_edge_t
,heap
) *succvec
= graph
->succs
[src
];
805 struct constraint_edge edge
;
810 /* Remove from the successors. */
811 place
= VEC_lower_bound (constraint_edge_t
, succvec
, &edge
,
812 constraint_edge_less
);
814 /* Make sure we found the edge. */
815 #ifdef ENABLE_CHECKING
817 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, succvec
, place
);
818 gcc_assert (constraint_edge_equal (*tmp
, edge
));
821 VEC_ordered_remove (constraint_edge_t
, succvec
, place
);
823 /* Remove from the predecessors. */
824 place
= VEC_lower_bound (constraint_edge_t
, predvec
, &edge
,
825 constraint_edge_less
);
827 /* Make sure we found the edge. */
828 #ifdef ENABLE_CHECKING
830 constraint_edge_t tmp
= VEC_index (constraint_edge_t
, predvec
, place
);
831 gcc_assert (constraint_edge_equal (*tmp
, edge
));
834 VEC_ordered_remove (constraint_edge_t
, predvec
, place
);
837 /* Remove edges involving NODE from GRAPH. */
840 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
842 VEC(constraint_edge_t
,heap
) *succvec
= graph
->succs
[node
];
843 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[node
];
846 constraint_edge_t c
= NULL
;
849 /* Walk the successors, erase the associated preds. */
851 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[node
], 0, j
, bi
)
853 bitmap_clear_bit (graph
->zero_weight_preds
[j
], node
);
855 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
859 struct constraint_edge lookfor
;
860 constraint_edge_t result
;
863 place
= VEC_lower_bound (constraint_edge_t
, graph
->preds
[c
->dest
],
864 &lookfor
, constraint_edge_less
);
865 result
= VEC_ordered_remove (constraint_edge_t
,
866 graph
->preds
[c
->dest
], place
);
867 pool_free (constraint_edge_pool
, result
);
870 /* Walk the preds, erase the associated succs. */
872 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_preds
[node
], 0, j
, bi
)
874 bitmap_clear_bit (graph
->zero_weight_succs
[j
], node
);
876 for (i
=0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
880 struct constraint_edge lookfor
;
881 constraint_edge_t result
;
884 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[c
->dest
],
885 &lookfor
, constraint_edge_less
);
886 result
= VEC_ordered_remove (constraint_edge_t
,
887 graph
->succs
[c
->dest
], place
);
888 pool_free (constraint_edge_pool
, result
);
892 if (graph
->zero_weight_preds
[node
])
894 BITMAP_FREE (graph
->zero_weight_preds
[node
]);
895 graph
->zero_weight_preds
[node
] = NULL
;
898 if (graph
->zero_weight_succs
[node
])
900 BITMAP_FREE (graph
->zero_weight_succs
[node
]);
901 graph
->zero_weight_succs
[node
] = NULL
;
904 VEC_free (constraint_edge_t
, heap
, graph
->preds
[node
]);
905 VEC_free (constraint_edge_t
, heap
, graph
->succs
[node
]);
906 graph
->preds
[node
] = NULL
;
907 graph
->succs
[node
] = NULL
;
910 static bool edge_added
= false;
912 /* Add edge (src, dest) to the graph. */
915 add_graph_edge (constraint_graph_t graph
, unsigned int src
, unsigned int dest
)
918 VEC(constraint_edge_t
,heap
) *vec
;
919 struct constraint_edge newe
;
922 vec
= graph
->preds
[src
];
923 place
= VEC_lower_bound (constraint_edge_t
, vec
, &newe
,
924 constraint_edge_less
);
925 if (place
== VEC_length (constraint_edge_t
, vec
)
926 || VEC_index (constraint_edge_t
, vec
, place
)->dest
!= dest
)
928 constraint_edge_t edge
= new_constraint_edge (dest
);
930 VEC_safe_insert (constraint_edge_t
, heap
, graph
->preds
[src
],
932 edge
= new_constraint_edge (src
);
934 place
= VEC_lower_bound (constraint_edge_t
, graph
->succs
[dest
],
935 edge
, constraint_edge_less
);
936 VEC_safe_insert (constraint_edge_t
, heap
, graph
->succs
[dest
],
947 /* Return the bitmap representing the weights of edge (SRC, DEST). */
950 get_graph_weights (constraint_graph_t graph
, unsigned int src
,
953 constraint_edge_t edge
;
954 VEC(constraint_edge_t
,heap
) *vec
;
955 struct constraint_edge lookfor
;
959 vec
= graph
->preds
[src
];
960 edge
= constraint_edge_vec_find (vec
, lookfor
);
961 gcc_assert (edge
!= NULL
);
962 return &edge
->weights
;
965 /* Allocate graph weight bitmap for the edges associated with SRC and
966 DEST in GRAPH. Both the pred and the succ edges share a single
967 bitmap, so we need to set both edges to that bitmap. */
970 allocate_graph_weights (constraint_graph_t graph
, unsigned int src
,
974 constraint_edge_t edge
;
975 VEC(constraint_edge_t
,heap
) *vec
;
976 struct constraint_edge lookfor
;
978 result
= BITMAP_ALLOC (&ptabitmap_obstack
);
980 /* Set the pred weight. */
982 vec
= graph
->preds
[src
];
983 edge
= constraint_edge_vec_find (vec
, lookfor
);
984 gcc_assert (edge
!= NULL
);
985 edge
->weights
= result
;
987 /* Set the succ weight. */
989 vec
= graph
->succs
[dest
];
990 edge
= constraint_edge_vec_find (vec
, lookfor
);
991 gcc_assert (edge
!= NULL
);
992 edge
->weights
= result
;
998 /* Merge GRAPH nodes FROM and TO into node TO. */
1001 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
1004 VEC(constraint_edge_t
,heap
) *succvec
= graph
->succs
[from
];
1005 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[from
];
1007 constraint_edge_t c
;
1011 /* Merge all the zero weighted predecessor edges. */
1012 if (graph
->zero_weight_preds
[from
])
1014 if (!graph
->zero_weight_preds
[to
])
1015 graph
->zero_weight_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1017 EXECUTE_IF_SET_IN_BITMAP (graph
->zero_weight_preds
[from
], 0, j
, bi
)
1021 bitmap_clear_bit (graph
->zero_weight_succs
[j
], from
);
1022 bitmap_set_bit (graph
->zero_weight_succs
[j
], to
);
1025 bitmap_ior_into (graph
->zero_weight_preds
[to
],
1026 graph
->zero_weight_preds
[from
]);
1029 /* Merge all the zero weighted successor edges. */
1030 if (graph
->zero_weight_succs
[from
])
1032 if (!graph
->zero_weight_succs
[to
])
1033 graph
->zero_weight_succs
[to
] = BITMAP_ALLOC (&ptabitmap_obstack
);
1034 EXECUTE_IF_SET_IN_BITMAP (graph
->zero_weight_succs
[from
], 0, j
, bi
)
1036 bitmap_clear_bit (graph
->zero_weight_preds
[j
], from
);
1037 bitmap_set_bit (graph
->zero_weight_preds
[j
], to
);
1039 bitmap_ior_into (graph
->zero_weight_succs
[to
],
1040 graph
->zero_weight_succs
[from
]);
1043 /* Merge all the non-zero weighted predecessor edges. */
1044 for (i
= 0; VEC_iterate (constraint_edge_t
, predvec
, i
, c
); i
++)
1046 unsigned int d
= c
->dest
;
1050 if (c
->dest
== from
)
1053 add_graph_edge (graph
, to
, d
);
1055 temp
= *(get_graph_weights (graph
, from
, c
->dest
));
1058 weights
= get_graph_weights (graph
, to
, d
);
1060 *weights
= allocate_graph_weights (graph
, to
, d
);
1062 bitmap_ior_into (*weights
, temp
);
1067 /* Merge all the non-zero weighted successor edges. */
1068 for (i
= 0; VEC_iterate (constraint_edge_t
, succvec
, i
, c
); i
++)
1070 unsigned int d
= c
->dest
;
1074 if (c
->dest
== from
)
1077 add_graph_edge (graph
, d
, to
);
1079 temp
= *(get_graph_weights (graph
, c
->dest
, from
));
1082 weights
= get_graph_weights (graph
, d
, to
);
1084 *weights
= allocate_graph_weights (graph
, d
, to
);
1085 bitmap_ior_into (*weights
, temp
);
1088 clear_edges_for_node (graph
, from
);
1091 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
1092 it doesn't exist in the graph already.
1093 Return false if the edge already existed, true otherwise. */
1096 int_add_graph_edge (constraint_graph_t graph
, unsigned int to
,
1097 unsigned int from
, unsigned HOST_WIDE_INT weight
)
1099 if (to
== from
&& weight
== 0)
1109 if (!graph
->zero_weight_preds
[to
])
1110 graph
->zero_weight_preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
1111 if (!graph
->zero_weight_succs
[from
])
1112 graph
->zero_weight_succs
[from
] = BITMAP_ALLOC (&ptabitmap_obstack
);
1113 if (!bitmap_bit_p (graph
->zero_weight_succs
[from
], to
))
1118 bitmap_set_bit (graph
->zero_weight_preds
[to
], from
);
1119 bitmap_set_bit (graph
->zero_weight_succs
[from
], to
);
1126 r
= add_graph_edge (graph
, to
, from
);
1127 weights
= get_graph_weights (graph
, to
, from
);
1132 *weights
= allocate_graph_weights (graph
, to
, from
);
1133 bitmap_set_bit (*weights
, weight
);
1137 r
|= !bitmap_bit_p (*weights
, weight
);
1138 bitmap_set_bit (*weights
, weight
);
1147 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1150 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
1153 struct constraint_edge lookfor
;
1156 return (graph
->zero_weight_succs
[dest
]
1157 && bitmap_bit_p (graph
->zero_weight_succs
[dest
], src
))
1158 || constraint_edge_vec_find (graph
->succs
[dest
], lookfor
) != NULL
;
1161 /* Return true if {DEST, SRC} is an existing weighted graph edge (IE has
1162 a weight other than 0) in GRAPH. */
1164 valid_weighted_graph_edge (constraint_graph_t graph
, unsigned int src
,
1167 struct constraint_edge lookfor
;
1170 return graph
->preds
[src
]
1171 && constraint_edge_vec_find (graph
->succs
[dest
], lookfor
) != NULL
;
1175 /* Build the constraint graph. */
1178 build_constraint_graph (void)
1183 graph
= XNEW (struct constraint_graph
);
1184 graph
->succs
= XCNEWVEC (VEC(constraint_edge_t
,heap
) *, VEC_length (varinfo_t
, varmap
) + 1);
1185 graph
->preds
= XCNEWVEC (VEC(constraint_edge_t
,heap
) *, VEC_length (varinfo_t
, varmap
) + 1);
1186 graph
->zero_weight_succs
= XCNEWVEC (bitmap
, VEC_length (varinfo_t
, varmap
) + 1);
1187 graph
->zero_weight_preds
= XCNEWVEC (bitmap
, VEC_length (varinfo_t
, varmap
) + 1);
1189 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1191 struct constraint_expr lhs
= c
->lhs
;
1192 struct constraint_expr rhs
= c
->rhs
;
1193 unsigned int lhsvar
= get_varinfo_fc (lhs
.var
)->id
;
1194 unsigned int rhsvar
= get_varinfo_fc (rhs
.var
)->id
;
1196 if (lhs
.type
== DEREF
)
1198 /* *x = y or *x = &y (complex) */
1199 if (rhs
.type
== ADDRESSOF
|| rhsvar
> anything_id
)
1200 insert_into_complex (lhsvar
, c
);
1202 else if (rhs
.type
== DEREF
)
1204 /* !special var= *y */
1205 if (!(get_varinfo (lhsvar
)->is_special_var
))
1206 insert_into_complex (rhsvar
, c
);
1208 else if (rhs
.type
== ADDRESSOF
)
1211 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1213 else if (lhsvar
> anything_id
)
1215 /* Ignore 0 weighted self edges, as they can't possibly contribute
1217 if (lhsvar
!= rhsvar
|| rhs
.offset
!= 0 || lhs
.offset
!= 0)
1219 /* x = y (simple) */
1220 int_add_graph_edge (graph
, lhs
.var
, rhs
.var
, rhs
.offset
);
1228 /* Changed variables on the last iteration. */
1229 static unsigned int changed_count
;
1230 static sbitmap changed
;
1232 DEF_VEC_I(unsigned);
1233 DEF_VEC_ALLOC_I(unsigned,heap
);
1236 /* Strongly Connected Component visitation info. */
1241 sbitmap in_component
;
1243 unsigned int *visited_index
;
1244 VEC(unsigned,heap
) *scc_stack
;
1245 VEC(unsigned,heap
) *unification_queue
;
1249 /* Recursive routine to find strongly connected components in GRAPH.
1250 SI is the SCC info to store the information in, and N is the id of current
1251 graph node we are processing.
1253 This is Tarjan's strongly connected component finding algorithm, as
1254 modified by Nuutila to keep only non-root nodes on the stack.
1255 The algorithm can be found in "On finding the strongly connected
1256 connected components in a directed graph" by Esko Nuutila and Eljas
1257 Soisalon-Soininen, in Information Processing Letters volume 49,
1258 number 1, pages 9-14. */
1261 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1266 gcc_assert (get_varinfo (n
)->node
== n
);
1267 SET_BIT (si
->visited
, n
);
1268 RESET_BIT (si
->in_component
, n
);
1269 si
->visited_index
[n
] = si
->current_index
++;
1271 /* Visit all the successors. */
1272 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[n
], 0, i
, bi
)
1275 if (!TEST_BIT (si
->visited
, w
))
1276 scc_visit (graph
, si
, w
);
1277 if (!TEST_BIT (si
->in_component
, w
))
1279 unsigned int t
= get_varinfo (w
)->node
;
1280 unsigned int nnode
= get_varinfo (n
)->node
;
1281 if (si
->visited_index
[t
] < si
->visited_index
[nnode
])
1282 get_varinfo (n
)->node
= t
;
1286 /* See if any components have been identified. */
1287 if (get_varinfo (n
)->node
== n
)
1289 unsigned int t
= si
->visited_index
[n
];
1290 SET_BIT (si
->in_component
, n
);
1291 while (VEC_length (unsigned, si
->scc_stack
) != 0
1292 && t
< si
->visited_index
[VEC_last (unsigned, si
->scc_stack
)])
1294 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1295 get_varinfo (w
)->node
= n
;
1296 SET_BIT (si
->in_component
, w
);
1297 /* Mark this node for collapsing. */
1298 VEC_safe_push (unsigned, heap
, si
->unification_queue
, w
);
1302 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1306 /* Collapse two variables into one variable. */
1309 collapse_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
)
1311 bitmap tosol
, fromsol
;
1313 condense_varmap_nodes (to
, from
);
1314 tosol
= get_varinfo (to
)->solution
;
1315 fromsol
= get_varinfo (from
)->solution
;
1316 bitmap_ior_into (tosol
, fromsol
);
1317 merge_graph_nodes (graph
, to
, from
);
1319 if (valid_graph_edge (graph
, to
, to
))
1321 if (graph
->zero_weight_preds
[to
])
1323 bitmap_clear_bit (graph
->zero_weight_preds
[to
], to
);
1324 bitmap_clear_bit (graph
->zero_weight_succs
[to
], to
);
1326 if (valid_weighted_graph_edge (graph
, to
, to
))
1328 bitmap weights
= *(get_graph_weights (graph
, to
, to
));
1329 if (!weights
|| bitmap_empty_p (weights
))
1330 erase_graph_self_edge (graph
, to
);
1333 BITMAP_FREE (fromsol
);
1334 get_varinfo (to
)->address_taken
|= get_varinfo (from
)->address_taken
;
1335 get_varinfo (to
)->indirect_target
|= get_varinfo (from
)->indirect_target
;
1339 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1340 SI is the Strongly Connected Components information structure that tells us
1341 what components to unify.
1342 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1343 count should be updated to reflect the unification. */
1346 process_unification_queue (constraint_graph_t graph
, struct scc_info
*si
,
1347 bool update_changed
)
1350 bitmap tmp
= BITMAP_ALLOC (update_changed
? &iteration_obstack
: NULL
);
1353 /* We proceed as follows:
1355 For each component in the queue (components are delineated by
1356 when current_queue_element->node != next_queue_element->node):
1358 rep = representative node for component
1360 For each node (tounify) to be unified in the component,
1361 merge the solution for tounify into tmp bitmap
1363 clear solution for tounify
1365 merge edges from tounify into rep
1367 merge complex constraints from tounify into rep
1369 update changed count to note that tounify will never change
1372 Merge tmp into solution for rep, marking rep changed if this
1373 changed rep's solution.
1375 Delete any 0 weighted self-edges we now have for rep. */
1376 while (i
!= VEC_length (unsigned, si
->unification_queue
))
1378 unsigned int tounify
= VEC_index (unsigned, si
->unification_queue
, i
);
1379 unsigned int n
= get_varinfo (tounify
)->node
;
1381 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1382 fprintf (dump_file
, "Unifying %s to %s\n",
1383 get_varinfo (tounify
)->name
,
1384 get_varinfo (n
)->name
);
1386 stats
.unified_vars_dynamic
++;
1388 stats
.unified_vars_static
++;
1389 bitmap_ior_into (tmp
, get_varinfo (tounify
)->solution
);
1390 merge_graph_nodes (graph
, n
, tounify
);
1391 condense_varmap_nodes (n
, tounify
);
1393 if (update_changed
&& TEST_BIT (changed
, tounify
))
1395 RESET_BIT (changed
, tounify
);
1396 if (!TEST_BIT (changed
, n
))
1397 SET_BIT (changed
, n
);
1400 gcc_assert (changed_count
> 0);
1405 bitmap_clear (get_varinfo (tounify
)->solution
);
1408 /* If we've either finished processing the entire queue, or
1409 finished processing all nodes for component n, update the solution for
1411 if (i
== VEC_length (unsigned, si
->unification_queue
)
1412 || get_varinfo (VEC_index (unsigned, si
->unification_queue
, i
))->node
!= n
)
1414 /* If the solution changes because of the merging, we need to mark
1415 the variable as changed. */
1416 if (bitmap_ior_into (get_varinfo (n
)->solution
, tmp
))
1418 if (update_changed
&& !TEST_BIT (changed
, n
))
1420 SET_BIT (changed
, n
);
1426 if (valid_graph_edge (graph
, n
, n
))
1428 if (graph
->zero_weight_succs
[n
])
1430 if (graph
->zero_weight_preds
[n
])
1431 bitmap_clear_bit (graph
->zero_weight_preds
[n
], n
);
1432 bitmap_clear_bit (graph
->zero_weight_succs
[n
], n
);
1434 if (valid_weighted_graph_edge (graph
, n
, n
))
1436 bitmap weights
= *(get_graph_weights (graph
, n
, n
));
1437 if (!weights
|| bitmap_empty_p (weights
))
1438 erase_graph_self_edge (graph
, n
);
1447 /* Information needed to compute the topological ordering of a graph. */
1451 /* sbitmap of visited nodes. */
1453 /* Array that stores the topological order of the graph, *in
1455 VEC(unsigned,heap
) *topo_order
;
1459 /* Initialize and return a topological info structure. */
1461 static struct topo_info
*
1462 init_topo_info (void)
1464 size_t size
= VEC_length (varinfo_t
, varmap
);
1465 struct topo_info
*ti
= XNEW (struct topo_info
);
1466 ti
->visited
= sbitmap_alloc (size
);
1467 sbitmap_zero (ti
->visited
);
1468 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1473 /* Free the topological sort info pointed to by TI. */
1476 free_topo_info (struct topo_info
*ti
)
1478 sbitmap_free (ti
->visited
);
1479 VEC_free (unsigned, heap
, ti
->topo_order
);
1483 /* Visit the graph in topological order, and store the order in the
1484 topo_info structure. */
1487 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1490 VEC(constraint_edge_t
,heap
) *succs
= graph
->succs
[n
];
1493 constraint_edge_t c
;
1497 SET_BIT (ti
->visited
, n
);
1498 if (VEC_length (constraint_edge_t
, succs
) != 0)
1500 temp
= BITMAP_ALLOC (&iteration_obstack
);
1501 if (graph
->zero_weight_succs
[n
])
1502 bitmap_ior_into (temp
, graph
->zero_weight_succs
[n
]);
1503 for (i
= 0; VEC_iterate (constraint_edge_t
, succs
, i
, c
); i
++)
1504 bitmap_set_bit (temp
, c
->dest
);
1507 temp
= graph
->zero_weight_succs
[n
];
1510 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, j
, bi
)
1512 if (!TEST_BIT (ti
->visited
, j
))
1513 topo_visit (graph
, ti
, j
);
1515 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1518 /* Return true if variable N + OFFSET is a legal field of N. */
1521 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1523 varinfo_t ninfo
= get_varinfo (n
);
1525 /* For things we've globbed to single variables, any offset into the
1526 variable acts like the entire variable, so that it becomes offset
1528 if (ninfo
->is_special_var
1529 || ninfo
->is_artificial_var
1530 || ninfo
->is_unknown_size_var
)
1535 return (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1538 #define DONT_PROPAGATE_WITH_ANYTHING 0
1540 /* Process a constraint C that represents *x = &y. */
1543 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1544 constraint_t c
, bitmap delta
)
1546 unsigned int rhs
= c
->rhs
.var
;
1550 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1551 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1553 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1554 if (type_safe (j
, &offset
) && !(get_varinfo (j
)->is_special_var
))
1556 /* *x != NULL && *x != ANYTHING*/
1560 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1562 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1566 sol
= get_varinfo (t
)->solution
;
1567 if (!bitmap_bit_p (sol
, rhs
))
1569 bitmap_set_bit (sol
, rhs
);
1570 if (!TEST_BIT (changed
, t
))
1572 SET_BIT (changed
, t
);
1577 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1578 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1583 /* Process a constraint C that represents x = *y, using DELTA as the
1584 starting solution. */
1587 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1590 unsigned int lhs
= get_varinfo (c
->lhs
.var
)->node
;
1592 bitmap sol
= get_varinfo (lhs
)->solution
;
1596 #if DONT_PROPAGATE_WITH_ANYTHING
1597 if (bitmap_bit_p (delta
, anything_id
))
1599 flag
= !bitmap_bit_p (sol
, anything_id
);
1601 bitmap_set_bit (sol
, anything_id
);
1605 /* For each variable j in delta (Sol(y)), add
1606 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1607 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1609 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1610 if (type_safe (j
, &roffset
))
1613 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1616 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1621 /* Adding edges from the special vars is pointless.
1622 They don't have sets that can change. */
1623 if (get_varinfo (t
) ->is_special_var
)
1624 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1625 else if (int_add_graph_edge (graph
, lhs
, t
, 0))
1626 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1628 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1629 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1632 #if DONT_PROPAGATE_WITH_ANYTHING
1635 /* If the LHS solution changed, mark the var as changed. */
1638 get_varinfo (lhs
)->solution
= sol
;
1639 if (!TEST_BIT (changed
, lhs
))
1641 SET_BIT (changed
, lhs
);
1647 /* Process a constraint C that represents *x = y. */
1650 do_ds_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1652 unsigned int rhs
= get_varinfo (c
->rhs
.var
)->node
;
1653 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1654 bitmap sol
= get_varinfo (rhs
)->solution
;
1658 #if DONT_PROPAGATE_WITH_ANYTHING
1659 if (bitmap_bit_p (sol
, anything_id
))
1661 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1663 varinfo_t jvi
= get_varinfo (j
);
1665 unsigned int loff
= c
->lhs
.offset
;
1666 unsigned HOST_WIDE_INT fieldoffset
= jvi
->offset
+ loff
;
1669 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1674 if (!bitmap_bit_p (get_varinfo (t
)->solution
, anything_id
))
1676 bitmap_set_bit (get_varinfo (t
)->solution
, anything_id
);
1677 if (!TEST_BIT (changed
, t
))
1679 SET_BIT (changed
, t
);
1688 /* For each member j of delta (Sol(x)), add an edge from y to j and
1689 union Sol(y) into Sol(j) */
1690 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1692 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1693 if (type_safe (j
, &loff
) && !(get_varinfo(j
)->is_special_var
))
1697 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1699 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1703 if (int_add_graph_edge (graph
, t
, rhs
, roff
))
1705 bitmap tmp
= get_varinfo (t
)->solution
;
1706 if (set_union_with_increment (tmp
, sol
, roff
))
1708 get_varinfo (t
)->solution
= tmp
;
1710 sol
= get_varinfo (rhs
)->solution
;
1711 if (!TEST_BIT (changed
, t
))
1713 SET_BIT (changed
, t
);
1719 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1720 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1724 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1725 constraint (IE *x = &y, x = *y, and *x = y). */
1728 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1730 if (c
->lhs
.type
== DEREF
)
1732 if (c
->rhs
.type
== ADDRESSOF
)
1735 do_da_constraint (graph
, c
, delta
);
1740 do_ds_constraint (graph
, c
, delta
);
1746 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1747 do_sd_constraint (graph
, c
, delta
);
1751 /* Initialize and return a new SCC info structure. */
1753 static struct scc_info
*
1754 init_scc_info (void)
1756 struct scc_info
*si
= XNEW (struct scc_info
);
1757 size_t size
= VEC_length (varinfo_t
, varmap
);
1759 si
->current_index
= 0;
1760 si
->visited
= sbitmap_alloc (size
);
1761 sbitmap_zero (si
->visited
);
1762 si
->in_component
= sbitmap_alloc (size
);
1763 sbitmap_ones (si
->in_component
);
1764 si
->visited_index
= XCNEWVEC (unsigned int, size
+ 1);
1765 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1766 si
->unification_queue
= VEC_alloc (unsigned, heap
, 1);
1770 /* Free an SCC info structure pointed to by SI */
1773 free_scc_info (struct scc_info
*si
)
1775 sbitmap_free (si
->visited
);
1776 sbitmap_free (si
->in_component
);
1777 free (si
->visited_index
);
1778 VEC_free (unsigned, heap
, si
->scc_stack
);
1779 VEC_free (unsigned, heap
, si
->unification_queue
);
1784 /* Find cycles in GRAPH that occur, using strongly connected components, and
1785 collapse the cycles into a single representative node. if UPDATE_CHANGED
1786 is true, then update the changed sbitmap to note those nodes whose
1787 solutions have changed as a result of collapsing. */
1790 find_and_collapse_graph_cycles (constraint_graph_t graph
, bool update_changed
)
1793 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1794 struct scc_info
*si
= init_scc_info ();
1796 for (i
= 0; i
!= size
; ++i
)
1797 if (!TEST_BIT (si
->visited
, i
) && get_varinfo (i
)->node
== i
)
1798 scc_visit (graph
, si
, i
);
1800 process_unification_queue (graph
, si
, update_changed
);
1804 /* Compute a topological ordering for GRAPH, and store the result in the
1805 topo_info structure TI. */
1808 compute_topo_order (constraint_graph_t graph
,
1809 struct topo_info
*ti
)
1812 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1814 for (i
= 0; i
!= size
; ++i
)
1815 if (!TEST_BIT (ti
->visited
, i
) && get_varinfo (i
)->node
== i
)
1816 topo_visit (graph
, ti
, i
);
1819 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1822 bitmap_other_than_zero_bit_set (bitmap b
)
1827 if (bitmap_empty_p (b
))
1829 EXECUTE_IF_SET_IN_BITMAP (b
, 1, i
, bi
)
1834 /* Perform offline variable substitution.
1836 This is a linear time way of identifying variables that must have
1837 equivalent points-to sets, including those caused by static cycles,
1838 and single entry subgraphs, in the constraint graph.
1840 The technique is described in "Off-line variable substitution for
1841 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1842 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1845 perform_var_substitution (constraint_graph_t graph
)
1847 struct topo_info
*ti
= init_topo_info ();
1849 bitmap_obstack_initialize (&iteration_obstack
);
1850 /* Compute the topological ordering of the graph, then visit each
1851 node in topological order. */
1852 compute_topo_order (graph
, ti
);
1854 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1856 unsigned int i
= VEC_pop (unsigned, ti
->topo_order
);
1858 varinfo_t vi
= get_varinfo (i
);
1859 bool okay_to_elim
= false;
1860 unsigned int root
= VEC_length (varinfo_t
, varmap
);
1861 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[i
];
1862 constraint_edge_t ce
= NULL
;
1867 /* We can't eliminate things whose address is taken, or which is
1868 the target of a dereference. */
1869 if (vi
->address_taken
|| vi
->indirect_target
)
1872 /* See if all predecessors of I are ripe for elimination */
1873 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_preds
[i
], 0, k
, bi
)
1876 w
= get_varinfo (k
)->node
;
1878 /* We can't eliminate the node if one of the predecessors is
1879 part of a different strongly connected component. */
1883 okay_to_elim
= true;
1887 okay_to_elim
= false;
1891 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1892 then Solution(i) is a subset of Solution (w), where w is a
1893 predecessor in the graph.
1894 Corollary: If all predecessors of i have the same
1895 points-to set, then i has that same points-to set as
1896 those predecessors. */
1897 tmp
= BITMAP_ALLOC (NULL
);
1898 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1899 get_varinfo (w
)->solution
);
1900 if (!bitmap_empty_p (tmp
))
1902 okay_to_elim
= false;
1911 VEC_iterate (constraint_edge_t
, predvec
, pred
, ce
);
1916 weight
= *(get_graph_weights (graph
, i
, ce
->dest
));
1918 /* We can't eliminate variables that have nonzero weighted
1919 edges between them. */
1920 if (weight
&& bitmap_other_than_zero_bit_set (weight
))
1922 okay_to_elim
= false;
1925 w
= get_varinfo (ce
->dest
)->node
;
1927 /* We can't eliminate the node if one of the predecessors is
1928 part of a different strongly connected component. */
1932 okay_to_elim
= true;
1936 okay_to_elim
= false;
1940 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1941 then Solution(i) is a subset of Solution (w), where w is a
1942 predecessor in the graph.
1943 Corollary: If all predecessors of i have the same
1944 points-to set, then i has that same points-to set as
1945 those predecessors. */
1946 tmp
= BITMAP_ALLOC (NULL
);
1947 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1948 get_varinfo (w
)->solution
);
1949 if (!bitmap_empty_p (tmp
))
1951 okay_to_elim
= false;
1958 /* See if the root is different than the original node.
1959 If so, we've found an equivalence. */
1960 if (root
!= get_varinfo (i
)->node
&& okay_to_elim
)
1962 /* Found an equivalence */
1963 get_varinfo (i
)->node
= root
;
1964 collapse_nodes (graph
, root
, i
);
1965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1966 fprintf (dump_file
, "Collapsing %s into %s\n",
1967 get_varinfo (i
)->name
,
1968 get_varinfo (root
)->name
);
1969 stats
.collapsed_vars
++;
1973 bitmap_obstack_release (&iteration_obstack
);
1974 free_topo_info (ti
);
1977 /* Solve the constraint graph GRAPH using our worklist solver.
1978 This is based on the PW* family of solvers from the "Efficient Field
1979 Sensitive Pointer Analysis for C" paper.
1980 It works by iterating over all the graph nodes, processing the complex
1981 constraints and propagating the copy constraints, until everything stops
1982 changed. This corresponds to steps 6-8 in the solving list given above. */
1985 solve_graph (constraint_graph_t graph
)
1987 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1990 changed_count
= size
;
1991 changed
= sbitmap_alloc (size
);
1992 sbitmap_ones (changed
);
1994 /* The already collapsed/unreachable nodes will never change, so we
1995 need to account for them in changed_count. */
1996 for (i
= 0; i
< size
; i
++)
1997 if (get_varinfo (i
)->node
!= i
)
2000 while (changed_count
> 0)
2003 struct topo_info
*ti
= init_topo_info ();
2006 bitmap_obstack_initialize (&iteration_obstack
);
2010 /* We already did cycle elimination once, when we did
2011 variable substitution, so we don't need it again for the
2013 if (stats
.iterations
> 1)
2014 find_and_collapse_graph_cycles (graph
, true);
2019 compute_topo_order (graph
, ti
);
2021 while (VEC_length (unsigned, ti
->topo_order
) != 0)
2023 i
= VEC_pop (unsigned, ti
->topo_order
);
2024 gcc_assert (get_varinfo (i
)->node
== i
);
2026 /* If the node has changed, we need to process the
2027 complex constraints and outgoing edges again. */
2028 if (TEST_BIT (changed
, i
))
2032 constraint_edge_t e
= NULL
;
2035 VEC(constraint_t
,heap
) *complex = get_varinfo (i
)->complex;
2036 VEC(constraint_edge_t
,heap
) *succs
;
2038 RESET_BIT (changed
, i
);
2041 /* Process the complex constraints */
2042 solution
= get_varinfo (i
)->solution
;
2043 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
2044 do_complex_constraint (graph
, c
, solution
);
2046 /* Propagate solution to all successors. */
2047 succs
= graph
->succs
[i
];
2049 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[i
], 0, j
, bi
)
2051 bitmap tmp
= get_varinfo (j
)->solution
;
2054 flag
= set_union_with_increment (tmp
, solution
, 0);
2058 get_varinfo (j
)->solution
= tmp
;
2059 if (!TEST_BIT (changed
, j
))
2061 SET_BIT (changed
, j
);
2066 for (j
= 0; VEC_iterate (constraint_edge_t
, succs
, j
, e
); j
++)
2068 bitmap tmp
= get_varinfo (e
->dest
)->solution
;
2071 bitmap weights
= e
->weights
;
2074 gcc_assert (weights
&& !bitmap_empty_p (weights
));
2075 EXECUTE_IF_SET_IN_BITMAP (weights
, 0, k
, bi
)
2076 flag
|= set_union_with_increment (tmp
, solution
, k
);
2080 get_varinfo (e
->dest
)->solution
= tmp
;
2081 if (!TEST_BIT (changed
, e
->dest
))
2083 SET_BIT (changed
, e
->dest
);
2090 free_topo_info (ti
);
2091 bitmap_obstack_release (&iteration_obstack
);
2094 sbitmap_free (changed
);
2098 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2100 /* Map from trees to variable ids. */
2101 static htab_t id_for_tree
;
2103 typedef struct tree_id
2109 /* Hash a tree id structure. */
2112 tree_id_hash (const void *p
)
2114 const tree_id_t ta
= (tree_id_t
) p
;
2115 return htab_hash_pointer (ta
->t
);
2118 /* Return true if the tree in P1 and the tree in P2 are the same. */
2121 tree_id_eq (const void *p1
, const void *p2
)
2123 const tree_id_t ta1
= (tree_id_t
) p1
;
2124 const tree_id_t ta2
= (tree_id_t
) p2
;
2125 return ta1
->t
== ta2
->t
;
2128 /* Insert ID as the variable id for tree T in the hashtable. */
2131 insert_id_for_tree (tree t
, int id
)
2134 struct tree_id finder
;
2138 slot
= htab_find_slot (id_for_tree
, &finder
, INSERT
);
2139 gcc_assert (*slot
== NULL
);
2140 new_pair
= XNEW (struct tree_id
);
2143 *slot
= (void *)new_pair
;
2146 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
2147 exist in the hash table, return false, otherwise, return true and
2148 set *ID to the id we found. */
2151 lookup_id_for_tree (tree t
, unsigned int *id
)
2154 struct tree_id finder
;
2157 pair
= htab_find (id_for_tree
, &finder
);
2164 /* Return a printable name for DECL */
2167 alias_get_name (tree decl
)
2169 const char *res
= get_name (decl
);
2171 int num_printed
= 0;
2177 if (TREE_CODE (decl
) == SSA_NAME
)
2179 num_printed
= asprintf (&temp
, "%s_%u",
2180 alias_get_name (SSA_NAME_VAR (decl
)),
2181 SSA_NAME_VERSION (decl
));
2183 else if (DECL_P (decl
))
2185 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2187 if (num_printed
> 0)
2189 res
= ggc_strdup (temp
);
2195 /* Find the variable id for tree T in the hashtable.
2196 If T doesn't exist in the hash table, create an entry for it. */
2199 get_id_for_tree (tree t
)
2202 struct tree_id finder
;
2205 pair
= htab_find (id_for_tree
, &finder
);
2207 return create_variable_info_for (t
, alias_get_name (t
));
2212 /* Get a constraint expression from an SSA_VAR_P node. */
2214 static struct constraint_expr
2215 get_constraint_exp_from_ssa_var (tree t
)
2217 struct constraint_expr cexpr
;
2219 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
2221 /* For parameters, get at the points-to set for the actual parm
2223 if (TREE_CODE (t
) == SSA_NAME
2224 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2225 && default_def (SSA_NAME_VAR (t
)) == t
)
2226 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
2228 cexpr
.type
= SCALAR
;
2230 cexpr
.var
= get_id_for_tree (t
);
2231 /* If we determine the result is "anything", and we know this is readonly,
2232 say it points to readonly memory instead. */
2233 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
2235 cexpr
.type
= ADDRESSOF
;
2236 cexpr
.var
= readonly_id
;
2243 /* Process a completed constraint T, and add it to the constraint
2247 process_constraint (constraint_t t
)
2249 struct constraint_expr rhs
= t
->rhs
;
2250 struct constraint_expr lhs
= t
->lhs
;
2252 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
2253 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
2255 /* ANYTHING == ANYTHING is pointless. */
2256 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
2259 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2260 else if (lhs
.var
== anything_id
&& lhs
.type
== ADDRESSOF
)
2265 process_constraint (t
);
2267 /* This can happen in our IR with things like n->a = *p */
2268 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
2270 /* Split into tmp = *rhs, *lhs = tmp */
2271 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
2272 tree pointertype
= TREE_TYPE (rhsdecl
);
2273 tree pointedtotype
= TREE_TYPE (pointertype
);
2274 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
2275 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2277 /* If this is an aggregate of known size, we should have passed
2278 this off to do_structure_copy, and it should have broken it
2280 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
2281 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
2283 process_constraint (new_constraint (tmplhs
, rhs
));
2284 process_constraint (new_constraint (lhs
, tmplhs
));
2286 else if (rhs
.type
== ADDRESSOF
)
2289 gcc_assert (rhs
.offset
== 0);
2291 for (vi
= get_varinfo (rhs
.var
); vi
!= NULL
; vi
= vi
->next
)
2292 vi
->address_taken
= true;
2294 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2298 if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2299 get_varinfo (lhs
.var
)->indirect_target
= true;
2300 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2305 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2308 static unsigned HOST_WIDE_INT
2309 bitpos_of_field (const tree fdecl
)
2312 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
2313 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
2316 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
2317 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
2321 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2322 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2325 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
2326 const unsigned HOST_WIDE_INT fieldsize
,
2327 const unsigned HOST_WIDE_INT accesspos
,
2328 const unsigned HOST_WIDE_INT accesssize
)
2330 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
2332 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
2334 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
2340 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2343 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
)
2346 HOST_WIDE_INT bitsize
= -1;
2347 HOST_WIDE_INT bitmaxsize
= -1;
2348 HOST_WIDE_INT bitpos
;
2350 struct constraint_expr
*result
;
2351 unsigned int beforelength
= VEC_length (ce_s
, *results
);
2353 /* Some people like to do cute things like take the address of
2356 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
2357 forzero
= TREE_OPERAND (forzero
, 0);
2359 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
2361 struct constraint_expr temp
;
2364 temp
.var
= integer_id
;
2366 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2370 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
2371 get_constraint_for (t
, results
);
2372 result
= VEC_last (ce_s
, *results
);
2373 result
->offset
= bitpos
;
2375 gcc_assert (beforelength
+ 1 == VEC_length (ce_s
, *results
));
2377 /* This can also happen due to weird offsetof type macros. */
2378 if (TREE_CODE (t
) != ADDR_EXPR
&& result
->type
== ADDRESSOF
)
2379 result
->type
= SCALAR
;
2381 if (result
->type
== SCALAR
)
2383 /* In languages like C, you can access one past the end of an
2384 array. You aren't allowed to dereference it, so we can
2385 ignore this constraint. When we handle pointer subtraction,
2386 we may have to do something cute here. */
2388 if (result
->offset
< get_varinfo (result
->var
)->fullsize
)
2390 /* It's also not true that the constraint will actually start at the
2391 right offset, it may start in some padding. We only care about
2392 setting the constraint to the first actual field it touches, so
2395 for (curr
= get_varinfo (result
->var
); curr
; curr
= curr
->next
)
2397 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2398 result
->offset
, bitmaxsize
))
2400 result
->var
= curr
->id
;
2404 /* assert that we found *some* field there. The user couldn't be
2405 accessing *only* padding. */
2406 /* Still the user could access one past the end of an array
2407 embedded in a struct resulting in accessing *only* padding. */
2408 gcc_assert (curr
|| ref_contains_array_ref (orig_t
));
2411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2412 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2419 /* Dereference the constraint expression CONS, and return the result.
2420 DEREF (ADDRESSOF) = SCALAR
2421 DEREF (SCALAR) = DEREF
2422 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2423 This is needed so that we can handle dereferencing DEREF constraints. */
2426 do_deref (VEC (ce_s
, heap
) **constraints
)
2428 struct constraint_expr
*c
;
2430 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
2432 if (c
->type
== SCALAR
)
2434 else if (c
->type
== ADDRESSOF
)
2436 else if (c
->type
== DEREF
)
2438 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "dereftmp");
2439 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2440 process_constraint (new_constraint (tmplhs
, *c
));
2441 c
->var
= tmplhs
.var
;
2449 /* Given a tree T, return the constraint expression for it. */
2452 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
2454 struct constraint_expr temp
;
2456 /* x = integer is all glommed to a single variable, which doesn't
2457 point to anything by itself. That is, of course, unless it is an
2458 integer constant being treated as a pointer, in which case, we
2459 will return that this is really the addressof anything. This
2460 happens below, since it will fall into the default case. The only
2461 case we know something about an integer treated like a pointer is
2462 when it is the NULL pointer, and then we just say it points to
2464 if (TREE_CODE (t
) == INTEGER_CST
2465 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2467 temp
.var
= integer_id
;
2470 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2473 else if (TREE_CODE (t
) == INTEGER_CST
2474 && integer_zerop (t
))
2476 temp
.var
= nothing_id
;
2477 temp
.type
= ADDRESSOF
;
2479 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2483 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2485 case tcc_expression
:
2487 switch (TREE_CODE (t
))
2491 struct constraint_expr
*c
;
2493 tree exp
= TREE_OPERAND (t
, 0);
2495 get_constraint_for (exp
, results
);
2496 /* Make sure we capture constraints to all elements
2498 if ((handled_component_p (exp
)
2499 && ref_contains_array_ref (exp
))
2500 || TREE_CODE (TREE_TYPE (exp
)) == ARRAY_TYPE
)
2502 struct constraint_expr
*origrhs
;
2504 struct constraint_expr tmp
;
2506 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2507 origrhs
= VEC_last (ce_s
, *results
);
2509 VEC_pop (ce_s
, *results
);
2510 origvar
= get_varinfo (origrhs
->var
);
2511 for (; origvar
; origvar
= origvar
->next
)
2513 tmp
.var
= origvar
->id
;
2514 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2517 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
2519 if (c
->type
== DEREF
)
2522 c
->type
= ADDRESSOF
;
2529 /* XXX: In interprocedural mode, if we didn't have the
2530 body, we would need to do *each pointer argument =
2532 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2535 tree heapvar
= heapvar_lookup (t
);
2537 if (heapvar
== NULL
)
2539 heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2540 DECL_EXTERNAL (heapvar
) = 1;
2541 add_referenced_tmp_var (heapvar
);
2542 heapvar_insert (t
, heapvar
);
2545 temp
.var
= create_variable_info_for (heapvar
,
2546 alias_get_name (heapvar
));
2548 vi
= get_varinfo (temp
.var
);
2549 vi
->is_artificial_var
= 1;
2550 vi
->is_heap_var
= 1;
2551 temp
.type
= ADDRESSOF
;
2553 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2559 temp
.type
= ADDRESSOF
;
2560 temp
.var
= anything_id
;
2562 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2569 switch (TREE_CODE (t
))
2573 get_constraint_for (TREE_OPERAND (t
, 0), results
);
2578 case ARRAY_RANGE_REF
:
2580 get_constraint_for_component_ref (t
, results
);
2584 temp
.type
= ADDRESSOF
;
2585 temp
.var
= anything_id
;
2587 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2594 switch (TREE_CODE (t
))
2598 case NON_LVALUE_EXPR
:
2600 tree op
= TREE_OPERAND (t
, 0);
2602 /* Cast from non-pointer to pointers are bad news for us.
2603 Anything else, we see through */
2604 if (!(POINTER_TYPE_P (TREE_TYPE (t
))
2605 && ! POINTER_TYPE_P (TREE_TYPE (op
))))
2607 get_constraint_for (op
, results
);
2615 temp
.type
= ADDRESSOF
;
2616 temp
.var
= anything_id
;
2618 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2623 case tcc_exceptional
:
2625 switch (TREE_CODE (t
))
2629 get_constraint_for (PHI_RESULT (t
), results
);
2635 struct constraint_expr temp
;
2636 temp
= get_constraint_exp_from_ssa_var (t
);
2637 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2643 temp
.type
= ADDRESSOF
;
2644 temp
.var
= anything_id
;
2646 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2651 case tcc_declaration
:
2653 struct constraint_expr temp
;
2654 temp
= get_constraint_exp_from_ssa_var (t
);
2655 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2660 temp
.type
= ADDRESSOF
;
2661 temp
.var
= anything_id
;
2663 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2670 /* Handle the structure copy case where we have a simple structure copy
2671 between LHS and RHS that is of SIZE (in bits)
2673 For each field of the lhs variable (lhsfield)
2674 For each field of the rhs variable at lhsfield.offset (rhsfield)
2675 add the constraint lhsfield = rhsfield
2677 If we fail due to some kind of type unsafety or other thing we
2678 can't handle, return false. We expect the caller to collapse the
2679 variable in that case. */
2682 do_simple_structure_copy (const struct constraint_expr lhs
,
2683 const struct constraint_expr rhs
,
2684 const unsigned HOST_WIDE_INT size
)
2686 varinfo_t p
= get_varinfo (lhs
.var
);
2687 unsigned HOST_WIDE_INT pstart
, last
;
2689 last
= p
->offset
+ size
;
2690 for (; p
&& p
->offset
< last
; p
= p
->next
)
2693 struct constraint_expr templhs
= lhs
;
2694 struct constraint_expr temprhs
= rhs
;
2695 unsigned HOST_WIDE_INT fieldoffset
;
2697 templhs
.var
= p
->id
;
2698 q
= get_varinfo (temprhs
.var
);
2699 fieldoffset
= p
->offset
- pstart
;
2700 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2703 temprhs
.var
= q
->id
;
2704 process_constraint (new_constraint (templhs
, temprhs
));
2710 /* Handle the structure copy case where we have a structure copy between a
2711 aggregate on the LHS and a dereference of a pointer on the RHS
2712 that is of SIZE (in bits)
2714 For each field of the lhs variable (lhsfield)
2715 rhs.offset = lhsfield->offset
2716 add the constraint lhsfield = rhs
2720 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2721 const struct constraint_expr rhs
,
2722 const unsigned HOST_WIDE_INT size
)
2724 varinfo_t p
= get_varinfo (lhs
.var
);
2725 unsigned HOST_WIDE_INT pstart
,last
;
2727 last
= p
->offset
+ size
;
2729 for (; p
&& p
->offset
< last
; p
= p
->next
)
2732 struct constraint_expr templhs
= lhs
;
2733 struct constraint_expr temprhs
= rhs
;
2734 unsigned HOST_WIDE_INT fieldoffset
;
2737 if (templhs
.type
== SCALAR
)
2738 templhs
.var
= p
->id
;
2740 templhs
.offset
= p
->offset
;
2742 q
= get_varinfo (temprhs
.var
);
2743 fieldoffset
= p
->offset
- pstart
;
2744 temprhs
.offset
+= fieldoffset
;
2745 process_constraint (new_constraint (templhs
, temprhs
));
2749 /* Handle the structure copy case where we have a structure copy
2750 between a aggregate on the RHS and a dereference of a pointer on
2751 the LHS that is of SIZE (in bits)
2753 For each field of the rhs variable (rhsfield)
2754 lhs.offset = rhsfield->offset
2755 add the constraint lhs = rhsfield
2759 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2760 const struct constraint_expr rhs
,
2761 const unsigned HOST_WIDE_INT size
)
2763 varinfo_t p
= get_varinfo (rhs
.var
);
2764 unsigned HOST_WIDE_INT pstart
,last
;
2766 last
= p
->offset
+ size
;
2768 for (; p
&& p
->offset
< last
; p
= p
->next
)
2771 struct constraint_expr templhs
= lhs
;
2772 struct constraint_expr temprhs
= rhs
;
2773 unsigned HOST_WIDE_INT fieldoffset
;
2776 if (temprhs
.type
== SCALAR
)
2777 temprhs
.var
= p
->id
;
2779 temprhs
.offset
= p
->offset
;
2781 q
= get_varinfo (templhs
.var
);
2782 fieldoffset
= p
->offset
- pstart
;
2783 templhs
.offset
+= fieldoffset
;
2784 process_constraint (new_constraint (templhs
, temprhs
));
2788 /* Sometimes, frontends like to give us bad type information. This
2789 function will collapse all the fields from VAR to the end of VAR,
2790 into VAR, so that we treat those fields as a single variable.
2791 We return the variable they were collapsed into. */
2794 collapse_rest_of_var (unsigned int var
)
2796 varinfo_t currvar
= get_varinfo (var
);
2799 for (field
= currvar
->next
; field
; field
= field
->next
)
2802 fprintf (dump_file
, "Type safety: Collapsing var %s into %s\n",
2803 field
->name
, currvar
->name
);
2805 gcc_assert (!field
->collapsed_to
);
2806 field
->collapsed_to
= currvar
;
2809 currvar
->next
= NULL
;
2810 currvar
->size
= currvar
->fullsize
- currvar
->offset
;
2815 /* Handle aggregate copies by expanding into copies of the respective
2816 fields of the structures. */
2819 do_structure_copy (tree lhsop
, tree rhsop
)
2821 struct constraint_expr lhs
, rhs
, tmp
;
2822 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
2824 unsigned HOST_WIDE_INT lhssize
;
2825 unsigned HOST_WIDE_INT rhssize
;
2827 get_constraint_for (lhsop
, &lhsc
);
2828 get_constraint_for (rhsop
, &rhsc
);
2829 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
2830 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
2831 lhs
= *(VEC_last (ce_s
, lhsc
));
2832 rhs
= *(VEC_last (ce_s
, rhsc
));
2834 VEC_free (ce_s
, heap
, lhsc
);
2835 VEC_free (ce_s
, heap
, rhsc
);
2837 /* If we have special var = x, swap it around. */
2838 if (lhs
.var
<= integer_id
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2845 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2846 possible it's something we could handle. However, most cases falling
2847 into this are dealing with transparent unions, which are slightly
2849 if (rhs
.type
== ADDRESSOF
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2851 rhs
.type
= ADDRESSOF
;
2852 rhs
.var
= anything_id
;
2855 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2856 that special var. */
2857 if (rhs
.var
<= integer_id
)
2859 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2861 struct constraint_expr templhs
= lhs
;
2862 struct constraint_expr temprhs
= rhs
;
2864 if (templhs
.type
== SCALAR
)
2865 templhs
.var
= p
->id
;
2867 templhs
.offset
+= p
->offset
;
2868 process_constraint (new_constraint (templhs
, temprhs
));
2873 tree rhstype
= TREE_TYPE (rhsop
);
2874 tree lhstype
= TREE_TYPE (lhsop
);
2878 lhstypesize
= DECL_P (lhsop
) ? DECL_SIZE (lhsop
) : TYPE_SIZE (lhstype
);
2879 rhstypesize
= DECL_P (rhsop
) ? DECL_SIZE (rhsop
) : TYPE_SIZE (rhstype
);
2881 /* If we have a variably sized types on the rhs or lhs, and a deref
2882 constraint, add the constraint, lhsconstraint = &ANYTHING.
2883 This is conservatively correct because either the lhs is an unknown
2884 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2885 constraint, and every variable it can point to must be unknown sized
2886 anyway, so we don't need to worry about fields at all. */
2887 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
2888 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
2890 rhs
.var
= anything_id
;
2891 rhs
.type
= ADDRESSOF
;
2893 process_constraint (new_constraint (lhs
, rhs
));
2897 /* The size only really matters insofar as we don't set more or less of
2898 the variable. If we hit an unknown size var, the size should be the
2899 whole darn thing. */
2900 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
2903 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
2905 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
2908 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
2911 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
2913 if (!do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
)))
2915 lhs
.var
= collapse_rest_of_var (lhs
.var
);
2916 rhs
.var
= collapse_rest_of_var (rhs
.var
);
2921 process_constraint (new_constraint (lhs
, rhs
));
2924 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2925 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2926 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
2927 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2930 tree pointedtotype
= lhstype
;
2933 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
2934 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
2935 do_structure_copy (tmpvar
, rhsop
);
2936 do_structure_copy (lhsop
, tmpvar
);
2941 /* Update related alias information kept in AI. This is used when
2942 building name tags, alias sets and deciding grouping heuristics.
2943 STMT is the statement to process. This function also updates
2944 ADDRESSABLE_VARS. */
2947 update_alias_info (tree stmt
, struct alias_info
*ai
)
2950 use_operand_p use_p
;
2952 enum escape_type stmt_escape_type
= is_escape_site (stmt
, ai
);
2955 /* Mark all the variables whose address are taken by the statement. */
2956 addr_taken
= addresses_taken (stmt
);
2959 bitmap_ior_into (addressable_vars
, addr_taken
);
2961 /* If STMT is an escape point, all the addresses taken by it are
2963 if (stmt_escape_type
!= NO_ESCAPE
)
2968 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
2970 tree rvar
= referenced_var (i
);
2971 if (!unmodifiable_var_p (rvar
))
2972 mark_call_clobbered (rvar
, stmt_escape_type
);
2977 /* Process each operand use. If an operand may be aliased, keep
2978 track of how many times it's being used. For pointers, determine
2979 whether they are dereferenced by the statement, or whether their
2980 value escapes, etc. */
2981 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2985 struct ptr_info_def
*pi
;
2986 bool is_store
, is_potential_deref
;
2987 unsigned num_uses
, num_derefs
;
2989 op
= USE_FROM_PTR (use_p
);
2991 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2992 to the set of addressable variables. */
2993 if (TREE_CODE (op
) == ADDR_EXPR
)
2995 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
);
2997 /* PHI nodes don't have annotations for pinning the set
2998 of addresses taken, so we collect them here.
3000 FIXME, should we allow PHI nodes to have annotations
3001 so that they can be treated like regular statements?
3002 Currently, they are treated as second-class
3004 add_to_addressable_set (TREE_OPERAND (op
, 0), &addressable_vars
);
3008 /* Ignore constants. */
3009 if (TREE_CODE (op
) != SSA_NAME
)
3012 var
= SSA_NAME_VAR (op
);
3013 v_ann
= var_ann (var
);
3015 /* The base variable of an ssa name must be a GIMPLE register, and thus
3016 it cannot be aliased. */
3017 gcc_assert (!may_be_aliased (var
));
3019 /* We are only interested in pointers. */
3020 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
3023 pi
= get_ptr_info (op
);
3025 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3026 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
)))
3028 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
));
3029 VARRAY_PUSH_TREE (ai
->processed_ptrs
, op
);
3032 /* If STMT is a PHI node, then it will not have pointer
3033 dereferences and it will not be an escape point. */
3034 if (TREE_CODE (stmt
) == PHI_NODE
)
3037 /* Determine whether OP is a dereferenced pointer, and if STMT
3038 is an escape point, whether OP escapes. */
3039 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
3041 /* Handle a corner case involving address expressions of the
3042 form '&PTR->FLD'. The problem with these expressions is that
3043 they do not represent a dereference of PTR. However, if some
3044 other transformation propagates them into an INDIRECT_REF
3045 expression, we end up with '*(&PTR->FLD)' which is folded
3048 So, if the original code had no other dereferences of PTR,
3049 the aliaser will not create memory tags for it, and when
3050 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3051 memory operations will receive no V_MAY_DEF/VUSE operands.
3053 One solution would be to have count_uses_and_derefs consider
3054 &PTR->FLD a dereference of PTR. But that is wrong, since it
3055 is not really a dereference but an offset calculation.
3057 What we do here is to recognize these special ADDR_EXPR
3058 nodes. Since these expressions are never GIMPLE values (they
3059 are not GIMPLE invariants), they can only appear on the RHS
3060 of an assignment and their base address is always an
3061 INDIRECT_REF expression. */
3062 is_potential_deref
= false;
3063 if (TREE_CODE (stmt
) == MODIFY_EXPR
3064 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ADDR_EXPR
3065 && !is_gimple_val (TREE_OPERAND (stmt
, 1)))
3067 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3068 this represents a potential dereference of PTR. */
3069 tree rhs
= TREE_OPERAND (stmt
, 1);
3070 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
3071 if (TREE_CODE (base
) == INDIRECT_REF
3072 && TREE_OPERAND (base
, 0) == op
)
3073 is_potential_deref
= true;
3076 if (num_derefs
> 0 || is_potential_deref
)
3078 /* Mark OP as dereferenced. In a subsequent pass,
3079 dereferenced pointers that point to a set of
3080 variables will be assigned a name tag to alias
3081 all the variables OP points to. */
3082 pi
->is_dereferenced
= 1;
3084 /* Keep track of how many time we've dereferenced each
3086 NUM_REFERENCES_INC (v_ann
);
3088 /* If this is a store operation, mark OP as being
3089 dereferenced to store, otherwise mark it as being
3090 dereferenced to load. */
3092 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
3094 bitmap_set_bit (ai
->dereferenced_ptrs_load
, DECL_UID (var
));
3097 if (stmt_escape_type
!= NO_ESCAPE
&& num_derefs
< num_uses
)
3099 /* If STMT is an escape point and STMT contains at
3100 least one direct use of OP, then the value of OP
3101 escapes and so the pointed-to variables need to
3102 be marked call-clobbered. */
3103 pi
->value_escapes_p
= 1;
3104 pi
->escape_mask
|= stmt_escape_type
;
3106 /* If the statement makes a function call, assume
3107 that pointer OP will be dereferenced in a store
3108 operation inside the called function. */
3109 if (get_call_expr_in (stmt
))
3111 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
3112 pi
->is_dereferenced
= 1;
3117 if (TREE_CODE (stmt
) == PHI_NODE
)
3120 /* Update reference counter for definitions to any
3121 potentially aliased variable. This is used in the alias
3122 grouping heuristics. */
3123 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3125 tree var
= SSA_NAME_VAR (op
);
3126 var_ann_t ann
= var_ann (var
);
3127 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
3128 if (may_be_aliased (var
))
3129 NUM_REFERENCES_INC (ann
);
3133 /* Mark variables in V_MAY_DEF operands as being written to. */
3134 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
3136 tree var
= DECL_P (op
) ? op
: SSA_NAME_VAR (op
);
3137 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
3142 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3143 Expressions of the type PTR + CST can be handled in two ways:
3145 1- If the constraint for PTR is ADDRESSOF for a non-structure
3146 variable, then we can use it directly because adding or
3147 subtracting a constant may not alter the original ADDRESSOF
3148 constraint (i.e., pointer arithmetic may not legally go outside
3149 an object's boundaries).
3151 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3152 then if CST is a compile-time constant that can be used as an
3153 offset, we can determine which sub-variable will be pointed-to
3156 Return true if the expression is handled. For any other kind of
3157 expression, return false so that each operand can be added as a
3158 separate constraint by the caller. */
3161 handle_ptr_arith (VEC (ce_s
, heap
) *lhsc
, tree expr
)
3164 struct constraint_expr
*c
, *c2
;
3167 VEC (ce_s
, heap
) *temp
= NULL
;
3168 unsigned int rhsoffset
= 0;
3170 if (TREE_CODE (expr
) != PLUS_EXPR
)
3173 op0
= TREE_OPERAND (expr
, 0);
3174 op1
= TREE_OPERAND (expr
, 1);
3176 get_constraint_for (op0
, &temp
);
3177 if (POINTER_TYPE_P (TREE_TYPE (op0
))
3178 && TREE_CODE (op1
) == INTEGER_CST
)
3180 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
3184 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
3185 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
3187 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
3189 varinfo_t temp
= get_varinfo (c2
->var
);
3191 /* An access one after the end of an array is valid,
3192 so simply punt on accesses we cannot resolve. */
3193 temp
= first_vi_for_offset (temp
, rhsoffset
);
3200 c2
->offset
= rhsoffset
;
3201 process_constraint (new_constraint (*c
, *c2
));
3204 VEC_free (ce_s
, heap
, temp
);
3210 /* Walk statement T setting up aliasing constraints according to the
3211 references found in T. This function is the main part of the
3212 constraint builder. AI points to auxiliary alias information used
3213 when building alias sets and computing alias grouping heuristics. */
3216 find_func_aliases (tree origt
)
3219 VEC(ce_s
, heap
) *lhsc
= NULL
;
3220 VEC(ce_s
, heap
) *rhsc
= NULL
;
3221 struct constraint_expr
*c
;
3223 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
3224 t
= TREE_OPERAND (t
, 0);
3226 /* Now build constraints expressions. */
3227 if (TREE_CODE (t
) == PHI_NODE
)
3229 /* Only care about pointers and structures containing
3231 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t
)))
3232 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))))
3237 /* For a phi node, assign all the arguments to
3239 get_constraint_for (PHI_RESULT (t
), &lhsc
);
3240 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
3242 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
3243 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3245 struct constraint_expr
*c2
;
3246 while (VEC_length (ce_s
, rhsc
) > 0)
3248 c2
= VEC_last (ce_s
, rhsc
);
3249 process_constraint (new_constraint (*c
, *c2
));
3250 VEC_pop (ce_s
, rhsc
);
3256 /* In IPA mode, we need to generate constraints to pass call
3257 arguments through their calls. There are two case, either a
3258 modify_expr when we are returning a value, or just a plain
3259 call_expr when we are not. */
3260 else if (in_ipa_mode
3261 && ((TREE_CODE (t
) == MODIFY_EXPR
3262 && TREE_CODE (TREE_OPERAND (t
, 1)) == CALL_EXPR
3263 && !(call_expr_flags (TREE_OPERAND (t
, 1))
3264 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
3265 || (TREE_CODE (t
) == CALL_EXPR
3266 && !(call_expr_flags (t
)
3267 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
3277 if (TREE_CODE (t
) == MODIFY_EXPR
)
3279 lhsop
= TREE_OPERAND (t
, 0);
3280 rhsop
= TREE_OPERAND (t
, 1);
3287 decl
= get_callee_fndecl (rhsop
);
3289 /* If we can directly resolve the function being called, do so.
3290 Otherwise, it must be some sort of indirect expression that
3291 we should still be able to handle. */
3294 found
= lookup_id_for_tree (decl
, &varid
);
3299 decl
= TREE_OPERAND (rhsop
, 0);
3300 found
= lookup_id_for_tree (decl
, &varid
);
3304 /* Assign all the passed arguments to the appropriate incoming
3305 parameters of the function. */
3306 fi
= get_varinfo (varid
);
3307 arglist
= TREE_OPERAND (rhsop
, 1);
3309 for (;arglist
; arglist
= TREE_CHAIN (arglist
))
3311 tree arg
= TREE_VALUE (arglist
);
3312 struct constraint_expr lhs
;
3313 struct constraint_expr
*rhsp
;
3315 get_constraint_for (arg
, &rhsc
);
3316 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3325 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3328 while (VEC_length (ce_s
, rhsc
) != 0)
3330 rhsp
= VEC_last (ce_s
, rhsc
);
3331 process_constraint (new_constraint (lhs
, *rhsp
));
3332 VEC_pop (ce_s
, rhsc
);
3336 /* If we are returning a value, assign it to the result. */
3339 struct constraint_expr rhs
;
3340 struct constraint_expr
*lhsp
;
3343 get_constraint_for (lhsop
, &lhsc
);
3344 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3353 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3356 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3357 process_constraint (new_constraint (*lhsp
, rhs
));
3360 /* Otherwise, just a regular assignment statement. */
3361 else if (TREE_CODE (t
) == MODIFY_EXPR
)
3363 tree lhsop
= TREE_OPERAND (t
, 0);
3364 tree rhsop
= TREE_OPERAND (t
, 1);
3367 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3368 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop
)))
3370 do_structure_copy (lhsop
, rhsop
);
3374 /* Only care about operations with pointers, structures
3375 containing pointers, dereferences, and call expressions. */
3376 if (POINTER_TYPE_P (TREE_TYPE (lhsop
))
3377 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3378 || TREE_CODE (rhsop
) == CALL_EXPR
)
3380 get_constraint_for (lhsop
, &lhsc
);
3381 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3383 /* RHS that consist of unary operations,
3384 exceptional types, or bare decls/constants, get
3385 handled directly by get_constraint_for. */
3387 case tcc_declaration
:
3389 case tcc_exceptional
:
3390 case tcc_expression
:
3394 tree strippedrhs
= rhsop
;
3397 /* XXX: Push this back into the ADDR_EXPR
3398 case, and remove anyoffset handling. */
3399 STRIP_NOPS (strippedrhs
);
3400 rhstype
= TREE_TYPE (strippedrhs
);
3402 get_constraint_for (rhsop
, &rhsc
);
3403 if (TREE_CODE (strippedrhs
) == ADDR_EXPR
3404 && AGGREGATE_TYPE_P (TREE_TYPE (rhstype
))
3405 && VEC_length (ce_s
, rhsc
) == 1)
3407 struct constraint_expr
*origrhs
;
3409 struct constraint_expr tmp
;
3411 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
3412 origrhs
= VEC_last (ce_s
, rhsc
);
3414 VEC_pop (ce_s
, rhsc
);
3415 origvar
= get_varinfo (origrhs
->var
);
3416 for (; origvar
; origvar
= origvar
->next
)
3418 tmp
.var
= origvar
->id
;
3419 VEC_safe_push (ce_s
, heap
, rhsc
, &tmp
);
3423 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3425 struct constraint_expr
*c2
;
3428 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3429 process_constraint (new_constraint (*c
, *c2
));
3437 /* For pointer arithmetic of the form
3438 PTR + CST, we can simply use PTR's
3439 constraint because pointer arithmetic is
3440 not allowed to go out of bounds. */
3441 if (handle_ptr_arith (lhsc
, rhsop
))
3446 /* Otherwise, walk each operand. Notice that we
3447 can't use the operand interface because we need
3448 to process expressions other than simple operands
3449 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3451 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
3453 tree op
= TREE_OPERAND (rhsop
, i
);
3456 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3457 get_constraint_for (op
, &rhsc
);
3458 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3460 struct constraint_expr
*c2
;
3461 while (VEC_length (ce_s
, rhsc
) > 0)
3463 c2
= VEC_last (ce_s
, rhsc
);
3464 process_constraint (new_constraint (*c
, *c2
));
3465 VEC_pop (ce_s
, rhsc
);
3474 /* After promoting variables and computing aliasing we will
3475 need to re-scan most statements. FIXME: Try to minimize the
3476 number of statements re-scanned. It's not really necessary to
3477 re-scan *all* statements. */
3478 mark_stmt_modified (origt
);
3479 VEC_free (ce_s
, heap
, rhsc
);
3480 VEC_free (ce_s
, heap
, lhsc
);
3484 /* Find the first varinfo in the same variable as START that overlaps with
3486 Effectively, walk the chain of fields for the variable START to find the
3487 first field that overlaps with OFFSET.
3488 Return NULL if we can't find one. */
3491 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3493 varinfo_t curr
= start
;
3496 /* We may not find a variable in the field list with the actual
3497 offset when when we have glommed a structure to a variable.
3498 In that case, however, offset should still be within the size
3500 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3508 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3512 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3514 varinfo_t prev
= base
;
3515 varinfo_t curr
= base
->next
;
3526 if (field
->offset
<= curr
->offset
)
3531 field
->next
= prev
->next
;
3536 /* qsort comparison function for two fieldoff's PA and PB */
3539 fieldoff_compare (const void *pa
, const void *pb
)
3541 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3542 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3543 HOST_WIDE_INT foasize
, fobsize
;
3545 if (foa
->offset
!= fob
->offset
)
3546 return foa
->offset
- fob
->offset
;
3548 foasize
= TREE_INT_CST_LOW (foa
->size
);
3549 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3550 return foasize
- fobsize
;
3553 /* Sort a fieldstack according to the field offset and sizes. */
3554 void sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3556 qsort (VEC_address (fieldoff_s
, fieldstack
),
3557 VEC_length (fieldoff_s
, fieldstack
),
3558 sizeof (fieldoff_s
),
3562 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3563 of TYPE onto fieldstack, recording their offsets along the way.
3564 OFFSET is used to keep track of the offset in this entire structure, rather
3565 than just the immediately containing structure. Returns the number
3567 HAS_UNION is set to true if we find a union type as a field of
3571 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3572 HOST_WIDE_INT offset
, bool *has_union
)
3577 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3579 fieldoff_s
*real_part
, *img_part
;
3580 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3581 real_part
->type
= TREE_TYPE (type
);
3582 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3583 real_part
->offset
= offset
;
3584 real_part
->decl
= NULL_TREE
;
3586 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3587 img_part
->type
= TREE_TYPE (type
);
3588 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3589 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3590 img_part
->decl
= NULL_TREE
;
3595 if (TREE_CODE (type
) == ARRAY_TYPE
)
3597 tree sz
= TYPE_SIZE (type
);
3598 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3603 || ! host_integerp (sz
, 1)
3604 || TREE_INT_CST_LOW (sz
) == 0
3606 || ! host_integerp (elsz
, 1)
3607 || TREE_INT_CST_LOW (elsz
) == 0)
3610 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3611 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3614 for (i
= 0; i
< nr
; ++i
)
3620 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3621 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3624 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3626 else if (!(pushed
= push_fields_onto_fieldstack
3627 (TREE_TYPE (type
), fieldstack
,
3628 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
)))
3629 /* Empty structures may have actual size, like in C++. So
3630 see if we didn't push any subfields and the size is
3631 nonzero, push the field onto the stack */
3638 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3639 pair
->type
= TREE_TYPE (type
);
3641 pair
->decl
= NULL_TREE
;
3642 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3652 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3653 if (TREE_CODE (field
) == FIELD_DECL
)
3659 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3660 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3663 if (!var_can_have_subvars (field
))
3665 else if (!(pushed
= push_fields_onto_fieldstack
3666 (TREE_TYPE (field
), fieldstack
,
3667 offset
+ bitpos_of_field (field
), has_union
))
3668 && DECL_SIZE (field
)
3669 && !integer_zerop (DECL_SIZE (field
)))
3670 /* Empty structures may have actual size, like in C++. So
3671 see if we didn't push any subfields and the size is
3672 nonzero, push the field onto the stack */
3679 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3680 pair
->type
= TREE_TYPE (field
);
3681 pair
->size
= DECL_SIZE (field
);
3683 pair
->offset
= offset
+ bitpos_of_field (field
);
3694 make_constraint_to_anything (varinfo_t vi
)
3696 struct constraint_expr lhs
, rhs
;
3702 rhs
.var
= anything_id
;
3704 rhs
.type
= ADDRESSOF
;
3705 process_constraint (new_constraint (lhs
, rhs
));
3708 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3709 if it is a varargs function. */
3712 count_num_arguments (tree decl
, bool *is_varargs
)
3717 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3721 if (TREE_VALUE (t
) == void_type_node
)
3731 /* Creation function node for DECL, using NAME, and return the index
3732 of the variable we've created for the function. */
3735 create_function_info_for (tree decl
, const char *name
)
3737 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3741 bool is_varargs
= false;
3743 /* Create the variable info. */
3745 vi
= new_var_info (decl
, index
, name
, index
);
3750 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3751 insert_id_for_tree (vi
->decl
, index
);
3752 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3756 /* If it's varargs, we don't know how many arguments it has, so we
3763 vi
->is_unknown_size_var
= true;
3768 arg
= DECL_ARGUMENTS (decl
);
3770 /* Set up variables for each argument. */
3771 for (i
= 1; i
< vi
->fullsize
; i
++)
3774 const char *newname
;
3776 unsigned int newindex
;
3777 tree argdecl
= decl
;
3782 newindex
= VEC_length (varinfo_t
, varmap
);
3783 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3784 newname
= ggc_strdup (tempname
);
3787 argvi
= new_var_info (argdecl
, newindex
,newname
, newindex
);
3788 argvi
->decl
= argdecl
;
3789 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3792 argvi
->fullsize
= vi
->fullsize
;
3793 argvi
->has_union
= false;
3794 insert_into_field_list (vi
, argvi
);
3795 stats
.total_vars
++;
3798 insert_id_for_tree (arg
, newindex
);
3799 arg
= TREE_CHAIN (arg
);
3803 /* Create a variable for the return var. */
3804 if (DECL_RESULT (decl
) != NULL
3805 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3808 const char *newname
;
3810 unsigned int newindex
;
3811 tree resultdecl
= decl
;
3816 if (DECL_RESULT (decl
))
3817 resultdecl
= DECL_RESULT (decl
);
3819 newindex
= VEC_length (varinfo_t
, varmap
);
3820 asprintf (&tempname
, "%s.result", name
);
3821 newname
= ggc_strdup (tempname
);
3824 resultvi
= new_var_info (resultdecl
, newindex
, newname
, newindex
);
3825 resultvi
->decl
= resultdecl
;
3826 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3827 resultvi
->offset
= i
;
3829 resultvi
->fullsize
= vi
->fullsize
;
3830 resultvi
->has_union
= false;
3831 insert_into_field_list (vi
, resultvi
);
3832 stats
.total_vars
++;
3833 if (DECL_RESULT (decl
))
3834 insert_id_for_tree (DECL_RESULT (decl
), newindex
);
3840 /* Return true if FIELDSTACK contains fields that overlap.
3841 FIELDSTACK is assumed to be sorted by offset. */
3844 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3846 fieldoff_s
*fo
= NULL
;
3848 HOST_WIDE_INT lastoffset
= -1;
3850 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3852 if (fo
->offset
== lastoffset
)
3854 lastoffset
= fo
->offset
;
3859 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3860 This will also create any varinfo structures necessary for fields
3864 create_variable_info_for (tree decl
, const char *name
)
3866 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3868 tree
decltype = TREE_TYPE (decl
);
3869 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
3870 bool notokay
= false;
3872 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
3873 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
3875 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
3876 return create_function_info_for (decl
, name
);
3878 hasunion
= TREE_CODE (decltype) == UNION_TYPE
3879 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
3880 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
3882 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
3885 VEC_free (fieldoff_s
, heap
, fieldstack
);
3891 /* If the variable doesn't have subvars, we may end up needing to
3892 sort the field list and create fake variables for all the
3894 vi
= new_var_info (decl
, index
, name
, index
);
3897 vi
->has_union
= hasunion
;
3899 || TREE_CODE (declsize
) != INTEGER_CST
3900 || TREE_CODE (decltype) == UNION_TYPE
3901 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
3903 vi
->is_unknown_size_var
= true;
3909 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
3910 vi
->size
= vi
->fullsize
;
3913 insert_id_for_tree (vi
->decl
, index
);
3914 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3915 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3916 make_constraint_to_anything (vi
);
3919 if (use_field_sensitive
3921 && !vi
->is_unknown_size_var
3922 && var_can_have_subvars (decl
))
3924 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
3925 fieldoff_s
*fo
= NULL
;
3928 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3931 || TREE_CODE (fo
->size
) != INTEGER_CST
3939 /* We can't sort them if we have a field with a variable sized type,
3940 which will make notokay = true. In that case, we are going to return
3941 without creating varinfos for the fields anyway, so sorting them is a
3945 sort_fieldstack (fieldstack
);
3946 /* Due to some C++ FE issues, like PR 22488, we might end up
3947 what appear to be overlapping fields even though they,
3948 in reality, do not overlap. Until the C++ FE is fixed,
3949 we will simply disable field-sensitivity for these cases. */
3950 notokay
= check_for_overlaps (fieldstack
);
3954 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
3955 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
3957 if (fo
== NULL
|| notokay
)
3959 vi
->is_unknown_size_var
= 1;
3962 VEC_free (fieldoff_s
, heap
, fieldstack
);
3966 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
3967 vi
->offset
= fo
->offset
;
3968 for (i
= 1; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3971 const char *newname
;
3974 newindex
= VEC_length (varinfo_t
, varmap
);
3976 asprintf (&tempname
, "%s.%s", vi
->name
, alias_get_name (fo
->decl
));
3978 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
, vi
->name
, fo
->offset
);
3979 newname
= ggc_strdup (tempname
);
3981 newvi
= new_var_info (decl
, newindex
, newname
, newindex
);
3982 newvi
->offset
= fo
->offset
;
3983 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
3984 newvi
->fullsize
= vi
->fullsize
;
3985 insert_into_field_list (vi
, newvi
);
3986 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
3987 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3988 make_constraint_to_anything (newvi
);
3992 VEC_free (fieldoff_s
, heap
, fieldstack
);
3997 /* Print out the points-to solution for VAR to FILE. */
4000 dump_solution_for_var (FILE *file
, unsigned int var
)
4002 varinfo_t vi
= get_varinfo (var
);
4006 fprintf (file
, "%s = { ", vi
->name
);
4007 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi
->node
)->solution
, 0, i
, bi
)
4009 fprintf (file
, "%s ", get_varinfo (i
)->name
);
4011 fprintf (file
, "}\n");
4014 /* Print the points-to solution for VAR to stdout. */
4017 debug_solution_for_var (unsigned int var
)
4019 dump_solution_for_var (stdout
, var
);
4023 /* Create varinfo structures for all of the variables in the
4024 function for intraprocedural mode. */
4027 intra_create_variable_infos (void)
4031 /* For each incoming argument arg, ARG = &ANYTHING or a dummy variable if
4032 flag_argument_noalias > 1. */
4033 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
4035 struct constraint_expr lhs
;
4040 lhs
.var
= create_variable_info_for (t
, alias_get_name (t
));
4042 /* With flag_argument_noalias greater than one means that the incomming
4043 argument cannot alias anything except for itself so create a HEAP
4045 if (POINTER_TYPE_P (TREE_TYPE (t
))
4046 && flag_argument_noalias
> 1)
4049 struct constraint_expr rhs
;
4050 tree heapvar
= heapvar_lookup (t
);
4052 if (heapvar
== NULL_TREE
)
4054 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)), "PARM_NOALIAS");
4055 DECL_EXTERNAL (heapvar
) = 1;
4056 add_referenced_tmp_var (heapvar
);
4057 heapvar_insert (t
, heapvar
);
4059 id
= create_variable_info_for (heapvar
,
4060 alias_get_name (heapvar
));
4061 vi
= get_varinfo (id
);
4062 vi
->is_artificial_var
= 1;
4063 vi
->is_heap_var
= 1;
4065 rhs
.type
= ADDRESSOF
;
4067 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4069 struct constraint_expr temp
= lhs
;
4071 process_constraint (new_constraint (temp
, rhs
));
4075 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4076 make_constraint_to_anything (p
);
4080 /* Set bits in INTO corresponding to the variable uids in solution set
4084 set_uids_in_ptset (bitmap into
, bitmap from
)
4090 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
4092 varinfo_t vi
= get_varinfo (i
);
4094 /* The only artificial variables that are allowed in a may-alias
4095 set are heap variables. */
4096 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
4099 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
4101 /* Variables containing unions may need to be converted to
4102 their SFT's, because SFT's can have unions and we cannot. */
4103 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
4104 bitmap_set_bit (into
, DECL_UID (sv
->var
));
4106 else if (TREE_CODE (vi
->decl
) == VAR_DECL
4107 || TREE_CODE (vi
->decl
) == PARM_DECL
)
4109 if (var_can_have_subvars (vi
->decl
)
4110 && get_subvars_for_var (vi
->decl
))
4112 /* If VI->DECL is an aggregate for which we created
4113 SFTs, add the SFT corresponding to VI->OFFSET. */
4114 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
4116 bitmap_set_bit (into
, DECL_UID (sft
));
4120 /* Otherwise, just add VI->DECL to the alias set. */
4121 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4128 static bool have_alias_info
= false;
4130 /* Given a pointer variable P, fill in its points-to set, or return
4131 false if we can't. */
4134 find_what_p_points_to (tree p
)
4136 unsigned int id
= 0;
4139 if (!have_alias_info
)
4142 /* For parameters, get at the points-to set for the actual parm
4144 if (TREE_CODE (p
) == SSA_NAME
4145 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
4146 && default_def (SSA_NAME_VAR (p
)) == p
)
4147 lookup_p
= SSA_NAME_VAR (p
);
4149 if (lookup_id_for_tree (lookup_p
, &id
))
4151 varinfo_t vi
= get_varinfo (id
);
4153 if (vi
->is_artificial_var
)
4156 /* See if this is a field or a structure. */
4157 if (vi
->size
!= vi
->fullsize
)
4159 /* Nothing currently asks about structure fields directly,
4160 but when they do, we need code here to hand back the
4162 if (!var_can_have_subvars (vi
->decl
)
4163 || get_subvars_for_var (vi
->decl
) == NULL
)
4168 struct ptr_info_def
*pi
= get_ptr_info (p
);
4172 /* This variable may have been collapsed, let's get the real
4174 vi
= get_varinfo (vi
->node
);
4176 /* Translate artificial variables into SSA_NAME_PTR_INFO
4178 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4180 varinfo_t vi
= get_varinfo (i
);
4182 if (vi
->is_artificial_var
)
4184 /* FIXME. READONLY should be handled better so that
4185 flow insensitive aliasing can disregard writable
4187 if (vi
->id
== nothing_id
)
4189 else if (vi
->id
== anything_id
)
4190 pi
->pt_anything
= 1;
4191 else if (vi
->id
== readonly_id
)
4192 pi
->pt_anything
= 1;
4193 else if (vi
->id
== integer_id
)
4194 pi
->pt_anything
= 1;
4195 else if (vi
->is_heap_var
)
4196 pi
->pt_global_mem
= 1;
4200 if (pi
->pt_anything
)
4204 pi
->pt_vars
= BITMAP_GGC_ALLOC ();
4206 set_uids_in_ptset (pi
->pt_vars
, vi
->solution
);
4208 if (bitmap_empty_p (pi
->pt_vars
))
4220 /* Dump points-to information to OUTFILE. */
4223 dump_sa_points_to_info (FILE *outfile
)
4227 fprintf (outfile
, "\nPoints-to sets\n\n");
4229 if (dump_flags
& TDF_STATS
)
4231 fprintf (outfile
, "Stats:\n");
4232 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4233 fprintf (outfile
, "Statically unified vars: %d\n",
4234 stats
.unified_vars_static
);
4235 fprintf (outfile
, "Collapsed vars: %d\n", stats
.collapsed_vars
);
4236 fprintf (outfile
, "Dynamically unified vars: %d\n",
4237 stats
.unified_vars_dynamic
);
4238 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4239 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4242 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4243 dump_solution_for_var (outfile
, i
);
4247 /* Debug points-to information to stderr. */
4250 debug_sa_points_to_info (void)
4252 dump_sa_points_to_info (stderr
);
4256 /* Initialize the always-existing constraint variables for NULL
4257 ANYTHING, READONLY, and INTEGER */
4260 init_base_vars (void)
4262 struct constraint_expr lhs
, rhs
;
4264 /* Create the NULL variable, used to represent that a variable points
4266 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4267 var_nothing
= new_var_info (nothing_tree
, 0, "NULL", 0);
4268 insert_id_for_tree (nothing_tree
, 0);
4269 var_nothing
->is_artificial_var
= 1;
4270 var_nothing
->offset
= 0;
4271 var_nothing
->size
= ~0;
4272 var_nothing
->fullsize
= ~0;
4273 var_nothing
->is_special_var
= 1;
4275 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4277 /* Create the ANYTHING variable, used to represent that a variable
4278 points to some unknown piece of memory. */
4279 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4280 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING", 1);
4281 insert_id_for_tree (anything_tree
, 1);
4282 var_anything
->is_artificial_var
= 1;
4283 var_anything
->size
= ~0;
4284 var_anything
->offset
= 0;
4285 var_anything
->next
= NULL
;
4286 var_anything
->fullsize
= ~0;
4287 var_anything
->is_special_var
= 1;
4290 /* Anything points to anything. This makes deref constraints just
4291 work in the presence of linked list and other p = *p type loops,
4292 by saying that *ANYTHING = ANYTHING. */
4293 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4295 lhs
.var
= anything_id
;
4297 rhs
.type
= ADDRESSOF
;
4298 rhs
.var
= anything_id
;
4300 var_anything
->address_taken
= true;
4302 /* This specifically does not use process_constraint because
4303 process_constraint ignores all anything = anything constraints, since all
4304 but this one are redundant. */
4305 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4307 /* Create the READONLY variable, used to represent that a variable
4308 points to readonly memory. */
4309 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4310 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY", 2);
4311 var_readonly
->is_artificial_var
= 1;
4312 var_readonly
->offset
= 0;
4313 var_readonly
->size
= ~0;
4314 var_readonly
->fullsize
= ~0;
4315 var_readonly
->next
= NULL
;
4316 var_readonly
->is_special_var
= 1;
4317 insert_id_for_tree (readonly_tree
, 2);
4319 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4321 /* readonly memory points to anything, in order to make deref
4322 easier. In reality, it points to anything the particular
4323 readonly variable can point to, but we don't track this
4326 lhs
.var
= readonly_id
;
4328 rhs
.type
= ADDRESSOF
;
4329 rhs
.var
= anything_id
;
4332 process_constraint (new_constraint (lhs
, rhs
));
4334 /* Create the INTEGER variable, used to represent that a variable points
4336 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4337 var_integer
= new_var_info (integer_tree
, 3, "INTEGER", 3);
4338 insert_id_for_tree (integer_tree
, 3);
4339 var_integer
->is_artificial_var
= 1;
4340 var_integer
->size
= ~0;
4341 var_integer
->fullsize
= ~0;
4342 var_integer
->offset
= 0;
4343 var_integer
->next
= NULL
;
4344 var_integer
->is_special_var
= 1;
4346 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4348 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
4349 integer will point to. */
4351 lhs
.var
= integer_id
;
4353 rhs
.type
= ADDRESSOF
;
4354 rhs
.var
= anything_id
;
4356 process_constraint (new_constraint (lhs
, rhs
));
4359 /* Return true if we actually need to solve the constraint graph in order to
4360 get our points-to sets. This is false when, for example, no addresses are
4361 taken other than special vars, or all points-to sets with members already
4362 contain the anything variable and there are no predecessors for other
4366 need_to_solve (void)
4370 bool found_address_taken
= false;
4371 bool found_non_anything
= false;
4373 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4375 if (v
->is_special_var
)
4378 if (v
->address_taken
)
4379 found_address_taken
= true;
4382 && !bitmap_empty_p (v
->solution
)
4383 && !bitmap_bit_p (v
->solution
, anything_id
))
4384 found_non_anything
= true;
4385 else if (bitmap_empty_p (v
->solution
)
4386 && (VEC_length (constraint_edge_t
, graph
->preds
[v
->id
]) != 0
4387 || (graph
->zero_weight_preds
[v
->id
] && !bitmap_empty_p (graph
->zero_weight_preds
[v
->id
]))))
4388 found_non_anything
= true;
4390 if (found_address_taken
&& found_non_anything
)
4397 /* Initialize things necessary to perform PTA */
4400 init_alias_vars (void)
4402 bitmap_obstack_initialize (&ptabitmap_obstack
);
4403 bitmap_obstack_initialize (&predbitmap_obstack
);
4405 constraint_pool
= create_alloc_pool ("Constraint pool",
4406 sizeof (struct constraint
), 30);
4407 variable_info_pool
= create_alloc_pool ("Variable info pool",
4408 sizeof (struct variable_info
), 30);
4409 constraint_edge_pool
= create_alloc_pool ("Constraint edges",
4410 sizeof (struct constraint_edge
), 30);
4412 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4413 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4414 id_for_tree
= htab_create (10, tree_id_hash
, tree_id_eq
, free
);
4415 memset (&stats
, 0, sizeof (stats
));
4421 /* Create points-to sets for the current function. See the comments
4422 at the start of the file for an algorithmic overview. */
4425 compute_points_to_sets (struct alias_info
*ai
)
4429 timevar_push (TV_TREE_PTA
);
4433 intra_create_variable_infos ();
4435 /* Now walk all statements and derive aliases. */
4438 block_stmt_iterator bsi
;
4441 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4443 if (is_gimple_reg (PHI_RESULT (phi
)))
4445 find_func_aliases (phi
);
4446 /* Update various related attributes like escaped
4447 addresses, pointer dereferences for loads and stores.
4448 This is used when creating name tags and alias
4450 update_alias_info (phi
, ai
);
4454 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4456 tree stmt
= bsi_stmt (bsi
);
4457 find_func_aliases (stmt
);
4458 /* Update various related attributes like escaped
4459 addresses, pointer dereferences for loads and stores.
4460 This is used when creating name tags and alias
4462 update_alias_info (stmt
, ai
);
4466 build_constraint_graph ();
4470 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4471 dump_constraints (dump_file
);
4474 if (need_to_solve ())
4478 "\nCollapsing static cycles and doing variable "
4481 find_and_collapse_graph_cycles (graph
, false);
4482 perform_var_substitution (graph
);
4485 fprintf (dump_file
, "\nSolving graph:\n");
4487 solve_graph (graph
);
4491 dump_sa_points_to_info (dump_file
);
4493 have_alias_info
= true;
4495 timevar_pop (TV_TREE_PTA
);
4499 /* Delete created points-to sets. */
4502 delete_points_to_sets (void)
4507 htab_delete (id_for_tree
);
4508 bitmap_obstack_release (&ptabitmap_obstack
);
4509 bitmap_obstack_release (&predbitmap_obstack
);
4510 VEC_free (constraint_t
, heap
, constraints
);
4512 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4514 VEC_free (constraint_edge_t
, heap
, graph
->succs
[i
]);
4515 VEC_free (constraint_edge_t
, heap
, graph
->preds
[i
]);
4516 VEC_free (constraint_t
, heap
, v
->complex);
4518 free (graph
->zero_weight_preds
);
4519 free (graph
->zero_weight_succs
);
4520 free (graph
->succs
);
4521 free (graph
->preds
);
4524 VEC_free (varinfo_t
, heap
, varmap
);
4525 free_alloc_pool (variable_info_pool
);
4526 free_alloc_pool (constraint_pool
);
4527 free_alloc_pool (constraint_edge_pool
);
4529 have_alias_info
= false;
4532 /* Return true if we should execute IPA PTA. */
4536 return (flag_unit_at_a_time
!= 0
4537 /* Don't bother doing anything if the program has errors. */
4538 && !(errorcount
|| sorrycount
));
4541 /* Execute the driver for IPA PTA. */
4543 ipa_pta_execute (void)
4545 struct cgraph_node
*node
;
4550 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4552 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
4556 varid
= create_function_info_for (node
->decl
,
4557 cgraph_node_name (node
));
4558 if (node
->local
.externally_visible
)
4560 varinfo_t fi
= get_varinfo (varid
);
4561 for (; fi
; fi
= fi
->next
)
4562 make_constraint_to_anything (fi
);
4566 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4568 if (node
->analyzed
&& cgraph_is_master_clone (node
))
4570 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
4572 tree old_func_decl
= current_function_decl
;
4575 "Generating constraints for %s\n",
4576 cgraph_node_name (node
));
4578 current_function_decl
= node
->decl
;
4580 FOR_EACH_BB_FN (bb
, cfun
)
4582 block_stmt_iterator bsi
;
4585 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4587 if (is_gimple_reg (PHI_RESULT (phi
)))
4589 find_func_aliases (phi
);
4593 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4595 tree stmt
= bsi_stmt (bsi
);
4596 find_func_aliases (stmt
);
4599 current_function_decl
= old_func_decl
;
4604 /* Make point to anything. */
4608 build_constraint_graph ();
4612 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4613 dump_constraints (dump_file
);
4616 if (need_to_solve ())
4620 "\nCollapsing static cycles and doing variable "
4623 find_and_collapse_graph_cycles (graph
, false);
4624 perform_var_substitution (graph
);
4627 fprintf (dump_file
, "\nSolving graph:\n");
4629 solve_graph (graph
);
4633 dump_sa_points_to_info (dump_file
);
4637 struct tree_opt_pass pass_ipa_pta
=
4640 gate_ipa_pta
, /* gate */
4641 ipa_pta_execute
, /* execute */
4644 0, /* static_pass_number */
4645 TV_IPA_PTA
, /* tv_id */
4646 0, /* properties_required */
4647 0, /* properties_provided */
4648 0, /* properties_destroyed */
4649 0, /* todo_flags_start */
4650 0, /* todo_flags_finish */
4654 /* Initialize the heapvar for statement mapping. */
4656 init_alias_heapvars (void)
4658 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
, NULL
);
4662 delete_alias_heapvars (void)
4664 htab_delete (heapvar_for_stmt
);
4668 #include "gt-tree-ssa-structalias.h"