OSDN Git Service

* tree-ssa-structalias.c: Don't include expr.h.
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-structalias.c
1 /* Tree based points-to analysis
2    Copyright (C) 2005 Free Software Foundation, Inc.
3    Contributed by Daniel Berlin <dberlin@dberlin.org>
4
5 This file is part of GCC.
6
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.
11
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.
16
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
20 */
21
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 "tree-ssa-structalias.h"
30 #include "flags.h"
31 #include "rtl.h"
32 #include "tm_p.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
35 #include "output.h"
36 #include "errors.h"
37 #include "diagnostic.h"
38 #include "tree.h"
39 #include "c-common.h"
40 #include "tree-flow.h"
41 #include "tree-inline.h"
42 #include "varray.h"
43 #include "c-tree.h"
44 #include "tree-gimple.h"
45 #include "hashtab.h"
46 #include "function.h"
47 #include "cgraph.h"
48 #include "tree-pass.h"
49 #include "timevar.h"
50 #include "alloc-pool.h"
51 #include "splay-tree.h"
52
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. 
56
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.
64
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
68
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 
72
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.  
76    
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.
83    
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.
86    
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 
91
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.
96
97    Thus, 
98    struct f
99    {
100      int a;
101      int b;
102    } foo;
103    int *bar;
104
105    looks like
106
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
110
111    
112   In order to solve the system of set constraints, the following is
113   done:
114
115   1. Each constraint variable x has a solution set associated with it,
116   Sol(x).
117   
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.
123   
124   3. All direct constraints of the form P = &Q are processed, such
125   that Q is added to Sol(P) 
126
127   4. All complex constraints for a given constraint variable are stored in a
128   linked list attached to that variable's node.  
129
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
133   
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).
137   
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.  
141
142   8. The process of walking the graph is iterated until no solution
143   sets change.
144
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.
148   
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.
152   
153   TODO: Constant bounded arrays can be handled as if they were structs of the
154   same number of elements. 
155
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.
158
159   TODO: We could handle unions, but to be honest, it's probably not
160   worth the pain or slowdown.  */
161
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);
165 static void build_constraint_graph (void);
166
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,gc);
171
172 static struct constraint_stats
173 {
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;
180
181 struct variable_info
182 {
183   /* ID of this variable  */
184   unsigned int id;
185
186   /* Name of this variable */
187   const char *name;
188
189   /* Tree that this variable is associated with.  */
190   tree decl;
191
192   /* Offset of this variable, in bits, from the base variable  */
193   unsigned HOST_WIDE_INT offset;  
194
195   /* Size of the variable, in bits.  */
196   unsigned HOST_WIDE_INT size;
197
198   /* Full size of the base variable, in bits.  */
199   unsigned HOST_WIDE_INT fullsize;
200
201   /* A link to the variable for the next field in this structure.  */
202   struct variable_info *next;
203
204   /* Node in the graph that represents the constraints and points-to
205      solution for the variable.  */
206   unsigned int node;
207
208   /* True if the address of this variable is taken.  Needed for
209      variable substitution.  */
210   unsigned int address_taken:1;
211
212   /* True if this variable is the target of a dereference.  Needed for
213      variable substitution.  */
214   unsigned int indirect_target:1;
215
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;
219
220   /* True for variables whose size is not known or variable.  */
221   unsigned int is_unknown_size_var:1;  
222
223   /* True for variables that have unions somewhere in them.  */
224   unsigned int has_union:1;
225
226   /* Points-to set for this variable.  */
227   bitmap solution;
228
229   /* Variable ids represented by this node.  */
230   bitmap variables;
231
232   /* Vector of complex constraints for this node.  Complex
233      constraints are those involving dereferences.  */
234   VEC(constraint_t,gc) *complex;
235 };
236 typedef struct variable_info *varinfo_t;
237
238 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
239
240 /* Pool of variable info structures.  */
241 static alloc_pool variable_info_pool;
242
243 DEF_VEC_P(varinfo_t);
244
245 DEF_VEC_ALLOC_P(varinfo_t, gc);
246
247 /* Table of variable info structures for constraint variables.  Indexed directly
248    by variable info id.  */
249 static VEC(varinfo_t,gc) *varmap;
250 #define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
251
252 /* Variable that represents the unknown pointer.  */
253 static varinfo_t var_anything;
254 static tree anything_tree;
255 static unsigned int anything_id;
256
257 /* Variable that represents the NULL pointer.  */
258 static varinfo_t var_nothing;
259 static tree nothing_tree;
260 static unsigned int nothing_id;
261
262 /* Variable that represents read only memory.  */
263 static varinfo_t var_readonly;
264 static tree readonly_tree;
265 static unsigned int readonly_id;
266
267 /* Variable that represents integers.  This is used for when people do things
268    like &0->a.b.  */
269 static varinfo_t var_integer;
270 static tree integer_tree;
271 static unsigned int integer_id;
272
273
274 /* Return a new variable info structure consisting for a variable
275    named NAME, and using constraint graph node NODE.  */
276
277 static varinfo_t
278 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
279 {
280   varinfo_t ret = pool_alloc (variable_info_pool);
281
282   ret->id = id;
283   ret->name = name;
284   ret->decl = t;
285   ret->node = node;
286   ret->address_taken = false;
287   ret->indirect_target = false;
288   ret->is_artificial_var = false;
289   ret->is_unknown_size_var = false;
290   ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
291   bitmap_clear (ret->solution);
292   ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
293   bitmap_clear (ret->variables);
294   ret->complex = NULL;
295   ret->next = NULL;
296   return ret;
297 }
298
299 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
300
301 /* An expression that appears in a constraint.  */
302
303 struct constraint_expr 
304 {
305   /* Constraint type.  */
306   constraint_expr_type type;
307
308   /* Variable we are referring to in the constraint.  */
309   unsigned int var;
310
311   /* Offset, in bits, of this constraint from the beginning of
312      variables it ends up referring to.
313
314      IOW, in a deref constraint, we would deref, get the result set,
315      then add OFFSET to each member.   */
316   unsigned HOST_WIDE_INT offset;
317 };
318
319 static struct constraint_expr do_deref (struct constraint_expr);
320
321 /* Our set constraints are made up of two constraint expressions, one
322    LHS, and one RHS.  
323
324    As described in the introduction, our set constraints each represent an
325    operation between set valued variables.
326 */
327 struct constraint
328 {
329   struct constraint_expr lhs;
330   struct constraint_expr rhs;
331 };
332
333 /* List of constraints that we use to build the constraint graph from.  */
334
335 static VEC(constraint_t,gc) *constraints;
336 static alloc_pool constraint_pool;
337
338 /* An edge in the constraint graph.  We technically have no use for
339    the src, since it will always be the same node that we are indexing
340    into the pred/succ arrays with, but it's nice for checking
341    purposes.  The edges are weighted, with a bit set in weights for
342    each edge from src to dest with that weight.  */
343
344 struct constraint_edge
345 {
346   unsigned int src;
347   unsigned int dest;
348   bitmap weights;
349 };
350
351 typedef struct constraint_edge *constraint_edge_t;
352 static alloc_pool constraint_edge_pool;
353
354 /* Return a new constraint edge from SRC to DEST.  */
355
356 static constraint_edge_t
357 new_constraint_edge (unsigned int src, unsigned int dest)
358 {
359   constraint_edge_t ret = pool_alloc (constraint_edge_pool);
360   ret->src = src;
361   ret->dest = dest;
362   ret->weights = NULL;
363   return ret;
364 }
365
366 DEF_VEC_P(constraint_edge_t);
367 DEF_VEC_ALLOC_P(constraint_edge_t,gc);
368
369
370 /* The constraint graph is simply a set of adjacency vectors, one per
371    variable. succs[x] is the vector of successors for variable x, and preds[x]
372    is the vector of predecessors for variable x. 
373    IOW, all edges are "forward" edges, which is not like our CFG.  
374    So remember that
375    preds[x]->src == x, and
376    succs[x]->src == x*/
377
378 struct constraint_graph
379 {
380   VEC(constraint_edge_t,gc) **succs;
381   VEC(constraint_edge_t,gc) **preds;
382 };
383
384 typedef struct constraint_graph *constraint_graph_t;
385
386 static constraint_graph_t graph;
387
388 /* Create a new constraint consisting of LHS and RHS expressions.  */
389
390 static constraint_t 
391 new_constraint (const struct constraint_expr lhs,
392                 const struct constraint_expr rhs)
393 {
394   constraint_t ret = pool_alloc (constraint_pool);
395   ret->lhs = lhs;
396   ret->rhs = rhs;
397   return ret;
398 }
399
400 /* Print out constraint C to FILE.  */
401
402 void
403 dump_constraint (FILE *file, constraint_t c)
404 {
405   if (c->lhs.type == ADDRESSOF)
406     fprintf (file, "&");
407   else if (c->lhs.type == DEREF)
408     fprintf (file, "*");  
409   fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
410   if (c->lhs.offset != 0)
411     fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
412   fprintf (file, " = ");
413   if (c->rhs.type == ADDRESSOF)
414     fprintf (file, "&");
415   else if (c->rhs.type == DEREF)
416     fprintf (file, "*");
417   fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
418   if (c->rhs.offset != 0)
419     fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
420   fprintf (file, "\n");
421 }
422
423 /* Print out constraint C to stderr.  */
424
425 void
426 debug_constraint (constraint_t c)
427 {
428   dump_constraint (stderr, c);
429 }
430
431 /* Print out all constraints to FILE */
432
433 void
434 dump_constraints (FILE *file)
435 {
436   int i;
437   constraint_t c;
438   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
439     dump_constraint (file, c);
440 }
441
442 /* Print out all constraints to stderr.  */
443
444 void
445 debug_constraints (void)
446 {
447   dump_constraints (stderr);
448 }
449
450 /* SOLVER FUNCTIONS 
451
452    The solver is a simple worklist solver, that works on the following
453    algorithm:
454    
455    sbitmap changed_nodes = all ones;
456    changed_count = number of nodes;
457    For each node that was already collapsed:
458        changed_count--;
459
460
461    while (changed_count > 0)
462    {
463      compute topological ordering for constraint graph
464   
465      find and collapse cycles in the constraint graph (updating
466      changed if necessary)
467      
468      for each node (n) in the graph in topological order:
469        changed_count--;
470
471        Process each complex constraint associated with the node,
472        updating changed if necessary.
473
474        For each outgoing edge from n, propagate the solution from n to
475        the destination of the edge, updating changed as necessary.
476
477    }  */
478
479 /* Return true if two constraint expressions A and B are equal.  */
480
481 static bool
482 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
483 {
484   return a.type == b.type
485     && a.var == b.var
486     && a.offset == b.offset;
487 }
488
489 /* Return true if constraint expression A is less than constraint expression
490    B.  This is just arbitrary, but consistent, in order to give them an
491    ordering.  */
492
493 static bool
494 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
495 {
496   if (a.type == b.type)
497     {
498       if (a.var == b.var)
499         return a.offset < b.offset;
500       else
501         return a.var < b.var;
502     }
503   else
504     return a.type < b.type;
505 }
506
507 /* Return true if constraint A is less than constraint B.  This is just
508    arbitrary, but consistent, in order to give them an ordering.  */
509
510 static bool
511 constraint_less (const constraint_t a, const constraint_t b)
512 {
513   if (constraint_expr_less (a->lhs, b->lhs))
514     return true;
515   else if (constraint_expr_less (b->lhs, a->lhs))
516     return false;
517   else
518     return constraint_expr_less (a->rhs, b->rhs);
519 }
520
521 /* Return true if two constraints A and B are equal.  */
522   
523 static bool
524 constraint_equal (struct constraint a, struct constraint b)
525 {
526   return constraint_expr_equal (a.lhs, b.lhs) 
527     && constraint_expr_equal (a.rhs, b.rhs);
528 }
529
530
531 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
532
533 static constraint_t
534 constraint_vec_find (VEC(constraint_t,gc) *vec,
535                      struct constraint lookfor)
536 {
537   unsigned int place;  
538   constraint_t found;
539
540   if (vec == NULL)
541     return NULL;
542
543   place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
544   if (place >= VEC_length (constraint_t, vec))
545     return NULL;
546   found = VEC_index (constraint_t, vec, place);
547   if (!constraint_equal (*found, lookfor))
548     return NULL;
549   return found;
550 }
551
552 /* Union two constraint vectors, TO and FROM.  Put the result in TO.  */
553
554 static void
555 constraint_set_union (VEC(constraint_t,gc) **to,
556                       VEC(constraint_t,gc) **from)
557 {
558   int i;
559   constraint_t c;
560
561   for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
562     {
563       if (constraint_vec_find (*to, *c) == NULL)
564         {
565           unsigned int place = VEC_lower_bound (constraint_t, *to, c,
566                                                 constraint_less);
567           VEC_safe_insert (constraint_t, gc, *to, place, c);
568         }
569     }
570 }
571
572 /* Take a solution set SET, add OFFSET to each member of the set, and
573    overwrite SET with the result when done.  */
574
575 static void
576 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
577 {
578   bitmap result = BITMAP_ALLOC (&iteration_obstack);
579   unsigned int i;
580   bitmap_iterator bi;
581
582   EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
583     {
584       /* If this is a properly sized variable, only add offset if it's
585          less than end.  Otherwise, it is globbed to a single
586          variable.  */
587       
588       if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
589         {
590           unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
591           varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
592           bitmap_set_bit (result, v->id);
593         }
594       else if (get_varinfo (i)->is_artificial_var 
595                || get_varinfo (i)->is_unknown_size_var)
596         {
597           bitmap_set_bit (result, i);
598         }
599     }
600   
601   bitmap_copy (set, result);  
602   BITMAP_FREE (result);
603 }
604
605 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
606    process.  */
607
608 static bool
609 set_union_with_increment  (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
610 {
611   if (inc == 0)
612     return bitmap_ior_into (to, from);
613   else
614     {
615       bitmap tmp;
616       bool res;
617
618       tmp = BITMAP_ALLOC (&iteration_obstack);
619       bitmap_copy (tmp, from);
620       solution_set_add (tmp, inc);
621       res = bitmap_ior_into (to, tmp);
622       BITMAP_FREE (tmp);
623       return res;
624     }
625 }
626
627 /* Insert constraint C into the list of complex constraints for VAR.  */
628
629 static void
630 insert_into_complex (unsigned int var, constraint_t c)
631 {
632   varinfo_t vi = get_varinfo (var);
633   unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
634                                         constraint_less);
635   VEC_safe_insert (constraint_t, gc, vi->complex, place, c);
636 }
637
638
639 /* Compare two constraint edges A and B, return true if they are equal.  */
640
641 static bool
642 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
643 {
644   return a.src == b.src && a.dest == b.dest;
645 }
646
647 /* Compare two constraint edges, return true if A is less than B */
648
649 static bool
650 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
651 {
652   if (a->dest < b->dest)
653     return true;
654   else if (a->dest == b->dest)
655     return a->src < b->src;
656   else
657     return false;
658 }
659
660 /* Find the constraint edge that matches LOOKFOR, in VEC.
661    Return the edge, if found, NULL otherwise.  */
662
663 static constraint_edge_t 
664 constraint_edge_vec_find (VEC(constraint_edge_t,gc) *vec, 
665                           struct constraint_edge lookfor)
666 {
667   unsigned int place;  
668   constraint_edge_t edge;
669
670   place = VEC_lower_bound (constraint_edge_t, vec, &lookfor, 
671                            constraint_edge_less);
672   edge = VEC_index (constraint_edge_t, vec, place);
673   if (!constraint_edge_equal (*edge, lookfor))
674     return NULL;
675   return edge;
676 }
677
678 /* Condense two variable nodes into a single variable node, by moving
679    all associated info from SRC to TO.  */
680
681 static void 
682 condense_varmap_nodes (unsigned int to, unsigned int src)
683 {
684   varinfo_t tovi = get_varinfo (to);
685   varinfo_t srcvi = get_varinfo (src);
686   unsigned int i;
687   constraint_t c;
688   bitmap_iterator bi;
689   
690   /* the src node, and all its variables, are now the to node.  */
691   srcvi->node = to;
692   EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
693     get_varinfo (i)->node = to;
694   
695   /* Merge the src node variables and the to node variables.  */
696   bitmap_set_bit (tovi->variables, src);
697   bitmap_ior_into (tovi->variables, srcvi->variables);
698   bitmap_clear (srcvi->variables);
699   
700   /* Move all complex constraints from src node into to node  */
701   for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
702     {
703       /* In complex constraints for node src, we may have either
704          a = *src, and *src = a.  */
705       
706       if (c->rhs.type == DEREF)
707         c->rhs.var = to;
708       else
709         c->lhs.var = to;
710     }
711   constraint_set_union (&tovi->complex, &srcvi->complex);
712   srcvi->complex = NULL;
713 }
714
715 /* Erase EDGE from GRAPH.  This routine only handles self-edges
716    (e.g. an edge from a to a).  */
717
718 static void
719 erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
720 {
721   VEC(constraint_edge_t,gc) *predvec = graph->preds[edge.src];
722   VEC(constraint_edge_t,gc) *succvec = graph->succs[edge.dest];
723   unsigned int place;
724   gcc_assert (edge.src == edge.dest);
725
726   /* Remove from the successors.  */
727   place = VEC_lower_bound (constraint_edge_t, succvec, &edge, 
728                            constraint_edge_less);
729   
730   /* Make sure we found the edge.  */
731 #ifdef ENABLE_CHECKING
732   {
733     constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
734     gcc_assert (constraint_edge_equal (*tmp, edge));
735   }
736 #endif
737   VEC_ordered_remove (constraint_edge_t, succvec, place);
738
739   /* Remove from the predecessors.  */
740   place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
741                            constraint_edge_less);
742
743   /* Make sure we found the edge.  */
744 #ifdef ENABLE_CHECKING
745   {
746     constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
747     gcc_assert (constraint_edge_equal (*tmp, edge));
748   }
749 #endif
750   VEC_ordered_remove (constraint_edge_t, predvec, place);
751 }
752
753 /* Remove edges involving NODE from GRAPH.  */
754
755 static void
756 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
757 {
758   VEC(constraint_edge_t,gc) *succvec = graph->succs[node];
759   VEC(constraint_edge_t,gc) *predvec = graph->preds[node];
760   constraint_edge_t c;
761   int i;
762   
763   /* Walk the successors, erase the associated preds.  */
764   for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
765     if (c->dest != node)
766       {
767         unsigned int place;
768         struct constraint_edge lookfor;
769         lookfor.src = c->dest;
770         lookfor.dest = node;
771         place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest], 
772                                  &lookfor, constraint_edge_less);
773         VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place);
774       }
775   /* Walk the preds, erase the associated succs.  */
776   for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
777     if (c->dest != node)
778       {
779         unsigned int place;
780         struct constraint_edge lookfor;
781         lookfor.src = c->dest;
782         lookfor.dest = node;
783         place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
784                                  &lookfor, constraint_edge_less);
785         VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
786       }    
787   
788   graph->preds[node] = NULL;
789   graph->succs[node] = NULL;
790 }
791
792 static bool edge_added = false;
793   
794 /* Add edge NEWE to the graph.  */
795
796 static bool
797 add_graph_edge (constraint_graph_t graph, struct constraint_edge newe)
798 {
799   unsigned int place;
800   unsigned int src = newe.src;
801   unsigned int dest = newe.dest;
802   VEC(constraint_edge_t,gc) *vec;
803
804   vec = graph->preds[src];
805   place = VEC_lower_bound (constraint_edge_t, vec, &newe, 
806                            constraint_edge_less);
807   if (place == VEC_length (constraint_edge_t, vec)
808       || VEC_index (constraint_edge_t, vec, place)->dest != dest)
809     {
810       constraint_edge_t edge = new_constraint_edge (src, dest);
811       bitmap weightbitmap;
812
813       weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
814       edge->weights = weightbitmap;
815       VEC_safe_insert (constraint_edge_t, gc, graph->preds[edge->src], 
816                        place, edge);
817       edge = new_constraint_edge (dest, src);
818       edge->weights = weightbitmap;
819       place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
820                                edge, constraint_edge_less);
821       VEC_safe_insert (constraint_edge_t, gc, graph->succs[edge->src], 
822                        place, edge);
823       edge_added = true;
824       return true;
825     }
826   else
827     return false;
828 }
829
830
831 /* Return the bitmap representing the weights of edge LOOKFOR */
832
833 static bitmap
834 get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor)
835 {
836   constraint_edge_t edge;
837   unsigned int src = lookfor.src;
838   VEC(constraint_edge_t,gc) *vec;
839   vec = graph->preds[src];
840   edge = constraint_edge_vec_find (vec, lookfor);
841   gcc_assert (edge != NULL);
842   return edge->weights;
843 }
844
845
846 /* Merge GRAPH nodes FROM and TO into node TO.  */
847
848 static void
849 merge_graph_nodes (constraint_graph_t graph, unsigned int to, 
850                    unsigned int from)
851 {
852   VEC(constraint_edge_t,gc) *succvec = graph->succs[from];
853   VEC(constraint_edge_t,gc) *predvec = graph->preds[from];
854   int i;
855   constraint_edge_t c;
856   
857   /* Merge all the predecessor edges.  */
858
859   for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
860     {
861       unsigned int d = c->dest;
862       struct constraint_edge olde;
863       struct constraint_edge newe;
864       bitmap temp;
865       bitmap weights;
866       if (c->dest == from)
867         d = to;
868       newe.src = to;
869       newe.dest = d;
870       add_graph_edge (graph, newe);
871       olde.src = from;
872       olde.dest = c->dest;
873       temp = get_graph_weights (graph, olde);
874       weights = get_graph_weights (graph, newe);
875       bitmap_ior_into (weights, temp);
876     }
877   
878   /* Merge all the successor edges.  */
879   for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
880     {
881       unsigned int d = c->dest;
882       struct constraint_edge olde;
883       struct constraint_edge newe;
884       bitmap temp;
885       bitmap weights;
886       if (c->dest == from)
887         d = to;
888       newe.src = d;
889       newe.dest = to;
890       add_graph_edge (graph, newe);
891       olde.src = c->dest;
892       olde.dest = from;
893       temp = get_graph_weights (graph, olde);
894       weights = get_graph_weights (graph, newe);
895       bitmap_ior_into (weights, temp);
896     }
897   clear_edges_for_node (graph, from);
898 }
899
900 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
901    it doesn't exist in the graph already.
902    Return false if the edge already existed, true otherwise.  */
903
904 static bool
905 int_add_graph_edge (constraint_graph_t graph, unsigned int to, 
906                     unsigned int from, unsigned HOST_WIDE_INT weight)
907 {
908   if (to == from && weight == 0)
909     {
910       return false;
911     }
912   else
913     {
914       bool r;
915       struct constraint_edge edge;
916       edge.src = to;
917       edge.dest = from;
918       r = add_graph_edge (graph, edge);
919       r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight);
920       bitmap_set_bit (get_graph_weights (graph, edge), weight);
921       return r;
922     }
923 }
924
925
926 /* Return true if LOOKFOR is an existing graph edge.  */
927
928 static bool
929 valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor)
930 {
931   return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL;
932 }
933
934
935 /* Build the constraint graph.  */
936
937 static void
938 build_constraint_graph (void)
939 {
940   int i = 0;
941   constraint_t c;
942
943   graph = ggc_alloc (sizeof (struct constraint_graph));
944   graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->succs));
945   graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->preds));
946   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
947     {
948       struct constraint_expr lhs = c->lhs;
949       struct constraint_expr rhs = c->rhs;
950       if (lhs.type == DEREF)
951         {
952           /* *x = y or *x = &y (complex) */
953           if (rhs.type == ADDRESSOF || rhs.var > anything_id)
954             insert_into_complex (lhs.var, c);
955         }
956       else if (rhs.type == DEREF)
957         {
958           /* !ANYTHING = *y */
959           if (lhs.var > anything_id) 
960             insert_into_complex (rhs.var, c);
961         }
962       else if (rhs.type == ADDRESSOF)
963         {
964           /* x = &y */
965           bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var);
966         }
967       else if (rhs.var > anything_id && lhs.var > anything_id)
968         {
969           /* Ignore 0 weighted self edges, as they can't possibly contribute
970              anything */
971           if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0)
972             {
973               
974               struct constraint_edge edge;
975               edge.src = lhs.var;
976               edge.dest = rhs.var;
977               /* x = y (simple) */
978               add_graph_edge (graph, edge);
979               bitmap_set_bit (get_graph_weights (graph, edge),
980                               rhs.offset);
981             }
982           
983         }
984     }
985 }
986 /* Changed variables on the last iteration.  */
987 static unsigned int changed_count;
988 static sbitmap changed;
989
990 DEF_VEC_I(unsigned);
991 DEF_VEC_ALLOC_I(unsigned,heap);
992
993
994 /* Strongly Connected Component visitation info.  */
995
996 struct scc_info
997 {
998   sbitmap visited;
999   sbitmap in_component;
1000   int current_index;
1001   unsigned int *visited_index;
1002   VEC(unsigned,heap) *scc_stack;
1003   VEC(unsigned,heap) *unification_queue;
1004 };
1005
1006
1007 /* Recursive routine to find strongly connected components in GRAPH.
1008    SI is the SCC info to store the information in, and N is the id of current
1009    graph node we are processing.
1010    
1011    This is Tarjan's strongly connected component finding algorithm, as
1012    modified by Nuutila to keep only non-root nodes on the stack.  
1013    The algorithm can be found in "On finding the strongly connected
1014    connected components in a directed graph" by Esko Nuutila and Eljas
1015    Soisalon-Soininen, in Information Processing Letters volume 49,
1016    number 1, pages 9-14.  */
1017
1018 static void
1019 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1020 {
1021   constraint_edge_t c;
1022   int i;
1023
1024   gcc_assert (get_varinfo (n)->node == n);
1025   SET_BIT (si->visited, n);
1026   RESET_BIT (si->in_component, n);
1027   si->visited_index[n] = si->current_index ++;
1028   
1029   /* Visit all the successors.  */
1030   for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++)
1031     {
1032       /* We only want to find and collapse the zero weight edges. */
1033       if (bitmap_bit_p (c->weights, 0))
1034         {
1035           unsigned int w = c->dest;
1036           if (!TEST_BIT (si->visited, w))
1037             scc_visit (graph, si, w);
1038           if (!TEST_BIT (si->in_component, w))
1039             {
1040               unsigned int t = get_varinfo (w)->node;
1041               unsigned int nnode = get_varinfo (n)->node;
1042               if (si->visited_index[t] < si->visited_index[nnode])
1043                 get_varinfo (n)->node = t;
1044             }
1045         }
1046     }
1047   
1048   /* See if any components have been identified.  */
1049   if (get_varinfo (n)->node == n)
1050     {
1051       unsigned int t = si->visited_index[n];
1052       SET_BIT (si->in_component, n);
1053       while (VEC_length (unsigned, si->scc_stack) != 0 
1054              && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1055         {
1056           unsigned int w = VEC_pop (unsigned, si->scc_stack);
1057           get_varinfo (w)->node = n;
1058           SET_BIT (si->in_component, w);
1059           /* Mark this node for collapsing.  */
1060           VEC_safe_push (unsigned, heap, si->unification_queue, w);
1061         } 
1062     }
1063   else
1064     VEC_safe_push (unsigned, heap, si->scc_stack, n);
1065 }
1066
1067
1068 /* Collapse two variables into one variable.  */
1069
1070 static void
1071 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1072 {
1073   bitmap tosol, fromsol;
1074   struct constraint_edge edge;
1075
1076
1077   condense_varmap_nodes (to, from);
1078   tosol = get_varinfo (to)->solution;
1079   fromsol = get_varinfo (from)->solution;
1080   bitmap_ior_into (tosol, fromsol);
1081   merge_graph_nodes (graph, to, from);
1082   edge.src = to;
1083   edge.dest = to;
1084   if (valid_graph_edge (graph, edge))
1085     {
1086       bitmap weights = get_graph_weights (graph, edge);
1087       bitmap_clear_bit (weights, 0);
1088       if (bitmap_empty_p (weights))
1089         erase_graph_self_edge (graph, edge);
1090     }
1091   bitmap_clear (fromsol);
1092   get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1093   get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1094 }
1095
1096
1097 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1098    SI is the Strongly Connected Components information structure that tells us
1099    what components to unify.
1100    UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1101    count should be updated to reflect the unification.  */
1102
1103 static void
1104 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1105                            bool update_changed)
1106 {
1107   size_t i = 0;
1108   bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1109   bitmap_clear (tmp);
1110
1111   /* We proceed as follows:
1112
1113      For each component in the queue (components are delineated by
1114      when current_queue_element->node != next_queue_element->node):
1115
1116         rep = representative node for component
1117
1118         For each node (tounify) to be unified in the component,
1119            merge the solution for tounify into tmp bitmap
1120
1121            clear solution for tounify
1122
1123            merge edges from tounify into rep
1124
1125            merge complex constraints from tounify into rep
1126
1127            update changed count to note that tounify will never change
1128            again
1129
1130         Merge tmp into solution for rep, marking rep changed if this
1131         changed rep's solution.
1132         
1133         Delete any 0 weighted self-edges we now have for rep.  */
1134   while (i != VEC_length (unsigned, si->unification_queue))
1135     {
1136       unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1137       unsigned int n = get_varinfo (tounify)->node;
1138
1139       if (dump_file && (dump_flags & TDF_DETAILS))
1140         fprintf (dump_file, "Unifying %s to %s\n", 
1141                  get_varinfo (tounify)->name,
1142                  get_varinfo (n)->name);
1143       if (update_changed)
1144         stats.unified_vars_dynamic++;
1145       else
1146         stats.unified_vars_static++;
1147       bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1148       merge_graph_nodes (graph, n, tounify);
1149       condense_varmap_nodes (n, tounify);
1150       
1151       if (update_changed && TEST_BIT (changed, tounify))
1152         {
1153           RESET_BIT (changed, tounify);
1154           if (!TEST_BIT (changed, n))
1155             SET_BIT (changed, n);
1156           else
1157             {
1158               gcc_assert (changed_count > 0);
1159               changed_count--;
1160             }
1161         }
1162
1163       bitmap_clear (get_varinfo (tounify)->solution);
1164       ++i;
1165
1166       /* If we've either finished processing the entire queue, or
1167          finished processing all nodes for component n, update the solution for
1168          n.  */
1169       if (i == VEC_length (unsigned, si->unification_queue)
1170           || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1171         {
1172           struct constraint_edge edge;
1173
1174           /* If the solution changes because of the merging, we need to mark
1175              the variable as changed.  */
1176           if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1177             {
1178               if (update_changed && !TEST_BIT (changed, n))
1179                 {
1180                   SET_BIT (changed, n);
1181                   changed_count++;
1182                 }
1183             }
1184           bitmap_clear (tmp);
1185           edge.src = n;
1186           edge.dest = n;
1187           if (valid_graph_edge (graph, edge))
1188             {
1189               bitmap weights = get_graph_weights (graph, edge);
1190               bitmap_clear_bit (weights, 0);
1191               if (bitmap_empty_p (weights))
1192                 erase_graph_self_edge (graph, edge);
1193             }
1194         }
1195     }
1196   BITMAP_FREE (tmp);
1197 }
1198
1199
1200 /* Information needed to compute the topological ordering of a graph.  */
1201
1202 struct topo_info
1203 {
1204   /* sbitmap of visited nodes.  */
1205   sbitmap visited;
1206   /* Array that stores the topological order of the graph, *in
1207      reverse*.  */
1208   VEC(unsigned,heap) *topo_order;
1209 };
1210
1211
1212 /* Initialize and return a topological info structure.  */
1213
1214 static struct topo_info *
1215 init_topo_info (void)
1216 {
1217   size_t size = VEC_length (varinfo_t, varmap);
1218   struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1219   ti->visited = sbitmap_alloc (size);
1220   sbitmap_zero (ti->visited);
1221   ti->topo_order = VEC_alloc (unsigned, heap, 1);
1222   return ti;
1223 }
1224
1225
1226 /* Free the topological sort info pointed to by TI.  */
1227
1228 static void
1229 free_topo_info (struct topo_info *ti)
1230 {
1231   sbitmap_free (ti->visited);
1232   VEC_free (unsigned, heap, ti->topo_order);
1233   free (ti);
1234 }
1235
1236 /* Visit the graph in topological order, and store the order in the
1237    topo_info structure.  */
1238
1239 static void
1240 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1241             unsigned int n)
1242 {
1243   VEC(constraint_edge_t,gc) *succs = graph->succs[n];
1244   constraint_edge_t c;
1245   int i;
1246   SET_BIT (ti->visited, n);
1247   for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1248     {
1249       if (!TEST_BIT (ti->visited, c->dest))
1250         topo_visit (graph, ti, c->dest);
1251     }
1252   VEC_safe_push (unsigned, heap, ti->topo_order, n);
1253 }
1254
1255 /* Return true if variable N + OFFSET is a legal field of N.  */
1256
1257 static bool 
1258 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1259 {
1260   varinfo_t ninfo = get_varinfo (n);
1261
1262   /* For things we've globbed to single variables, any offset into the
1263      variable acts like the entire variable, so that it becomes offset
1264      0.  */
1265   if (n == anything_id
1266       || ninfo->is_artificial_var
1267       || ninfo->is_unknown_size_var)
1268     {
1269       *offset = 0;
1270       return true;
1271     }
1272   return n > anything_id 
1273     && (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1274 }
1275
1276 /* Process a constraint C that represents *x = &y.  */
1277
1278 static void
1279 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1280                   constraint_t c, bitmap delta)
1281 {
1282   unsigned int rhs = c->rhs.var;
1283   unsigned HOST_WIDE_INT offset = c->lhs.offset;
1284   unsigned int j;
1285   bitmap_iterator bi;
1286
1287   /* For each member j of Delta (Sol(x)), add x to Sol(j)  */
1288   EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1289     {
1290       if (type_safe (j, &offset))
1291         {
1292         /* *x != NULL && *x != ANYTHING*/
1293           varinfo_t v;
1294           unsigned int t;
1295           bitmap sol;
1296           unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1297           v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1298           t = v->node;
1299           sol = get_varinfo (t)->solution;
1300           if (!bitmap_bit_p (sol, rhs))
1301             {             
1302               bitmap_set_bit (sol, rhs);
1303               if (!TEST_BIT (changed, t))
1304                 {
1305                   SET_BIT (changed, t);
1306                   changed_count++;
1307                 }
1308             }
1309         }
1310       else if (dump_file)
1311         fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1312       
1313     }
1314 }
1315
1316 /* Process a constraint C that represents x = *y, using DELTA as the
1317    starting solution.  */
1318
1319 static void
1320 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1321                   bitmap delta)
1322 {
1323   unsigned int lhs = get_varinfo (c->lhs.var)->node;
1324   unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1325   bool flag = false;
1326   bitmap sol = get_varinfo (lhs)->solution;
1327   unsigned int j;
1328   bitmap_iterator bi;
1329   
1330   /* For each variable j in delta (Sol(y)), add    
1331      an edge in the graph from j to x, and union Sol(j) into Sol(x).  */
1332   EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1333     {
1334       if (type_safe (j, &roffset))
1335         {
1336           varinfo_t v;
1337           unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1338           unsigned int t;
1339
1340           v = first_vi_for_offset (get_varinfo (j), fieldoffset);         
1341           t = v->node;
1342           if (int_add_graph_edge (graph, lhs, t, 0))
1343             flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);     
1344         }
1345       else if (dump_file)
1346         fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1347       
1348     }
1349
1350   /* If the LHS solution changed, mark the var as changed.  */
1351   if (flag)
1352     {
1353       get_varinfo (lhs)->solution = sol;
1354       if (!TEST_BIT (changed, lhs))
1355         {
1356           SET_BIT (changed, lhs);
1357           changed_count++;
1358         }
1359     }    
1360 }
1361
1362 /* Process a constraint C that represents *x = y.  */
1363
1364 static void
1365 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1366 {
1367   unsigned int rhs = get_varinfo (c->rhs.var)->node;
1368   unsigned HOST_WIDE_INT loff = c->lhs.offset;
1369   unsigned HOST_WIDE_INT roff = c->rhs.offset;
1370   bitmap sol = get_varinfo (rhs)->solution;
1371   unsigned int j;
1372   bitmap_iterator bi;
1373
1374   /* For each member j of delta (Sol(x)), add an edge from y to j and
1375      union Sol(y) into Sol(j) */
1376   EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1377     {
1378       if (type_safe (j, &loff))
1379         {
1380           varinfo_t v;
1381           unsigned int t;
1382           unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1383
1384           v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1385           t = v->node;
1386           if (int_add_graph_edge (graph, t, rhs, roff))
1387             {
1388               bitmap tmp = get_varinfo (t)->solution;
1389               if (set_union_with_increment (tmp, sol, roff))
1390                 {
1391                   get_varinfo (t)->solution = tmp;
1392                   if (t == rhs)
1393                     {
1394                       sol = get_varinfo (rhs)->solution;
1395                     }
1396                   if (!TEST_BIT (changed, t))
1397                     {
1398                       SET_BIT (changed, t);
1399                       changed_count++;
1400                     }
1401                 }
1402             }
1403         }    
1404       else if (dump_file)
1405         fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1406     }
1407 }
1408
1409 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1410    constraint (IE *x = &y, x = *y, and *x = y).  */
1411    
1412 static void
1413 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1414 {
1415   if (c->lhs.type == DEREF)
1416     {
1417       if (c->rhs.type == ADDRESSOF)
1418         {
1419           /* *x = &y */
1420           do_da_constraint (graph, c, delta);
1421         }
1422       else
1423         {
1424           /* *x = y */
1425           do_ds_constraint (graph, c, delta);
1426         }
1427     }
1428   else
1429     {
1430       /* x = *y */
1431       do_sd_constraint (graph, c, delta);
1432     }
1433 }
1434
1435 /* Initialize and return a new SCC info structure.  */
1436
1437 static struct scc_info *
1438 init_scc_info (void)
1439 {
1440   struct scc_info *si = xmalloc (sizeof (struct scc_info));
1441   size_t size = VEC_length (varinfo_t, varmap);
1442
1443   si->current_index = 0;
1444   si->visited = sbitmap_alloc (size);
1445   sbitmap_zero (si->visited);
1446   si->in_component = sbitmap_alloc (size);
1447   sbitmap_ones (si->in_component);
1448   si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1449   si->scc_stack = VEC_alloc (unsigned, heap, 1);
1450   si->unification_queue = VEC_alloc (unsigned, heap, 1);
1451   return si;
1452 }
1453
1454 /* Free an SCC info structure pointed to by SI */
1455
1456 static void
1457 free_scc_info (struct scc_info *si)
1458 {  
1459   sbitmap_free (si->visited);
1460   sbitmap_free (si->in_component);
1461   free (si->visited_index);
1462   VEC_free (unsigned, heap, si->scc_stack);
1463   VEC_free (unsigned, heap, si->unification_queue);
1464   free(si); 
1465 }
1466
1467
1468 /* Find cycles in GRAPH that occur, using strongly connected components, and
1469    collapse the cycles into a single representative node.  if UPDATE_CHANGED
1470    is true, then update the changed sbitmap to note those nodes whose
1471    solutions have changed as a result of collapsing.  */
1472
1473 static void
1474 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1475 {
1476   unsigned int i;
1477   unsigned int size = VEC_length (varinfo_t, varmap);
1478   struct scc_info *si = init_scc_info ();
1479
1480   for (i = 0; i != size; ++i)
1481     if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1482       scc_visit (graph, si, i);
1483   process_unification_queue (graph, si, update_changed);
1484   free_scc_info (si);
1485 }
1486
1487 /* Compute a topological ordering for GRAPH, and store the result in the
1488    topo_info structure TI.  */
1489
1490 static void 
1491 compute_topo_order (constraint_graph_t graph,
1492                     struct topo_info *ti)
1493 {
1494   unsigned int i;
1495   unsigned int size = VEC_length (varinfo_t, varmap);
1496   
1497   for (i = 0; i != size; ++i)
1498     if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1499       topo_visit (graph, ti, i);
1500 }
1501
1502 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1503
1504 static bool
1505 bitmap_other_than_zero_bit_set (bitmap b)
1506 {
1507   unsigned int i;
1508   bitmap_iterator bi;
1509
1510   if (bitmap_empty_p (b))
1511     return false;
1512   EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1513     return true;
1514   return false;
1515 }
1516
1517 /* Perform offline variable substitution.
1518    
1519    This is a linear time way of identifying variables that must have
1520    equivalent points-to sets, including those caused by static cycles,
1521    and single entry subgraphs, in the constraint graph.
1522
1523    The technique is described in "Off-line variable substitution for
1524    scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1525    in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56.  */
1526
1527 static void
1528 perform_var_substitution (constraint_graph_t graph)
1529 {
1530   struct topo_info *ti = init_topo_info ();
1531  
1532   /* Compute the topological ordering of the graph, then visit each
1533      node in topological order.  */
1534   compute_topo_order (graph, ti);
1535  
1536   while (VEC_length (unsigned, ti->topo_order) != 0)
1537     {
1538       unsigned int i = VEC_pop (unsigned, ti->topo_order);
1539       unsigned int pred;
1540       varinfo_t vi = get_varinfo (i);
1541       bool okay_to_elim = false;
1542       unsigned int root = VEC_length (varinfo_t, varmap);
1543       VEC(constraint_edge_t,gc) *predvec = graph->preds[i];
1544       constraint_edge_t ce;
1545       bitmap tmp;
1546
1547       /* We can't eliminate things whose address is taken, or which is
1548          the target of a dereference.  */
1549       if (vi->address_taken || vi->indirect_target)
1550         continue;
1551
1552       /* See if all predecessors of I are ripe for elimination */
1553       for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++)
1554         {
1555           bitmap weight;
1556           unsigned int w;
1557           weight = get_graph_weights (graph, *ce);
1558         
1559           /* We can't eliminate variables that have non-zero weighted
1560              edges between them.  */
1561           if (bitmap_other_than_zero_bit_set (weight))
1562             {
1563               okay_to_elim = false;
1564               break;
1565             }
1566           w = get_varinfo (ce->dest)->node;
1567
1568           /* We can't eliminate the node if one of the predecessors is
1569              part of a different strongly connected component.  */
1570           if (!okay_to_elim)
1571             {
1572               root = w;
1573               okay_to_elim = true;
1574             }
1575           else if (w != root)
1576             {
1577               okay_to_elim = false;
1578               break;
1579             }
1580
1581           /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1582              then Solution(i) is a subset of Solution (w), where w is a
1583              predecessor in the graph.  
1584              Corollary: If all predecessors of i have the same
1585              points-to set, then i has that same points-to set as
1586              those predecessors.  */
1587           tmp = BITMAP_ALLOC (NULL);
1588           bitmap_and_compl (tmp, get_varinfo (i)->solution,
1589                             get_varinfo (w)->solution);
1590           if (!bitmap_empty_p (tmp))
1591             {
1592               okay_to_elim = false;
1593               BITMAP_FREE (tmp);
1594               break;
1595             }
1596           BITMAP_FREE (tmp);
1597         }
1598
1599       /* See if the root is different than the original node. 
1600          If so, we've found an equivalence.  */
1601       if (root != get_varinfo (i)->node && okay_to_elim)
1602         {
1603           /* Found an equivalence */
1604           get_varinfo (i)->node = root;
1605           collapse_nodes (graph, root, i);
1606           if (dump_file && (dump_flags & TDF_DETAILS))
1607             fprintf (dump_file, "Collapsing %s into %s\n",
1608                      get_varinfo (i)->name,
1609                      get_varinfo (root)->name);
1610           stats.collapsed_vars++;
1611         }
1612     }
1613
1614   free_topo_info (ti);
1615 }
1616
1617
1618 /* Solve the constraint graph GRAPH using our worklist solver.
1619    This is based on the PW* family of solvers from the "Efficient Field
1620    Sensitive Pointer Analysis for C" paper.
1621    It works by iterating over all the graph nodes, processing the complex
1622    constraints and propagating the copy constraints, until everything stops
1623    changed.  This corresponds to steps 6-8 in the solving list given above.  */
1624
1625 static void
1626 solve_graph (constraint_graph_t graph)
1627 {
1628   unsigned int size = VEC_length (varinfo_t, varmap);
1629   unsigned int i;
1630
1631   changed_count = size;
1632   changed = sbitmap_alloc (size);
1633   sbitmap_ones (changed);
1634   
1635   /* The already collapsed/unreachable nodes will never change, so we
1636      need to  account for them in changed_count.  */
1637   for (i = 0; i < size; i++)
1638     if (get_varinfo (i)->node != i)
1639       changed_count--;
1640   
1641   while (changed_count > 0)
1642     {
1643       unsigned int i;
1644       struct topo_info *ti = init_topo_info ();
1645       stats.iterations++;
1646       
1647       bitmap_obstack_initialize (&iteration_obstack);
1648       
1649       if (edge_added)
1650         {
1651           /* We already did cycle elimination once, when we did
1652              variable substitution, so we don't need it again for the
1653              first iteration.  */
1654           if (stats.iterations > 1)
1655             find_and_collapse_graph_cycles (graph, true);
1656           
1657           edge_added = false;
1658         }
1659
1660       compute_topo_order (graph, ti);
1661
1662       while (VEC_length (unsigned, ti->topo_order) != 0)
1663         {
1664           i = VEC_pop (unsigned, ti->topo_order);
1665           gcc_assert (get_varinfo (i)->node == i);
1666
1667           /* If the node has changed, we need to process the
1668              complex constraints and outgoing edges again.  */
1669           if (TEST_BIT (changed, i))
1670             {
1671               unsigned int j;
1672               constraint_t c;
1673               constraint_edge_t e;
1674               bitmap solution;
1675               VEC(constraint_t,gc) *complex = get_varinfo (i)->complex;
1676               VEC(constraint_edge_t,gc) *succs;
1677
1678               RESET_BIT (changed, i);
1679               changed_count--;
1680
1681               /* Process the complex constraints */
1682               solution = get_varinfo (i)->solution;
1683               for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1684                 do_complex_constraint (graph, c, solution);
1685
1686               /* Propagate solution to all successors.  */
1687               succs = graph->succs[i];
1688               for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
1689                 {
1690                   bitmap tmp = get_varinfo (e->dest)->solution;
1691                   bool flag = false;
1692                   unsigned int k;
1693                   bitmap weights = e->weights;
1694                   bitmap_iterator bi;
1695
1696                   gcc_assert (!bitmap_empty_p (weights));
1697                   EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
1698                     flag |= set_union_with_increment (tmp, solution, k);
1699
1700                   if (flag)
1701                     {
1702                       get_varinfo (e->dest)->solution = tmp;                
1703                       if (!TEST_BIT (changed, e->dest))
1704                         {
1705                           SET_BIT (changed, e->dest);
1706                           changed_count++;
1707                         }
1708                     }
1709                 }
1710             }
1711         }
1712       free_topo_info (ti);
1713       bitmap_obstack_release (&iteration_obstack);
1714     }
1715
1716   sbitmap_free (changed);
1717 }
1718
1719
1720 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1721
1722 /* Map from trees to variable ids.  */    
1723 static htab_t id_for_tree;
1724
1725 typedef struct tree_id
1726 {
1727   tree t;
1728   unsigned int id;
1729 } *tree_id_t;
1730
1731 /* Hash a tree id structure.  */
1732
1733 static hashval_t 
1734 tree_id_hash (const void *p)
1735 {
1736   const tree_id_t ta = (tree_id_t) p;
1737   return htab_hash_pointer (ta->t);
1738 }
1739
1740 /* Return true if the tree in P1 and the tree in P2 are the same.  */
1741
1742 static int
1743 tree_id_eq (const void *p1, const void *p2)
1744 {
1745   const tree_id_t ta1 = (tree_id_t) p1;
1746   const tree_id_t ta2 = (tree_id_t) p2;
1747   return ta1->t == ta2->t;
1748 }
1749
1750 /* Insert ID as the variable id for tree T in the hashtable.  */
1751
1752 static void 
1753 insert_id_for_tree (tree t, int id)
1754 {
1755   void **slot;
1756   struct tree_id finder;
1757   tree_id_t new_pair;
1758   
1759   finder.t = t;
1760   slot = htab_find_slot (id_for_tree, &finder, INSERT);
1761   gcc_assert (*slot == NULL);
1762   new_pair = xmalloc (sizeof (struct tree_id));
1763   new_pair->t = t;
1764   new_pair->id = id;
1765   *slot = (void *)new_pair;
1766 }
1767
1768 /* Find the variable id for tree T in ID_FOR_TREE.  If T does not
1769    exist in the hash table, return false, otherwise, return true and
1770    set *ID to the id we found.  */
1771
1772 static bool
1773 lookup_id_for_tree (tree t, unsigned int *id)
1774 {
1775   tree_id_t pair;
1776   struct tree_id finder;
1777
1778   finder.t = t;
1779   pair = htab_find (id_for_tree,  &finder);
1780   if (pair == NULL)
1781     return false;
1782   *id = pair->id;
1783   return true;
1784 }
1785
1786 /* Return a printable name for DECL  */
1787
1788 static const char *
1789 alias_get_name (tree decl)
1790 {
1791   const char *res = get_name (decl);
1792   char *temp;
1793   int num_printed = 0;
1794
1795   if (res != NULL)
1796     return res;
1797
1798   res = "NULL";
1799   if (TREE_CODE (decl) == SSA_NAME)
1800     {
1801       num_printed = asprintf (&temp, "%s_%u", 
1802                               alias_get_name (SSA_NAME_VAR (decl)),
1803                               SSA_NAME_VERSION (decl));
1804     }
1805   else if (DECL_P (decl))
1806     {
1807       num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1808     }
1809   if (num_printed > 0)
1810     {
1811       res = ggc_strdup (temp);
1812       free (temp);
1813     }
1814   return res;
1815 }
1816
1817 /* Find the variable id for tree T in the hashtable.
1818    If T doesn't exist in the hash table, create an entry for it.  */
1819
1820 static unsigned int
1821 get_id_for_tree (tree t)
1822 {
1823   tree_id_t pair;
1824   struct tree_id finder;
1825
1826   finder.t = t;
1827   pair = htab_find (id_for_tree,  &finder);
1828   if (pair == NULL)
1829     return create_variable_info_for (t, alias_get_name (t));
1830   
1831   return pair->id;
1832 }
1833
1834 /* Get a constraint expression from an SSA_VAR_P node.  */
1835
1836 static struct constraint_expr
1837 get_constraint_exp_from_ssa_var (tree t)
1838 {
1839   struct constraint_expr cexpr;
1840
1841   gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1842
1843   /* For parameters, get at the points-to set for the actual parm
1844      decl.  */
1845   if (TREE_CODE (t) == SSA_NAME 
1846       && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL 
1847       && default_def (SSA_NAME_VAR (t)) == t)
1848     return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1849
1850   cexpr.type = SCALAR;
1851   
1852   if (TREE_READONLY (t))
1853     {
1854       cexpr.type = ADDRESSOF;
1855       cexpr.var = readonly_id;
1856     }
1857   else
1858     cexpr.var = get_id_for_tree (t);    
1859     
1860   cexpr.offset = 0;
1861   return cexpr;
1862 }
1863
1864 /* Process a completed constraint T, and add it to the constraint
1865    list.  */
1866
1867 static void
1868 process_constraint (constraint_t t)
1869 {
1870   struct constraint_expr rhs = t->rhs;
1871   struct constraint_expr lhs = t->lhs;
1872   
1873   gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1874   gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1875
1876   /* ANYTHING == ANYTHING is pointless.  */
1877   if (lhs.var == anything_id && rhs.var == anything_id)
1878     return;
1879
1880   /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1881   else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
1882     {
1883       rhs = t->lhs;
1884       t->lhs = t->rhs;
1885       t->rhs = rhs;
1886       process_constraint (t);
1887     }   
1888   /* This can happen in our IR with things like n->a = *p */
1889   else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1890     {
1891       /* Split into tmp = *rhs, *lhs = tmp */
1892       tree rhsdecl = get_varinfo (rhs.var)->decl;
1893       tree pointertype = TREE_TYPE (rhsdecl);
1894       tree pointedtotype = TREE_TYPE (pointertype);
1895       tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1896       struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1897       
1898       /* If this is an aggregate of known size, we should have passed
1899          this off to do_structure_copy, and it should have broken it
1900          up.  */
1901       gcc_assert (!AGGREGATE_TYPE_P (pointedtotype) 
1902                   || get_varinfo (rhs.var)->is_unknown_size_var);
1903       
1904       process_constraint (new_constraint (tmplhs, rhs));
1905       process_constraint (new_constraint (lhs, tmplhs));
1906     }
1907   else if (rhs.type == ADDRESSOF)
1908     {
1909       varinfo_t vi;
1910       gcc_assert (rhs.offset == 0);
1911       
1912       for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1913         vi->address_taken = true;
1914
1915       VEC_safe_push (constraint_t, gc, constraints, t);
1916     }
1917   else
1918     {
1919       if (lhs.type != DEREF && rhs.type == DEREF)
1920         get_varinfo (lhs.var)->indirect_target = true;
1921       VEC_safe_push (constraint_t, gc, constraints, t);
1922     }
1923 }
1924
1925
1926 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1927    structure.  */
1928
1929 static unsigned HOST_WIDE_INT
1930 bitpos_of_field (const tree fdecl)
1931 {
1932
1933   if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1934       || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1935     return -1;
1936   
1937   return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8) 
1938          + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1939 }
1940
1941
1942 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1943    overlaps with a field at [FIELDPOS, FIELDSIZE] */
1944
1945 static bool
1946 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
1947                              const unsigned HOST_WIDE_INT fieldsize,
1948                              const unsigned HOST_WIDE_INT accesspos,
1949                              const unsigned HOST_WIDE_INT accesssize)
1950 {
1951   if (fieldpos == accesspos && fieldsize == accesssize)
1952     return true;
1953   if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
1954     return true;
1955   if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
1956     return true;
1957   
1958   return false;
1959 }
1960
1961 /* Given a COMPONENT_REF T, return the constraint_expr for it.  */
1962
1963 static struct constraint_expr
1964 get_constraint_for_component_ref (tree t)
1965 {
1966   struct constraint_expr result;
1967   HOST_WIDE_INT bitsize;
1968   HOST_WIDE_INT bitpos;
1969   tree offset;
1970   enum machine_mode mode;
1971   int unsignedp;
1972   int volatilep;
1973   tree forzero;
1974   
1975   result.offset = 0;
1976   result.type = SCALAR;
1977   result.var = 0;
1978
1979   /* Some people like to do cute things like take the address of
1980      &0->a.b */
1981   forzero = t;
1982   while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
1983       forzero = TREE_OPERAND (forzero, 0);
1984
1985   if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero)) 
1986     {
1987       result.offset = 0;
1988       result.var = integer_id;
1989       result.type = SCALAR;
1990       return result;
1991     }
1992  
1993   t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
1994                            &unsignedp, &volatilep, false);
1995   result = get_constraint_for (t);
1996
1997   /* This can also happen due to weird offsetof type macros.  */
1998   if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
1999     result.type = SCALAR;
2000   
2001   /* If we know where this goes, then yay. Otherwise, booo. */
2002
2003   if (offset == NULL && bitsize != -1)
2004     {
2005       result.offset = bitpos;
2006     }   
2007   else
2008     {
2009       result.var = anything_id;
2010       result.offset = 0;      
2011     }
2012
2013   if (result.type == SCALAR)
2014     {
2015       /* In languages like C, you can access one past the end of an
2016          array.  You aren't allowed to dereference it, so we can
2017          ignore this constraint. When we handle pointer subtraction,
2018          we may have to do something cute here.  */
2019       
2020       if (result.offset < get_varinfo (result.var)->fullsize)   
2021         {
2022           /* It's also not true that the constraint will actually start at the
2023              right offset, it may start in some padding.  We only care about
2024              setting the constraint to the first actual field it touches, so
2025              walk to find it.  */ 
2026           varinfo_t curr;
2027           for (curr = get_varinfo (result.var); curr; curr = curr->next)
2028             {
2029               if (offset_overlaps_with_access (curr->offset, curr->size,
2030                                                result.offset, bitsize))
2031                 {
2032                   result.var = curr->id;
2033                   break;
2034
2035                 }
2036             }
2037           /* assert that we found *some* field there. The user couldn't be
2038              accessing *only* padding.  */
2039              
2040           gcc_assert (curr);
2041         }
2042       else
2043         if (dump_file && (dump_flags & TDF_DETAILS))
2044           fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2045
2046       result.offset = 0;
2047     }
2048   
2049   return result;
2050 }
2051
2052
2053 /* Dereference the constraint expression CONS, and return the result.
2054    DEREF (ADDRESSOF) = SCALAR
2055    DEREF (SCALAR) = DEREF
2056    DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2057    This is needed so that we can handle dereferencing DEREF constraints.  */
2058
2059 static struct constraint_expr
2060 do_deref (struct constraint_expr cons)
2061 {
2062   if (cons.type == SCALAR)
2063     {
2064       cons.type = DEREF;
2065       return cons;
2066     }
2067   else if (cons.type == ADDRESSOF)
2068     {
2069       cons.type = SCALAR;
2070       return cons;
2071     }
2072   else if (cons.type == DEREF)
2073     {
2074       tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2075       struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2076       process_constraint (new_constraint (tmplhs, cons));
2077       cons.var = tmplhs.var;
2078       return cons;
2079     }
2080   gcc_unreachable ();
2081 }
2082
2083
2084 /* Given a tree T, return the constraint expression for it.  */
2085
2086 static struct constraint_expr
2087 get_constraint_for (tree t)
2088 {
2089   struct constraint_expr temp;
2090
2091   /* x = integer is all glommed to a single variable, which doesn't
2092      point to anything by itself.  That is, of course, unless it is an
2093      integer constant being treated as a pointer, in which case, we
2094      will return that this is really the addressof anything.  This
2095      happens below, since it will fall into the default case. The only
2096      case we know something about an integer treated like a pointer is
2097      when it is the NULL pointer, and then we just say it points to
2098      NULL.  */
2099   if (TREE_CODE (t) == INTEGER_CST
2100       && !POINTER_TYPE_P (TREE_TYPE (t)))
2101     {
2102       temp.var = integer_id;
2103       temp.type = SCALAR;
2104       temp.offset = 0;
2105       return temp;
2106     }
2107   else if (TREE_CODE (t) == INTEGER_CST
2108            && integer_zerop (t))
2109     {
2110       temp.var = nothing_id;
2111       temp.type = ADDRESSOF;
2112       temp.offset = 0;
2113       return temp;
2114     }
2115
2116   switch (TREE_CODE_CLASS (TREE_CODE (t)))
2117     {
2118     case tcc_expression:
2119       {
2120         switch (TREE_CODE (t))
2121           {
2122           case ADDR_EXPR:
2123             {
2124               temp = get_constraint_for (TREE_OPERAND (t, 0));
2125                if (temp.type == DEREF)
2126                  temp.type = SCALAR;
2127                else
2128                  temp.type = ADDRESSOF;
2129               return temp;
2130             }
2131             break;
2132           case CALL_EXPR:
2133             
2134             /* XXX: In interprocedural mode, if we didn't have the
2135                body, we would need to do *each pointer argument =
2136                &ANYTHING added.  */
2137             if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2138               {
2139                 tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2140                 temp.var = create_variable_info_for (heapvar,
2141                                                      alias_get_name (heapvar));
2142                 
2143                 get_varinfo (temp.var)->is_artificial_var = 1;
2144                 temp.type = ADDRESSOF;
2145                 temp.offset = 0;
2146                 return temp;
2147               }
2148             /* FALLTHRU */
2149           default:
2150             {
2151               temp.type = ADDRESSOF;
2152               temp.var = anything_id;
2153               temp.offset = 0;
2154               return temp;
2155             }
2156           }
2157       }
2158     case tcc_reference:
2159       {
2160         switch (TREE_CODE (t))
2161           {
2162           case INDIRECT_REF:
2163             {
2164               temp = get_constraint_for (TREE_OPERAND (t, 0));
2165               temp = do_deref (temp);
2166               return temp;
2167             }
2168           case ARRAY_REF:
2169           case COMPONENT_REF:
2170             temp = get_constraint_for_component_ref (t);
2171             return temp;
2172           default:
2173             {
2174               temp.type = ADDRESSOF;
2175               temp.var = anything_id;
2176               temp.offset = 0;
2177               return temp;
2178             }
2179           }
2180       }
2181     case tcc_unary:
2182       {
2183         switch (TREE_CODE (t))
2184           {
2185           case NOP_EXPR:
2186           case CONVERT_EXPR:
2187           case NON_LVALUE_EXPR:
2188             {
2189               tree op = TREE_OPERAND (t, 0);
2190               
2191               /* Cast from non-pointer to pointers are bad news for us.
2192                  Anything else, we see through */
2193               if (!(POINTER_TYPE_P (TREE_TYPE (t))  &&
2194                     ! POINTER_TYPE_P (TREE_TYPE (op))))
2195                 return get_constraint_for (op);
2196             }
2197           default:
2198             {
2199               temp.type = ADDRESSOF;
2200               temp.var = anything_id;
2201               temp.offset = 0;
2202               return temp;
2203             }
2204           }
2205       }
2206     case tcc_exceptional:
2207       {
2208         switch (TREE_CODE (t))
2209           {
2210           case PHI_NODE:           
2211             return get_constraint_for (PHI_RESULT (t));
2212           case SSA_NAME:
2213             return get_constraint_exp_from_ssa_var (t);
2214           default:
2215             {
2216               temp.type = ADDRESSOF;
2217               temp.var = anything_id;
2218               temp.offset = 0;
2219               return temp;
2220             }
2221           }
2222       }
2223     case tcc_declaration:
2224       return get_constraint_exp_from_ssa_var (t);
2225     default:
2226       {
2227         temp.type = ADDRESSOF;
2228         temp.var = anything_id;
2229         temp.offset = 0;
2230         return temp;
2231       }
2232     }
2233 }
2234
2235
2236 /* Handle the structure copy case where we have a simple structure copy
2237    between LHS and RHS that is of SIZE (in bits) 
2238   
2239    For each field of the lhs variable (lhsfield)
2240      For each field of the rhs variable at lhsfield.offset (rhsfield)
2241        add the constraint lhsfield = rhsfield
2242 */
2243
2244 static void
2245 do_simple_structure_copy (const struct constraint_expr lhs,
2246                           const struct constraint_expr rhs,
2247                           const unsigned HOST_WIDE_INT size)
2248 {
2249   varinfo_t p = get_varinfo (lhs.var);
2250   unsigned HOST_WIDE_INT pstart, last;
2251   pstart = p->offset;
2252   last = p->offset + size;
2253   for (; p && p->offset < last; p = p->next)
2254     {
2255       varinfo_t q;
2256       struct constraint_expr templhs = lhs;
2257       struct constraint_expr temprhs = rhs;
2258       unsigned HOST_WIDE_INT fieldoffset;
2259
2260       templhs.var = p->id;            
2261       q = get_varinfo (temprhs.var);
2262       fieldoffset = p->offset - pstart;
2263       q = first_vi_for_offset (q, q->offset + fieldoffset);
2264       temprhs.var = q->id;
2265       process_constraint (new_constraint (templhs, temprhs));
2266     }
2267 }
2268
2269
2270 /* Handle the structure copy case where we have a  structure copy between a
2271    aggregate on the LHS and a dereference of a pointer on the RHS
2272    that is of SIZE (in bits) 
2273   
2274    For each field of the lhs variable (lhsfield)
2275        rhs.offset = lhsfield->offset
2276        add the constraint lhsfield = rhs
2277 */
2278
2279 static void
2280 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2281                              const struct constraint_expr rhs,
2282                              const unsigned HOST_WIDE_INT size)
2283 {
2284   varinfo_t p = get_varinfo (lhs.var);
2285   unsigned HOST_WIDE_INT pstart,last;
2286   pstart = p->offset;
2287   last = p->offset + size;
2288
2289   for (; p && p->offset < last; p = p->next)
2290     {
2291       varinfo_t q;
2292       struct constraint_expr templhs = lhs;
2293       struct constraint_expr temprhs = rhs;
2294       unsigned HOST_WIDE_INT fieldoffset;
2295
2296
2297       if (templhs.type == SCALAR)
2298         templhs.var = p->id;      
2299       else
2300         templhs.offset = p->offset;
2301       
2302       q = get_varinfo (temprhs.var);
2303       fieldoffset = p->offset - pstart;      
2304       temprhs.offset += fieldoffset;
2305       process_constraint (new_constraint (templhs, temprhs));
2306     }
2307 }
2308
2309 /* Handle the structure copy case where we have a structure copy
2310    between a aggregate on the RHS and a dereference of a pointer on
2311    the LHS that is of SIZE (in bits) 
2312
2313    For each field of the rhs variable (rhsfield)
2314        lhs.offset = rhsfield->offset
2315        add the constraint lhs = rhsfield
2316 */
2317
2318 static void
2319 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2320                              const struct constraint_expr rhs,
2321                              const unsigned HOST_WIDE_INT size)
2322 {
2323   varinfo_t p = get_varinfo (rhs.var);
2324   unsigned HOST_WIDE_INT pstart,last;
2325   pstart = p->offset;
2326   last = p->offset + size;
2327
2328   for (; p && p->offset < last; p = p->next)
2329     {
2330       varinfo_t q;
2331       struct constraint_expr templhs = lhs;
2332       struct constraint_expr temprhs = rhs;
2333       unsigned HOST_WIDE_INT fieldoffset;
2334
2335
2336       if (temprhs.type == SCALAR)
2337         temprhs.var = p->id;      
2338       else
2339         temprhs.offset = p->offset;
2340       
2341       q = get_varinfo (templhs.var);
2342       fieldoffset = p->offset - pstart;      
2343       templhs.offset += fieldoffset;
2344       process_constraint (new_constraint (templhs, temprhs));
2345     }
2346 }
2347
2348
2349 /* Handle aggregate copies by expanding into copies of the respective
2350    fields of the structures.  */
2351
2352 static void
2353 do_structure_copy (tree lhsop, tree rhsop)
2354 {
2355   struct constraint_expr lhs, rhs, tmp;
2356   varinfo_t p;
2357   unsigned HOST_WIDE_INT lhssize;
2358   unsigned HOST_WIDE_INT rhssize;
2359
2360   lhs = get_constraint_for (lhsop);  
2361   rhs = get_constraint_for (rhsop);
2362   
2363   /* If we have special var = x, swap it around.  */
2364   if (lhs.var <= integer_id && rhs.var > integer_id)
2365     {
2366       tmp = lhs;
2367       lhs = rhs;
2368       rhs = tmp;
2369     }
2370   
2371   /*  This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2372       possible it's something we could handle.  However, most cases falling
2373       into this are dealing with transparent unions, which are slightly
2374       weird. */
2375   if (rhs.type == ADDRESSOF && rhs.var > integer_id)
2376     {
2377       rhs.type = ADDRESSOF;
2378       rhs.var = anything_id;
2379     }
2380
2381   /* If the RHS is a special var, or an addressof, set all the LHS fields to
2382      that special var.  */
2383   if (rhs.var <= integer_id)
2384     {
2385       for (p = get_varinfo (lhs.var); p; p = p->next)
2386         {
2387           struct constraint_expr templhs = lhs;
2388           struct constraint_expr temprhs = rhs;
2389           if (templhs.type == SCALAR )
2390             templhs.var = p->id;
2391           else
2392             templhs.offset += p->offset;
2393           process_constraint (new_constraint (templhs, temprhs));
2394         }
2395     }
2396   else
2397     {
2398       /* The size only really matters insofar as we don't set more or less of
2399          the variable.  If we hit an unknown size var, the size should be the
2400          whole darn thing.  */
2401       if (get_varinfo (rhs.var)->is_unknown_size_var)
2402         rhssize = ~0;
2403       else
2404         rhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (rhsop)));
2405
2406       if (get_varinfo (lhs.var)->is_unknown_size_var)
2407         lhssize = ~0;
2408       else
2409         lhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (lhsop)));
2410
2411   
2412       if (rhs.type == SCALAR && lhs.type == SCALAR)  
2413         do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2414       else if (lhs.type != DEREF && rhs.type == DEREF)
2415         do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2416       else if (lhs.type == DEREF && rhs.type != DEREF)
2417         do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2418       else
2419         {
2420           tree rhsdecl = get_varinfo (rhs.var)->decl;
2421           tree pointertype = TREE_TYPE (rhsdecl);
2422           tree pointedtotype = TREE_TYPE (pointertype);
2423           tree tmpvar;  
2424
2425           gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2426           tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2427           do_structure_copy (tmpvar, rhsop);
2428           do_structure_copy (lhsop, tmpvar);
2429         }
2430     }
2431 }
2432
2433
2434 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2435    in it.  */
2436
2437 static inline bool
2438 ref_contains_indirect_ref (tree ref)
2439 {
2440   while (handled_component_p (ref))
2441     {
2442       if (TREE_CODE (ref) == INDIRECT_REF)
2443         return true;
2444       ref = TREE_OPERAND (ref, 0);
2445     }
2446   return false;
2447 }
2448
2449
2450 /*  Tree walker that is the heart of the aliasing infrastructure.
2451     TP is a pointer to the current tree.
2452     WALK_SUBTREES specifies whether to continue traversing subtrees or
2453     not.
2454     Returns NULL_TREE when we should stop.
2455     
2456     This function is the main part of the constraint builder. It
2457     walks the trees, calling the appropriate building functions
2458     to process various statements.  */
2459
2460 static void
2461 find_func_aliases (tree t)
2462 {
2463   struct constraint_expr lhs, rhs;
2464   switch (TREE_CODE (t))
2465     {      
2466     case PHI_NODE:
2467       {
2468         int i;
2469
2470         /* Only care about pointers and structures containing
2471            pointers.  */
2472         if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2473             || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2474           {
2475             lhs = get_constraint_for (PHI_RESULT (t));
2476             for (i = 0; i < PHI_NUM_ARGS (t); i++)
2477               {
2478                 rhs = get_constraint_for (PHI_ARG_DEF (t, i));
2479                 process_constraint (new_constraint (lhs, rhs));
2480               }
2481           }
2482       }
2483       break;
2484
2485     case MODIFY_EXPR:
2486       {
2487         tree lhsop = TREE_OPERAND (t, 0);
2488         tree rhsop = TREE_OPERAND (t, 1);
2489         int i;  
2490
2491         if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) 
2492             && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2493           {
2494             do_structure_copy (lhsop, rhsop);
2495           }
2496         else
2497           {
2498             /* Only care about operations with pointers, structures
2499                containing pointers, dereferences, and call
2500                expressions.  */
2501             if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2502                 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2503                 || ref_contains_indirect_ref (lhsop)
2504                 || TREE_CODE (rhsop) == CALL_EXPR)
2505               {
2506                 lhs = get_constraint_for (lhsop);
2507                 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2508                   {
2509                     /* RHS that consist of unary operations,
2510                        exceptional types, or bare decls/constants, get
2511                        handled directly by get_constraint_for.  */ 
2512                   case tcc_reference:
2513                   case tcc_declaration:
2514                   case tcc_constant:
2515                   case tcc_exceptional:
2516                   case tcc_expression:
2517                   case tcc_unary:
2518                     {
2519                       rhs = get_constraint_for (rhsop);
2520                       process_constraint (new_constraint (lhs, rhs));
2521                     }
2522                     break;
2523
2524                     /* Otherwise, walk each operand.  */
2525                   default:
2526                     for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2527                       {
2528                         tree op = TREE_OPERAND (rhsop, i);
2529                         rhs = get_constraint_for (op);
2530                         process_constraint (new_constraint (lhs, rhs));
2531                       }
2532                   }      
2533               }
2534           }
2535       }
2536       break;
2537
2538     default:
2539       break;
2540     }
2541 }
2542
2543
2544 /* Find the first varinfo in the same variable as START that overlaps with
2545    OFFSET.
2546    Effectively, walk the chain of fields for the variable START to find the
2547    first field that overlaps with OFFSET.
2548    Abort if we can't find one.  */
2549
2550 static varinfo_t 
2551 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2552 {
2553   varinfo_t curr = start;
2554   while (curr)
2555     {
2556       /* We may not find a variable in the field list with the actual
2557          offset when when we have glommed a structure to a variable.
2558          In that case, however, offset should still be within the size
2559          of the variable. */
2560       if (offset >= curr->offset && offset < (curr->offset +  curr->size))
2561         return curr;
2562       curr = curr->next;
2563     }
2564
2565   gcc_unreachable ();
2566 }
2567
2568
2569 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2570    offset.  */
2571
2572 static void
2573 insert_into_field_list (varinfo_t base, varinfo_t field)
2574 {
2575   varinfo_t prev = base;
2576   varinfo_t curr = base->next;
2577   
2578   if (curr == NULL)
2579     {
2580       prev->next = field;
2581       field->next = NULL;
2582     }
2583   else
2584     {
2585       while (curr)
2586         {
2587           if (field->offset <= curr->offset)
2588             break;
2589           prev = curr;
2590           curr = curr->next;
2591         }
2592       field->next = prev->next;
2593       prev->next = field;
2594     }
2595 }
2596
2597 /* qsort comparison function for two fieldoff's PA and PB */
2598
2599 static int 
2600 fieldoff_compare (const void *pa, const void *pb)
2601 {
2602   const fieldoff_s *foa = (const fieldoff_s *)pa;
2603   const fieldoff_s *fob = (const fieldoff_s *)pb;
2604   HOST_WIDE_INT foasize, fobsize;
2605   
2606   if (foa->offset != fob->offset)
2607     return foa->offset - fob->offset;
2608
2609   foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2610   fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2611   return foasize - fobsize;
2612 }
2613
2614 /* Sort a fieldstack according to the field offset and sizes.  */
2615 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2616 {
2617   qsort (VEC_address (fieldoff_s, fieldstack), 
2618          VEC_length (fieldoff_s, fieldstack), 
2619          sizeof (fieldoff_s),
2620          fieldoff_compare);
2621 }
2622
2623 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2624    of TYPE onto fieldstack, recording their offsets along the way.
2625    OFFSET is used to keep track of the offset in this entire structure, rather
2626    than just the immediately containing structure.  Returns the number
2627    of fields pushed.
2628    HAS_UNION is set to true if we find a union type as a field of
2629    TYPE.  */
2630
2631 int
2632 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, 
2633                              HOST_WIDE_INT offset, bool *has_union)
2634 {
2635   tree field;
2636   int count = 0;
2637
2638   for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2639     if (TREE_CODE (field) == FIELD_DECL)
2640       {
2641         bool push = false;
2642         
2643         if (has_union 
2644             && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2645                 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2646           *has_union = true;
2647         
2648         if (!var_can_have_subvars (field))
2649           push = true;
2650         else if (!(push_fields_onto_fieldstack
2651                    (TREE_TYPE (field), fieldstack,
2652                     offset + bitpos_of_field (field), has_union))
2653                  && DECL_SIZE (field)
2654                  && !integer_zerop (DECL_SIZE (field)))
2655           /* Empty structures may have actual size, like in C++. So
2656              see if we didn't push any subfields and the size is
2657              nonzero, push the field onto the stack */
2658           push = true;
2659         
2660         if (push)
2661           {
2662             fieldoff_s *pair;
2663
2664             pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
2665             pair->field = field;
2666             pair->offset = offset + bitpos_of_field (field);
2667             count++;
2668           }
2669       }
2670
2671   return count;
2672 }
2673
2674 static void
2675 make_constraint_to_anything (varinfo_t vi)
2676 {
2677   struct constraint_expr lhs, rhs;
2678   
2679   lhs.var = vi->id;
2680   lhs.offset = 0;
2681   lhs.type = SCALAR;
2682   
2683   rhs.var = anything_id;
2684   rhs.offset =0 ;
2685   rhs.type = ADDRESSOF;
2686   process_constraint (new_constraint (lhs, rhs));
2687 }
2688
2689 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2690    This will also create any varinfo structures necessary for fields
2691    of DECL.  */
2692
2693 static unsigned int
2694 create_variable_info_for (tree decl, const char *name)
2695 {
2696   unsigned int index = VEC_length (varinfo_t, varmap);
2697   varinfo_t vi;
2698   tree decltype = TREE_TYPE (decl);
2699   bool notokay = false;
2700   bool hasunion;
2701   subvar_t svars;
2702   bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
2703   VEC (fieldoff_s,heap) *fieldstack = NULL;
2704   
2705
2706   hasunion = TREE_CODE (decltype) == UNION_TYPE || TREE_CODE (decltype) == QUAL_UNION_TYPE;
2707   if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
2708     {
2709       push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
2710       if (hasunion)
2711         {
2712           VEC_free (fieldoff_s, heap, fieldstack);
2713           notokay = true;
2714         }        
2715     }
2716
2717   /* If this variable already has subvars, just create the variables for the
2718      subvars and we are done.
2719      NOTE: This assumes things haven't generated uses of previously
2720      unused structure fields.  */
2721   if (use_field_sensitive 
2722       && !notokay 
2723       && var_can_have_subvars (decl) 
2724       && var_ann (decl)      
2725       && (svars = get_subvars_for_var (decl)))
2726     {
2727       subvar_t sv;
2728       varinfo_t base = NULL;
2729       unsigned int firstindex = index;
2730
2731       for (sv = svars; sv; sv = sv->next)
2732         {
2733           /* For debugging purposes, this will print the names of the
2734              fields as "<var>.<offset>.<size>"
2735              This is only for debugging purposes.  */
2736 #define PRINT_LONG_NAMES
2737 #ifdef PRINT_LONG_NAMES
2738           char *tempname;
2739           const char *newname;
2740
2741           asprintf (&tempname,
2742                     "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC,
2743                     alias_get_name (decl), sv->offset, sv->size);
2744           newname = ggc_strdup (tempname);
2745           free (tempname);
2746           vi = new_var_info (sv->var, index, newname, index);
2747 #else
2748           vi = new_var_info (sv->var, index, alias_get_name (sv->var), index);
2749 #endif
2750           vi->decl = sv->var;
2751           vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2752           vi->size = sv->size;
2753           vi->offset = sv->offset;
2754           if (!base)
2755             {
2756               base = vi;
2757               insert_id_for_tree (decl, index);
2758             }
2759           else
2760             {
2761               insert_into_field_list (base, vi);
2762             }
2763           insert_id_for_tree (sv->var, index);  
2764           VEC_safe_push (varinfo_t, gc, varmap, vi);
2765           if (is_global)
2766             make_constraint_to_anything (vi);
2767           index++;
2768           
2769         }
2770       return firstindex;
2771     }
2772   
2773
2774   /* If the variable doesn't have subvars, we may end up needing to
2775      sort the field list and create fake variables for all the
2776      fields.  */
2777   vi = new_var_info (decl, index, name, index);
2778   vi->decl = decl;
2779   vi->offset = 0;
2780   vi->has_union = hasunion;
2781   if (!TYPE_SIZE (decltype) 
2782       || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
2783       || TREE_CODE (decltype) == ARRAY_TYPE
2784       || TREE_CODE (decltype) == UNION_TYPE
2785       || TREE_CODE (decltype) == QUAL_UNION_TYPE)
2786     {
2787       vi->is_unknown_size_var = true;
2788       vi->fullsize = ~0;
2789       vi->size = ~0;
2790     }
2791   else
2792     {
2793       vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2794       vi->size = vi->fullsize;
2795     }
2796   
2797   insert_id_for_tree (vi->decl, index);  
2798   VEC_safe_push (varinfo_t, gc, varmap, vi);
2799   if (is_global)
2800     make_constraint_to_anything (vi);
2801
2802   stats.total_vars++;
2803   if (use_field_sensitive 
2804       && !notokay 
2805       && !vi->is_unknown_size_var 
2806       && var_can_have_subvars (decl))
2807     {
2808       unsigned int newindex = VEC_length (varinfo_t, varmap);
2809       fieldoff_s *fo = NULL;
2810       unsigned int i;
2811       tree field;
2812
2813       for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2814         {
2815           if (!DECL_SIZE (fo->field) 
2816               || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
2817               || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
2818               || fo->offset < 0)
2819             {
2820               notokay = true;
2821               break;
2822             }
2823         }
2824
2825       /* We can't sort them if we have a field with a variable sized type,
2826          which will make notokay = true.  In that case, we are going to return
2827          without creating varinfos for the fields anyway, so sorting them is a
2828          waste to boot.  */
2829       if (!notokay)     
2830         sort_fieldstack (fieldstack);
2831       
2832       if (VEC_length (fieldoff_s, fieldstack) != 0)
2833         fo = VEC_index (fieldoff_s, fieldstack, 0);
2834
2835       if (fo == NULL || notokay)
2836         {
2837           vi->is_unknown_size_var = 1;
2838           vi->fullsize = ~0;
2839           vi->size = ~0;
2840           VEC_free (fieldoff_s, heap, fieldstack);
2841           return index;
2842         }
2843       
2844       field = fo->field;
2845       vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2846       for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2847         {
2848           varinfo_t newvi;
2849           const char *newname;
2850           char *tempname;
2851
2852           field = fo->field;
2853           newindex = VEC_length (varinfo_t, varmap);
2854           asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
2855           newname = ggc_strdup (tempname);
2856           free (tempname);
2857           newvi = new_var_info (decl, newindex, newname, newindex);
2858           newvi->offset = fo->offset;
2859           newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2860           newvi->fullsize = vi->fullsize;
2861           insert_into_field_list (vi, newvi);
2862           VEC_safe_push (varinfo_t, gc, varmap, newvi);
2863           if (is_global)
2864             make_constraint_to_anything (newvi);
2865
2866           stats.total_vars++;     
2867         }
2868       VEC_free (fieldoff_s, heap, fieldstack);
2869     }
2870   return index;
2871 }
2872
2873 /* Print out the points-to solution for VAR to FILE.  */
2874
2875 void
2876 dump_solution_for_var (FILE *file, unsigned int var)
2877 {
2878   varinfo_t vi = get_varinfo (var);
2879   unsigned int i;
2880   bitmap_iterator bi; 
2881   
2882   fprintf (file, "%s = { ", vi->name);
2883   EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
2884     {
2885       fprintf (file, "%s ", get_varinfo (i)->name);
2886     }
2887   fprintf (file, "}\n");
2888 }
2889
2890 /* Print the points-to solution for VAR to stdout.  */
2891
2892 void
2893 debug_solution_for_var (unsigned int var)
2894 {
2895   dump_solution_for_var (stdout, var);
2896 }
2897
2898
2899 /* Create varinfo structures for all of the variables in the
2900    function for intraprocedural mode.  */
2901
2902 static void
2903 intra_create_variable_infos (void)
2904 {
2905   tree t;
2906
2907   /* For each incoming argument arg, ARG = &ANYTHING */
2908   for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
2909     {
2910       struct constraint_expr lhs;
2911       struct constraint_expr rhs;
2912       varinfo_t p;
2913       
2914       lhs.offset = 0;
2915       lhs.type = SCALAR;
2916       lhs.var  = create_variable_info_for (t, alias_get_name (t));
2917       
2918       get_varinfo (lhs.var)->is_artificial_var = true;
2919       rhs.var = anything_id;
2920       rhs.type = ADDRESSOF;
2921       rhs.offset = 0;
2922
2923       for (p = get_varinfo (lhs.var); p; p = p->next)
2924         {
2925           struct constraint_expr temp = lhs;
2926           temp.var = p->id;
2927           process_constraint (new_constraint (temp, rhs));
2928         }
2929     }   
2930
2931 }
2932
2933 /* Set bits in INTO corresponding to the variable uids in solution set
2934    FROM  */
2935
2936 static void
2937 set_uids_in_ptset (bitmap into, bitmap from)
2938 {
2939   unsigned int i;
2940   bitmap_iterator bi;
2941
2942   EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
2943     {
2944       varinfo_t vi = get_varinfo (i);
2945       
2946       /* Variables containing unions may need to be converted to their 
2947          SFT's, because SFT's can have unions and we cannot.  */
2948       if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
2949         {
2950           subvar_t svars = get_subvars_for_var (vi->decl);
2951           subvar_t sv;
2952           for (sv = svars; sv; sv = sv->next)
2953             bitmap_set_bit (into, DECL_UID (sv->var));
2954         }
2955       /* We may end up with labels in the points-to set because people
2956          take their address, and they are _DECL's.  */
2957       else if (TREE_CODE (vi->decl) == VAR_DECL 
2958           || TREE_CODE (vi->decl) == PARM_DECL)
2959         bitmap_set_bit (into, DECL_UID (vi->decl));
2960
2961           
2962     }
2963 }
2964 static int have_alias_info = false;
2965
2966 /* Given a pointer variable P, fill in its points-to set, or return
2967    false if we can't.  */
2968
2969 bool
2970 find_what_p_points_to (tree p)
2971 {
2972   unsigned int id = 0;
2973   if (!have_alias_info)
2974     return false;
2975   if (lookup_id_for_tree (p, &id))
2976     {
2977       varinfo_t vi = get_varinfo (id);
2978       
2979       if (vi->is_artificial_var)
2980         return false;
2981
2982       /* See if this is a field or a structure */
2983       if (vi->size != vi->fullsize)
2984         {
2985           if (!var_can_have_subvars (vi->decl)
2986               || get_subvars_for_var (vi->decl) == NULL)
2987             return false;
2988           /* Nothing currently asks about structure fields directly, but when
2989              they do, we need code here to hand back the points-to set.  */
2990         } 
2991       else
2992         {
2993           struct ptr_info_def *pi = get_ptr_info (p);
2994           unsigned int i;
2995           bitmap_iterator bi;
2996
2997           /* This variable may have been collapsed, let's get the real
2998              variable.  */
2999           vi = get_varinfo (vi->node);
3000           
3001           /* Make sure there aren't any artificial vars in the points to set.
3002              XXX: Note that we need to translate our heap variables to
3003              something.  */
3004           EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
3005             {
3006               if (get_varinfo (i)->is_artificial_var)
3007                 return false;
3008             }
3009           pi->pt_anything = false;
3010           if (!pi->pt_vars)
3011             pi->pt_vars = BITMAP_GGC_ALLOC ();
3012           set_uids_in_ptset (pi->pt_vars, vi->solution);
3013           return true;
3014         }
3015     }
3016   return false;
3017 }
3018
3019
3020 /* Initialize things necessary to perform PTA */
3021
3022 static void
3023 init_alias_vars (void)
3024 {
3025   bitmap_obstack_initialize (&ptabitmap_obstack);
3026 }
3027
3028
3029 /* Dump points-to information to OUTFILE.  */
3030
3031 void
3032 dump_sa_points_to_info (FILE *outfile)
3033 {
3034   unsigned int i;
3035
3036   fprintf (outfile, "\nPoints-to information\n\n");
3037
3038   if (dump_flags & TDF_STATS)
3039     {
3040       fprintf (outfile, "Stats:\n");
3041       fprintf (outfile, "Total vars:               %d\n", stats.total_vars);
3042       fprintf (outfile, "Statically unified vars:  %d\n",
3043                stats.unified_vars_static);
3044       fprintf (outfile, "Collapsed vars:           %d\n", stats.collapsed_vars);
3045       fprintf (outfile, "Dynamically unified vars: %d\n",
3046                stats.unified_vars_dynamic);
3047       fprintf (outfile, "Iterations:               %d\n", stats.iterations);
3048     }
3049
3050   for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
3051     dump_solution_for_var (outfile, i);
3052 }
3053
3054
3055 /* Debug points-to information to stderr.  */
3056
3057 void
3058 debug_sa_points_to_info (void)
3059 {
3060   dump_sa_points_to_info (stderr);
3061 }
3062
3063
3064 /* Initialize the always-existing constraint variables for NULL
3065    ANYTHING, READONLY, and INTEGER */
3066
3067 static void
3068 init_base_vars (void)
3069 {
3070   struct constraint_expr lhs, rhs;
3071
3072   /* Create the NULL variable, used to represent that a variable points
3073      to NULL.  */
3074   nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
3075   var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
3076   insert_id_for_tree (nothing_tree, 0);
3077   var_nothing->is_artificial_var = 1;
3078   var_nothing->offset = 0;
3079   var_nothing->size = ~0;
3080   var_nothing->fullsize = ~0;
3081   nothing_id = 0;
3082   VEC_safe_push (varinfo_t, gc, varmap, var_nothing);
3083
3084   /* Create the ANYTHING variable, used to represent that a variable
3085      points to some unknown piece of memory.  */
3086   anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
3087   var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1); 
3088   insert_id_for_tree (anything_tree, 1);
3089   var_anything->is_artificial_var = 1;
3090   var_anything->size = ~0;
3091   var_anything->offset = 0;
3092   var_anything->next = NULL;
3093   var_anything->fullsize = ~0;
3094   anything_id = 1;
3095
3096   /* Anything points to anything.  This makes deref constraints just
3097      work in the presence of linked list and other p = *p type loops, 
3098      by saying that *ANYTHING = ANYTHING. */
3099   VEC_safe_push (varinfo_t, gc, varmap, var_anything);
3100   lhs.type = SCALAR;
3101   lhs.var = anything_id;
3102   lhs.offset = 0;
3103   rhs.type = ADDRESSOF;
3104   rhs.var = anything_id;
3105   rhs.offset = 0;
3106   var_anything->address_taken = true;
3107   /* This specifically does not use process_constraint because
3108      process_constraint ignores all anything = anything constraints, since all
3109      but this one are redundant.  */
3110   VEC_safe_push (constraint_t, gc, constraints, new_constraint (lhs, rhs));
3111   
3112   /* Create the READONLY variable, used to represent that a variable
3113      points to readonly memory.  */
3114   readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3115   var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3116   var_readonly->is_artificial_var = 1;
3117   var_readonly->offset = 0;
3118   var_readonly->size = ~0;
3119   var_readonly->fullsize = ~0;
3120   var_readonly->next = NULL;
3121   insert_id_for_tree (readonly_tree, 2);
3122   readonly_id = 2;
3123   VEC_safe_push (varinfo_t, gc, varmap, var_readonly);
3124
3125   /* readonly memory points to anything, in order to make deref
3126      easier.  In reality, it points to anything the particular
3127      readonly variable can point to, but we don't track this
3128      separately. */
3129   lhs.type = SCALAR;
3130   lhs.var = readonly_id;
3131   lhs.offset = 0;
3132   rhs.type = ADDRESSOF;
3133   rhs.var = anything_id;
3134   rhs.offset = 0;
3135   
3136   process_constraint (new_constraint (lhs, rhs));
3137   
3138   /* Create the INTEGER variable, used to represent that a variable points
3139      to an INTEGER.  */
3140   integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3141   var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3142   insert_id_for_tree (integer_tree, 3);
3143   var_integer->is_artificial_var = 1;
3144   var_integer->size = ~0;
3145   var_integer->fullsize = ~0;
3146   var_integer->offset = 0;
3147   var_integer->next = NULL;
3148   integer_id = 3;
3149   VEC_safe_push (varinfo_t, gc, varmap, var_integer);
3150
3151   /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3152      integer will point to.  */
3153   lhs.type = SCALAR;
3154   lhs.var = integer_id;
3155   lhs.offset = 0;
3156   rhs.type = ADDRESSOF;
3157   rhs.var = anything_id;
3158   rhs.offset = 0;
3159   process_constraint (new_constraint (lhs, rhs));
3160 }  
3161
3162
3163 /* Create points-to sets for the current function.  See the comments
3164    at the start of the file for an algorithmic overview.  */
3165
3166 static void
3167 create_alias_vars (void)
3168 {
3169   basic_block bb;
3170   
3171   init_alias_vars ();
3172
3173   constraint_pool = create_alloc_pool ("Constraint pool", 
3174                                        sizeof (struct constraint), 30);
3175   variable_info_pool = create_alloc_pool ("Variable info pool",
3176                                           sizeof (struct variable_info), 30);
3177   constraint_edge_pool = create_alloc_pool ("Constraint edges",
3178                                             sizeof (struct constraint_edge), 30);
3179   
3180   constraints = VEC_alloc (constraint_t, gc, 8);
3181   varmap = VEC_alloc (varinfo_t, gc, 8);
3182   id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3183   memset (&stats, 0, sizeof (stats));
3184   
3185   init_base_vars ();
3186
3187   intra_create_variable_infos ();
3188
3189   /* Now walk all statements and derive aliases.  */
3190   FOR_EACH_BB (bb)
3191     {
3192       block_stmt_iterator bsi; 
3193       tree phi;
3194
3195       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3196         if (is_gimple_reg (PHI_RESULT (phi)))
3197           find_func_aliases (phi);
3198
3199       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3200         find_func_aliases (bsi_stmt (bsi));
3201     }
3202
3203   build_constraint_graph ();
3204
3205   if (dump_file)
3206     {
3207       fprintf (dump_file, "Constraints:\n");
3208       dump_constraints (dump_file);
3209     }
3210
3211   if (dump_file)
3212     fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n");
3213
3214   find_and_collapse_graph_cycles (graph, false);
3215   perform_var_substitution (graph);
3216
3217   if (dump_file)
3218     fprintf (dump_file, "Solving graph:\n");
3219
3220   solve_graph (graph);
3221
3222   if (dump_file)
3223     dump_sa_points_to_info (dump_file);
3224   
3225   have_alias_info = true;
3226 }
3227
3228 struct tree_opt_pass pass_build_pta = 
3229 {
3230   "pta",                                /* name */
3231   NULL,                                 /* gate */
3232   create_alias_vars,                    /* execute */
3233   NULL,                                 /* sub */
3234   NULL,                                 /* next */
3235   0,                                    /* static_pass_number */
3236   TV_TREE_PTA,                          /* tv_id */
3237   PROP_cfg,                             /* properties_required */
3238   PROP_pta,                             /* properties_provided */
3239   0,                                    /* properties_destroyed */
3240   0,                                    /* todo_flags_start */
3241   0,                                    /* todo_flags_finish */
3242   0                                     /* letter */
3243 };
3244  
3245
3246 /* Delete created points-to sets.  */
3247
3248 static void
3249 delete_alias_vars (void)
3250 {
3251   htab_delete (id_for_tree);
3252   free_alloc_pool (variable_info_pool);
3253   free_alloc_pool (constraint_pool); 
3254   free_alloc_pool (constraint_edge_pool);
3255   bitmap_obstack_release (&ptabitmap_obstack);
3256   have_alias_info = false;
3257 }
3258
3259 struct tree_opt_pass pass_del_pta = 
3260 {
3261   NULL,                                 /* name */
3262   NULL,                                 /* gate */
3263   delete_alias_vars,                    /* execute */
3264   NULL,                                 /* sub */
3265   NULL,                                 /* next */
3266   0,                                    /* static_pass_number */
3267   TV_TREE_PTA,                          /* tv_id */
3268   PROP_pta,                             /* properties_required */
3269   0,                                    /* properties_provided */
3270   PROP_pta,                             /* properties_destroyed */
3271   0,                                    /* todo_flags_start */
3272   0,                                    /* todo_flags_finish */
3273   0                                     /* letter */
3274 };