1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006 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 #include "pointer-set.h"
57 /* The idea behind this analyzer is to generate set constraints from the
58 program, then solve the resulting constraints in order to generate the
61 Set constraints are a way of modeling program analysis problems that
62 involve sets. They consist of an inclusion constraint language,
63 describing the variables (each variable is a set) and operations that
64 are involved on the variables, and a set of rules that derive facts
65 from these operations. To solve a system of set constraints, you derive
66 all possible facts under the rules, which gives you the correct sets
69 See "Efficient Field-sensitive pointer analysis for C" by "David
70 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
71 http://citeseer.ist.psu.edu/pearce04efficient.html
73 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
74 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
75 http://citeseer.ist.psu.edu/heintze01ultrafast.html
77 There are three types of real constraint expressions, DEREF,
78 ADDRESSOF, and SCALAR. There is one type of fake constraint
79 expression, called INCLUDES. Each constraint expression consists
80 of a constraint type, a variable, and an offset.
82 SCALAR is a constraint expression type used to represent x, whether
83 it appears on the LHS or the RHS of a statement.
84 DEREF is a constraint expression type used to represent *x, whether
85 it appears on the LHS or the RHS of a statement.
86 ADDRESSOF is a constraint expression used to represent &x, whether
87 it appears on the LHS or the RHS of a statement.
88 INCLUDES is a constraint expression type used to represent just a
89 setting of a bit in the points-to set without having the address
90 taken. It exists mainly for abstraction sake, and is used for
91 initializing fake variables like the ESCAPED_VARS set.
93 Each pointer variable in the program is assigned an integer id, and
94 each field of a structure variable is assigned an integer id as well.
96 Structure variables are linked to their list of fields through a "next
97 field" in each variable that points to the next field in offset
99 Each variable for a structure field has
101 1. "size", that tells the size in bits of that field.
102 2. "fullsize, that tells the size in bits of the entire structure.
103 3. "offset", that tells the offset in bits from the beginning of the
104 structure to this field.
116 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
117 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
118 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
121 In order to solve the system of set constraints, the following is
124 1. Each constraint variable x has a solution set associated with it,
127 2. Constraints are separated into direct, copy, and complex.
128 Direct constraints are ADDRESSOF constraints that require no extra
129 processing, such as P = &Q
130 Copy constraints are those of the form P = Q.
131 Complex constraints are all the constraints involving dereferences
132 and offsets (including offsetted copies).
134 3. All direct constraints of the form P = &Q are processed, such
135 that Q is added to Sol(P)
137 4. All complex constraints for a given constraint variable are stored in a
138 linked list attached to that variable's node.
140 5. A directed graph is built out of the copy constraints. Each
141 constraint variable is a node in the graph, and an edge from
142 Q to P is added for each copy constraint of the form P = Q
144 6. The graph is then walked, and solution sets are
145 propagated along the copy edges, such that an edge from Q to P
146 causes Sol(P) <- Sol(P) union Sol(Q).
148 7. As we visit each node, all complex constraints associated with
149 that node are processed by adding appropriate copy edges to the graph, or the
150 appropriate variables to the solution set.
152 8. The process of walking the graph is iterated until no solution
155 Prior to walking the graph in steps 6 and 7, We perform static
156 cycle elimination on the constraint graph, as well
157 as off-line variable substitution.
159 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
160 on and turned into anything), but isn't. You can just see what offset
161 inside the pointed-to struct it's going to access.
163 TODO: Constant bounded arrays can be handled as if they were structs of the
164 same number of elements.
166 TODO: Modeling heap and incoming pointers becomes much better if we
167 add fields to them as we discover them, which we could do.
169 TODO: We could handle unions, but to be honest, it's probably not
170 worth the pain or slowdown. */
172 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map
)))
173 htab_t heapvar_for_stmt
;
175 static bool use_field_sensitive
= true;
176 static int in_ipa_mode
= 0;
177 static bitmap_obstack predbitmap_obstack
;
178 static bitmap_obstack ptabitmap_obstack
;
179 static bitmap_obstack iteration_obstack
;
181 static unsigned int create_variable_info_for (tree
, const char *);
182 static void build_constraint_graph (void);
184 DEF_VEC_P(constraint_t
);
185 DEF_VEC_ALLOC_P(constraint_t
,heap
);
187 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
189 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
191 static struct constraint_stats
193 unsigned int total_vars
;
194 unsigned int collapsed_vars
;
195 unsigned int unified_vars_static
;
196 unsigned int unified_vars_dynamic
;
197 unsigned int iterations
;
198 unsigned int num_edges
;
203 /* ID of this variable */
206 /* Name of this variable */
209 /* Tree that this variable is associated with. */
212 /* Offset of this variable, in bits, from the base variable */
213 unsigned HOST_WIDE_INT offset
;
215 /* Size of the variable, in bits. */
216 unsigned HOST_WIDE_INT size
;
218 /* Full size of the base variable, in bits. */
219 unsigned HOST_WIDE_INT fullsize
;
221 /* A link to the variable for the next field in this structure. */
222 struct variable_info
*next
;
224 /* Node in the graph that represents the constraints and points-to
225 solution for the variable. */
228 /* True if the address of this variable is taken. Needed for
229 variable substitution. */
230 unsigned int address_taken
:1;
232 /* True if this variable is the target of a dereference. Needed for
233 variable substitution. */
234 unsigned int indirect_target
:1;
236 /* True if the variable is directly the target of a dereference.
237 This is used to track which variables are *actually* dereferenced
238 so we can prune their points to listed. This is equivalent to the
239 indirect_target flag when no merging of variables happens. */
240 unsigned int directly_dereferenced
:1;
242 /* True if this is a variable created by the constraint analysis, such as
243 heap variables and constraints we had to break up. */
244 unsigned int is_artificial_var
:1;
246 /* True if this is a special variable whose solution set should not be
248 unsigned int is_special_var
:1;
250 /* True for variables whose size is not known or variable. */
251 unsigned int is_unknown_size_var
:1;
253 /* True for variables that have unions somewhere in them. */
254 unsigned int has_union
:1;
256 /* True if this is a heap variable. */
257 unsigned int is_heap_var
:1;
259 /* Points-to set for this variable. */
262 /* Finished points-to set for this variable (IE what is returned
263 from find_what_p_points_to. */
264 bitmap finished_solution
;
266 /* Variable ids represented by this node. */
269 /* Vector of complex constraints for this node. Complex
270 constraints are those involving dereferences. */
271 VEC(constraint_t
,heap
) *complex;
273 /* Variable id this was collapsed to due to type unsafety.
274 This should be unused completely after build_constraint_graph, or
275 something is broken. */
276 struct variable_info
*collapsed_to
;
278 typedef struct variable_info
*varinfo_t
;
280 static varinfo_t
first_vi_for_offset (varinfo_t
, unsigned HOST_WIDE_INT
);
282 /* Pool of variable info structures. */
283 static alloc_pool variable_info_pool
;
285 DEF_VEC_P(varinfo_t
);
287 DEF_VEC_ALLOC_P(varinfo_t
, heap
);
289 /* Table of variable info structures for constraint variables.
290 Indexed directly by variable info id. */
291 static VEC(varinfo_t
,heap
) *varmap
;
293 /* Return the varmap element N */
295 static inline varinfo_t
296 get_varinfo (unsigned int n
)
298 return VEC_index(varinfo_t
, varmap
, n
);
301 /* Return the varmap element N, following the collapsed_to link. */
303 static inline varinfo_t
304 get_varinfo_fc (unsigned int n
)
306 varinfo_t v
= VEC_index(varinfo_t
, varmap
, n
);
309 return v
->collapsed_to
;
313 /* Variable that represents the unknown pointer. */
314 static varinfo_t var_anything
;
315 static tree anything_tree
;
316 static unsigned int anything_id
;
318 /* Variable that represents the NULL pointer. */
319 static varinfo_t var_nothing
;
320 static tree nothing_tree
;
321 static unsigned int nothing_id
;
323 /* Variable that represents read only memory. */
324 static varinfo_t var_readonly
;
325 static tree readonly_tree
;
326 static unsigned int readonly_id
;
328 /* Variable that represents integers. This is used for when people do things
330 static varinfo_t var_integer
;
331 static tree integer_tree
;
332 static unsigned int integer_id
;
334 /* Lookup a heap var for FROM, and return it if we find one. */
337 heapvar_lookup (tree from
)
339 struct tree_map
*h
, in
;
342 h
= htab_find_with_hash (heapvar_for_stmt
, &in
, htab_hash_pointer (from
));
348 /* Insert a mapping FROM->TO in the heap var for statement
352 heapvar_insert (tree from
, tree to
)
357 h
= ggc_alloc (sizeof (struct tree_map
));
358 h
->hash
= htab_hash_pointer (from
);
361 loc
= htab_find_slot_with_hash (heapvar_for_stmt
, h
, h
->hash
, INSERT
);
362 *(struct tree_map
**) loc
= h
;
365 /* Return a new variable info structure consisting for a variable
366 named NAME, and using constraint graph node NODE. */
369 new_var_info (tree t
, unsigned int id
, const char *name
, unsigned int node
)
371 varinfo_t ret
= pool_alloc (variable_info_pool
);
377 ret
->address_taken
= false;
378 ret
->indirect_target
= false;
379 ret
->directly_dereferenced
= false;
380 ret
->is_artificial_var
= false;
381 ret
->is_heap_var
= false;
382 ret
->is_special_var
= false;
383 ret
->is_unknown_size_var
= false;
384 ret
->has_union
= false;
385 ret
->solution
= BITMAP_ALLOC (&ptabitmap_obstack
);
386 ret
->variables
= BITMAP_ALLOC (&ptabitmap_obstack
);
387 ret
->finished_solution
= NULL
;
390 ret
->collapsed_to
= NULL
;
394 typedef enum {SCALAR
, DEREF
, ADDRESSOF
, INCLUDES
} constraint_expr_type
;
396 /* An expression that appears in a constraint. */
398 struct constraint_expr
400 /* Constraint type. */
401 constraint_expr_type type
;
403 /* Variable we are referring to in the constraint. */
406 /* Offset, in bits, of this constraint from the beginning of
407 variables it ends up referring to.
409 IOW, in a deref constraint, we would deref, get the result set,
410 then add OFFSET to each member. */
411 unsigned HOST_WIDE_INT offset
;
414 typedef struct constraint_expr ce_s
;
416 DEF_VEC_ALLOC_O(ce_s
, heap
);
417 static void get_constraint_for (tree
, VEC(ce_s
, heap
) **);
418 static void do_deref (VEC (ce_s
, heap
) **);
420 /* Our set constraints are made up of two constraint expressions, one
423 As described in the introduction, our set constraints each represent an
424 operation between set valued variables.
428 struct constraint_expr lhs
;
429 struct constraint_expr rhs
;
432 /* List of constraints that we use to build the constraint graph from. */
434 static VEC(constraint_t
,heap
) *constraints
;
435 static alloc_pool constraint_pool
;
438 /* The constraint graph is represented as an array of bitmaps
439 containing successor nodes. */
441 struct constraint_graph
447 typedef struct constraint_graph
*constraint_graph_t
;
449 static constraint_graph_t graph
;
451 /* Create a new constraint consisting of LHS and RHS expressions. */
454 new_constraint (const struct constraint_expr lhs
,
455 const struct constraint_expr rhs
)
457 constraint_t ret
= pool_alloc (constraint_pool
);
463 /* Print out constraint C to FILE. */
466 dump_constraint (FILE *file
, constraint_t c
)
468 if (c
->lhs
.type
== ADDRESSOF
)
470 else if (c
->lhs
.type
== DEREF
)
472 fprintf (file
, "%s", get_varinfo_fc (c
->lhs
.var
)->name
);
473 if (c
->lhs
.offset
!= 0)
474 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->lhs
.offset
);
475 fprintf (file
, " = ");
476 if (c
->rhs
.type
== ADDRESSOF
)
478 else if (c
->rhs
.type
== DEREF
)
480 else if (c
->rhs
.type
== INCLUDES
)
482 fprintf (file
, "%s", get_varinfo_fc (c
->rhs
.var
)->name
);
483 if (c
->rhs
.offset
!= 0)
484 fprintf (file
, " + " HOST_WIDE_INT_PRINT_DEC
, c
->rhs
.offset
);
485 if (c
->rhs
.type
== INCLUDES
)
487 fprintf (file
, "\n");
490 /* Print out constraint C to stderr. */
493 debug_constraint (constraint_t c
)
495 dump_constraint (stderr
, c
);
498 /* Print out all constraints to FILE */
501 dump_constraints (FILE *file
)
505 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
506 dump_constraint (file
, c
);
509 /* Print out all constraints to stderr. */
512 debug_constraints (void)
514 dump_constraints (stderr
);
519 The solver is a simple worklist solver, that works on the following
522 sbitmap changed_nodes = all ones;
523 changed_count = number of nodes;
524 For each node that was already collapsed:
527 while (changed_count > 0)
529 compute topological ordering for constraint graph
531 find and collapse cycles in the constraint graph (updating
532 changed if necessary)
534 for each node (n) in the graph in topological order:
537 Process each complex constraint associated with the node,
538 updating changed if necessary.
540 For each outgoing edge from n, propagate the solution from n to
541 the destination of the edge, updating changed as necessary.
545 /* Return true if two constraint expressions A and B are equal. */
548 constraint_expr_equal (struct constraint_expr a
, struct constraint_expr b
)
550 return a
.type
== b
.type
&& a
.var
== b
.var
&& a
.offset
== b
.offset
;
553 /* Return true if constraint expression A is less than constraint expression
554 B. This is just arbitrary, but consistent, in order to give them an
558 constraint_expr_less (struct constraint_expr a
, struct constraint_expr b
)
560 if (a
.type
== b
.type
)
563 return a
.offset
< b
.offset
;
565 return a
.var
< b
.var
;
568 return a
.type
< b
.type
;
571 /* Return true if constraint A is less than constraint B. This is just
572 arbitrary, but consistent, in order to give them an ordering. */
575 constraint_less (const constraint_t a
, const constraint_t b
)
577 if (constraint_expr_less (a
->lhs
, b
->lhs
))
579 else if (constraint_expr_less (b
->lhs
, a
->lhs
))
582 return constraint_expr_less (a
->rhs
, b
->rhs
);
585 /* Return true if two constraints A and B are equal. */
588 constraint_equal (struct constraint a
, struct constraint b
)
590 return constraint_expr_equal (a
.lhs
, b
.lhs
)
591 && constraint_expr_equal (a
.rhs
, b
.rhs
);
595 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
598 constraint_vec_find (VEC(constraint_t
,heap
) *vec
,
599 struct constraint lookfor
)
607 place
= VEC_lower_bound (constraint_t
, vec
, &lookfor
, constraint_less
);
608 if (place
>= VEC_length (constraint_t
, vec
))
610 found
= VEC_index (constraint_t
, vec
, place
);
611 if (!constraint_equal (*found
, lookfor
))
616 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
619 constraint_set_union (VEC(constraint_t
,heap
) **to
,
620 VEC(constraint_t
,heap
) **from
)
625 for (i
= 0; VEC_iterate (constraint_t
, *from
, i
, c
); i
++)
627 if (constraint_vec_find (*to
, *c
) == NULL
)
629 unsigned int place
= VEC_lower_bound (constraint_t
, *to
, c
,
631 VEC_safe_insert (constraint_t
, heap
, *to
, place
, c
);
636 /* Take a solution set SET, add OFFSET to each member of the set, and
637 overwrite SET with the result when done. */
640 solution_set_add (bitmap set
, unsigned HOST_WIDE_INT offset
)
642 bitmap result
= BITMAP_ALLOC (&iteration_obstack
);
646 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
648 /* If this is a properly sized variable, only add offset if it's
649 less than end. Otherwise, it is globbed to a single
652 if ((get_varinfo (i
)->offset
+ offset
) < get_varinfo (i
)->fullsize
)
654 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (i
)->offset
+ offset
;
655 varinfo_t v
= first_vi_for_offset (get_varinfo (i
), fieldoffset
);
658 bitmap_set_bit (result
, v
->id
);
660 else if (get_varinfo (i
)->is_artificial_var
661 || get_varinfo (i
)->has_union
662 || get_varinfo (i
)->is_unknown_size_var
)
664 bitmap_set_bit (result
, i
);
668 bitmap_copy (set
, result
);
669 BITMAP_FREE (result
);
672 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
676 set_union_with_increment (bitmap to
, bitmap from
, unsigned HOST_WIDE_INT inc
)
679 return bitmap_ior_into (to
, from
);
685 tmp
= BITMAP_ALLOC (&iteration_obstack
);
686 bitmap_copy (tmp
, from
);
687 solution_set_add (tmp
, inc
);
688 res
= bitmap_ior_into (to
, tmp
);
694 /* Insert constraint C into the list of complex constraints for VAR. */
697 insert_into_complex (unsigned int var
, constraint_t c
)
699 varinfo_t vi
= get_varinfo (var
);
700 unsigned int place
= VEC_lower_bound (constraint_t
, vi
->complex, c
,
702 VEC_safe_insert (constraint_t
, heap
, vi
->complex, place
, c
);
706 /* Condense two variable nodes into a single variable node, by moving
707 all associated info from SRC to TO. */
710 condense_varmap_nodes (unsigned int to
, unsigned int src
)
712 varinfo_t tovi
= get_varinfo (to
);
713 varinfo_t srcvi
= get_varinfo (src
);
718 /* the src node, and all its variables, are now the to node. */
720 EXECUTE_IF_SET_IN_BITMAP (srcvi
->variables
, 0, i
, bi
)
721 get_varinfo (i
)->node
= to
;
723 /* Merge the src node variables and the to node variables. */
724 bitmap_set_bit (tovi
->variables
, src
);
725 bitmap_ior_into (tovi
->variables
, srcvi
->variables
);
726 bitmap_clear (srcvi
->variables
);
728 /* Move all complex constraints from src node into to node */
729 for (i
= 0; VEC_iterate (constraint_t
, srcvi
->complex, i
, c
); i
++)
731 /* In complex constraints for node src, we may have either
732 a = *src, and *src = a. */
734 if (c
->rhs
.type
== DEREF
)
739 constraint_set_union (&tovi
->complex, &srcvi
->complex);
740 VEC_free (constraint_t
, heap
, srcvi
->complex);
741 srcvi
->complex = NULL
;
745 /* Remove edges involving NODE from GRAPH. */
748 clear_edges_for_node (constraint_graph_t graph
, unsigned int node
)
753 /* Walk the successors, erase the associated preds. */
755 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[node
], 0, j
, bi
)
757 bitmap_clear_bit (graph
->preds
[j
], node
);
760 /* Walk the preds, erase the associated succs. */
762 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[node
], 0, j
, bi
)
764 bitmap_clear_bit (graph
->succs
[j
], node
);
767 if (graph
->preds
[node
])
769 BITMAP_FREE (graph
->preds
[node
]);
770 graph
->preds
[node
] = NULL
;
773 if (graph
->succs
[node
])
775 BITMAP_FREE (graph
->succs
[node
]);
776 graph
->succs
[node
] = NULL
;
780 static bool edge_added
= false;
782 /* Merge GRAPH nodes FROM and TO into node TO. */
785 merge_graph_nodes (constraint_graph_t graph
, unsigned int to
,
791 /* Merge all the predecessor edges. */
792 if (graph
->preds
[from
])
794 if (!graph
->preds
[to
])
795 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
797 EXECUTE_IF_SET_IN_BITMAP (graph
->preds
[from
], 0, j
, bi
)
801 bitmap_clear_bit (graph
->succs
[j
], from
);
802 bitmap_set_bit (graph
->succs
[j
], to
);
805 bitmap_ior_into (graph
->preds
[to
],
809 /* Merge all the successor edges. */
810 if (graph
->succs
[from
])
812 if (!graph
->succs
[to
])
813 graph
->succs
[to
] = BITMAP_ALLOC (&ptabitmap_obstack
);
814 EXECUTE_IF_SET_IN_BITMAP (graph
->succs
[from
], 0, j
, bi
)
816 bitmap_clear_bit (graph
->preds
[j
], from
);
817 bitmap_set_bit (graph
->preds
[j
], to
);
819 bitmap_ior_into (graph
->succs
[to
],
823 clear_edges_for_node (graph
, from
);
826 /* Add a graph edge to GRAPH, going from TO to FROM if
827 it doesn't exist in the graph already.
828 Return false if the edge already existed, true otherwise. */
831 add_graph_edge (constraint_graph_t graph
, unsigned int to
,
842 if (!graph
->preds
[to
])
843 graph
->preds
[to
] = BITMAP_ALLOC (&predbitmap_obstack
);
844 if (!graph
->succs
[from
])
845 graph
->succs
[from
] = BITMAP_ALLOC (&ptabitmap_obstack
);
846 if (!bitmap_bit_p (graph
->succs
[from
], to
))
851 bitmap_set_bit (graph
->preds
[to
], from
);
852 bitmap_set_bit (graph
->succs
[from
], to
);
859 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
862 valid_graph_edge (constraint_graph_t graph
, unsigned int src
,
865 return (graph
->succs
[dest
]
866 && bitmap_bit_p (graph
->succs
[dest
], src
));
869 /* Build the constraint graph. */
872 build_constraint_graph (void)
878 graph
= XNEW (struct constraint_graph
);
879 graph_size
= VEC_length (varinfo_t
, varmap
) + 1;
880 graph
->succs
= XCNEWVEC (bitmap
, graph_size
);
881 graph
->preds
= XCNEWVEC (bitmap
, graph_size
);
883 for (i
= 0; VEC_iterate (constraint_t
, constraints
, i
, c
); i
++)
885 struct constraint_expr lhs
= c
->lhs
;
886 struct constraint_expr rhs
= c
->rhs
;
887 unsigned int lhsvar
= get_varinfo_fc (lhs
.var
)->id
;
888 unsigned int rhsvar
= get_varinfo_fc (rhs
.var
)->id
;
890 if (lhs
.type
== DEREF
)
892 /* *x = y or *x = &y (complex) */
893 if (rhs
.type
== ADDRESSOF
|| rhsvar
> anything_id
)
894 insert_into_complex (lhsvar
, c
);
896 else if (rhs
.type
== DEREF
)
898 /* !special var= *y */
899 if (!(get_varinfo (lhsvar
)->is_special_var
))
900 insert_into_complex (rhsvar
, c
);
902 else if (rhs
.type
== ADDRESSOF
|| rhs
.type
== INCLUDES
)
905 bitmap_set_bit (get_varinfo (lhsvar
)->solution
, rhsvar
);
907 else if (lhsvar
> anything_id
)
909 /* Ignore self edges, as they can't possibly contribute
911 if (lhsvar
!= rhsvar
|| rhs
.offset
!= 0 || lhs
.offset
!= 0)
913 if (rhs
.offset
!= 0 || lhs
.offset
!= 0)
914 insert_into_complex (lhsvar
, c
);
916 add_graph_edge (graph
, lhs
.var
, rhs
.var
);
924 /* Changed variables on the last iteration. */
925 static unsigned int changed_count
;
926 static sbitmap changed
;
929 DEF_VEC_ALLOC_I(unsigned,heap
);
932 /* Strongly Connected Component visitation info. */
937 sbitmap in_component
;
939 unsigned int *visited_index
;
940 VEC(unsigned,heap
) *scc_stack
;
941 VEC(unsigned,heap
) *unification_queue
;
945 /* Recursive routine to find strongly connected components in GRAPH.
946 SI is the SCC info to store the information in, and N is the id of current
947 graph node we are processing.
949 This is Tarjan's strongly connected component finding algorithm, as
950 modified by Nuutila to keep only non-root nodes on the stack.
951 The algorithm can be found in "On finding the strongly connected
952 connected components in a directed graph" by Esko Nuutila and Eljas
953 Soisalon-Soininen, in Information Processing Letters volume 49,
954 number 1, pages 9-14. */
957 scc_visit (constraint_graph_t graph
, struct scc_info
*si
, unsigned int n
)
962 gcc_assert (get_varinfo (n
)->node
== n
);
963 SET_BIT (si
->visited
, n
);
964 RESET_BIT (si
->in_component
, n
);
965 si
->visited_index
[n
] = si
->current_index
++;
967 /* Visit all the successors. */
968 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[n
], 0, i
, bi
)
971 if (!TEST_BIT (si
->visited
, w
))
972 scc_visit (graph
, si
, w
);
973 if (!TEST_BIT (si
->in_component
, w
))
975 unsigned int t
= get_varinfo (w
)->node
;
976 unsigned int nnode
= get_varinfo (n
)->node
;
977 if (si
->visited_index
[t
] < si
->visited_index
[nnode
])
978 get_varinfo (n
)->node
= t
;
982 /* See if any components have been identified. */
983 if (get_varinfo (n
)->node
== n
)
985 unsigned int t
= si
->visited_index
[n
];
986 SET_BIT (si
->in_component
, n
);
987 while (VEC_length (unsigned, si
->scc_stack
) != 0
988 && t
< si
->visited_index
[VEC_last (unsigned, si
->scc_stack
)])
990 unsigned int w
= VEC_pop (unsigned, si
->scc_stack
);
991 get_varinfo (w
)->node
= n
;
992 SET_BIT (si
->in_component
, w
);
993 /* Mark this node for collapsing. */
994 VEC_safe_push (unsigned, heap
, si
->unification_queue
, w
);
998 VEC_safe_push (unsigned, heap
, si
->scc_stack
, n
);
1002 /* Collapse two variables into one variable, merging solutions if
1006 collapse_nodes (constraint_graph_t graph
, unsigned int to
, unsigned int from
,
1007 bool merge_solutions
)
1009 bitmap tosol
, fromsol
;
1011 merge_graph_nodes (graph
, to
, from
);
1012 condense_varmap_nodes (to
, from
);
1013 if (merge_solutions
)
1015 tosol
= get_varinfo (to
)->solution
;
1016 fromsol
= get_varinfo (from
)->solution
;
1017 bitmap_ior_into (tosol
, fromsol
);
1018 BITMAP_FREE (fromsol
);
1021 if (valid_graph_edge (graph
, to
, to
))
1023 if (graph
->preds
[to
])
1025 bitmap_clear_bit (graph
->preds
[to
], to
);
1026 bitmap_clear_bit (graph
->succs
[to
], to
);
1032 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1033 SI is the Strongly Connected Components information structure that tells us
1034 what components to unify.
1035 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1036 count should be updated to reflect the unification. */
1039 process_unification_queue (constraint_graph_t graph
, struct scc_info
*si
,
1040 bool update_changed
)
1043 bitmap tmp
= BITMAP_ALLOC (update_changed
? &iteration_obstack
: NULL
);
1046 /* We proceed as follows:
1048 For each component in the queue (components are delineated by
1049 when current_queue_element->node != next_queue_element->node):
1051 rep = representative node for component
1053 For each node (tounify) to be unified in the component,
1054 merge the solution for tounify into tmp bitmap
1056 clear solution for tounify
1058 merge edges from tounify into rep
1060 merge complex constraints from tounify into rep
1062 update changed count to note that tounify will never change
1065 Merge tmp into solution for rep, marking rep changed if this
1066 changed rep's solution.
1068 Delete any self-edges we now have for rep. */
1069 while (i
!= VEC_length (unsigned, si
->unification_queue
))
1071 unsigned int tounify
= VEC_index (unsigned, si
->unification_queue
, i
);
1072 unsigned int n
= get_varinfo (tounify
)->node
;
1074 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1075 fprintf (dump_file
, "Unifying %s to %s\n",
1076 get_varinfo (tounify
)->name
,
1077 get_varinfo (n
)->name
);
1079 stats
.unified_vars_dynamic
++;
1081 stats
.unified_vars_static
++;
1082 bitmap_ior_into (tmp
, get_varinfo (tounify
)->solution
);
1083 collapse_nodes (graph
, n
, tounify
, false);
1085 if (update_changed
&& TEST_BIT (changed
, tounify
))
1087 RESET_BIT (changed
, tounify
);
1088 if (!TEST_BIT (changed
, n
))
1089 SET_BIT (changed
, n
);
1092 gcc_assert (changed_count
> 0);
1097 bitmap_clear (get_varinfo (tounify
)->solution
);
1100 /* If we've either finished processing the entire queue, or
1101 finished processing all nodes for component n, update the solution for
1103 if (i
== VEC_length (unsigned, si
->unification_queue
)
1104 || get_varinfo (VEC_index (unsigned, si
->unification_queue
, i
))->node
!= n
)
1106 /* If the solution changes because of the merging, we need to mark
1107 the variable as changed. */
1108 if (bitmap_ior_into (get_varinfo (n
)->solution
, tmp
))
1110 if (update_changed
&& !TEST_BIT (changed
, n
))
1112 SET_BIT (changed
, n
);
1118 if (valid_graph_edge (graph
, n
, n
))
1120 if (graph
->succs
[n
])
1122 if (graph
->preds
[n
])
1123 bitmap_clear_bit (graph
->preds
[n
], n
);
1124 bitmap_clear_bit (graph
->succs
[n
], n
);
1133 /* Information needed to compute the topological ordering of a graph. */
1137 /* sbitmap of visited nodes. */
1139 /* Array that stores the topological order of the graph, *in
1141 VEC(unsigned,heap
) *topo_order
;
1145 /* Initialize and return a topological info structure. */
1147 static struct topo_info
*
1148 init_topo_info (void)
1150 size_t size
= VEC_length (varinfo_t
, varmap
);
1151 struct topo_info
*ti
= XNEW (struct topo_info
);
1152 ti
->visited
= sbitmap_alloc (size
);
1153 sbitmap_zero (ti
->visited
);
1154 ti
->topo_order
= VEC_alloc (unsigned, heap
, 1);
1159 /* Free the topological sort info pointed to by TI. */
1162 free_topo_info (struct topo_info
*ti
)
1164 sbitmap_free (ti
->visited
);
1165 VEC_free (unsigned, heap
, ti
->topo_order
);
1169 /* Visit the graph in topological order, and store the order in the
1170 topo_info structure. */
1173 topo_visit (constraint_graph_t graph
, struct topo_info
*ti
,
1180 SET_BIT (ti
->visited
, n
);
1181 temp
= graph
->succs
[n
];
1184 EXECUTE_IF_SET_IN_BITMAP (temp
, 0, j
, bi
)
1186 if (!TEST_BIT (ti
->visited
, j
))
1187 topo_visit (graph
, ti
, j
);
1189 VEC_safe_push (unsigned, heap
, ti
->topo_order
, n
);
1192 /* Return true if variable N + OFFSET is a legal field of N. */
1195 type_safe (unsigned int n
, unsigned HOST_WIDE_INT
*offset
)
1197 varinfo_t ninfo
= get_varinfo (n
);
1199 /* For things we've globbed to single variables, any offset into the
1200 variable acts like the entire variable, so that it becomes offset
1202 if (ninfo
->is_special_var
1203 || ninfo
->is_artificial_var
1204 || ninfo
->is_unknown_size_var
)
1209 return (get_varinfo (n
)->offset
+ *offset
) < get_varinfo (n
)->fullsize
;
1212 /* Process a constraint C that represents *x = &y. */
1215 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED
,
1216 constraint_t c
, bitmap delta
)
1218 unsigned int rhs
= c
->rhs
.var
;
1222 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1223 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1225 unsigned HOST_WIDE_INT offset
= c
->lhs
.offset
;
1226 if (type_safe (j
, &offset
) && !(get_varinfo (j
)->is_special_var
))
1228 /* *x != NULL && *x != ANYTHING*/
1232 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ offset
;
1234 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1238 sol
= get_varinfo (t
)->solution
;
1239 if (!bitmap_bit_p (sol
, rhs
))
1241 bitmap_set_bit (sol
, rhs
);
1242 if (!TEST_BIT (changed
, t
))
1244 SET_BIT (changed
, t
);
1249 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1250 fprintf (dump_file
, "Untypesafe usage in do_da_constraint.\n");
1255 /* Process a constraint C that represents x = *y, using DELTA as the
1256 starting solution. */
1259 do_sd_constraint (constraint_graph_t graph
, constraint_t c
,
1262 unsigned int lhs
= get_varinfo (c
->lhs
.var
)->node
;
1264 bitmap sol
= get_varinfo (lhs
)->solution
;
1268 if (bitmap_bit_p (delta
, anything_id
))
1270 flag
= !bitmap_bit_p (sol
, anything_id
);
1272 bitmap_set_bit (sol
, anything_id
);
1275 /* For each variable j in delta (Sol(y)), add
1276 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1277 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1279 unsigned HOST_WIDE_INT roffset
= c
->rhs
.offset
;
1280 if (type_safe (j
, &roffset
))
1283 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ roffset
;
1286 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1291 /* Adding edges from the special vars is pointless.
1292 They don't have sets that can change. */
1293 if (get_varinfo (t
) ->is_special_var
)
1294 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1295 else if (add_graph_edge (graph
, lhs
, t
))
1296 flag
|= bitmap_ior_into (sol
, get_varinfo (t
)->solution
);
1298 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1299 fprintf (dump_file
, "Untypesafe usage in do_sd_constraint\n");
1304 /* If the LHS solution changed, mark the var as changed. */
1307 get_varinfo (lhs
)->solution
= sol
;
1308 if (!TEST_BIT (changed
, lhs
))
1310 SET_BIT (changed
, lhs
);
1316 /* Process a constraint C that represents *x = y. */
1319 do_ds_constraint (constraint_t c
, bitmap delta
)
1321 unsigned int rhs
= get_varinfo (c
->rhs
.var
)->node
;
1322 unsigned HOST_WIDE_INT roff
= c
->rhs
.offset
;
1323 bitmap sol
= get_varinfo (rhs
)->solution
;
1327 if (bitmap_bit_p (sol
, anything_id
))
1329 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1331 varinfo_t jvi
= get_varinfo (j
);
1333 unsigned int loff
= c
->lhs
.offset
;
1334 unsigned HOST_WIDE_INT fieldoffset
= jvi
->offset
+ loff
;
1337 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1342 if (!bitmap_bit_p (get_varinfo (t
)->solution
, anything_id
))
1344 bitmap_set_bit (get_varinfo (t
)->solution
, anything_id
);
1345 if (!TEST_BIT (changed
, t
))
1347 SET_BIT (changed
, t
);
1355 /* For each member j of delta (Sol(x)), add an edge from y to j and
1356 union Sol(y) into Sol(j) */
1357 EXECUTE_IF_SET_IN_BITMAP (delta
, 0, j
, bi
)
1359 unsigned HOST_WIDE_INT loff
= c
->lhs
.offset
;
1360 if (type_safe (j
, &loff
) && !(get_varinfo(j
)->is_special_var
))
1364 unsigned HOST_WIDE_INT fieldoffset
= get_varinfo (j
)->offset
+ loff
;
1367 v
= first_vi_for_offset (get_varinfo (j
), fieldoffset
);
1371 tmp
= get_varinfo (t
)->solution
;
1373 if (set_union_with_increment (tmp
, sol
, roff
))
1375 get_varinfo (t
)->solution
= tmp
;
1377 sol
= get_varinfo (rhs
)->solution
;
1378 if (!TEST_BIT (changed
, t
))
1380 SET_BIT (changed
, t
);
1385 else if (0 && dump_file
&& !(get_varinfo (j
)->is_special_var
))
1386 fprintf (dump_file
, "Untypesafe usage in do_ds_constraint\n");
1390 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1391 constraint (IE *x = &y, x = *y, and *x = y). */
1394 do_complex_constraint (constraint_graph_t graph
, constraint_t c
, bitmap delta
)
1396 if (c
->lhs
.type
== DEREF
)
1398 if (c
->rhs
.type
== ADDRESSOF
)
1401 do_da_constraint (graph
, c
, delta
);
1406 do_ds_constraint (c
, delta
);
1409 else if (c
->rhs
.type
== DEREF
)
1412 if (!(get_varinfo (c
->lhs
.var
)->is_special_var
))
1413 do_sd_constraint (graph
, c
, delta
);
1422 gcc_assert(c
->rhs
.type
== SCALAR
&& c
->lhs
.type
== SCALAR
);
1423 t
= get_varinfo (c
->rhs
.var
)->node
;
1424 solution
= get_varinfo (t
)->solution
;
1425 t
= get_varinfo (c
->lhs
.var
)->node
;
1426 tmp
= get_varinfo (t
)->solution
;
1428 flag
= set_union_with_increment (tmp
, solution
, c
->rhs
.offset
);
1432 get_varinfo (t
)->solution
= tmp
;
1433 if (!TEST_BIT (changed
, c
->lhs
.var
))
1435 SET_BIT (changed
, c
->lhs
.var
);
1442 /* Initialize and return a new SCC info structure. */
1444 static struct scc_info
*
1445 init_scc_info (void)
1447 struct scc_info
*si
= XNEW (struct scc_info
);
1448 size_t size
= VEC_length (varinfo_t
, varmap
);
1450 si
->current_index
= 0;
1451 si
->visited
= sbitmap_alloc (size
);
1452 sbitmap_zero (si
->visited
);
1453 si
->in_component
= sbitmap_alloc (size
);
1454 sbitmap_ones (si
->in_component
);
1455 si
->visited_index
= XCNEWVEC (unsigned int, size
+ 1);
1456 si
->scc_stack
= VEC_alloc (unsigned, heap
, 1);
1457 si
->unification_queue
= VEC_alloc (unsigned, heap
, 1);
1461 /* Free an SCC info structure pointed to by SI */
1464 free_scc_info (struct scc_info
*si
)
1466 sbitmap_free (si
->visited
);
1467 sbitmap_free (si
->in_component
);
1468 free (si
->visited_index
);
1469 VEC_free (unsigned, heap
, si
->scc_stack
);
1470 VEC_free (unsigned, heap
, si
->unification_queue
);
1475 /* Find cycles in GRAPH that occur, using strongly connected components, and
1476 collapse the cycles into a single representative node. if UPDATE_CHANGED
1477 is true, then update the changed sbitmap to note those nodes whose
1478 solutions have changed as a result of collapsing. */
1481 find_and_collapse_graph_cycles (constraint_graph_t graph
, bool update_changed
)
1484 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1485 struct scc_info
*si
= init_scc_info ();
1487 for (i
= 0; i
!= size
; ++i
)
1488 if (!TEST_BIT (si
->visited
, i
) && get_varinfo (i
)->node
== i
)
1489 scc_visit (graph
, si
, i
);
1491 process_unification_queue (graph
, si
, update_changed
);
1495 /* Compute a topological ordering for GRAPH, and store the result in the
1496 topo_info structure TI. */
1499 compute_topo_order (constraint_graph_t graph
,
1500 struct topo_info
*ti
)
1503 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1505 for (i
= 0; i
!= size
; ++i
)
1506 if (!TEST_BIT (ti
->visited
, i
) && get_varinfo (i
)->node
== i
)
1507 topo_visit (graph
, ti
, i
);
1510 /* Perform offline variable substitution.
1512 This is a linear time way of identifying variables that must have
1513 equivalent points-to sets, including those caused by static cycles,
1514 and single entry subgraphs, in the constraint graph.
1516 The technique is described in "Off-line variable substitution for
1517 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1518 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1521 perform_var_substitution (constraint_graph_t graph
)
1523 struct topo_info
*ti
= init_topo_info ();
1525 bitmap_obstack_initialize (&iteration_obstack
);
1526 /* Compute the topological ordering of the graph, then visit each
1527 node in topological order. */
1528 compute_topo_order (graph
, ti
);
1530 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1532 unsigned int i
= VEC_pop (unsigned, ti
->topo_order
);
1533 varinfo_t vi
= get_varinfo (i
);
1534 bool okay_to_elim
= false;
1535 unsigned int root
= VEC_length (varinfo_t
, varmap
);
1540 /* We can't eliminate things whose address is taken, or which is
1541 the target of a dereference. */
1542 if (vi
->address_taken
|| vi
->indirect_target
)
1545 /* See if all predecessors of I are ripe for elimination */
1546 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->preds
[i
], 0, k
, bi
)
1549 w
= get_varinfo (k
)->node
;
1551 /* We can't eliminate the node if one of the predecessors is
1552 part of a different strongly connected component. */
1556 okay_to_elim
= true;
1560 okay_to_elim
= false;
1564 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1565 then Solution(i) is a subset of Solution (w), where w is a
1566 predecessor in the graph.
1567 Corollary: If all predecessors of i have the same
1568 points-to set, then i has that same points-to set as
1569 those predecessors. */
1570 tmp
= BITMAP_ALLOC (NULL
);
1571 bitmap_and_compl (tmp
, get_varinfo (i
)->solution
,
1572 get_varinfo (w
)->solution
);
1573 if (!bitmap_empty_p (tmp
))
1575 okay_to_elim
= false;
1582 /* See if the root is different than the original node.
1583 If so, we've found an equivalence. */
1584 if (root
!= get_varinfo (i
)->node
&& okay_to_elim
)
1586 /* Found an equivalence */
1587 get_varinfo (i
)->node
= root
;
1588 collapse_nodes (graph
, root
, i
, true);
1589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1590 fprintf (dump_file
, "Collapsing %s into %s\n",
1591 get_varinfo (i
)->name
,
1592 get_varinfo (root
)->name
);
1593 stats
.collapsed_vars
++;
1597 bitmap_obstack_release (&iteration_obstack
);
1598 free_topo_info (ti
);
1601 /* Solve the constraint graph GRAPH using our worklist solver.
1602 This is based on the PW* family of solvers from the "Efficient Field
1603 Sensitive Pointer Analysis for C" paper.
1604 It works by iterating over all the graph nodes, processing the complex
1605 constraints and propagating the copy constraints, until everything stops
1606 changed. This corresponds to steps 6-8 in the solving list given above. */
1609 solve_graph (constraint_graph_t graph
)
1611 unsigned int size
= VEC_length (varinfo_t
, varmap
);
1614 changed_count
= size
;
1615 changed
= sbitmap_alloc (size
);
1616 sbitmap_ones (changed
);
1618 /* The already collapsed/unreachable nodes will never change, so we
1619 need to account for them in changed_count. */
1620 for (i
= 0; i
< size
; i
++)
1621 if (get_varinfo (i
)->node
!= i
)
1624 while (changed_count
> 0)
1627 struct topo_info
*ti
= init_topo_info ();
1630 bitmap_obstack_initialize (&iteration_obstack
);
1634 /* We already did cycle elimination once, when we did
1635 variable substitution, so we don't need it again for the
1637 if (stats
.iterations
> 1)
1638 find_and_collapse_graph_cycles (graph
, true);
1643 compute_topo_order (graph
, ti
);
1645 while (VEC_length (unsigned, ti
->topo_order
) != 0)
1647 i
= VEC_pop (unsigned, ti
->topo_order
);
1648 gcc_assert (get_varinfo (i
)->node
== i
);
1650 /* If the node has changed, we need to process the
1651 complex constraints and outgoing edges again. */
1652 if (TEST_BIT (changed
, i
))
1658 VEC(constraint_t
,heap
) *complex = get_varinfo (i
)->complex;
1659 bool solution_empty
;
1661 RESET_BIT (changed
, i
);
1664 solution
= get_varinfo (i
)->solution
;
1665 solution_empty
= bitmap_empty_p (solution
);
1667 /* Process the complex constraints */
1668 for (j
= 0; VEC_iterate (constraint_t
, complex, j
, c
); j
++)
1670 /* The only complex constraint that can change our
1671 solution to non-empty, given an empty solution,
1672 is a constraint where the lhs side is receiving
1673 some set from elsewhere. */
1674 if (!solution_empty
|| c
->lhs
.type
!= DEREF
)
1675 do_complex_constraint (graph
, c
, solution
);
1678 solution_empty
= bitmap_empty_p (solution
);
1680 if (!solution_empty
)
1682 /* Propagate solution to all successors. */
1683 EXECUTE_IF_IN_NONNULL_BITMAP (graph
->succs
[i
],
1686 bitmap tmp
= get_varinfo (j
)->solution
;
1689 gcc_assert (get_varinfo (j
)->node
== j
);
1691 flag
= set_union_with_increment (tmp
, solution
, 0);
1695 get_varinfo (j
)->solution
= tmp
;
1696 if (!TEST_BIT (changed
, j
))
1698 SET_BIT (changed
, j
);
1706 free_topo_info (ti
);
1707 bitmap_obstack_release (&iteration_obstack
);
1710 sbitmap_free (changed
);
1714 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1716 /* Map from trees to variable ids. */
1717 static htab_t id_for_tree
;
1719 typedef struct tree_id
1725 /* Hash a tree id structure. */
1728 tree_id_hash (const void *p
)
1730 const tree_id_t ta
= (tree_id_t
) p
;
1731 return htab_hash_pointer (ta
->t
);
1734 /* Return true if the tree in P1 and the tree in P2 are the same. */
1737 tree_id_eq (const void *p1
, const void *p2
)
1739 const tree_id_t ta1
= (tree_id_t
) p1
;
1740 const tree_id_t ta2
= (tree_id_t
) p2
;
1741 return ta1
->t
== ta2
->t
;
1744 /* Insert ID as the variable id for tree T in the hashtable. */
1747 insert_id_for_tree (tree t
, int id
)
1750 struct tree_id finder
;
1754 slot
= htab_find_slot (id_for_tree
, &finder
, INSERT
);
1755 gcc_assert (*slot
== NULL
);
1756 new_pair
= XNEW (struct tree_id
);
1759 *slot
= (void *)new_pair
;
1762 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1763 exist in the hash table, return false, otherwise, return true and
1764 set *ID to the id we found. */
1767 lookup_id_for_tree (tree t
, unsigned int *id
)
1770 struct tree_id finder
;
1773 pair
= htab_find (id_for_tree
, &finder
);
1780 /* Return a printable name for DECL */
1783 alias_get_name (tree decl
)
1785 const char *res
= get_name (decl
);
1787 int num_printed
= 0;
1796 if (TREE_CODE (decl
) == SSA_NAME
)
1798 num_printed
= asprintf (&temp
, "%s_%u",
1799 alias_get_name (SSA_NAME_VAR (decl
)),
1800 SSA_NAME_VERSION (decl
));
1802 else if (DECL_P (decl
))
1804 num_printed
= asprintf (&temp
, "D.%u", DECL_UID (decl
));
1806 if (num_printed
> 0)
1808 res
= ggc_strdup (temp
);
1814 /* Find the variable id for tree T in the hashtable.
1815 If T doesn't exist in the hash table, create an entry for it. */
1818 get_id_for_tree (tree t
)
1821 struct tree_id finder
;
1824 pair
= htab_find (id_for_tree
, &finder
);
1826 return create_variable_info_for (t
, alias_get_name (t
));
1831 /* Get a constraint expression from an SSA_VAR_P node. */
1833 static struct constraint_expr
1834 get_constraint_exp_from_ssa_var (tree t
)
1836 struct constraint_expr cexpr
;
1838 gcc_assert (SSA_VAR_P (t
) || DECL_P (t
));
1840 /* For parameters, get at the points-to set for the actual parm
1842 if (TREE_CODE (t
) == SSA_NAME
1843 && TREE_CODE (SSA_NAME_VAR (t
)) == PARM_DECL
1844 && SSA_NAME_IS_DEFAULT_DEF (t
))
1845 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t
));
1847 cexpr
.type
= SCALAR
;
1849 cexpr
.var
= get_id_for_tree (t
);
1850 /* If we determine the result is "anything", and we know this is readonly,
1851 say it points to readonly memory instead. */
1852 if (cexpr
.var
== anything_id
&& TREE_READONLY (t
))
1854 cexpr
.type
= INCLUDES
;
1855 cexpr
.var
= readonly_id
;
1862 /* Process a completed constraint T, and add it to the constraint
1866 process_constraint (constraint_t t
)
1868 struct constraint_expr rhs
= t
->rhs
;
1869 struct constraint_expr lhs
= t
->lhs
;
1871 gcc_assert (rhs
.var
< VEC_length (varinfo_t
, varmap
));
1872 gcc_assert (lhs
.var
< VEC_length (varinfo_t
, varmap
));
1874 gcc_assert (lhs
.type
!= INCLUDES
);
1876 if (lhs
.type
== DEREF
)
1877 get_varinfo (lhs
.var
)->directly_dereferenced
= true;
1878 if (rhs
.type
== DEREF
)
1879 get_varinfo (rhs
.var
)->directly_dereferenced
= true;
1881 if (!use_field_sensitive
)
1887 /* ANYTHING == ANYTHING is pointless. */
1888 if (lhs
.var
== anything_id
&& rhs
.var
== anything_id
)
1891 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1892 else if (lhs
.var
== anything_id
1893 && (lhs
.type
== INCLUDES
|| lhs
.type
== ADDRESSOF
))
1898 process_constraint (t
);
1900 /* This can happen in our IR with things like n->a = *p */
1901 else if (rhs
.type
== DEREF
&& lhs
.type
== DEREF
&& rhs
.var
!= anything_id
)
1903 /* Split into tmp = *rhs, *lhs = tmp */
1904 tree rhsdecl
= get_varinfo (rhs
.var
)->decl
;
1905 tree pointertype
= TREE_TYPE (rhsdecl
);
1906 tree pointedtotype
= TREE_TYPE (pointertype
);
1907 tree tmpvar
= create_tmp_var_raw (pointedtotype
, "doubledereftmp");
1908 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
1910 /* If this is an aggregate of known size, we should have passed
1911 this off to do_structure_copy, and it should have broken it
1913 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype
)
1914 || get_varinfo (rhs
.var
)->is_unknown_size_var
);
1916 process_constraint (new_constraint (tmplhs
, rhs
));
1917 process_constraint (new_constraint (lhs
, tmplhs
));
1919 else if (rhs
.type
== ADDRESSOF
)
1922 gcc_assert (rhs
.offset
== 0);
1924 for (vi
= get_varinfo (rhs
.var
); vi
!= NULL
; vi
= vi
->next
)
1925 vi
->address_taken
= true;
1927 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
1931 if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
1932 get_varinfo (lhs
.var
)->indirect_target
= true;
1933 VEC_safe_push (constraint_t
, heap
, constraints
, t
);
1937 /* Return true if T is a variable of a type that could contain
1941 could_have_pointers (tree t
)
1943 tree type
= TREE_TYPE (t
);
1945 if (POINTER_TYPE_P (type
) || AGGREGATE_TYPE_P (type
)
1946 || TREE_CODE (type
) == COMPLEX_TYPE
)
1951 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1954 static unsigned HOST_WIDE_INT
1955 bitpos_of_field (const tree fdecl
)
1958 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl
)) != INTEGER_CST
1959 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl
)) != INTEGER_CST
)
1962 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl
), 1) * 8)
1963 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl
), 1);
1967 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1968 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1971 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos
,
1972 const unsigned HOST_WIDE_INT fieldsize
,
1973 const unsigned HOST_WIDE_INT accesspos
,
1974 const unsigned HOST_WIDE_INT accesssize
)
1976 if (fieldpos
== accesspos
&& fieldsize
== accesssize
)
1978 if (accesspos
>= fieldpos
&& accesspos
< (fieldpos
+ fieldsize
))
1980 if (accesspos
< fieldpos
&& (accesspos
+ accesssize
> fieldpos
))
1986 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1989 get_constraint_for_component_ref (tree t
, VEC(ce_s
, heap
) **results
)
1992 HOST_WIDE_INT bitsize
= -1;
1993 HOST_WIDE_INT bitmaxsize
= -1;
1994 HOST_WIDE_INT bitpos
;
1996 struct constraint_expr
*result
;
1997 unsigned int beforelength
= VEC_length (ce_s
, *results
);
1999 /* Some people like to do cute things like take the address of
2002 while (!SSA_VAR_P (forzero
) && !CONSTANT_CLASS_P (forzero
))
2003 forzero
= TREE_OPERAND (forzero
, 0);
2005 if (CONSTANT_CLASS_P (forzero
) && integer_zerop (forzero
))
2007 struct constraint_expr temp
;
2010 temp
.var
= integer_id
;
2012 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2016 t
= get_ref_base_and_extent (t
, &bitpos
, &bitsize
, &bitmaxsize
);
2018 /* String constants are readonly, so there is nothing to really do
2020 if (TREE_CODE (t
) == STRING_CST
)
2023 get_constraint_for (t
, results
);
2024 result
= VEC_last (ce_s
, *results
);
2025 result
->offset
= bitpos
;
2027 gcc_assert (beforelength
+ 1 == VEC_length (ce_s
, *results
));
2029 /* This can also happen due to weird offsetof type macros. */
2030 if (TREE_CODE (t
) != ADDR_EXPR
&& result
->type
== ADDRESSOF
)
2031 result
->type
= SCALAR
;
2033 if (result
->type
== SCALAR
)
2035 /* In languages like C, you can access one past the end of an
2036 array. You aren't allowed to dereference it, so we can
2037 ignore this constraint. When we handle pointer subtraction,
2038 we may have to do something cute here. */
2040 if (result
->offset
< get_varinfo (result
->var
)->fullsize
2043 /* It's also not true that the constraint will actually start at the
2044 right offset, it may start in some padding. We only care about
2045 setting the constraint to the first actual field it touches, so
2048 for (curr
= get_varinfo (result
->var
); curr
; curr
= curr
->next
)
2050 if (offset_overlaps_with_access (curr
->offset
, curr
->size
,
2051 result
->offset
, bitmaxsize
))
2053 result
->var
= curr
->id
;
2057 /* assert that we found *some* field there. The user couldn't be
2058 accessing *only* padding. */
2059 /* Still the user could access one past the end of an array
2060 embedded in a struct resulting in accessing *only* padding. */
2061 gcc_assert (curr
|| ref_contains_array_ref (orig_t
));
2063 else if (bitmaxsize
== 0)
2065 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2066 fprintf (dump_file
, "Access to zero-sized part of variable,"
2070 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2071 fprintf (dump_file
, "Access to past the end of variable, ignoring\n");
2078 /* Dereference the constraint expression CONS, and return the result.
2079 DEREF (ADDRESSOF) = SCALAR
2080 DEREF (SCALAR) = DEREF
2081 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2082 This is needed so that we can handle dereferencing DEREF constraints. */
2085 do_deref (VEC (ce_s
, heap
) **constraints
)
2087 struct constraint_expr
*c
;
2090 for (i
= 0; VEC_iterate (ce_s
, *constraints
, i
, c
); i
++)
2092 if (c
->type
== SCALAR
)
2094 else if (c
->type
== ADDRESSOF
)
2096 else if (c
->type
== DEREF
)
2098 tree tmpvar
= create_tmp_var_raw (ptr_type_node
, "dereftmp");
2099 struct constraint_expr tmplhs
= get_constraint_exp_from_ssa_var (tmpvar
);
2100 process_constraint (new_constraint (tmplhs
, *c
));
2101 c
->var
= tmplhs
.var
;
2108 /* Given a tree T, return the constraint expression for it. */
2111 get_constraint_for (tree t
, VEC (ce_s
, heap
) **results
)
2113 struct constraint_expr temp
;
2115 /* x = integer is all glommed to a single variable, which doesn't
2116 point to anything by itself. That is, of course, unless it is an
2117 integer constant being treated as a pointer, in which case, we
2118 will return that this is really the addressof anything. This
2119 happens below, since it will fall into the default case. The only
2120 case we know something about an integer treated like a pointer is
2121 when it is the NULL pointer, and then we just say it points to
2123 if (TREE_CODE (t
) == INTEGER_CST
2124 && !POINTER_TYPE_P (TREE_TYPE (t
)))
2126 temp
.var
= integer_id
;
2129 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2132 else if (TREE_CODE (t
) == INTEGER_CST
2133 && integer_zerop (t
))
2135 temp
.var
= nothing_id
;
2136 temp
.type
= ADDRESSOF
;
2138 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2142 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
2144 case tcc_expression
:
2146 switch (TREE_CODE (t
))
2150 struct constraint_expr
*c
;
2152 tree exp
= TREE_OPERAND (t
, 0);
2153 tree pttype
= TREE_TYPE (TREE_TYPE (t
));
2155 get_constraint_for (exp
, results
);
2156 /* Make sure we capture constraints to all elements
2158 if ((handled_component_p (exp
)
2159 && ref_contains_array_ref (exp
))
2160 || TREE_CODE (TREE_TYPE (exp
)) == ARRAY_TYPE
)
2162 struct constraint_expr
*origrhs
;
2164 struct constraint_expr tmp
;
2166 if (VEC_length (ce_s
, *results
) == 0)
2169 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2170 origrhs
= VEC_last (ce_s
, *results
);
2172 VEC_pop (ce_s
, *results
);
2173 origvar
= get_varinfo (origrhs
->var
);
2174 for (; origvar
; origvar
= origvar
->next
)
2176 tmp
.var
= origvar
->id
;
2177 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2180 else if (VEC_length (ce_s
, *results
) == 1
2181 && (AGGREGATE_TYPE_P (pttype
)
2182 || TREE_CODE (pttype
) == COMPLEX_TYPE
))
2184 struct constraint_expr
*origrhs
;
2186 struct constraint_expr tmp
;
2188 gcc_assert (VEC_length (ce_s
, *results
) == 1);
2189 origrhs
= VEC_last (ce_s
, *results
);
2191 VEC_pop (ce_s
, *results
);
2192 origvar
= get_varinfo (origrhs
->var
);
2193 for (; origvar
; origvar
= origvar
->next
)
2195 tmp
.var
= origvar
->id
;
2196 VEC_safe_push (ce_s
, heap
, *results
, &tmp
);
2200 for (i
= 0; VEC_iterate (ce_s
, *results
, i
, c
); i
++)
2202 if (c
->type
== DEREF
)
2205 c
->type
= ADDRESSOF
;
2211 /* XXX: In interprocedural mode, if we didn't have the
2212 body, we would need to do *each pointer argument =
2214 if (call_expr_flags (t
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
))
2217 tree heapvar
= heapvar_lookup (t
);
2219 if (heapvar
== NULL
)
2221 heapvar
= create_tmp_var_raw (ptr_type_node
, "HEAP");
2222 DECL_EXTERNAL (heapvar
) = 1;
2223 get_var_ann (heapvar
)->is_heapvar
= 1;
2224 if (gimple_referenced_vars (cfun
))
2225 add_referenced_var (heapvar
);
2226 heapvar_insert (t
, heapvar
);
2229 temp
.var
= create_variable_info_for (heapvar
,
2230 alias_get_name (heapvar
));
2232 vi
= get_varinfo (temp
.var
);
2233 vi
->is_artificial_var
= 1;
2234 vi
->is_heap_var
= 1;
2235 temp
.type
= INCLUDES
;
2237 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2242 temp
.var
= anything_id
;
2245 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2251 temp
.type
= ADDRESSOF
;
2252 temp
.var
= anything_id
;
2254 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2261 switch (TREE_CODE (t
))
2265 get_constraint_for (TREE_OPERAND (t
, 0), results
);
2270 case ARRAY_RANGE_REF
:
2272 get_constraint_for_component_ref (t
, results
);
2276 temp
.type
= ADDRESSOF
;
2277 temp
.var
= anything_id
;
2279 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2286 switch (TREE_CODE (t
))
2290 case NON_LVALUE_EXPR
:
2292 tree op
= TREE_OPERAND (t
, 0);
2294 /* Cast from non-pointer to pointers are bad news for us.
2295 Anything else, we see through */
2296 if (!(POINTER_TYPE_P (TREE_TYPE (t
))
2297 && ! POINTER_TYPE_P (TREE_TYPE (op
))))
2299 get_constraint_for (op
, results
);
2307 temp
.type
= ADDRESSOF
;
2308 temp
.var
= anything_id
;
2310 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2315 case tcc_exceptional
:
2317 switch (TREE_CODE (t
))
2321 get_constraint_for (PHI_RESULT (t
), results
);
2327 struct constraint_expr temp
;
2328 temp
= get_constraint_exp_from_ssa_var (t
);
2329 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2335 temp
.type
= ADDRESSOF
;
2336 temp
.var
= anything_id
;
2338 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2343 case tcc_declaration
:
2345 struct constraint_expr temp
;
2346 temp
= get_constraint_exp_from_ssa_var (t
);
2347 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2352 temp
.type
= ADDRESSOF
;
2353 temp
.var
= anything_id
;
2355 VEC_safe_push (ce_s
, heap
, *results
, &temp
);
2362 /* Handle the structure copy case where we have a simple structure copy
2363 between LHS and RHS that is of SIZE (in bits)
2365 For each field of the lhs variable (lhsfield)
2366 For each field of the rhs variable at lhsfield.offset (rhsfield)
2367 add the constraint lhsfield = rhsfield
2369 If we fail due to some kind of type unsafety or other thing we
2370 can't handle, return false. We expect the caller to collapse the
2371 variable in that case. */
2374 do_simple_structure_copy (const struct constraint_expr lhs
,
2375 const struct constraint_expr rhs
,
2376 const unsigned HOST_WIDE_INT size
)
2378 varinfo_t p
= get_varinfo (lhs
.var
);
2379 unsigned HOST_WIDE_INT pstart
, last
;
2381 last
= p
->offset
+ size
;
2382 for (; p
&& p
->offset
< last
; p
= p
->next
)
2385 struct constraint_expr templhs
= lhs
;
2386 struct constraint_expr temprhs
= rhs
;
2387 unsigned HOST_WIDE_INT fieldoffset
;
2389 templhs
.var
= p
->id
;
2390 q
= get_varinfo (temprhs
.var
);
2391 fieldoffset
= p
->offset
- pstart
;
2392 q
= first_vi_for_offset (q
, q
->offset
+ fieldoffset
);
2395 temprhs
.var
= q
->id
;
2396 process_constraint (new_constraint (templhs
, temprhs
));
2402 /* Handle the structure copy case where we have a structure copy between a
2403 aggregate on the LHS and a dereference of a pointer on the RHS
2404 that is of SIZE (in bits)
2406 For each field of the lhs variable (lhsfield)
2407 rhs.offset = lhsfield->offset
2408 add the constraint lhsfield = rhs
2412 do_rhs_deref_structure_copy (const struct constraint_expr lhs
,
2413 const struct constraint_expr rhs
,
2414 const unsigned HOST_WIDE_INT size
)
2416 varinfo_t p
= get_varinfo (lhs
.var
);
2417 unsigned HOST_WIDE_INT pstart
,last
;
2419 last
= p
->offset
+ size
;
2421 for (; p
&& p
->offset
< last
; p
= p
->next
)
2424 struct constraint_expr templhs
= lhs
;
2425 struct constraint_expr temprhs
= rhs
;
2426 unsigned HOST_WIDE_INT fieldoffset
;
2429 if (templhs
.type
== SCALAR
)
2430 templhs
.var
= p
->id
;
2432 templhs
.offset
= p
->offset
;
2434 q
= get_varinfo (temprhs
.var
);
2435 fieldoffset
= p
->offset
- pstart
;
2436 temprhs
.offset
+= fieldoffset
;
2437 process_constraint (new_constraint (templhs
, temprhs
));
2441 /* Handle the structure copy case where we have a structure copy
2442 between a aggregate on the RHS and a dereference of a pointer on
2443 the LHS that is of SIZE (in bits)
2445 For each field of the rhs variable (rhsfield)
2446 lhs.offset = rhsfield->offset
2447 add the constraint lhs = rhsfield
2451 do_lhs_deref_structure_copy (const struct constraint_expr lhs
,
2452 const struct constraint_expr rhs
,
2453 const unsigned HOST_WIDE_INT size
)
2455 varinfo_t p
= get_varinfo (rhs
.var
);
2456 unsigned HOST_WIDE_INT pstart
,last
;
2458 last
= p
->offset
+ size
;
2460 for (; p
&& p
->offset
< last
; p
= p
->next
)
2463 struct constraint_expr templhs
= lhs
;
2464 struct constraint_expr temprhs
= rhs
;
2465 unsigned HOST_WIDE_INT fieldoffset
;
2468 if (temprhs
.type
== SCALAR
)
2469 temprhs
.var
= p
->id
;
2471 temprhs
.offset
= p
->offset
;
2473 q
= get_varinfo (templhs
.var
);
2474 fieldoffset
= p
->offset
- pstart
;
2475 templhs
.offset
+= fieldoffset
;
2476 process_constraint (new_constraint (templhs
, temprhs
));
2480 /* Sometimes, frontends like to give us bad type information. This
2481 function will collapse all the fields from VAR to the end of VAR,
2482 into VAR, so that we treat those fields as a single variable.
2483 We return the variable they were collapsed into. */
2486 collapse_rest_of_var (unsigned int var
)
2488 varinfo_t currvar
= get_varinfo (var
);
2491 for (field
= currvar
->next
; field
; field
= field
->next
)
2494 fprintf (dump_file
, "Type safety: Collapsing var %s into %s\n",
2495 field
->name
, currvar
->name
);
2497 gcc_assert (!field
->collapsed_to
);
2498 field
->collapsed_to
= currvar
;
2501 currvar
->next
= NULL
;
2502 currvar
->size
= currvar
->fullsize
- currvar
->offset
;
2507 /* Handle aggregate copies by expanding into copies of the respective
2508 fields of the structures. */
2511 do_structure_copy (tree lhsop
, tree rhsop
)
2513 struct constraint_expr lhs
, rhs
, tmp
;
2514 VEC (ce_s
, heap
) *lhsc
= NULL
, *rhsc
= NULL
;
2516 unsigned HOST_WIDE_INT lhssize
;
2517 unsigned HOST_WIDE_INT rhssize
;
2519 get_constraint_for (lhsop
, &lhsc
);
2520 get_constraint_for (rhsop
, &rhsc
);
2521 gcc_assert (VEC_length (ce_s
, lhsc
) == 1);
2522 gcc_assert (VEC_length (ce_s
, rhsc
) == 1);
2523 lhs
= *(VEC_last (ce_s
, lhsc
));
2524 rhs
= *(VEC_last (ce_s
, rhsc
));
2526 VEC_free (ce_s
, heap
, lhsc
);
2527 VEC_free (ce_s
, heap
, rhsc
);
2529 /* If we have special var = x, swap it around. */
2530 if (lhs
.var
<= integer_id
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2537 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2538 possible it's something we could handle. However, most cases falling
2539 into this are dealing with transparent unions, which are slightly
2541 if (rhs
.type
== ADDRESSOF
&& !(get_varinfo (rhs
.var
)->is_special_var
))
2543 rhs
.type
= ADDRESSOF
;
2544 rhs
.var
= anything_id
;
2547 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2548 that special var. */
2549 if (rhs
.var
<= integer_id
)
2551 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
2553 struct constraint_expr templhs
= lhs
;
2554 struct constraint_expr temprhs
= rhs
;
2556 if (templhs
.type
== SCALAR
)
2557 templhs
.var
= p
->id
;
2559 templhs
.offset
+= p
->offset
;
2560 process_constraint (new_constraint (templhs
, temprhs
));
2565 tree rhstype
= TREE_TYPE (rhsop
);
2566 tree lhstype
= TREE_TYPE (lhsop
);
2570 lhstypesize
= DECL_P (lhsop
) ? DECL_SIZE (lhsop
) : TYPE_SIZE (lhstype
);
2571 rhstypesize
= DECL_P (rhsop
) ? DECL_SIZE (rhsop
) : TYPE_SIZE (rhstype
);
2573 /* If we have a variably sized types on the rhs or lhs, and a deref
2574 constraint, add the constraint, lhsconstraint = &ANYTHING.
2575 This is conservatively correct because either the lhs is an unknown
2576 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2577 constraint, and every variable it can point to must be unknown sized
2578 anyway, so we don't need to worry about fields at all. */
2579 if ((rhs
.type
== DEREF
&& TREE_CODE (rhstypesize
) != INTEGER_CST
)
2580 || (lhs
.type
== DEREF
&& TREE_CODE (lhstypesize
) != INTEGER_CST
))
2582 rhs
.var
= anything_id
;
2583 rhs
.type
= ADDRESSOF
;
2585 process_constraint (new_constraint (lhs
, rhs
));
2589 /* The size only really matters insofar as we don't set more or less of
2590 the variable. If we hit an unknown size var, the size should be the
2591 whole darn thing. */
2592 if (get_varinfo (rhs
.var
)->is_unknown_size_var
)
2595 rhssize
= TREE_INT_CST_LOW (rhstypesize
);
2597 if (get_varinfo (lhs
.var
)->is_unknown_size_var
)
2600 lhssize
= TREE_INT_CST_LOW (lhstypesize
);
2603 if (rhs
.type
== SCALAR
&& lhs
.type
== SCALAR
)
2605 if (!do_simple_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
)))
2607 lhs
.var
= collapse_rest_of_var (lhs
.var
);
2608 rhs
.var
= collapse_rest_of_var (rhs
.var
);
2613 process_constraint (new_constraint (lhs
, rhs
));
2616 else if (lhs
.type
!= DEREF
&& rhs
.type
== DEREF
)
2617 do_rhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2618 else if (lhs
.type
== DEREF
&& rhs
.type
!= DEREF
)
2619 do_lhs_deref_structure_copy (lhs
, rhs
, MIN (lhssize
, rhssize
));
2622 tree pointedtotype
= lhstype
;
2625 gcc_assert (rhs
.type
== DEREF
&& lhs
.type
== DEREF
);
2626 tmpvar
= create_tmp_var_raw (pointedtotype
, "structcopydereftmp");
2627 do_structure_copy (tmpvar
, rhsop
);
2628 do_structure_copy (lhsop
, tmpvar
);
2633 /* Update related alias information kept in AI. This is used when
2634 building name tags, alias sets and deciding grouping heuristics.
2635 STMT is the statement to process. This function also updates
2636 ADDRESSABLE_VARS. */
2639 update_alias_info (tree stmt
, struct alias_info
*ai
)
2642 use_operand_p use_p
;
2644 enum escape_type stmt_escape_type
= is_escape_site (stmt
);
2646 if (stmt_escape_type
== ESCAPE_TO_CALL
2647 || stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
2649 ai
->num_calls_found
++;
2650 if (stmt_escape_type
== ESCAPE_TO_PURE_CONST
)
2651 ai
->num_pure_const_calls_found
++;
2654 /* Mark all the variables whose address are taken by the statement. */
2655 addr_taken
= addresses_taken (stmt
);
2658 bitmap_ior_into (gimple_addressable_vars (cfun
), addr_taken
);
2660 /* If STMT is an escape point, all the addresses taken by it are
2662 if (stmt_escape_type
!= NO_ESCAPE
)
2667 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
2669 tree rvar
= referenced_var (i
);
2670 if (!unmodifiable_var_p (rvar
))
2671 mark_call_clobbered (rvar
, stmt_escape_type
);
2676 /* Process each operand use. If an operand may be aliased, keep
2677 track of how many times it's being used. For pointers, determine
2678 whether they are dereferenced by the statement, or whether their
2679 value escapes, etc. */
2680 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2684 struct ptr_info_def
*pi
;
2685 bool is_store
, is_potential_deref
;
2686 unsigned num_uses
, num_derefs
;
2688 op
= USE_FROM_PTR (use_p
);
2690 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2691 to the set of addressable variables. */
2692 if (TREE_CODE (op
) == ADDR_EXPR
)
2694 bitmap addressable_vars
= gimple_addressable_vars (cfun
);
2696 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
);
2697 gcc_assert (addressable_vars
);
2699 /* PHI nodes don't have annotations for pinning the set
2700 of addresses taken, so we collect them here.
2702 FIXME, should we allow PHI nodes to have annotations
2703 so that they can be treated like regular statements?
2704 Currently, they are treated as second-class
2706 add_to_addressable_set (TREE_OPERAND (op
, 0),
2711 /* Ignore constants. */
2712 if (TREE_CODE (op
) != SSA_NAME
)
2715 var
= SSA_NAME_VAR (op
);
2716 v_ann
= var_ann (var
);
2718 /* The base variable of an SSA name must be a GIMPLE register, and thus
2719 it cannot be aliased. */
2720 gcc_assert (!may_be_aliased (var
));
2722 /* We are only interested in pointers. */
2723 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
2726 pi
= get_ptr_info (op
);
2728 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2729 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
)))
2731 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (op
));
2732 VEC_safe_push (tree
, heap
, ai
->processed_ptrs
, op
);
2735 /* If STMT is a PHI node, then it will not have pointer
2736 dereferences and it will not be an escape point. */
2737 if (TREE_CODE (stmt
) == PHI_NODE
)
2740 /* Determine whether OP is a dereferenced pointer, and if STMT
2741 is an escape point, whether OP escapes. */
2742 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
2744 /* Handle a corner case involving address expressions of the
2745 form '&PTR->FLD'. The problem with these expressions is that
2746 they do not represent a dereference of PTR. However, if some
2747 other transformation propagates them into an INDIRECT_REF
2748 expression, we end up with '*(&PTR->FLD)' which is folded
2751 So, if the original code had no other dereferences of PTR,
2752 the aliaser will not create memory tags for it, and when
2753 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
2754 memory operations will receive no VDEF/VUSE operands.
2756 One solution would be to have count_uses_and_derefs consider
2757 &PTR->FLD a dereference of PTR. But that is wrong, since it
2758 is not really a dereference but an offset calculation.
2760 What we do here is to recognize these special ADDR_EXPR
2761 nodes. Since these expressions are never GIMPLE values (they
2762 are not GIMPLE invariants), they can only appear on the RHS
2763 of an assignment and their base address is always an
2764 INDIRECT_REF expression. */
2765 is_potential_deref
= false;
2766 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
2767 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == ADDR_EXPR
2768 && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt
, 1)))
2770 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
2771 this represents a potential dereference of PTR. */
2772 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
2773 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
2774 if (TREE_CODE (base
) == INDIRECT_REF
2775 && TREE_OPERAND (base
, 0) == op
)
2776 is_potential_deref
= true;
2779 if (num_derefs
> 0 || is_potential_deref
)
2781 /* Mark OP as dereferenced. In a subsequent pass,
2782 dereferenced pointers that point to a set of
2783 variables will be assigned a name tag to alias
2784 all the variables OP points to. */
2785 pi
->is_dereferenced
= 1;
2787 /* If this is a store operation, mark OP as being
2788 dereferenced to store, otherwise mark it as being
2789 dereferenced to load. */
2791 pointer_set_insert (ai
->dereferenced_ptrs_store
, var
);
2793 pointer_set_insert (ai
->dereferenced_ptrs_load
, var
);
2796 if (stmt_escape_type
!= NO_ESCAPE
&& num_derefs
< num_uses
)
2798 /* If STMT is an escape point and STMT contains at
2799 least one direct use of OP, then the value of OP
2800 escapes and so the pointed-to variables need to
2801 be marked call-clobbered. */
2802 pi
->value_escapes_p
= 1;
2803 pi
->escape_mask
|= stmt_escape_type
;
2805 /* If the statement makes a function call, assume
2806 that pointer OP will be dereferenced in a store
2807 operation inside the called function. */
2808 if (get_call_expr_in (stmt
)
2809 || stmt_escape_type
== ESCAPE_STORED_IN_GLOBAL
)
2811 pointer_set_insert (ai
->dereferenced_ptrs_store
, var
);
2812 pi
->is_dereferenced
= 1;
2817 if (TREE_CODE (stmt
) == PHI_NODE
)
2820 /* Mark stored variables in STMT as being written to and update the
2821 reference counter for potentially aliased symbols in STMT. */
2822 if (stmt_references_memory_p (stmt
) && STORED_SYMS (stmt
))
2826 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt
), 0, i
, bi
)
2827 pointer_set_insert (ai
->written_vars
, referenced_var (i
));
2832 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
2833 Expressions of the type PTR + CST can be handled in two ways:
2835 1- If the constraint for PTR is ADDRESSOF for a non-structure
2836 variable, then we can use it directly because adding or
2837 subtracting a constant may not alter the original ADDRESSOF
2838 constraint (i.e., pointer arithmetic may not legally go outside
2839 an object's boundaries).
2841 2- If the constraint for PTR is ADDRESSOF for a structure variable,
2842 then if CST is a compile-time constant that can be used as an
2843 offset, we can determine which sub-variable will be pointed-to
2846 Return true if the expression is handled. For any other kind of
2847 expression, return false so that each operand can be added as a
2848 separate constraint by the caller. */
2851 handle_ptr_arith (VEC (ce_s
, heap
) *lhsc
, tree expr
)
2854 struct constraint_expr
*c
, *c2
;
2857 VEC (ce_s
, heap
) *temp
= NULL
;
2858 unsigned int rhsoffset
= 0;
2860 if (TREE_CODE (expr
) != PLUS_EXPR
2861 && TREE_CODE (expr
) != MINUS_EXPR
)
2864 op0
= TREE_OPERAND (expr
, 0);
2865 op1
= TREE_OPERAND (expr
, 1);
2867 get_constraint_for (op0
, &temp
);
2868 if (POINTER_TYPE_P (TREE_TYPE (op0
))
2869 && TREE_CODE (op1
) == INTEGER_CST
2870 && TREE_CODE (expr
) == PLUS_EXPR
)
2872 rhsoffset
= TREE_INT_CST_LOW (op1
) * BITS_PER_UNIT
;
2876 for (i
= 0; VEC_iterate (ce_s
, lhsc
, i
, c
); i
++)
2877 for (j
= 0; VEC_iterate (ce_s
, temp
, j
, c2
); j
++)
2879 if (c2
->type
== ADDRESSOF
&& rhsoffset
!= 0)
2881 varinfo_t temp
= get_varinfo (c2
->var
);
2883 /* An access one after the end of an array is valid,
2884 so simply punt on accesses we cannot resolve. */
2885 temp
= first_vi_for_offset (temp
, rhsoffset
);
2892 c2
->offset
= rhsoffset
;
2893 process_constraint (new_constraint (*c
, *c2
));
2896 VEC_free (ce_s
, heap
, temp
);
2902 /* Walk statement T setting up aliasing constraints according to the
2903 references found in T. This function is the main part of the
2904 constraint builder. AI points to auxiliary alias information used
2905 when building alias sets and computing alias grouping heuristics. */
2908 find_func_aliases (tree origt
)
2911 VEC(ce_s
, heap
) *lhsc
= NULL
;
2912 VEC(ce_s
, heap
) *rhsc
= NULL
;
2913 struct constraint_expr
*c
;
2915 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
2916 t
= TREE_OPERAND (t
, 0);
2918 /* Now build constraints expressions. */
2919 if (TREE_CODE (t
) == PHI_NODE
)
2921 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t
))));
2923 /* Only care about pointers and structures containing
2925 if (could_have_pointers (PHI_RESULT (t
)))
2930 /* For a phi node, assign all the arguments to
2932 get_constraint_for (PHI_RESULT (t
), &lhsc
);
2933 for (i
= 0; i
< PHI_NUM_ARGS (t
); i
++)
2936 tree strippedrhs
= PHI_ARG_DEF (t
, i
);
2938 STRIP_NOPS (strippedrhs
);
2939 rhstype
= TREE_TYPE (strippedrhs
);
2940 get_constraint_for (PHI_ARG_DEF (t
, i
), &rhsc
);
2942 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
2944 struct constraint_expr
*c2
;
2945 while (VEC_length (ce_s
, rhsc
) > 0)
2947 c2
= VEC_last (ce_s
, rhsc
);
2948 process_constraint (new_constraint (*c
, *c2
));
2949 VEC_pop (ce_s
, rhsc
);
2955 /* In IPA mode, we need to generate constraints to pass call
2956 arguments through their calls. There are two case, either a
2957 modify_expr when we are returning a value, or just a plain
2958 call_expr when we are not. */
2959 else if (in_ipa_mode
2960 && ((TREE_CODE (t
) == GIMPLE_MODIFY_STMT
2961 && TREE_CODE (GIMPLE_STMT_OPERAND (t
, 1)) == CALL_EXPR
2962 && !(call_expr_flags (GIMPLE_STMT_OPERAND (t
, 1))
2963 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
2964 || (TREE_CODE (t
) == CALL_EXPR
2965 && !(call_expr_flags (t
)
2966 & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))))
2975 if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
2977 lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
2978 rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
2985 decl
= get_callee_fndecl (rhsop
);
2987 /* If we can directly resolve the function being called, do so.
2988 Otherwise, it must be some sort of indirect expression that
2989 we should still be able to handle. */
2992 varid
= get_id_for_tree (decl
);
2996 decl
= TREE_OPERAND (rhsop
, 0);
2997 varid
= get_id_for_tree (decl
);
3000 /* Assign all the passed arguments to the appropriate incoming
3001 parameters of the function. */
3002 fi
= get_varinfo (varid
);
3003 arglist
= TREE_OPERAND (rhsop
, 1);
3005 for (;arglist
; arglist
= TREE_CHAIN (arglist
))
3007 tree arg
= TREE_VALUE (arglist
);
3008 struct constraint_expr lhs
;
3009 struct constraint_expr
*rhsp
;
3011 get_constraint_for (arg
, &rhsc
);
3012 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3021 lhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3024 while (VEC_length (ce_s
, rhsc
) != 0)
3026 rhsp
= VEC_last (ce_s
, rhsc
);
3027 process_constraint (new_constraint (lhs
, *rhsp
));
3028 VEC_pop (ce_s
, rhsc
);
3032 /* If we are returning a value, assign it to the result. */
3035 struct constraint_expr rhs
;
3036 struct constraint_expr
*lhsp
;
3039 get_constraint_for (lhsop
, &lhsc
);
3040 if (TREE_CODE (decl
) != FUNCTION_DECL
)
3049 rhs
.var
= first_vi_for_offset (fi
, i
)->id
;
3052 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, lhsp
); j
++)
3053 process_constraint (new_constraint (*lhsp
, rhs
));
3056 /* Otherwise, just a regular assignment statement. */
3057 else if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
3059 tree lhsop
= GIMPLE_STMT_OPERAND (t
, 0);
3060 tree rhsop
= GIMPLE_STMT_OPERAND (t
, 1);
3063 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop
))
3064 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
)
3065 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop
))
3066 || TREE_CODE (TREE_TYPE (lhsop
)) == COMPLEX_TYPE
))
3068 do_structure_copy (lhsop
, rhsop
);
3072 /* Only care about operations with pointers, structures
3073 containing pointers, dereferences, and call expressions. */
3074 if (could_have_pointers (lhsop
)
3075 || TREE_CODE (rhsop
) == CALL_EXPR
)
3077 get_constraint_for (lhsop
, &lhsc
);
3078 switch (TREE_CODE_CLASS (TREE_CODE (rhsop
)))
3080 /* RHS that consist of unary operations,
3081 exceptional types, or bare decls/constants, get
3082 handled directly by get_constraint_for. */
3084 case tcc_declaration
:
3086 case tcc_exceptional
:
3087 case tcc_expression
:
3092 get_constraint_for (rhsop
, &rhsc
);
3093 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3095 struct constraint_expr
*c2
;
3098 for (k
= 0; VEC_iterate (ce_s
, rhsc
, k
, c2
); k
++)
3099 process_constraint (new_constraint (*c
, *c2
));
3107 /* For pointer arithmetic of the form
3108 PTR + CST, we can simply use PTR's
3109 constraint because pointer arithmetic is
3110 not allowed to go out of bounds. */
3111 if (handle_ptr_arith (lhsc
, rhsop
))
3116 /* Otherwise, walk each operand. Notice that we
3117 can't use the operand interface because we need
3118 to process expressions other than simple operands
3119 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3121 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (rhsop
)); i
++)
3123 tree op
= TREE_OPERAND (rhsop
, i
);
3126 gcc_assert (VEC_length (ce_s
, rhsc
) == 0);
3127 get_constraint_for (op
, &rhsc
);
3128 for (j
= 0; VEC_iterate (ce_s
, lhsc
, j
, c
); j
++)
3130 struct constraint_expr
*c2
;
3131 while (VEC_length (ce_s
, rhsc
) > 0)
3133 c2
= VEC_last (ce_s
, rhsc
);
3134 process_constraint (new_constraint (*c
, *c2
));
3135 VEC_pop (ce_s
, rhsc
);
3144 /* After promoting variables and computing aliasing we will
3145 need to re-scan most statements. FIXME: Try to minimize the
3146 number of statements re-scanned. It's not really necessary to
3147 re-scan *all* statements. */
3148 mark_stmt_modified (origt
);
3149 VEC_free (ce_s
, heap
, rhsc
);
3150 VEC_free (ce_s
, heap
, lhsc
);
3154 /* Find the first varinfo in the same variable as START that overlaps with
3156 Effectively, walk the chain of fields for the variable START to find the
3157 first field that overlaps with OFFSET.
3158 Return NULL if we can't find one. */
3161 first_vi_for_offset (varinfo_t start
, unsigned HOST_WIDE_INT offset
)
3163 varinfo_t curr
= start
;
3166 /* We may not find a variable in the field list with the actual
3167 offset when when we have glommed a structure to a variable.
3168 In that case, however, offset should still be within the size
3170 if (offset
>= curr
->offset
&& offset
< (curr
->offset
+ curr
->size
))
3178 /* Insert the varinfo FIELD into the field list for BASE, at the front
3182 insert_into_field_list (varinfo_t base
, varinfo_t field
)
3184 varinfo_t prev
= base
;
3185 varinfo_t curr
= base
->next
;
3191 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3195 insert_into_field_list_sorted (varinfo_t base
, varinfo_t field
)
3197 varinfo_t prev
= base
;
3198 varinfo_t curr
= base
->next
;
3209 if (field
->offset
<= curr
->offset
)
3214 field
->next
= prev
->next
;
3219 /* qsort comparison function for two fieldoff's PA and PB */
3222 fieldoff_compare (const void *pa
, const void *pb
)
3224 const fieldoff_s
*foa
= (const fieldoff_s
*)pa
;
3225 const fieldoff_s
*fob
= (const fieldoff_s
*)pb
;
3226 HOST_WIDE_INT foasize
, fobsize
;
3228 if (foa
->offset
!= fob
->offset
)
3229 return foa
->offset
- fob
->offset
;
3231 foasize
= TREE_INT_CST_LOW (foa
->size
);
3232 fobsize
= TREE_INT_CST_LOW (fob
->size
);
3233 return foasize
- fobsize
;
3236 /* Sort a fieldstack according to the field offset and sizes. */
3238 sort_fieldstack (VEC(fieldoff_s
,heap
) *fieldstack
)
3240 qsort (VEC_address (fieldoff_s
, fieldstack
),
3241 VEC_length (fieldoff_s
, fieldstack
),
3242 sizeof (fieldoff_s
),
3246 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3247 of TYPE onto fieldstack, recording their offsets along the way.
3248 OFFSET is used to keep track of the offset in this entire structure, rather
3249 than just the immediately containing structure. Returns the number
3251 HAS_UNION is set to true if we find a union type as a field of
3255 push_fields_onto_fieldstack (tree type
, VEC(fieldoff_s
,heap
) **fieldstack
,
3256 HOST_WIDE_INT offset
, bool *has_union
)
3261 if (TREE_CODE (type
) == COMPLEX_TYPE
)
3263 fieldoff_s
*real_part
, *img_part
;
3264 real_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3265 real_part
->type
= TREE_TYPE (type
);
3266 real_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3267 real_part
->offset
= offset
;
3268 real_part
->decl
= NULL_TREE
;
3270 img_part
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3271 img_part
->type
= TREE_TYPE (type
);
3272 img_part
->size
= TYPE_SIZE (TREE_TYPE (type
));
3273 img_part
->offset
= offset
+ TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type
)));
3274 img_part
->decl
= NULL_TREE
;
3279 if (TREE_CODE (type
) == ARRAY_TYPE
)
3281 tree sz
= TYPE_SIZE (type
);
3282 tree elsz
= TYPE_SIZE (TREE_TYPE (type
));
3287 || ! host_integerp (sz
, 1)
3288 || TREE_INT_CST_LOW (sz
) == 0
3290 || ! host_integerp (elsz
, 1)
3291 || TREE_INT_CST_LOW (elsz
) == 0)
3294 nr
= TREE_INT_CST_LOW (sz
) / TREE_INT_CST_LOW (elsz
);
3295 if (nr
> SALIAS_MAX_ARRAY_ELEMENTS
)
3298 for (i
= 0; i
< nr
; ++i
)
3304 && (TREE_CODE (TREE_TYPE (type
)) == QUAL_UNION_TYPE
3305 || TREE_CODE (TREE_TYPE (type
)) == UNION_TYPE
))
3308 if (!AGGREGATE_TYPE_P (TREE_TYPE (type
))) /* var_can_have_subvars */
3310 else if (!(pushed
= push_fields_onto_fieldstack
3311 (TREE_TYPE (type
), fieldstack
,
3312 offset
+ i
* TREE_INT_CST_LOW (elsz
), has_union
)))
3313 /* Empty structures may have actual size, like in C++. So
3314 see if we didn't push any subfields and the size is
3315 nonzero, push the field onto the stack */
3322 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3323 pair
->type
= TREE_TYPE (type
);
3325 pair
->decl
= NULL_TREE
;
3326 pair
->offset
= offset
+ i
* TREE_INT_CST_LOW (elsz
);
3336 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
3337 if (TREE_CODE (field
) == FIELD_DECL
)
3343 && (TREE_CODE (TREE_TYPE (field
)) == QUAL_UNION_TYPE
3344 || TREE_CODE (TREE_TYPE (field
)) == UNION_TYPE
))
3347 if (!var_can_have_subvars (field
))
3349 else if (!(pushed
= push_fields_onto_fieldstack
3350 (TREE_TYPE (field
), fieldstack
,
3351 offset
+ bitpos_of_field (field
), has_union
))
3352 && DECL_SIZE (field
)
3353 && !integer_zerop (DECL_SIZE (field
)))
3354 /* Empty structures may have actual size, like in C++. So
3355 see if we didn't push any subfields and the size is
3356 nonzero, push the field onto the stack */
3363 pair
= VEC_safe_push (fieldoff_s
, heap
, *fieldstack
, NULL
);
3364 pair
->type
= TREE_TYPE (field
);
3365 pair
->size
= DECL_SIZE (field
);
3367 pair
->offset
= offset
+ bitpos_of_field (field
);
3377 /* Create a constraint from ANYTHING variable to VI. */
3379 make_constraint_from_anything (varinfo_t vi
)
3381 struct constraint_expr lhs
, rhs
;
3387 rhs
.var
= anything_id
;
3389 rhs
.type
= INCLUDES
;
3390 process_constraint (new_constraint (lhs
, rhs
));
3393 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3394 if it is a varargs function. */
3397 count_num_arguments (tree decl
, bool *is_varargs
)
3402 for (t
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
3406 if (TREE_VALUE (t
) == void_type_node
)
3416 /* Creation function node for DECL, using NAME, and return the index
3417 of the variable we've created for the function. */
3420 create_function_info_for (tree decl
, const char *name
)
3422 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3426 bool is_varargs
= false;
3428 /* Create the variable info. */
3430 vi
= new_var_info (decl
, index
, name
, index
);
3435 vi
->fullsize
= count_num_arguments (decl
, &is_varargs
) + 1;
3436 insert_id_for_tree (vi
->decl
, index
);
3437 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3441 /* If it's varargs, we don't know how many arguments it has, so we
3448 vi
->is_unknown_size_var
= true;
3453 arg
= DECL_ARGUMENTS (decl
);
3455 /* Set up variables for each argument. */
3456 for (i
= 1; i
< vi
->fullsize
; i
++)
3459 const char *newname
;
3461 unsigned int newindex
;
3462 tree argdecl
= decl
;
3467 newindex
= VEC_length (varinfo_t
, varmap
);
3468 asprintf (&tempname
, "%s.arg%d", name
, i
-1);
3469 newname
= ggc_strdup (tempname
);
3472 argvi
= new_var_info (argdecl
, newindex
,newname
, newindex
);
3473 argvi
->decl
= argdecl
;
3474 VEC_safe_push (varinfo_t
, heap
, varmap
, argvi
);
3477 argvi
->fullsize
= vi
->fullsize
;
3478 argvi
->has_union
= false;
3479 insert_into_field_list_sorted (vi
, argvi
);
3480 stats
.total_vars
++;
3483 insert_id_for_tree (arg
, newindex
);
3484 arg
= TREE_CHAIN (arg
);
3488 /* Create a variable for the return var. */
3489 if (DECL_RESULT (decl
) != NULL
3490 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl
))))
3493 const char *newname
;
3495 unsigned int newindex
;
3496 tree resultdecl
= decl
;
3500 if (DECL_RESULT (decl
))
3501 resultdecl
= DECL_RESULT (decl
);
3503 newindex
= VEC_length (varinfo_t
, varmap
);
3504 asprintf (&tempname
, "%s.result", name
);
3505 newname
= ggc_strdup (tempname
);
3508 resultvi
= new_var_info (resultdecl
, newindex
, newname
, newindex
);
3509 resultvi
->decl
= resultdecl
;
3510 VEC_safe_push (varinfo_t
, heap
, varmap
, resultvi
);
3511 resultvi
->offset
= i
;
3513 resultvi
->fullsize
= vi
->fullsize
;
3514 resultvi
->has_union
= false;
3515 insert_into_field_list_sorted (vi
, resultvi
);
3516 stats
.total_vars
++;
3517 if (DECL_RESULT (decl
))
3518 insert_id_for_tree (DECL_RESULT (decl
), newindex
);
3524 /* Return true if FIELDSTACK contains fields that overlap.
3525 FIELDSTACK is assumed to be sorted by offset. */
3528 check_for_overlaps (VEC (fieldoff_s
,heap
) *fieldstack
)
3530 fieldoff_s
*fo
= NULL
;
3532 HOST_WIDE_INT lastoffset
= -1;
3534 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3536 if (fo
->offset
== lastoffset
)
3538 lastoffset
= fo
->offset
;
3543 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3544 This will also create any varinfo structures necessary for fields
3548 create_variable_info_for (tree decl
, const char *name
)
3550 unsigned int index
= VEC_length (varinfo_t
, varmap
);
3552 tree
decltype = TREE_TYPE (decl
);
3553 tree declsize
= DECL_P (decl
) ? DECL_SIZE (decl
) : TYPE_SIZE (decltype);
3554 bool notokay
= false;
3556 bool is_global
= DECL_P (decl
) ? is_global_var (decl
) : false;
3557 VEC (fieldoff_s
,heap
) *fieldstack
= NULL
;
3559 if (TREE_CODE (decl
) == FUNCTION_DECL
&& in_ipa_mode
)
3560 return create_function_info_for (decl
, name
);
3562 hasunion
= TREE_CODE (decltype) == UNION_TYPE
3563 || TREE_CODE (decltype) == QUAL_UNION_TYPE
;
3564 if (var_can_have_subvars (decl
) && use_field_sensitive
&& !hasunion
)
3566 push_fields_onto_fieldstack (decltype, &fieldstack
, 0, &hasunion
);
3569 VEC_free (fieldoff_s
, heap
, fieldstack
);
3575 /* If the variable doesn't have subvars, we may end up needing to
3576 sort the field list and create fake variables for all the
3578 vi
= new_var_info (decl
, index
, name
, index
);
3581 vi
->has_union
= hasunion
;
3583 || TREE_CODE (declsize
) != INTEGER_CST
3584 || TREE_CODE (decltype) == UNION_TYPE
3585 || TREE_CODE (decltype) == QUAL_UNION_TYPE
)
3587 vi
->is_unknown_size_var
= true;
3593 vi
->fullsize
= TREE_INT_CST_LOW (declsize
);
3594 vi
->size
= vi
->fullsize
;
3597 insert_id_for_tree (vi
->decl
, index
);
3598 VEC_safe_push (varinfo_t
, heap
, varmap
, vi
);
3599 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3600 make_constraint_from_anything (vi
);
3603 if (use_field_sensitive
3605 && !vi
->is_unknown_size_var
3606 && var_can_have_subvars (decl
)
3607 && VEC_length (fieldoff_s
, fieldstack
) <= MAX_FIELDS_FOR_FIELD_SENSITIVE
)
3609 unsigned int newindex
= VEC_length (varinfo_t
, varmap
);
3610 fieldoff_s
*fo
= NULL
;
3613 for (i
= 0; !notokay
&& VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3616 || TREE_CODE (fo
->size
) != INTEGER_CST
3624 /* We can't sort them if we have a field with a variable sized type,
3625 which will make notokay = true. In that case, we are going to return
3626 without creating varinfos for the fields anyway, so sorting them is a
3630 sort_fieldstack (fieldstack
);
3631 /* Due to some C++ FE issues, like PR 22488, we might end up
3632 what appear to be overlapping fields even though they,
3633 in reality, do not overlap. Until the C++ FE is fixed,
3634 we will simply disable field-sensitivity for these cases. */
3635 notokay
= check_for_overlaps (fieldstack
);
3639 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
3640 fo
= VEC_index (fieldoff_s
, fieldstack
, 0);
3642 if (fo
== NULL
|| notokay
)
3644 vi
->is_unknown_size_var
= 1;
3647 VEC_free (fieldoff_s
, heap
, fieldstack
);
3651 vi
->size
= TREE_INT_CST_LOW (fo
->size
);
3652 vi
->offset
= fo
->offset
;
3653 for (i
= VEC_length (fieldoff_s
, fieldstack
) - 1;
3654 i
>= 1 && VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
);
3658 const char *newname
= "NULL";
3661 newindex
= VEC_length (varinfo_t
, varmap
);
3665 asprintf (&tempname
, "%s.%s",
3666 vi
->name
, alias_get_name (fo
->decl
));
3668 asprintf (&tempname
, "%s." HOST_WIDE_INT_PRINT_DEC
,
3669 vi
->name
, fo
->offset
);
3670 newname
= ggc_strdup (tempname
);
3673 newvi
= new_var_info (decl
, newindex
, newname
, newindex
);
3674 newvi
->offset
= fo
->offset
;
3675 newvi
->size
= TREE_INT_CST_LOW (fo
->size
);
3676 newvi
->fullsize
= vi
->fullsize
;
3677 insert_into_field_list (vi
, newvi
);
3678 VEC_safe_push (varinfo_t
, heap
, varmap
, newvi
);
3679 if (is_global
&& (!flag_whole_program
|| !in_ipa_mode
))
3680 make_constraint_from_anything (newvi
);
3684 VEC_free (fieldoff_s
, heap
, fieldstack
);
3689 /* Print out the points-to solution for VAR to FILE. */
3692 dump_solution_for_var (FILE *file
, unsigned int var
)
3694 varinfo_t vi
= get_varinfo (var
);
3698 if (vi
->node
!= var
)
3700 varinfo_t vipt
= get_varinfo (vi
->node
);
3701 fprintf (file
, "%s = same as %s\n", vi
->name
, vipt
->name
);
3705 fprintf (file
, "%s = { ", vi
->name
);
3706 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi
->node
)->solution
, 0, i
, bi
)
3708 fprintf (file
, "%s ", get_varinfo (i
)->name
);
3710 fprintf (file
, "}\n");
3714 /* Print the points-to solution for VAR to stdout. */
3717 debug_solution_for_var (unsigned int var
)
3719 dump_solution_for_var (stdout
, var
);
3722 /* Create varinfo structures for all of the variables in the
3723 function for intraprocedural mode. */
3726 intra_create_variable_infos (void)
3729 struct constraint_expr lhs
, rhs
;
3731 /* For each incoming pointer argument arg, ARG = ANYTHING or a
3732 dummy variable if flag_argument_noalias > 2. */
3733 for (t
= DECL_ARGUMENTS (current_function_decl
); t
; t
= TREE_CHAIN (t
))
3736 unsigned int arg_id
;
3738 if (!could_have_pointers (t
))
3741 arg_id
= get_id_for_tree (t
);
3743 /* With flag_argument_noalias greater than two means that the incoming
3744 argument cannot alias anything except for itself so create a HEAP
3746 if (POINTER_TYPE_P (TREE_TYPE (t
))
3747 && flag_argument_noalias
> 2)
3750 tree heapvar
= heapvar_lookup (t
);
3755 lhs
.var
= get_id_for_tree (t
);
3757 if (heapvar
== NULL_TREE
)
3759 heapvar
= create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t
)),
3761 get_var_ann (heapvar
)->is_heapvar
= 1;
3762 DECL_EXTERNAL (heapvar
) = 1;
3763 if (gimple_referenced_vars (cfun
))
3764 add_referenced_var (heapvar
);
3765 heapvar_insert (t
, heapvar
);
3767 id
= get_id_for_tree (heapvar
);
3768 vi
= get_varinfo (id
);
3769 vi
->is_artificial_var
= 1;
3770 vi
->is_heap_var
= 1;
3772 rhs
.type
= INCLUDES
;
3774 for (p
= get_varinfo (lhs
.var
); p
; p
= p
->next
)
3776 struct constraint_expr temp
= lhs
;
3778 process_constraint (new_constraint (temp
, rhs
));
3783 for (p
= get_varinfo (arg_id
); p
; p
= p
->next
)
3784 make_constraint_from_anything (p
);
3789 /* Set bits in INTO corresponding to the variable uids in solution set
3790 FROM, which came from variable PTR.
3791 For variables that are actually dereferenced, we also use type
3792 based alias analysis to prune the points-to sets. */
3795 set_uids_in_ptset (tree ptr
, bitmap into
, bitmap from
)
3800 HOST_WIDE_INT ptr_alias_set
= get_alias_set (TREE_TYPE (ptr
));
3802 EXECUTE_IF_SET_IN_BITMAP (from
, 0, i
, bi
)
3804 varinfo_t vi
= get_varinfo (i
);
3805 unsigned HOST_WIDE_INT var_alias_set
;
3807 /* The only artificial variables that are allowed in a may-alias
3808 set are heap variables. */
3809 if (vi
->is_artificial_var
&& !vi
->is_heap_var
)
3812 if (vi
->has_union
&& get_subvars_for_var (vi
->decl
) != NULL
)
3814 /* Variables containing unions may need to be converted to
3815 their SFT's, because SFT's can have unions and we cannot. */
3816 for (sv
= get_subvars_for_var (vi
->decl
); sv
; sv
= sv
->next
)
3817 bitmap_set_bit (into
, DECL_UID (sv
->var
));
3819 else if (TREE_CODE (vi
->decl
) == VAR_DECL
3820 || TREE_CODE (vi
->decl
) == PARM_DECL
)
3822 if (var_can_have_subvars (vi
->decl
)
3823 && get_subvars_for_var (vi
->decl
))
3825 /* If VI->DECL is an aggregate for which we created
3826 SFTs, add the SFT corresponding to VI->OFFSET. */
3827 tree sft
= get_subvar_at (vi
->decl
, vi
->offset
);
3830 var_alias_set
= get_alias_set (sft
);
3831 if (!vi
->directly_dereferenced
3832 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
3833 bitmap_set_bit (into
, DECL_UID (sft
));
3838 /* Otherwise, just add VI->DECL to the alias set.
3839 Don't type prune artificial vars. */
3840 if (vi
->is_artificial_var
)
3841 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
3844 var_alias_set
= get_alias_set (vi
->decl
);
3845 if (!vi
->directly_dereferenced
3846 || alias_sets_conflict_p (ptr_alias_set
, var_alias_set
))
3847 bitmap_set_bit (into
, DECL_UID (vi
->decl
));
3855 static bool have_alias_info
= false;
3857 /* The list of SMT's that are in use by our pointer variables. This
3858 is the set of SMT's for all pointers that can point to anything. */
3859 static bitmap used_smts
;
3861 /* Due to the ordering of points-to set calculation and SMT
3862 calculation being a bit co-dependent, we can't just calculate SMT
3863 used info whenever we want, we have to calculate it around the time
3864 that find_what_p_points_to is called. */
3866 /* Mark which SMT's are in use by points-to anything variables. */
3869 set_used_smts (void)
3873 used_smts
= BITMAP_ALLOC (&ptabitmap_obstack
);
3875 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, vi
); i
++)
3877 tree var
= vi
->decl
;
3880 struct ptr_info_def
*pi
= NULL
;
3882 /* For parm decls, the pointer info may be under the default
3884 if (TREE_CODE (vi
->decl
) == PARM_DECL
3885 && gimple_default_def (cfun
, var
))
3886 pi
= SSA_NAME_PTR_INFO (gimple_default_def (cfun
, var
));
3887 else if (TREE_CODE (var
) == SSA_NAME
)
3888 pi
= SSA_NAME_PTR_INFO (var
);
3890 /* Skip the special variables and those without their own
3892 if (vi
->is_special_var
|| vi
->node
!= vi
->id
|| !SSA_VAR_P (var
)
3893 || (pi
&& !pi
->is_dereferenced
)
3894 || (TREE_CODE (var
) == VAR_DECL
&& !may_be_aliased (var
))
3895 || !POINTER_TYPE_P (TREE_TYPE (var
)))
3898 if (TREE_CODE (var
) == SSA_NAME
)
3899 var
= SSA_NAME_VAR (var
);
3905 smt
= va
->symbol_mem_tag
;
3906 if (smt
&& bitmap_bit_p (vi
->solution
, anything_id
))
3907 bitmap_set_bit (used_smts
, DECL_UID (smt
));
3911 /* Merge the necessary SMT's into the solution set for VI, which is
3912 P's varinfo. This involves merging all SMT's that are a subset of
3913 the SMT necessary for P. */
3916 merge_smts_into (tree p
, varinfo_t vi
)
3921 VEC(tree
, gc
) *aliases
;
3924 if (TREE_CODE (p
) == SSA_NAME
)
3925 var
= SSA_NAME_VAR (p
);
3927 smt
= var_ann (var
)->symbol_mem_tag
;
3930 HOST_WIDE_INT smtset
= get_alias_set (TREE_TYPE (smt
));
3932 /* Need to set the SMT subsets first before this
3933 will work properly. */
3934 bitmap_set_bit (vi
->finished_solution
, DECL_UID (smt
));
3935 EXECUTE_IF_SET_IN_BITMAP (used_smts
, 0, i
, bi
)
3937 tree newsmt
= referenced_var (i
);
3938 tree newsmttype
= TREE_TYPE (newsmt
);
3940 if (alias_set_subset_of (get_alias_set (newsmttype
),
3942 bitmap_set_bit (vi
->finished_solution
, i
);
3945 aliases
= var_ann (smt
)->may_aliases
;
3950 for (k
= 0; VEC_iterate (tree
, aliases
, k
, al
); k
++)
3951 bitmap_set_bit (vi
->finished_solution
,
3957 /* Given a pointer variable P, fill in its points-to set, or return
3959 Rather than return false for variables that point-to anything, we
3960 instead find the corresponding SMT, and merge in it's aliases. In
3961 addition to these aliases, we also set the bits for the SMT's
3962 themselves and their subsets, as SMT's are still in use by
3963 non-SSA_NAME's, and pruning may eliminate every one of their
3964 aliases. In such a case, if we did not include the right set of
3965 SMT's in the points-to set of the variable, we'd end up with
3966 statements that do not conflict but should. */
3969 find_what_p_points_to (tree p
)
3971 unsigned int id
= 0;
3974 if (!have_alias_info
)
3977 /* For parameters, get at the points-to set for the actual parm
3979 if (TREE_CODE (p
) == SSA_NAME
3980 && TREE_CODE (SSA_NAME_VAR (p
)) == PARM_DECL
3981 && SSA_NAME_IS_DEFAULT_DEF (p
))
3982 lookup_p
= SSA_NAME_VAR (p
);
3984 if (lookup_id_for_tree (lookup_p
, &id
))
3986 varinfo_t vi
= get_varinfo (id
);
3988 if (vi
->is_artificial_var
)
3991 /* See if this is a field or a structure. */
3992 if (vi
->size
!= vi
->fullsize
)
3994 /* Nothing currently asks about structure fields directly,
3995 but when they do, we need code here to hand back the
3997 if (!var_can_have_subvars (vi
->decl
)
3998 || get_subvars_for_var (vi
->decl
) == NULL
)
4003 struct ptr_info_def
*pi
= get_ptr_info (p
);
4006 bool was_pt_anything
= false;
4008 if (!pi
->is_dereferenced
)
4011 /* This variable may have been collapsed, let's get the real
4013 vi
= get_varinfo (vi
->node
);
4015 /* Translate artificial variables into SSA_NAME_PTR_INFO
4017 EXECUTE_IF_SET_IN_BITMAP (vi
->solution
, 0, i
, bi
)
4019 varinfo_t vi
= get_varinfo (i
);
4021 if (vi
->is_artificial_var
)
4023 /* FIXME. READONLY should be handled better so that
4024 flow insensitive aliasing can disregard writable
4026 if (vi
->id
== nothing_id
)
4028 else if (vi
->id
== anything_id
)
4029 was_pt_anything
= 1;
4030 else if (vi
->id
== readonly_id
)
4031 was_pt_anything
= 1;
4032 else if (vi
->id
== integer_id
)
4033 was_pt_anything
= 1;
4034 else if (vi
->is_heap_var
)
4035 pi
->pt_global_mem
= 1;
4039 /* Share the final set of variables between the SSA_NAME
4040 pointer infos for collapsed nodes that are collapsed to
4041 non-special variables. This is because special vars have
4042 no real types associated with them, so while we know the
4043 pointers are equivalent to them, we need to generate the
4044 solution separately since it will include SMT's from the
4045 original non-collapsed variable. */
4046 if (!vi
->is_special_var
&& vi
->finished_solution
)
4048 pi
->pt_vars
= vi
->finished_solution
;
4052 vi
->finished_solution
= BITMAP_GGC_ALLOC ();
4054 /* Instead of using pt_anything, we instead merge in the SMT
4055 aliases for the underlying SMT. */
4056 if (was_pt_anything
)
4058 merge_smts_into (p
, vi
);
4059 pi
->pt_global_mem
= 1;
4062 set_uids_in_ptset (vi
->decl
, vi
->finished_solution
, vi
->solution
);
4063 pi
->pt_vars
= vi
->finished_solution
;
4066 if (bitmap_empty_p (pi
->pt_vars
))
4078 /* Dump points-to information to OUTFILE. */
4081 dump_sa_points_to_info (FILE *outfile
)
4085 fprintf (outfile
, "\nPoints-to sets\n\n");
4087 if (dump_flags
& TDF_STATS
)
4089 fprintf (outfile
, "Stats:\n");
4090 fprintf (outfile
, "Total vars: %d\n", stats
.total_vars
);
4091 fprintf (outfile
, "Statically unified vars: %d\n",
4092 stats
.unified_vars_static
);
4093 fprintf (outfile
, "Collapsed vars: %d\n", stats
.collapsed_vars
);
4094 fprintf (outfile
, "Dynamically unified vars: %d\n",
4095 stats
.unified_vars_dynamic
);
4096 fprintf (outfile
, "Iterations: %d\n", stats
.iterations
);
4097 fprintf (outfile
, "Number of edges: %d\n", stats
.num_edges
);
4100 for (i
= 0; i
< VEC_length (varinfo_t
, varmap
); i
++)
4101 dump_solution_for_var (outfile
, i
);
4105 /* Debug points-to information to stderr. */
4108 debug_sa_points_to_info (void)
4110 dump_sa_points_to_info (stderr
);
4114 /* Initialize the always-existing constraint variables for NULL
4115 ANYTHING, READONLY, and INTEGER */
4118 init_base_vars (void)
4120 struct constraint_expr lhs
, rhs
;
4122 /* Create the NULL variable, used to represent that a variable points
4124 nothing_tree
= create_tmp_var_raw (void_type_node
, "NULL");
4125 var_nothing
= new_var_info (nothing_tree
, 0, "NULL", 0);
4126 insert_id_for_tree (nothing_tree
, 0);
4127 var_nothing
->is_artificial_var
= 1;
4128 var_nothing
->offset
= 0;
4129 var_nothing
->size
= ~0;
4130 var_nothing
->fullsize
= ~0;
4131 var_nothing
->is_special_var
= 1;
4133 VEC_safe_push (varinfo_t
, heap
, varmap
, var_nothing
);
4135 /* Create the ANYTHING variable, used to represent that a variable
4136 points to some unknown piece of memory. */
4137 anything_tree
= create_tmp_var_raw (void_type_node
, "ANYTHING");
4138 var_anything
= new_var_info (anything_tree
, 1, "ANYTHING", 1);
4139 insert_id_for_tree (anything_tree
, 1);
4140 var_anything
->is_artificial_var
= 1;
4141 var_anything
->size
= ~0;
4142 var_anything
->offset
= 0;
4143 var_anything
->next
= NULL
;
4144 var_anything
->fullsize
= ~0;
4145 var_anything
->is_special_var
= 1;
4148 /* Anything points to anything. This makes deref constraints just
4149 work in the presence of linked list and other p = *p type loops,
4150 by saying that *ANYTHING = ANYTHING. */
4151 VEC_safe_push (varinfo_t
, heap
, varmap
, var_anything
);
4153 lhs
.var
= anything_id
;
4155 rhs
.type
= INCLUDES
;
4156 rhs
.var
= anything_id
;
4158 var_anything
->address_taken
= true;
4160 /* This specifically does not use process_constraint because
4161 process_constraint ignores all anything = anything constraints, since all
4162 but this one are redundant. */
4163 VEC_safe_push (constraint_t
, heap
, constraints
, new_constraint (lhs
, rhs
));
4165 /* Create the READONLY variable, used to represent that a variable
4166 points to readonly memory. */
4167 readonly_tree
= create_tmp_var_raw (void_type_node
, "READONLY");
4168 var_readonly
= new_var_info (readonly_tree
, 2, "READONLY", 2);
4169 var_readonly
->is_artificial_var
= 1;
4170 var_readonly
->offset
= 0;
4171 var_readonly
->size
= ~0;
4172 var_readonly
->fullsize
= ~0;
4173 var_readonly
->next
= NULL
;
4174 var_readonly
->is_special_var
= 1;
4175 insert_id_for_tree (readonly_tree
, 2);
4177 VEC_safe_push (varinfo_t
, heap
, varmap
, var_readonly
);
4179 /* readonly memory points to anything, in order to make deref
4180 easier. In reality, it points to anything the particular
4181 readonly variable can point to, but we don't track this
4184 lhs
.var
= readonly_id
;
4186 rhs
.type
= INCLUDES
;
4187 rhs
.var
= anything_id
;
4190 process_constraint (new_constraint (lhs
, rhs
));
4192 /* Create the INTEGER variable, used to represent that a variable points
4194 integer_tree
= create_tmp_var_raw (void_type_node
, "INTEGER");
4195 var_integer
= new_var_info (integer_tree
, 3, "INTEGER", 3);
4196 insert_id_for_tree (integer_tree
, 3);
4197 var_integer
->is_artificial_var
= 1;
4198 var_integer
->size
= ~0;
4199 var_integer
->fullsize
= ~0;
4200 var_integer
->offset
= 0;
4201 var_integer
->next
= NULL
;
4202 var_integer
->is_special_var
= 1;
4204 VEC_safe_push (varinfo_t
, heap
, varmap
, var_integer
);
4206 /* INTEGER = ANYTHING, because we don't know where a dereference of
4207 a random integer will point to. */
4209 lhs
.var
= integer_id
;
4211 rhs
.type
= INCLUDES
;
4212 rhs
.var
= anything_id
;
4214 process_constraint (new_constraint (lhs
, rhs
));
4217 /* Initialize things necessary to perform PTA */
4220 init_alias_vars (void)
4222 bitmap_obstack_initialize (&ptabitmap_obstack
);
4223 bitmap_obstack_initialize (&predbitmap_obstack
);
4225 constraint_pool
= create_alloc_pool ("Constraint pool",
4226 sizeof (struct constraint
), 30);
4227 variable_info_pool
= create_alloc_pool ("Variable info pool",
4228 sizeof (struct variable_info
), 30);
4229 constraints
= VEC_alloc (constraint_t
, heap
, 8);
4230 varmap
= VEC_alloc (varinfo_t
, heap
, 8);
4231 id_for_tree
= htab_create (10, tree_id_hash
, tree_id_eq
, free
);
4232 memset (&stats
, 0, sizeof (stats
));
4237 /* Create points-to sets for the current function. See the comments
4238 at the start of the file for an algorithmic overview. */
4241 compute_points_to_sets (struct alias_info
*ai
)
4245 timevar_push (TV_TREE_PTA
);
4249 intra_create_variable_infos ();
4251 /* Now walk all statements and derive aliases. */
4254 block_stmt_iterator bsi
;
4257 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4259 if (is_gimple_reg (PHI_RESULT (phi
)))
4261 find_func_aliases (phi
);
4262 /* Update various related attributes like escaped
4263 addresses, pointer dereferences for loads and stores.
4264 This is used when creating name tags and alias
4266 update_alias_info (phi
, ai
);
4270 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4272 tree stmt
= bsi_stmt (bsi
);
4274 find_func_aliases (stmt
);
4276 /* Update various related attributes like escaped
4277 addresses, pointer dereferences for loads and stores.
4278 This is used when creating name tags and alias
4280 update_alias_info (stmt
, ai
);
4284 build_constraint_graph ();
4288 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4289 dump_constraints (dump_file
);
4294 "\nCollapsing static cycles and doing variable "
4297 find_and_collapse_graph_cycles (graph
, false);
4298 perform_var_substitution (graph
);
4301 fprintf (dump_file
, "\nSolving graph:\n");
4303 solve_graph (graph
);
4306 dump_sa_points_to_info (dump_file
);
4308 have_alias_info
= true;
4310 timevar_pop (TV_TREE_PTA
);
4314 /* Delete created points-to sets. */
4317 delete_points_to_sets (void)
4322 htab_delete (id_for_tree
);
4323 bitmap_obstack_release (&ptabitmap_obstack
);
4324 bitmap_obstack_release (&predbitmap_obstack
);
4325 VEC_free (constraint_t
, heap
, constraints
);
4327 for (i
= 0; VEC_iterate (varinfo_t
, varmap
, i
, v
); i
++)
4328 VEC_free (constraint_t
, heap
, v
->complex);
4330 free (graph
->preds
);
4331 free (graph
->succs
);
4334 VEC_free (varinfo_t
, heap
, varmap
);
4335 free_alloc_pool (variable_info_pool
);
4336 free_alloc_pool (constraint_pool
);
4337 have_alias_info
= false;
4340 /* Return true if we should execute IPA PTA. */
4344 return (flag_unit_at_a_time
!= 0
4346 /* Don't bother doing anything if the program has errors. */
4347 && !(errorcount
|| sorrycount
));
4350 /* Execute the driver for IPA PTA. */
4352 ipa_pta_execute (void)
4354 struct cgraph_node
*node
;
4356 init_alias_heapvars ();
4359 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4361 if (!node
->analyzed
|| cgraph_is_master_clone (node
))
4365 varid
= create_function_info_for (node
->decl
,
4366 cgraph_node_name (node
));
4367 if (node
->local
.externally_visible
)
4369 varinfo_t fi
= get_varinfo (varid
);
4370 for (; fi
; fi
= fi
->next
)
4371 make_constraint_from_anything (fi
);
4375 for (node
= cgraph_nodes
; node
; node
= node
->next
)
4377 if (node
->analyzed
&& cgraph_is_master_clone (node
))
4379 struct function
*cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
4381 tree old_func_decl
= current_function_decl
;
4384 "Generating constraints for %s\n",
4385 cgraph_node_name (node
));
4387 current_function_decl
= node
->decl
;
4389 FOR_EACH_BB_FN (bb
, cfun
)
4391 block_stmt_iterator bsi
;
4394 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4396 if (is_gimple_reg (PHI_RESULT (phi
)))
4398 find_func_aliases (phi
);
4402 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4404 tree stmt
= bsi_stmt (bsi
);
4405 find_func_aliases (stmt
);
4408 current_function_decl
= old_func_decl
;
4413 /* Make point to anything. */
4417 build_constraint_graph ();
4421 fprintf (dump_file
, "Points-to analysis\n\nConstraints:\n\n");
4422 dump_constraints (dump_file
);
4427 "\nCollapsing static cycles and doing variable "
4430 find_and_collapse_graph_cycles (graph
, false);
4431 perform_var_substitution (graph
);
4434 fprintf (dump_file
, "\nSolving graph:\n");
4436 solve_graph (graph
);
4439 dump_sa_points_to_info (dump_file
);
4442 delete_alias_heapvars ();
4443 delete_points_to_sets ();
4447 struct tree_opt_pass pass_ipa_pta
=
4450 gate_ipa_pta
, /* gate */
4451 ipa_pta_execute
, /* execute */
4454 0, /* static_pass_number */
4455 TV_IPA_PTA
, /* tv_id */
4456 0, /* properties_required */
4457 0, /* properties_provided */
4458 0, /* properties_destroyed */
4459 0, /* todo_flags_start */
4460 0, /* todo_flags_finish */
4464 /* Initialize the heapvar for statement mapping. */
4466 init_alias_heapvars (void)
4468 heapvar_for_stmt
= htab_create_ggc (11, tree_map_hash
, tree_map_eq
,
4473 delete_alias_heapvars (void)
4475 htab_delete (heapvar_for_stmt
);
4479 #include "gt-tree-ssa-structalias.h"