OSDN Git Service

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