OSDN Git Service

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