* tree-cfg.c (tree_find_edge_insert_loc): Handle naked RETURN_EXPR.
[official-gcc.git] / gcc / tree-ssa-structalias.c
blob1e1d64d7b9e9b1e2980d9a2fdcea11b22b0c9ceb
1 /* Tree based points-to analysis
2 Copyright (C) 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
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 "tree-ssa-structalias.h"
53 /* The idea behind this analyzer is to generate set constraints from the
54 program, then solve the resulting constraints in order to generate the
55 points-to sets.
57 Set constraints are a way of modeling program analysis problems that
58 involve sets. They consist of an inclusion constraint language,
59 describing the variables (each variable is a set) and operations that
60 are involved on the variables, and a set of rules that derive facts
61 from these operations. To solve a system of set constraints, you derive
62 all possible facts under the rules, which gives you the correct sets
63 as a consequence.
65 See "Efficient Field-sensitive pointer analysis for C" by "David
66 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
67 http://citeseer.ist.psu.edu/pearce04efficient.html
69 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
70 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
71 http://citeseer.ist.psu.edu/heintze01ultrafast.html
73 There are three types of constraint expressions, DEREF, ADDRESSOF, and
74 SCALAR. Each constraint expression consists of a constraint type,
75 a variable, and an offset.
77 SCALAR is a constraint expression type used to represent x, whether
78 it appears on the LHS or the RHS of a statement.
79 DEREF is a constraint expression type used to represent *x, whether
80 it appears on the LHS or the RHS of a statement.
81 ADDRESSOF is a constraint expression used to represent &x, whether
82 it appears on the LHS or the RHS of a statement.
84 Each pointer variable in the program is assigned an integer id, and
85 each field of a structure variable is assigned an integer id as well.
87 Structure variables are linked to their list of fields through a "next
88 field" in each variable that points to the next field in offset
89 order.
90 Each variable for a structure field has
92 1. "size", that tells the size in bits of that field.
93 2. "fullsize, that tells the size in bits of the entire structure.
94 3. "offset", that tells the offset in bits from the beginning of the
95 structure to this field.
97 Thus,
98 struct f
100 int a;
101 int b;
102 } foo;
103 int *bar;
105 looks like
107 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
108 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
109 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112 In order to solve the system of set constraints, the following is
113 done:
115 1. Each constraint variable x has a solution set associated with it,
116 Sol(x).
118 2. Constraints are separated into direct, copy, and complex.
119 Direct constraints are ADDRESSOF constraints that require no extra
120 processing, such as P = &Q
121 Copy constraints are those of the form P = Q.
122 Complex constraints are all the constraints involving dereferences.
124 3. All direct constraints of the form P = &Q are processed, such
125 that Q is added to Sol(P)
127 4. All complex constraints for a given constraint variable are stored in a
128 linked list attached to that variable's node.
130 5. A directed graph is built out of the copy constraints. Each
131 constraint variable is a node in the graph, and an edge from
132 Q to P is added for each copy constraint of the form P = Q
134 6. The graph is then walked, and solution sets are
135 propagated along the copy edges, such that an edge from Q to P
136 causes Sol(P) <- Sol(P) union Sol(Q).
138 7. As we visit each node, all complex constraints associated with
139 that node are processed by adding appropriate copy edges to the graph, or the
140 appropriate variables to the solution set.
142 8. The process of walking the graph is iterated until no solution
143 sets change.
145 Prior to walking the graph in steps 6 and 7, We perform static
146 cycle elimination on the constraint graph, as well
147 as off-line variable substitution.
149 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
150 on and turned into anything), but isn't. You can just see what offset
151 inside the pointed-to struct it's going to access.
153 TODO: Constant bounded arrays can be handled as if they were structs of the
154 same number of elements.
156 TODO: Modeling heap and incoming pointers becomes much better if we
157 add fields to them as we discover them, which we could do.
159 TODO: We could handle unions, but to be honest, it's probably not
160 worth the pain or slowdown. */
162 static bool use_field_sensitive = true;
163 static unsigned int create_variable_info_for (tree, const char *);
164 static struct constraint_expr get_constraint_for (tree, bool *);
165 static void build_constraint_graph (void);
167 static bitmap_obstack ptabitmap_obstack;
168 static bitmap_obstack iteration_obstack;
169 DEF_VEC_P(constraint_t);
170 DEF_VEC_ALLOC_P(constraint_t,heap);
172 static struct constraint_stats
174 unsigned int total_vars;
175 unsigned int collapsed_vars;
176 unsigned int unified_vars_static;
177 unsigned int unified_vars_dynamic;
178 unsigned int iterations;
179 } stats;
181 struct variable_info
183 /* ID of this variable */
184 unsigned int id;
186 /* Name of this variable */
187 const char *name;
189 /* Tree that this variable is associated with. */
190 tree decl;
192 /* Offset of this variable, in bits, from the base variable */
193 unsigned HOST_WIDE_INT offset;
195 /* Size of the variable, in bits. */
196 unsigned HOST_WIDE_INT size;
198 /* Full size of the base variable, in bits. */
199 unsigned HOST_WIDE_INT fullsize;
201 /* A link to the variable for the next field in this structure. */
202 struct variable_info *next;
204 /* Node in the graph that represents the constraints and points-to
205 solution for the variable. */
206 unsigned int node;
208 /* True if the address of this variable is taken. Needed for
209 variable substitution. */
210 unsigned int address_taken:1;
212 /* True if this variable is the target of a dereference. Needed for
213 variable substitution. */
214 unsigned int indirect_target:1;
216 /* True if this is a variable created by the constraint analysis, such as
217 heap variables and constraints we had to break up. */
218 unsigned int is_artificial_var:1;
220 /* True if this is a special variable whose solution set should not be
221 changed. */
222 unsigned int is_special_var:1;
224 /* True for variables whose size is not known or variable. */
225 unsigned int is_unknown_size_var:1;
227 /* True for variables that have unions somewhere in them. */
228 unsigned int has_union:1;
230 /* True if this is a heap variable. */
231 unsigned int is_heap_var:1;
233 /* Points-to set for this variable. */
234 bitmap solution;
236 /* Variable ids represented by this node. */
237 bitmap variables;
239 /* Vector of complex constraints for this node. Complex
240 constraints are those involving dereferences. */
241 VEC(constraint_t,heap) *complex;
243 typedef struct variable_info *varinfo_t;
245 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
247 /* Pool of variable info structures. */
248 static alloc_pool variable_info_pool;
250 DEF_VEC_P(varinfo_t);
252 DEF_VEC_ALLOC_P(varinfo_t, heap);
254 /* Table of variable info structures for constraint variables. Indexed directly
255 by variable info id. */
256 static VEC(varinfo_t,heap) *varmap;
258 /* Return the varmap element N */
260 static inline varinfo_t
261 get_varinfo(unsigned int n)
263 return VEC_index(varinfo_t, varmap, n);
266 /* Variable that represents the unknown pointer. */
267 static varinfo_t var_anything;
268 static tree anything_tree;
269 static unsigned int anything_id;
271 /* Variable that represents the NULL pointer. */
272 static varinfo_t var_nothing;
273 static tree nothing_tree;
274 static unsigned int nothing_id;
276 /* Variable that represents read only memory. */
277 static varinfo_t var_readonly;
278 static tree readonly_tree;
279 static unsigned int readonly_id;
281 /* Variable that represents integers. This is used for when people do things
282 like &0->a.b. */
283 static varinfo_t var_integer;
284 static tree integer_tree;
285 static unsigned int integer_id;
287 /* Variable that represents arbitrary offsets into an object. Used to
288 represent pointer arithmetic, which may not legally escape the
289 bounds of an object. */
290 static varinfo_t var_anyoffset;
291 static tree anyoffset_tree;
292 static unsigned int anyoffset_id;
294 /* Return a new variable info structure consisting for a variable
295 named NAME, and using constraint graph node NODE. */
297 static varinfo_t
298 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
300 varinfo_t ret = pool_alloc (variable_info_pool);
302 ret->id = id;
303 ret->name = name;
304 ret->decl = t;
305 ret->node = node;
306 ret->address_taken = false;
307 ret->indirect_target = false;
308 ret->is_artificial_var = false;
309 ret->is_heap_var = false;
310 ret->is_special_var = false;
311 ret->is_unknown_size_var = false;
312 ret->has_union = false;
313 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
314 bitmap_clear (ret->solution);
315 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
316 bitmap_clear (ret->variables);
317 ret->complex = NULL;
318 ret->next = NULL;
319 return ret;
322 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
324 /* An expression that appears in a constraint. */
326 struct constraint_expr
328 /* Constraint type. */
329 constraint_expr_type type;
331 /* Variable we are referring to in the constraint. */
332 unsigned int var;
334 /* Offset, in bits, of this constraint from the beginning of
335 variables it ends up referring to.
337 IOW, in a deref constraint, we would deref, get the result set,
338 then add OFFSET to each member. */
339 unsigned HOST_WIDE_INT offset;
342 static struct constraint_expr do_deref (struct constraint_expr);
344 /* Our set constraints are made up of two constraint expressions, one
345 LHS, and one RHS.
347 As described in the introduction, our set constraints each represent an
348 operation between set valued variables.
350 struct constraint
352 struct constraint_expr lhs;
353 struct constraint_expr rhs;
356 /* List of constraints that we use to build the constraint graph from. */
358 static VEC(constraint_t,heap) *constraints;
359 static alloc_pool constraint_pool;
361 /* An edge in the constraint graph. We technically have no use for
362 the src, since it will always be the same node that we are indexing
363 into the pred/succ arrays with, but it's nice for checking
364 purposes. The edges are weighted, with a bit set in weights for
365 each edge from src to dest with that weight. */
367 struct constraint_edge
369 unsigned int src;
370 unsigned int dest;
371 bitmap weights;
374 typedef struct constraint_edge *constraint_edge_t;
375 static alloc_pool constraint_edge_pool;
377 /* Return a new constraint edge from SRC to DEST. */
379 static constraint_edge_t
380 new_constraint_edge (unsigned int src, unsigned int dest)
382 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
383 ret->src = src;
384 ret->dest = dest;
385 ret->weights = NULL;
386 return ret;
389 DEF_VEC_P(constraint_edge_t);
390 DEF_VEC_ALLOC_P(constraint_edge_t,heap);
393 /* The constraint graph is simply a set of adjacency vectors, one per
394 variable. succs[x] is the vector of successors for variable x, and preds[x]
395 is the vector of predecessors for variable x.
396 IOW, all edges are "forward" edges, which is not like our CFG.
397 So remember that
398 preds[x]->src == x, and
399 succs[x]->src == x. */
401 struct constraint_graph
403 VEC(constraint_edge_t,heap) **succs;
404 VEC(constraint_edge_t,heap) **preds;
407 typedef struct constraint_graph *constraint_graph_t;
409 static constraint_graph_t graph;
411 /* Create a new constraint consisting of LHS and RHS expressions. */
413 static constraint_t
414 new_constraint (const struct constraint_expr lhs,
415 const struct constraint_expr rhs)
417 constraint_t ret = pool_alloc (constraint_pool);
418 ret->lhs = lhs;
419 ret->rhs = rhs;
420 return ret;
423 /* Print out constraint C to FILE. */
425 void
426 dump_constraint (FILE *file, constraint_t c)
428 if (c->lhs.type == ADDRESSOF)
429 fprintf (file, "&");
430 else if (c->lhs.type == DEREF)
431 fprintf (file, "*");
432 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
433 if (c->lhs.offset != 0)
434 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
435 fprintf (file, " = ");
436 if (c->rhs.type == ADDRESSOF)
437 fprintf (file, "&");
438 else if (c->rhs.type == DEREF)
439 fprintf (file, "*");
440 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
441 if (c->rhs.offset != 0)
442 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
443 fprintf (file, "\n");
446 /* Print out constraint C to stderr. */
448 void
449 debug_constraint (constraint_t c)
451 dump_constraint (stderr, c);
454 /* Print out all constraints to FILE */
456 void
457 dump_constraints (FILE *file)
459 int i;
460 constraint_t c;
461 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
462 dump_constraint (file, c);
465 /* Print out all constraints to stderr. */
467 void
468 debug_constraints (void)
470 dump_constraints (stderr);
473 /* SOLVER FUNCTIONS
475 The solver is a simple worklist solver, that works on the following
476 algorithm:
478 sbitmap changed_nodes = all ones;
479 changed_count = number of nodes;
480 For each node that was already collapsed:
481 changed_count--;
484 while (changed_count > 0)
486 compute topological ordering for constraint graph
488 find and collapse cycles in the constraint graph (updating
489 changed if necessary)
491 for each node (n) in the graph in topological order:
492 changed_count--;
494 Process each complex constraint associated with the node,
495 updating changed if necessary.
497 For each outgoing edge from n, propagate the solution from n to
498 the destination of the edge, updating changed as necessary.
500 } */
502 /* Return true if two constraint expressions A and B are equal. */
504 static bool
505 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
507 return a.type == b.type
508 && a.var == b.var
509 && a.offset == b.offset;
512 /* Return true if constraint expression A is less than constraint expression
513 B. This is just arbitrary, but consistent, in order to give them an
514 ordering. */
516 static bool
517 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
519 if (a.type == b.type)
521 if (a.var == b.var)
522 return a.offset < b.offset;
523 else
524 return a.var < b.var;
526 else
527 return a.type < b.type;
530 /* Return true if constraint A is less than constraint B. This is just
531 arbitrary, but consistent, in order to give them an ordering. */
533 static bool
534 constraint_less (const constraint_t a, const constraint_t b)
536 if (constraint_expr_less (a->lhs, b->lhs))
537 return true;
538 else if (constraint_expr_less (b->lhs, a->lhs))
539 return false;
540 else
541 return constraint_expr_less (a->rhs, b->rhs);
544 /* Return true if two constraints A and B are equal. */
546 static bool
547 constraint_equal (struct constraint a, struct constraint b)
549 return constraint_expr_equal (a.lhs, b.lhs)
550 && constraint_expr_equal (a.rhs, b.rhs);
554 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
556 static constraint_t
557 constraint_vec_find (VEC(constraint_t,heap) *vec,
558 struct constraint lookfor)
560 unsigned int place;
561 constraint_t found;
563 if (vec == NULL)
564 return NULL;
566 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
567 if (place >= VEC_length (constraint_t, vec))
568 return NULL;
569 found = VEC_index (constraint_t, vec, place);
570 if (!constraint_equal (*found, lookfor))
571 return NULL;
572 return found;
575 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
577 static void
578 constraint_set_union (VEC(constraint_t,heap) **to,
579 VEC(constraint_t,heap) **from)
581 int i;
582 constraint_t c;
584 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
586 if (constraint_vec_find (*to, *c) == NULL)
588 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
589 constraint_less);
590 VEC_safe_insert (constraint_t, heap, *to, place, c);
595 /* Take a solution set SET, add OFFSET to each member of the set, and
596 overwrite SET with the result when done. */
598 static void
599 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
601 bitmap result = BITMAP_ALLOC (&iteration_obstack);
602 unsigned int i;
603 bitmap_iterator bi;
605 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
607 /* If this is a properly sized variable, only add offset if it's
608 less than end. Otherwise, it is globbed to a single
609 variable. */
611 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
613 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
614 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
615 if (!v)
616 continue;
617 bitmap_set_bit (result, v->id);
619 else if (get_varinfo (i)->is_artificial_var
620 || get_varinfo (i)->has_union
621 || get_varinfo (i)->is_unknown_size_var)
623 bitmap_set_bit (result, i);
627 bitmap_copy (set, result);
628 BITMAP_FREE (result);
631 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
632 process. */
634 static bool
635 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
637 if (inc == 0)
638 return bitmap_ior_into (to, from);
639 else
641 bitmap tmp;
642 bool res;
644 tmp = BITMAP_ALLOC (&iteration_obstack);
645 bitmap_copy (tmp, from);
646 solution_set_add (tmp, inc);
647 res = bitmap_ior_into (to, tmp);
648 BITMAP_FREE (tmp);
649 return res;
653 /* Insert constraint C into the list of complex constraints for VAR. */
655 static void
656 insert_into_complex (unsigned int var, constraint_t c)
658 varinfo_t vi = get_varinfo (var);
659 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
660 constraint_less);
661 VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
665 /* Compare two constraint edges A and B, return true if they are equal. */
667 static bool
668 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
670 return a.src == b.src && a.dest == b.dest;
673 /* Compare two constraint edges, return true if A is less than B */
675 static bool
676 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
678 if (a->dest < b->dest)
679 return true;
680 else if (a->dest == b->dest)
681 return a->src < b->src;
682 else
683 return false;
686 /* Find the constraint edge that matches LOOKFOR, in VEC.
687 Return the edge, if found, NULL otherwise. */
689 static constraint_edge_t
690 constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
691 struct constraint_edge lookfor)
693 unsigned int place;
694 constraint_edge_t edge;
696 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
697 constraint_edge_less);
698 edge = VEC_index (constraint_edge_t, vec, place);
699 if (!constraint_edge_equal (*edge, lookfor))
700 return NULL;
701 return edge;
704 /* Condense two variable nodes into a single variable node, by moving
705 all associated info from SRC to TO. */
707 static void
708 condense_varmap_nodes (unsigned int to, unsigned int src)
710 varinfo_t tovi = get_varinfo (to);
711 varinfo_t srcvi = get_varinfo (src);
712 unsigned int i;
713 constraint_t c;
714 bitmap_iterator bi;
716 /* the src node, and all its variables, are now the to node. */
717 srcvi->node = to;
718 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
719 get_varinfo (i)->node = to;
721 /* Merge the src node variables and the to node variables. */
722 bitmap_set_bit (tovi->variables, src);
723 bitmap_ior_into (tovi->variables, srcvi->variables);
724 bitmap_clear (srcvi->variables);
726 /* Move all complex constraints from src node into to node */
727 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
729 /* In complex constraints for node src, we may have either
730 a = *src, and *src = a. */
732 if (c->rhs.type == DEREF)
733 c->rhs.var = to;
734 else
735 c->lhs.var = to;
737 constraint_set_union (&tovi->complex, &srcvi->complex);
738 VEC_free (constraint_t, heap, srcvi->complex);
739 srcvi->complex = NULL;
742 /* Erase EDGE from GRAPH. This routine only handles self-edges
743 (e.g. an edge from a to a). */
745 static void
746 erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
748 VEC(constraint_edge_t,heap) *predvec = graph->preds[edge.src];
749 VEC(constraint_edge_t,heap) *succvec = graph->succs[edge.dest];
750 unsigned int place;
751 gcc_assert (edge.src == edge.dest);
753 /* Remove from the successors. */
754 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
755 constraint_edge_less);
757 /* Make sure we found the edge. */
758 #ifdef ENABLE_CHECKING
760 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
761 gcc_assert (constraint_edge_equal (*tmp, edge));
763 #endif
764 VEC_ordered_remove (constraint_edge_t, succvec, place);
766 /* Remove from the predecessors. */
767 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
768 constraint_edge_less);
770 /* Make sure we found the edge. */
771 #ifdef ENABLE_CHECKING
773 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
774 gcc_assert (constraint_edge_equal (*tmp, edge));
776 #endif
777 VEC_ordered_remove (constraint_edge_t, predvec, place);
780 /* Remove edges involving NODE from GRAPH. */
782 static void
783 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
785 VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
786 VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
787 constraint_edge_t c;
788 int i;
790 /* Walk the successors, erase the associated preds. */
791 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
792 if (c->dest != node)
794 unsigned int place;
795 struct constraint_edge lookfor;
796 lookfor.src = c->dest;
797 lookfor.dest = node;
798 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
799 &lookfor, constraint_edge_less);
800 VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place);
802 /* Walk the preds, erase the associated succs. */
803 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
804 if (c->dest != node)
806 unsigned int place;
807 struct constraint_edge lookfor;
808 lookfor.src = c->dest;
809 lookfor.dest = node;
810 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
811 &lookfor, constraint_edge_less);
812 VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
815 VEC_free (constraint_edge_t, heap, graph->preds[node]);
816 VEC_free (constraint_edge_t, heap, graph->succs[node]);
817 graph->preds[node] = NULL;
818 graph->succs[node] = NULL;
821 static bool edge_added = false;
823 /* Add edge NEWE to the graph. */
825 static bool
826 add_graph_edge (constraint_graph_t graph, struct constraint_edge newe)
828 unsigned int place;
829 unsigned int src = newe.src;
830 unsigned int dest = newe.dest;
831 VEC(constraint_edge_t,heap) *vec;
833 vec = graph->preds[src];
834 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
835 constraint_edge_less);
836 if (place == VEC_length (constraint_edge_t, vec)
837 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
839 constraint_edge_t edge = new_constraint_edge (src, dest);
840 bitmap weightbitmap;
842 weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
843 edge->weights = weightbitmap;
844 VEC_safe_insert (constraint_edge_t, heap, graph->preds[edge->src],
845 place, edge);
846 edge = new_constraint_edge (dest, src);
847 edge->weights = weightbitmap;
848 place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
849 edge, constraint_edge_less);
850 VEC_safe_insert (constraint_edge_t, heap, graph->succs[edge->src],
851 place, edge);
852 edge_added = true;
853 return true;
855 else
856 return false;
860 /* Return the bitmap representing the weights of edge LOOKFOR */
862 static bitmap
863 get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor)
865 constraint_edge_t edge;
866 unsigned int src = lookfor.src;
867 VEC(constraint_edge_t,heap) *vec;
868 vec = graph->preds[src];
869 edge = constraint_edge_vec_find (vec, lookfor);
870 gcc_assert (edge != NULL);
871 return edge->weights;
875 /* Merge GRAPH nodes FROM and TO into node TO. */
877 static void
878 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
879 unsigned int from)
881 VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
882 VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
883 int i;
884 constraint_edge_t c;
886 /* Merge all the predecessor edges. */
888 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
890 unsigned int d = c->dest;
891 struct constraint_edge olde;
892 struct constraint_edge newe;
893 bitmap temp;
894 bitmap weights;
895 if (c->dest == from)
896 d = to;
897 newe.src = to;
898 newe.dest = d;
899 add_graph_edge (graph, newe);
900 olde.src = from;
901 olde.dest = c->dest;
902 olde.weights = NULL;
903 temp = get_graph_weights (graph, olde);
904 weights = get_graph_weights (graph, newe);
905 bitmap_ior_into (weights, temp);
908 /* Merge all the successor edges. */
909 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
911 unsigned int d = c->dest;
912 struct constraint_edge olde;
913 struct constraint_edge newe;
914 bitmap temp;
915 bitmap weights;
916 if (c->dest == from)
917 d = to;
918 newe.src = d;
919 newe.dest = to;
920 add_graph_edge (graph, newe);
921 olde.src = c->dest;
922 olde.dest = from;
923 olde.weights = NULL;
924 temp = get_graph_weights (graph, olde);
925 weights = get_graph_weights (graph, newe);
926 bitmap_ior_into (weights, temp);
928 clear_edges_for_node (graph, from);
931 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
932 it doesn't exist in the graph already.
933 Return false if the edge already existed, true otherwise. */
935 static bool
936 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
937 unsigned int from, unsigned HOST_WIDE_INT weight)
939 if (to == from && weight == 0)
941 return false;
943 else
945 bool r;
946 struct constraint_edge edge;
947 edge.src = to;
948 edge.dest = from;
949 edge.weights = NULL;
950 r = add_graph_edge (graph, edge);
951 r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight);
952 bitmap_set_bit (get_graph_weights (graph, edge), weight);
953 return r;
958 /* Return true if LOOKFOR is an existing graph edge. */
960 static bool
961 valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor)
963 return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL;
967 /* Build the constraint graph. */
969 static void
970 build_constraint_graph (void)
972 int i = 0;
973 constraint_t c;
975 graph = xmalloc (sizeof (struct constraint_graph));
976 graph->succs = xcalloc (VEC_length (varinfo_t, varmap),
977 sizeof (*graph->succs));
978 graph->preds = xcalloc (VEC_length (varinfo_t, varmap),
979 sizeof (*graph->preds));
981 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
983 struct constraint_expr lhs = c->lhs;
984 struct constraint_expr rhs = c->rhs;
985 if (lhs.type == DEREF)
987 /* *x = y or *x = &y (complex) */
988 if (rhs.type == ADDRESSOF || rhs.var > anything_id)
989 insert_into_complex (lhs.var, c);
991 else if (rhs.type == DEREF)
993 /* !special var= *y */
994 if (!(get_varinfo (lhs.var)->is_special_var))
995 insert_into_complex (rhs.var, c);
997 else if (rhs.type == ADDRESSOF)
999 /* x = &y */
1000 bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var);
1002 else if (lhs.var > anything_id)
1004 /* Ignore 0 weighted self edges, as they can't possibly contribute
1005 anything */
1006 if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0)
1009 struct constraint_edge edge;
1010 edge.src = lhs.var;
1011 edge.dest = rhs.var;
1012 /* x = y (simple) */
1013 add_graph_edge (graph, edge);
1014 bitmap_set_bit (get_graph_weights (graph, edge),
1015 rhs.offset);
1023 /* Changed variables on the last iteration. */
1024 static unsigned int changed_count;
1025 static sbitmap changed;
1027 DEF_VEC_I(unsigned);
1028 DEF_VEC_ALLOC_I(unsigned,heap);
1031 /* Strongly Connected Component visitation info. */
1033 struct scc_info
1035 sbitmap visited;
1036 sbitmap in_component;
1037 int current_index;
1038 unsigned int *visited_index;
1039 VEC(unsigned,heap) *scc_stack;
1040 VEC(unsigned,heap) *unification_queue;
1044 /* Recursive routine to find strongly connected components in GRAPH.
1045 SI is the SCC info to store the information in, and N is the id of current
1046 graph node we are processing.
1048 This is Tarjan's strongly connected component finding algorithm, as
1049 modified by Nuutila to keep only non-root nodes on the stack.
1050 The algorithm can be found in "On finding the strongly connected
1051 connected components in a directed graph" by Esko Nuutila and Eljas
1052 Soisalon-Soininen, in Information Processing Letters volume 49,
1053 number 1, pages 9-14. */
1055 static void
1056 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1058 constraint_edge_t c;
1059 int i;
1061 gcc_assert (get_varinfo (n)->node == n);
1062 SET_BIT (si->visited, n);
1063 RESET_BIT (si->in_component, n);
1064 si->visited_index[n] = si->current_index ++;
1066 /* Visit all the successors. */
1067 for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++)
1069 /* We only want to find and collapse the zero weight edges. */
1070 if (bitmap_bit_p (c->weights, 0))
1072 unsigned int w = c->dest;
1073 if (!TEST_BIT (si->visited, w))
1074 scc_visit (graph, si, w);
1075 if (!TEST_BIT (si->in_component, w))
1077 unsigned int t = get_varinfo (w)->node;
1078 unsigned int nnode = get_varinfo (n)->node;
1079 if (si->visited_index[t] < si->visited_index[nnode])
1080 get_varinfo (n)->node = t;
1085 /* See if any components have been identified. */
1086 if (get_varinfo (n)->node == n)
1088 unsigned int t = si->visited_index[n];
1089 SET_BIT (si->in_component, n);
1090 while (VEC_length (unsigned, si->scc_stack) != 0
1091 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1093 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1094 get_varinfo (w)->node = n;
1095 SET_BIT (si->in_component, w);
1096 /* Mark this node for collapsing. */
1097 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1100 else
1101 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1105 /* Collapse two variables into one variable. */
1107 static void
1108 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1110 bitmap tosol, fromsol;
1111 struct constraint_edge edge;
1114 condense_varmap_nodes (to, from);
1115 tosol = get_varinfo (to)->solution;
1116 fromsol = get_varinfo (from)->solution;
1117 bitmap_ior_into (tosol, fromsol);
1118 merge_graph_nodes (graph, to, from);
1119 edge.src = to;
1120 edge.dest = to;
1121 edge.weights = NULL;
1122 if (valid_graph_edge (graph, edge))
1124 bitmap weights = get_graph_weights (graph, edge);
1125 bitmap_clear_bit (weights, 0);
1126 if (bitmap_empty_p (weights))
1127 erase_graph_self_edge (graph, edge);
1129 bitmap_clear (fromsol);
1130 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1131 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1135 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1136 SI is the Strongly Connected Components information structure that tells us
1137 what components to unify.
1138 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1139 count should be updated to reflect the unification. */
1141 static void
1142 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1143 bool update_changed)
1145 size_t i = 0;
1146 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1147 bitmap_clear (tmp);
1149 /* We proceed as follows:
1151 For each component in the queue (components are delineated by
1152 when current_queue_element->node != next_queue_element->node):
1154 rep = representative node for component
1156 For each node (tounify) to be unified in the component,
1157 merge the solution for tounify into tmp bitmap
1159 clear solution for tounify
1161 merge edges from tounify into rep
1163 merge complex constraints from tounify into rep
1165 update changed count to note that tounify will never change
1166 again
1168 Merge tmp into solution for rep, marking rep changed if this
1169 changed rep's solution.
1171 Delete any 0 weighted self-edges we now have for rep. */
1172 while (i != VEC_length (unsigned, si->unification_queue))
1174 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1175 unsigned int n = get_varinfo (tounify)->node;
1177 if (dump_file && (dump_flags & TDF_DETAILS))
1178 fprintf (dump_file, "Unifying %s to %s\n",
1179 get_varinfo (tounify)->name,
1180 get_varinfo (n)->name);
1181 if (update_changed)
1182 stats.unified_vars_dynamic++;
1183 else
1184 stats.unified_vars_static++;
1185 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1186 merge_graph_nodes (graph, n, tounify);
1187 condense_varmap_nodes (n, tounify);
1189 if (update_changed && TEST_BIT (changed, tounify))
1191 RESET_BIT (changed, tounify);
1192 if (!TEST_BIT (changed, n))
1193 SET_BIT (changed, n);
1194 else
1196 gcc_assert (changed_count > 0);
1197 changed_count--;
1201 bitmap_clear (get_varinfo (tounify)->solution);
1202 ++i;
1204 /* If we've either finished processing the entire queue, or
1205 finished processing all nodes for component n, update the solution for
1206 n. */
1207 if (i == VEC_length (unsigned, si->unification_queue)
1208 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1210 struct constraint_edge edge;
1212 /* If the solution changes because of the merging, we need to mark
1213 the variable as changed. */
1214 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1216 if (update_changed && !TEST_BIT (changed, n))
1218 SET_BIT (changed, n);
1219 changed_count++;
1222 bitmap_clear (tmp);
1223 edge.src = n;
1224 edge.dest = n;
1225 edge.weights = NULL;
1226 if (valid_graph_edge (graph, edge))
1228 bitmap weights = get_graph_weights (graph, edge);
1229 bitmap_clear_bit (weights, 0);
1230 if (bitmap_empty_p (weights))
1231 erase_graph_self_edge (graph, edge);
1235 BITMAP_FREE (tmp);
1239 /* Information needed to compute the topological ordering of a graph. */
1241 struct topo_info
1243 /* sbitmap of visited nodes. */
1244 sbitmap visited;
1245 /* Array that stores the topological order of the graph, *in
1246 reverse*. */
1247 VEC(unsigned,heap) *topo_order;
1251 /* Initialize and return a topological info structure. */
1253 static struct topo_info *
1254 init_topo_info (void)
1256 size_t size = VEC_length (varinfo_t, varmap);
1257 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1258 ti->visited = sbitmap_alloc (size);
1259 sbitmap_zero (ti->visited);
1260 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1261 return ti;
1265 /* Free the topological sort info pointed to by TI. */
1267 static void
1268 free_topo_info (struct topo_info *ti)
1270 sbitmap_free (ti->visited);
1271 VEC_free (unsigned, heap, ti->topo_order);
1272 free (ti);
1275 /* Visit the graph in topological order, and store the order in the
1276 topo_info structure. */
1278 static void
1279 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1280 unsigned int n)
1282 VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1283 constraint_edge_t c;
1284 int i;
1285 SET_BIT (ti->visited, n);
1286 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1288 if (!TEST_BIT (ti->visited, c->dest))
1289 topo_visit (graph, ti, c->dest);
1291 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1294 /* Return true if variable N + OFFSET is a legal field of N. */
1296 static bool
1297 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1299 varinfo_t ninfo = get_varinfo (n);
1301 /* For things we've globbed to single variables, any offset into the
1302 variable acts like the entire variable, so that it becomes offset
1303 0. */
1304 if (ninfo->is_special_var
1305 || ninfo->is_artificial_var
1306 || ninfo->is_unknown_size_var)
1308 *offset = 0;
1309 return true;
1311 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1314 /* Process a constraint C that represents *x = &y. */
1316 static void
1317 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1318 constraint_t c, bitmap delta)
1320 unsigned int rhs = c->rhs.var;
1321 unsigned int j;
1322 bitmap_iterator bi;
1324 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1325 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1327 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1328 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1330 /* *x != NULL && *x != ANYTHING*/
1331 varinfo_t v;
1332 unsigned int t;
1333 bitmap sol;
1334 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1336 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1337 if (!v)
1338 continue;
1339 t = v->node;
1340 sol = get_varinfo (t)->solution;
1341 if (!bitmap_bit_p (sol, rhs))
1343 bitmap_set_bit (sol, rhs);
1344 if (!TEST_BIT (changed, t))
1346 SET_BIT (changed, t);
1347 changed_count++;
1351 else if (dump_file && !(get_varinfo (j)->is_special_var))
1352 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1357 /* Process a constraint C that represents x = *y, using DELTA as the
1358 starting solution. */
1360 static void
1361 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1362 bitmap delta)
1364 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1365 bool flag = false;
1366 bitmap sol = get_varinfo (lhs)->solution;
1367 unsigned int j;
1368 bitmap_iterator bi;
1370 /* For each variable j in delta (Sol(y)), add
1371 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1372 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1374 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1375 if (type_safe (j, &roffset))
1377 varinfo_t v;
1378 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1379 unsigned int t;
1381 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1382 if (!v)
1383 continue;
1384 t = v->node;
1385 if (int_add_graph_edge (graph, lhs, t, 0))
1386 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1388 else if (dump_file && !(get_varinfo (j)->is_special_var))
1389 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1393 /* If the LHS solution changed, mark the var as changed. */
1394 if (flag)
1396 get_varinfo (lhs)->solution = sol;
1397 if (!TEST_BIT (changed, lhs))
1399 SET_BIT (changed, lhs);
1400 changed_count++;
1405 /* Process a constraint C that represents *x = y. */
1407 static void
1408 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1410 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1411 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1412 bitmap sol = get_varinfo (rhs)->solution;
1413 unsigned int j;
1414 bitmap_iterator bi;
1416 /* For each member j of delta (Sol(x)), add an edge from y to j and
1417 union Sol(y) into Sol(j) */
1418 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1420 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1421 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1423 varinfo_t v;
1424 unsigned int t;
1425 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1427 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1428 if (!v)
1429 continue;
1430 t = v->node;
1431 if (int_add_graph_edge (graph, t, rhs, roff))
1433 bitmap tmp = get_varinfo (t)->solution;
1434 if (set_union_with_increment (tmp, sol, roff))
1436 get_varinfo (t)->solution = tmp;
1437 if (t == rhs)
1439 sol = get_varinfo (rhs)->solution;
1441 if (!TEST_BIT (changed, t))
1443 SET_BIT (changed, t);
1444 changed_count++;
1449 else if (dump_file && !(get_varinfo (j)->is_special_var))
1450 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1454 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1455 constraint (IE *x = &y, x = *y, and *x = y). */
1457 static void
1458 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1460 if (c->lhs.type == DEREF)
1462 if (c->rhs.type == ADDRESSOF)
1464 /* *x = &y */
1465 do_da_constraint (graph, c, delta);
1467 else
1469 /* *x = y */
1470 do_ds_constraint (graph, c, delta);
1473 else
1475 /* x = *y */
1476 if (!(get_varinfo (c->lhs.var)->is_special_var))
1477 do_sd_constraint (graph, c, delta);
1481 /* Initialize and return a new SCC info structure. */
1483 static struct scc_info *
1484 init_scc_info (void)
1486 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1487 size_t size = VEC_length (varinfo_t, varmap);
1489 si->current_index = 0;
1490 si->visited = sbitmap_alloc (size);
1491 sbitmap_zero (si->visited);
1492 si->in_component = sbitmap_alloc (size);
1493 sbitmap_ones (si->in_component);
1494 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1495 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1496 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1497 return si;
1500 /* Free an SCC info structure pointed to by SI */
1502 static void
1503 free_scc_info (struct scc_info *si)
1505 sbitmap_free (si->visited);
1506 sbitmap_free (si->in_component);
1507 free (si->visited_index);
1508 VEC_free (unsigned, heap, si->scc_stack);
1509 VEC_free (unsigned, heap, si->unification_queue);
1510 free(si);
1514 /* Find cycles in GRAPH that occur, using strongly connected components, and
1515 collapse the cycles into a single representative node. if UPDATE_CHANGED
1516 is true, then update the changed sbitmap to note those nodes whose
1517 solutions have changed as a result of collapsing. */
1519 static void
1520 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1522 unsigned int i;
1523 unsigned int size = VEC_length (varinfo_t, varmap);
1524 struct scc_info *si = init_scc_info ();
1526 for (i = 0; i != size; ++i)
1527 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1528 scc_visit (graph, si, i);
1529 process_unification_queue (graph, si, update_changed);
1530 free_scc_info (si);
1533 /* Compute a topological ordering for GRAPH, and store the result in the
1534 topo_info structure TI. */
1536 static void
1537 compute_topo_order (constraint_graph_t graph,
1538 struct topo_info *ti)
1540 unsigned int i;
1541 unsigned int size = VEC_length (varinfo_t, varmap);
1543 for (i = 0; i != size; ++i)
1544 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1545 topo_visit (graph, ti, i);
1548 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1550 static bool
1551 bitmap_other_than_zero_bit_set (bitmap b)
1553 unsigned int i;
1554 bitmap_iterator bi;
1556 if (bitmap_empty_p (b))
1557 return false;
1558 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1559 return true;
1560 return false;
1563 /* Perform offline variable substitution.
1565 This is a linear time way of identifying variables that must have
1566 equivalent points-to sets, including those caused by static cycles,
1567 and single entry subgraphs, in the constraint graph.
1569 The technique is described in "Off-line variable substitution for
1570 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1571 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1573 static void
1574 perform_var_substitution (constraint_graph_t graph)
1576 struct topo_info *ti = init_topo_info ();
1578 /* Compute the topological ordering of the graph, then visit each
1579 node in topological order. */
1580 compute_topo_order (graph, ti);
1582 while (VEC_length (unsigned, ti->topo_order) != 0)
1584 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1585 unsigned int pred;
1586 varinfo_t vi = get_varinfo (i);
1587 bool okay_to_elim = false;
1588 unsigned int root = VEC_length (varinfo_t, varmap);
1589 VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1590 constraint_edge_t ce;
1591 bitmap tmp;
1593 /* We can't eliminate things whose address is taken, or which is
1594 the target of a dereference. */
1595 if (vi->address_taken || vi->indirect_target)
1596 continue;
1598 /* See if all predecessors of I are ripe for elimination */
1599 for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++)
1601 bitmap weight;
1602 unsigned int w;
1603 weight = get_graph_weights (graph, *ce);
1605 /* We can't eliminate variables that have nonzero weighted
1606 edges between them. */
1607 if (bitmap_other_than_zero_bit_set (weight))
1609 okay_to_elim = false;
1610 break;
1612 w = get_varinfo (ce->dest)->node;
1614 /* We can't eliminate the node if one of the predecessors is
1615 part of a different strongly connected component. */
1616 if (!okay_to_elim)
1618 root = w;
1619 okay_to_elim = true;
1621 else if (w != root)
1623 okay_to_elim = false;
1624 break;
1627 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1628 then Solution(i) is a subset of Solution (w), where w is a
1629 predecessor in the graph.
1630 Corollary: If all predecessors of i have the same
1631 points-to set, then i has that same points-to set as
1632 those predecessors. */
1633 tmp = BITMAP_ALLOC (NULL);
1634 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1635 get_varinfo (w)->solution);
1636 if (!bitmap_empty_p (tmp))
1638 okay_to_elim = false;
1639 BITMAP_FREE (tmp);
1640 break;
1642 BITMAP_FREE (tmp);
1645 /* See if the root is different than the original node.
1646 If so, we've found an equivalence. */
1647 if (root != get_varinfo (i)->node && okay_to_elim)
1649 /* Found an equivalence */
1650 get_varinfo (i)->node = root;
1651 collapse_nodes (graph, root, i);
1652 if (dump_file && (dump_flags & TDF_DETAILS))
1653 fprintf (dump_file, "Collapsing %s into %s\n",
1654 get_varinfo (i)->name,
1655 get_varinfo (root)->name);
1656 stats.collapsed_vars++;
1660 free_topo_info (ti);
1664 /* Solve the constraint graph GRAPH using our worklist solver.
1665 This is based on the PW* family of solvers from the "Efficient Field
1666 Sensitive Pointer Analysis for C" paper.
1667 It works by iterating over all the graph nodes, processing the complex
1668 constraints and propagating the copy constraints, until everything stops
1669 changed. This corresponds to steps 6-8 in the solving list given above. */
1671 static void
1672 solve_graph (constraint_graph_t graph)
1674 unsigned int size = VEC_length (varinfo_t, varmap);
1675 unsigned int i;
1677 changed_count = size;
1678 changed = sbitmap_alloc (size);
1679 sbitmap_ones (changed);
1681 /* The already collapsed/unreachable nodes will never change, so we
1682 need to account for them in changed_count. */
1683 for (i = 0; i < size; i++)
1684 if (get_varinfo (i)->node != i)
1685 changed_count--;
1687 while (changed_count > 0)
1689 unsigned int i;
1690 struct topo_info *ti = init_topo_info ();
1691 stats.iterations++;
1693 bitmap_obstack_initialize (&iteration_obstack);
1695 if (edge_added)
1697 /* We already did cycle elimination once, when we did
1698 variable substitution, so we don't need it again for the
1699 first iteration. */
1700 if (stats.iterations > 1)
1701 find_and_collapse_graph_cycles (graph, true);
1703 edge_added = false;
1706 compute_topo_order (graph, ti);
1708 while (VEC_length (unsigned, ti->topo_order) != 0)
1710 i = VEC_pop (unsigned, ti->topo_order);
1711 gcc_assert (get_varinfo (i)->node == i);
1713 /* If the node has changed, we need to process the
1714 complex constraints and outgoing edges again. */
1715 if (TEST_BIT (changed, i))
1717 unsigned int j;
1718 constraint_t c;
1719 constraint_edge_t e;
1720 bitmap solution;
1721 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
1722 VEC(constraint_edge_t,heap) *succs;
1724 RESET_BIT (changed, i);
1725 changed_count--;
1727 /* Process the complex constraints */
1728 solution = get_varinfo (i)->solution;
1729 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1730 do_complex_constraint (graph, c, solution);
1732 /* Propagate solution to all successors. */
1733 succs = graph->succs[i];
1734 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
1736 bitmap tmp = get_varinfo (e->dest)->solution;
1737 bool flag = false;
1738 unsigned int k;
1739 bitmap weights = e->weights;
1740 bitmap_iterator bi;
1742 gcc_assert (!bitmap_empty_p (weights));
1743 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
1744 flag |= set_union_with_increment (tmp, solution, k);
1746 if (flag)
1748 get_varinfo (e->dest)->solution = tmp;
1749 if (!TEST_BIT (changed, e->dest))
1751 SET_BIT (changed, e->dest);
1752 changed_count++;
1758 free_topo_info (ti);
1759 bitmap_obstack_release (&iteration_obstack);
1762 sbitmap_free (changed);
1766 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1768 /* Map from trees to variable ids. */
1769 static htab_t id_for_tree;
1771 typedef struct tree_id
1773 tree t;
1774 unsigned int id;
1775 } *tree_id_t;
1777 /* Hash a tree id structure. */
1779 static hashval_t
1780 tree_id_hash (const void *p)
1782 const tree_id_t ta = (tree_id_t) p;
1783 return htab_hash_pointer (ta->t);
1786 /* Return true if the tree in P1 and the tree in P2 are the same. */
1788 static int
1789 tree_id_eq (const void *p1, const void *p2)
1791 const tree_id_t ta1 = (tree_id_t) p1;
1792 const tree_id_t ta2 = (tree_id_t) p2;
1793 return ta1->t == ta2->t;
1796 /* Insert ID as the variable id for tree T in the hashtable. */
1798 static void
1799 insert_id_for_tree (tree t, int id)
1801 void **slot;
1802 struct tree_id finder;
1803 tree_id_t new_pair;
1805 finder.t = t;
1806 slot = htab_find_slot (id_for_tree, &finder, INSERT);
1807 gcc_assert (*slot == NULL);
1808 new_pair = xmalloc (sizeof (struct tree_id));
1809 new_pair->t = t;
1810 new_pair->id = id;
1811 *slot = (void *)new_pair;
1814 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1815 exist in the hash table, return false, otherwise, return true and
1816 set *ID to the id we found. */
1818 static bool
1819 lookup_id_for_tree (tree t, unsigned int *id)
1821 tree_id_t pair;
1822 struct tree_id finder;
1824 finder.t = t;
1825 pair = htab_find (id_for_tree, &finder);
1826 if (pair == NULL)
1827 return false;
1828 *id = pair->id;
1829 return true;
1832 /* Return a printable name for DECL */
1834 static const char *
1835 alias_get_name (tree decl)
1837 const char *res = get_name (decl);
1838 char *temp;
1839 int num_printed = 0;
1841 if (res != NULL)
1842 return res;
1844 res = "NULL";
1845 if (TREE_CODE (decl) == SSA_NAME)
1847 num_printed = asprintf (&temp, "%s_%u",
1848 alias_get_name (SSA_NAME_VAR (decl)),
1849 SSA_NAME_VERSION (decl));
1851 else if (DECL_P (decl))
1853 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1855 if (num_printed > 0)
1857 res = ggc_strdup (temp);
1858 free (temp);
1860 return res;
1863 /* Find the variable id for tree T in the hashtable.
1864 If T doesn't exist in the hash table, create an entry for it. */
1866 static unsigned int
1867 get_id_for_tree (tree t)
1869 tree_id_t pair;
1870 struct tree_id finder;
1872 finder.t = t;
1873 pair = htab_find (id_for_tree, &finder);
1874 if (pair == NULL)
1875 return create_variable_info_for (t, alias_get_name (t));
1877 return pair->id;
1880 /* Get a constraint expression from an SSA_VAR_P node. */
1882 static struct constraint_expr
1883 get_constraint_exp_from_ssa_var (tree t)
1885 struct constraint_expr cexpr;
1887 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1889 /* For parameters, get at the points-to set for the actual parm
1890 decl. */
1891 if (TREE_CODE (t) == SSA_NAME
1892 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
1893 && default_def (SSA_NAME_VAR (t)) == t)
1894 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1896 cexpr.type = SCALAR;
1898 cexpr.var = get_id_for_tree (t);
1899 /* If we determine the result is "anything", and we know this is readonly,
1900 say it points to readonly memory instead. */
1901 if (cexpr.var == anything_id && TREE_READONLY (t))
1903 cexpr.type = ADDRESSOF;
1904 cexpr.var = readonly_id;
1907 cexpr.offset = 0;
1908 return cexpr;
1911 /* Process a completed constraint T, and add it to the constraint
1912 list. */
1914 static void
1915 process_constraint (constraint_t t)
1917 struct constraint_expr rhs = t->rhs;
1918 struct constraint_expr lhs = t->lhs;
1920 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1921 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1923 /* ANYTHING == ANYTHING is pointless. */
1924 if (lhs.var == anything_id && rhs.var == anything_id)
1925 return;
1927 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1928 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
1930 rhs = t->lhs;
1931 t->lhs = t->rhs;
1932 t->rhs = rhs;
1933 process_constraint (t);
1935 /* This can happen in our IR with things like n->a = *p */
1936 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1938 /* Split into tmp = *rhs, *lhs = tmp */
1939 tree rhsdecl = get_varinfo (rhs.var)->decl;
1940 tree pointertype = TREE_TYPE (rhsdecl);
1941 tree pointedtotype = TREE_TYPE (pointertype);
1942 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1943 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1945 /* If this is an aggregate of known size, we should have passed
1946 this off to do_structure_copy, and it should have broken it
1947 up. */
1948 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
1949 || get_varinfo (rhs.var)->is_unknown_size_var);
1951 process_constraint (new_constraint (tmplhs, rhs));
1952 process_constraint (new_constraint (lhs, tmplhs));
1954 else if (rhs.type == ADDRESSOF)
1956 varinfo_t vi;
1957 gcc_assert (rhs.offset == 0);
1959 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1960 vi->address_taken = true;
1962 VEC_safe_push (constraint_t, heap, constraints, t);
1964 else
1966 if (lhs.type != DEREF && rhs.type == DEREF)
1967 get_varinfo (lhs.var)->indirect_target = true;
1968 VEC_safe_push (constraint_t, heap, constraints, t);
1973 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1974 structure. */
1976 static unsigned HOST_WIDE_INT
1977 bitpos_of_field (const tree fdecl)
1980 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1981 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1982 return -1;
1984 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
1985 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1989 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1990 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1992 static bool
1993 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
1994 const unsigned HOST_WIDE_INT fieldsize,
1995 const unsigned HOST_WIDE_INT accesspos,
1996 const unsigned HOST_WIDE_INT accesssize)
1998 if (fieldpos == accesspos && fieldsize == accesssize)
1999 return true;
2000 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2001 return true;
2002 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2003 return true;
2005 return false;
2008 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2010 static struct constraint_expr
2011 get_constraint_for_component_ref (tree t, bool *need_anyoffset)
2013 struct constraint_expr result;
2014 HOST_WIDE_INT bitsize = -1;
2015 HOST_WIDE_INT bitpos;
2016 tree offset = NULL_TREE;
2017 enum machine_mode mode;
2018 int unsignedp;
2019 int volatilep;
2020 tree forzero;
2022 result.offset = 0;
2023 result.type = SCALAR;
2024 result.var = 0;
2026 /* Some people like to do cute things like take the address of
2027 &0->a.b */
2028 forzero = t;
2029 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2030 forzero = TREE_OPERAND (forzero, 0);
2032 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2034 result.offset = 0;
2035 result.var = integer_id;
2036 result.type = SCALAR;
2037 return result;
2040 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
2041 &unsignedp, &volatilep, false);
2042 result = get_constraint_for (t, need_anyoffset);
2044 /* This can also happen due to weird offsetof type macros. */
2045 if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
2046 result.type = SCALAR;
2048 /* If we know where this goes, then yay. Otherwise, booo. */
2050 if (offset == NULL && bitsize != -1)
2052 result.offset = bitpos;
2054 else if (need_anyoffset)
2056 result.offset = 0;
2057 *need_anyoffset = true;
2059 else
2061 result.var = anything_id;
2062 result.offset = 0;
2065 if (result.type == SCALAR)
2067 /* In languages like C, you can access one past the end of an
2068 array. You aren't allowed to dereference it, so we can
2069 ignore this constraint. When we handle pointer subtraction,
2070 we may have to do something cute here. */
2072 if (result.offset < get_varinfo (result.var)->fullsize)
2074 /* It's also not true that the constraint will actually start at the
2075 right offset, it may start in some padding. We only care about
2076 setting the constraint to the first actual field it touches, so
2077 walk to find it. */
2078 varinfo_t curr;
2079 for (curr = get_varinfo (result.var); curr; curr = curr->next)
2081 if (offset_overlaps_with_access (curr->offset, curr->size,
2082 result.offset, bitsize))
2084 result.var = curr->id;
2085 break;
2089 /* assert that we found *some* field there. The user couldn't be
2090 accessing *only* padding. */
2092 gcc_assert (curr);
2094 else
2095 if (dump_file && (dump_flags & TDF_DETAILS))
2096 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2098 result.offset = 0;
2101 return result;
2105 /* Dereference the constraint expression CONS, and return the result.
2106 DEREF (ADDRESSOF) = SCALAR
2107 DEREF (SCALAR) = DEREF
2108 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2109 This is needed so that we can handle dereferencing DEREF constraints. */
2111 static struct constraint_expr
2112 do_deref (struct constraint_expr cons)
2114 if (cons.type == SCALAR)
2116 cons.type = DEREF;
2117 return cons;
2119 else if (cons.type == ADDRESSOF)
2121 cons.type = SCALAR;
2122 return cons;
2124 else if (cons.type == DEREF)
2126 tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2127 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2128 process_constraint (new_constraint (tmplhs, cons));
2129 cons.var = tmplhs.var;
2130 return cons;
2132 gcc_unreachable ();
2136 /* Given a tree T, return the constraint expression for it. */
2138 static struct constraint_expr
2139 get_constraint_for (tree t, bool *need_anyoffset)
2141 struct constraint_expr temp;
2143 /* x = integer is all glommed to a single variable, which doesn't
2144 point to anything by itself. That is, of course, unless it is an
2145 integer constant being treated as a pointer, in which case, we
2146 will return that this is really the addressof anything. This
2147 happens below, since it will fall into the default case. The only
2148 case we know something about an integer treated like a pointer is
2149 when it is the NULL pointer, and then we just say it points to
2150 NULL. */
2151 if (TREE_CODE (t) == INTEGER_CST
2152 && !POINTER_TYPE_P (TREE_TYPE (t)))
2154 temp.var = integer_id;
2155 temp.type = SCALAR;
2156 temp.offset = 0;
2157 return temp;
2159 else if (TREE_CODE (t) == INTEGER_CST
2160 && integer_zerop (t))
2162 temp.var = nothing_id;
2163 temp.type = ADDRESSOF;
2164 temp.offset = 0;
2165 return temp;
2168 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2170 case tcc_expression:
2172 switch (TREE_CODE (t))
2174 case ADDR_EXPR:
2176 temp = get_constraint_for (TREE_OPERAND (t, 0), need_anyoffset);
2177 if (temp.type == DEREF)
2178 temp.type = SCALAR;
2179 else
2180 temp.type = ADDRESSOF;
2181 return temp;
2183 break;
2184 case CALL_EXPR:
2186 /* XXX: In interprocedural mode, if we didn't have the
2187 body, we would need to do *each pointer argument =
2188 &ANYTHING added. */
2189 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2191 varinfo_t vi;
2192 tree heapvar;
2194 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2195 DECL_EXTERNAL (heapvar) = 1;
2196 add_referenced_tmp_var (heapvar);
2197 temp.var = create_variable_info_for (heapvar,
2198 alias_get_name (heapvar));
2200 vi = get_varinfo (temp.var);
2201 vi->is_artificial_var = 1;
2202 vi->is_heap_var = 1;
2203 temp.type = ADDRESSOF;
2204 temp.offset = 0;
2205 return temp;
2207 /* FALLTHRU */
2208 default:
2210 temp.type = ADDRESSOF;
2211 temp.var = anything_id;
2212 temp.offset = 0;
2213 return temp;
2217 case tcc_reference:
2219 switch (TREE_CODE (t))
2221 case INDIRECT_REF:
2223 temp = get_constraint_for (TREE_OPERAND (t, 0), need_anyoffset);
2224 temp = do_deref (temp);
2225 return temp;
2227 case ARRAY_REF:
2228 case COMPONENT_REF:
2229 temp = get_constraint_for_component_ref (t, need_anyoffset);
2230 return temp;
2231 default:
2233 temp.type = ADDRESSOF;
2234 temp.var = anything_id;
2235 temp.offset = 0;
2236 return temp;
2240 case tcc_unary:
2242 switch (TREE_CODE (t))
2244 case NOP_EXPR:
2245 case CONVERT_EXPR:
2246 case NON_LVALUE_EXPR:
2248 tree op = TREE_OPERAND (t, 0);
2250 /* Cast from non-pointer to pointers are bad news for us.
2251 Anything else, we see through */
2252 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2253 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2254 return get_constraint_for (op, need_anyoffset);
2256 /* FALLTHRU */
2258 default:
2260 temp.type = ADDRESSOF;
2261 temp.var = anything_id;
2262 temp.offset = 0;
2263 return temp;
2267 case tcc_exceptional:
2269 switch (TREE_CODE (t))
2271 case PHI_NODE:
2272 return get_constraint_for (PHI_RESULT (t), need_anyoffset);
2273 case SSA_NAME:
2274 return get_constraint_exp_from_ssa_var (t);
2275 default:
2277 temp.type = ADDRESSOF;
2278 temp.var = anything_id;
2279 temp.offset = 0;
2280 return temp;
2284 case tcc_declaration:
2285 return get_constraint_exp_from_ssa_var (t);
2286 default:
2288 temp.type = ADDRESSOF;
2289 temp.var = anything_id;
2290 temp.offset = 0;
2291 return temp;
2297 /* Handle the structure copy case where we have a simple structure copy
2298 between LHS and RHS that is of SIZE (in bits)
2300 For each field of the lhs variable (lhsfield)
2301 For each field of the rhs variable at lhsfield.offset (rhsfield)
2302 add the constraint lhsfield = rhsfield
2305 static void
2306 do_simple_structure_copy (const struct constraint_expr lhs,
2307 const struct constraint_expr rhs,
2308 const unsigned HOST_WIDE_INT size)
2310 varinfo_t p = get_varinfo (lhs.var);
2311 unsigned HOST_WIDE_INT pstart, last;
2312 pstart = p->offset;
2313 last = p->offset + size;
2314 for (; p && p->offset < last; p = p->next)
2316 varinfo_t q;
2317 struct constraint_expr templhs = lhs;
2318 struct constraint_expr temprhs = rhs;
2319 unsigned HOST_WIDE_INT fieldoffset;
2321 templhs.var = p->id;
2322 q = get_varinfo (temprhs.var);
2323 fieldoffset = p->offset - pstart;
2324 q = first_vi_for_offset (q, q->offset + fieldoffset);
2325 temprhs.var = q->id;
2326 process_constraint (new_constraint (templhs, temprhs));
2331 /* Handle the structure copy case where we have a structure copy between a
2332 aggregate on the LHS and a dereference of a pointer on the RHS
2333 that is of SIZE (in bits)
2335 For each field of the lhs variable (lhsfield)
2336 rhs.offset = lhsfield->offset
2337 add the constraint lhsfield = rhs
2340 static void
2341 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2342 const struct constraint_expr rhs,
2343 const unsigned HOST_WIDE_INT size)
2345 varinfo_t p = get_varinfo (lhs.var);
2346 unsigned HOST_WIDE_INT pstart,last;
2347 pstart = p->offset;
2348 last = p->offset + size;
2350 for (; p && p->offset < last; p = p->next)
2352 varinfo_t q;
2353 struct constraint_expr templhs = lhs;
2354 struct constraint_expr temprhs = rhs;
2355 unsigned HOST_WIDE_INT fieldoffset;
2358 if (templhs.type == SCALAR)
2359 templhs.var = p->id;
2360 else
2361 templhs.offset = p->offset;
2363 q = get_varinfo (temprhs.var);
2364 fieldoffset = p->offset - pstart;
2365 temprhs.offset += fieldoffset;
2366 process_constraint (new_constraint (templhs, temprhs));
2370 /* Handle the structure copy case where we have a structure copy
2371 between a aggregate on the RHS and a dereference of a pointer on
2372 the LHS that is of SIZE (in bits)
2374 For each field of the rhs variable (rhsfield)
2375 lhs.offset = rhsfield->offset
2376 add the constraint lhs = rhsfield
2379 static void
2380 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2381 const struct constraint_expr rhs,
2382 const unsigned HOST_WIDE_INT size)
2384 varinfo_t p = get_varinfo (rhs.var);
2385 unsigned HOST_WIDE_INT pstart,last;
2386 pstart = p->offset;
2387 last = p->offset + size;
2389 for (; p && p->offset < last; p = p->next)
2391 varinfo_t q;
2392 struct constraint_expr templhs = lhs;
2393 struct constraint_expr temprhs = rhs;
2394 unsigned HOST_WIDE_INT fieldoffset;
2397 if (temprhs.type == SCALAR)
2398 temprhs.var = p->id;
2399 else
2400 temprhs.offset = p->offset;
2402 q = get_varinfo (templhs.var);
2403 fieldoffset = p->offset - pstart;
2404 templhs.offset += fieldoffset;
2405 process_constraint (new_constraint (templhs, temprhs));
2410 /* Handle aggregate copies by expanding into copies of the respective
2411 fields of the structures. */
2413 static void
2414 do_structure_copy (tree lhsop, tree rhsop)
2416 struct constraint_expr lhs, rhs, tmp;
2417 varinfo_t p;
2418 unsigned HOST_WIDE_INT lhssize;
2419 unsigned HOST_WIDE_INT rhssize;
2421 lhs = get_constraint_for (lhsop, NULL);
2422 rhs = get_constraint_for (rhsop, NULL);
2424 /* If we have special var = x, swap it around. */
2425 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2427 tmp = lhs;
2428 lhs = rhs;
2429 rhs = tmp;
2432 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2433 possible it's something we could handle. However, most cases falling
2434 into this are dealing with transparent unions, which are slightly
2435 weird. */
2436 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2438 rhs.type = ADDRESSOF;
2439 rhs.var = anything_id;
2442 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2443 that special var. */
2444 if (rhs.var <= integer_id)
2446 for (p = get_varinfo (lhs.var); p; p = p->next)
2448 struct constraint_expr templhs = lhs;
2449 struct constraint_expr temprhs = rhs;
2450 if (templhs.type == SCALAR )
2451 templhs.var = p->id;
2452 else
2453 templhs.offset += p->offset;
2454 process_constraint (new_constraint (templhs, temprhs));
2457 else
2459 tree rhstype = TREE_TYPE (rhsop);
2460 tree lhstype = TREE_TYPE (lhsop);
2461 tree rhstypesize = TYPE_SIZE (rhstype);
2462 tree lhstypesize = TYPE_SIZE (lhstype);
2464 /* If we have a variably sized types on the rhs or lhs, and a deref
2465 constraint, add the constraint, lhsconstraint = &ANYTHING.
2466 This is conservatively correct because either the lhs is an unknown
2467 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2468 constraint, and every variable it can point to must be unknown sized
2469 anyway, so we don't need to worry about fields at all. */
2470 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2471 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2473 rhs.var = anything_id;
2474 rhs.type = ADDRESSOF;
2475 rhs.offset = 0;
2476 process_constraint (new_constraint (lhs, rhs));
2477 return;
2480 /* The size only really matters insofar as we don't set more or less of
2481 the variable. If we hit an unknown size var, the size should be the
2482 whole darn thing. */
2483 if (get_varinfo (rhs.var)->is_unknown_size_var)
2484 rhssize = ~0;
2485 else
2486 rhssize = TREE_INT_CST_LOW (rhstypesize);
2488 if (get_varinfo (lhs.var)->is_unknown_size_var)
2489 lhssize = ~0;
2490 else
2491 lhssize = TREE_INT_CST_LOW (lhstypesize);
2494 if (rhs.type == SCALAR && lhs.type == SCALAR)
2495 do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2496 else if (lhs.type != DEREF && rhs.type == DEREF)
2497 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2498 else if (lhs.type == DEREF && rhs.type != DEREF)
2499 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2500 else
2502 tree pointedtotype = lhstype;
2503 tree tmpvar;
2505 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2506 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2507 do_structure_copy (tmpvar, rhsop);
2508 do_structure_copy (lhsop, tmpvar);
2513 /* Update related alias information kept in AI. This is used when
2514 building name tags, alias sets and deciding grouping heuristics.
2515 STMT is the statement to process. This function also updates
2516 ADDRESSABLE_VARS. */
2518 static void
2519 update_alias_info (tree stmt, struct alias_info *ai)
2521 bitmap addr_taken;
2522 use_operand_p use_p;
2523 ssa_op_iter iter;
2524 bool stmt_escapes_p = is_escape_site (stmt, ai);
2525 tree op;
2527 /* Mark all the variables whose address are taken by the statement. */
2528 addr_taken = addresses_taken (stmt);
2529 if (addr_taken)
2531 bitmap_ior_into (addressable_vars, addr_taken);
2533 /* If STMT is an escape point, all the addresses taken by it are
2534 call-clobbered. */
2535 if (stmt_escapes_p)
2537 bitmap_iterator bi;
2538 unsigned i;
2540 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2541 mark_call_clobbered (referenced_var (i));
2545 /* Process each operand use. If an operand may be aliased, keep
2546 track of how many times it's being used. For pointers, determine
2547 whether they are dereferenced by the statement, or whether their
2548 value escapes, etc. */
2549 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2551 tree op, var;
2552 var_ann_t v_ann;
2553 struct ptr_info_def *pi;
2554 bool is_store, is_potential_deref;
2555 unsigned num_uses, num_derefs;
2557 op = USE_FROM_PTR (use_p);
2559 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2560 to the set of addressable variables. */
2561 if (TREE_CODE (op) == ADDR_EXPR)
2563 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
2565 /* PHI nodes don't have annotations for pinning the set
2566 of addresses taken, so we collect them here.
2568 FIXME, should we allow PHI nodes to have annotations
2569 so that they can be treated like regular statements?
2570 Currently, they are treated as second-class
2571 statements. */
2572 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
2573 continue;
2576 /* Ignore constants. */
2577 if (TREE_CODE (op) != SSA_NAME)
2578 continue;
2580 var = SSA_NAME_VAR (op);
2581 v_ann = var_ann (var);
2583 /* If the operand's variable may be aliased, keep track of how
2584 many times we've referenced it. This is used for alias
2585 grouping in compute_flow_insensitive_aliasing. */
2586 if (may_be_aliased (var))
2587 NUM_REFERENCES_INC (v_ann);
2589 /* We are only interested in pointers. */
2590 if (!POINTER_TYPE_P (TREE_TYPE (op)))
2591 continue;
2593 pi = get_ptr_info (op);
2595 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2596 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
2598 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
2599 VARRAY_PUSH_TREE (ai->processed_ptrs, op);
2602 /* If STMT is a PHI node, then it will not have pointer
2603 dereferences and it will not be an escape point. */
2604 if (TREE_CODE (stmt) == PHI_NODE)
2605 continue;
2607 /* Determine whether OP is a dereferenced pointer, and if STMT
2608 is an escape point, whether OP escapes. */
2609 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2611 /* Handle a corner case involving address expressions of the
2612 form '&PTR->FLD'. The problem with these expressions is that
2613 they do not represent a dereference of PTR. However, if some
2614 other transformation propagates them into an INDIRECT_REF
2615 expression, we end up with '*(&PTR->FLD)' which is folded
2616 into 'PTR->FLD'.
2618 So, if the original code had no other dereferences of PTR,
2619 the aliaser will not create memory tags for it, and when
2620 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
2621 memory operations will receive no V_MAY_DEF/VUSE operands.
2623 One solution would be to have count_uses_and_derefs consider
2624 &PTR->FLD a dereference of PTR. But that is wrong, since it
2625 is not really a dereference but an offset calculation.
2627 What we do here is to recognize these special ADDR_EXPR
2628 nodes. Since these expressions are never GIMPLE values (they
2629 are not GIMPLE invariants), they can only appear on the RHS
2630 of an assignment and their base address is always an
2631 INDIRECT_REF expression. */
2632 is_potential_deref = false;
2633 if (TREE_CODE (stmt) == MODIFY_EXPR
2634 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
2635 && !is_gimple_val (TREE_OPERAND (stmt, 1)))
2637 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
2638 this represents a potential dereference of PTR. */
2639 tree rhs = TREE_OPERAND (stmt, 1);
2640 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2641 if (TREE_CODE (base) == INDIRECT_REF
2642 && TREE_OPERAND (base, 0) == op)
2643 is_potential_deref = true;
2646 if (num_derefs > 0 || is_potential_deref)
2648 /* Mark OP as dereferenced. In a subsequent pass,
2649 dereferenced pointers that point to a set of
2650 variables will be assigned a name tag to alias
2651 all the variables OP points to. */
2652 pi->is_dereferenced = 1;
2654 /* Keep track of how many time we've dereferenced each
2655 pointer. */
2656 NUM_REFERENCES_INC (v_ann);
2658 /* If this is a store operation, mark OP as being
2659 dereferenced to store, otherwise mark it as being
2660 dereferenced to load. */
2661 if (is_store)
2662 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2663 else
2664 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
2667 if (stmt_escapes_p && num_derefs < num_uses)
2669 /* If STMT is an escape point and STMT contains at
2670 least one direct use of OP, then the value of OP
2671 escapes and so the pointed-to variables need to
2672 be marked call-clobbered. */
2673 pi->value_escapes_p = 1;
2675 /* If the statement makes a function call, assume
2676 that pointer OP will be dereferenced in a store
2677 operation inside the called function. */
2678 if (get_call_expr_in (stmt))
2680 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2681 pi->is_dereferenced = 1;
2686 if (TREE_CODE (stmt) == PHI_NODE)
2687 return;
2689 /* Update reference counter for definitions to any
2690 potentially aliased variable. This is used in the alias
2691 grouping heuristics. */
2692 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
2694 tree var = SSA_NAME_VAR (op);
2695 var_ann_t ann = var_ann (var);
2696 bitmap_set_bit (ai->written_vars, DECL_UID (var));
2697 if (may_be_aliased (var))
2698 NUM_REFERENCES_INC (ann);
2702 /* Mark variables in V_MAY_DEF operands as being written to. */
2703 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
2705 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
2706 bitmap_set_bit (ai->written_vars, DECL_UID (var));
2711 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
2712 Expressions of the type PTR + CST can be handled in two ways:
2714 1- If the constraint for PTR is ADDRESSOF for a non-structure
2715 variable, then we can use it directly because adding or
2716 subtracting a constant may not alter the original ADDRESSOF
2717 constraint (i.e., pointer arithmetic may not legally go outside
2718 an object's boundaries).
2720 2- If the constraint for PTR is ADDRESSOF for a structure variable,
2721 then if CST is a compile-time constant that can be used as an
2722 offset, we can determine which sub-variable will be pointed-to
2723 by the expression.
2725 Return true if the expression is handled. For any other kind of
2726 expression, return false so that each operand can be added as a
2727 separate constraint by the caller. */
2729 static bool
2730 handle_ptr_arith (struct constraint_expr lhs, tree expr)
2732 tree op0, op1;
2733 struct constraint_expr base, offset;
2735 if (TREE_CODE (expr) != PLUS_EXPR)
2736 return false;
2738 op0 = TREE_OPERAND (expr, 0);
2739 op1 = TREE_OPERAND (expr, 1);
2741 base = get_constraint_for (op0, NULL);
2743 offset.var = anyoffset_id;
2744 offset.type = ADDRESSOF;
2745 offset.offset = 0;
2747 process_constraint (new_constraint (lhs, base));
2748 process_constraint (new_constraint (lhs, offset));
2750 return true;
2754 /* Walk statement T setting up aliasing constraints according to the
2755 references found in T. This function is the main part of the
2756 constraint builder. AI points to auxiliary alias information used
2757 when building alias sets and computing alias grouping heuristics. */
2759 static void
2760 find_func_aliases (tree t, struct alias_info *ai)
2762 struct constraint_expr lhs, rhs;
2764 /* Update various related attributes like escaped addresses, pointer
2765 dereferences for loads and stores. This is used when creating
2766 name tags and alias sets. */
2767 update_alias_info (t, ai);
2769 /* Now build constraints expressions. */
2770 if (TREE_CODE (t) == PHI_NODE)
2772 /* Only care about pointers and structures containing
2773 pointers. */
2774 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2775 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2777 int i;
2779 lhs = get_constraint_for (PHI_RESULT (t), NULL);
2780 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2782 rhs = get_constraint_for (PHI_ARG_DEF (t, i), NULL);
2783 process_constraint (new_constraint (lhs, rhs));
2787 else if (TREE_CODE (t) == MODIFY_EXPR)
2789 tree lhsop = TREE_OPERAND (t, 0);
2790 tree rhsop = TREE_OPERAND (t, 1);
2791 int i;
2793 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2794 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2796 do_structure_copy (lhsop, rhsop);
2798 else
2800 /* Only care about operations with pointers, structures
2801 containing pointers, dereferences, and call expressions. */
2802 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2803 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2804 || ref_contains_indirect_ref (lhsop)
2805 || TREE_CODE (rhsop) == CALL_EXPR)
2807 lhs = get_constraint_for (lhsop, NULL);
2808 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2810 /* RHS that consist of unary operations,
2811 exceptional types, or bare decls/constants, get
2812 handled directly by get_constraint_for. */
2813 case tcc_reference:
2814 case tcc_declaration:
2815 case tcc_constant:
2816 case tcc_exceptional:
2817 case tcc_expression:
2818 case tcc_unary:
2820 tree anyoffsetrhs = rhsop;
2821 bool need_anyoffset = false;
2822 rhs = get_constraint_for (rhsop, &need_anyoffset);
2823 process_constraint (new_constraint (lhs, rhs));
2825 STRIP_NOPS (anyoffsetrhs);
2826 /* When taking the address of an aggregate
2827 type, from the LHS we can access any field
2828 of the RHS. */
2829 if (need_anyoffset || (rhs.type == ADDRESSOF
2830 && !(get_varinfo (rhs.var)->is_special_var)
2831 && AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (anyoffsetrhs)))))
2833 rhs.var = anyoffset_id;
2834 rhs.type = ADDRESSOF;
2835 rhs.offset = 0;
2836 process_constraint (new_constraint (lhs, rhs));
2839 break;
2841 case tcc_binary:
2843 /* For pointer arithmetic of the form
2844 PTR + CST, we can simply use PTR's
2845 constraint because pointer arithmetic is
2846 not allowed to go out of bounds. */
2847 if (handle_ptr_arith (lhs, rhsop))
2848 break;
2850 /* FALLTHRU */
2852 /* Otherwise, walk each operand. Notice that we
2853 can't use the operand interface because we need
2854 to process expressions other than simple operands
2855 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
2856 default:
2857 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2859 tree op = TREE_OPERAND (rhsop, i);
2860 rhs = get_constraint_for (op, NULL);
2861 process_constraint (new_constraint (lhs, rhs));
2868 /* After promoting variables and computing aliasing we will
2869 need to re-scan most statements. FIXME: Try to minimize the
2870 number of statements re-scanned. It's not really necessary to
2871 re-scan *all* statements. */
2872 mark_stmt_modified (t);
2876 /* Find the first varinfo in the same variable as START that overlaps with
2877 OFFSET.
2878 Effectively, walk the chain of fields for the variable START to find the
2879 first field that overlaps with OFFSET.
2880 Return NULL if we can't find one. */
2882 static varinfo_t
2883 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2885 varinfo_t curr = start;
2886 while (curr)
2888 /* We may not find a variable in the field list with the actual
2889 offset when when we have glommed a structure to a variable.
2890 In that case, however, offset should still be within the size
2891 of the variable. */
2892 if (offset >= curr->offset && offset < (curr->offset + curr->size))
2893 return curr;
2894 curr = curr->next;
2896 return NULL;
2900 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2901 offset. */
2903 static void
2904 insert_into_field_list (varinfo_t base, varinfo_t field)
2906 varinfo_t prev = base;
2907 varinfo_t curr = base->next;
2909 if (curr == NULL)
2911 prev->next = field;
2912 field->next = NULL;
2914 else
2916 while (curr)
2918 if (field->offset <= curr->offset)
2919 break;
2920 prev = curr;
2921 curr = curr->next;
2923 field->next = prev->next;
2924 prev->next = field;
2928 /* qsort comparison function for two fieldoff's PA and PB */
2930 static int
2931 fieldoff_compare (const void *pa, const void *pb)
2933 const fieldoff_s *foa = (const fieldoff_s *)pa;
2934 const fieldoff_s *fob = (const fieldoff_s *)pb;
2935 HOST_WIDE_INT foasize, fobsize;
2937 if (foa->offset != fob->offset)
2938 return foa->offset - fob->offset;
2940 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2941 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2942 return foasize - fobsize;
2945 /* Sort a fieldstack according to the field offset and sizes. */
2946 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2948 qsort (VEC_address (fieldoff_s, fieldstack),
2949 VEC_length (fieldoff_s, fieldstack),
2950 sizeof (fieldoff_s),
2951 fieldoff_compare);
2954 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2955 of TYPE onto fieldstack, recording their offsets along the way.
2956 OFFSET is used to keep track of the offset in this entire structure, rather
2957 than just the immediately containing structure. Returns the number
2958 of fields pushed.
2959 HAS_UNION is set to true if we find a union type as a field of
2960 TYPE. */
2963 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
2964 HOST_WIDE_INT offset, bool *has_union)
2966 tree field;
2967 int count = 0;
2969 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2970 if (TREE_CODE (field) == FIELD_DECL)
2972 bool push = false;
2973 int pushed = 0;
2975 if (has_union
2976 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2977 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2978 *has_union = true;
2980 if (!var_can_have_subvars (field))
2981 push = true;
2982 else if (!(pushed = push_fields_onto_fieldstack
2983 (TREE_TYPE (field), fieldstack,
2984 offset + bitpos_of_field (field), has_union))
2985 && DECL_SIZE (field)
2986 && !integer_zerop (DECL_SIZE (field)))
2987 /* Empty structures may have actual size, like in C++. So
2988 see if we didn't push any subfields and the size is
2989 nonzero, push the field onto the stack */
2990 push = true;
2992 if (push)
2994 fieldoff_s *pair;
2996 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
2997 pair->field = field;
2998 pair->offset = offset + bitpos_of_field (field);
2999 count++;
3001 else
3002 count += pushed;
3005 return count;
3008 static void
3009 make_constraint_to_anything (varinfo_t vi)
3011 struct constraint_expr lhs, rhs;
3013 lhs.var = vi->id;
3014 lhs.offset = 0;
3015 lhs.type = SCALAR;
3017 rhs.var = anything_id;
3018 rhs.offset =0 ;
3019 rhs.type = ADDRESSOF;
3020 process_constraint (new_constraint (lhs, rhs));
3024 /* Return true if FIELDSTACK contains fields that overlap.
3025 FIELDSTACK is assumed to be sorted by offset. */
3027 static bool
3028 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3030 fieldoff_s *fo = NULL;
3031 unsigned int i;
3032 HOST_WIDE_INT lastoffset = -1;
3034 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3036 if (fo->offset == lastoffset)
3037 return true;
3038 lastoffset = fo->offset;
3040 return false;
3043 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3044 This will also create any varinfo structures necessary for fields
3045 of DECL. */
3047 static unsigned int
3048 create_variable_info_for (tree decl, const char *name)
3050 unsigned int index = VEC_length (varinfo_t, varmap);
3051 varinfo_t vi;
3052 tree decltype = TREE_TYPE (decl);
3053 bool notokay = false;
3054 bool hasunion;
3055 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
3056 VEC (fieldoff_s,heap) *fieldstack = NULL;
3059 hasunion = TREE_CODE (decltype) == UNION_TYPE
3060 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3061 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3063 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3064 if (hasunion)
3066 VEC_free (fieldoff_s, heap, fieldstack);
3067 notokay = true;
3072 /* If the variable doesn't have subvars, we may end up needing to
3073 sort the field list and create fake variables for all the
3074 fields. */
3075 vi = new_var_info (decl, index, name, index);
3076 vi->decl = decl;
3077 vi->offset = 0;
3078 vi->has_union = hasunion;
3079 if (!TYPE_SIZE (decltype)
3080 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
3081 || TREE_CODE (decltype) == ARRAY_TYPE
3082 || TREE_CODE (decltype) == UNION_TYPE
3083 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3085 vi->is_unknown_size_var = true;
3086 vi->fullsize = ~0;
3087 vi->size = ~0;
3089 else
3091 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
3092 vi->size = vi->fullsize;
3095 insert_id_for_tree (vi->decl, index);
3096 VEC_safe_push (varinfo_t, heap, varmap, vi);
3097 if (is_global)
3098 make_constraint_to_anything (vi);
3100 stats.total_vars++;
3101 if (use_field_sensitive
3102 && !notokay
3103 && !vi->is_unknown_size_var
3104 && var_can_have_subvars (decl))
3106 unsigned int newindex = VEC_length (varinfo_t, varmap);
3107 fieldoff_s *fo = NULL;
3108 unsigned int i;
3109 tree field;
3111 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3113 if (!DECL_SIZE (fo->field)
3114 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
3115 || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
3116 || fo->offset < 0)
3118 notokay = true;
3119 break;
3123 /* We can't sort them if we have a field with a variable sized type,
3124 which will make notokay = true. In that case, we are going to return
3125 without creating varinfos for the fields anyway, so sorting them is a
3126 waste to boot. */
3127 if (!notokay)
3129 sort_fieldstack (fieldstack);
3130 /* Due to some C++ FE issues, like PR 22488, we might end up
3131 what appear to be overlapping fields even though they,
3132 in reality, do not overlap. Until the C++ FE is fixed,
3133 we will simply disable field-sensitivity for these cases. */
3134 notokay = check_for_overlaps (fieldstack);
3138 if (VEC_length (fieldoff_s, fieldstack) != 0)
3139 fo = VEC_index (fieldoff_s, fieldstack, 0);
3141 if (fo == NULL || notokay)
3143 vi->is_unknown_size_var = 1;
3144 vi->fullsize = ~0;
3145 vi->size = ~0;
3146 VEC_free (fieldoff_s, heap, fieldstack);
3147 return index;
3150 field = fo->field;
3151 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3152 vi->offset = fo->offset;
3153 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3155 varinfo_t newvi;
3156 const char *newname;
3157 char *tempname;
3159 field = fo->field;
3160 newindex = VEC_length (varinfo_t, varmap);
3161 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
3162 newname = ggc_strdup (tempname);
3163 free (tempname);
3164 newvi = new_var_info (decl, newindex, newname, newindex);
3165 newvi->offset = fo->offset;
3166 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3167 newvi->fullsize = vi->fullsize;
3168 insert_into_field_list (vi, newvi);
3169 VEC_safe_push (varinfo_t, heap, varmap, newvi);
3170 if (is_global)
3171 make_constraint_to_anything (newvi);
3173 stats.total_vars++;
3175 VEC_free (fieldoff_s, heap, fieldstack);
3177 return index;
3180 /* Print out the points-to solution for VAR to FILE. */
3182 void
3183 dump_solution_for_var (FILE *file, unsigned int var)
3185 varinfo_t vi = get_varinfo (var);
3186 unsigned int i;
3187 bitmap_iterator bi;
3189 fprintf (file, "%s = { ", vi->name);
3190 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
3192 fprintf (file, "%s ", get_varinfo (i)->name);
3194 fprintf (file, "}\n");
3197 /* Print the points-to solution for VAR to stdout. */
3199 void
3200 debug_solution_for_var (unsigned int var)
3202 dump_solution_for_var (stdout, var);
3206 /* Create varinfo structures for all of the variables in the
3207 function for intraprocedural mode. */
3209 static void
3210 intra_create_variable_infos (void)
3212 tree t;
3214 /* For each incoming argument arg, ARG = &ANYTHING */
3215 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
3217 struct constraint_expr lhs;
3218 struct constraint_expr rhs;
3219 varinfo_t p;
3221 lhs.offset = 0;
3222 lhs.type = SCALAR;
3223 lhs.var = create_variable_info_for (t, alias_get_name (t));
3225 rhs.var = anything_id;
3226 rhs.type = ADDRESSOF;
3227 rhs.offset = 0;
3229 for (p = get_varinfo (lhs.var); p; p = p->next)
3231 struct constraint_expr temp = lhs;
3232 temp.var = p->id;
3233 process_constraint (new_constraint (temp, rhs));
3239 /* Set bits in INTO corresponding to the variable uids in solution set
3240 FROM */
3242 static void
3243 set_uids_in_ptset (bitmap into, bitmap from)
3245 unsigned int i;
3246 bitmap_iterator bi;
3247 bool found_anyoffset = false;
3248 subvar_t sv;
3250 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
3252 varinfo_t vi = get_varinfo (i);
3254 /* If we find ANYOFFSET in the solution and the solution
3255 includes SFTs for some structure, then all the SFTs in that
3256 structure will need to be added to the alias set. */
3257 if (vi->id == anyoffset_id)
3259 found_anyoffset = true;
3260 continue;
3263 /* The only artificial variables that are allowed in a may-alias
3264 set are heap variables. */
3265 if (vi->is_artificial_var && !vi->is_heap_var)
3266 continue;
3268 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
3270 /* Variables containing unions may need to be converted to
3271 their SFT's, because SFT's can have unions and we cannot. */
3272 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3273 bitmap_set_bit (into, DECL_UID (sv->var));
3275 else if (TREE_CODE (vi->decl) == VAR_DECL
3276 || TREE_CODE (vi->decl) == PARM_DECL)
3278 if (found_anyoffset
3279 && var_can_have_subvars (vi->decl)
3280 && get_subvars_for_var (vi->decl))
3282 /* If ANYOFFSET is in the solution set and VI->DECL is
3283 an aggregate variable with sub-variables, then any of
3284 the SFTs inside VI->DECL may have been accessed. Add
3285 all the sub-vars for VI->DECL. */
3286 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3287 bitmap_set_bit (into, DECL_UID (sv->var));
3289 else if (var_can_have_subvars (vi->decl)
3290 && get_subvars_for_var (vi->decl))
3292 /* If VI->DECL is an aggregate for which we created
3293 SFTs, add the SFT corresponding to VI->OFFSET. */
3294 tree sft = get_subvar_at (vi->decl, vi->offset);
3295 bitmap_set_bit (into, DECL_UID (sft));
3297 else
3299 /* Otherwise, just add VI->DECL to the alias set. */
3300 bitmap_set_bit (into, DECL_UID (vi->decl));
3307 static bool have_alias_info = false;
3309 /* Given a pointer variable P, fill in its points-to set, or return
3310 false if we can't. */
3312 bool
3313 find_what_p_points_to (tree p)
3315 unsigned int id = 0;
3317 if (!have_alias_info)
3318 return false;
3320 if (lookup_id_for_tree (p, &id))
3322 varinfo_t vi = get_varinfo (id);
3324 if (vi->is_artificial_var)
3325 return false;
3327 /* See if this is a field or a structure. */
3328 if (vi->size != vi->fullsize)
3330 /* Nothing currently asks about structure fields directly,
3331 but when they do, we need code here to hand back the
3332 points-to set. */
3333 if (!var_can_have_subvars (vi->decl)
3334 || get_subvars_for_var (vi->decl) == NULL)
3335 return false;
3337 else
3339 struct ptr_info_def *pi = get_ptr_info (p);
3340 unsigned int i;
3341 bitmap_iterator bi;
3343 /* This variable may have been collapsed, let's get the real
3344 variable. */
3345 vi = get_varinfo (vi->node);
3347 /* Translate artificial variables into SSA_NAME_PTR_INFO
3348 attributes. */
3349 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
3351 varinfo_t vi = get_varinfo (i);
3353 if (vi->is_artificial_var)
3355 /* FIXME. READONLY should be handled better so that
3356 flow insensitive aliasing can disregard writable
3357 aliases. */
3358 if (vi->id == nothing_id)
3359 pi->pt_null = 1;
3360 else if (vi->id == anything_id)
3361 pi->pt_anything = 1;
3362 else if (vi->id == readonly_id)
3363 pi->pt_anything = 1;
3364 else if (vi->id == integer_id)
3365 pi->pt_anything = 1;
3366 else if (vi->is_heap_var)
3367 pi->pt_global_mem = 1;
3371 if (pi->pt_anything)
3372 return false;
3374 if (!pi->pt_vars)
3375 pi->pt_vars = BITMAP_GGC_ALLOC ();
3377 set_uids_in_ptset (pi->pt_vars, vi->solution);
3379 if (bitmap_empty_p (pi->pt_vars))
3380 pi->pt_vars = NULL;
3382 return true;
3386 return false;
3390 /* Initialize things necessary to perform PTA */
3392 static void
3393 init_alias_vars (void)
3395 bitmap_obstack_initialize (&ptabitmap_obstack);
3399 /* Dump points-to information to OUTFILE. */
3401 void
3402 dump_sa_points_to_info (FILE *outfile)
3404 unsigned int i;
3406 fprintf (outfile, "\nPoints-to sets\n\n");
3408 if (dump_flags & TDF_STATS)
3410 fprintf (outfile, "Stats:\n");
3411 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
3412 fprintf (outfile, "Statically unified vars: %d\n",
3413 stats.unified_vars_static);
3414 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
3415 fprintf (outfile, "Dynamically unified vars: %d\n",
3416 stats.unified_vars_dynamic);
3417 fprintf (outfile, "Iterations: %d\n", stats.iterations);
3420 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
3421 dump_solution_for_var (outfile, i);
3425 /* Debug points-to information to stderr. */
3427 void
3428 debug_sa_points_to_info (void)
3430 dump_sa_points_to_info (stderr);
3434 /* Initialize the always-existing constraint variables for NULL
3435 ANYTHING, READONLY, and INTEGER */
3437 static void
3438 init_base_vars (void)
3440 struct constraint_expr lhs, rhs;
3442 /* Create the NULL variable, used to represent that a variable points
3443 to NULL. */
3444 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
3445 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
3446 insert_id_for_tree (nothing_tree, 0);
3447 var_nothing->is_artificial_var = 1;
3448 var_nothing->offset = 0;
3449 var_nothing->size = ~0;
3450 var_nothing->fullsize = ~0;
3451 var_nothing->is_special_var = 1;
3452 nothing_id = 0;
3453 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
3455 /* Create the ANYTHING variable, used to represent that a variable
3456 points to some unknown piece of memory. */
3457 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
3458 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
3459 insert_id_for_tree (anything_tree, 1);
3460 var_anything->is_artificial_var = 1;
3461 var_anything->size = ~0;
3462 var_anything->offset = 0;
3463 var_anything->next = NULL;
3464 var_anything->fullsize = ~0;
3465 var_anything->is_special_var = 1;
3466 anything_id = 1;
3468 /* Anything points to anything. This makes deref constraints just
3469 work in the presence of linked list and other p = *p type loops,
3470 by saying that *ANYTHING = ANYTHING. */
3471 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
3472 lhs.type = SCALAR;
3473 lhs.var = anything_id;
3474 lhs.offset = 0;
3475 rhs.type = ADDRESSOF;
3476 rhs.var = anything_id;
3477 rhs.offset = 0;
3478 var_anything->address_taken = true;
3480 /* This specifically does not use process_constraint because
3481 process_constraint ignores all anything = anything constraints, since all
3482 but this one are redundant. */
3483 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
3485 /* Create the READONLY variable, used to represent that a variable
3486 points to readonly memory. */
3487 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3488 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3489 var_readonly->is_artificial_var = 1;
3490 var_readonly->offset = 0;
3491 var_readonly->size = ~0;
3492 var_readonly->fullsize = ~0;
3493 var_readonly->next = NULL;
3494 var_readonly->is_special_var = 1;
3495 insert_id_for_tree (readonly_tree, 2);
3496 readonly_id = 2;
3497 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
3499 /* readonly memory points to anything, in order to make deref
3500 easier. In reality, it points to anything the particular
3501 readonly variable can point to, but we don't track this
3502 separately. */
3503 lhs.type = SCALAR;
3504 lhs.var = readonly_id;
3505 lhs.offset = 0;
3506 rhs.type = ADDRESSOF;
3507 rhs.var = anything_id;
3508 rhs.offset = 0;
3510 process_constraint (new_constraint (lhs, rhs));
3512 /* Create the INTEGER variable, used to represent that a variable points
3513 to an INTEGER. */
3514 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3515 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3516 insert_id_for_tree (integer_tree, 3);
3517 var_integer->is_artificial_var = 1;
3518 var_integer->size = ~0;
3519 var_integer->fullsize = ~0;
3520 var_integer->offset = 0;
3521 var_integer->next = NULL;
3522 var_integer->is_special_var = 1;
3523 integer_id = 3;
3524 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
3526 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3527 integer will point to. */
3528 lhs.type = SCALAR;
3529 lhs.var = integer_id;
3530 lhs.offset = 0;
3531 rhs.type = ADDRESSOF;
3532 rhs.var = anything_id;
3533 rhs.offset = 0;
3534 process_constraint (new_constraint (lhs, rhs));
3536 /* Create the ANYOFFSET variable, used to represent an arbitrary offset
3537 inside an object. This is similar to ANYTHING, but less drastic.
3538 It means that the pointer can point anywhere inside an object,
3539 but not outside of it. */
3540 anyoffset_tree = create_tmp_var_raw (void_type_node, "ANYOFFSET");
3541 anyoffset_id = 4;
3542 var_anyoffset = new_var_info (anyoffset_tree, anyoffset_id, "ANYOFFSET",
3543 anyoffset_id);
3544 insert_id_for_tree (anyoffset_tree, anyoffset_id);
3545 var_anyoffset->is_artificial_var = 1;
3546 var_anyoffset->size = ~0;
3547 var_anyoffset->offset = 0;
3548 var_anyoffset->next = NULL;
3549 var_anyoffset->fullsize = ~0;
3550 var_anyoffset->is_special_var = 1;
3551 VEC_safe_push (varinfo_t, heap, varmap, var_anyoffset);
3553 /* ANYOFFSET points to ANYOFFSET. */
3554 lhs.type = SCALAR;
3555 lhs.var = anyoffset_id;
3556 lhs.offset = 0;
3557 rhs.type = ADDRESSOF;
3558 rhs.var = anyoffset_id;
3559 rhs.offset = 0;
3560 process_constraint (new_constraint (lhs, rhs));
3563 /* Return true if we actually need to solve the constraint graph in order to
3564 get our points-to sets. This is false when, for example, no addresses are
3565 taken other than special vars, or all points-to sets with members already
3566 contain the anything variable and there are no predecessors for other
3567 sets. */
3569 static bool
3570 need_to_solve (void)
3572 int i;
3573 varinfo_t v;
3574 bool found_address_taken = false;
3575 bool found_non_anything = false;
3577 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
3579 if (v->is_special_var)
3580 continue;
3582 if (v->address_taken)
3583 found_address_taken = true;
3585 if (v->solution
3586 && !bitmap_empty_p (v->solution)
3587 && !bitmap_bit_p (v->solution, anything_id))
3588 found_non_anything = true;
3589 else if (bitmap_empty_p (v->solution)
3590 && VEC_length (constraint_edge_t, graph->preds[v->id]) != 0)
3591 found_non_anything = true;
3593 if (found_address_taken && found_non_anything)
3594 return true;
3597 return false;
3600 /* Create points-to sets for the current function. See the comments
3601 at the start of the file for an algorithmic overview. */
3603 void
3604 compute_points_to_sets (struct alias_info *ai)
3606 basic_block bb;
3608 timevar_push (TV_TREE_PTA);
3610 init_alias_vars ();
3612 constraint_pool = create_alloc_pool ("Constraint pool",
3613 sizeof (struct constraint), 30);
3614 variable_info_pool = create_alloc_pool ("Variable info pool",
3615 sizeof (struct variable_info), 30);
3616 constraint_edge_pool = create_alloc_pool ("Constraint edges",
3617 sizeof (struct constraint_edge), 30);
3619 constraints = VEC_alloc (constraint_t, heap, 8);
3620 varmap = VEC_alloc (varinfo_t, heap, 8);
3621 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3622 memset (&stats, 0, sizeof (stats));
3624 init_base_vars ();
3626 intra_create_variable_infos ();
3628 /* Now walk all statements and derive aliases. */
3629 FOR_EACH_BB (bb)
3631 block_stmt_iterator bsi;
3632 tree phi;
3634 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3635 if (is_gimple_reg (PHI_RESULT (phi)))
3636 find_func_aliases (phi, ai);
3638 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3639 find_func_aliases (bsi_stmt (bsi), ai);
3642 build_constraint_graph ();
3644 if (dump_file)
3646 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
3647 dump_constraints (dump_file);
3650 if (need_to_solve ())
3652 if (dump_file)
3653 fprintf (dump_file, "\nCollapsing static cycles and doing variable "
3654 "substitution:\n");
3656 find_and_collapse_graph_cycles (graph, false);
3657 perform_var_substitution (graph);
3659 if (dump_file)
3660 fprintf (dump_file, "\nSolving graph:\n");
3662 solve_graph (graph);
3665 if (dump_file)
3666 dump_sa_points_to_info (dump_file);
3668 have_alias_info = true;
3670 timevar_pop (TV_TREE_PTA);
3674 /* Delete created points-to sets. */
3676 void
3677 delete_points_to_sets (void)
3679 varinfo_t v;
3680 int i;
3682 htab_delete (id_for_tree);
3683 bitmap_obstack_release (&ptabitmap_obstack);
3684 VEC_free (constraint_t, heap, constraints);
3686 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
3688 VEC_free (constraint_edge_t, heap, graph->succs[i]);
3689 VEC_free (constraint_edge_t, heap, graph->preds[i]);
3690 VEC_free (constraint_t, heap, v->complex);
3692 free (graph->succs);
3693 free (graph->preds);
3694 free (graph);
3696 VEC_free (varinfo_t, heap, varmap);
3697 free_alloc_pool (variable_info_pool);
3698 free_alloc_pool (constraint_pool);
3699 free_alloc_pool (constraint_edge_pool);
3701 have_alias_info = false;