OSDN Git Service

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