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
= xmalloc (sizeof (struct constraint_graph
));
1184 graph
->succs
= xcalloc (VEC_length (varinfo_t
, varmap
) + 1,
1185 sizeof (*graph
->succs
));
1186 graph
->preds
= xcalloc (VEC_length (varinfo_t
, varmap
) + 1,
1187 sizeof (*graph
->preds
));
1188 graph
->zero_weight_succs
= xcalloc (VEC_length (varinfo_t
, varmap
) + 1,
1189 sizeof (*graph
->zero_weight_succs
));
1190 graph
->zero_weight_preds
= xcalloc (VEC_length (varinfo_t
, varmap
) + 1,
1191 sizeof (*graph
->zero_weight_preds
));
1193 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
1195 struct constraint_expr lhs
= c
->lhs
;
1196 struct constraint_expr rhs
= c
->rhs
;
1197 unsigned int lhsvar
= get_varinfo_fc (lhs
.var
)->id
;
1198 unsigned int rhsvar
= get_varinfo_fc (rhs
.var
)->id
;
1200 if (lhs
.type
== DEREF
)
1202 /* *x = y or *x = &y (complex) */
1203 if (rhs
.type
== ADDRESSOF
|| rhsvar
> anything_id
)
1204 insert_into_complex (lhsvar
, c
);
1206 else if (rhs
.type
== DEREF
)
1208 /* !special var= *y */
1209 if (!(get_varinfo (lhsvar
)->is_special_var
))
1210 insert_into_complex (rhsvar
, c
);
1212 else if (rhs
.type
== ADDRESSOF
)
1215 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
1217 else if (lhsvar
> anything_id
)
1219 /* Ignore 0 weighted self edges, as they can't possibly contribute
1221 if (lhsvar
!= rhsvar
|| rhs
.offset
!= 0 || lhs
.offset
!= 0)
1223 /* x = y (simple) */
1224 int_add_graph_edge (graph
, lhs
.var
, rhs
.var
, rhs
.offset
);
1232 /* Changed variables on the last iteration. */
1233 static unsigned int changed_count
;
1234 static sbitmap changed
;
1236 DEF_VEC_I(unsigned);
1237 DEF_VEC_ALLOC_I(unsigned,heap
);
1240 /* Strongly Connected Component visitation info. */
1245 sbitmap in_component
;
1247 unsigned int *visited_index
;
1248 VEC(unsigned,heap
) *scc_stack
;
1249 VEC(unsigned,heap
) *unification_queue
;
1253 /* Recursive routine to find strongly connected components in GRAPH.
1254 SI is the SCC info to store the information in, and N is the id of current
1255 graph node we are processing.
1257 This is Tarjan's strongly connected component finding algorithm, as
1258 modified by Nuutila to keep only non-root nodes on the stack.
1259 The algorithm can be found in "On finding the strongly connected
1260 connected components in a directed graph" by Esko Nuutila and Eljas
1261 Soisalon-Soininen, in Information Processing Letters volume 49,
1262 number 1, pages 9-14. */
1265 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
1270 gcc_assert (get_varinfo (n
)->node
== n
);
1271 SET_BIT (si
->visited
, n
);
1272 RESET_BIT (si
->in_component
, n
);
1273 si
->visited_index
[n
] = si
->current_index
++;
1275 /* Visit all the successors. */
1276 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[n
], 0, i
, bi
)
1279 if (!TEST_BIT (si
->visited
, w
))
1280 scc_visit (graph
, si
, w
);
1281 if (!TEST_BIT (si
->in_component
, w
))
1283 unsigned int t
= get_varinfo (w
)->node
;
1284 unsigned int nnode
= get_varinfo (n
)->node
;
1285 if (si
->visited_index
[t
] < si
->visited_index
[nnode
])
1286 get_varinfo (n
)->node
= t
;
1290 /* See if any components have been identified. */
1291 if (get_varinfo (n
)->node
== n
)
1293 unsigned int t
= si
->visited_index
[n
];
1294 SET_BIT (si
->in_component
, n
);
1295 while (VEC_length (unsigned, si
->scc_stack
) != 0
1296 && t
< si
->visited_index
[VEC_last (unsigned, si
->scc_stack
)])
1298 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
1299 get_varinfo (w
)->node
= n
;
1300 SET_BIT (si
->in_component
, w
);
1301 /* Mark this node for collapsing. */
1302 VEC_safe_push (unsigned, heap
, si
->unification_queue
, w
);
1306 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1310 /* Collapse two variables into one variable. */
1313 collapse_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
)
1315 bitmap tosol
, fromsol
;
1317 condense_varmap_nodes (to
, from
);
1318 tosol
= get_varinfo (to
)->solution
;
1319 fromsol
= get_varinfo (from
)->solution
;
1320 bitmap_ior_into (tosol
, fromsol
);
1321 merge_graph_nodes (graph
, to
, from
);
1323 if (valid_graph_edge (graph
, to
, to
))
1325 if (graph
->zero_weight_preds
[to
])
1327 bitmap_clear_bit (graph
->zero_weight_preds
[to
], to
);
1328 bitmap_clear_bit (graph
->zero_weight_succs
[to
], to
);
1330 if (valid_weighted_graph_edge (graph
, to
, to
))
1332 bitmap weights
= *(get_graph_weights (graph
, to
, to
));
1333 if (!weights
|| bitmap_empty_p (weights
))
1334 erase_graph_self_edge (graph
, to
);
1337 BITMAP_FREE (fromsol
);
1338 get_varinfo (to
)->address_taken
|= get_varinfo (from
)->address_taken
;
1339 get_varinfo (to
)->indirect_target
|= get_varinfo (from
)->indirect_target
;
1343 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1344 SI is the Strongly Connected Components information structure that tells us
1345 what components to unify.
1346 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1347 count should be updated to reflect the unification. */
1350 process_unification_queue (constraint_graph_t graph
, struct scc_info
*si
,
1351 bool update_changed
)
1354 bitmap tmp
= BITMAP_ALLOC (update_changed
? &iteration_obstack
: NULL
);
1357 /* We proceed as follows:
1359 For each component in the queue (components are delineated by
1360 when current_queue_element->node != next_queue_element->node):
1362 rep = representative node for component
1364 For each node (tounify) to be unified in the component,
1365 merge the solution for tounify into tmp bitmap
1367 clear solution for tounify
1369 merge edges from tounify into rep
1371 merge complex constraints from tounify into rep
1373 update changed count to note that tounify will never change
1376 Merge tmp into solution for rep, marking rep changed if this
1377 changed rep's solution.
1379 Delete any 0 weighted self-edges we now have for rep. */
1380 while (i
!= VEC_length (unsigned, si
->unification_queue
))
1382 unsigned int tounify
= VEC_index (unsigned, si
->unification_queue
, i
);
1383 unsigned int n
= get_varinfo (tounify
)->node
;
1385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1386 fprintf (dump_file
, "Unifying %s to %s\n",
1387 get_varinfo (tounify
)->name
,
1388 get_varinfo (n
)->name
);
1390 stats
.unified_vars_dynamic
++;
1392 stats
.unified_vars_static
++;
1393 bitmap_ior_into (tmp
, get_varinfo (tounify
)->solution
);
1394 merge_graph_nodes (graph
, n
, tounify
);
1395 condense_varmap_nodes (n
, tounify
);
1397 if (update_changed
&& TEST_BIT (changed
, tounify
))
1399 RESET_BIT (changed
, tounify
);
1400 if (!TEST_BIT (changed
, n
))
1401 SET_BIT (changed
, n
);
1404 gcc_assert (changed_count
> 0);
1409 bitmap_clear (get_varinfo (tounify
)->solution
);
1412 /* If we've either finished processing the entire queue, or
1413 finished processing all nodes for component n, update the solution for
1415 if (i
== VEC_length (unsigned, si
->unification_queue
)
1416 || get_varinfo (VEC_index (unsigned, si
->unification_queue
, i
))->node
!= n
)
1418 /* If the solution changes because of the merging, we need to mark
1419 the variable as changed. */
1420 if (bitmap_ior_into (get_varinfo (n
)->solution
, tmp
))
1422 if (update_changed
&& !TEST_BIT (changed
, n
))
1424 SET_BIT (changed
, n
);
1430 if (valid_graph_edge (graph
, n
, n
))
1432 if (graph
->zero_weight_succs
[n
])
1434 if (graph
->zero_weight_preds
[n
])
1435 bitmap_clear_bit (graph
->zero_weight_preds
[n
], n
);
1436 bitmap_clear_bit (graph
->zero_weight_succs
[n
], n
);
1438 if (valid_weighted_graph_edge (graph
, n
, n
))
1440 bitmap weights
= *(get_graph_weights (graph
, n
, n
));
1441 if (!weights
|| bitmap_empty_p (weights
))
1442 erase_graph_self_edge (graph
, n
);
1451 /* Information needed to compute the topological ordering of a graph. */
1455 /* sbitmap of visited nodes. */
1457 /* Array that stores the topological order of the graph, *in
1459 VEC(unsigned,heap
) *topo_order
;
1463 /* Initialize and return a topological info structure. */
1465 static struct topo_info
*
1466 init_topo_info (void)
1468 size_t size
= VEC_length (varinfo_t
, varmap
);
1469 struct topo_info
*ti
= xmalloc (sizeof (struct topo_info
));
1470 ti
->visited
= sbitmap_alloc (size
);
1471 sbitmap_zero (ti
->visited
);
1472 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1477 /* Free the topological sort info pointed to by TI. */
1480 free_topo_info (struct topo_info
*ti
)
1482 sbitmap_free (ti
->visited
);
1483 VEC_free (unsigned, heap
, ti
->topo_order
);
1487 /* Visit the graph in topological order, and store the order in the
1488 topo_info structure. */
1491 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1494 VEC(constraint_edge_t
,heap
) *succs
= graph
->succs
[n
];
1497 constraint_edge_t c
;
1501 SET_BIT (ti
->visited
, n
);
1502 if (VEC_length (constraint_edge_t
, succs
) != 0)
1504 temp
= BITMAP_ALLOC (&iteration_obstack
);
1505 if (graph
->zero_weight_succs
[n
])
1506 bitmap_ior_into (temp
, graph
->zero_weight_succs
[n
]);
1507 for (i
= 0; VEC_iterate (constraint_edge_t
, succs
, i
, c
); i
++)
1508 bitmap_set_bit (temp
, c
->dest
);
1511 temp
= graph
->zero_weight_succs
[n
];
1514 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, j
, bi
)
1516 if (!TEST_BIT (ti
->visited
, j
))
1517 topo_visit (graph
, ti
, j
);
1519 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1522 /* Return true if variable N + OFFSET is a legal field of N. */
1525 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1527 varinfo_t ninfo
= get_varinfo (n
);
1529 /* For things we've globbed to single variables, any offset into the
1530 variable acts like the entire variable, so that it becomes offset
1532 if (ninfo
->is_special_var
1533 || ninfo
->is_artificial_var
1534 || ninfo
->is_unknown_size_var
)
1539 return (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1542 #define DONT_PROPAGATE_WITH_ANYTHING 0
1544 /* Process a constraint C that represents *x = &y. */
1547 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1548 constraint_t c
, bitmap delta
)
1550 unsigned int rhs
= c
->rhs
.var
;
1554 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1555 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1557 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1558 if (type_safe (j
, &offset
) && !(get_varinfo (j
)->is_special_var
))
1560 /* *x != NULL && *x != ANYTHING*/
1564 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1566 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1570 sol
= get_varinfo (t
)->solution
;
1571 if (!bitmap_bit_p (sol
, rhs
))
1573 bitmap_set_bit (sol
, rhs
);
1574 if (!TEST_BIT (changed
, t
))
1576 SET_BIT (changed
, t
);
1581 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1582 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1587 /* Process a constraint C that represents x = *y, using DELTA as the
1588 starting solution. */
1591 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1594 unsigned int lhs
= get_varinfo (c
->lhs
.var
)->node
;
1596 bitmap sol
= get_varinfo (lhs
)->solution
;
1600 #if DONT_PROPAGATE_WITH_ANYTHING
1601 if (bitmap_bit_p (delta
, anything_id
))
1603 flag
= !bitmap_bit_p (sol
, anything_id
);
1605 bitmap_set_bit (sol
, anything_id
);
1609 /* For each variable j in delta (Sol(y)), add
1610 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1611 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1613 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1614 if (type_safe (j
, &roffset
))
1617 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1620 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1625 /* Adding edges from the special vars is pointless.
1626 They don't have sets that can change. */
1627 if (get_varinfo (t
) ->is_special_var
)
1628 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1629 else if (int_add_graph_edge (graph
, lhs
, t
, 0))
1630 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1632 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1633 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1636 #if DONT_PROPAGATE_WITH_ANYTHING
1639 /* If the LHS solution changed, mark the var as changed. */
1642 get_varinfo (lhs
)->solution
= sol
;
1643 if (!TEST_BIT (changed
, lhs
))
1645 SET_BIT (changed
, lhs
);
1651 /* Process a constraint C that represents *x = y. */
1654 do_ds_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1656 unsigned int rhs
= get_varinfo (c
->rhs
.var
)->node
;
1657 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1658 bitmap sol
= get_varinfo (rhs
)->solution
;
1662 #if DONT_PROPAGATE_WITH_ANYTHING
1663 if (bitmap_bit_p (sol
, anything_id
))
1665 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1667 varinfo_t jvi
= get_varinfo (j
);
1669 unsigned int loff
= c
->lhs
.offset
;
1670 unsigned HOST_WIDE_INT fieldoffset
= jvi
->offset
+ loff
;
1673 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1678 if (!bitmap_bit_p (get_varinfo (t
)->solution
, anything_id
))
1680 bitmap_set_bit (get_varinfo (t
)->solution
, anything_id
);
1681 if (!TEST_BIT (changed
, t
))
1683 SET_BIT (changed
, t
);
1692 /* For each member j of delta (Sol(x)), add an edge from y to j and
1693 union Sol(y) into Sol(j) */
1694 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1696 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1697 if (type_safe (j
, &loff
) && !(get_varinfo(j
)->is_special_var
))
1701 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1703 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1707 if (int_add_graph_edge (graph
, t
, rhs
, roff
))
1709 bitmap tmp
= get_varinfo (t
)->solution
;
1710 if (set_union_with_increment (tmp
, sol
, roff
))
1712 get_varinfo (t
)->solution
= tmp
;
1714 sol
= get_varinfo (rhs
)->solution
;
1715 if (!TEST_BIT (changed
, t
))
1717 SET_BIT (changed
, t
);
1723 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1724 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1728 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1729 constraint (IE *x = &y, x = *y, and *x = y). */
1732 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1734 if (c
->lhs
.type
== DEREF
)
1736 if (c
->rhs
.type
== ADDRESSOF
)
1739 do_da_constraint (graph
, c
, delta
);
1744 do_ds_constraint (graph
, c
, delta
);
1750 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1751 do_sd_constraint (graph
, c
, delta
);
1755 /* Initialize and return a new SCC info structure. */
1757 static struct scc_info
*
1758 init_scc_info (void)
1760 struct scc_info
*si
= xmalloc (sizeof (struct scc_info
));
1761 size_t size
= VEC_length (varinfo_t
, varmap
);
1763 si
->current_index
= 0;
1764 si
->visited
= sbitmap_alloc (size
);
1765 sbitmap_zero (si
->visited
);
1766 si
->in_component
= sbitmap_alloc (size
);
1767 sbitmap_ones (si
->in_component
);
1768 si
->visited_index
= xcalloc (sizeof (unsigned int), size
+ 1);
1769 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1770 si
->unification_queue
= VEC_alloc (unsigned, heap
, 1);
1774 /* Free an SCC info structure pointed to by SI */
1777 free_scc_info (struct scc_info
*si
)
1779 sbitmap_free (si
->visited
);
1780 sbitmap_free (si
->in_component
);
1781 free (si
->visited_index
);
1782 VEC_free (unsigned, heap
, si
->scc_stack
);
1783 VEC_free (unsigned, heap
, si
->unification_queue
);
1788 /* Find cycles in GRAPH that occur, using strongly connected components, and
1789 collapse the cycles into a single representative node. if UPDATE_CHANGED
1790 is true, then update the changed sbitmap to note those nodes whose
1791 solutions have changed as a result of collapsing. */
1794 find_and_collapse_graph_cycles (constraint_graph_t graph
, bool update_changed
)
1797 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1798 struct scc_info
*si
= init_scc_info ();
1800 for (i
= 0; i
!= size
; ++i
)
1801 if (!TEST_BIT (si
->visited
, i
) && get_varinfo (i
)->node
== i
)
1802 scc_visit (graph
, si
, i
);
1804 process_unification_queue (graph
, si
, update_changed
);
1808 /* Compute a topological ordering for GRAPH, and store the result in the
1809 topo_info structure TI. */
1812 compute_topo_order (constraint_graph_t graph
,
1813 struct topo_info
*ti
)
1816 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1818 for (i
= 0; i
!= size
; ++i
)
1819 if (!TEST_BIT (ti
->visited
, i
) && get_varinfo (i
)->node
== i
)
1820 topo_visit (graph
, ti
, i
);
1823 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1826 bitmap_other_than_zero_bit_set (bitmap b
)
1831 if (bitmap_empty_p (b
))
1833 EXECUTE_IF_SET_IN_BITMAP (b
, 1, i
, bi
)
1838 /* Perform offline variable substitution.
1840 This is a linear time way of identifying variables that must have
1841 equivalent points-to sets, including those caused by static cycles,
1842 and single entry subgraphs, in the constraint graph.
1844 The technique is described in "Off-line variable substitution for
1845 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1846 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1849 perform_var_substitution (constraint_graph_t graph
)
1851 struct topo_info
*ti
= init_topo_info ();
1853 bitmap_obstack_initialize (&iteration_obstack
);
1854 /* Compute the topological ordering of the graph, then visit each
1855 node in topological order. */
1856 compute_topo_order (graph
, ti
);
1858 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1860 unsigned int i
= VEC_pop (unsigned, ti
->topo_order
);
1862 varinfo_t vi
= get_varinfo (i
);
1863 bool okay_to_elim
= false;
1864 unsigned int root
= VEC_length (varinfo_t
, varmap
);
1865 VEC(constraint_edge_t
,heap
) *predvec
= graph
->preds
[i
];
1866 constraint_edge_t ce
= NULL
;
1871 /* We can't eliminate things whose address is taken, or which is
1872 the target of a dereference. */
1873 if (vi
->address_taken
|| vi
->indirect_target
)
1876 /* See if all predecessors of I are ripe for elimination */
1877 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_preds
[i
], 0, k
, bi
)
1880 w
= get_varinfo (k
)->node
;
1882 /* We can't eliminate the node if one of the predecessors is
1883 part of a different strongly connected component. */
1887 okay_to_elim
= true;
1891 okay_to_elim
= false;
1895 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1896 then Solution(i) is a subset of Solution (w), where w is a
1897 predecessor in the graph.
1898 Corollary: If all predecessors of i have the same
1899 points-to set, then i has that same points-to set as
1900 those predecessors. */
1901 tmp
= BITMAP_ALLOC (NULL
);
1902 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1903 get_varinfo (w
)->solution
);
1904 if (!bitmap_empty_p (tmp
))
1906 okay_to_elim
= false;
1915 VEC_iterate (constraint_edge_t
, predvec
, pred
, ce
);
1920 weight
= *(get_graph_weights (graph
, i
, ce
->dest
));
1922 /* We can't eliminate variables that have nonzero weighted
1923 edges between them. */
1924 if (weight
&& bitmap_other_than_zero_bit_set (weight
))
1926 okay_to_elim
= false;
1929 w
= get_varinfo (ce
->dest
)->node
;
1931 /* We can't eliminate the node if one of the predecessors is
1932 part of a different strongly connected component. */
1936 okay_to_elim
= true;
1940 okay_to_elim
= false;
1944 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1945 then Solution(i) is a subset of Solution (w), where w is a
1946 predecessor in the graph.
1947 Corollary: If all predecessors of i have the same
1948 points-to set, then i has that same points-to set as
1949 those predecessors. */
1950 tmp
= BITMAP_ALLOC (NULL
);
1951 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1952 get_varinfo (w
)->solution
);
1953 if (!bitmap_empty_p (tmp
))
1955 okay_to_elim
= false;
1962 /* See if the root is different than the original node.
1963 If so, we've found an equivalence. */
1964 if (root
!= get_varinfo (i
)->node
&& okay_to_elim
)
1966 /* Found an equivalence */
1967 get_varinfo (i
)->node
= root
;
1968 collapse_nodes (graph
, root
, i
);
1969 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1970 fprintf (dump_file
, "Collapsing %s into %s\n",
1971 get_varinfo (i
)->name
,
1972 get_varinfo (root
)->name
);
1973 stats
.collapsed_vars
++;
1977 bitmap_obstack_release (&iteration_obstack
);
1978 free_topo_info (ti
);
1981 /* Solve the constraint graph GRAPH using our worklist solver.
1982 This is based on the PW* family of solvers from the "Efficient Field
1983 Sensitive Pointer Analysis for C" paper.
1984 It works by iterating over all the graph nodes, processing the complex
1985 constraints and propagating the copy constraints, until everything stops
1986 changed. This corresponds to steps 6-8 in the solving list given above. */
1989 solve_graph (constraint_graph_t graph
)
1991 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1994 changed_count
= size
;
1995 changed
= sbitmap_alloc (size
);
1996 sbitmap_ones (changed
);
1998 /* The already collapsed/unreachable nodes will never change, so we
1999 need to account for them in changed_count. */
2000 for (i
= 0; i
< size
; i
++)
2001 if (get_varinfo (i
)->node
!= i
)
2004 while (changed_count
> 0)
2007 struct topo_info
*ti
= init_topo_info ();
2010 bitmap_obstack_initialize (&iteration_obstack
);
2014 /* We already did cycle elimination once, when we did
2015 variable substitution, so we don't need it again for the
2017 if (stats
.iterations
> 1)
2018 find_and_collapse_graph_cycles (graph
, true);
2023 compute_topo_order (graph
, ti
);
2025 while (VEC_length (unsigned, ti
->topo_order
) != 0)
2027 i
= VEC_pop (unsigned, ti
->topo_order
);
2028 gcc_assert (get_varinfo (i
)->node
== i
);
2030 /* If the node has changed, we need to process the
2031 complex constraints and outgoing edges again. */
2032 if (TEST_BIT (changed
, i
))
2036 constraint_edge_t e
= NULL
;
2039 VEC(constraint_t
,heap
) *complex = get_varinfo (i
)->complex;
2040 VEC(constraint_edge_t
,heap
) *succs
;
2042 RESET_BIT (changed
, i
);
2045 /* Process the complex constraints */
2046 solution
= get_varinfo (i
)->solution
;
2047 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
2048 do_complex_constraint (graph
, c
, solution
);
2050 /* Propagate solution to all successors. */
2051 succs
= graph
->succs
[i
];
2053 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->zero_weight_succs
[i
], 0, j
, bi
)
2055 bitmap tmp
= get_varinfo (j
)->solution
;
2058 flag
= set_union_with_increment (tmp
, solution
, 0);
2062 get_varinfo (j
)->solution
= tmp
;
2063 if (!TEST_BIT (changed
, j
))
2065 SET_BIT (changed
, j
);
2070 for (j
= 0; VEC_iterate (constraint_edge_t
, succs
, j
, e
); j
++)
2072 bitmap tmp
= get_varinfo (e
->dest
)->solution
;
2075 bitmap weights
= e
->weights
;
2078 gcc_assert (weights
&& !bitmap_empty_p (weights
));
2079 EXECUTE_IF_SET_IN_BITMAP (weights
, 0, k
, bi
)
2080 flag
|= set_union_with_increment (tmp
, solution
, k
);
2084 get_varinfo (e
->dest
)->solution
= tmp
;
2085 if (!TEST_BIT (changed
, e
->dest
))
2087 SET_BIT (changed
, e
->dest
);
2094 free_topo_info (ti
);
2095 bitmap_obstack_release (&iteration_obstack
);
2098 sbitmap_free (changed
);
2102 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2104 /* Map from trees to variable ids. */
2105 static htab_t id_for_tree
;
2107 typedef struct tree_id
2113 /* Hash a tree id structure. */
2116 tree_id_hash (const void *p
)
2118 const tree_id_t ta
= (tree_id_t
) p
;
2119 return htab_hash_pointer (ta
->t
);
2122 /* Return true if the tree in P1 and the tree in P2 are the same. */
2125 tree_id_eq (const void *p1
, const void *p2
)
2127 const tree_id_t ta1
= (tree_id_t
) p1
;
2128 const tree_id_t ta2
= (tree_id_t
) p2
;
2129 return ta1
->t
== ta2
->t
;
2132 /* Insert ID as the variable id for tree T in the hashtable. */
2135 insert_id_for_tree (tree t
, int id
)
2138 struct tree_id finder
;
2142 slot
= htab_find_slot (id_for_tree
, &finder
, INSERT
);
2143 gcc_assert (*slot
== NULL
);
2144 new_pair
= xmalloc (sizeof (struct tree_id
));
2147 *slot
= (void *)new_pair
;
2150 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
2151 exist in the hash table, return false, otherwise, return true and
2152 set *ID to the id we found. */
2155 lookup_id_for_tree (tree t
, unsigned int *id
)
2158 struct tree_id finder
;
2161 pair
= htab_find (id_for_tree
, &finder
);
2168 /* Return a printable name for DECL */
2171 alias_get_name (tree decl
)
2173 const char *res
= get_name (decl
);
2175 int num_printed
= 0;
2181 if (TREE_CODE (decl
) == SSA_NAME
)
2183 num_printed
= asprintf (&temp
, "%s_%u",
2184 alias_get_name (SSA_NAME_VAR (decl
)),
2185 SSA_NAME_VERSION (decl
));
2187 else if (DECL_P (decl
))
2189 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
2191 if (num_printed
> 0)
2193 res
= ggc_strdup (temp
);
2199 /* Find the variable id for tree T in the hashtable.
2200 If T doesn't exist in the hash table, create an entry for it. */
2203 get_id_for_tree (tree t
)
2206 struct tree_id finder
;
2209 pair
= htab_find (id_for_tree
, &finder
);
2211 return create_variable_info_for (t
, alias_get_name (t
));
2216 /* Get a constraint expression from an SSA_VAR_P node. */
2218 static struct constraint_expr
2219 get_constraint_exp_from_ssa_var (tree t
)
2221 struct constraint_expr cexpr
;
2223 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
2225 /* For parameters, get at the points-to set for the actual parm
2227 if (TREE_CODE (t
) == SSA_NAME
2228 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
2229 && default_def (SSA_NAME_VAR (t
)) == t
)
2230 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
2232 cexpr
.type
= SCALAR
;
2234 cexpr
.var
= get_id_for_tree (t
);
2235 /* If we determine the result is "anything", and we know this is readonly,
2236 say it points to readonly memory instead. */
2237 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
2239 cexpr
.type
= ADDRESSOF
;
2240 cexpr
.var
= readonly_id
;
2247 /* Process a completed constraint T, and add it to the constraint
2251 process_constraint (constraint_t t
)
2253 struct constraint_expr rhs
= t
->rhs
;
2254 struct constraint_expr lhs
= t
->lhs
;
2256 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
2257 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
2259 /* ANYTHING == ANYTHING is pointless. */
2260 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
2263 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2264 else if (lhs
.var
== anything_id
&& lhs
.type
== ADDRESSOF
)
2269 process_constraint (t
);
2271 /* This can happen in our IR with things like n->a = *p */
2272 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
2274 /* Split into tmp = *rhs, *lhs = tmp */
2275 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
2276 tree pointertype
= TREE_TYPE (rhsdecl
);
2277 tree pointedtotype
= TREE_TYPE (pointertype
);
2278 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
2279 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2281 /* If this is an aggregate of known size, we should have passed
2282 this off to do_structure_copy, and it should have broken it
2284 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
2285 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
2287 process_constraint (new_constraint (tmplhs
, rhs
));
2288 process_constraint (new_constraint (lhs
, tmplhs
));
2290 else if (rhs
.type
== ADDRESSOF
)
2293 gcc_assert (rhs
.offset
== 0);
2295 for (vi
= get_varinfo (rhs
.var
); vi
!= NULL
; vi
= vi
->next
)
2296 vi
->address_taken
= true;
2298 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2302 if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2303 get_varinfo (lhs
.var
)->indirect_target
= true;
2304 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
2309 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2312 static unsigned HOST_WIDE_INT
2313 bitpos_of_field (const tree fdecl
)
2316 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
2317 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
2320 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
2321 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
2325 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2326 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2329 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
2330 const unsigned HOST_WIDE_INT fieldsize
,
2331 const unsigned HOST_WIDE_INT accesspos
,
2332 const unsigned HOST_WIDE_INT accesssize
)
2334 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
2336 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
2338 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
2344 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2347 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
)
2350 HOST_WIDE_INT bitsize
= -1;
2351 HOST_WIDE_INT bitmaxsize
= -1;
2352 HOST_WIDE_INT bitpos
;
2354 struct constraint_expr
*result
;
2355 unsigned int beforelength
= VEC_length (ce_s
, *results
);
2357 /* Some people like to do cute things like take the address of
2360 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
2361 forzero
= TREE_OPERAND (forzero
, 0);
2363 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
2365 struct constraint_expr temp
;
2368 temp
.var
= integer_id
;
2370 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2374 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
2375 get_constraint_for (t
, results
);
2376 result
= VEC_last (ce_s
, *results
);
2377 result
->offset
= bitpos
;
2379 gcc_assert (beforelength
+ 1 == VEC_length (ce_s
, *results
));
2381 /* This can also happen due to weird offsetof type macros. */
2382 if (TREE_CODE (t
) != ADDR_EXPR
&& result
->type
== ADDRESSOF
)
2383 result
->type
= SCALAR
;
2385 if (result
->type
== SCALAR
)
2387 /* In languages like C, you can access one past the end of an
2388 array. You aren't allowed to dereference it, so we can
2389 ignore this constraint. When we handle pointer subtraction,
2390 we may have to do something cute here. */
2392 if (result
->offset
< get_varinfo (result
->var
)->fullsize
)
2394 /* It's also not true that the constraint will actually start at the
2395 right offset, it may start in some padding. We only care about
2396 setting the constraint to the first actual field it touches, so
2399 for (curr
= get_varinfo (result
->var
); curr
; curr
= curr
->next
)
2401 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2402 result
->offset
, bitmaxsize
))
2404 result
->var
= curr
->id
;
2408 /* assert that we found *some* field there. The user couldn't be
2409 accessing *only* padding. */
2410 /* Still the user could access one past the end of an array
2411 embedded in a struct resulting in accessing *only* padding. */
2412 gcc_assert (curr
|| ref_contains_array_ref (orig_t
));
2415 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2416 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2423 /* Dereference the constraint expression CONS, and return the result.
2424 DEREF (ADDRESSOF) = SCALAR
2425 DEREF (SCALAR) = DEREF
2426 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2427 This is needed so that we can handle dereferencing DEREF constraints. */
2430 do_deref (VEC (ce_s
, heap
) **constraints
)
2432 struct constraint_expr
*c
;
2434 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
2436 if (c
->type
== SCALAR
)
2438 else if (c
->type
== ADDRESSOF
)
2440 else if (c
->type
== DEREF
)
2442 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "dereftmp");
2443 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2444 process_constraint (new_constraint (tmplhs
, *c
));
2445 c
->var
= tmplhs
.var
;
2453 /* Given a tree T, return the constraint expression for it. */
2456 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
2458 struct constraint_expr temp
;
2460 /* x = integer is all glommed to a single variable, which doesn't
2461 point to anything by itself. That is, of course, unless it is an
2462 integer constant being treated as a pointer, in which case, we
2463 will return that this is really the addressof anything. This
2464 happens below, since it will fall into the default case. The only
2465 case we know something about an integer treated like a pointer is
2466 when it is the NULL pointer, and then we just say it points to
2468 if (TREE_CODE (t
) == INTEGER_CST
2469 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2471 temp
.var
= integer_id
;
2474 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2477 else if (TREE_CODE (t
) == INTEGER_CST
2478 && integer_zerop (t
))
2480 temp
.var
= nothing_id
;
2481 temp
.type
= ADDRESSOF
;
2483 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2487 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2489 case tcc_expression
:
2491 switch (TREE_CODE (t
))
2495 struct constraint_expr
*c
;
2497 tree exp
= TREE_OPERAND (t
, 0);
2499 get_constraint_for (exp
, results
);
2500 /* Make sure we capture constraints to all elements
2502 if ((handled_component_p (exp
)
2503 && ref_contains_array_ref (exp
))
2504 || TREE_CODE (TREE_TYPE (exp
)) == ARRAY_TYPE
)
2506 struct constraint_expr
*origrhs
;
2508 struct constraint_expr tmp
;
2510 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2511 origrhs
= VEC_last (ce_s
, *results
);
2513 VEC_pop (ce_s
, *results
);
2514 origvar
= get_varinfo (origrhs
->var
);
2515 for (; origvar
; origvar
= origvar
->next
)
2517 tmp
.var
= origvar
->id
;
2518 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2521 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
2523 if (c
->type
== DEREF
)
2526 c
->type
= ADDRESSOF
;
2533 /* XXX: In interprocedural mode, if we didn't have the
2534 body, we would need to do *each pointer argument =
2536 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2539 tree heapvar
= heapvar_lookup (t
);
2541 if (heapvar
== NULL
)
2543 heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2544 DECL_EXTERNAL (heapvar
) = 1;
2545 add_referenced_tmp_var (heapvar
);
2546 heapvar_insert (t
, heapvar
);
2549 temp
.var
= create_variable_info_for (heapvar
,
2550 alias_get_name (heapvar
));
2552 vi
= get_varinfo (temp
.var
);
2553 vi
->is_artificial_var
= 1;
2554 vi
->is_heap_var
= 1;
2555 temp
.type
= ADDRESSOF
;
2557 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2563 temp
.type
= ADDRESSOF
;
2564 temp
.var
= anything_id
;
2566 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2573 switch (TREE_CODE (t
))
2577 get_constraint_for (TREE_OPERAND (t
, 0), results
);
2582 case ARRAY_RANGE_REF
:
2584 get_constraint_for_component_ref (t
, results
);
2588 temp
.type
= ADDRESSOF
;
2589 temp
.var
= anything_id
;
2591 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2598 switch (TREE_CODE (t
))
2602 case NON_LVALUE_EXPR
:
2604 tree op
= TREE_OPERAND (t
, 0);
2606 /* Cast from non-pointer to pointers are bad news for us.
2607 Anything else, we see through */
2608 if (!(POINTER_TYPE_P (TREE_TYPE (t
))
2609 && ! POINTER_TYPE_P (TREE_TYPE (op
))))
2611 get_constraint_for (op
, results
);
2619 temp
.type
= ADDRESSOF
;
2620 temp
.var
= anything_id
;
2622 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2627 case tcc_exceptional
:
2629 switch (TREE_CODE (t
))
2633 get_constraint_for (PHI_RESULT (t
), results
);
2639 struct constraint_expr temp
;
2640 temp
= get_constraint_exp_from_ssa_var (t
);
2641 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2647 temp
.type
= ADDRESSOF
;
2648 temp
.var
= anything_id
;
2650 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2655 case tcc_declaration
:
2657 struct constraint_expr temp
;
2658 temp
= get_constraint_exp_from_ssa_var (t
);
2659 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2664 temp
.type
= ADDRESSOF
;
2665 temp
.var
= anything_id
;
2667 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2674 /* Handle the structure copy case where we have a simple structure copy
2675 between LHS and RHS that is of SIZE (in bits)
2677 For each field of the lhs variable (lhsfield)
2678 For each field of the rhs variable at lhsfield.offset (rhsfield)
2679 add the constraint lhsfield = rhsfield
2681 If we fail due to some kind of type unsafety or other thing we
2682 can't handle, return false. We expect the caller to collapse the
2683 variable in that case. */
2686 do_simple_structure_copy (const struct constraint_expr lhs
,
2687 const struct constraint_expr rhs
,
2688 const unsigned HOST_WIDE_INT size
)
2690 varinfo_t p
= get_varinfo (lhs
.var
);
2691 unsigned HOST_WIDE_INT pstart
, last
;
2693 last
= p
->offset
+ size
;
2694 for (; p
&& p
->offset
< last
; p
= p
->next
)
2697 struct constraint_expr templhs
= lhs
;
2698 struct constraint_expr temprhs
= rhs
;
2699 unsigned HOST_WIDE_INT fieldoffset
;
2701 templhs
.var
= p
->id
;
2702 q
= get_varinfo (temprhs
.var
);
2703 fieldoffset
= p
->offset
- pstart
;
2704 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2707 temprhs
.var
= q
->id
;
2708 process_constraint (new_constraint (templhs
, temprhs
));
2714 /* Handle the structure copy case where we have a structure copy between a
2715 aggregate on the LHS and a dereference of a pointer on the RHS
2716 that is of SIZE (in bits)
2718 For each field of the lhs variable (lhsfield)
2719 rhs.offset = lhsfield->offset
2720 add the constraint lhsfield = rhs
2724 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2725 const struct constraint_expr rhs
,
2726 const unsigned HOST_WIDE_INT size
)
2728 varinfo_t p
= get_varinfo (lhs
.var
);
2729 unsigned HOST_WIDE_INT pstart
,last
;
2731 last
= p
->offset
+ size
;
2733 for (; p
&& p
->offset
< last
; p
= p
->next
)
2736 struct constraint_expr templhs
= lhs
;
2737 struct constraint_expr temprhs
= rhs
;
2738 unsigned HOST_WIDE_INT fieldoffset
;
2741 if (templhs
.type
== SCALAR
)
2742 templhs
.var
= p
->id
;
2744 templhs
.offset
= p
->offset
;
2746 q
= get_varinfo (temprhs
.var
);
2747 fieldoffset
= p
->offset
- pstart
;
2748 temprhs
.offset
+= fieldoffset
;
2749 process_constraint (new_constraint (templhs
, temprhs
));
2753 /* Handle the structure copy case where we have a structure copy
2754 between a aggregate on the RHS and a dereference of a pointer on
2755 the LHS that is of SIZE (in bits)
2757 For each field of the rhs variable (rhsfield)
2758 lhs.offset = rhsfield->offset
2759 add the constraint lhs = rhsfield
2763 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2764 const struct constraint_expr rhs
,
2765 const unsigned HOST_WIDE_INT size
)
2767 varinfo_t p
= get_varinfo (rhs
.var
);
2768 unsigned HOST_WIDE_INT pstart
,last
;
2770 last
= p
->offset
+ size
;
2772 for (; p
&& p
->offset
< last
; p
= p
->next
)
2775 struct constraint_expr templhs
= lhs
;
2776 struct constraint_expr temprhs
= rhs
;
2777 unsigned HOST_WIDE_INT fieldoffset
;
2780 if (temprhs
.type
== SCALAR
)
2781 temprhs
.var
= p
->id
;
2783 temprhs
.offset
= p
->offset
;
2785 q
= get_varinfo (templhs
.var
);
2786 fieldoffset
= p
->offset
- pstart
;
2787 templhs
.offset
+= fieldoffset
;
2788 process_constraint (new_constraint (templhs
, temprhs
));
2792 /* Sometimes, frontends like to give us bad type information. This
2793 function will collapse all the fields from VAR to the end of VAR,
2794 into VAR, so that we treat those fields as a single variable.
2795 We return the variable they were collapsed into. */
2798 collapse_rest_of_var (unsigned int var
)
2800 varinfo_t currvar
= get_varinfo (var
);
2803 for (field
= currvar
->next
; field
; field
= field
->next
)
2806 fprintf (dump_file
, "Type safety: Collapsing var %s into %s\n",
2807 field
->name
, currvar
->name
);
2809 gcc_assert (!field
->collapsed_to
);
2810 field
->collapsed_to
= currvar
;
2813 currvar
->next
= NULL
;
2814 currvar
->size
= currvar
->fullsize
- currvar
->offset
;
2819 /* Handle aggregate copies by expanding into copies of the respective
2820 fields of the structures. */
2823 do_structure_copy (tree lhsop
, tree rhsop
)
2825 struct constraint_expr lhs
, rhs
, tmp
;
2826 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
2828 unsigned HOST_WIDE_INT lhssize
;
2829 unsigned HOST_WIDE_INT rhssize
;
2831 get_constraint_for (lhsop
, &lhsc
);
2832 get_constraint_for (rhsop
, &rhsc
);
2833 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
2834 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
2835 lhs
= *(VEC_last (ce_s
, lhsc
));
2836 rhs
= *(VEC_last (ce_s
, rhsc
));
2838 VEC_free (ce_s
, heap
, lhsc
);
2839 VEC_free (ce_s
, heap
, rhsc
);
2841 /* If we have special var = x, swap it around. */
2842 if (lhs
.var
<= integer_id
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2849 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2850 possible it's something we could handle. However, most cases falling
2851 into this are dealing with transparent unions, which are slightly
2853 if (rhs
.type
== ADDRESSOF
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2855 rhs
.type
= ADDRESSOF
;
2856 rhs
.var
= anything_id
;
2859 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2860 that special var. */
2861 if (rhs
.var
<= integer_id
)
2863 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2865 struct constraint_expr templhs
= lhs
;
2866 struct constraint_expr temprhs
= rhs
;
2868 if (templhs
.type
== SCALAR
)
2869 templhs
.var
= p
->id
;
2871 templhs
.offset
+= p
->offset
;
2872 process_constraint (new_constraint (templhs
, temprhs
));
2877 tree rhstype
= TREE_TYPE (rhsop
);
2878 tree lhstype
= TREE_TYPE (lhsop
);
2882 lhstypesize
= DECL_P (lhsop
) ? DECL_SIZE (lhsop
) : TYPE_SIZE (lhstype
);
2883 rhstypesize
= DECL_P (rhsop
) ? DECL_SIZE (rhsop
) : TYPE_SIZE (rhstype
);
2885 /* If we have a variably sized types on the rhs or lhs, and a deref
2886 constraint, add the constraint, lhsconstraint = &ANYTHING.
2887 This is conservatively correct because either the lhs is an unknown
2888 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2889 constraint, and every variable it can point to must be unknown sized
2890 anyway, so we don't need to worry about fields at all. */
2891 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
2892 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
2894 rhs
.var
= anything_id
;
2895 rhs
.type
= ADDRESSOF
;
2897 process_constraint (new_constraint (lhs
, rhs
));
2901 /* The size only really matters insofar as we don't set more or less of
2902 the variable. If we hit an unknown size var, the size should be the
2903 whole darn thing. */
2904 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
2907 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
2909 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
2912 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
2915 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
2917 if (!do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
)))
2919 lhs
.var
= collapse_rest_of_var (lhs
.var
);
2920 rhs
.var
= collapse_rest_of_var (rhs
.var
);
2925 process_constraint (new_constraint (lhs
, rhs
));
2928 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2929 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2930 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
2931 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2934 tree pointedtotype
= lhstype
;
2937 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
2938 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
2939 do_structure_copy (tmpvar
, rhsop
);
2940 do_structure_copy (lhsop
, tmpvar
);
2945 /* Update related alias information kept in AI. This is used when
2946 building name tags, alias sets and deciding grouping heuristics.
2947 STMT is the statement to process. This function also updates
2948 ADDRESSABLE_VARS. */
2951 update_alias_info (tree stmt
, struct alias_info
*ai
)
2954 use_operand_p use_p
;
2956 enum escape_type stmt_escape_type
= is_escape_site (stmt
, ai
);
2959 /* Mark all the variables whose address are taken by the statement. */
2960 addr_taken
= addresses_taken (stmt
);
2963 bitmap_ior_into (addressable_vars
, addr_taken
);
2965 /* If STMT is an escape point, all the addresses taken by it are
2967 if (stmt_escape_type
!= NO_ESCAPE
)
2972 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
2974 tree rvar
= referenced_var (i
);
2975 if (!unmodifiable_var_p (rvar
))
2976 mark_call_clobbered (rvar
, stmt_escape_type
);
2981 /* Process each operand use. If an operand may be aliased, keep
2982 track of how many times it's being used. For pointers, determine
2983 whether they are dereferenced by the statement, or whether their
2984 value escapes, etc. */
2985 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2989 struct ptr_info_def
*pi
;
2990 bool is_store
, is_potential_deref
;
2991 unsigned num_uses
, num_derefs
;
2993 op
= USE_FROM_PTR (use_p
);
2995 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2996 to the set of addressable variables. */
2997 if (TREE_CODE (op
) == ADDR_EXPR
)
2999 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
);
3001 /* PHI nodes don't have annotations for pinning the set
3002 of addresses taken, so we collect them here.
3004 FIXME, should we allow PHI nodes to have annotations
3005 so that they can be treated like regular statements?
3006 Currently, they are treated as second-class
3008 add_to_addressable_set (TREE_OPERAND (op
, 0), &addressable_vars
);
3012 /* Ignore constants. */
3013 if (TREE_CODE (op
) != SSA_NAME
)
3016 var
= SSA_NAME_VAR (op
);
3017 v_ann
= var_ann (var
);
3019 /* The base variable of an ssa name must be a GIMPLE register, and thus
3020 it cannot be aliased. */
3021 gcc_assert (!may_be_aliased (var
));
3023 /* We are only interested in pointers. */
3024 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
3027 pi
= get_ptr_info (op
);
3029 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3030 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
)))
3032 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
));
3033 VARRAY_PUSH_TREE (ai
->processed_ptrs
, op
);
3036 /* If STMT is a PHI node, then it will not have pointer
3037 dereferences and it will not be an escape point. */
3038 if (TREE_CODE (stmt
) == PHI_NODE
)
3041 /* Determine whether OP is a dereferenced pointer, and if STMT
3042 is an escape point, whether OP escapes. */
3043 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
3045 /* Handle a corner case involving address expressions of the
3046 form '&PTR->FLD'. The problem with these expressions is that
3047 they do not represent a dereference of PTR. However, if some
3048 other transformation propagates them into an INDIRECT_REF
3049 expression, we end up with '*(&PTR->FLD)' which is folded
3052 So, if the original code had no other dereferences of PTR,
3053 the aliaser will not create memory tags for it, and when
3054 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3055 memory operations will receive no V_MAY_DEF/VUSE operands.
3057 One solution would be to have count_uses_and_derefs consider
3058 &PTR->FLD a dereference of PTR. But that is wrong, since it
3059 is not really a dereference but an offset calculation.
3061 What we do here is to recognize these special ADDR_EXPR
3062 nodes. Since these expressions are never GIMPLE values (they
3063 are not GIMPLE invariants), they can only appear on the RHS
3064 of an assignment and their base address is always an
3065 INDIRECT_REF expression. */
3066 is_potential_deref
= false;
3067 if (TREE_CODE (stmt
) == MODIFY_EXPR
3068 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ADDR_EXPR
3069 && !is_gimple_val (TREE_OPERAND (stmt
, 1)))
3071 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3072 this represents a potential dereference of PTR. */
3073 tree rhs
= TREE_OPERAND (stmt
, 1);
3074 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
3075 if (TREE_CODE (base
) == INDIRECT_REF
3076 && TREE_OPERAND (base
, 0) == op
)
3077 is_potential_deref
= true;
3080 if (num_derefs
> 0 || is_potential_deref
)
3082 /* Mark OP as dereferenced. In a subsequent pass,
3083 dereferenced pointers that point to a set of
3084 variables will be assigned a name tag to alias
3085 all the variables OP points to. */
3086 pi
->is_dereferenced
= 1;
3088 /* Keep track of how many time we've dereferenced each
3090 NUM_REFERENCES_INC (v_ann
);
3092 /* If this is a store operation, mark OP as being
3093 dereferenced to store, otherwise mark it as being
3094 dereferenced to load. */
3096 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
3098 bitmap_set_bit (ai
->dereferenced_ptrs_load
, DECL_UID (var
));
3101 if (stmt_escape_type
!= NO_ESCAPE
&& num_derefs
< num_uses
)
3103 /* If STMT is an escape point and STMT contains at
3104 least one direct use of OP, then the value of OP
3105 escapes and so the pointed-to variables need to
3106 be marked call-clobbered. */
3107 pi
->value_escapes_p
= 1;
3108 pi
->escape_mask
|= stmt_escape_type
;
3110 /* If the statement makes a function call, assume
3111 that pointer OP will be dereferenced in a store
3112 operation inside the called function. */
3113 if (get_call_expr_in (stmt
))
3115 bitmap_set_bit (ai
->dereferenced_ptrs_store
, DECL_UID (var
));
3116 pi
->is_dereferenced
= 1;
3121 if (TREE_CODE (stmt
) == PHI_NODE
)
3124 /* Update reference counter for definitions to any
3125 potentially aliased variable. This is used in the alias
3126 grouping heuristics. */
3127 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
3129 tree var
= SSA_NAME_VAR (op
);
3130 var_ann_t ann
= var_ann (var
);
3131 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
3132 if (may_be_aliased (var
))
3133 NUM_REFERENCES_INC (ann
);
3137 /* Mark variables in V_MAY_DEF operands as being written to. */
3138 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
3140 tree var
= DECL_P (op
) ? op
: SSA_NAME_VAR (op
);
3141 bitmap_set_bit (ai
->written_vars
, DECL_UID (var
));
3146 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3147 Expressions of the type PTR + CST can be handled in two ways:
3149 1- If the constraint for PTR is ADDRESSOF for a non-structure
3150 variable, then we can use it directly because adding or
3151 subtracting a constant may not alter the original ADDRESSOF
3152 constraint (i.e., pointer arithmetic may not legally go outside
3153 an object's boundaries).
3155 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3156 then if CST is a compile-time constant that can be used as an
3157 offset, we can determine which sub-variable will be pointed-to
3160 Return true if the expression is handled. For any other kind of
3161 expression, return false so that each operand can be added as a
3162 separate constraint by the caller. */
3165 handle_ptr_arith (VEC (ce_s
, heap
) *lhsc
, tree expr
)
3168 struct constraint_expr
*c
, *c2
;
3171 VEC (ce_s
, heap
) *temp
= NULL
;
3172 unsigned int rhsoffset
= 0;
3174 if (TREE_CODE (expr
) != PLUS_EXPR
)
3177 op0
= TREE_OPERAND (expr
, 0);
3178 op1
= TREE_OPERAND (expr
, 1);
3180 get_constraint_for (op0
, &temp
);
3181 if (POINTER_TYPE_P (TREE_TYPE (op0
))
3182 && TREE_CODE (op1
) == INTEGER_CST
)
3184 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
3188 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
3189 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
3191 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
3193 varinfo_t temp
= get_varinfo (c2
->var
);
3195 /* An access one after the end of an array is valid,
3196 so simply punt on accesses we cannot resolve. */
3197 temp
= first_vi_for_offset (temp
, rhsoffset
);
3204 c2
->offset
= rhsoffset
;
3205 process_constraint (new_constraint (*c
, *c2
));
3208 VEC_free (ce_s
, heap
, temp
);
3214 /* Walk statement T setting up aliasing constraints according to the
3215 references found in T. This function is the main part of the
3216 constraint builder. AI points to auxiliary alias information used
3217 when building alias sets and computing alias grouping heuristics. */
3220 find_func_aliases (tree origt
)
3223 VEC(ce_s
, heap
) *lhsc
= NULL
;
3224 VEC(ce_s
, heap
) *rhsc
= NULL
;
3225 struct constraint_expr
*c
;
3227 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
3228 t
= TREE_OPERAND (t
, 0);
3230 /* Now build constraints expressions. */
3231 if (TREE_CODE (t
) == PHI_NODE
)
3233 /* Only care about pointers and structures containing
3235 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t
)))
3236 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))))
3241 /* For a phi node, assign all the arguments to
3243 get_constraint_for (PHI_RESULT (t
), &lhsc
);
3244 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
3246 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
3247 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3249 struct constraint_expr
*c2
;
3250 while (VEC_length (ce_s
, rhsc
) > 0)
3252 c2
= VEC_last (ce_s
, rhsc
);
3253 process_constraint (new_constraint (*c
, *c2
));
3254 VEC_pop (ce_s
, rhsc
);
3260 /* In IPA mode, we need to generate constraints to pass call
3261 arguments through their calls. There are two case, either a
3262 modify_expr when we are returning a value, or just a plain
3263 call_expr when we are not. */
3264 else if (in_ipa_mode
3265 && ((TREE_CODE (t
) == MODIFY_EXPR
3266 && TREE_CODE (TREE_OPERAND (t
, 1)) == CALL_EXPR
3267 && !(call_expr_flags (TREE_OPERAND (t
, 1))
3268 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
3269 || (TREE_CODE (t
) == CALL_EXPR
3270 && !(call_expr_flags (t
)
3271 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
3281 if (TREE_CODE (t
) == MODIFY_EXPR
)
3283 lhsop
= TREE_OPERAND (t
, 0);
3284 rhsop
= TREE_OPERAND (t
, 1);
3291 decl
= get_callee_fndecl (rhsop
);
3293 /* If we can directly resolve the function being called, do so.
3294 Otherwise, it must be some sort of indirect expression that
3295 we should still be able to handle. */
3298 found
= lookup_id_for_tree (decl
, &varid
);
3303 decl
= TREE_OPERAND (rhsop
, 0);
3304 found
= lookup_id_for_tree (decl
, &varid
);
3308 /* Assign all the passed arguments to the appropriate incoming
3309 parameters of the function. */
3310 fi
= get_varinfo (varid
);
3311 arglist
= TREE_OPERAND (rhsop
, 1);
3313 for (;arglist
; arglist
= TREE_CHAIN (arglist
))
3315 tree arg
= TREE_VALUE (arglist
);
3316 struct constraint_expr lhs
;
3317 struct constraint_expr
*rhsp
;
3319 get_constraint_for (arg
, &rhsc
);
3320 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3329 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3332 while (VEC_length (ce_s
, rhsc
) != 0)
3334 rhsp
= VEC_last (ce_s
, rhsc
);
3335 process_constraint (new_constraint (lhs
, *rhsp
));
3336 VEC_pop (ce_s
, rhsc
);
3340 /* If we are returning a value, assign it to the result. */
3343 struct constraint_expr rhs
;
3344 struct constraint_expr
*lhsp
;
3347 get_constraint_for (lhsop
, &lhsc
);
3348 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3357 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3360 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3361 process_constraint (new_constraint (*lhsp
, rhs
));
3364 /* Otherwise, just a regular assignment statement. */
3365 else if (TREE_CODE (t
) == MODIFY_EXPR
)
3367 tree lhsop
= TREE_OPERAND (t
, 0);
3368 tree rhsop
= TREE_OPERAND (t
, 1);
3371 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3372 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop
)))
3374 do_structure_copy (lhsop
, rhsop
);
3378 /* Only care about operations with pointers, structures
3379 containing pointers, dereferences, and call expressions. */
3380 if (POINTER_TYPE_P (TREE_TYPE (lhsop
))
3381 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3382 || TREE_CODE (rhsop
) == CALL_EXPR
)
3384 get_constraint_for (lhsop
, &lhsc
);
3385 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3387 /* RHS that consist of unary operations,
3388 exceptional types, or bare decls/constants, get
3389 handled directly by get_constraint_for. */
3391 case tcc_declaration
:
3393 case tcc_exceptional
:
3394 case tcc_expression
:
3398 tree strippedrhs
= rhsop
;
3401 /* XXX: Push this back into the ADDR_EXPR
3402 case, and remove anyoffset handling. */
3403 STRIP_NOPS (strippedrhs
);
3404 rhstype
= TREE_TYPE (strippedrhs
);
3406 get_constraint_for (rhsop
, &rhsc
);
3407 if (TREE_CODE (strippedrhs
) == ADDR_EXPR
3408 && AGGREGATE_TYPE_P (TREE_TYPE (rhstype
))
3409 && VEC_length (ce_s
, rhsc
) == 1)
3411 struct constraint_expr
*origrhs
;
3413 struct constraint_expr tmp
;
3415 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
3416 origrhs
= VEC_last (ce_s
, rhsc
);
3418 VEC_pop (ce_s
, rhsc
);
3419 origvar
= get_varinfo (origrhs
->var
);
3420 for (; origvar
; origvar
= origvar
->next
)
3422 tmp
.var
= origvar
->id
;
3423 VEC_safe_push (ce_s
, heap
, rhsc
, &tmp
);
3427 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3429 struct constraint_expr
*c2
;
3432 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3433 process_constraint (new_constraint (*c
, *c2
));
3441 /* For pointer arithmetic of the form
3442 PTR + CST, we can simply use PTR's
3443 constraint because pointer arithmetic is
3444 not allowed to go out of bounds. */
3445 if (handle_ptr_arith (lhsc
, rhsop
))
3450 /* Otherwise, walk each operand. Notice that we
3451 can't use the operand interface because we need
3452 to process expressions other than simple operands
3453 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3455 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
3457 tree op
= TREE_OPERAND (rhsop
, i
);
3460 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3461 get_constraint_for (op
, &rhsc
);
3462 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3464 struct constraint_expr
*c2
;
3465 while (VEC_length (ce_s
, rhsc
) > 0)
3467 c2
= VEC_last (ce_s
, rhsc
);
3468 process_constraint (new_constraint (*c
, *c2
));
3469 VEC_pop (ce_s
, rhsc
);
3478 /* After promoting variables and computing aliasing we will
3479 need to re-scan most statements. FIXME: Try to minimize the
3480 number of statements re-scanned. It's not really necessary to
3481 re-scan *all* statements. */
3482 mark_stmt_modified (origt
);
3483 VEC_free (ce_s
, heap
, rhsc
);
3484 VEC_free (ce_s
, heap
, lhsc
);
3488 /* Find the first varinfo in the same variable as START that overlaps with
3490 Effectively, walk the chain of fields for the variable START to find the
3491 first field that overlaps with OFFSET.
3492 Return NULL if we can't find one. */
3495 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3497 varinfo_t curr
= start
;
3500 /* We may not find a variable in the field list with the actual
3501 offset when when we have glommed a structure to a variable.
3502 In that case, however, offset should still be within the size
3504 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3512 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3516 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3518 varinfo_t prev
= base
;
3519 varinfo_t curr
= base
->next
;
3530 if (field
->offset
<= curr
->offset
)
3535 field
->next
= prev
->next
;
3540 /* qsort comparison function for two fieldoff's PA and PB */
3543 fieldoff_compare (const void *pa
, const void *pb
)
3545 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3546 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3547 HOST_WIDE_INT foasize
, fobsize
;
3549 if (foa
->offset
!= fob
->offset
)
3550 return foa
->offset
- fob
->offset
;
3552 foasize
= TREE_INT_CST_LOW (foa
->size
);
3553 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3554 return foasize
- fobsize
;
3557 /* Sort a fieldstack according to the field offset and sizes. */
3558 void sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3560 qsort (VEC_address (fieldoff_s
, fieldstack
),
3561 VEC_length (fieldoff_s
, fieldstack
),
3562 sizeof (fieldoff_s
),
3566 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3567 of TYPE onto fieldstack, recording their offsets along the way.
3568 OFFSET is used to keep track of the offset in this entire structure, rather
3569 than just the immediately containing structure. Returns the number
3571 HAS_UNION is set to true if we find a union type as a field of
3575 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3576 HOST_WIDE_INT offset
, bool *has_union
)
3581 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3583 fieldoff_s
*real_part
, *img_part
;
3584 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3585 real_part
->type
= TREE_TYPE (type
);
3586 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3587 real_part
->offset
= offset
;
3588 real_part
->decl
= NULL_TREE
;
3590 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3591 img_part
->type
= TREE_TYPE (type
);
3592 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3593 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3594 img_part
->decl
= NULL_TREE
;
3599 if (TREE_CODE (type
) == ARRAY_TYPE
)
3601 tree sz
= TYPE_SIZE (type
);
3602 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3607 || ! host_integerp (sz
, 1)
3608 || TREE_INT_CST_LOW (sz
) == 0
3610 || ! host_integerp (elsz
, 1)
3611 || TREE_INT_CST_LOW (elsz
) == 0)
3614 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3615 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3618 for (i
= 0; i
< nr
; ++i
)
3624 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3625 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3628 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3630 else if (!(pushed
= push_fields_onto_fieldstack
3631 (TREE_TYPE (type
), fieldstack
,
3632 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
)))
3633 /* Empty structures may have actual size, like in C++. So
3634 see if we didn't push any subfields and the size is
3635 nonzero, push the field onto the stack */
3642 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3643 pair
->type
= TREE_TYPE (type
);
3645 pair
->decl
= NULL_TREE
;
3646 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3656 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3657 if (TREE_CODE (field
) == FIELD_DECL
)
3663 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3664 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3667 if (!var_can_have_subvars (field
))
3669 else if (!(pushed
= push_fields_onto_fieldstack
3670 (TREE_TYPE (field
), fieldstack
,
3671 offset
+ bitpos_of_field (field
), has_union
))
3672 && DECL_SIZE (field
)
3673 && !integer_zerop (DECL_SIZE (field
)))
3674 /* Empty structures may have actual size, like in C++. So
3675 see if we didn't push any subfields and the size is
3676 nonzero, push the field onto the stack */
3683 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3684 pair
->type
= TREE_TYPE (field
);
3685 pair
->size
= DECL_SIZE (field
);
3687 pair
->offset
= offset
+ bitpos_of_field (field
);
3698 make_constraint_to_anything (varinfo_t vi
)
3700 struct constraint_expr lhs
, rhs
;
3706 rhs
.var
= anything_id
;
3708 rhs
.type
= ADDRESSOF
;
3709 process_constraint (new_constraint (lhs
, rhs
));
3712 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3713 if it is a varargs function. */
3716 count_num_arguments (tree decl
, bool *is_varargs
)
3721 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3725 if (TREE_VALUE (t
) == void_type_node
)
3735 /* Creation function node for DECL, using NAME, and return the index
3736 of the variable we've created for the function. */
3739 create_function_info_for (tree decl
, const char *name
)
3741 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3745 bool is_varargs
= false;
3747 /* Create the variable info. */
3749 vi
= new_var_info (decl
, index
, name
, index
);
3754 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3755 insert_id_for_tree (vi
->decl
, index
);
3756 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3760 /* If it's varargs, we don't know how many arguments it has, so we
3767 vi
->is_unknown_size_var
= true;
3772 arg
= DECL_ARGUMENTS (decl
);
3774 /* Set up variables for each argument. */
3775 for (i
= 1; i
< vi
->fullsize
; i
++)
3778 const char *newname
;
3780 unsigned int newindex
;
3781 tree argdecl
= decl
;
3786 newindex
= VEC_length (varinfo_t
, varmap
);
3787 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3788 newname
= ggc_strdup (tempname
);
3791 argvi
= new_var_info (argdecl
, newindex
,newname
, newindex
);
3792 argvi
->decl
= argdecl
;
3793 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3796 argvi
->fullsize
= vi
->fullsize
;
3797 argvi
->has_union
= false;
3798 insert_into_field_list (vi
, argvi
);
3799 stats
.total_vars
++;
3802 insert_id_for_tree (arg
, newindex
);
3803 arg
= TREE_CHAIN (arg
);
3807 /* Create a variable for the return var. */
3808 if (DECL_RESULT (decl
) != NULL
3809 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3812 const char *newname
;
3814 unsigned int newindex
;
3815 tree resultdecl
= decl
;
3820 if (DECL_RESULT (decl
))
3821 resultdecl
= DECL_RESULT (decl
);
3823 newindex
= VEC_length (varinfo_t
, varmap
);
3824 asprintf (&tempname
, "%s.result", name
);
3825 newname
= ggc_strdup (tempname
);
3828 resultvi
= new_var_info (resultdecl
, newindex
, newname
, newindex
);
3829 resultvi
->decl
= resultdecl
;
3830 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3831 resultvi
->offset
= i
;
3833 resultvi
->fullsize
= vi
->fullsize
;
3834 resultvi
->has_union
= false;
3835 insert_into_field_list (vi
, resultvi
);
3836 stats
.total_vars
++;
3837 if (DECL_RESULT (decl
))
3838 insert_id_for_tree (DECL_RESULT (decl
), newindex
);
3844 /* Return true if FIELDSTACK contains fields that overlap.
3845 FIELDSTACK is assumed to be sorted by offset. */
3848 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3850 fieldoff_s
*fo
= NULL
;
3852 HOST_WIDE_INT lastoffset
= -1;
3854 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3856 if (fo
->offset
== lastoffset
)
3858 lastoffset
= fo
->offset
;
3863 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3864 This will also create any varinfo structures necessary for fields
3868 create_variable_info_for (tree decl
, const char *name
)
3870 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3872 tree
decltype = TREE_TYPE (decl
);
3873 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
3874 bool notokay
= false;
3876 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
3877 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
3879 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
3880 return create_function_info_for (decl
, name
);
3882 hasunion
= TREE_CODE (decltype) == UNION_TYPE
3883 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
3884 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
3886 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
3889 VEC_free (fieldoff_s
, heap
, fieldstack
);
3895 /* If the variable doesn't have subvars, we may end up needing to
3896 sort the field list and create fake variables for all the
3898 vi
= new_var_info (decl
, index
, name
, index
);
3901 vi
->has_union
= hasunion
;
3903 || TREE_CODE (declsize
) != INTEGER_CST
3904 || TREE_CODE (decltype) == UNION_TYPE
3905 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
3907 vi
->is_unknown_size_var
= true;
3913 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
3914 vi
->size
= vi
->fullsize
;
3917 insert_id_for_tree (vi
->decl
, index
);
3918 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3919 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3920 make_constraint_to_anything (vi
);
3923 if (use_field_sensitive
3925 && !vi
->is_unknown_size_var
3926 && var_can_have_subvars (decl
))
3928 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
3929 fieldoff_s
*fo
= NULL
;
3932 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3935 || TREE_CODE (fo
->size
) != INTEGER_CST
3943 /* We can't sort them if we have a field with a variable sized type,
3944 which will make notokay = true. In that case, we are going to return
3945 without creating varinfos for the fields anyway, so sorting them is a
3949 sort_fieldstack (fieldstack
);
3950 /* Due to some C++ FE issues, like PR 22488, we might end up
3951 what appear to be overlapping fields even though they,
3952 in reality, do not overlap. Until the C++ FE is fixed,
3953 we will simply disable field-sensitivity for these cases. */
3954 notokay
= check_for_overlaps (fieldstack
);
3958 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
3959 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
3961 if (fo
== NULL
|| notokay
)
3963 vi
->is_unknown_size_var
= 1;
3966 VEC_free (fieldoff_s
, heap
, fieldstack
);
3970 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
3971 vi
->offset
= fo
->offset
;
3972 for (i
= 1; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3975 const char *newname
;
3978 newindex
= VEC_length (varinfo_t
, varmap
);
3980 asprintf (&tempname
, "%s.%s", vi
->name
, alias_get_name (fo
->decl
));
3982 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
, vi
->name
, fo
->offset
);
3983 newname
= ggc_strdup (tempname
);
3985 newvi
= new_var_info (decl
, newindex
, newname
, newindex
);
3986 newvi
->offset
= fo
->offset
;
3987 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
3988 newvi
->fullsize
= vi
->fullsize
;
3989 insert_into_field_list (vi
, newvi
);
3990 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
3991 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3992 make_constraint_to_anything (newvi
);
3996 VEC_free (fieldoff_s
, heap
, fieldstack
);
4001 /* Print out the points-to solution for VAR to FILE. */
4004 dump_solution_for_var (FILE *file
, unsigned int var
)
4006 varinfo_t vi
= get_varinfo (var
);
4010 fprintf (file
, "%s = { ", vi
->name
);
4011 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi
->node
)->solution
, 0, i
, bi
)
4013 fprintf (file
, "%s ", get_varinfo (i
)->name
);
4015 fprintf (file
, "}\n");
4018 /* Print the points-to solution for VAR to stdout. */
4021 debug_solution_for_var (unsigned int var
)
4023 dump_solution_for_var (stdout
, var
);
4027 /* Create varinfo structures for all of the variables in the
4028 function for intraprocedural mode. */
4031 intra_create_variable_infos (void)
4035 /* For each incoming argument arg, ARG = &ANYTHING or a dummy variable if
4036 flag_argument_noalias > 1. */
4037 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
4039 struct constraint_expr lhs
;
4044 lhs
.var
= create_variable_info_for (t
, alias_get_name (t
));
4046 /* With flag_argument_noalias greater than one means that the incomming
4047 argument cannot alias anything except for itself so create a HEAP
4049 if (POINTER_TYPE_P (TREE_TYPE (t
))
4050 && flag_argument_noalias
> 1)
4053 struct constraint_expr rhs
;
4054 tree heapvar
= heapvar_lookup (t
);
4056 if (heapvar
== NULL_TREE
)
4058 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)), "PARM_NOALIAS");
4059 DECL_EXTERNAL (heapvar
) = 1;
4060 add_referenced_tmp_var (heapvar
);
4061 heapvar_insert (t
, heapvar
);
4063 id
= create_variable_info_for (heapvar
,
4064 alias_get_name (heapvar
));
4065 vi
= get_varinfo (id
);
4066 vi
->is_artificial_var
= 1;
4067 vi
->is_heap_var
= 1;
4069 rhs
.type
= ADDRESSOF
;
4071 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4073 struct constraint_expr temp
= lhs
;
4075 process_constraint (new_constraint (temp
, rhs
));
4079 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
4080 make_constraint_to_anything (p
);
4084 /* Set bits in INTO corresponding to the variable uids in solution set
4088 set_uids_in_ptset (bitmap into
, bitmap from
)
4094 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
4096 varinfo_t vi
= get_varinfo (i
);
4098 /* The only artificial variables that are allowed in a may-alias
4099 set are heap variables. */
4100 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
4103 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
4105 /* Variables containing unions may need to be converted to
4106 their SFT's, because SFT's can have unions and we cannot. */
4107 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
4108 bitmap_set_bit (into
, DECL_UID (sv
->var
));
4110 else if (TREE_CODE (vi
->decl
) == VAR_DECL
4111 || TREE_CODE (vi
->decl
) == PARM_DECL
)
4113 if (var_can_have_subvars (vi
->decl
)
4114 && get_subvars_for_var (vi
->decl
))
4116 /* If VI->DECL is an aggregate for which we created
4117 SFTs, add the SFT corresponding to VI->OFFSET. */
4118 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
4120 bitmap_set_bit (into
, DECL_UID (sft
));
4124 /* Otherwise, just add VI->DECL to the alias set. */
4125 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
4132 static bool have_alias_info
= false;
4134 /* Given a pointer variable P, fill in its points-to set, or return
4135 false if we can't. */
4138 find_what_p_points_to (tree p
)
4140 unsigned int id
= 0;
4143 if (!have_alias_info
)
4146 /* For parameters, get at the points-to set for the actual parm
4148 if (TREE_CODE (p
) == SSA_NAME
4149 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
4150 && default_def (SSA_NAME_VAR (p
)) == p
)
4151 lookup_p
= SSA_NAME_VAR (p
);
4153 if (lookup_id_for_tree (lookup_p
, &id
))
4155 varinfo_t vi
= get_varinfo (id
);
4157 if (vi
->is_artificial_var
)
4160 /* See if this is a field or a structure. */
4161 if (vi
->size
!= vi
->fullsize
)
4163 /* Nothing currently asks about structure fields directly,
4164 but when they do, we need code here to hand back the
4166 if (!var_can_have_subvars (vi
->decl
)
4167 || get_subvars_for_var (vi
->decl
) == NULL
)
4172 struct ptr_info_def
*pi
= get_ptr_info (p
);
4176 /* This variable may have been collapsed, let's get the real
4178 vi
= get_varinfo (vi
->node
);
4180 /* Translate artificial variables into SSA_NAME_PTR_INFO
4182 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4184 varinfo_t vi
= get_varinfo (i
);
4186 if (vi
->is_artificial_var
)
4188 /* FIXME. READONLY should be handled better so that
4189 flow insensitive aliasing can disregard writable
4191 if (vi
->id
== nothing_id
)
4193 else if (vi
->id
== anything_id
)
4194 pi
->pt_anything
= 1;
4195 else if (vi
->id
== readonly_id
)
4196 pi
->pt_anything
= 1;
4197 else if (vi
->id
== integer_id
)
4198 pi
->pt_anything
= 1;
4199 else if (vi
->is_heap_var
)
4200 pi
->pt_global_mem
= 1;
4204 if (pi
->pt_anything
)
4208 pi
->pt_vars
= BITMAP_GGC_ALLOC ();
4210 set_uids_in_ptset (pi
->pt_vars
, vi
->solution
);
4212 if (bitmap_empty_p (pi
->pt_vars
))
4224 /* Dump points-to information to OUTFILE. */
4227 dump_sa_points_to_info (FILE *outfile
)
4231 fprintf (outfile
, "\nPoints-to sets\n\n");
4233 if (dump_flags
& TDF_STATS
)
4235 fprintf (outfile
, "Stats:\n");
4236 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4237 fprintf (outfile
, "Statically unified vars: %d\n",
4238 stats
.unified_vars_static
);
4239 fprintf (outfile
, "Collapsed vars: %d\n", stats
.collapsed_vars
);
4240 fprintf (outfile
, "Dynamically unified vars: %d\n",
4241 stats
.unified_vars_dynamic
);
4242 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4243 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4246 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4247 dump_solution_for_var (outfile
, i
);
4251 /* Debug points-to information to stderr. */
4254 debug_sa_points_to_info (void)
4256 dump_sa_points_to_info (stderr
);
4260 /* Initialize the always-existing constraint variables for NULL
4261 ANYTHING, READONLY, and INTEGER */
4264 init_base_vars (void)
4266 struct constraint_expr lhs
, rhs
;
4268 /* Create the NULL variable, used to represent that a variable points
4270 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4271 var_nothing
= new_var_info (nothing_tree
, 0, "NULL", 0);
4272 insert_id_for_tree (nothing_tree
, 0);
4273 var_nothing
->is_artificial_var
= 1;
4274 var_nothing
->offset
= 0;
4275 var_nothing
->size
= ~0;
4276 var_nothing
->fullsize
= ~0;
4277 var_nothing
->is_special_var
= 1;
4279 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4281 /* Create the ANYTHING variable, used to represent that a variable
4282 points to some unknown piece of memory. */
4283 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4284 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING", 1);
4285 insert_id_for_tree (anything_tree
, 1);
4286 var_anything
->is_artificial_var
= 1;
4287 var_anything
->size
= ~0;
4288 var_anything
->offset
= 0;
4289 var_anything
->next
= NULL
;
4290 var_anything
->fullsize
= ~0;
4291 var_anything
->is_special_var
= 1;
4294 /* Anything points to anything. This makes deref constraints just
4295 work in the presence of linked list and other p = *p type loops,
4296 by saying that *ANYTHING = ANYTHING. */
4297 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4299 lhs
.var
= anything_id
;
4301 rhs
.type
= ADDRESSOF
;
4302 rhs
.var
= anything_id
;
4304 var_anything
->address_taken
= true;
4306 /* This specifically does not use process_constraint because
4307 process_constraint ignores all anything = anything constraints, since all
4308 but this one are redundant. */
4309 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4311 /* Create the READONLY variable, used to represent that a variable
4312 points to readonly memory. */
4313 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4314 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY", 2);
4315 var_readonly
->is_artificial_var
= 1;
4316 var_readonly
->offset
= 0;
4317 var_readonly
->size
= ~0;
4318 var_readonly
->fullsize
= ~0;
4319 var_readonly
->next
= NULL
;
4320 var_readonly
->is_special_var
= 1;
4321 insert_id_for_tree (readonly_tree
, 2);
4323 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4325 /* readonly memory points to anything, in order to make deref
4326 easier. In reality, it points to anything the particular
4327 readonly variable can point to, but we don't track this
4330 lhs
.var
= readonly_id
;
4332 rhs
.type
= ADDRESSOF
;
4333 rhs
.var
= anything_id
;
4336 process_constraint (new_constraint (lhs
, rhs
));
4338 /* Create the INTEGER variable, used to represent that a variable points
4340 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4341 var_integer
= new_var_info (integer_tree
, 3, "INTEGER", 3);
4342 insert_id_for_tree (integer_tree
, 3);
4343 var_integer
->is_artificial_var
= 1;
4344 var_integer
->size
= ~0;
4345 var_integer
->fullsize
= ~0;
4346 var_integer
->offset
= 0;
4347 var_integer
->next
= NULL
;
4348 var_integer
->is_special_var
= 1;
4350 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4352 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
4353 integer will point to. */
4355 lhs
.var
= integer_id
;
4357 rhs
.type
= ADDRESSOF
;
4358 rhs
.var
= anything_id
;
4360 process_constraint (new_constraint (lhs
, rhs
));
4363 /* Return true if we actually need to solve the constraint graph in order to
4364 get our points-to sets. This is false when, for example, no addresses are
4365 taken other than special vars, or all points-to sets with members already
4366 contain the anything variable and there are no predecessors for other
4370 need_to_solve (void)
4374 bool found_address_taken
= false;
4375 bool found_non_anything
= false;
4377 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4379 if (v
->is_special_var
)
4382 if (v
->address_taken
)
4383 found_address_taken
= true;
4386 && !bitmap_empty_p (v
->solution
)
4387 && !bitmap_bit_p (v
->solution
, anything_id
))
4388 found_non_anything
= true;
4389 else if (bitmap_empty_p (v
->solution
)
4390 && (VEC_length (constraint_edge_t
, graph
->preds
[v
->id
]) != 0
4391 || (graph
->zero_weight_preds
[v
->id
] && !bitmap_empty_p (graph
->zero_weight_preds
[v
->id
]))))
4392 found_non_anything
= true;
4394 if (found_address_taken
&& found_non_anything
)
4401 /* Initialize things necessary to perform PTA */
4404 init_alias_vars (void)
4406 bitmap_obstack_initialize (&ptabitmap_obstack
);
4407 bitmap_obstack_initialize (&predbitmap_obstack
);
4409 constraint_pool
= create_alloc_pool ("Constraint pool",
4410 sizeof (struct constraint
), 30);
4411 variable_info_pool
= create_alloc_pool ("Variable info pool",
4412 sizeof (struct variable_info
), 30);
4413 constraint_edge_pool
= create_alloc_pool ("Constraint edges",
4414 sizeof (struct constraint_edge
), 30);
4416 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4417 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4418 id_for_tree
= htab_create (10, tree_id_hash
, tree_id_eq
, free
);
4419 memset (&stats
, 0, sizeof (stats
));
4425 /* Create points-to sets for the current function. See the comments
4426 at the start of the file for an algorithmic overview. */
4429 compute_points_to_sets (struct alias_info
*ai
)
4433 timevar_push (TV_TREE_PTA
);
4437 intra_create_variable_infos ();
4439 /* Now walk all statements and derive aliases. */
4442 block_stmt_iterator bsi
;
4445 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4447 if (is_gimple_reg (PHI_RESULT (phi
)))
4449 find_func_aliases (phi
);
4450 /* Update various related attributes like escaped
4451 addresses, pointer dereferences for loads and stores.
4452 This is used when creating name tags and alias
4454 update_alias_info (phi
, ai
);
4458 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4460 tree stmt
= bsi_stmt (bsi
);
4461 find_func_aliases (stmt
);
4462 /* Update various related attributes like escaped
4463 addresses, pointer dereferences for loads and stores.
4464 This is used when creating name tags and alias
4466 update_alias_info (stmt
, ai
);
4470 build_constraint_graph ();
4474 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4475 dump_constraints (dump_file
);
4478 if (need_to_solve ())
4482 "\nCollapsing static cycles and doing variable "
4485 find_and_collapse_graph_cycles (graph
, false);
4486 perform_var_substitution (graph
);
4489 fprintf (dump_file
, "\nSolving graph:\n");
4491 solve_graph (graph
);
4495 dump_sa_points_to_info (dump_file
);
4497 have_alias_info
= true;
4499 timevar_pop (TV_TREE_PTA
);
4503 /* Delete created points-to sets. */
4506 delete_points_to_sets (void)
4511 htab_delete (id_for_tree
);
4512 bitmap_obstack_release (&ptabitmap_obstack
);
4513 bitmap_obstack_release (&predbitmap_obstack
);
4514 VEC_free (constraint_t
, heap
, constraints
);
4516 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4518 VEC_free (constraint_edge_t
, heap
, graph
->succs
[i
]);
4519 VEC_free (constraint_edge_t
, heap
, graph
->preds
[i
]);
4520 VEC_free (constraint_t
, heap
, v
->complex);
4522 free (graph
->zero_weight_preds
);
4523 free (graph
->zero_weight_succs
);
4524 free (graph
->succs
);
4525 free (graph
->preds
);
4528 VEC_free (varinfo_t
, heap
, varmap
);
4529 free_alloc_pool (variable_info_pool
);
4530 free_alloc_pool (constraint_pool
);
4531 free_alloc_pool (constraint_edge_pool
);
4533 have_alias_info
= false;
4536 /* Return true if we should execute IPA PTA. */
4540 return (flag_unit_at_a_time
!= 0
4541 /* Don't bother doing anything if the program has errors. */
4542 && !(errorcount
|| sorrycount
));
4545 /* Execute the driver for IPA PTA. */
4547 ipa_pta_execute (void)
4549 struct cgraph_node
*node
;
4554 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4556 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
4560 varid
= create_function_info_for (node
->decl
,
4561 cgraph_node_name (node
));
4562 if (node
->local
.externally_visible
)
4564 varinfo_t fi
= get_varinfo (varid
);
4565 for (; fi
; fi
= fi
->next
)
4566 make_constraint_to_anything (fi
);
4570 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4572 if (node
->analyzed
&& cgraph_is_master_clone (node
))
4574 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
4576 tree old_func_decl
= current_function_decl
;
4579 "Generating constraints for %s\n",
4580 cgraph_node_name (node
));
4582 current_function_decl
= node
->decl
;
4584 FOR_EACH_BB_FN (bb
, cfun
)
4586 block_stmt_iterator bsi
;
4589 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4591 if (is_gimple_reg (PHI_RESULT (phi
)))
4593 find_func_aliases (phi
);
4597 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4599 tree stmt
= bsi_stmt (bsi
);
4600 find_func_aliases (stmt
);
4603 current_function_decl
= old_func_decl
;
4608 /* Make point to anything. */
4612 build_constraint_graph ();
4616 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4617 dump_constraints (dump_file
);
4620 if (need_to_solve ())
4624 "\nCollapsing static cycles and doing variable "
4627 find_and_collapse_graph_cycles (graph
, false);
4628 perform_var_substitution (graph
);
4631 fprintf (dump_file
, "\nSolving graph:\n");
4633 solve_graph (graph
);
4637 dump_sa_points_to_info (dump_file
);
4641 struct tree_opt_pass pass_ipa_pta
=
4644 gate_ipa_pta
, /* gate */
4645 ipa_pta_execute
, /* execute */
4648 0, /* static_pass_number */
4649 TV_IPA_PTA
, /* tv_id */
4650 0, /* properties_required */
4651 0, /* properties_provided */
4652 0, /* properties_destroyed */
4653 0, /* todo_flags_start */
4654 0, /* todo_flags_finish */
4658 /* Initialize the heapvar for statement mapping. */
4660 init_alias_heapvars (void)
4662 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
, NULL
);
4666 delete_alias_heapvars (void)
4668 htab_delete (heapvar_for_stmt
);
4672 #include "gt-tree-ssa-structalias.h"