tree.h (enum tree_code_class): Add tcc_vl_exp.
[official-gcc.git] / gcc / tree-ssa-structalias.c
bloba6a2a68c3caa104e07df6ca312e74603b9733423
1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007 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
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "ggc.h"
27 #include "obstack.h"
28 #include "bitmap.h"
29 #include "flags.h"
30 #include "rtl.h"
31 #include "tm_p.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
34 #include "output.h"
35 #include "errors.h"
36 #include "diagnostic.h"
37 #include "tree.h"
38 #include "c-common.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
41 #include "varray.h"
42 #include "c-tree.h"
43 #include "tree-gimple.h"
44 #include "hashtab.h"
45 #include "function.h"
46 #include "cgraph.h"
47 #include "tree-pass.h"
48 #include "timevar.h"
49 #include "alloc-pool.h"
50 #include "splay-tree.h"
51 #include "params.h"
52 #include "tree-ssa-structalias.h"
53 #include "cgraph.h"
54 #include "alias.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
59 points-to sets.
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
67 as a consequence.
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. Each constraint expression consists
79 of a constraint type, a variable, and an offset.
81 SCALAR is a constraint expression type used to represent x, whether
82 it appears on the LHS or the RHS of a statement.
83 DEREF is a constraint expression type used to represent *x, whether
84 it appears on the LHS or the RHS of a statement.
85 ADDRESSOF is a constraint expression used to represent &x, whether
86 it appears on the LHS or the RHS of a statement.
88 Each pointer variable in the program is assigned an integer id, and
89 each field of a structure variable is assigned an integer id as well.
91 Structure variables are linked to their list of fields through a "next
92 field" in each variable that points to the next field in offset
93 order.
94 Each variable for a structure field has
96 1. "size", that tells the size in bits of that field.
97 2. "fullsize, that tells the size in bits of the entire structure.
98 3. "offset", that tells the offset in bits from the beginning of the
99 structure to this field.
101 Thus,
102 struct f
104 int a;
105 int b;
106 } foo;
107 int *bar;
109 looks like
111 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
112 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
113 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
116 In order to solve the system of set constraints, the following is
117 done:
119 1. Each constraint variable x has a solution set associated with it,
120 Sol(x).
122 2. Constraints are separated into direct, copy, and complex.
123 Direct constraints are ADDRESSOF constraints that require no extra
124 processing, such as P = &Q
125 Copy constraints are those of the form P = Q.
126 Complex constraints are all the constraints involving dereferences
127 and offsets (including offsetted copies).
129 3. All direct constraints of the form P = &Q are processed, such
130 that Q is added to Sol(P)
132 4. All complex constraints for a given constraint variable are stored in a
133 linked list attached to that variable's node.
135 5. A directed graph is built out of the copy constraints. Each
136 constraint variable is a node in the graph, and an edge from
137 Q to P is added for each copy constraint of the form P = Q
139 6. The graph is then walked, and solution sets are
140 propagated along the copy edges, such that an edge from Q to P
141 causes Sol(P) <- Sol(P) union Sol(Q).
143 7. As we visit each node, all complex constraints associated with
144 that node are processed by adding appropriate copy edges to the graph, or the
145 appropriate variables to the solution set.
147 8. The process of walking the graph is iterated until no solution
148 sets change.
150 Prior to walking the graph in steps 6 and 7, We perform static
151 cycle elimination on the constraint graph, as well
152 as off-line variable substitution.
154 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
155 on and turned into anything), but isn't. You can just see what offset
156 inside the pointed-to struct it's going to access.
158 TODO: Constant bounded arrays can be handled as if they were structs of the
159 same number of elements.
161 TODO: Modeling heap and incoming pointers becomes much better if we
162 add fields to them as we discover them, which we could do.
164 TODO: We could handle unions, but to be honest, it's probably not
165 worth the pain or slowdown. */
167 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
168 htab_t heapvar_for_stmt;
170 static bool use_field_sensitive = true;
171 static int in_ipa_mode = 0;
173 /* Used for predecessor bitmaps. */
174 static bitmap_obstack predbitmap_obstack;
176 /* Used for points-to sets. */
177 static bitmap_obstack pta_obstack;
179 /* Used for oldsolution members of variables. */
180 static bitmap_obstack oldpta_obstack;
182 /* Used for per-solver-iteration bitmaps. */
183 static bitmap_obstack iteration_obstack;
185 static unsigned int create_variable_info_for (tree, const char *);
186 typedef struct constraint_graph *constraint_graph_t;
187 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
189 DEF_VEC_P(constraint_t);
190 DEF_VEC_ALLOC_P(constraint_t,heap);
192 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
193 if (a) \
194 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
196 static struct constraint_stats
198 unsigned int total_vars;
199 unsigned int nonpointer_vars;
200 unsigned int unified_vars_static;
201 unsigned int unified_vars_dynamic;
202 unsigned int iterations;
203 unsigned int num_edges;
204 unsigned int num_implicit_edges;
205 unsigned int points_to_sets_created;
206 } stats;
208 struct variable_info
210 /* ID of this variable */
211 unsigned int id;
213 /* Name of this variable */
214 const char *name;
216 /* Tree that this variable is associated with. */
217 tree decl;
219 /* Offset of this variable, in bits, from the base variable */
220 unsigned HOST_WIDE_INT offset;
222 /* Size of the variable, in bits. */
223 unsigned HOST_WIDE_INT size;
225 /* Full size of the base variable, in bits. */
226 unsigned HOST_WIDE_INT fullsize;
228 /* A link to the variable for the next field in this structure. */
229 struct variable_info *next;
231 /* True if the variable is directly the target of a dereference.
232 This is used to track which variables are *actually* dereferenced
233 so we can prune their points to listed. */
234 unsigned int directly_dereferenced:1;
236 /* True if this is a variable created by the constraint analysis, such as
237 heap variables and constraints we had to break up. */
238 unsigned int is_artificial_var:1;
240 /* True if this is a special variable whose solution set should not be
241 changed. */
242 unsigned int is_special_var:1;
244 /* True for variables whose size is not known or variable. */
245 unsigned int is_unknown_size_var:1;
247 /* True for variables that have unions somewhere in them. */
248 unsigned int has_union:1;
250 /* True if this is a heap variable. */
251 unsigned int is_heap_var:1;
253 /* Points-to set for this variable. */
254 bitmap solution;
256 /* Old points-to set for this variable. */
257 bitmap oldsolution;
259 /* Finished points-to set for this variable (IE what is returned
260 from find_what_p_points_to. */
261 bitmap finished_solution;
263 /* Variable ids represented by this node. */
264 bitmap variables;
266 /* Variable id this was collapsed to due to type unsafety. This
267 should be unused completely after build_succ_graph, or something
268 is broken. */
269 struct variable_info *collapsed_to;
271 typedef struct variable_info *varinfo_t;
273 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
275 /* Pool of variable info structures. */
276 static alloc_pool variable_info_pool;
278 DEF_VEC_P(varinfo_t);
280 DEF_VEC_ALLOC_P(varinfo_t, heap);
282 /* Table of variable info structures for constraint variables.
283 Indexed directly by variable info id. */
284 static VEC(varinfo_t,heap) *varmap;
286 /* Return the varmap element N */
288 static inline varinfo_t
289 get_varinfo (unsigned int n)
291 return VEC_index (varinfo_t, varmap, n);
294 /* Return the varmap element N, following the collapsed_to link. */
296 static inline varinfo_t
297 get_varinfo_fc (unsigned int n)
299 varinfo_t v = VEC_index (varinfo_t, varmap, n);
301 if (v->collapsed_to)
302 return v->collapsed_to;
303 return v;
306 /* Variable that represents the unknown pointer. */
307 static varinfo_t var_anything;
308 static tree anything_tree;
309 static unsigned int anything_id;
311 /* Variable that represents the NULL pointer. */
312 static varinfo_t var_nothing;
313 static tree nothing_tree;
314 static unsigned int nothing_id;
316 /* Variable that represents read only memory. */
317 static varinfo_t var_readonly;
318 static tree readonly_tree;
319 static unsigned int readonly_id;
321 /* Variable that represents integers. This is used for when people do things
322 like &0->a.b. */
323 static varinfo_t var_integer;
324 static tree integer_tree;
325 static unsigned int integer_id;
327 /* Lookup a heap var for FROM, and return it if we find one. */
329 static tree
330 heapvar_lookup (tree from)
332 struct tree_map *h, in;
333 in.from = from;
335 h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));
336 if (h)
337 return h->to;
338 return NULL_TREE;
341 /* Insert a mapping FROM->TO in the heap var for statement
342 hashtable. */
344 static void
345 heapvar_insert (tree from, tree to)
347 struct tree_map *h;
348 void **loc;
350 h = ggc_alloc (sizeof (struct tree_map));
351 h->hash = htab_hash_pointer (from);
352 h->from = from;
353 h->to = to;
354 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
355 *(struct tree_map **) loc = h;
358 /* Return a new variable info structure consisting for a variable
359 named NAME, and using constraint graph node NODE. */
361 static varinfo_t
362 new_var_info (tree t, unsigned int id, const char *name)
364 varinfo_t ret = pool_alloc (variable_info_pool);
366 ret->id = id;
367 ret->name = name;
368 ret->decl = t;
369 ret->directly_dereferenced = false;
370 ret->is_artificial_var = false;
371 ret->is_heap_var = false;
372 ret->is_special_var = false;
373 ret->is_unknown_size_var = false;
374 ret->has_union = false;
375 ret->solution = BITMAP_ALLOC (&pta_obstack);
376 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
377 ret->finished_solution = NULL;
378 ret->next = NULL;
379 ret->collapsed_to = NULL;
380 return ret;
383 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
385 /* An expression that appears in a constraint. */
387 struct constraint_expr
389 /* Constraint type. */
390 constraint_expr_type type;
392 /* Variable we are referring to in the constraint. */
393 unsigned int var;
395 /* Offset, in bits, of this constraint from the beginning of
396 variables it ends up referring to.
398 IOW, in a deref constraint, we would deref, get the result set,
399 then add OFFSET to each member. */
400 unsigned HOST_WIDE_INT offset;
403 typedef struct constraint_expr ce_s;
404 DEF_VEC_O(ce_s);
405 DEF_VEC_ALLOC_O(ce_s, heap);
406 static void get_constraint_for (tree, VEC(ce_s, heap) **);
407 static void do_deref (VEC (ce_s, heap) **);
409 /* Our set constraints are made up of two constraint expressions, one
410 LHS, and one RHS.
412 As described in the introduction, our set constraints each represent an
413 operation between set valued variables.
415 struct constraint
417 struct constraint_expr lhs;
418 struct constraint_expr rhs;
421 /* List of constraints that we use to build the constraint graph from. */
423 static VEC(constraint_t,heap) *constraints;
424 static alloc_pool constraint_pool;
427 DEF_VEC_I(int);
428 DEF_VEC_ALLOC_I(int, heap);
430 /* The constraint graph is represented as an array of bitmaps
431 containing successor nodes. */
433 struct constraint_graph
435 /* Size of this graph, which may be different than the number of
436 nodes in the variable map. */
437 unsigned int size;
439 /* Explicit successors of each node. */
440 bitmap *succs;
442 /* Implicit predecessors of each node (Used for variable
443 substitution). */
444 bitmap *implicit_preds;
446 /* Explicit predecessors of each node (Used for variable substitution). */
447 bitmap *preds;
449 /* Indirect cycle representatives, or -1 if the node has no indirect
450 cycles. */
451 int *indirect_cycles;
453 /* Representative node for a node. rep[a] == a unless the node has
454 been unified. */
455 unsigned int *rep;
457 /* Equivalence class representative for a node. This is used for
458 variable substitution. */
459 int *eq_rep;
461 /* Label for each node, used during variable substitution. */
462 unsigned int *label;
464 /* Bitmap of nodes where the bit is set if the node is a direct
465 node. Used for variable substitution. */
466 sbitmap direct_nodes;
468 /* Vector of complex constraints for each graph node. Complex
469 constraints are those involving dereferences or offsets that are
470 not 0. */
471 VEC(constraint_t,heap) **complex;
474 static constraint_graph_t graph;
476 /* During variable substitution and the offline version of indirect
477 cycle finding, we create nodes to represent dereferences and
478 address taken constraints. These represent where these start and
479 end. */
480 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
481 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
482 #define FIRST_ADDR_NODE (LAST_REF_NODE + 1)
484 /* Return the representative node for NODE, if NODE has been unioned
485 with another NODE.
486 This function performs path compression along the way to finding
487 the representative. */
489 static unsigned int
490 find (unsigned int node)
492 gcc_assert (node < graph->size);
493 if (graph->rep[node] != node)
494 return graph->rep[node] = find (graph->rep[node]);
495 return node;
498 /* Union the TO and FROM nodes to the TO nodes.
499 Note that at some point in the future, we may want to do
500 union-by-rank, in which case we are going to have to return the
501 node we unified to. */
503 static bool
504 unite (unsigned int to, unsigned int from)
506 gcc_assert (to < graph->size && from < graph->size);
507 if (to != from && graph->rep[from] != to)
509 graph->rep[from] = to;
510 return true;
512 return false;
515 /* Create a new constraint consisting of LHS and RHS expressions. */
517 static constraint_t
518 new_constraint (const struct constraint_expr lhs,
519 const struct constraint_expr rhs)
521 constraint_t ret = pool_alloc (constraint_pool);
522 ret->lhs = lhs;
523 ret->rhs = rhs;
524 return ret;
527 /* Print out constraint C to FILE. */
529 void
530 dump_constraint (FILE *file, constraint_t c)
532 if (c->lhs.type == ADDRESSOF)
533 fprintf (file, "&");
534 else if (c->lhs.type == DEREF)
535 fprintf (file, "*");
536 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
537 if (c->lhs.offset != 0)
538 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
539 fprintf (file, " = ");
540 if (c->rhs.type == ADDRESSOF)
541 fprintf (file, "&");
542 else if (c->rhs.type == DEREF)
543 fprintf (file, "*");
544 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
545 if (c->rhs.offset != 0)
546 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
547 fprintf (file, "\n");
550 /* Print out constraint C to stderr. */
552 void
553 debug_constraint (constraint_t c)
555 dump_constraint (stderr, c);
558 /* Print out all constraints to FILE */
560 void
561 dump_constraints (FILE *file)
563 int i;
564 constraint_t c;
565 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
566 dump_constraint (file, c);
569 /* Print out all constraints to stderr. */
571 void
572 debug_constraints (void)
574 dump_constraints (stderr);
577 /* SOLVER FUNCTIONS
579 The solver is a simple worklist solver, that works on the following
580 algorithm:
582 sbitmap changed_nodes = all zeroes;
583 changed_count = 0;
584 For each node that is not already collapsed:
585 changed_count++;
586 set bit in changed nodes
588 while (changed_count > 0)
590 compute topological ordering for constraint graph
592 find and collapse cycles in the constraint graph (updating
593 changed if necessary)
595 for each node (n) in the graph in topological order:
596 changed_count--;
598 Process each complex constraint associated with the node,
599 updating changed if necessary.
601 For each outgoing edge from n, propagate the solution from n to
602 the destination of the edge, updating changed as necessary.
604 } */
606 /* Return true if two constraint expressions A and B are equal. */
608 static bool
609 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
611 return a.type == b.type && a.var == b.var && a.offset == b.offset;
614 /* Return true if constraint expression A is less than constraint expression
615 B. This is just arbitrary, but consistent, in order to give them an
616 ordering. */
618 static bool
619 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
621 if (a.type == b.type)
623 if (a.var == b.var)
624 return a.offset < b.offset;
625 else
626 return a.var < b.var;
628 else
629 return a.type < b.type;
632 /* Return true if constraint A is less than constraint B. This is just
633 arbitrary, but consistent, in order to give them an ordering. */
635 static bool
636 constraint_less (const constraint_t a, const constraint_t b)
638 if (constraint_expr_less (a->lhs, b->lhs))
639 return true;
640 else if (constraint_expr_less (b->lhs, a->lhs))
641 return false;
642 else
643 return constraint_expr_less (a->rhs, b->rhs);
646 /* Return true if two constraints A and B are equal. */
648 static bool
649 constraint_equal (struct constraint a, struct constraint b)
651 return constraint_expr_equal (a.lhs, b.lhs)
652 && constraint_expr_equal (a.rhs, b.rhs);
656 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
658 static constraint_t
659 constraint_vec_find (VEC(constraint_t,heap) *vec,
660 struct constraint lookfor)
662 unsigned int place;
663 constraint_t found;
665 if (vec == NULL)
666 return NULL;
668 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
669 if (place >= VEC_length (constraint_t, vec))
670 return NULL;
671 found = VEC_index (constraint_t, vec, place);
672 if (!constraint_equal (*found, lookfor))
673 return NULL;
674 return found;
677 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
679 static void
680 constraint_set_union (VEC(constraint_t,heap) **to,
681 VEC(constraint_t,heap) **from)
683 int i;
684 constraint_t c;
686 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
688 if (constraint_vec_find (*to, *c) == NULL)
690 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
691 constraint_less);
692 VEC_safe_insert (constraint_t, heap, *to, place, c);
697 /* Take a solution set SET, add OFFSET to each member of the set, and
698 overwrite SET with the result when done. */
700 static void
701 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
703 bitmap result = BITMAP_ALLOC (&iteration_obstack);
704 unsigned int i;
705 bitmap_iterator bi;
707 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
709 /* If this is a properly sized variable, only add offset if it's
710 less than end. Otherwise, it is globbed to a single
711 variable. */
713 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
715 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
716 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
717 if (!v)
718 continue;
719 bitmap_set_bit (result, v->id);
721 else if (get_varinfo (i)->is_artificial_var
722 || get_varinfo (i)->has_union
723 || get_varinfo (i)->is_unknown_size_var)
725 bitmap_set_bit (result, i);
729 bitmap_copy (set, result);
730 BITMAP_FREE (result);
733 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
734 process. */
736 static bool
737 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
739 if (inc == 0)
740 return bitmap_ior_into (to, from);
741 else
743 bitmap tmp;
744 bool res;
746 tmp = BITMAP_ALLOC (&iteration_obstack);
747 bitmap_copy (tmp, from);
748 solution_set_add (tmp, inc);
749 res = bitmap_ior_into (to, tmp);
750 BITMAP_FREE (tmp);
751 return res;
755 /* Insert constraint C into the list of complex constraints for graph
756 node VAR. */
758 static void
759 insert_into_complex (constraint_graph_t graph,
760 unsigned int var, constraint_t c)
762 VEC (constraint_t, heap) *complex = graph->complex[var];
763 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
764 constraint_less);
766 /* Only insert constraints that do not already exist. */
767 if (place >= VEC_length (constraint_t, complex)
768 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
769 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
773 /* Condense two variable nodes into a single variable node, by moving
774 all associated info from SRC to TO. */
776 static void
777 merge_node_constraints (constraint_graph_t graph, unsigned int to,
778 unsigned int from)
780 unsigned int i;
781 constraint_t c;
783 gcc_assert (find (from) == to);
785 /* Move all complex constraints from src node into to node */
786 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
788 /* In complex constraints for node src, we may have either
789 a = *src, and *src = a, or an offseted constraint which are
790 always added to the rhs node's constraints. */
792 if (c->rhs.type == DEREF)
793 c->rhs.var = to;
794 else if (c->lhs.type == DEREF)
795 c->lhs.var = to;
796 else
797 c->rhs.var = to;
799 constraint_set_union (&graph->complex[to], &graph->complex[from]);
800 VEC_free (constraint_t, heap, graph->complex[from]);
801 graph->complex[from] = NULL;
805 /* Remove edges involving NODE from GRAPH. */
807 static void
808 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
810 if (graph->succs[node])
811 BITMAP_FREE (graph->succs[node]);
814 /* Merge GRAPH nodes FROM and TO into node TO. */
816 static void
817 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
818 unsigned int from)
820 if (graph->indirect_cycles[from] != -1)
822 /* If we have indirect cycles with the from node, and we have
823 none on the to node, the to node has indirect cycles from the
824 from node now that they are unified.
825 If indirect cycles exist on both, unify the nodes that they
826 are in a cycle with, since we know they are in a cycle with
827 each other. */
828 if (graph->indirect_cycles[to] == -1)
830 graph->indirect_cycles[to] = graph->indirect_cycles[from];
832 else
834 unsigned int tonode = find (graph->indirect_cycles[to]);
835 unsigned int fromnode = find (graph->indirect_cycles[from]);
837 if (unite (tonode, fromnode))
838 unify_nodes (graph, tonode, fromnode, true);
842 /* Merge all the successor edges. */
843 if (graph->succs[from])
845 if (!graph->succs[to])
846 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
847 bitmap_ior_into (graph->succs[to],
848 graph->succs[from]);
851 clear_edges_for_node (graph, from);
855 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
856 it doesn't exist in the graph already. */
858 static void
859 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
860 unsigned int from)
862 if (to == from)
863 return;
865 if (!graph->implicit_preds[to])
866 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
868 if (!bitmap_bit_p (graph->implicit_preds[to], from))
870 stats.num_implicit_edges++;
871 bitmap_set_bit (graph->implicit_preds[to], from);
875 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
876 it doesn't exist in the graph already.
877 Return false if the edge already existed, true otherwise. */
879 static void
880 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
881 unsigned int from)
883 if (!graph->preds[to])
884 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
885 if (!bitmap_bit_p (graph->preds[to], from))
886 bitmap_set_bit (graph->preds[to], from);
889 /* Add a graph edge to GRAPH, going from FROM to TO if
890 it doesn't exist in the graph already.
891 Return false if the edge already existed, true otherwise. */
893 static bool
894 add_graph_edge (constraint_graph_t graph, unsigned int to,
895 unsigned int from)
897 if (to == from)
899 return false;
901 else
903 bool r = false;
905 if (!graph->succs[from])
906 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
907 if (!bitmap_bit_p (graph->succs[from], to))
909 r = true;
910 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
911 stats.num_edges++;
912 bitmap_set_bit (graph->succs[from], to);
914 return r;
919 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
921 static bool
922 valid_graph_edge (constraint_graph_t graph, unsigned int src,
923 unsigned int dest)
925 return (graph->succs[dest]
926 && bitmap_bit_p (graph->succs[dest], src));
929 /* Build the constraint graph, adding only predecessor edges right now. */
931 static void
932 build_pred_graph (void)
934 int i;
935 constraint_t c;
936 unsigned int j;
938 graph = XNEW (struct constraint_graph);
939 graph->size = (VEC_length (varinfo_t, varmap)) * 3;
940 graph->succs = XCNEWVEC (bitmap, graph->size);
941 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
942 graph->preds = XCNEWVEC (bitmap, graph->size);
943 graph->indirect_cycles = XNEWVEC (int, VEC_length (varinfo_t, varmap));
944 graph->label = XCNEWVEC (unsigned int, graph->size);
945 graph->rep = XNEWVEC (unsigned int, graph->size);
946 graph->eq_rep = XNEWVEC (int, graph->size);
947 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *,
948 VEC_length (varinfo_t, varmap));
949 graph->direct_nodes = sbitmap_alloc (graph->size);
950 sbitmap_zero (graph->direct_nodes);
952 for (j = 0; j < FIRST_REF_NODE; j++)
954 if (!get_varinfo (j)->is_special_var)
955 SET_BIT (graph->direct_nodes, j);
958 for (j = 0; j < graph->size; j++)
960 graph->rep[j] = j;
961 graph->eq_rep[j] = -1;
964 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
965 graph->indirect_cycles[j] = -1;
967 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
969 struct constraint_expr lhs = c->lhs;
970 struct constraint_expr rhs = c->rhs;
971 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
972 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
974 if (lhs.type == DEREF)
976 /* *x = y. */
977 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
978 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
979 if (rhs.type == ADDRESSOF)
980 RESET_BIT (graph->direct_nodes, rhsvar);
982 else if (rhs.type == DEREF)
984 /* x = *y */
985 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
986 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
987 else
988 RESET_BIT (graph->direct_nodes, lhsvar);
990 else if (rhs.type == ADDRESSOF)
992 /* x = &y */
993 add_pred_graph_edge (graph, lhsvar, FIRST_ADDR_NODE + rhsvar);
994 /* Implicitly, *x = y */
995 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
997 RESET_BIT (graph->direct_nodes, rhsvar);
999 else if (lhsvar > anything_id
1000 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1002 /* x = y */
1003 add_pred_graph_edge (graph, lhsvar, rhsvar);
1004 /* Implicitly, *x = *y */
1005 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1006 FIRST_REF_NODE + rhsvar);
1008 else if (lhs.offset != 0 || rhs.offset != 0)
1010 if (rhs.offset != 0)
1011 RESET_BIT (graph->direct_nodes, lhs.var);
1012 if (lhs.offset != 0)
1013 RESET_BIT (graph->direct_nodes, rhs.var);
1018 /* Build the constraint graph, adding successor edges. */
1020 static void
1021 build_succ_graph (void)
1023 int i;
1024 constraint_t c;
1026 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1028 struct constraint_expr lhs;
1029 struct constraint_expr rhs;
1030 unsigned int lhsvar;
1031 unsigned int rhsvar;
1033 if (!c)
1034 continue;
1036 lhs = c->lhs;
1037 rhs = c->rhs;
1038 lhsvar = find (get_varinfo_fc (lhs.var)->id);
1039 rhsvar = find (get_varinfo_fc (rhs.var)->id);
1041 if (lhs.type == DEREF)
1043 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1044 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1046 else if (rhs.type == DEREF)
1048 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1049 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1051 else if (rhs.type == ADDRESSOF)
1053 /* x = &y */
1054 gcc_assert (find (get_varinfo_fc (rhs.var)->id)
1055 == get_varinfo_fc (rhs.var)->id);
1056 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1058 else if (lhsvar > anything_id
1059 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1061 add_graph_edge (graph, lhsvar, rhsvar);
1067 /* Changed variables on the last iteration. */
1068 static unsigned int changed_count;
1069 static sbitmap changed;
1071 DEF_VEC_I(unsigned);
1072 DEF_VEC_ALLOC_I(unsigned,heap);
1075 /* Strongly Connected Component visitation info. */
1077 struct scc_info
1079 sbitmap visited;
1080 sbitmap roots;
1081 unsigned int *dfs;
1082 unsigned int *node_mapping;
1083 int current_index;
1084 VEC(unsigned,heap) *scc_stack;
1088 /* Recursive routine to find strongly connected components in GRAPH.
1089 SI is the SCC info to store the information in, and N is the id of current
1090 graph node we are processing.
1092 This is Tarjan's strongly connected component finding algorithm, as
1093 modified by Nuutila to keep only non-root nodes on the stack.
1094 The algorithm can be found in "On finding the strongly connected
1095 connected components in a directed graph" by Esko Nuutila and Eljas
1096 Soisalon-Soininen, in Information Processing Letters volume 49,
1097 number 1, pages 9-14. */
1099 static void
1100 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1102 unsigned int i;
1103 bitmap_iterator bi;
1104 unsigned int my_dfs;
1106 SET_BIT (si->visited, n);
1107 si->dfs[n] = si->current_index ++;
1108 my_dfs = si->dfs[n];
1110 /* Visit all the successors. */
1111 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1113 unsigned int w;
1115 if (i > LAST_REF_NODE)
1116 break;
1118 w = find (i);
1119 if (TEST_BIT (si->roots, w))
1120 continue;
1122 if (!TEST_BIT (si->visited, w))
1123 scc_visit (graph, si, w);
1125 unsigned int t = find (w);
1126 unsigned int nnode = find (n);
1127 gcc_assert (nnode == n);
1129 if (si->dfs[t] < si->dfs[nnode])
1130 si->dfs[n] = si->dfs[t];
1134 /* See if any components have been identified. */
1135 if (si->dfs[n] == my_dfs)
1137 if (VEC_length (unsigned, si->scc_stack) > 0
1138 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1140 bitmap scc = BITMAP_ALLOC (NULL);
1141 bool have_ref_node = n >= FIRST_REF_NODE;
1142 unsigned int lowest_node;
1143 bitmap_iterator bi;
1145 bitmap_set_bit (scc, n);
1147 while (VEC_length (unsigned, si->scc_stack) != 0
1148 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1150 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1152 bitmap_set_bit (scc, w);
1153 if (w >= FIRST_REF_NODE)
1154 have_ref_node = true;
1157 lowest_node = bitmap_first_set_bit (scc);
1158 gcc_assert (lowest_node < FIRST_REF_NODE);
1159 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1161 if (i < FIRST_REF_NODE)
1163 /* Mark this node for collapsing. */
1164 if (unite (lowest_node, i))
1165 unify_nodes (graph, lowest_node, i, false);
1167 else
1169 unite (lowest_node, i);
1170 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1174 SET_BIT (si->roots, n);
1176 else
1177 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1180 /* Unify node FROM into node TO, updating the changed count if
1181 necessary when UPDATE_CHANGED is true. */
1183 static void
1184 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1185 bool update_changed)
1188 gcc_assert (to != from && find (to) == to);
1189 if (dump_file && (dump_flags & TDF_DETAILS))
1190 fprintf (dump_file, "Unifying %s to %s\n",
1191 get_varinfo (from)->name,
1192 get_varinfo (to)->name);
1194 if (update_changed)
1195 stats.unified_vars_dynamic++;
1196 else
1197 stats.unified_vars_static++;
1199 merge_graph_nodes (graph, to, from);
1200 merge_node_constraints (graph, to, from);
1202 if (update_changed && TEST_BIT (changed, from))
1204 RESET_BIT (changed, from);
1205 if (!TEST_BIT (changed, to))
1206 SET_BIT (changed, to);
1207 else
1209 gcc_assert (changed_count > 0);
1210 changed_count--;
1214 /* If the solution changes because of the merging, we need to mark
1215 the variable as changed. */
1216 if (bitmap_ior_into (get_varinfo (to)->solution,
1217 get_varinfo (from)->solution))
1219 if (update_changed && !TEST_BIT (changed, to))
1221 SET_BIT (changed, to);
1222 changed_count++;
1226 BITMAP_FREE (get_varinfo (from)->solution);
1227 BITMAP_FREE (get_varinfo (from)->oldsolution);
1229 if (stats.iterations > 0)
1231 BITMAP_FREE (get_varinfo (to)->oldsolution);
1232 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1235 if (valid_graph_edge (graph, to, to))
1237 if (graph->succs[to])
1238 bitmap_clear_bit (graph->succs[to], to);
1242 /* Information needed to compute the topological ordering of a graph. */
1244 struct topo_info
1246 /* sbitmap of visited nodes. */
1247 sbitmap visited;
1248 /* Array that stores the topological order of the graph, *in
1249 reverse*. */
1250 VEC(unsigned,heap) *topo_order;
1254 /* Initialize and return a topological info structure. */
1256 static struct topo_info *
1257 init_topo_info (void)
1259 size_t size = VEC_length (varinfo_t, varmap);
1260 struct topo_info *ti = XNEW (struct topo_info);
1261 ti->visited = sbitmap_alloc (size);
1262 sbitmap_zero (ti->visited);
1263 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1264 return ti;
1268 /* Free the topological sort info pointed to by TI. */
1270 static void
1271 free_topo_info (struct topo_info *ti)
1273 sbitmap_free (ti->visited);
1274 VEC_free (unsigned, heap, ti->topo_order);
1275 free (ti);
1278 /* Visit the graph in topological order, and store the order in the
1279 topo_info structure. */
1281 static void
1282 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1283 unsigned int n)
1285 bitmap_iterator bi;
1286 unsigned int j;
1288 SET_BIT (ti->visited, n);
1290 if (graph->succs[n])
1291 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1293 if (!TEST_BIT (ti->visited, j))
1294 topo_visit (graph, ti, j);
1297 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1300 /* Return true if variable N + OFFSET is a legal field of N. */
1302 static bool
1303 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1305 varinfo_t ninfo = get_varinfo (n);
1307 /* For things we've globbed to single variables, any offset into the
1308 variable acts like the entire variable, so that it becomes offset
1309 0. */
1310 if (ninfo->is_special_var
1311 || ninfo->is_artificial_var
1312 || ninfo->is_unknown_size_var)
1314 *offset = 0;
1315 return true;
1317 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1320 /* Process a constraint C that represents *x = &y. */
1322 static void
1323 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1324 constraint_t c, bitmap delta)
1326 unsigned int rhs = c->rhs.var;
1327 unsigned int j;
1328 bitmap_iterator bi;
1330 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1331 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1333 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1334 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1336 /* *x != NULL && *x != ANYTHING*/
1337 varinfo_t v;
1338 unsigned int t;
1339 bitmap sol;
1340 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1342 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1343 if (!v)
1344 continue;
1345 t = find (v->id);
1346 sol = get_varinfo (t)->solution;
1347 if (!bitmap_bit_p (sol, rhs))
1349 bitmap_set_bit (sol, rhs);
1350 if (!TEST_BIT (changed, t))
1352 SET_BIT (changed, t);
1353 changed_count++;
1357 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1358 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1363 /* Process a constraint C that represents x = *y, using DELTA as the
1364 starting solution. */
1366 static void
1367 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1368 bitmap delta)
1370 unsigned int lhs = find (c->lhs.var);
1371 bool flag = false;
1372 bitmap sol = get_varinfo (lhs)->solution;
1373 unsigned int j;
1374 bitmap_iterator bi;
1376 if (bitmap_bit_p (delta, anything_id))
1378 flag = !bitmap_bit_p (sol, anything_id);
1379 if (flag)
1380 bitmap_set_bit (sol, anything_id);
1381 goto done;
1383 /* For each variable j in delta (Sol(y)), add
1384 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1385 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1387 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1388 if (type_safe (j, &roffset))
1390 varinfo_t v;
1391 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1392 unsigned int t;
1394 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1395 if (!v)
1396 continue;
1397 t = find (v->id);
1399 /* Adding edges from the special vars is pointless.
1400 They don't have sets that can change. */
1401 if (get_varinfo (t) ->is_special_var)
1402 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1403 else if (add_graph_edge (graph, lhs, t))
1404 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1406 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1407 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1411 done:
1412 /* If the LHS solution changed, mark the var as changed. */
1413 if (flag)
1415 get_varinfo (lhs)->solution = sol;
1416 if (!TEST_BIT (changed, lhs))
1418 SET_BIT (changed, lhs);
1419 changed_count++;
1424 /* Process a constraint C that represents *x = y. */
1426 static void
1427 do_ds_constraint (constraint_t c, bitmap delta)
1429 unsigned int rhs = find (c->rhs.var);
1430 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1431 bitmap sol = get_varinfo (rhs)->solution;
1432 unsigned int j;
1433 bitmap_iterator bi;
1435 if (bitmap_bit_p (sol, anything_id))
1437 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1439 varinfo_t jvi = get_varinfo (j);
1440 unsigned int t;
1441 unsigned int loff = c->lhs.offset;
1442 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1443 varinfo_t v;
1445 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1446 if (!v)
1447 continue;
1448 t = find (v->id);
1450 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1452 bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1453 if (!TEST_BIT (changed, t))
1455 SET_BIT (changed, t);
1456 changed_count++;
1460 return;
1463 /* For each member j of delta (Sol(x)), add an edge from y to j and
1464 union Sol(y) into Sol(j) */
1465 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1467 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1468 if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
1470 varinfo_t v;
1471 unsigned int t;
1472 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1473 bitmap tmp;
1475 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1476 if (!v)
1477 continue;
1478 t = find (v->id);
1479 tmp = get_varinfo (t)->solution;
1481 if (set_union_with_increment (tmp, sol, roff))
1483 get_varinfo (t)->solution = tmp;
1484 if (t == rhs)
1485 sol = get_varinfo (rhs)->solution;
1486 if (!TEST_BIT (changed, t))
1488 SET_BIT (changed, t);
1489 changed_count++;
1493 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1494 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1498 /* Handle a non-simple (simple meaning requires no iteration),
1499 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1501 static void
1502 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1504 if (c->lhs.type == DEREF)
1506 if (c->rhs.type == ADDRESSOF)
1508 /* *x = &y */
1509 do_da_constraint (graph, c, delta);
1511 else
1513 /* *x = y */
1514 do_ds_constraint (c, delta);
1517 else if (c->rhs.type == DEREF)
1519 /* x = *y */
1520 if (!(get_varinfo (c->lhs.var)->is_special_var))
1521 do_sd_constraint (graph, c, delta);
1523 else
1525 bitmap tmp;
1526 bitmap solution;
1527 bool flag = false;
1528 unsigned int t;
1530 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1531 t = find (c->rhs.var);
1532 solution = get_varinfo (t)->solution;
1533 t = find (c->lhs.var);
1534 tmp = get_varinfo (t)->solution;
1536 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1538 if (flag)
1540 get_varinfo (t)->solution = tmp;
1541 if (!TEST_BIT (changed, t))
1543 SET_BIT (changed, t);
1544 changed_count++;
1550 /* Initialize and return a new SCC info structure. */
1552 static struct scc_info *
1553 init_scc_info (size_t size)
1555 struct scc_info *si = XNEW (struct scc_info);
1556 size_t i;
1558 si->current_index = 0;
1559 si->visited = sbitmap_alloc (size);
1560 sbitmap_zero (si->visited);
1561 si->roots = sbitmap_alloc (size);
1562 sbitmap_zero (si->roots);
1563 si->node_mapping = XNEWVEC (unsigned int, size);
1564 si->dfs = XCNEWVEC (unsigned int, size);
1566 for (i = 0; i < size; i++)
1567 si->node_mapping[i] = i;
1569 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1570 return si;
1573 /* Free an SCC info structure pointed to by SI */
1575 static void
1576 free_scc_info (struct scc_info *si)
1578 sbitmap_free (si->visited);
1579 sbitmap_free (si->roots);
1580 free (si->node_mapping);
1581 free (si->dfs);
1582 VEC_free (unsigned, heap, si->scc_stack);
1583 free (si);
1587 /* Find indirect cycles in GRAPH that occur, using strongly connected
1588 components, and note them in the indirect cycles map.
1590 This technique comes from Ben Hardekopf and Calvin Lin,
1591 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1592 Lines of Code", submitted to PLDI 2007. */
1594 static void
1595 find_indirect_cycles (constraint_graph_t graph)
1597 unsigned int i;
1598 unsigned int size = graph->size;
1599 struct scc_info *si = init_scc_info (size);
1601 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1602 if (!TEST_BIT (si->visited, i) && find (i) == i)
1603 scc_visit (graph, si, i);
1605 free_scc_info (si);
1608 /* Compute a topological ordering for GRAPH, and store the result in the
1609 topo_info structure TI. */
1611 static void
1612 compute_topo_order (constraint_graph_t graph,
1613 struct topo_info *ti)
1615 unsigned int i;
1616 unsigned int size = VEC_length (varinfo_t, varmap);
1618 for (i = 0; i != size; ++i)
1619 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1620 topo_visit (graph, ti, i);
1623 /* Perform offline variable substitution.
1625 This is a linear time way of identifying variables that must have
1626 equivalent points-to sets, including those caused by static cycles,
1627 and single entry subgraphs, in the constraint graph.
1629 The technique is described in "Off-line variable substitution for
1630 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1631 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56.
1633 There is an optimal way to do this involving hash based value
1634 numbering, once the technique is published i will implement it
1635 here.
1637 The general method of finding equivalence classes is as follows:
1638 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1639 Add fake nodes (ADDRESS nodes) and edges for a = &b constraints.
1640 Initialize all non-REF/ADDRESS nodes to be direct nodes
1641 For each SCC in the predecessor graph:
1642 for each member (x) of the SCC
1643 if x is not a direct node:
1644 set rootnode(SCC) to be not a direct node
1645 collapse node x into rootnode(SCC).
1646 if rootnode(SCC) is not a direct node:
1647 label rootnode(SCC) with a new equivalence class
1648 else:
1649 if all labeled predecessors of rootnode(SCC) have the same
1650 label:
1651 label rootnode(SCC) with this label
1652 else:
1653 label rootnode(SCC) with a new equivalence class
1655 All direct nodes with the same equivalence class can be replaced
1656 with a single representative node.
1657 All unlabeled nodes (label == 0) are not pointers and all edges
1658 involving them can be eliminated.
1659 We perform these optimizations during move_complex_constraints.
1662 static int equivalence_class;
1664 /* Recursive routine to find strongly connected components in GRAPH,
1665 and label it's nodes with equivalence classes.
1666 This is used during variable substitution to find cycles involving
1667 the regular or implicit predecessors, and label them as equivalent.
1668 The SCC finding algorithm used is the same as that for scc_visit. */
1670 static void
1671 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1673 unsigned int i;
1674 bitmap_iterator bi;
1675 unsigned int my_dfs;
1677 gcc_assert (si->node_mapping[n] == n);
1678 SET_BIT (si->visited, n);
1679 si->dfs[n] = si->current_index ++;
1680 my_dfs = si->dfs[n];
1682 /* Visit all the successors. */
1683 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1685 unsigned int w = si->node_mapping[i];
1687 if (TEST_BIT (si->roots, w))
1688 continue;
1690 if (!TEST_BIT (si->visited, w))
1691 label_visit (graph, si, w);
1693 unsigned int t = si->node_mapping[w];
1694 unsigned int nnode = si->node_mapping[n];
1695 gcc_assert (nnode == n);
1697 if (si->dfs[t] < si->dfs[nnode])
1698 si->dfs[n] = si->dfs[t];
1702 /* Visit all the implicit predecessors. */
1703 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1705 unsigned int w = si->node_mapping[i];
1707 if (TEST_BIT (si->roots, w))
1708 continue;
1710 if (!TEST_BIT (si->visited, w))
1711 label_visit (graph, si, w);
1713 unsigned int t = si->node_mapping[w];
1714 unsigned int nnode = si->node_mapping[n];
1715 gcc_assert (nnode == n);
1717 if (si->dfs[t] < si->dfs[nnode])
1718 si->dfs[n] = si->dfs[t];
1722 /* See if any components have been identified. */
1723 if (si->dfs[n] == my_dfs)
1725 while (VEC_length (unsigned, si->scc_stack) != 0
1726 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1728 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1729 si->node_mapping[w] = n;
1731 if (!TEST_BIT (graph->direct_nodes, w))
1732 RESET_BIT (graph->direct_nodes, n);
1734 SET_BIT (si->roots, n);
1736 if (!TEST_BIT (graph->direct_nodes, n))
1738 graph->label[n] = equivalence_class++;
1740 else
1742 unsigned int size = 0;
1743 unsigned int firstlabel = ~0;
1745 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1747 unsigned int j = si->node_mapping[i];
1749 if (j == n || graph->label[j] == 0)
1750 continue;
1752 if (firstlabel == (unsigned int)~0)
1754 firstlabel = graph->label[j];
1755 size++;
1757 else if (graph->label[j] != firstlabel)
1758 size++;
1761 if (size == 0)
1762 graph->label[n] = 0;
1763 else if (size == 1)
1764 graph->label[n] = firstlabel;
1765 else
1766 graph->label[n] = equivalence_class++;
1769 else
1770 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1773 /* Perform offline variable substitution, discovering equivalence
1774 classes, and eliminating non-pointer variables. */
1776 static struct scc_info *
1777 perform_var_substitution (constraint_graph_t graph)
1779 unsigned int i;
1780 unsigned int size = graph->size;
1781 struct scc_info *si = init_scc_info (size);
1783 bitmap_obstack_initialize (&iteration_obstack);
1784 equivalence_class = 0;
1786 /* We only need to visit the non-address nodes for labeling
1787 purposes, as the address nodes will never have any predecessors,
1788 because &x never appears on the LHS of a constraint. */
1789 for (i = 0; i < LAST_REF_NODE; i++)
1790 if (!TEST_BIT (si->visited, si->node_mapping[i]))
1791 label_visit (graph, si, si->node_mapping[i]);
1793 if (dump_file && (dump_flags & TDF_DETAILS))
1794 for (i = 0; i < FIRST_REF_NODE; i++)
1796 bool direct_node = TEST_BIT (graph->direct_nodes, i);
1797 fprintf (dump_file,
1798 "Equivalence class for %s node id %d:%s is %d\n",
1799 direct_node ? "Direct node" : "Indirect node", i,
1800 get_varinfo (i)->name,
1801 graph->label[si->node_mapping[i]]);
1804 /* Quickly eliminate our non-pointer variables. */
1806 for (i = 0; i < FIRST_REF_NODE; i++)
1808 unsigned int node = si->node_mapping[i];
1810 if (graph->label[node] == 0 && TEST_BIT (graph->direct_nodes, node))
1812 if (dump_file && (dump_flags & TDF_DETAILS))
1813 fprintf (dump_file,
1814 "%s is a non-pointer variable, eliminating edges.\n",
1815 get_varinfo (node)->name);
1816 stats.nonpointer_vars++;
1817 clear_edges_for_node (graph, node);
1820 return si;
1823 /* Free information that was only necessary for variable
1824 substitution. */
1826 static void
1827 free_var_substitution_info (struct scc_info *si)
1829 free_scc_info (si);
1830 free (graph->label);
1831 free (graph->eq_rep);
1832 sbitmap_free (graph->direct_nodes);
1833 bitmap_obstack_release (&iteration_obstack);
1836 /* Return an existing node that is equivalent to NODE, which has
1837 equivalence class LABEL, if one exists. Return NODE otherwise. */
1839 static unsigned int
1840 find_equivalent_node (constraint_graph_t graph,
1841 unsigned int node, unsigned int label)
1843 /* If the address version of this variable is unused, we can
1844 substitute it for anything else with the same label.
1845 Otherwise, we know the pointers are equivalent, but not the
1846 locations. */
1848 if (graph->label[FIRST_ADDR_NODE + node] == 0)
1850 gcc_assert (label < graph->size);
1852 if (graph->eq_rep[label] != -1)
1854 /* Unify the two variables since we know they are equivalent. */
1855 if (unite (graph->eq_rep[label], node))
1856 unify_nodes (graph, graph->eq_rep[label], node, false);
1857 return graph->eq_rep[label];
1859 else
1861 graph->eq_rep[label] = node;
1864 return node;
1867 /* Move complex constraints to the appropriate nodes, and collapse
1868 variables we've discovered are equivalent during variable
1869 substitution. SI is the SCC_INFO that is the result of
1870 perform_variable_substitution. */
1872 static void
1873 move_complex_constraints (constraint_graph_t graph,
1874 struct scc_info *si)
1876 int i;
1877 unsigned int j;
1878 constraint_t c;
1880 for (j = 0; j < graph->size; j++)
1881 gcc_assert (find (j) == j);
1883 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1885 struct constraint_expr lhs = c->lhs;
1886 struct constraint_expr rhs = c->rhs;
1887 unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
1888 unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
1889 unsigned int lhsnode, rhsnode;
1890 unsigned int lhslabel, rhslabel;
1892 lhsnode = si->node_mapping[lhsvar];
1893 rhsnode = si->node_mapping[rhsvar];
1894 lhslabel = graph->label[lhsnode];
1895 rhslabel = graph->label[rhsnode];
1897 /* See if it is really a non-pointer variable, and if so, ignore
1898 the constraint. */
1899 if (lhslabel == 0)
1901 if (!TEST_BIT (graph->direct_nodes, lhsnode))
1902 lhslabel = graph->label[lhsnode] = equivalence_class++;
1903 else
1905 if (dump_file && (dump_flags & TDF_DETAILS))
1908 fprintf (dump_file, "%s is a non-pointer variable,"
1909 "ignoring constraint:",
1910 get_varinfo (lhs.var)->name);
1911 dump_constraint (dump_file, c);
1913 VEC_replace (constraint_t, constraints, i, NULL);
1914 continue;
1918 if (rhslabel == 0)
1920 if (!TEST_BIT (graph->direct_nodes, rhsnode))
1921 rhslabel = graph->label[rhsnode] = equivalence_class++;
1922 else
1924 if (dump_file && (dump_flags & TDF_DETAILS))
1927 fprintf (dump_file, "%s is a non-pointer variable,"
1928 "ignoring constraint:",
1929 get_varinfo (rhs.var)->name);
1930 dump_constraint (dump_file, c);
1932 VEC_replace (constraint_t, constraints, i, NULL);
1933 continue;
1937 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
1938 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
1939 c->lhs.var = lhsvar;
1940 c->rhs.var = rhsvar;
1942 if (lhs.type == DEREF)
1944 if (rhs.type == ADDRESSOF || rhsvar > anything_id)
1945 insert_into_complex (graph, lhsvar, c);
1947 else if (rhs.type == DEREF)
1949 if (!(get_varinfo (lhsvar)->is_special_var))
1950 insert_into_complex (graph, rhsvar, c);
1952 else if (rhs.type != ADDRESSOF && lhsvar > anything_id
1953 && (lhs.offset != 0 || rhs.offset != 0))
1955 insert_into_complex (graph, rhsvar, c);
1961 /* Eliminate indirect cycles involving NODE. Return true if NODE was
1962 part of an SCC, false otherwise. */
1964 static bool
1965 eliminate_indirect_cycles (unsigned int node)
1967 if (graph->indirect_cycles[node] != -1
1968 && !bitmap_empty_p (get_varinfo (node)->solution))
1970 unsigned int i;
1971 VEC(unsigned,heap) *queue = NULL;
1972 int queuepos;
1973 unsigned int to = find (graph->indirect_cycles[node]);
1974 bitmap_iterator bi;
1976 /* We can't touch the solution set and call unify_nodes
1977 at the same time, because unify_nodes is going to do
1978 bitmap unions into it. */
1980 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
1982 if (find (i) == i && i != to)
1984 if (unite (to, i))
1985 VEC_safe_push (unsigned, heap, queue, i);
1989 for (queuepos = 0;
1990 VEC_iterate (unsigned, queue, queuepos, i);
1991 queuepos++)
1993 unify_nodes (graph, to, i, true);
1995 VEC_free (unsigned, heap, queue);
1996 return true;
1998 return false;
2001 /* Solve the constraint graph GRAPH using our worklist solver.
2002 This is based on the PW* family of solvers from the "Efficient Field
2003 Sensitive Pointer Analysis for C" paper.
2004 It works by iterating over all the graph nodes, processing the complex
2005 constraints and propagating the copy constraints, until everything stops
2006 changed. This corresponds to steps 6-8 in the solving list given above. */
2008 static void
2009 solve_graph (constraint_graph_t graph)
2011 unsigned int size = VEC_length (varinfo_t, varmap);
2012 unsigned int i;
2013 bitmap pts;
2015 changed_count = 0;
2016 changed = sbitmap_alloc (size);
2017 sbitmap_zero (changed);
2019 /* Mark all initial non-collapsed nodes as changed. */
2020 for (i = 0; i < size; i++)
2022 varinfo_t ivi = get_varinfo (i);
2023 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2024 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2025 || VEC_length (constraint_t, graph->complex[i]) > 0))
2027 SET_BIT (changed, i);
2028 changed_count++;
2032 /* Allocate a bitmap to be used to store the changed bits. */
2033 pts = BITMAP_ALLOC (&pta_obstack);
2035 while (changed_count > 0)
2037 unsigned int i;
2038 struct topo_info *ti = init_topo_info ();
2039 stats.iterations++;
2041 bitmap_obstack_initialize (&iteration_obstack);
2043 compute_topo_order (graph, ti);
2045 while (VEC_length (unsigned, ti->topo_order) != 0)
2048 i = VEC_pop (unsigned, ti->topo_order);
2050 /* If this variable is not a representative, skip it. */
2051 if (find (i) != i)
2052 continue;
2054 /* In certain indirect cycle cases, we may merge this
2055 variable to another. */
2056 if (eliminate_indirect_cycles (i) && find (i) != i)
2057 continue;
2059 /* If the node has changed, we need to process the
2060 complex constraints and outgoing edges again. */
2061 if (TEST_BIT (changed, i))
2063 unsigned int j;
2064 constraint_t c;
2065 bitmap solution;
2066 VEC(constraint_t,heap) *complex = graph->complex[i];
2067 bool solution_empty;
2069 RESET_BIT (changed, i);
2070 changed_count--;
2072 /* Compute the changed set of solution bits. */
2073 bitmap_and_compl (pts, get_varinfo (i)->solution,
2074 get_varinfo (i)->oldsolution);
2076 if (bitmap_empty_p (pts))
2077 continue;
2079 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2081 solution = get_varinfo (i)->solution;
2082 solution_empty = bitmap_empty_p (solution);
2084 /* Process the complex constraints */
2085 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2087 /* The only complex constraint that can change our
2088 solution to non-empty, given an empty solution,
2089 is a constraint where the lhs side is receiving
2090 some set from elsewhere. */
2091 if (!solution_empty || c->lhs.type != DEREF)
2092 do_complex_constraint (graph, c, pts);
2095 solution_empty = bitmap_empty_p (solution);
2097 if (!solution_empty)
2099 bitmap_iterator bi;
2101 /* Propagate solution to all successors. */
2102 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2103 0, j, bi)
2105 bitmap tmp;
2106 bool flag;
2108 unsigned int to = find (j);
2109 tmp = get_varinfo (to)->solution;
2110 flag = false;
2112 /* Don't try to propagate to ourselves. */
2113 if (to == i)
2114 continue;
2116 flag = set_union_with_increment (tmp, pts, 0);
2118 if (flag)
2120 get_varinfo (to)->solution = tmp;
2121 if (!TEST_BIT (changed, to))
2123 SET_BIT (changed, to);
2124 changed_count++;
2131 free_topo_info (ti);
2132 bitmap_obstack_release (&iteration_obstack);
2135 BITMAP_FREE (pts);
2136 sbitmap_free (changed);
2137 bitmap_obstack_release (&oldpta_obstack);
2140 /* Map from trees to variable infos. */
2141 static struct pointer_map_t *vi_for_tree;
2144 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2146 static void
2147 insert_vi_for_tree (tree t, varinfo_t vi)
2149 void **slot = pointer_map_insert (vi_for_tree, t);
2150 gcc_assert (vi);
2151 gcc_assert (*slot == NULL);
2152 *slot = vi;
2155 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2156 exist in the map, return NULL, otherwise, return the varinfo we found. */
2158 static varinfo_t
2159 lookup_vi_for_tree (tree t)
2161 void **slot = pointer_map_contains (vi_for_tree, t);
2162 if (slot == NULL)
2163 return NULL;
2165 return (varinfo_t) *slot;
2168 /* Return a printable name for DECL */
2170 static const char *
2171 alias_get_name (tree decl)
2173 const char *res = get_name (decl);
2174 char *temp;
2175 int num_printed = 0;
2177 if (res != NULL)
2178 return res;
2180 res = "NULL";
2181 if (!dump_file)
2182 return res;
2184 if (TREE_CODE (decl) == SSA_NAME)
2186 num_printed = asprintf (&temp, "%s_%u",
2187 alias_get_name (SSA_NAME_VAR (decl)),
2188 SSA_NAME_VERSION (decl));
2190 else if (DECL_P (decl))
2192 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2194 if (num_printed > 0)
2196 res = ggc_strdup (temp);
2197 free (temp);
2199 return res;
2202 /* Find the variable id for tree T in the map.
2203 If T doesn't exist in the map, create an entry for it and return it. */
2205 static varinfo_t
2206 get_vi_for_tree (tree t)
2208 void **slot = pointer_map_contains (vi_for_tree, t);
2209 if (slot == NULL)
2210 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2212 return (varinfo_t) *slot;
2215 /* Get a constraint expression from an SSA_VAR_P node. */
2217 static struct constraint_expr
2218 get_constraint_exp_from_ssa_var (tree t)
2220 struct constraint_expr cexpr;
2222 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2224 /* For parameters, get at the points-to set for the actual parm
2225 decl. */
2226 if (TREE_CODE (t) == SSA_NAME
2227 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2228 && SSA_NAME_IS_DEFAULT_DEF (t))
2229 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2231 cexpr.type = SCALAR;
2233 cexpr.var = get_vi_for_tree (t)->id;
2234 /* If we determine the result is "anything", and we know this is readonly,
2235 say it points to readonly memory instead. */
2236 if (cexpr.var == anything_id && TREE_READONLY (t))
2238 cexpr.type = ADDRESSOF;
2239 cexpr.var = readonly_id;
2242 cexpr.offset = 0;
2243 return cexpr;
2246 /* Process a completed constraint T, and add it to the constraint
2247 list. */
2249 static void
2250 process_constraint (constraint_t t)
2252 struct constraint_expr rhs = t->rhs;
2253 struct constraint_expr lhs = t->lhs;
2255 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2256 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2258 if (lhs.type == DEREF)
2259 get_varinfo (lhs.var)->directly_dereferenced = true;
2260 if (rhs.type == DEREF)
2261 get_varinfo (rhs.var)->directly_dereferenced = true;
2263 if (!use_field_sensitive)
2265 t->rhs.offset = 0;
2266 t->lhs.offset = 0;
2269 /* ANYTHING == ANYTHING is pointless. */
2270 if (lhs.var == anything_id && rhs.var == anything_id)
2271 return;
2273 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2274 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2276 rhs = t->lhs;
2277 t->lhs = t->rhs;
2278 t->rhs = rhs;
2279 process_constraint (t);
2281 /* This can happen in our IR with things like n->a = *p */
2282 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2284 /* Split into tmp = *rhs, *lhs = tmp */
2285 tree rhsdecl = get_varinfo (rhs.var)->decl;
2286 tree pointertype = TREE_TYPE (rhsdecl);
2287 tree pointedtotype = TREE_TYPE (pointertype);
2288 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2289 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2291 /* If this is an aggregate of known size, we should have passed
2292 this off to do_structure_copy, and it should have broken it
2293 up. */
2294 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
2295 || get_varinfo (rhs.var)->is_unknown_size_var);
2297 process_constraint (new_constraint (tmplhs, rhs));
2298 process_constraint (new_constraint (lhs, tmplhs));
2300 else
2302 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2303 VEC_safe_push (constraint_t, heap, constraints, t);
2307 /* Return true if T is a variable of a type that could contain
2308 pointers. */
2310 static bool
2311 could_have_pointers (tree t)
2313 tree type = TREE_TYPE (t);
2315 if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type)
2316 || TREE_CODE (type) == COMPLEX_TYPE)
2317 return true;
2318 return false;
2321 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2322 structure. */
2324 static unsigned HOST_WIDE_INT
2325 bitpos_of_field (const tree fdecl)
2328 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2329 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2330 return -1;
2332 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2333 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2337 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2338 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2340 static bool
2341 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
2342 const unsigned HOST_WIDE_INT fieldsize,
2343 const unsigned HOST_WIDE_INT accesspos,
2344 const unsigned HOST_WIDE_INT accesssize)
2346 if (fieldpos == accesspos && fieldsize == accesssize)
2347 return true;
2348 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2349 return true;
2350 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2351 return true;
2353 return false;
2356 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2358 static void
2359 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
2361 tree orig_t = t;
2362 HOST_WIDE_INT bitsize = -1;
2363 HOST_WIDE_INT bitmaxsize = -1;
2364 HOST_WIDE_INT bitpos;
2365 tree forzero;
2366 struct constraint_expr *result;
2367 unsigned int beforelength = VEC_length (ce_s, *results);
2369 /* Some people like to do cute things like take the address of
2370 &0->a.b */
2371 forzero = t;
2372 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2373 forzero = TREE_OPERAND (forzero, 0);
2375 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2377 struct constraint_expr temp;
2379 temp.offset = 0;
2380 temp.var = integer_id;
2381 temp.type = SCALAR;
2382 VEC_safe_push (ce_s, heap, *results, &temp);
2383 return;
2386 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2388 /* String constants are readonly, so there is nothing to really do
2389 here. */
2390 if (TREE_CODE (t) == STRING_CST)
2391 return;
2393 get_constraint_for (t, results);
2394 result = VEC_last (ce_s, *results);
2395 result->offset = bitpos;
2397 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2399 /* This can also happen due to weird offsetof type macros. */
2400 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2401 result->type = SCALAR;
2403 if (result->type == SCALAR)
2405 /* In languages like C, you can access one past the end of an
2406 array. You aren't allowed to dereference it, so we can
2407 ignore this constraint. When we handle pointer subtraction,
2408 we may have to do something cute here. */
2410 if (result->offset < get_varinfo (result->var)->fullsize
2411 && bitmaxsize != 0)
2413 /* It's also not true that the constraint will actually start at the
2414 right offset, it may start in some padding. We only care about
2415 setting the constraint to the first actual field it touches, so
2416 walk to find it. */
2417 varinfo_t curr;
2418 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2420 if (offset_overlaps_with_access (curr->offset, curr->size,
2421 result->offset, bitmaxsize))
2423 result->var = curr->id;
2424 break;
2427 /* assert that we found *some* field there. The user couldn't be
2428 accessing *only* padding. */
2429 /* Still the user could access one past the end of an array
2430 embedded in a struct resulting in accessing *only* padding. */
2431 gcc_assert (curr || ref_contains_array_ref (orig_t));
2433 else if (bitmaxsize == 0)
2435 if (dump_file && (dump_flags & TDF_DETAILS))
2436 fprintf (dump_file, "Access to zero-sized part of variable,"
2437 "ignoring\n");
2439 else
2440 if (dump_file && (dump_flags & TDF_DETAILS))
2441 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2443 result->offset = 0;
2448 /* Dereference the constraint expression CONS, and return the result.
2449 DEREF (ADDRESSOF) = SCALAR
2450 DEREF (SCALAR) = DEREF
2451 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2452 This is needed so that we can handle dereferencing DEREF constraints. */
2454 static void
2455 do_deref (VEC (ce_s, heap) **constraints)
2457 struct constraint_expr *c;
2458 unsigned int i = 0;
2460 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2462 if (c->type == SCALAR)
2463 c->type = DEREF;
2464 else if (c->type == ADDRESSOF)
2465 c->type = SCALAR;
2466 else if (c->type == DEREF)
2468 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2469 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2470 process_constraint (new_constraint (tmplhs, *c));
2471 c->var = tmplhs.var;
2473 else
2474 gcc_unreachable ();
2478 /* Given a tree T, return the constraint expression for it. */
2480 static void
2481 get_constraint_for (tree t, VEC (ce_s, heap) **results)
2483 struct constraint_expr temp;
2485 /* x = integer is all glommed to a single variable, which doesn't
2486 point to anything by itself. That is, of course, unless it is an
2487 integer constant being treated as a pointer, in which case, we
2488 will return that this is really the addressof anything. This
2489 happens below, since it will fall into the default case. The only
2490 case we know something about an integer treated like a pointer is
2491 when it is the NULL pointer, and then we just say it points to
2492 NULL. */
2493 if (TREE_CODE (t) == INTEGER_CST
2494 && !POINTER_TYPE_P (TREE_TYPE (t)))
2496 temp.var = integer_id;
2497 temp.type = SCALAR;
2498 temp.offset = 0;
2499 VEC_safe_push (ce_s, heap, *results, &temp);
2500 return;
2502 else if (TREE_CODE (t) == INTEGER_CST
2503 && integer_zerop (t))
2505 temp.var = nothing_id;
2506 temp.type = ADDRESSOF;
2507 temp.offset = 0;
2508 VEC_safe_push (ce_s, heap, *results, &temp);
2509 return;
2512 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2514 case tcc_expression:
2515 case tcc_vl_exp:
2517 switch (TREE_CODE (t))
2519 case ADDR_EXPR:
2521 struct constraint_expr *c;
2522 unsigned int i;
2523 tree exp = TREE_OPERAND (t, 0);
2524 tree pttype = TREE_TYPE (TREE_TYPE (t));
2526 get_constraint_for (exp, results);
2527 /* Make sure we capture constraints to all elements
2528 of an array. */
2529 if ((handled_component_p (exp)
2530 && ref_contains_array_ref (exp))
2531 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2533 struct constraint_expr *origrhs;
2534 varinfo_t origvar;
2535 struct constraint_expr tmp;
2537 if (VEC_length (ce_s, *results) == 0)
2538 return;
2540 gcc_assert (VEC_length (ce_s, *results) == 1);
2541 origrhs = VEC_last (ce_s, *results);
2542 tmp = *origrhs;
2543 VEC_pop (ce_s, *results);
2544 origvar = get_varinfo (origrhs->var);
2545 for (; origvar; origvar = origvar->next)
2547 tmp.var = origvar->id;
2548 VEC_safe_push (ce_s, heap, *results, &tmp);
2551 else if (VEC_length (ce_s, *results) == 1
2552 && (AGGREGATE_TYPE_P (pttype)
2553 || TREE_CODE (pttype) == COMPLEX_TYPE))
2555 struct constraint_expr *origrhs;
2556 varinfo_t origvar;
2557 struct constraint_expr tmp;
2559 gcc_assert (VEC_length (ce_s, *results) == 1);
2560 origrhs = VEC_last (ce_s, *results);
2561 tmp = *origrhs;
2562 VEC_pop (ce_s, *results);
2563 origvar = get_varinfo (origrhs->var);
2564 for (; origvar; origvar = origvar->next)
2566 tmp.var = origvar->id;
2567 VEC_safe_push (ce_s, heap, *results, &tmp);
2571 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2573 if (c->type == DEREF)
2574 c->type = SCALAR;
2575 else
2576 c->type = ADDRESSOF;
2578 return;
2580 break;
2581 case CALL_EXPR:
2582 /* XXX: In interprocedural mode, if we didn't have the
2583 body, we would need to do *each pointer argument =
2584 &ANYTHING added. */
2585 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2587 varinfo_t vi;
2588 tree heapvar = heapvar_lookup (t);
2590 if (heapvar == NULL)
2592 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2593 DECL_EXTERNAL (heapvar) = 1;
2594 get_var_ann (heapvar)->is_heapvar = 1;
2595 if (gimple_referenced_vars (cfun))
2596 add_referenced_var (heapvar);
2597 heapvar_insert (t, heapvar);
2600 temp.var = create_variable_info_for (heapvar,
2601 alias_get_name (heapvar));
2603 vi = get_varinfo (temp.var);
2604 vi->is_artificial_var = 1;
2605 vi->is_heap_var = 1;
2606 temp.type = ADDRESSOF;
2607 temp.offset = 0;
2608 VEC_safe_push (ce_s, heap, *results, &temp);
2609 return;
2611 else
2613 temp.var = anything_id;
2614 temp.type = SCALAR;
2615 temp.offset = 0;
2616 VEC_safe_push (ce_s, heap, *results, &temp);
2617 return;
2619 break;
2620 default:
2622 temp.type = ADDRESSOF;
2623 temp.var = anything_id;
2624 temp.offset = 0;
2625 VEC_safe_push (ce_s, heap, *results, &temp);
2626 return;
2630 case tcc_reference:
2632 switch (TREE_CODE (t))
2634 case INDIRECT_REF:
2636 get_constraint_for (TREE_OPERAND (t, 0), results);
2637 do_deref (results);
2638 return;
2640 case ARRAY_REF:
2641 case ARRAY_RANGE_REF:
2642 case COMPONENT_REF:
2643 get_constraint_for_component_ref (t, results);
2644 return;
2645 default:
2647 temp.type = ADDRESSOF;
2648 temp.var = anything_id;
2649 temp.offset = 0;
2650 VEC_safe_push (ce_s, heap, *results, &temp);
2651 return;
2655 case tcc_unary:
2657 switch (TREE_CODE (t))
2659 case NOP_EXPR:
2660 case CONVERT_EXPR:
2661 case NON_LVALUE_EXPR:
2663 tree op = TREE_OPERAND (t, 0);
2665 /* Cast from non-pointer to pointers are bad news for us.
2666 Anything else, we see through */
2667 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2668 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2670 get_constraint_for (op, results);
2671 return;
2674 /* FALLTHRU */
2676 default:
2678 temp.type = ADDRESSOF;
2679 temp.var = anything_id;
2680 temp.offset = 0;
2681 VEC_safe_push (ce_s, heap, *results, &temp);
2682 return;
2686 case tcc_exceptional:
2688 switch (TREE_CODE (t))
2690 case PHI_NODE:
2692 get_constraint_for (PHI_RESULT (t), results);
2693 return;
2695 break;
2696 case SSA_NAME:
2698 struct constraint_expr temp;
2699 temp = get_constraint_exp_from_ssa_var (t);
2700 VEC_safe_push (ce_s, heap, *results, &temp);
2701 return;
2703 break;
2704 default:
2706 temp.type = ADDRESSOF;
2707 temp.var = anything_id;
2708 temp.offset = 0;
2709 VEC_safe_push (ce_s, heap, *results, &temp);
2710 return;
2714 case tcc_declaration:
2716 struct constraint_expr temp;
2717 temp = get_constraint_exp_from_ssa_var (t);
2718 VEC_safe_push (ce_s, heap, *results, &temp);
2719 return;
2721 default:
2723 temp.type = ADDRESSOF;
2724 temp.var = anything_id;
2725 temp.offset = 0;
2726 VEC_safe_push (ce_s, heap, *results, &temp);
2727 return;
2733 /* Handle the structure copy case where we have a simple structure copy
2734 between LHS and RHS that is of SIZE (in bits)
2736 For each field of the lhs variable (lhsfield)
2737 For each field of the rhs variable at lhsfield.offset (rhsfield)
2738 add the constraint lhsfield = rhsfield
2740 If we fail due to some kind of type unsafety or other thing we
2741 can't handle, return false. We expect the caller to collapse the
2742 variable in that case. */
2744 static bool
2745 do_simple_structure_copy (const struct constraint_expr lhs,
2746 const struct constraint_expr rhs,
2747 const unsigned HOST_WIDE_INT size)
2749 varinfo_t p = get_varinfo (lhs.var);
2750 unsigned HOST_WIDE_INT pstart, last;
2751 pstart = p->offset;
2752 last = p->offset + size;
2753 for (; p && p->offset < last; p = p->next)
2755 varinfo_t q;
2756 struct constraint_expr templhs = lhs;
2757 struct constraint_expr temprhs = rhs;
2758 unsigned HOST_WIDE_INT fieldoffset;
2760 templhs.var = p->id;
2761 q = get_varinfo (temprhs.var);
2762 fieldoffset = p->offset - pstart;
2763 q = first_vi_for_offset (q, q->offset + fieldoffset);
2764 if (!q)
2765 return false;
2766 temprhs.var = q->id;
2767 process_constraint (new_constraint (templhs, temprhs));
2769 return true;
2773 /* Handle the structure copy case where we have a structure copy between a
2774 aggregate on the LHS and a dereference of a pointer on the RHS
2775 that is of SIZE (in bits)
2777 For each field of the lhs variable (lhsfield)
2778 rhs.offset = lhsfield->offset
2779 add the constraint lhsfield = rhs
2782 static void
2783 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2784 const struct constraint_expr rhs,
2785 const unsigned HOST_WIDE_INT size)
2787 varinfo_t p = get_varinfo (lhs.var);
2788 unsigned HOST_WIDE_INT pstart,last;
2789 pstart = p->offset;
2790 last = p->offset + size;
2792 for (; p && p->offset < last; p = p->next)
2794 varinfo_t q;
2795 struct constraint_expr templhs = lhs;
2796 struct constraint_expr temprhs = rhs;
2797 unsigned HOST_WIDE_INT fieldoffset;
2800 if (templhs.type == SCALAR)
2801 templhs.var = p->id;
2802 else
2803 templhs.offset = p->offset;
2805 q = get_varinfo (temprhs.var);
2806 fieldoffset = p->offset - pstart;
2807 temprhs.offset += fieldoffset;
2808 process_constraint (new_constraint (templhs, temprhs));
2812 /* Handle the structure copy case where we have a structure copy
2813 between a aggregate on the RHS and a dereference of a pointer on
2814 the LHS that is of SIZE (in bits)
2816 For each field of the rhs variable (rhsfield)
2817 lhs.offset = rhsfield->offset
2818 add the constraint lhs = rhsfield
2821 static void
2822 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2823 const struct constraint_expr rhs,
2824 const unsigned HOST_WIDE_INT size)
2826 varinfo_t p = get_varinfo (rhs.var);
2827 unsigned HOST_WIDE_INT pstart,last;
2828 pstart = p->offset;
2829 last = p->offset + size;
2831 for (; p && p->offset < last; p = p->next)
2833 varinfo_t q;
2834 struct constraint_expr templhs = lhs;
2835 struct constraint_expr temprhs = rhs;
2836 unsigned HOST_WIDE_INT fieldoffset;
2839 if (temprhs.type == SCALAR)
2840 temprhs.var = p->id;
2841 else
2842 temprhs.offset = p->offset;
2844 q = get_varinfo (templhs.var);
2845 fieldoffset = p->offset - pstart;
2846 templhs.offset += fieldoffset;
2847 process_constraint (new_constraint (templhs, temprhs));
2851 /* Sometimes, frontends like to give us bad type information. This
2852 function will collapse all the fields from VAR to the end of VAR,
2853 into VAR, so that we treat those fields as a single variable.
2854 We return the variable they were collapsed into. */
2856 static unsigned int
2857 collapse_rest_of_var (unsigned int var)
2859 varinfo_t currvar = get_varinfo (var);
2860 varinfo_t field;
2862 for (field = currvar->next; field; field = field->next)
2864 if (dump_file)
2865 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2866 field->name, currvar->name);
2868 gcc_assert (!field->collapsed_to);
2869 field->collapsed_to = currvar;
2872 currvar->next = NULL;
2873 currvar->size = currvar->fullsize - currvar->offset;
2875 return currvar->id;
2878 /* Handle aggregate copies by expanding into copies of the respective
2879 fields of the structures. */
2881 static void
2882 do_structure_copy (tree lhsop, tree rhsop)
2884 struct constraint_expr lhs, rhs, tmp;
2885 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2886 varinfo_t p;
2887 unsigned HOST_WIDE_INT lhssize;
2888 unsigned HOST_WIDE_INT rhssize;
2890 get_constraint_for (lhsop, &lhsc);
2891 get_constraint_for (rhsop, &rhsc);
2892 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2893 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2894 lhs = *(VEC_last (ce_s, lhsc));
2895 rhs = *(VEC_last (ce_s, rhsc));
2897 VEC_free (ce_s, heap, lhsc);
2898 VEC_free (ce_s, heap, rhsc);
2900 /* If we have special var = x, swap it around. */
2901 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2903 tmp = lhs;
2904 lhs = rhs;
2905 rhs = tmp;
2908 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2909 possible it's something we could handle. However, most cases falling
2910 into this are dealing with transparent unions, which are slightly
2911 weird. */
2912 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2914 rhs.type = ADDRESSOF;
2915 rhs.var = anything_id;
2918 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2919 that special var. */
2920 if (rhs.var <= integer_id)
2922 for (p = get_varinfo (lhs.var); p; p = p->next)
2924 struct constraint_expr templhs = lhs;
2925 struct constraint_expr temprhs = rhs;
2927 if (templhs.type == SCALAR )
2928 templhs.var = p->id;
2929 else
2930 templhs.offset += p->offset;
2931 process_constraint (new_constraint (templhs, temprhs));
2934 else
2936 tree rhstype = TREE_TYPE (rhsop);
2937 tree lhstype = TREE_TYPE (lhsop);
2938 tree rhstypesize;
2939 tree lhstypesize;
2941 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2942 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2944 /* If we have a variably sized types on the rhs or lhs, and a deref
2945 constraint, add the constraint, lhsconstraint = &ANYTHING.
2946 This is conservatively correct because either the lhs is an unknown
2947 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2948 constraint, and every variable it can point to must be unknown sized
2949 anyway, so we don't need to worry about fields at all. */
2950 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2951 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2953 rhs.var = anything_id;
2954 rhs.type = ADDRESSOF;
2955 rhs.offset = 0;
2956 process_constraint (new_constraint (lhs, rhs));
2957 return;
2960 /* The size only really matters insofar as we don't set more or less of
2961 the variable. If we hit an unknown size var, the size should be the
2962 whole darn thing. */
2963 if (get_varinfo (rhs.var)->is_unknown_size_var)
2964 rhssize = ~0;
2965 else
2966 rhssize = TREE_INT_CST_LOW (rhstypesize);
2968 if (get_varinfo (lhs.var)->is_unknown_size_var)
2969 lhssize = ~0;
2970 else
2971 lhssize = TREE_INT_CST_LOW (lhstypesize);
2974 if (rhs.type == SCALAR && lhs.type == SCALAR)
2976 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
2978 lhs.var = collapse_rest_of_var (lhs.var);
2979 rhs.var = collapse_rest_of_var (rhs.var);
2980 lhs.offset = 0;
2981 rhs.offset = 0;
2982 lhs.type = SCALAR;
2983 rhs.type = SCALAR;
2984 process_constraint (new_constraint (lhs, rhs));
2987 else if (lhs.type != DEREF && rhs.type == DEREF)
2988 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2989 else if (lhs.type == DEREF && rhs.type != DEREF)
2990 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2991 else
2993 tree pointedtotype = lhstype;
2994 tree tmpvar;
2996 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2997 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2998 do_structure_copy (tmpvar, rhsop);
2999 do_structure_copy (lhsop, tmpvar);
3004 /* Update related alias information kept in AI. This is used when
3005 building name tags, alias sets and deciding grouping heuristics.
3006 STMT is the statement to process. This function also updates
3007 ADDRESSABLE_VARS. */
3009 static void
3010 update_alias_info (tree stmt, struct alias_info *ai)
3012 bitmap addr_taken;
3013 use_operand_p use_p;
3014 ssa_op_iter iter;
3015 enum escape_type stmt_escape_type = is_escape_site (stmt);
3017 if (stmt_escape_type == ESCAPE_TO_CALL
3018 || stmt_escape_type == ESCAPE_TO_PURE_CONST)
3020 ai->num_calls_found++;
3021 if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
3022 ai->num_pure_const_calls_found++;
3025 /* Mark all the variables whose address are taken by the statement. */
3026 addr_taken = addresses_taken (stmt);
3027 if (addr_taken)
3029 bitmap_ior_into (gimple_addressable_vars (cfun), addr_taken);
3031 /* If STMT is an escape point, all the addresses taken by it are
3032 call-clobbered. */
3033 if (stmt_escape_type != NO_ESCAPE)
3035 bitmap_iterator bi;
3036 unsigned i;
3038 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
3040 tree rvar = referenced_var (i);
3041 if (!unmodifiable_var_p (rvar))
3042 mark_call_clobbered (rvar, stmt_escape_type);
3047 /* Process each operand use. If an operand may be aliased, keep
3048 track of how many times it's being used. For pointers, determine
3049 whether they are dereferenced by the statement, or whether their
3050 value escapes, etc. */
3051 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3053 tree op, var;
3054 var_ann_t v_ann;
3055 struct ptr_info_def *pi;
3056 bool is_store, is_potential_deref;
3057 unsigned num_uses, num_derefs;
3059 op = USE_FROM_PTR (use_p);
3061 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3062 to the set of addressable variables. */
3063 if (TREE_CODE (op) == ADDR_EXPR)
3065 bitmap addressable_vars = gimple_addressable_vars (cfun);
3067 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
3068 gcc_assert (addressable_vars);
3070 /* PHI nodes don't have annotations for pinning the set
3071 of addresses taken, so we collect them here.
3073 FIXME, should we allow PHI nodes to have annotations
3074 so that they can be treated like regular statements?
3075 Currently, they are treated as second-class
3076 statements. */
3077 add_to_addressable_set (TREE_OPERAND (op, 0),
3078 &addressable_vars);
3079 continue;
3082 /* Ignore constants. */
3083 if (TREE_CODE (op) != SSA_NAME)
3084 continue;
3086 var = SSA_NAME_VAR (op);
3087 v_ann = var_ann (var);
3089 /* The base variable of an SSA name must be a GIMPLE register, and thus
3090 it cannot be aliased. */
3091 gcc_assert (!may_be_aliased (var));
3093 /* We are only interested in pointers. */
3094 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3095 continue;
3097 pi = get_ptr_info (op);
3099 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3100 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3102 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3103 VEC_safe_push (tree, heap, ai->processed_ptrs, op);
3106 /* If STMT is a PHI node, then it will not have pointer
3107 dereferences and it will not be an escape point. */
3108 if (TREE_CODE (stmt) == PHI_NODE)
3109 continue;
3111 /* Determine whether OP is a dereferenced pointer, and if STMT
3112 is an escape point, whether OP escapes. */
3113 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
3115 /* Handle a corner case involving address expressions of the
3116 form '&PTR->FLD'. The problem with these expressions is that
3117 they do not represent a dereference of PTR. However, if some
3118 other transformation propagates them into an INDIRECT_REF
3119 expression, we end up with '*(&PTR->FLD)' which is folded
3120 into 'PTR->FLD'.
3122 So, if the original code had no other dereferences of PTR,
3123 the aliaser will not create memory tags for it, and when
3124 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3125 memory operations will receive no VDEF/VUSE operands.
3127 One solution would be to have count_uses_and_derefs consider
3128 &PTR->FLD a dereference of PTR. But that is wrong, since it
3129 is not really a dereference but an offset calculation.
3131 What we do here is to recognize these special ADDR_EXPR
3132 nodes. Since these expressions are never GIMPLE values (they
3133 are not GIMPLE invariants), they can only appear on the RHS
3134 of an assignment and their base address is always an
3135 INDIRECT_REF expression. */
3136 is_potential_deref = false;
3137 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3138 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ADDR_EXPR
3139 && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt, 1)))
3141 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3142 this represents a potential dereference of PTR. */
3143 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3144 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3145 if (TREE_CODE (base) == INDIRECT_REF
3146 && TREE_OPERAND (base, 0) == op)
3147 is_potential_deref = true;
3150 if (num_derefs > 0 || is_potential_deref)
3152 /* Mark OP as dereferenced. In a subsequent pass,
3153 dereferenced pointers that point to a set of
3154 variables will be assigned a name tag to alias
3155 all the variables OP points to. */
3156 pi->is_dereferenced = 1;
3158 /* If this is a store operation, mark OP as being
3159 dereferenced to store, otherwise mark it as being
3160 dereferenced to load. */
3161 if (is_store)
3162 pointer_set_insert (ai->dereferenced_ptrs_store, var);
3163 else
3164 pointer_set_insert (ai->dereferenced_ptrs_load, var);
3167 if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses)
3169 /* If STMT is an escape point and STMT contains at
3170 least one direct use of OP, then the value of OP
3171 escapes and so the pointed-to variables need to
3172 be marked call-clobbered. */
3173 pi->value_escapes_p = 1;
3174 pi->escape_mask |= stmt_escape_type;
3176 /* If the statement makes a function call, assume
3177 that pointer OP will be dereferenced in a store
3178 operation inside the called function. */
3179 if (get_call_expr_in (stmt)
3180 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
3182 pointer_set_insert (ai->dereferenced_ptrs_store, var);
3183 pi->is_dereferenced = 1;
3188 if (TREE_CODE (stmt) == PHI_NODE)
3189 return;
3191 /* Mark stored variables in STMT as being written to and update the
3192 reference counter for potentially aliased symbols in STMT. */
3193 if (stmt_references_memory_p (stmt) && STORED_SYMS (stmt))
3195 unsigned i;
3196 bitmap_iterator bi;
3197 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
3198 pointer_set_insert (ai->written_vars, referenced_var (i));
3203 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3204 Expressions of the type PTR + CST can be handled in two ways:
3206 1- If the constraint for PTR is ADDRESSOF for a non-structure
3207 variable, then we can use it directly because adding or
3208 subtracting a constant may not alter the original ADDRESSOF
3209 constraint (i.e., pointer arithmetic may not legally go outside
3210 an object's boundaries).
3212 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3213 then if CST is a compile-time constant that can be used as an
3214 offset, we can determine which sub-variable will be pointed-to
3215 by the expression.
3217 Return true if the expression is handled. For any other kind of
3218 expression, return false so that each operand can be added as a
3219 separate constraint by the caller. */
3221 static bool
3222 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3224 tree op0, op1;
3225 struct constraint_expr *c, *c2;
3226 unsigned int i = 0;
3227 unsigned int j = 0;
3228 VEC (ce_s, heap) *temp = NULL;
3229 unsigned int rhsoffset = 0;
3231 if (TREE_CODE (expr) != PLUS_EXPR
3232 && TREE_CODE (expr) != MINUS_EXPR)
3233 return false;
3235 op0 = TREE_OPERAND (expr, 0);
3236 op1 = TREE_OPERAND (expr, 1);
3238 get_constraint_for (op0, &temp);
3239 if (POINTER_TYPE_P (TREE_TYPE (op0))
3240 && TREE_CODE (op1) == INTEGER_CST
3241 && TREE_CODE (expr) == PLUS_EXPR)
3243 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3245 else
3246 return false;
3249 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3250 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3252 if (c2->type == ADDRESSOF && rhsoffset != 0)
3254 varinfo_t temp = get_varinfo (c2->var);
3256 /* An access one after the end of an array is valid,
3257 so simply punt on accesses we cannot resolve. */
3258 temp = first_vi_for_offset (temp, rhsoffset);
3259 if (temp == NULL)
3260 continue;
3261 c2->var = temp->id;
3262 c2->offset = 0;
3264 else
3265 c2->offset = rhsoffset;
3266 process_constraint (new_constraint (*c, *c2));
3269 VEC_free (ce_s, heap, temp);
3271 return true;
3275 /* Walk statement T setting up aliasing constraints according to the
3276 references found in T. This function is the main part of the
3277 constraint builder. AI points to auxiliary alias information used
3278 when building alias sets and computing alias grouping heuristics. */
3280 static void
3281 find_func_aliases (tree origt)
3283 tree t = origt;
3284 VEC(ce_s, heap) *lhsc = NULL;
3285 VEC(ce_s, heap) *rhsc = NULL;
3286 struct constraint_expr *c;
3288 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3289 t = TREE_OPERAND (t, 0);
3291 /* Now build constraints expressions. */
3292 if (TREE_CODE (t) == PHI_NODE)
3294 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
3296 /* Only care about pointers and structures containing
3297 pointers. */
3298 if (could_have_pointers (PHI_RESULT (t)))
3300 int i;
3301 unsigned int j;
3303 /* For a phi node, assign all the arguments to
3304 the result. */
3305 get_constraint_for (PHI_RESULT (t), &lhsc);
3306 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3308 tree rhstype;
3309 tree strippedrhs = PHI_ARG_DEF (t, i);
3311 STRIP_NOPS (strippedrhs);
3312 rhstype = TREE_TYPE (strippedrhs);
3313 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3315 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3317 struct constraint_expr *c2;
3318 while (VEC_length (ce_s, rhsc) > 0)
3320 c2 = VEC_last (ce_s, rhsc);
3321 process_constraint (new_constraint (*c, *c2));
3322 VEC_pop (ce_s, rhsc);
3328 /* In IPA mode, we need to generate constraints to pass call
3329 arguments through their calls. There are two case, either a
3330 modify_expr when we are returning a value, or just a plain
3331 call_expr when we are not. */
3332 else if (in_ipa_mode
3333 && ((TREE_CODE (t) == GIMPLE_MODIFY_STMT
3334 && TREE_CODE (GIMPLE_STMT_OPERAND (t, 1)) == CALL_EXPR
3335 && !(call_expr_flags (GIMPLE_STMT_OPERAND (t, 1))
3336 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3337 || (TREE_CODE (t) == CALL_EXPR
3338 && !(call_expr_flags (t)
3339 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3341 tree lhsop;
3342 tree rhsop;
3343 tree arg;
3344 call_expr_arg_iterator iter;
3345 varinfo_t fi;
3346 int i = 1;
3347 tree decl;
3348 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3350 lhsop = GIMPLE_STMT_OPERAND (t, 0);
3351 rhsop = GIMPLE_STMT_OPERAND (t, 1);
3353 else
3355 lhsop = NULL;
3356 rhsop = t;
3358 decl = get_callee_fndecl (rhsop);
3360 /* If we can directly resolve the function being called, do so.
3361 Otherwise, it must be some sort of indirect expression that
3362 we should still be able to handle. */
3363 if (decl)
3365 fi = get_vi_for_tree (decl);
3367 else
3369 decl = CALL_EXPR_FN (rhsop);
3370 fi = get_vi_for_tree (decl);
3373 /* Assign all the passed arguments to the appropriate incoming
3374 parameters of the function. */
3376 FOR_EACH_CALL_EXPR_ARG (arg, iter, rhsop)
3378 struct constraint_expr lhs ;
3379 struct constraint_expr *rhsp;
3381 get_constraint_for (arg, &rhsc);
3382 if (TREE_CODE (decl) != FUNCTION_DECL)
3384 lhs.type = DEREF;
3385 lhs.var = fi->id;
3386 lhs.offset = i;
3388 else
3390 lhs.type = SCALAR;
3391 lhs.var = first_vi_for_offset (fi, i)->id;
3392 lhs.offset = 0;
3394 while (VEC_length (ce_s, rhsc) != 0)
3396 rhsp = VEC_last (ce_s, rhsc);
3397 process_constraint (new_constraint (lhs, *rhsp));
3398 VEC_pop (ce_s, rhsc);
3400 i++;
3402 /* If we are returning a value, assign it to the result. */
3403 if (lhsop)
3405 struct constraint_expr rhs;
3406 struct constraint_expr *lhsp;
3407 unsigned int j = 0;
3409 get_constraint_for (lhsop, &lhsc);
3410 if (TREE_CODE (decl) != FUNCTION_DECL)
3412 rhs.type = DEREF;
3413 rhs.var = fi->id;
3414 rhs.offset = i;
3416 else
3418 rhs.type = SCALAR;
3419 rhs.var = first_vi_for_offset (fi, i)->id;
3420 rhs.offset = 0;
3422 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3423 process_constraint (new_constraint (*lhsp, rhs));
3426 /* Otherwise, just a regular assignment statement. */
3427 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3429 tree lhsop = GIMPLE_STMT_OPERAND (t, 0);
3430 tree rhsop = GIMPLE_STMT_OPERAND (t, 1);
3431 int i;
3433 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3434 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3435 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3436 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3438 do_structure_copy (lhsop, rhsop);
3440 else
3442 /* Only care about operations with pointers, structures
3443 containing pointers, dereferences, and call expressions. */
3444 if (could_have_pointers (lhsop)
3445 || TREE_CODE (rhsop) == CALL_EXPR)
3447 get_constraint_for (lhsop, &lhsc);
3448 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3450 /* RHS that consist of unary operations,
3451 exceptional types, or bare decls/constants, get
3452 handled directly by get_constraint_for. */
3453 case tcc_reference:
3454 case tcc_declaration:
3455 case tcc_constant:
3456 case tcc_exceptional:
3457 case tcc_expression:
3458 case tcc_vl_exp:
3459 case tcc_unary:
3461 unsigned int j;
3463 get_constraint_for (rhsop, &rhsc);
3464 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3466 struct constraint_expr *c2;
3467 unsigned int k;
3469 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3470 process_constraint (new_constraint (*c, *c2));
3474 break;
3476 case tcc_binary:
3478 /* For pointer arithmetic of the form
3479 PTR + CST, we can simply use PTR's
3480 constraint because pointer arithmetic is
3481 not allowed to go out of bounds. */
3482 if (handle_ptr_arith (lhsc, rhsop))
3483 break;
3485 /* FALLTHRU */
3487 /* Otherwise, walk each operand. Notice that we
3488 can't use the operand interface because we need
3489 to process expressions other than simple operands
3490 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3491 default:
3492 for (i = 0; i < TREE_OPERAND_LENGTH (rhsop); i++)
3494 tree op = TREE_OPERAND (rhsop, i);
3495 unsigned int j;
3497 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3498 get_constraint_for (op, &rhsc);
3499 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3501 struct constraint_expr *c2;
3502 while (VEC_length (ce_s, rhsc) > 0)
3504 c2 = VEC_last (ce_s, rhsc);
3505 process_constraint (new_constraint (*c, *c2));
3506 VEC_pop (ce_s, rhsc);
3515 /* After promoting variables and computing aliasing we will
3516 need to re-scan most statements. FIXME: Try to minimize the
3517 number of statements re-scanned. It's not really necessary to
3518 re-scan *all* statements. */
3519 mark_stmt_modified (origt);
3520 VEC_free (ce_s, heap, rhsc);
3521 VEC_free (ce_s, heap, lhsc);
3525 /* Find the first varinfo in the same variable as START that overlaps with
3526 OFFSET.
3527 Effectively, walk the chain of fields for the variable START to find the
3528 first field that overlaps with OFFSET.
3529 Return NULL if we can't find one. */
3531 static varinfo_t
3532 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3534 varinfo_t curr = start;
3535 while (curr)
3537 /* We may not find a variable in the field list with the actual
3538 offset when when we have glommed a structure to a variable.
3539 In that case, however, offset should still be within the size
3540 of the variable. */
3541 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3542 return curr;
3543 curr = curr->next;
3545 return NULL;
3549 /* Insert the varinfo FIELD into the field list for BASE, at the front
3550 of the list. */
3552 static void
3553 insert_into_field_list (varinfo_t base, varinfo_t field)
3555 varinfo_t prev = base;
3556 varinfo_t curr = base->next;
3558 field->next = curr;
3559 prev->next = field;
3562 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3563 offset. */
3565 static void
3566 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3568 varinfo_t prev = base;
3569 varinfo_t curr = base->next;
3571 if (curr == NULL)
3573 prev->next = field;
3574 field->next = NULL;
3576 else
3578 while (curr)
3580 if (field->offset <= curr->offset)
3581 break;
3582 prev = curr;
3583 curr = curr->next;
3585 field->next = prev->next;
3586 prev->next = field;
3590 /* qsort comparison function for two fieldoff's PA and PB */
3592 static int
3593 fieldoff_compare (const void *pa, const void *pb)
3595 const fieldoff_s *foa = (const fieldoff_s *)pa;
3596 const fieldoff_s *fob = (const fieldoff_s *)pb;
3597 HOST_WIDE_INT foasize, fobsize;
3599 if (foa->offset != fob->offset)
3600 return foa->offset - fob->offset;
3602 foasize = TREE_INT_CST_LOW (foa->size);
3603 fobsize = TREE_INT_CST_LOW (fob->size);
3604 return foasize - fobsize;
3607 /* Sort a fieldstack according to the field offset and sizes. */
3608 void
3609 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3611 qsort (VEC_address (fieldoff_s, fieldstack),
3612 VEC_length (fieldoff_s, fieldstack),
3613 sizeof (fieldoff_s),
3614 fieldoff_compare);
3617 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3618 of TYPE onto fieldstack, recording their offsets along the way.
3619 OFFSET is used to keep track of the offset in this entire structure, rather
3620 than just the immediately containing structure. Returns the number
3621 of fields pushed.
3622 HAS_UNION is set to true if we find a union type as a field of
3623 TYPE. */
3626 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3627 HOST_WIDE_INT offset, bool *has_union)
3629 tree field;
3630 int count = 0;
3632 if (TREE_CODE (type) == COMPLEX_TYPE)
3634 fieldoff_s *real_part, *img_part;
3635 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3636 real_part->type = TREE_TYPE (type);
3637 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3638 real_part->offset = offset;
3639 real_part->decl = NULL_TREE;
3641 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3642 img_part->type = TREE_TYPE (type);
3643 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3644 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3645 img_part->decl = NULL_TREE;
3647 return 2;
3650 if (TREE_CODE (type) == ARRAY_TYPE)
3652 tree sz = TYPE_SIZE (type);
3653 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3654 HOST_WIDE_INT nr;
3655 int i;
3657 if (! sz
3658 || ! host_integerp (sz, 1)
3659 || TREE_INT_CST_LOW (sz) == 0
3660 || ! elsz
3661 || ! host_integerp (elsz, 1)
3662 || TREE_INT_CST_LOW (elsz) == 0)
3663 return 0;
3665 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3666 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3667 return 0;
3669 for (i = 0; i < nr; ++i)
3671 bool push = false;
3672 int pushed = 0;
3674 if (has_union
3675 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3676 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3677 *has_union = true;
3679 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3680 push = true;
3681 else if (!(pushed = push_fields_onto_fieldstack
3682 (TREE_TYPE (type), fieldstack,
3683 offset + i * TREE_INT_CST_LOW (elsz), has_union)))
3684 /* Empty structures may have actual size, like in C++. So
3685 see if we didn't push any subfields and the size is
3686 nonzero, push the field onto the stack */
3687 push = true;
3689 if (push)
3691 fieldoff_s *pair;
3693 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3694 pair->type = TREE_TYPE (type);
3695 pair->size = elsz;
3696 pair->decl = NULL_TREE;
3697 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3698 count++;
3700 else
3701 count += pushed;
3704 return count;
3707 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3708 if (TREE_CODE (field) == FIELD_DECL)
3710 bool push = false;
3711 int pushed = 0;
3713 if (has_union
3714 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3715 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3716 *has_union = true;
3718 if (!var_can_have_subvars (field))
3719 push = true;
3720 else if (!(pushed = push_fields_onto_fieldstack
3721 (TREE_TYPE (field), fieldstack,
3722 offset + bitpos_of_field (field), has_union))
3723 && DECL_SIZE (field)
3724 && !integer_zerop (DECL_SIZE (field)))
3725 /* Empty structures may have actual size, like in C++. So
3726 see if we didn't push any subfields and the size is
3727 nonzero, push the field onto the stack */
3728 push = true;
3730 if (push)
3732 fieldoff_s *pair;
3734 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3735 pair->type = TREE_TYPE (field);
3736 pair->size = DECL_SIZE (field);
3737 pair->decl = field;
3738 pair->offset = offset + bitpos_of_field (field);
3739 count++;
3741 else
3742 count += pushed;
3745 return count;
3748 /* Create a constraint from ANYTHING variable to VI. */
3749 static void
3750 make_constraint_from_anything (varinfo_t vi)
3752 struct constraint_expr lhs, rhs;
3754 lhs.var = vi->id;
3755 lhs.offset = 0;
3756 lhs.type = SCALAR;
3758 rhs.var = anything_id;
3759 rhs.offset = 0;
3760 rhs.type = ADDRESSOF;
3761 process_constraint (new_constraint (lhs, rhs));
3764 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3765 if it is a varargs function. */
3767 static unsigned int
3768 count_num_arguments (tree decl, bool *is_varargs)
3770 unsigned int i = 0;
3771 tree t;
3773 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3775 t = TREE_CHAIN (t))
3777 if (TREE_VALUE (t) == void_type_node)
3778 break;
3779 i++;
3782 if (!t)
3783 *is_varargs = true;
3784 return i;
3787 /* Creation function node for DECL, using NAME, and return the index
3788 of the variable we've created for the function. */
3790 static unsigned int
3791 create_function_info_for (tree decl, const char *name)
3793 unsigned int index = VEC_length (varinfo_t, varmap);
3794 varinfo_t vi;
3795 tree arg;
3796 unsigned int i;
3797 bool is_varargs = false;
3799 /* Create the variable info. */
3801 vi = new_var_info (decl, index, name);
3802 vi->decl = decl;
3803 vi->offset = 0;
3804 vi->has_union = 0;
3805 vi->size = 1;
3806 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3807 insert_vi_for_tree (vi->decl, vi);
3808 VEC_safe_push (varinfo_t, heap, varmap, vi);
3810 stats.total_vars++;
3812 /* If it's varargs, we don't know how many arguments it has, so we
3813 can't do much.
3815 if (is_varargs)
3817 vi->fullsize = ~0;
3818 vi->size = ~0;
3819 vi->is_unknown_size_var = true;
3820 return index;
3824 arg = DECL_ARGUMENTS (decl);
3826 /* Set up variables for each argument. */
3827 for (i = 1; i < vi->fullsize; i++)
3829 varinfo_t argvi;
3830 const char *newname;
3831 char *tempname;
3832 unsigned int newindex;
3833 tree argdecl = decl;
3835 if (arg)
3836 argdecl = arg;
3838 newindex = VEC_length (varinfo_t, varmap);
3839 asprintf (&tempname, "%s.arg%d", name, i-1);
3840 newname = ggc_strdup (tempname);
3841 free (tempname);
3843 argvi = new_var_info (argdecl, newindex, newname);
3844 argvi->decl = argdecl;
3845 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3846 argvi->offset = i;
3847 argvi->size = 1;
3848 argvi->fullsize = vi->fullsize;
3849 argvi->has_union = false;
3850 insert_into_field_list_sorted (vi, argvi);
3851 stats.total_vars ++;
3852 if (arg)
3854 insert_vi_for_tree (arg, argvi);
3855 arg = TREE_CHAIN (arg);
3859 /* Create a variable for the return var. */
3860 if (DECL_RESULT (decl) != NULL
3861 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3863 varinfo_t resultvi;
3864 const char *newname;
3865 char *tempname;
3866 unsigned int newindex;
3867 tree resultdecl = decl;
3869 vi->fullsize ++;
3871 if (DECL_RESULT (decl))
3872 resultdecl = DECL_RESULT (decl);
3874 newindex = VEC_length (varinfo_t, varmap);
3875 asprintf (&tempname, "%s.result", name);
3876 newname = ggc_strdup (tempname);
3877 free (tempname);
3879 resultvi = new_var_info (resultdecl, newindex, newname);
3880 resultvi->decl = resultdecl;
3881 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3882 resultvi->offset = i;
3883 resultvi->size = 1;
3884 resultvi->fullsize = vi->fullsize;
3885 resultvi->has_union = false;
3886 insert_into_field_list_sorted (vi, resultvi);
3887 stats.total_vars ++;
3888 if (DECL_RESULT (decl))
3889 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
3891 return index;
3895 /* Return true if FIELDSTACK contains fields that overlap.
3896 FIELDSTACK is assumed to be sorted by offset. */
3898 static bool
3899 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3901 fieldoff_s *fo = NULL;
3902 unsigned int i;
3903 HOST_WIDE_INT lastoffset = -1;
3905 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3907 if (fo->offset == lastoffset)
3908 return true;
3909 lastoffset = fo->offset;
3911 return false;
3914 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3915 This will also create any varinfo structures necessary for fields
3916 of DECL. */
3918 static unsigned int
3919 create_variable_info_for (tree decl, const char *name)
3921 unsigned int index = VEC_length (varinfo_t, varmap);
3922 varinfo_t vi;
3923 tree decltype = TREE_TYPE (decl);
3924 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
3925 bool notokay = false;
3926 bool hasunion;
3927 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
3928 VEC (fieldoff_s,heap) *fieldstack = NULL;
3930 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
3931 return create_function_info_for (decl, name);
3933 hasunion = TREE_CODE (decltype) == UNION_TYPE
3934 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3935 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3937 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3938 if (hasunion)
3940 VEC_free (fieldoff_s, heap, fieldstack);
3941 notokay = true;
3946 /* If the variable doesn't have subvars, we may end up needing to
3947 sort the field list and create fake variables for all the
3948 fields. */
3949 vi = new_var_info (decl, index, name);
3950 vi->decl = decl;
3951 vi->offset = 0;
3952 vi->has_union = hasunion;
3953 if (!declsize
3954 || TREE_CODE (declsize) != INTEGER_CST
3955 || TREE_CODE (decltype) == UNION_TYPE
3956 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3958 vi->is_unknown_size_var = true;
3959 vi->fullsize = ~0;
3960 vi->size = ~0;
3962 else
3964 vi->fullsize = TREE_INT_CST_LOW (declsize);
3965 vi->size = vi->fullsize;
3968 insert_vi_for_tree (vi->decl, vi);
3969 VEC_safe_push (varinfo_t, heap, varmap, vi);
3970 if (is_global && (!flag_whole_program || !in_ipa_mode))
3971 make_constraint_from_anything (vi);
3973 stats.total_vars++;
3974 if (use_field_sensitive
3975 && !notokay
3976 && !vi->is_unknown_size_var
3977 && var_can_have_subvars (decl)
3978 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
3980 unsigned int newindex = VEC_length (varinfo_t, varmap);
3981 fieldoff_s *fo = NULL;
3982 unsigned int i;
3984 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3986 if (! fo->size
3987 || TREE_CODE (fo->size) != INTEGER_CST
3988 || fo->offset < 0)
3990 notokay = true;
3991 break;
3995 /* We can't sort them if we have a field with a variable sized type,
3996 which will make notokay = true. In that case, we are going to return
3997 without creating varinfos for the fields anyway, so sorting them is a
3998 waste to boot. */
3999 if (!notokay)
4001 sort_fieldstack (fieldstack);
4002 /* Due to some C++ FE issues, like PR 22488, we might end up
4003 what appear to be overlapping fields even though they,
4004 in reality, do not overlap. Until the C++ FE is fixed,
4005 we will simply disable field-sensitivity for these cases. */
4006 notokay = check_for_overlaps (fieldstack);
4010 if (VEC_length (fieldoff_s, fieldstack) != 0)
4011 fo = VEC_index (fieldoff_s, fieldstack, 0);
4013 if (fo == NULL || notokay)
4015 vi->is_unknown_size_var = 1;
4016 vi->fullsize = ~0;
4017 vi->size = ~0;
4018 VEC_free (fieldoff_s, heap, fieldstack);
4019 return index;
4022 vi->size = TREE_INT_CST_LOW (fo->size);
4023 vi->offset = fo->offset;
4024 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4025 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4026 i--)
4028 varinfo_t newvi;
4029 const char *newname = "NULL";
4030 char *tempname;
4032 newindex = VEC_length (varinfo_t, varmap);
4033 if (dump_file)
4035 if (fo->decl)
4036 asprintf (&tempname, "%s.%s",
4037 vi->name, alias_get_name (fo->decl));
4038 else
4039 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
4040 vi->name, fo->offset);
4041 newname = ggc_strdup (tempname);
4042 free (tempname);
4044 newvi = new_var_info (decl, newindex, newname);
4045 newvi->offset = fo->offset;
4046 newvi->size = TREE_INT_CST_LOW (fo->size);
4047 newvi->fullsize = vi->fullsize;
4048 insert_into_field_list (vi, newvi);
4049 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4050 if (is_global && (!flag_whole_program || !in_ipa_mode))
4051 make_constraint_from_anything (newvi);
4053 stats.total_vars++;
4055 VEC_free (fieldoff_s, heap, fieldstack);
4057 return index;
4060 /* Print out the points-to solution for VAR to FILE. */
4062 void
4063 dump_solution_for_var (FILE *file, unsigned int var)
4065 varinfo_t vi = get_varinfo (var);
4066 unsigned int i;
4067 bitmap_iterator bi;
4069 if (find (var) != var)
4071 varinfo_t vipt = get_varinfo (find (var));
4072 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4074 else
4076 fprintf (file, "%s = { ", vi->name);
4077 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4079 fprintf (file, "%s ", get_varinfo (i)->name);
4081 fprintf (file, "}\n");
4085 /* Print the points-to solution for VAR to stdout. */
4087 void
4088 debug_solution_for_var (unsigned int var)
4090 dump_solution_for_var (stdout, var);
4093 /* Create varinfo structures for all of the variables in the
4094 function for intraprocedural mode. */
4096 static void
4097 intra_create_variable_infos (void)
4099 tree t;
4100 struct constraint_expr lhs, rhs;
4102 /* For each incoming pointer argument arg, ARG = ANYTHING or a
4103 dummy variable if flag_argument_noalias > 2. */
4104 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4106 varinfo_t p;
4108 if (!could_have_pointers (t))
4109 continue;
4111 /* With flag_argument_noalias greater than two means that the incoming
4112 argument cannot alias anything except for itself so create a HEAP
4113 variable. */
4114 if (POINTER_TYPE_P (TREE_TYPE (t))
4115 && flag_argument_noalias > 2)
4117 varinfo_t vi;
4118 tree heapvar = heapvar_lookup (t);
4120 lhs.offset = 0;
4121 lhs.type = SCALAR;
4122 lhs.var = get_vi_for_tree (t)->id;
4124 if (heapvar == NULL_TREE)
4126 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4127 "PARM_NOALIAS");
4128 get_var_ann (heapvar)->is_heapvar = 1;
4129 DECL_EXTERNAL (heapvar) = 1;
4130 if (gimple_referenced_vars (cfun))
4131 add_referenced_var (heapvar);
4132 heapvar_insert (t, heapvar);
4134 vi = get_vi_for_tree (heapvar);
4135 vi->is_artificial_var = 1;
4136 vi->is_heap_var = 1;
4137 rhs.var = vi->id;
4138 rhs.type = ADDRESSOF;
4139 rhs.offset = 0;
4140 for (p = get_varinfo (lhs.var); p; p = p->next)
4142 struct constraint_expr temp = lhs;
4143 temp.var = p->id;
4144 process_constraint (new_constraint (temp, rhs));
4147 else
4149 varinfo_t arg_vi = get_vi_for_tree (t);
4151 for (p = arg_vi; p; p = p->next)
4152 make_constraint_from_anything (p);
4157 /* Set bits in INTO corresponding to the variable uids in solution set
4158 FROM, which came from variable PTR.
4159 For variables that are actually dereferenced, we also use type
4160 based alias analysis to prune the points-to sets. */
4162 static void
4163 set_uids_in_ptset (tree ptr, bitmap into, bitmap from)
4165 unsigned int i;
4166 bitmap_iterator bi;
4167 subvar_t sv;
4168 HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
4170 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4172 varinfo_t vi = get_varinfo (i);
4173 unsigned HOST_WIDE_INT var_alias_set;
4175 /* The only artificial variables that are allowed in a may-alias
4176 set are heap variables. */
4177 if (vi->is_artificial_var && !vi->is_heap_var)
4178 continue;
4180 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
4182 /* Variables containing unions may need to be converted to
4183 their SFT's, because SFT's can have unions and we cannot. */
4184 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
4185 bitmap_set_bit (into, DECL_UID (sv->var));
4187 else if (TREE_CODE (vi->decl) == VAR_DECL
4188 || TREE_CODE (vi->decl) == PARM_DECL)
4190 if (var_can_have_subvars (vi->decl)
4191 && get_subvars_for_var (vi->decl))
4193 /* If VI->DECL is an aggregate for which we created
4194 SFTs, add the SFT corresponding to VI->OFFSET. */
4195 tree sft = get_subvar_at (vi->decl, vi->offset);
4196 if (sft)
4198 var_alias_set = get_alias_set (sft);
4199 if (!vi->directly_dereferenced
4200 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4201 bitmap_set_bit (into, DECL_UID (sft));
4204 else
4206 /* Otherwise, just add VI->DECL to the alias set.
4207 Don't type prune artificial vars. */
4208 if (vi->is_artificial_var)
4209 bitmap_set_bit (into, DECL_UID (vi->decl));
4210 else
4212 var_alias_set = get_alias_set (vi->decl);
4213 if (!vi->directly_dereferenced
4214 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4215 bitmap_set_bit (into, DECL_UID (vi->decl));
4223 static bool have_alias_info = false;
4225 /* The list of SMT's that are in use by our pointer variables. This
4226 is the set of SMT's for all pointers that can point to anything. */
4227 static bitmap used_smts;
4229 /* Due to the ordering of points-to set calculation and SMT
4230 calculation being a bit co-dependent, we can't just calculate SMT
4231 used info whenever we want, we have to calculate it around the time
4232 that find_what_p_points_to is called. */
4234 /* Mark which SMT's are in use by points-to anything variables. */
4236 void
4237 set_used_smts (void)
4239 int i;
4240 varinfo_t vi;
4241 used_smts = BITMAP_ALLOC (&pta_obstack);
4243 for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); i++)
4245 tree var = vi->decl;
4246 tree smt;
4247 var_ann_t va;
4248 struct ptr_info_def *pi = NULL;
4250 /* For parm decls, the pointer info may be under the default
4251 def. */
4252 if (TREE_CODE (vi->decl) == PARM_DECL
4253 && gimple_default_def (cfun, var))
4254 pi = SSA_NAME_PTR_INFO (gimple_default_def (cfun, var));
4255 else if (TREE_CODE (var) == SSA_NAME)
4256 pi = SSA_NAME_PTR_INFO (var);
4258 /* Skip the special variables and those without their own
4259 solution set. */
4260 if (vi->is_special_var || find (vi->id) != vi->id
4261 || !SSA_VAR_P (var)
4262 || (pi && !pi->is_dereferenced)
4263 || (TREE_CODE (var) == VAR_DECL && !may_be_aliased (var))
4264 || !POINTER_TYPE_P (TREE_TYPE (var)))
4265 continue;
4267 if (TREE_CODE (var) == SSA_NAME)
4268 var = SSA_NAME_VAR (var);
4270 va = var_ann (var);
4271 if (!va)
4272 continue;
4274 smt = va->symbol_mem_tag;
4275 if (smt && bitmap_bit_p (vi->solution, anything_id))
4276 bitmap_set_bit (used_smts, DECL_UID (smt));
4280 /* Merge the necessary SMT's into the solution set for VI, which is
4281 P's varinfo. This involves merging all SMT's that are a subset of
4282 the SMT necessary for P. */
4284 static void
4285 merge_smts_into (tree p, varinfo_t vi)
4287 unsigned int i;
4288 bitmap_iterator bi;
4289 tree smt;
4290 bitmap aliases;
4291 tree var = p;
4293 if (TREE_CODE (p) == SSA_NAME)
4294 var = SSA_NAME_VAR (p);
4296 smt = var_ann (var)->symbol_mem_tag;
4297 if (smt)
4299 HOST_WIDE_INT smtset = get_alias_set (TREE_TYPE (smt));
4301 /* Need to set the SMT subsets first before this
4302 will work properly. */
4303 bitmap_set_bit (vi->finished_solution, DECL_UID (smt));
4304 EXECUTE_IF_SET_IN_BITMAP (used_smts, 0, i, bi)
4306 tree newsmt = referenced_var (i);
4307 tree newsmttype = TREE_TYPE (newsmt);
4309 if (alias_set_subset_of (get_alias_set (newsmttype),
4310 smtset))
4311 bitmap_set_bit (vi->finished_solution, i);
4314 aliases = MTAG_ALIASES (smt);
4315 if (aliases)
4316 bitmap_ior_into (vi->finished_solution, aliases);
4320 /* Given a pointer variable P, fill in its points-to set, or return
4321 false if we can't.
4322 Rather than return false for variables that point-to anything, we
4323 instead find the corresponding SMT, and merge in it's aliases. In
4324 addition to these aliases, we also set the bits for the SMT's
4325 themselves and their subsets, as SMT's are still in use by
4326 non-SSA_NAME's, and pruning may eliminate every one of their
4327 aliases. In such a case, if we did not include the right set of
4328 SMT's in the points-to set of the variable, we'd end up with
4329 statements that do not conflict but should. */
4331 bool
4332 find_what_p_points_to (tree p)
4334 tree lookup_p = p;
4335 varinfo_t vi;
4337 if (!have_alias_info)
4338 return false;
4340 /* For parameters, get at the points-to set for the actual parm
4341 decl. */
4342 if (TREE_CODE (p) == SSA_NAME
4343 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4344 && SSA_NAME_IS_DEFAULT_DEF (p))
4345 lookup_p = SSA_NAME_VAR (p);
4347 vi = lookup_vi_for_tree (lookup_p);
4348 if (vi)
4350 if (vi->is_artificial_var)
4351 return false;
4353 /* See if this is a field or a structure. */
4354 if (vi->size != vi->fullsize)
4356 /* Nothing currently asks about structure fields directly,
4357 but when they do, we need code here to hand back the
4358 points-to set. */
4359 if (!var_can_have_subvars (vi->decl)
4360 || get_subvars_for_var (vi->decl) == NULL)
4361 return false;
4363 else
4365 struct ptr_info_def *pi = get_ptr_info (p);
4366 unsigned int i;
4367 bitmap_iterator bi;
4368 bool was_pt_anything = false;
4370 if (!pi->is_dereferenced)
4371 return false;
4373 /* This variable may have been collapsed, let's get the real
4374 variable. */
4375 vi = get_varinfo (find (vi->id));
4377 /* Translate artificial variables into SSA_NAME_PTR_INFO
4378 attributes. */
4379 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4381 varinfo_t vi = get_varinfo (i);
4383 if (vi->is_artificial_var)
4385 /* FIXME. READONLY should be handled better so that
4386 flow insensitive aliasing can disregard writable
4387 aliases. */
4388 if (vi->id == nothing_id)
4389 pi->pt_null = 1;
4390 else if (vi->id == anything_id)
4391 was_pt_anything = 1;
4392 else if (vi->id == readonly_id)
4393 was_pt_anything = 1;
4394 else if (vi->id == integer_id)
4395 was_pt_anything = 1;
4396 else if (vi->is_heap_var)
4397 pi->pt_global_mem = 1;
4401 /* Share the final set of variables between the SSA_NAME
4402 pointer infos for collapsed nodes that are collapsed to
4403 non-special variables. This is because special vars have
4404 no real types associated with them, so while we know the
4405 pointers are equivalent to them, we need to generate the
4406 solution separately since it will include SMT's from the
4407 original non-collapsed variable. */
4408 if (!vi->is_special_var && vi->finished_solution)
4410 pi->pt_vars = vi->finished_solution;
4412 else
4414 vi->finished_solution = BITMAP_GGC_ALLOC ();
4415 stats.points_to_sets_created++;
4417 /* Instead of using pt_anything, we instead merge in the SMT
4418 aliases for the underlying SMT. */
4419 if (was_pt_anything)
4421 merge_smts_into (p, vi);
4422 pi->pt_global_mem = 1;
4425 set_uids_in_ptset (vi->decl, vi->finished_solution, vi->solution);
4426 pi->pt_vars = vi->finished_solution;
4429 if (bitmap_empty_p (pi->pt_vars))
4430 pi->pt_vars = NULL;
4432 return true;
4436 return false;
4441 /* Dump points-to information to OUTFILE. */
4443 void
4444 dump_sa_points_to_info (FILE *outfile)
4446 unsigned int i;
4448 fprintf (outfile, "\nPoints-to sets\n\n");
4450 if (dump_flags & TDF_STATS)
4452 fprintf (outfile, "Stats:\n");
4453 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4454 fprintf (outfile, "Non-pointer vars: %d\n",
4455 stats.nonpointer_vars);
4456 fprintf (outfile, "Statically unified vars: %d\n",
4457 stats.unified_vars_static);
4458 fprintf (outfile, "Dynamically unified vars: %d\n",
4459 stats.unified_vars_dynamic);
4460 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4461 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4462 fprintf (outfile, "Number of implicit edges: %d\n",
4463 stats.num_implicit_edges);
4466 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4467 dump_solution_for_var (outfile, i);
4471 /* Debug points-to information to stderr. */
4473 void
4474 debug_sa_points_to_info (void)
4476 dump_sa_points_to_info (stderr);
4480 /* Initialize the always-existing constraint variables for NULL
4481 ANYTHING, READONLY, and INTEGER */
4483 static void
4484 init_base_vars (void)
4486 struct constraint_expr lhs, rhs;
4488 /* Create the NULL variable, used to represent that a variable points
4489 to NULL. */
4490 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4491 var_nothing = new_var_info (nothing_tree, 0, "NULL");
4492 insert_vi_for_tree (nothing_tree, var_nothing);
4493 var_nothing->is_artificial_var = 1;
4494 var_nothing->offset = 0;
4495 var_nothing->size = ~0;
4496 var_nothing->fullsize = ~0;
4497 var_nothing->is_special_var = 1;
4498 nothing_id = 0;
4499 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4501 /* Create the ANYTHING variable, used to represent that a variable
4502 points to some unknown piece of memory. */
4503 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4504 var_anything = new_var_info (anything_tree, 1, "ANYTHING");
4505 insert_vi_for_tree (anything_tree, var_anything);
4506 var_anything->is_artificial_var = 1;
4507 var_anything->size = ~0;
4508 var_anything->offset = 0;
4509 var_anything->next = NULL;
4510 var_anything->fullsize = ~0;
4511 var_anything->is_special_var = 1;
4512 anything_id = 1;
4514 /* Anything points to anything. This makes deref constraints just
4515 work in the presence of linked list and other p = *p type loops,
4516 by saying that *ANYTHING = ANYTHING. */
4517 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4518 lhs.type = SCALAR;
4519 lhs.var = anything_id;
4520 lhs.offset = 0;
4521 rhs.type = ADDRESSOF;
4522 rhs.var = anything_id;
4523 rhs.offset = 0;
4525 /* This specifically does not use process_constraint because
4526 process_constraint ignores all anything = anything constraints, since all
4527 but this one are redundant. */
4528 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4530 /* Create the READONLY variable, used to represent that a variable
4531 points to readonly memory. */
4532 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4533 var_readonly = new_var_info (readonly_tree, 2, "READONLY");
4534 var_readonly->is_artificial_var = 1;
4535 var_readonly->offset = 0;
4536 var_readonly->size = ~0;
4537 var_readonly->fullsize = ~0;
4538 var_readonly->next = NULL;
4539 var_readonly->is_special_var = 1;
4540 insert_vi_for_tree (readonly_tree, var_readonly);
4541 readonly_id = 2;
4542 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4544 /* readonly memory points to anything, in order to make deref
4545 easier. In reality, it points to anything the particular
4546 readonly variable can point to, but we don't track this
4547 separately. */
4548 lhs.type = SCALAR;
4549 lhs.var = readonly_id;
4550 lhs.offset = 0;
4551 rhs.type = ADDRESSOF;
4552 rhs.var = anything_id;
4553 rhs.offset = 0;
4555 process_constraint (new_constraint (lhs, rhs));
4557 /* Create the INTEGER variable, used to represent that a variable points
4558 to an INTEGER. */
4559 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4560 var_integer = new_var_info (integer_tree, 3, "INTEGER");
4561 insert_vi_for_tree (integer_tree, var_integer);
4562 var_integer->is_artificial_var = 1;
4563 var_integer->size = ~0;
4564 var_integer->fullsize = ~0;
4565 var_integer->offset = 0;
4566 var_integer->next = NULL;
4567 var_integer->is_special_var = 1;
4568 integer_id = 3;
4569 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4571 /* INTEGER = ANYTHING, because we don't know where a dereference of
4572 a random integer will point to. */
4573 lhs.type = SCALAR;
4574 lhs.var = integer_id;
4575 lhs.offset = 0;
4576 rhs.type = ADDRESSOF;
4577 rhs.var = anything_id;
4578 rhs.offset = 0;
4579 process_constraint (new_constraint (lhs, rhs));
4582 /* Initialize things necessary to perform PTA */
4584 static void
4585 init_alias_vars (void)
4587 bitmap_obstack_initialize (&pta_obstack);
4588 bitmap_obstack_initialize (&oldpta_obstack);
4589 bitmap_obstack_initialize (&predbitmap_obstack);
4591 constraint_pool = create_alloc_pool ("Constraint pool",
4592 sizeof (struct constraint), 30);
4593 variable_info_pool = create_alloc_pool ("Variable info pool",
4594 sizeof (struct variable_info), 30);
4595 constraints = VEC_alloc (constraint_t, heap, 8);
4596 varmap = VEC_alloc (varinfo_t, heap, 8);
4597 vi_for_tree = pointer_map_create ();
4599 memset (&stats, 0, sizeof (stats));
4601 init_base_vars ();
4604 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
4605 predecessor edges. */
4607 static void
4608 remove_preds_and_fake_succs (constraint_graph_t graph)
4610 unsigned int i;
4612 /* Clear the implicit ref and address nodes from the successor
4613 lists. */
4614 for (i = 0; i < FIRST_REF_NODE; i++)
4616 if (graph->succs[i])
4617 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
4618 FIRST_REF_NODE * 2);
4621 /* Free the successor list for the non-ref nodes. */
4622 for (i = FIRST_REF_NODE; i < graph->size; i++)
4624 if (graph->succs[i])
4625 BITMAP_FREE (graph->succs[i]);
4628 /* Now reallocate the size of the successor list as, and blow away
4629 the predecessor bitmaps. */
4630 graph->size = VEC_length (varinfo_t, varmap);
4631 graph->succs = xrealloc (graph->succs, graph->size * sizeof (bitmap));
4633 free (graph->implicit_preds);
4634 graph->implicit_preds = NULL;
4635 free (graph->preds);
4636 graph->preds = NULL;
4637 bitmap_obstack_release (&predbitmap_obstack);
4640 /* Create points-to sets for the current function. See the comments
4641 at the start of the file for an algorithmic overview. */
4643 void
4644 compute_points_to_sets (struct alias_info *ai)
4646 struct scc_info *si;
4647 basic_block bb;
4649 timevar_push (TV_TREE_PTA);
4651 init_alias_vars ();
4652 init_alias_heapvars ();
4654 intra_create_variable_infos ();
4656 /* Now walk all statements and derive aliases. */
4657 FOR_EACH_BB (bb)
4659 block_stmt_iterator bsi;
4660 tree phi;
4662 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4664 if (is_gimple_reg (PHI_RESULT (phi)))
4666 find_func_aliases (phi);
4668 /* Update various related attributes like escaped
4669 addresses, pointer dereferences for loads and stores.
4670 This is used when creating name tags and alias
4671 sets. */
4672 update_alias_info (phi, ai);
4676 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4678 tree stmt = bsi_stmt (bsi);
4680 find_func_aliases (stmt);
4682 /* Update various related attributes like escaped
4683 addresses, pointer dereferences for loads and stores.
4684 This is used when creating name tags and alias
4685 sets. */
4686 update_alias_info (stmt, ai);
4691 if (dump_file)
4693 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4694 dump_constraints (dump_file);
4697 if (dump_file)
4698 fprintf (dump_file,
4699 "\nCollapsing static cycles and doing variable "
4700 "substitution:\n");
4701 build_pred_graph ();
4702 si = perform_var_substitution (graph);
4703 move_complex_constraints (graph, si);
4704 free_var_substitution_info (si);
4706 build_succ_graph ();
4707 find_indirect_cycles (graph);
4709 /* Implicit nodes and predecessors are no longer necessary at this
4710 point. */
4711 remove_preds_and_fake_succs (graph);
4713 if (dump_file)
4714 fprintf (dump_file, "\nSolving graph:\n");
4716 solve_graph (graph);
4718 if (dump_file)
4719 dump_sa_points_to_info (dump_file);
4721 have_alias_info = true;
4723 timevar_pop (TV_TREE_PTA);
4727 /* Delete created points-to sets. */
4729 void
4730 delete_points_to_sets (void)
4732 varinfo_t v;
4733 int i;
4735 if (dump_file && (dump_flags & TDF_STATS))
4736 fprintf (dump_file, "Points to sets created:%d\n",
4737 stats.points_to_sets_created);
4739 pointer_map_destroy (vi_for_tree);
4740 bitmap_obstack_release (&pta_obstack);
4741 VEC_free (constraint_t, heap, constraints);
4743 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4744 VEC_free (constraint_t, heap, graph->complex[i]);
4746 free (graph->rep);
4747 free (graph->succs);
4748 free (graph->indirect_cycles);
4749 free (graph);
4751 VEC_free (varinfo_t, heap, varmap);
4752 free_alloc_pool (variable_info_pool);
4753 free_alloc_pool (constraint_pool);
4754 have_alias_info = false;
4757 /* Return true if we should execute IPA PTA. */
4758 static bool
4759 gate_ipa_pta (void)
4761 return (flag_unit_at_a_time != 0
4762 && flag_ipa_pta
4763 /* Don't bother doing anything if the program has errors. */
4764 && !(errorcount || sorrycount));
4767 /* Execute the driver for IPA PTA. */
4768 static unsigned int
4769 ipa_pta_execute (void)
4771 struct cgraph_node *node;
4772 struct scc_info *si;
4774 in_ipa_mode = 1;
4775 init_alias_heapvars ();
4776 init_alias_vars ();
4778 for (node = cgraph_nodes; node; node = node->next)
4780 if (!node->analyzed || cgraph_is_master_clone (node))
4782 unsigned int varid;
4784 varid = create_function_info_for (node->decl,
4785 cgraph_node_name (node));
4786 if (node->local.externally_visible)
4788 varinfo_t fi = get_varinfo (varid);
4789 for (; fi; fi = fi->next)
4790 make_constraint_from_anything (fi);
4794 for (node = cgraph_nodes; node; node = node->next)
4796 if (node->analyzed && cgraph_is_master_clone (node))
4798 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
4799 basic_block bb;
4800 tree old_func_decl = current_function_decl;
4801 if (dump_file)
4802 fprintf (dump_file,
4803 "Generating constraints for %s\n",
4804 cgraph_node_name (node));
4805 push_cfun (cfun);
4806 current_function_decl = node->decl;
4808 FOR_EACH_BB_FN (bb, cfun)
4810 block_stmt_iterator bsi;
4811 tree phi;
4813 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4815 if (is_gimple_reg (PHI_RESULT (phi)))
4817 find_func_aliases (phi);
4821 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4823 tree stmt = bsi_stmt (bsi);
4824 find_func_aliases (stmt);
4827 current_function_decl = old_func_decl;
4828 pop_cfun ();
4830 else
4832 /* Make point to anything. */
4838 if (dump_file)
4840 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4841 dump_constraints (dump_file);
4844 if (dump_file)
4845 fprintf (dump_file,
4846 "\nCollapsing static cycles and doing variable "
4847 "substitution:\n");
4849 build_pred_graph ();
4850 si = perform_var_substitution (graph);
4851 move_complex_constraints (graph, si);
4852 free_var_substitution_info (si);
4854 build_succ_graph ();
4855 find_indirect_cycles (graph);
4857 /* Implicit nodes and predecessors are no longer necessary at this
4858 point. */
4859 remove_preds_and_fake_succs (graph);
4861 if (dump_file)
4862 fprintf (dump_file, "\nSolving graph:\n");
4864 solve_graph (graph);
4866 if (dump_file)
4867 dump_sa_points_to_info (dump_file);
4869 in_ipa_mode = 0;
4870 delete_alias_heapvars ();
4871 delete_points_to_sets ();
4872 return 0;
4875 struct tree_opt_pass pass_ipa_pta =
4877 "pta", /* name */
4878 gate_ipa_pta, /* gate */
4879 ipa_pta_execute, /* execute */
4880 NULL, /* sub */
4881 NULL, /* next */
4882 0, /* static_pass_number */
4883 TV_IPA_PTA, /* tv_id */
4884 0, /* properties_required */
4885 0, /* properties_provided */
4886 0, /* properties_destroyed */
4887 0, /* todo_flags_start */
4888 0, /* todo_flags_finish */
4889 0 /* letter */
4892 /* Initialize the heapvar for statement mapping. */
4893 void
4894 init_alias_heapvars (void)
4896 if (!heapvar_for_stmt)
4897 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
4898 NULL);
4901 void
4902 delete_alias_heapvars (void)
4904 htab_delete (heapvar_for_stmt);
4905 heapvar_for_stmt = NULL;
4909 #include "gt-tree-ssa-structalias.h"