OSDN Git Service

2010-04-13 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-structalias.c
1 /* Tree based points-to analysis
2    Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4    Contributed by Daniel Berlin <dberlin@dberlin.org>
5
6    This file is part of GCC.
7
8    GCC is free software; you can redistribute it and/or modify
9    under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 3 of the License, or
11    (at your option) any later version.
12
13    GCC is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17
18    You should have received a copy of the GNU General Public License
19    along with GCC; see the file COPYING3.  If not see
20    <http://www.gnu.org/licenses/>.  */
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 "tree.h"
36 #include "tree-flow.h"
37 #include "tree-inline.h"
38 #include "varray.h"
39 #include "diagnostic.h"
40 #include "toplev.h"
41 #include "gimple.h"
42 #include "hashtab.h"
43 #include "function.h"
44 #include "cgraph.h"
45 #include "tree-pass.h"
46 #include "timevar.h"
47 #include "alloc-pool.h"
48 #include "splay-tree.h"
49 #include "params.h"
50 #include "cgraph.h"
51 #include "alias.h"
52 #include "pointer-set.h"
53
54 /* The idea behind this analyzer is to generate set constraints from the
55    program, then solve the resulting constraints in order to generate the
56    points-to sets.
57
58    Set constraints are a way of modeling program analysis problems that
59    involve sets.  They consist of an inclusion constraint language,
60    describing the variables (each variable is a set) and operations that
61    are involved on the variables, and a set of rules that derive facts
62    from these operations.  To solve a system of set constraints, you derive
63    all possible facts under the rules, which gives you the correct sets
64    as a consequence.
65
66    See  "Efficient Field-sensitive pointer analysis for C" by "David
67    J. Pearce and Paul H. J. Kelly and Chris Hankin, at
68    http://citeseer.ist.psu.edu/pearce04efficient.html
69
70    Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
71    of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
72    http://citeseer.ist.psu.edu/heintze01ultrafast.html
73
74    There are three types of real constraint expressions, DEREF,
75    ADDRESSOF, and SCALAR.  Each constraint expression consists
76    of a constraint type, a variable, and an offset.
77
78    SCALAR is a constraint expression type used to represent x, whether
79    it appears on the LHS or the RHS of a statement.
80    DEREF is a constraint expression type used to represent *x, whether
81    it appears on the LHS or the RHS of a statement.
82    ADDRESSOF is a constraint expression used to represent &x, whether
83    it appears on the LHS or the RHS of a statement.
84
85    Each pointer variable in the program is assigned an integer id, and
86    each field of a structure variable is assigned an integer id as well.
87
88    Structure variables are linked to their list of fields through a "next
89    field" in each variable that points to the next field in offset
90    order.
91    Each variable for a structure field has
92
93    1. "size", that tells the size in bits of that field.
94    2. "fullsize, that tells the size in bits of the entire structure.
95    3. "offset", that tells the offset in bits from the beginning of the
96    structure to this field.
97
98    Thus,
99    struct f
100    {
101      int a;
102      int b;
103    } foo;
104    int *bar;
105
106    looks like
107
108    foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
109    foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
110    bar -> id 3, size 32, offset 0, fullsize 32, next NULL
111
112
113   In order to solve the system of set constraints, the following is
114   done:
115
116   1. Each constraint variable x has a solution set associated with it,
117   Sol(x).
118
119   2. Constraints are separated into direct, copy, and complex.
120   Direct constraints are ADDRESSOF constraints that require no extra
121   processing, such as P = &Q
122   Copy constraints are those of the form P = Q.
123   Complex constraints are all the constraints involving dereferences
124   and offsets (including offsetted copies).
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
167 static bool use_field_sensitive = true;
168 static int in_ipa_mode = 0;
169
170 /* Used for predecessor bitmaps. */
171 static bitmap_obstack predbitmap_obstack;
172
173 /* Used for points-to sets.  */
174 static bitmap_obstack pta_obstack;
175
176 /* Used for oldsolution members of variables. */
177 static bitmap_obstack oldpta_obstack;
178
179 /* Used for per-solver-iteration bitmaps.  */
180 static bitmap_obstack iteration_obstack;
181
182 static unsigned int create_variable_info_for (tree, const char *);
183 typedef struct constraint_graph *constraint_graph_t;
184 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
185
186 struct constraint;
187 typedef struct constraint *constraint_t;
188
189 DEF_VEC_P(constraint_t);
190 DEF_VEC_ALLOC_P(constraint_t,heap);
191
192 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d)        \
193   if (a)                                                \
194     EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
195
196 static struct constraint_stats
197 {
198   unsigned int total_vars;
199   unsigned int nonpointer_vars;
200   unsigned int unified_vars_static;
201   unsigned int unified_vars_dynamic;
202   unsigned int iterations;
203   unsigned int num_edges;
204   unsigned int num_implicit_edges;
205   unsigned int points_to_sets_created;
206 } stats;
207
208 struct variable_info
209 {
210   /* ID of this variable  */
211   unsigned int id;
212
213   /* True if this is a variable created by the constraint analysis, such as
214      heap variables and constraints we had to break up.  */
215   unsigned int is_artificial_var : 1;
216
217   /* True if this is a special variable whose solution set should not be
218      changed.  */
219   unsigned int is_special_var : 1;
220
221   /* True for variables whose size is not known or variable.  */
222   unsigned int is_unknown_size_var : 1;
223
224   /* True for (sub-)fields that represent a whole variable.  */
225   unsigned int is_full_var : 1;
226
227   /* True if this is a heap variable.  */
228   unsigned int is_heap_var : 1;
229
230   /* True if this is a variable tracking a restrict pointer source.  */
231   unsigned int is_restrict_var : 1;
232
233   /* True if this field may contain pointers.  */
234   unsigned int may_have_pointers : 1;
235
236   /* True if this represents a global variable.  */
237   unsigned int is_global_var : 1;
238
239   /* A link to the variable for the next field in this structure.  */
240   struct variable_info *next;
241
242   /* Offset of this variable, in bits, from the base variable  */
243   unsigned HOST_WIDE_INT offset;
244
245   /* Size of the variable, in bits.  */
246   unsigned HOST_WIDE_INT size;
247
248   /* Full size of the base variable, in bits.  */
249   unsigned HOST_WIDE_INT fullsize;
250
251   /* Name of this variable */
252   const char *name;
253
254   /* Tree that this variable is associated with.  */
255   tree decl;
256
257   /* Points-to set for this variable.  */
258   bitmap solution;
259
260   /* Old points-to set for this variable.  */
261   bitmap oldsolution;
262 };
263 typedef struct variable_info *varinfo_t;
264
265 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
266 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
267                                                    unsigned HOST_WIDE_INT);
268 static varinfo_t lookup_vi_for_tree (tree);
269
270 /* Pool of variable info structures.  */
271 static alloc_pool variable_info_pool;
272
273 DEF_VEC_P(varinfo_t);
274
275 DEF_VEC_ALLOC_P(varinfo_t, heap);
276
277 /* Table of variable info structures for constraint variables.
278    Indexed directly by variable info id.  */
279 static VEC(varinfo_t,heap) *varmap;
280
281 /* Return the varmap element N */
282
283 static inline varinfo_t
284 get_varinfo (unsigned int n)
285 {
286   return VEC_index (varinfo_t, varmap, n);
287 }
288
289 /* Static IDs for the special variables.  */
290 enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
291        escaped_id = 3, nonlocal_id = 4,
292        storedanything_id = 5, integer_id = 6 };
293
294 struct GTY(()) heapvar_map {
295   struct tree_map map;
296   unsigned HOST_WIDE_INT offset;
297 };
298
299 static int
300 heapvar_map_eq (const void *p1, const void *p2)
301 {
302   const struct heapvar_map *h1 = (const struct heapvar_map *)p1;
303   const struct heapvar_map *h2 = (const struct heapvar_map *)p2;
304   return (h1->map.base.from == h2->map.base.from
305           && h1->offset == h2->offset);
306 }
307
308 static unsigned int
309 heapvar_map_hash (struct heapvar_map *h)
310 {
311   return iterative_hash_host_wide_int (h->offset,
312                                        htab_hash_pointer (h->map.base.from));
313 }
314
315 /* Lookup a heap var for FROM, and return it if we find one.  */
316
317 static tree
318 heapvar_lookup (tree from, unsigned HOST_WIDE_INT offset)
319 {
320   struct heapvar_map *h, in;
321   in.map.base.from = from;
322   in.offset = offset;
323   h = (struct heapvar_map *) htab_find_with_hash (heapvar_for_stmt, &in,
324                                                   heapvar_map_hash (&in));
325   if (h)
326     return h->map.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, unsigned HOST_WIDE_INT offset, tree to)
335 {
336   struct heapvar_map *h;
337   void **loc;
338
339   h = GGC_NEW (struct heapvar_map);
340   h->map.base.from = from;
341   h->offset = offset;
342   h->map.hash = heapvar_map_hash (h);
343   h->map.to = to;
344   loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->map.hash, INSERT);
345   gcc_assert (*loc == NULL);
346   *(struct heapvar_map **) loc = h;
347 }
348
349 /* Return a new variable info structure consisting for a variable
350    named NAME, and using constraint graph node NODE.  Append it
351    to the vector of variable info structures.  */
352
353 static varinfo_t
354 new_var_info (tree t, const char *name)
355 {
356   unsigned index = VEC_length (varinfo_t, varmap);
357   varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
358
359   ret->id = index;
360   ret->name = name;
361   ret->decl = t;
362   /* Vars without decl are artificial and do not have sub-variables.  */
363   ret->is_artificial_var = (t == NULL_TREE);
364   ret->is_special_var = false;
365   ret->is_unknown_size_var = false;
366   ret->is_full_var = (t == NULL_TREE);
367   ret->is_heap_var = false;
368   ret->is_restrict_var = false;
369   ret->may_have_pointers = true;
370   ret->is_global_var = (t == NULL_TREE);
371   if (t && DECL_P (t))
372     ret->is_global_var = is_global_var (t);
373   ret->solution = BITMAP_ALLOC (&pta_obstack);
374   ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
375   ret->next = NULL;
376
377   VEC_safe_push (varinfo_t, heap, varmap, ret);
378
379   return ret;
380 }
381
382
383 /* A map mapping call statements to per-stmt variables for uses
384    and clobbers specific to the call.  */
385 struct pointer_map_t *call_stmt_vars;
386
387 /* Lookup or create the variable for the call statement CALL.  */
388
389 static varinfo_t
390 get_call_vi (gimple call)
391 {
392   void **slot_p;
393   varinfo_t vi, vi2;
394
395   slot_p = pointer_map_insert (call_stmt_vars, call);
396   if (*slot_p)
397     return (varinfo_t) *slot_p;
398
399   vi = new_var_info (NULL_TREE, "CALLUSED");
400   vi->offset = 0;
401   vi->size = 1;
402   vi->fullsize = 2;
403   vi->is_full_var = true;
404
405   vi->next = vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
406   vi2->offset = 1;
407   vi2->size = 1;
408   vi2->fullsize = 2;
409   vi2->is_full_var = true;
410
411   *slot_p = (void *) vi;
412   return vi;
413 }
414
415 /* Lookup the variable for the call statement CALL representing
416    the uses.  Returns NULL if there is nothing special about this call.  */
417
418 static varinfo_t
419 lookup_call_use_vi (gimple call)
420 {
421   void **slot_p;
422
423   slot_p = pointer_map_contains (call_stmt_vars, call);
424   if (slot_p)
425     return (varinfo_t) *slot_p;
426
427   return NULL;
428 }
429
430 /* Lookup the variable for the call statement CALL representing
431    the clobbers.  Returns NULL if there is nothing special about this call.  */
432
433 static varinfo_t
434 lookup_call_clobber_vi (gimple call)
435 {
436   varinfo_t uses = lookup_call_use_vi (call);
437   if (!uses)
438     return NULL;
439
440   return uses->next;
441 }
442
443 /* Lookup or create the variable for the call statement CALL representing
444    the uses.  */
445
446 static varinfo_t
447 get_call_use_vi (gimple call)
448 {
449   return get_call_vi (call);
450 }
451
452 /* Lookup or create the variable for the call statement CALL representing
453    the clobbers.  */
454
455 static varinfo_t ATTRIBUTE_UNUSED
456 get_call_clobber_vi (gimple call)
457 {
458   return get_call_vi (call)->next;
459 }
460
461
462 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
463
464 /* An expression that appears in a constraint.  */
465
466 struct constraint_expr
467 {
468   /* Constraint type.  */
469   constraint_expr_type type;
470
471   /* Variable we are referring to in the constraint.  */
472   unsigned int var;
473
474   /* Offset, in bits, of this constraint from the beginning of
475      variables it ends up referring to.
476
477      IOW, in a deref constraint, we would deref, get the result set,
478      then add OFFSET to each member.   */
479   HOST_WIDE_INT offset;
480 };
481
482 /* Use 0x8000... as special unknown offset.  */
483 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
484
485 typedef struct constraint_expr ce_s;
486 DEF_VEC_O(ce_s);
487 DEF_VEC_ALLOC_O(ce_s, heap);
488 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
489 static void get_constraint_for (tree, VEC(ce_s, heap) **);
490 static void do_deref (VEC (ce_s, heap) **);
491
492 /* Our set constraints are made up of two constraint expressions, one
493    LHS, and one RHS.
494
495    As described in the introduction, our set constraints each represent an
496    operation between set valued variables.
497 */
498 struct constraint
499 {
500   struct constraint_expr lhs;
501   struct constraint_expr rhs;
502 };
503
504 /* List of constraints that we use to build the constraint graph from.  */
505
506 static VEC(constraint_t,heap) *constraints;
507 static alloc_pool constraint_pool;
508
509 /* The constraint graph is represented as an array of bitmaps
510    containing successor nodes.  */
511
512 struct constraint_graph
513 {
514   /* Size of this graph, which may be different than the number of
515      nodes in the variable map.  */
516   unsigned int size;
517
518   /* Explicit successors of each node. */
519   bitmap *succs;
520
521   /* Implicit predecessors of each node (Used for variable
522      substitution). */
523   bitmap *implicit_preds;
524
525   /* Explicit predecessors of each node (Used for variable substitution).  */
526   bitmap *preds;
527
528   /* Indirect cycle representatives, or -1 if the node has no indirect
529      cycles.  */
530   int *indirect_cycles;
531
532   /* Representative node for a node.  rep[a] == a unless the node has
533      been unified. */
534   unsigned int *rep;
535
536   /* Equivalence class representative for a label.  This is used for
537      variable substitution.  */
538   int *eq_rep;
539
540   /* Pointer equivalence label for a node.  All nodes with the same
541      pointer equivalence label can be unified together at some point
542      (either during constraint optimization or after the constraint
543      graph is built).  */
544   unsigned int *pe;
545
546   /* Pointer equivalence representative for a label.  This is used to
547      handle nodes that are pointer equivalent but not location
548      equivalent.  We can unite these once the addressof constraints
549      are transformed into initial points-to sets.  */
550   int *pe_rep;
551
552   /* Pointer equivalence label for each node, used during variable
553      substitution.  */
554   unsigned int *pointer_label;
555
556   /* Location equivalence label for each node, used during location
557      equivalence finding.  */
558   unsigned int *loc_label;
559
560   /* Pointed-by set for each node, used during location equivalence
561      finding.  This is pointed-by rather than pointed-to, because it
562      is constructed using the predecessor graph.  */
563   bitmap *pointed_by;
564
565   /* Points to sets for pointer equivalence.  This is *not* the actual
566      points-to sets for nodes.  */
567   bitmap *points_to;
568
569   /* Bitmap of nodes where the bit is set if the node is a direct
570      node.  Used for variable substitution.  */
571   sbitmap direct_nodes;
572
573   /* Bitmap of nodes where the bit is set if the node is address
574      taken.  Used for variable substitution.  */
575   bitmap address_taken;
576
577   /* Vector of complex constraints for each graph node.  Complex
578      constraints are those involving dereferences or offsets that are
579      not 0.  */
580   VEC(constraint_t,heap) **complex;
581 };
582
583 static constraint_graph_t graph;
584
585 /* During variable substitution and the offline version of indirect
586    cycle finding, we create nodes to represent dereferences and
587    address taken constraints.  These represent where these start and
588    end.  */
589 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
590 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
591
592 /* Return the representative node for NODE, if NODE has been unioned
593    with another NODE.
594    This function performs path compression along the way to finding
595    the representative.  */
596
597 static unsigned int
598 find (unsigned int node)
599 {
600   gcc_assert (node < graph->size);
601   if (graph->rep[node] != node)
602     return graph->rep[node] = find (graph->rep[node]);
603   return node;
604 }
605
606 /* Union the TO and FROM nodes to the TO nodes.
607    Note that at some point in the future, we may want to do
608    union-by-rank, in which case we are going to have to return the
609    node we unified to.  */
610
611 static bool
612 unite (unsigned int to, unsigned int from)
613 {
614   gcc_assert (to < graph->size && from < graph->size);
615   if (to != from && graph->rep[from] != to)
616     {
617       graph->rep[from] = to;
618       return true;
619     }
620   return false;
621 }
622
623 /* Create a new constraint consisting of LHS and RHS expressions.  */
624
625 static constraint_t
626 new_constraint (const struct constraint_expr lhs,
627                 const struct constraint_expr rhs)
628 {
629   constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
630   ret->lhs = lhs;
631   ret->rhs = rhs;
632   return ret;
633 }
634
635 /* Print out constraint C to FILE.  */
636
637 static void
638 dump_constraint (FILE *file, constraint_t c)
639 {
640   if (c->lhs.type == ADDRESSOF)
641     fprintf (file, "&");
642   else if (c->lhs.type == DEREF)
643     fprintf (file, "*");
644   fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
645   if (c->lhs.offset == UNKNOWN_OFFSET)
646     fprintf (file, " + UNKNOWN");
647   else if (c->lhs.offset != 0)
648     fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
649   fprintf (file, " = ");
650   if (c->rhs.type == ADDRESSOF)
651     fprintf (file, "&");
652   else if (c->rhs.type == DEREF)
653     fprintf (file, "*");
654   fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
655   if (c->rhs.offset == UNKNOWN_OFFSET)
656     fprintf (file, " + UNKNOWN");
657   else if (c->rhs.offset != 0)
658     fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
659   fprintf (file, "\n");
660 }
661
662
663 void debug_constraint (constraint_t);
664 void debug_constraints (void);
665 void debug_constraint_graph (void);
666 void debug_solution_for_var (unsigned int);
667 void debug_sa_points_to_info (void);
668
669 /* Print out constraint C to stderr.  */
670
671 void
672 debug_constraint (constraint_t c)
673 {
674   dump_constraint (stderr, c);
675 }
676
677 /* Print out all constraints to FILE */
678
679 static void
680 dump_constraints (FILE *file)
681 {
682   int i;
683   constraint_t c;
684   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
685     dump_constraint (file, c);
686 }
687
688 /* Print out all constraints to stderr.  */
689
690 void
691 debug_constraints (void)
692 {
693   dump_constraints (stderr);
694 }
695
696 /* Print out to FILE the edge in the constraint graph that is created by
697    constraint c. The edge may have a label, depending on the type of
698    constraint that it represents. If complex1, e.g: a = *b, then the label
699    is "=*", if complex2, e.g: *a = b, then the label is "*=", if
700    complex with an offset, e.g: a = b + 8, then the label is "+".
701    Otherwise the edge has no label.  */
702
703 static void
704 dump_constraint_edge (FILE *file, constraint_t c)
705 {
706   if (c->rhs.type != ADDRESSOF)
707     {
708       const char *src = get_varinfo (c->rhs.var)->name;
709       const char *dst = get_varinfo (c->lhs.var)->name;
710       fprintf (file, "  \"%s\" -> \"%s\" ", src, dst);
711       /* Due to preprocessing of constraints, instructions like *a = *b are
712          illegal; thus, we do not have to handle such cases.  */
713       if (c->lhs.type == DEREF)
714         fprintf (file, " [ label=\"*=\" ] ;\n");
715       else if (c->rhs.type == DEREF)
716         fprintf (file, " [ label=\"=*\" ] ;\n");
717       else
718         {
719           /* We must check the case where the constraint is an offset.
720              In this case, it is treated as a complex constraint.  */
721           if (c->rhs.offset != c->lhs.offset)
722             fprintf (file, " [ label=\"+\" ] ;\n");
723           else
724             fprintf (file, " ;\n");
725         }
726     }
727 }
728
729 /* Print the constraint graph in dot format.  */
730
731 static void
732 dump_constraint_graph (FILE *file)
733 {
734   unsigned int i=0, size;
735   constraint_t c;
736
737   /* Only print the graph if it has already been initialized:  */
738   if (!graph)
739     return;
740
741   /* Print the constraints used to produce the constraint graph. The
742      constraints will be printed as comments in the dot file:  */
743   fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
744   dump_constraints (file);
745   fprintf (file, "*/\n");
746
747   /* Prints the header of the dot file:  */
748   fprintf (file, "\n\n// The constraint graph in dot format:\n");
749   fprintf (file, "strict digraph {\n");
750   fprintf (file, "  node [\n    shape = box\n  ]\n");
751   fprintf (file, "  edge [\n    fontsize = \"12\"\n  ]\n");
752   fprintf (file, "\n  // List of nodes in the constraint graph:\n");
753
754   /* The next lines print the nodes in the graph. In order to get the
755      number of nodes in the graph, we must choose the minimum between the
756      vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
757      yet been initialized, then graph->size == 0, otherwise we must only
758      read nodes that have an entry in VEC (varinfo_t, varmap).  */
759   size = VEC_length (varinfo_t, varmap);
760   size = size < graph->size ? size : graph->size;
761   for (i = 0; i < size; i++)
762     {
763       const char *name = get_varinfo (graph->rep[i])->name;
764       fprintf (file, "  \"%s\" ;\n", name);
765     }
766
767   /* Go over the list of constraints printing the edges in the constraint
768      graph.  */
769   fprintf (file, "\n  // The constraint edges:\n");
770   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
771     if (c)
772       dump_constraint_edge (file, c);
773
774   /* Prints the tail of the dot file. By now, only the closing bracket.  */
775   fprintf (file, "}\n\n\n");
776 }
777
778 /* Print out the constraint graph to stderr.  */
779
780 void
781 debug_constraint_graph (void)
782 {
783   dump_constraint_graph (stderr);
784 }
785
786 /* SOLVER FUNCTIONS
787
788    The solver is a simple worklist solver, that works on the following
789    algorithm:
790
791    sbitmap changed_nodes = all zeroes;
792    changed_count = 0;
793    For each node that is not already collapsed:
794        changed_count++;
795        set bit in changed nodes
796
797    while (changed_count > 0)
798    {
799      compute topological ordering for constraint graph
800
801      find and collapse cycles in the constraint graph (updating
802      changed if necessary)
803
804      for each node (n) in the graph in topological order:
805        changed_count--;
806
807        Process each complex constraint associated with the node,
808        updating changed if necessary.
809
810        For each outgoing edge from n, propagate the solution from n to
811        the destination of the edge, updating changed as necessary.
812
813    }  */
814
815 /* Return true if two constraint expressions A and B are equal.  */
816
817 static bool
818 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
819 {
820   return a.type == b.type && a.var == b.var && a.offset == b.offset;
821 }
822
823 /* Return true if constraint expression A is less than constraint expression
824    B.  This is just arbitrary, but consistent, in order to give them an
825    ordering.  */
826
827 static bool
828 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
829 {
830   if (a.type == b.type)
831     {
832       if (a.var == b.var)
833         return a.offset < b.offset;
834       else
835         return a.var < b.var;
836     }
837   else
838     return a.type < b.type;
839 }
840
841 /* Return true if constraint A is less than constraint B.  This is just
842    arbitrary, but consistent, in order to give them an ordering.  */
843
844 static bool
845 constraint_less (const constraint_t a, const constraint_t b)
846 {
847   if (constraint_expr_less (a->lhs, b->lhs))
848     return true;
849   else if (constraint_expr_less (b->lhs, a->lhs))
850     return false;
851   else
852     return constraint_expr_less (a->rhs, b->rhs);
853 }
854
855 /* Return true if two constraints A and B are equal.  */
856
857 static bool
858 constraint_equal (struct constraint a, struct constraint b)
859 {
860   return constraint_expr_equal (a.lhs, b.lhs)
861     && constraint_expr_equal (a.rhs, b.rhs);
862 }
863
864
865 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
866
867 static constraint_t
868 constraint_vec_find (VEC(constraint_t,heap) *vec,
869                      struct constraint lookfor)
870 {
871   unsigned int place;
872   constraint_t found;
873
874   if (vec == NULL)
875     return NULL;
876
877   place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
878   if (place >= VEC_length (constraint_t, vec))
879     return NULL;
880   found = VEC_index (constraint_t, vec, place);
881   if (!constraint_equal (*found, lookfor))
882     return NULL;
883   return found;
884 }
885
886 /* Union two constraint vectors, TO and FROM.  Put the result in TO.  */
887
888 static void
889 constraint_set_union (VEC(constraint_t,heap) **to,
890                       VEC(constraint_t,heap) **from)
891 {
892   int i;
893   constraint_t c;
894
895   for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
896     {
897       if (constraint_vec_find (*to, *c) == NULL)
898         {
899           unsigned int place = VEC_lower_bound (constraint_t, *to, c,
900                                                 constraint_less);
901           VEC_safe_insert (constraint_t, heap, *to, place, c);
902         }
903     }
904 }
905
906 /* Expands the solution in SET to all sub-fields of variables included.
907    Union the expanded result into RESULT.  */
908
909 static void
910 solution_set_expand (bitmap result, bitmap set)
911 {
912   bitmap_iterator bi;
913   bitmap vars = NULL;
914   unsigned j;
915
916   /* In a first pass record all variables we need to add all
917      sub-fields off.  This avoids quadratic behavior.  */
918   EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
919     {
920       varinfo_t v = get_varinfo (j);
921       if (v->is_artificial_var
922           || v->is_full_var)
923         continue;
924       v = lookup_vi_for_tree (v->decl);
925       if (vars == NULL)
926         vars = BITMAP_ALLOC (NULL);
927       bitmap_set_bit (vars, v->id);
928     }
929
930   /* In the second pass now do the addition to the solution and
931      to speed up solving add it to the delta as well.  */
932   if (vars != NULL)
933     {
934       EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
935         {
936           varinfo_t v = get_varinfo (j);
937           for (; v != NULL; v = v->next)
938             bitmap_set_bit (result, v->id);
939         }
940       BITMAP_FREE (vars);
941     }
942 }
943
944 /* Take a solution set SET, add OFFSET to each member of the set, and
945    overwrite SET with the result when done.  */
946
947 static void
948 solution_set_add (bitmap set, HOST_WIDE_INT offset)
949 {
950   bitmap result = BITMAP_ALLOC (&iteration_obstack);
951   unsigned int i;
952   bitmap_iterator bi;
953
954   /* If the offset is unknown we have to expand the solution to
955      all subfields.  */
956   if (offset == UNKNOWN_OFFSET)
957     {
958       solution_set_expand (set, set);
959       return;
960     }
961
962   EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
963     {
964       varinfo_t vi = get_varinfo (i);
965
966       /* If this is a variable with just one field just set its bit
967          in the result.  */
968       if (vi->is_artificial_var
969           || vi->is_unknown_size_var
970           || vi->is_full_var)
971         bitmap_set_bit (result, i);
972       else
973         {
974           unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
975
976           /* If the offset makes the pointer point to before the
977              variable use offset zero for the field lookup.  */
978           if (offset < 0
979               && fieldoffset > vi->offset)
980             fieldoffset = 0;
981
982           if (offset != 0)
983             vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
984
985           bitmap_set_bit (result, vi->id);
986           /* If the result is not exactly at fieldoffset include the next
987              field as well.  See get_constraint_for_ptr_offset for more
988              rationale.  */
989           if (vi->offset != fieldoffset
990               && vi->next != NULL)
991             bitmap_set_bit (result, vi->next->id);
992         }
993     }
994
995   bitmap_copy (set, result);
996   BITMAP_FREE (result);
997 }
998
999 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
1000    process.  */
1001
1002 static bool
1003 set_union_with_increment  (bitmap to, bitmap from, HOST_WIDE_INT inc)
1004 {
1005   if (inc == 0)
1006     return bitmap_ior_into (to, from);
1007   else
1008     {
1009       bitmap tmp;
1010       bool res;
1011
1012       tmp = BITMAP_ALLOC (&iteration_obstack);
1013       bitmap_copy (tmp, from);
1014       solution_set_add (tmp, inc);
1015       res = bitmap_ior_into (to, tmp);
1016       BITMAP_FREE (tmp);
1017       return res;
1018     }
1019 }
1020
1021 /* Insert constraint C into the list of complex constraints for graph
1022    node VAR.  */
1023
1024 static void
1025 insert_into_complex (constraint_graph_t graph,
1026                      unsigned int var, constraint_t c)
1027 {
1028   VEC (constraint_t, heap) *complex = graph->complex[var];
1029   unsigned int place = VEC_lower_bound (constraint_t, complex, c,
1030                                         constraint_less);
1031
1032   /* Only insert constraints that do not already exist.  */
1033   if (place >= VEC_length (constraint_t, complex)
1034       || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
1035     VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
1036 }
1037
1038
1039 /* Condense two variable nodes into a single variable node, by moving
1040    all associated info from SRC to TO.  */
1041
1042 static void
1043 merge_node_constraints (constraint_graph_t graph, unsigned int to,
1044                         unsigned int from)
1045 {
1046   unsigned int i;
1047   constraint_t c;
1048
1049   gcc_assert (find (from) == to);
1050
1051   /* Move all complex constraints from src node into to node  */
1052   for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
1053     {
1054       /* In complex constraints for node src, we may have either
1055          a = *src, and *src = a, or an offseted constraint which are
1056          always added to the rhs node's constraints.  */
1057
1058       if (c->rhs.type == DEREF)
1059         c->rhs.var = to;
1060       else if (c->lhs.type == DEREF)
1061         c->lhs.var = to;
1062       else
1063         c->rhs.var = to;
1064     }
1065   constraint_set_union (&graph->complex[to], &graph->complex[from]);
1066   VEC_free (constraint_t, heap, graph->complex[from]);
1067   graph->complex[from] = NULL;
1068 }
1069
1070
1071 /* Remove edges involving NODE from GRAPH.  */
1072
1073 static void
1074 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1075 {
1076   if (graph->succs[node])
1077     BITMAP_FREE (graph->succs[node]);
1078 }
1079
1080 /* Merge GRAPH nodes FROM and TO into node TO.  */
1081
1082 static void
1083 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1084                    unsigned int from)
1085 {
1086   if (graph->indirect_cycles[from] != -1)
1087     {
1088       /* If we have indirect cycles with the from node, and we have
1089          none on the to node, the to node has indirect cycles from the
1090          from node now that they are unified.
1091          If indirect cycles exist on both, unify the nodes that they
1092          are in a cycle with, since we know they are in a cycle with
1093          each other.  */
1094       if (graph->indirect_cycles[to] == -1)
1095         graph->indirect_cycles[to] = graph->indirect_cycles[from];
1096     }
1097
1098   /* Merge all the successor edges.  */
1099   if (graph->succs[from])
1100     {
1101       if (!graph->succs[to])
1102         graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1103       bitmap_ior_into (graph->succs[to],
1104                        graph->succs[from]);
1105     }
1106
1107   clear_edges_for_node (graph, from);
1108 }
1109
1110
1111 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1112    it doesn't exist in the graph already.  */
1113
1114 static void
1115 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1116                          unsigned int from)
1117 {
1118   if (to == from)
1119     return;
1120
1121   if (!graph->implicit_preds[to])
1122     graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1123
1124   if (bitmap_set_bit (graph->implicit_preds[to], from))
1125     stats.num_implicit_edges++;
1126 }
1127
1128 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1129    it doesn't exist in the graph already.
1130    Return false if the edge already existed, true otherwise.  */
1131
1132 static void
1133 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1134                      unsigned int from)
1135 {
1136   if (!graph->preds[to])
1137     graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1138   bitmap_set_bit (graph->preds[to], from);
1139 }
1140
1141 /* Add a graph edge to GRAPH, going from FROM to TO if
1142    it doesn't exist in the graph already.
1143    Return false if the edge already existed, true otherwise.  */
1144
1145 static bool
1146 add_graph_edge (constraint_graph_t graph, unsigned int to,
1147                 unsigned int from)
1148 {
1149   if (to == from)
1150     {
1151       return false;
1152     }
1153   else
1154     {
1155       bool r = false;
1156
1157       if (!graph->succs[from])
1158         graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1159       if (bitmap_set_bit (graph->succs[from], to))
1160         {
1161           r = true;
1162           if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1163             stats.num_edges++;
1164         }
1165       return r;
1166     }
1167 }
1168
1169
1170 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH.  */
1171
1172 static bool
1173 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1174                   unsigned int dest)
1175 {
1176   return (graph->succs[dest]
1177           && bitmap_bit_p (graph->succs[dest], src));
1178 }
1179
1180 /* Initialize the constraint graph structure to contain SIZE nodes.  */
1181
1182 static void
1183 init_graph (unsigned int size)
1184 {
1185   unsigned int j;
1186
1187   graph = XCNEW (struct constraint_graph);
1188   graph->size = size;
1189   graph->succs = XCNEWVEC (bitmap, graph->size);
1190   graph->indirect_cycles = XNEWVEC (int, graph->size);
1191   graph->rep = XNEWVEC (unsigned int, graph->size);
1192   graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1193   graph->pe = XCNEWVEC (unsigned int, graph->size);
1194   graph->pe_rep = XNEWVEC (int, graph->size);
1195
1196   for (j = 0; j < graph->size; j++)
1197     {
1198       graph->rep[j] = j;
1199       graph->pe_rep[j] = -1;
1200       graph->indirect_cycles[j] = -1;
1201     }
1202 }
1203
1204 /* Build the constraint graph, adding only predecessor edges right now.  */
1205
1206 static void
1207 build_pred_graph (void)
1208 {
1209   int i;
1210   constraint_t c;
1211   unsigned int j;
1212
1213   graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1214   graph->preds = XCNEWVEC (bitmap, graph->size);
1215   graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1216   graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1217   graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1218   graph->points_to = XCNEWVEC (bitmap, graph->size);
1219   graph->eq_rep = XNEWVEC (int, graph->size);
1220   graph->direct_nodes = sbitmap_alloc (graph->size);
1221   graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1222   sbitmap_zero (graph->direct_nodes);
1223
1224   for (j = 0; j < FIRST_REF_NODE; j++)
1225     {
1226       if (!get_varinfo (j)->is_special_var)
1227         SET_BIT (graph->direct_nodes, j);
1228     }
1229
1230   for (j = 0; j < graph->size; j++)
1231     graph->eq_rep[j] = -1;
1232
1233   for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1234     graph->indirect_cycles[j] = -1;
1235
1236   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1237     {
1238       struct constraint_expr lhs = c->lhs;
1239       struct constraint_expr rhs = c->rhs;
1240       unsigned int lhsvar = lhs.var;
1241       unsigned int rhsvar = rhs.var;
1242
1243       if (lhs.type == DEREF)
1244         {
1245           /* *x = y.  */
1246           if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1247             add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1248         }
1249       else if (rhs.type == DEREF)
1250         {
1251           /* x = *y */
1252           if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1253             add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1254           else
1255             RESET_BIT (graph->direct_nodes, lhsvar);
1256         }
1257       else if (rhs.type == ADDRESSOF)
1258         {
1259           varinfo_t v;
1260
1261           /* x = &y */
1262           if (graph->points_to[lhsvar] == NULL)
1263             graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1264           bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1265
1266           if (graph->pointed_by[rhsvar] == NULL)
1267             graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1268           bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1269
1270           /* Implicitly, *x = y */
1271           add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1272
1273           /* All related variables are no longer direct nodes.  */
1274           RESET_BIT (graph->direct_nodes, rhsvar);
1275           v = get_varinfo (rhsvar);
1276           if (!v->is_full_var)
1277             {
1278               v = lookup_vi_for_tree (v->decl);
1279               do
1280                 {
1281                   RESET_BIT (graph->direct_nodes, v->id);
1282                   v = v->next;
1283                 }
1284               while (v != NULL);
1285             }
1286           bitmap_set_bit (graph->address_taken, rhsvar);
1287         }
1288       else if (lhsvar > anything_id
1289                && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1290         {
1291           /* x = y */
1292           add_pred_graph_edge (graph, lhsvar, rhsvar);
1293           /* Implicitly, *x = *y */
1294           add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1295                                    FIRST_REF_NODE + rhsvar);
1296         }
1297       else if (lhs.offset != 0 || rhs.offset != 0)
1298         {
1299           if (rhs.offset != 0)
1300             RESET_BIT (graph->direct_nodes, lhs.var);
1301           else if (lhs.offset != 0)
1302             RESET_BIT (graph->direct_nodes, rhs.var);
1303         }
1304     }
1305 }
1306
1307 /* Build the constraint graph, adding successor edges.  */
1308
1309 static void
1310 build_succ_graph (void)
1311 {
1312   unsigned i, t;
1313   constraint_t c;
1314
1315   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1316     {
1317       struct constraint_expr lhs;
1318       struct constraint_expr rhs;
1319       unsigned int lhsvar;
1320       unsigned int rhsvar;
1321
1322       if (!c)
1323         continue;
1324
1325       lhs = c->lhs;
1326       rhs = c->rhs;
1327       lhsvar = find (lhs.var);
1328       rhsvar = find (rhs.var);
1329
1330       if (lhs.type == DEREF)
1331         {
1332           if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1333             add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1334         }
1335       else if (rhs.type == DEREF)
1336         {
1337           if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1338             add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1339         }
1340       else if (rhs.type == ADDRESSOF)
1341         {
1342           /* x = &y */
1343           gcc_assert (find (rhs.var) == rhs.var);
1344           bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1345         }
1346       else if (lhsvar > anything_id
1347                && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1348         {
1349           add_graph_edge (graph, lhsvar, rhsvar);
1350         }
1351     }
1352
1353   /* Add edges from STOREDANYTHING to all non-direct nodes that can
1354      receive pointers.  */
1355   t = find (storedanything_id);
1356   for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1357     {
1358       if (!TEST_BIT (graph->direct_nodes, i)
1359           && get_varinfo (i)->may_have_pointers)
1360         add_graph_edge (graph, find (i), t);
1361     }
1362
1363   /* Everything stored to ANYTHING also potentially escapes.  */
1364   add_graph_edge (graph, find (escaped_id), t);
1365 }
1366
1367
1368 /* Changed variables on the last iteration.  */
1369 static unsigned int changed_count;
1370 static sbitmap changed;
1371
1372 /* Strongly Connected Component visitation info.  */
1373
1374 struct scc_info
1375 {
1376   sbitmap visited;
1377   sbitmap deleted;
1378   unsigned int *dfs;
1379   unsigned int *node_mapping;
1380   int current_index;
1381   VEC(unsigned,heap) *scc_stack;
1382 };
1383
1384
1385 /* Recursive routine to find strongly connected components in GRAPH.
1386    SI is the SCC info to store the information in, and N is the id of current
1387    graph node we are processing.
1388
1389    This is Tarjan's strongly connected component finding algorithm, as
1390    modified by Nuutila to keep only non-root nodes on the stack.
1391    The algorithm can be found in "On finding the strongly connected
1392    connected components in a directed graph" by Esko Nuutila and Eljas
1393    Soisalon-Soininen, in Information Processing Letters volume 49,
1394    number 1, pages 9-14.  */
1395
1396 static void
1397 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1398 {
1399   unsigned int i;
1400   bitmap_iterator bi;
1401   unsigned int my_dfs;
1402
1403   SET_BIT (si->visited, n);
1404   si->dfs[n] = si->current_index ++;
1405   my_dfs = si->dfs[n];
1406
1407   /* Visit all the successors.  */
1408   EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1409     {
1410       unsigned int w;
1411
1412       if (i > LAST_REF_NODE)
1413         break;
1414
1415       w = find (i);
1416       if (TEST_BIT (si->deleted, w))
1417         continue;
1418
1419       if (!TEST_BIT (si->visited, w))
1420         scc_visit (graph, si, w);
1421       {
1422         unsigned int t = find (w);
1423         unsigned int nnode = find (n);
1424         gcc_assert (nnode == n);
1425
1426         if (si->dfs[t] < si->dfs[nnode])
1427           si->dfs[n] = si->dfs[t];
1428       }
1429     }
1430
1431   /* See if any components have been identified.  */
1432   if (si->dfs[n] == my_dfs)
1433     {
1434       if (VEC_length (unsigned, si->scc_stack) > 0
1435           && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1436         {
1437           bitmap scc = BITMAP_ALLOC (NULL);
1438           unsigned int lowest_node;
1439           bitmap_iterator bi;
1440
1441           bitmap_set_bit (scc, n);
1442
1443           while (VEC_length (unsigned, si->scc_stack) != 0
1444                  && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1445             {
1446               unsigned int w = VEC_pop (unsigned, si->scc_stack);
1447
1448               bitmap_set_bit (scc, w);
1449             }
1450
1451           lowest_node = bitmap_first_set_bit (scc);
1452           gcc_assert (lowest_node < FIRST_REF_NODE);
1453
1454           /* Collapse the SCC nodes into a single node, and mark the
1455              indirect cycles.  */
1456           EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1457             {
1458               if (i < FIRST_REF_NODE)
1459                 {
1460                   if (unite (lowest_node, i))
1461                     unify_nodes (graph, lowest_node, i, false);
1462                 }
1463               else
1464                 {
1465                   unite (lowest_node, i);
1466                   graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1467                 }
1468             }
1469         }
1470       SET_BIT (si->deleted, n);
1471     }
1472   else
1473     VEC_safe_push (unsigned, heap, si->scc_stack, n);
1474 }
1475
1476 /* Unify node FROM into node TO, updating the changed count if
1477    necessary when UPDATE_CHANGED is true.  */
1478
1479 static void
1480 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1481              bool update_changed)
1482 {
1483
1484   gcc_assert (to != from && find (to) == to);
1485   if (dump_file && (dump_flags & TDF_DETAILS))
1486     fprintf (dump_file, "Unifying %s to %s\n",
1487              get_varinfo (from)->name,
1488              get_varinfo (to)->name);
1489
1490   if (update_changed)
1491     stats.unified_vars_dynamic++;
1492   else
1493     stats.unified_vars_static++;
1494
1495   merge_graph_nodes (graph, to, from);
1496   merge_node_constraints (graph, to, from);
1497
1498   /* Mark TO as changed if FROM was changed. If TO was already marked
1499      as changed, decrease the changed count.  */
1500
1501   if (update_changed && TEST_BIT (changed, from))
1502     {
1503       RESET_BIT (changed, from);
1504       if (!TEST_BIT (changed, to))
1505         SET_BIT (changed, to);
1506       else
1507         {
1508           gcc_assert (changed_count > 0);
1509           changed_count--;
1510         }
1511     }
1512   if (get_varinfo (from)->solution)
1513     {
1514       /* If the solution changes because of the merging, we need to mark
1515          the variable as changed.  */
1516       if (bitmap_ior_into (get_varinfo (to)->solution,
1517                            get_varinfo (from)->solution))
1518         {
1519           if (update_changed && !TEST_BIT (changed, to))
1520             {
1521               SET_BIT (changed, to);
1522               changed_count++;
1523             }
1524         }
1525
1526       BITMAP_FREE (get_varinfo (from)->solution);
1527       BITMAP_FREE (get_varinfo (from)->oldsolution);
1528
1529       if (stats.iterations > 0)
1530         {
1531           BITMAP_FREE (get_varinfo (to)->oldsolution);
1532           get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1533         }
1534     }
1535   if (valid_graph_edge (graph, to, to))
1536     {
1537       if (graph->succs[to])
1538         bitmap_clear_bit (graph->succs[to], to);
1539     }
1540 }
1541
1542 /* Information needed to compute the topological ordering of a graph.  */
1543
1544 struct topo_info
1545 {
1546   /* sbitmap of visited nodes.  */
1547   sbitmap visited;
1548   /* Array that stores the topological order of the graph, *in
1549      reverse*.  */
1550   VEC(unsigned,heap) *topo_order;
1551 };
1552
1553
1554 /* Initialize and return a topological info structure.  */
1555
1556 static struct topo_info *
1557 init_topo_info (void)
1558 {
1559   size_t size = graph->size;
1560   struct topo_info *ti = XNEW (struct topo_info);
1561   ti->visited = sbitmap_alloc (size);
1562   sbitmap_zero (ti->visited);
1563   ti->topo_order = VEC_alloc (unsigned, heap, 1);
1564   return ti;
1565 }
1566
1567
1568 /* Free the topological sort info pointed to by TI.  */
1569
1570 static void
1571 free_topo_info (struct topo_info *ti)
1572 {
1573   sbitmap_free (ti->visited);
1574   VEC_free (unsigned, heap, ti->topo_order);
1575   free (ti);
1576 }
1577
1578 /* Visit the graph in topological order, and store the order in the
1579    topo_info structure.  */
1580
1581 static void
1582 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1583             unsigned int n)
1584 {
1585   bitmap_iterator bi;
1586   unsigned int j;
1587
1588   SET_BIT (ti->visited, n);
1589
1590   if (graph->succs[n])
1591     EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1592       {
1593         if (!TEST_BIT (ti->visited, j))
1594           topo_visit (graph, ti, j);
1595       }
1596
1597   VEC_safe_push (unsigned, heap, ti->topo_order, n);
1598 }
1599
1600 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1601    starting solution for y.  */
1602
1603 static void
1604 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1605                   bitmap delta)
1606 {
1607   unsigned int lhs = c->lhs.var;
1608   bool flag = false;
1609   bitmap sol = get_varinfo (lhs)->solution;
1610   unsigned int j;
1611   bitmap_iterator bi;
1612   HOST_WIDE_INT roffset = c->rhs.offset;
1613
1614   /* Our IL does not allow this.  */
1615   gcc_assert (c->lhs.offset == 0);
1616
1617   /* If the solution of Y contains anything it is good enough to transfer
1618      this to the LHS.  */
1619   if (bitmap_bit_p (delta, anything_id))
1620     {
1621       flag |= bitmap_set_bit (sol, anything_id);
1622       goto done;
1623     }
1624
1625   /* If we do not know at with offset the rhs is dereferenced compute
1626      the reachability set of DELTA, conservatively assuming it is
1627      dereferenced at all valid offsets.  */
1628   if (roffset == UNKNOWN_OFFSET)
1629     {
1630       solution_set_expand (delta, delta);
1631       /* No further offset processing is necessary.  */
1632       roffset = 0;
1633     }
1634
1635   /* For each variable j in delta (Sol(y)), add
1636      an edge in the graph from j to x, and union Sol(j) into Sol(x).  */
1637   EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1638     {
1639       varinfo_t v = get_varinfo (j);
1640       HOST_WIDE_INT fieldoffset = v->offset + roffset;
1641       unsigned int t;
1642
1643       if (v->is_full_var)
1644         fieldoffset = v->offset;
1645       else if (roffset != 0)
1646         v = first_vi_for_offset (v, fieldoffset);
1647       /* If the access is outside of the variable we can ignore it.  */
1648       if (!v)
1649         continue;
1650
1651       do
1652         {
1653           t = find (v->id);
1654
1655           /* Adding edges from the special vars is pointless.
1656              They don't have sets that can change.  */
1657           if (get_varinfo (t)->is_special_var)
1658             flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1659           /* Merging the solution from ESCAPED needlessly increases
1660              the set.  Use ESCAPED as representative instead.  */
1661           else if (v->id == escaped_id)
1662             flag |= bitmap_set_bit (sol, escaped_id);
1663           else if (add_graph_edge (graph, lhs, t))
1664             flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1665
1666           /* If the variable is not exactly at the requested offset
1667              we have to include the next one.  */
1668           if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1669               || v->next == NULL)
1670             break;
1671
1672           v = v->next;
1673           fieldoffset = v->offset;
1674         }
1675       while (1);
1676     }
1677
1678 done:
1679   /* If the LHS solution changed, mark the var as changed.  */
1680   if (flag)
1681     {
1682       get_varinfo (lhs)->solution = sol;
1683       if (!TEST_BIT (changed, lhs))
1684         {
1685           SET_BIT (changed, lhs);
1686           changed_count++;
1687         }
1688     }
1689 }
1690
1691 /* Process a constraint C that represents *(x + off) = y using DELTA
1692    as the starting solution for x.  */
1693
1694 static void
1695 do_ds_constraint (constraint_t c, bitmap delta)
1696 {
1697   unsigned int rhs = c->rhs.var;
1698   bitmap sol = get_varinfo (rhs)->solution;
1699   unsigned int j;
1700   bitmap_iterator bi;
1701   HOST_WIDE_INT loff = c->lhs.offset;
1702
1703   /* Our IL does not allow this.  */
1704   gcc_assert (c->rhs.offset == 0);
1705
1706   /* If the solution of y contains ANYTHING simply use the ANYTHING
1707      solution.  This avoids needlessly increasing the points-to sets.  */
1708   if (bitmap_bit_p (sol, anything_id))
1709     sol = get_varinfo (find (anything_id))->solution;
1710
1711   /* If the solution for x contains ANYTHING we have to merge the
1712      solution of y into all pointer variables which we do via
1713      STOREDANYTHING.  */
1714   if (bitmap_bit_p (delta, anything_id))
1715     {
1716       unsigned t = find (storedanything_id);
1717       if (add_graph_edge (graph, t, rhs))
1718         {
1719           if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1720             {
1721               if (!TEST_BIT (changed, t))
1722                 {
1723                   SET_BIT (changed, t);
1724                   changed_count++;
1725                 }
1726             }
1727         }
1728       return;
1729     }
1730
1731   /* If we do not know at with offset the rhs is dereferenced compute
1732      the reachability set of DELTA, conservatively assuming it is
1733      dereferenced at all valid offsets.  */
1734   if (loff == UNKNOWN_OFFSET)
1735     {
1736       solution_set_expand (delta, delta);
1737       loff = 0;
1738     }
1739
1740   /* For each member j of delta (Sol(x)), add an edge from y to j and
1741      union Sol(y) into Sol(j) */
1742   EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1743     {
1744       varinfo_t v = get_varinfo (j);
1745       unsigned int t;
1746       HOST_WIDE_INT fieldoffset = v->offset + loff;
1747
1748       /* If v is a global variable then this is an escape point.  */
1749       if (v->is_global_var)
1750         {
1751           t = find (escaped_id);
1752           if (add_graph_edge (graph, t, rhs)
1753               && bitmap_ior_into (get_varinfo (t)->solution, sol)
1754               && !TEST_BIT (changed, t))
1755             {
1756               SET_BIT (changed, t);
1757               changed_count++;
1758             }
1759         }
1760
1761       if (v->is_special_var)
1762         continue;
1763
1764       if (v->is_full_var)
1765         fieldoffset = v->offset;
1766       else if (loff != 0)
1767         v = first_vi_for_offset (v, fieldoffset);
1768       /* If the access is outside of the variable we can ignore it.  */
1769       if (!v)
1770         continue;
1771
1772       do
1773         {
1774           if (v->may_have_pointers)
1775             {
1776               t = find (v->id);
1777               if (add_graph_edge (graph, t, rhs)
1778                   && bitmap_ior_into (get_varinfo (t)->solution, sol)
1779                   && !TEST_BIT (changed, t))
1780                 {
1781                   SET_BIT (changed, t);
1782                   changed_count++;
1783                 }
1784             }
1785
1786           /* If the variable is not exactly at the requested offset
1787              we have to include the next one.  */
1788           if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1789               || v->next == NULL)
1790             break;
1791
1792           v = v->next;
1793           fieldoffset = v->offset;
1794         }
1795       while (1);
1796     }
1797 }
1798
1799 /* Handle a non-simple (simple meaning requires no iteration),
1800    constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved).  */
1801
1802 static void
1803 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1804 {
1805   if (c->lhs.type == DEREF)
1806     {
1807       if (c->rhs.type == ADDRESSOF)
1808         {
1809           gcc_unreachable();
1810         }
1811       else
1812         {
1813           /* *x = y */
1814           do_ds_constraint (c, delta);
1815         }
1816     }
1817   else if (c->rhs.type == DEREF)
1818     {
1819       /* x = *y */
1820       if (!(get_varinfo (c->lhs.var)->is_special_var))
1821         do_sd_constraint (graph, c, delta);
1822     }
1823   else
1824     {
1825       bitmap tmp;
1826       bitmap solution;
1827       bool flag = false;
1828
1829       gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1830       solution = get_varinfo (c->rhs.var)->solution;
1831       tmp = get_varinfo (c->lhs.var)->solution;
1832
1833       flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1834
1835       if (flag)
1836         {
1837           get_varinfo (c->lhs.var)->solution = tmp;
1838           if (!TEST_BIT (changed, c->lhs.var))
1839             {
1840               SET_BIT (changed, c->lhs.var);
1841               changed_count++;
1842             }
1843         }
1844     }
1845 }
1846
1847 /* Initialize and return a new SCC info structure.  */
1848
1849 static struct scc_info *
1850 init_scc_info (size_t size)
1851 {
1852   struct scc_info *si = XNEW (struct scc_info);
1853   size_t i;
1854
1855   si->current_index = 0;
1856   si->visited = sbitmap_alloc (size);
1857   sbitmap_zero (si->visited);
1858   si->deleted = sbitmap_alloc (size);
1859   sbitmap_zero (si->deleted);
1860   si->node_mapping = XNEWVEC (unsigned int, size);
1861   si->dfs = XCNEWVEC (unsigned int, size);
1862
1863   for (i = 0; i < size; i++)
1864     si->node_mapping[i] = i;
1865
1866   si->scc_stack = VEC_alloc (unsigned, heap, 1);
1867   return si;
1868 }
1869
1870 /* Free an SCC info structure pointed to by SI */
1871
1872 static void
1873 free_scc_info (struct scc_info *si)
1874 {
1875   sbitmap_free (si->visited);
1876   sbitmap_free (si->deleted);
1877   free (si->node_mapping);
1878   free (si->dfs);
1879   VEC_free (unsigned, heap, si->scc_stack);
1880   free (si);
1881 }
1882
1883
1884 /* Find indirect cycles in GRAPH that occur, using strongly connected
1885    components, and note them in the indirect cycles map.
1886
1887    This technique comes from Ben Hardekopf and Calvin Lin,
1888    "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1889    Lines of Code", submitted to PLDI 2007.  */
1890
1891 static void
1892 find_indirect_cycles (constraint_graph_t graph)
1893 {
1894   unsigned int i;
1895   unsigned int size = graph->size;
1896   struct scc_info *si = init_scc_info (size);
1897
1898   for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1899     if (!TEST_BIT (si->visited, i) && find (i) == i)
1900       scc_visit (graph, si, i);
1901
1902   free_scc_info (si);
1903 }
1904
1905 /* Compute a topological ordering for GRAPH, and store the result in the
1906    topo_info structure TI.  */
1907
1908 static void
1909 compute_topo_order (constraint_graph_t graph,
1910                     struct topo_info *ti)
1911 {
1912   unsigned int i;
1913   unsigned int size = graph->size;
1914
1915   for (i = 0; i != size; ++i)
1916     if (!TEST_BIT (ti->visited, i) && find (i) == i)
1917       topo_visit (graph, ti, i);
1918 }
1919
1920 /* Structure used to for hash value numbering of pointer equivalence
1921    classes.  */
1922
1923 typedef struct equiv_class_label
1924 {
1925   hashval_t hashcode;
1926   unsigned int equivalence_class;
1927   bitmap labels;
1928 } *equiv_class_label_t;
1929 typedef const struct equiv_class_label *const_equiv_class_label_t;
1930
1931 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1932    classes.  */
1933 static htab_t pointer_equiv_class_table;
1934
1935 /* A hashtable for mapping a bitmap of labels->location equivalence
1936    classes.  */
1937 static htab_t location_equiv_class_table;
1938
1939 /* Hash function for a equiv_class_label_t */
1940
1941 static hashval_t
1942 equiv_class_label_hash (const void *p)
1943 {
1944   const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1945   return ecl->hashcode;
1946 }
1947
1948 /* Equality function for two equiv_class_label_t's.  */
1949
1950 static int
1951 equiv_class_label_eq (const void *p1, const void *p2)
1952 {
1953   const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1954   const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1955   return (eql1->hashcode == eql2->hashcode
1956           && bitmap_equal_p (eql1->labels, eql2->labels));
1957 }
1958
1959 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1960    contains.  */
1961
1962 static unsigned int
1963 equiv_class_lookup (htab_t table, bitmap labels)
1964 {
1965   void **slot;
1966   struct equiv_class_label ecl;
1967
1968   ecl.labels = labels;
1969   ecl.hashcode = bitmap_hash (labels);
1970
1971   slot = htab_find_slot_with_hash (table, &ecl,
1972                                    ecl.hashcode, NO_INSERT);
1973   if (!slot)
1974     return 0;
1975   else
1976     return ((equiv_class_label_t) *slot)->equivalence_class;
1977 }
1978
1979
1980 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1981    to TABLE.  */
1982
1983 static void
1984 equiv_class_add (htab_t table, unsigned int equivalence_class,
1985                  bitmap labels)
1986 {
1987   void **slot;
1988   equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1989
1990   ecl->labels = labels;
1991   ecl->equivalence_class = equivalence_class;
1992   ecl->hashcode = bitmap_hash (labels);
1993
1994   slot = htab_find_slot_with_hash (table, ecl,
1995                                    ecl->hashcode, INSERT);
1996   gcc_assert (!*slot);
1997   *slot = (void *) ecl;
1998 }
1999
2000 /* Perform offline variable substitution.
2001
2002    This is a worst case quadratic time way of identifying variables
2003    that must have equivalent points-to sets, including those caused by
2004    static cycles, and single entry subgraphs, in the constraint graph.
2005
2006    The technique is described in "Exploiting Pointer and Location
2007    Equivalence to Optimize Pointer Analysis. In the 14th International
2008    Static Analysis Symposium (SAS), August 2007."  It is known as the
2009    "HU" algorithm, and is equivalent to value numbering the collapsed
2010    constraint graph including evaluating unions.
2011
2012    The general method of finding equivalence classes is as follows:
2013    Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
2014    Initialize all non-REF nodes to be direct nodes.
2015    For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
2016    variable}
2017    For each constraint containing the dereference, we also do the same
2018    thing.
2019
2020    We then compute SCC's in the graph and unify nodes in the same SCC,
2021    including pts sets.
2022
2023    For each non-collapsed node x:
2024     Visit all unvisited explicit incoming edges.
2025     Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
2026     where y->x.
2027     Lookup the equivalence class for pts(x).
2028      If we found one, equivalence_class(x) = found class.
2029      Otherwise, equivalence_class(x) = new class, and new_class is
2030     added to the lookup table.
2031
2032    All direct nodes with the same equivalence class can be replaced
2033    with a single representative node.
2034    All unlabeled nodes (label == 0) are not pointers and all edges
2035    involving them can be eliminated.
2036    We perform these optimizations during rewrite_constraints
2037
2038    In addition to pointer equivalence class finding, we also perform
2039    location equivalence class finding.  This is the set of variables
2040    that always appear together in points-to sets.  We use this to
2041    compress the size of the points-to sets.  */
2042
2043 /* Current maximum pointer equivalence class id.  */
2044 static int pointer_equiv_class;
2045
2046 /* Current maximum location equivalence class id.  */
2047 static int location_equiv_class;
2048
2049 /* Recursive routine to find strongly connected components in GRAPH,
2050    and label it's nodes with DFS numbers.  */
2051
2052 static void
2053 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2054 {
2055   unsigned int i;
2056   bitmap_iterator bi;
2057   unsigned int my_dfs;
2058
2059   gcc_assert (si->node_mapping[n] == n);
2060   SET_BIT (si->visited, n);
2061   si->dfs[n] = si->current_index ++;
2062   my_dfs = si->dfs[n];
2063
2064   /* Visit all the successors.  */
2065   EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2066     {
2067       unsigned int w = si->node_mapping[i];
2068
2069       if (TEST_BIT (si->deleted, w))
2070         continue;
2071
2072       if (!TEST_BIT (si->visited, w))
2073         condense_visit (graph, si, w);
2074       {
2075         unsigned int t = si->node_mapping[w];
2076         unsigned int nnode = si->node_mapping[n];
2077         gcc_assert (nnode == n);
2078
2079         if (si->dfs[t] < si->dfs[nnode])
2080           si->dfs[n] = si->dfs[t];
2081       }
2082     }
2083
2084   /* Visit all the implicit predecessors.  */
2085   EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2086     {
2087       unsigned int w = si->node_mapping[i];
2088
2089       if (TEST_BIT (si->deleted, w))
2090         continue;
2091
2092       if (!TEST_BIT (si->visited, w))
2093         condense_visit (graph, si, w);
2094       {
2095         unsigned int t = si->node_mapping[w];
2096         unsigned int nnode = si->node_mapping[n];
2097         gcc_assert (nnode == n);
2098
2099         if (si->dfs[t] < si->dfs[nnode])
2100           si->dfs[n] = si->dfs[t];
2101       }
2102     }
2103
2104   /* See if any components have been identified.  */
2105   if (si->dfs[n] == my_dfs)
2106     {
2107       while (VEC_length (unsigned, si->scc_stack) != 0
2108              && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
2109         {
2110           unsigned int w = VEC_pop (unsigned, si->scc_stack);
2111           si->node_mapping[w] = n;
2112
2113           if (!TEST_BIT (graph->direct_nodes, w))
2114             RESET_BIT (graph->direct_nodes, n);
2115
2116           /* Unify our nodes.  */
2117           if (graph->preds[w])
2118             {
2119               if (!graph->preds[n])
2120                 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2121               bitmap_ior_into (graph->preds[n], graph->preds[w]);
2122             }
2123           if (graph->implicit_preds[w])
2124             {
2125               if (!graph->implicit_preds[n])
2126                 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2127               bitmap_ior_into (graph->implicit_preds[n],
2128                                graph->implicit_preds[w]);
2129             }
2130           if (graph->points_to[w])
2131             {
2132               if (!graph->points_to[n])
2133                 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2134               bitmap_ior_into (graph->points_to[n],
2135                                graph->points_to[w]);
2136             }
2137         }
2138       SET_BIT (si->deleted, n);
2139     }
2140   else
2141     VEC_safe_push (unsigned, heap, si->scc_stack, n);
2142 }
2143
2144 /* Label pointer equivalences.  */
2145
2146 static void
2147 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2148 {
2149   unsigned int i;
2150   bitmap_iterator bi;
2151   SET_BIT (si->visited, n);
2152
2153   if (!graph->points_to[n])
2154     graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2155
2156   /* Label and union our incoming edges's points to sets.  */
2157   EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2158     {
2159       unsigned int w = si->node_mapping[i];
2160       if (!TEST_BIT (si->visited, w))
2161         label_visit (graph, si, w);
2162
2163       /* Skip unused edges  */
2164       if (w == n || graph->pointer_label[w] == 0)
2165         continue;
2166
2167       if (graph->points_to[w])
2168         bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2169     }
2170   /* Indirect nodes get fresh variables.  */
2171   if (!TEST_BIT (graph->direct_nodes, n))
2172     bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2173
2174   if (!bitmap_empty_p (graph->points_to[n]))
2175     {
2176       unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2177                                                graph->points_to[n]);
2178       if (!label)
2179         {
2180           label = pointer_equiv_class++;
2181           equiv_class_add (pointer_equiv_class_table,
2182                            label, graph->points_to[n]);
2183         }
2184       graph->pointer_label[n] = label;
2185     }
2186 }
2187
2188 /* Perform offline variable substitution, discovering equivalence
2189    classes, and eliminating non-pointer variables.  */
2190
2191 static struct scc_info *
2192 perform_var_substitution (constraint_graph_t graph)
2193 {
2194   unsigned int i;
2195   unsigned int size = graph->size;
2196   struct scc_info *si = init_scc_info (size);
2197
2198   bitmap_obstack_initialize (&iteration_obstack);
2199   pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2200                                            equiv_class_label_eq, free);
2201   location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2202                                             equiv_class_label_eq, free);
2203   pointer_equiv_class = 1;
2204   location_equiv_class = 1;
2205
2206   /* Condense the nodes, which means to find SCC's, count incoming
2207      predecessors, and unite nodes in SCC's.  */
2208   for (i = 0; i < FIRST_REF_NODE; i++)
2209     if (!TEST_BIT (si->visited, si->node_mapping[i]))
2210       condense_visit (graph, si, si->node_mapping[i]);
2211
2212   sbitmap_zero (si->visited);
2213   /* Actually the label the nodes for pointer equivalences  */
2214   for (i = 0; i < FIRST_REF_NODE; i++)
2215     if (!TEST_BIT (si->visited, si->node_mapping[i]))
2216       label_visit (graph, si, si->node_mapping[i]);
2217
2218   /* Calculate location equivalence labels.  */
2219   for (i = 0; i < FIRST_REF_NODE; i++)
2220     {
2221       bitmap pointed_by;
2222       bitmap_iterator bi;
2223       unsigned int j;
2224       unsigned int label;
2225
2226       if (!graph->pointed_by[i])
2227         continue;
2228       pointed_by = BITMAP_ALLOC (&iteration_obstack);
2229
2230       /* Translate the pointed-by mapping for pointer equivalence
2231          labels.  */
2232       EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2233         {
2234           bitmap_set_bit (pointed_by,
2235                           graph->pointer_label[si->node_mapping[j]]);
2236         }
2237       /* The original pointed_by is now dead.  */
2238       BITMAP_FREE (graph->pointed_by[i]);
2239
2240       /* Look up the location equivalence label if one exists, or make
2241          one otherwise.  */
2242       label = equiv_class_lookup (location_equiv_class_table,
2243                                   pointed_by);
2244       if (label == 0)
2245         {
2246           label = location_equiv_class++;
2247           equiv_class_add (location_equiv_class_table,
2248                            label, pointed_by);
2249         }
2250       else
2251         {
2252           if (dump_file && (dump_flags & TDF_DETAILS))
2253             fprintf (dump_file, "Found location equivalence for node %s\n",
2254                      get_varinfo (i)->name);
2255           BITMAP_FREE (pointed_by);
2256         }
2257       graph->loc_label[i] = label;
2258
2259     }
2260
2261   if (dump_file && (dump_flags & TDF_DETAILS))
2262     for (i = 0; i < FIRST_REF_NODE; i++)
2263       {
2264         bool direct_node = TEST_BIT (graph->direct_nodes, i);
2265         fprintf (dump_file,
2266                  "Equivalence classes for %s node id %d:%s are pointer: %d"
2267                  ", location:%d\n",
2268                  direct_node ? "Direct node" : "Indirect node", i,
2269                  get_varinfo (i)->name,
2270                  graph->pointer_label[si->node_mapping[i]],
2271                  graph->loc_label[si->node_mapping[i]]);
2272       }
2273
2274   /* Quickly eliminate our non-pointer variables.  */
2275
2276   for (i = 0; i < FIRST_REF_NODE; i++)
2277     {
2278       unsigned int node = si->node_mapping[i];
2279
2280       if (graph->pointer_label[node] == 0)
2281         {
2282           if (dump_file && (dump_flags & TDF_DETAILS))
2283             fprintf (dump_file,
2284                      "%s is a non-pointer variable, eliminating edges.\n",
2285                      get_varinfo (node)->name);
2286           stats.nonpointer_vars++;
2287           clear_edges_for_node (graph, node);
2288         }
2289     }
2290
2291   return si;
2292 }
2293
2294 /* Free information that was only necessary for variable
2295    substitution.  */
2296
2297 static void
2298 free_var_substitution_info (struct scc_info *si)
2299 {
2300   free_scc_info (si);
2301   free (graph->pointer_label);
2302   free (graph->loc_label);
2303   free (graph->pointed_by);
2304   free (graph->points_to);
2305   free (graph->eq_rep);
2306   sbitmap_free (graph->direct_nodes);
2307   htab_delete (pointer_equiv_class_table);
2308   htab_delete (location_equiv_class_table);
2309   bitmap_obstack_release (&iteration_obstack);
2310 }
2311
2312 /* Return an existing node that is equivalent to NODE, which has
2313    equivalence class LABEL, if one exists.  Return NODE otherwise.  */
2314
2315 static unsigned int
2316 find_equivalent_node (constraint_graph_t graph,
2317                       unsigned int node, unsigned int label)
2318 {
2319   /* If the address version of this variable is unused, we can
2320      substitute it for anything else with the same label.
2321      Otherwise, we know the pointers are equivalent, but not the
2322      locations, and we can unite them later.  */
2323
2324   if (!bitmap_bit_p (graph->address_taken, node))
2325     {
2326       gcc_assert (label < graph->size);
2327
2328       if (graph->eq_rep[label] != -1)
2329         {
2330           /* Unify the two variables since we know they are equivalent.  */
2331           if (unite (graph->eq_rep[label], node))
2332             unify_nodes (graph, graph->eq_rep[label], node, false);
2333           return graph->eq_rep[label];
2334         }
2335       else
2336         {
2337           graph->eq_rep[label] = node;
2338           graph->pe_rep[label] = node;
2339         }
2340     }
2341   else
2342     {
2343       gcc_assert (label < graph->size);
2344       graph->pe[node] = label;
2345       if (graph->pe_rep[label] == -1)
2346         graph->pe_rep[label] = node;
2347     }
2348
2349   return node;
2350 }
2351
2352 /* Unite pointer equivalent but not location equivalent nodes in
2353    GRAPH.  This may only be performed once variable substitution is
2354    finished.  */
2355
2356 static void
2357 unite_pointer_equivalences (constraint_graph_t graph)
2358 {
2359   unsigned int i;
2360
2361   /* Go through the pointer equivalences and unite them to their
2362      representative, if they aren't already.  */
2363   for (i = 0; i < FIRST_REF_NODE; i++)
2364     {
2365       unsigned int label = graph->pe[i];
2366       if (label)
2367         {
2368           int label_rep = graph->pe_rep[label];
2369
2370           if (label_rep == -1)
2371             continue;
2372
2373           label_rep = find (label_rep);
2374           if (label_rep >= 0 && unite (label_rep, find (i)))
2375             unify_nodes (graph, label_rep, i, false);
2376         }
2377     }
2378 }
2379
2380 /* Move complex constraints to the GRAPH nodes they belong to.  */
2381
2382 static void
2383 move_complex_constraints (constraint_graph_t graph)
2384 {
2385   int i;
2386   constraint_t c;
2387
2388   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2389     {
2390       if (c)
2391         {
2392           struct constraint_expr lhs = c->lhs;
2393           struct constraint_expr rhs = c->rhs;
2394
2395           if (lhs.type == DEREF)
2396             {
2397               insert_into_complex (graph, lhs.var, c);
2398             }
2399           else if (rhs.type == DEREF)
2400             {
2401               if (!(get_varinfo (lhs.var)->is_special_var))
2402                 insert_into_complex (graph, rhs.var, c);
2403             }
2404           else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2405                    && (lhs.offset != 0 || rhs.offset != 0))
2406             {
2407               insert_into_complex (graph, rhs.var, c);
2408             }
2409         }
2410     }
2411 }
2412
2413
2414 /* Optimize and rewrite complex constraints while performing
2415    collapsing of equivalent nodes.  SI is the SCC_INFO that is the
2416    result of perform_variable_substitution.  */
2417
2418 static void
2419 rewrite_constraints (constraint_graph_t graph,
2420                      struct scc_info *si)
2421 {
2422   int i;
2423   unsigned int j;
2424   constraint_t c;
2425
2426   for (j = 0; j < graph->size; j++)
2427     gcc_assert (find (j) == j);
2428
2429   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2430     {
2431       struct constraint_expr lhs = c->lhs;
2432       struct constraint_expr rhs = c->rhs;
2433       unsigned int lhsvar = find (lhs.var);
2434       unsigned int rhsvar = find (rhs.var);
2435       unsigned int lhsnode, rhsnode;
2436       unsigned int lhslabel, rhslabel;
2437
2438       lhsnode = si->node_mapping[lhsvar];
2439       rhsnode = si->node_mapping[rhsvar];
2440       lhslabel = graph->pointer_label[lhsnode];
2441       rhslabel = graph->pointer_label[rhsnode];
2442
2443       /* See if it is really a non-pointer variable, and if so, ignore
2444          the constraint.  */
2445       if (lhslabel == 0)
2446         {
2447           if (dump_file && (dump_flags & TDF_DETAILS))
2448             {
2449
2450               fprintf (dump_file, "%s is a non-pointer variable,"
2451                        "ignoring constraint:",
2452                        get_varinfo (lhs.var)->name);
2453               dump_constraint (dump_file, c);
2454             }
2455           VEC_replace (constraint_t, constraints, i, NULL);
2456           continue;
2457         }
2458
2459       if (rhslabel == 0)
2460         {
2461           if (dump_file && (dump_flags & TDF_DETAILS))
2462             {
2463
2464               fprintf (dump_file, "%s is a non-pointer variable,"
2465                        "ignoring constraint:",
2466                        get_varinfo (rhs.var)->name);
2467               dump_constraint (dump_file, c);
2468             }
2469           VEC_replace (constraint_t, constraints, i, NULL);
2470           continue;
2471         }
2472
2473       lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2474       rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2475       c->lhs.var = lhsvar;
2476       c->rhs.var = rhsvar;
2477
2478     }
2479 }
2480
2481 /* Eliminate indirect cycles involving NODE.  Return true if NODE was
2482    part of an SCC, false otherwise.  */
2483
2484 static bool
2485 eliminate_indirect_cycles (unsigned int node)
2486 {
2487   if (graph->indirect_cycles[node] != -1
2488       && !bitmap_empty_p (get_varinfo (node)->solution))
2489     {
2490       unsigned int i;
2491       VEC(unsigned,heap) *queue = NULL;
2492       int queuepos;
2493       unsigned int to = find (graph->indirect_cycles[node]);
2494       bitmap_iterator bi;
2495
2496       /* We can't touch the solution set and call unify_nodes
2497          at the same time, because unify_nodes is going to do
2498          bitmap unions into it. */
2499
2500       EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2501         {
2502           if (find (i) == i && i != to)
2503             {
2504               if (unite (to, i))
2505                 VEC_safe_push (unsigned, heap, queue, i);
2506             }
2507         }
2508
2509       for (queuepos = 0;
2510            VEC_iterate (unsigned, queue, queuepos, i);
2511            queuepos++)
2512         {
2513           unify_nodes (graph, to, i, true);
2514         }
2515       VEC_free (unsigned, heap, queue);
2516       return true;
2517     }
2518   return false;
2519 }
2520
2521 /* Solve the constraint graph GRAPH using our worklist solver.
2522    This is based on the PW* family of solvers from the "Efficient Field
2523    Sensitive Pointer Analysis for C" paper.
2524    It works by iterating over all the graph nodes, processing the complex
2525    constraints and propagating the copy constraints, until everything stops
2526    changed.  This corresponds to steps 6-8 in the solving list given above.  */
2527
2528 static void
2529 solve_graph (constraint_graph_t graph)
2530 {
2531   unsigned int size = graph->size;
2532   unsigned int i;
2533   bitmap pts;
2534
2535   changed_count = 0;
2536   changed = sbitmap_alloc (size);
2537   sbitmap_zero (changed);
2538
2539   /* Mark all initial non-collapsed nodes as changed.  */
2540   for (i = 0; i < size; i++)
2541     {
2542       varinfo_t ivi = get_varinfo (i);
2543       if (find (i) == i && !bitmap_empty_p (ivi->solution)
2544           && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2545               || VEC_length (constraint_t, graph->complex[i]) > 0))
2546         {
2547           SET_BIT (changed, i);
2548           changed_count++;
2549         }
2550     }
2551
2552   /* Allocate a bitmap to be used to store the changed bits.  */
2553   pts = BITMAP_ALLOC (&pta_obstack);
2554
2555   while (changed_count > 0)
2556     {
2557       unsigned int i;
2558       struct topo_info *ti = init_topo_info ();
2559       stats.iterations++;
2560
2561       bitmap_obstack_initialize (&iteration_obstack);
2562
2563       compute_topo_order (graph, ti);
2564
2565       while (VEC_length (unsigned, ti->topo_order) != 0)
2566         {
2567
2568           i = VEC_pop (unsigned, ti->topo_order);
2569
2570           /* If this variable is not a representative, skip it.  */
2571           if (find (i) != i)
2572             continue;
2573
2574           /* In certain indirect cycle cases, we may merge this
2575              variable to another.  */
2576           if (eliminate_indirect_cycles (i) && find (i) != i)
2577             continue;
2578
2579           /* If the node has changed, we need to process the
2580              complex constraints and outgoing edges again.  */
2581           if (TEST_BIT (changed, i))
2582             {
2583               unsigned int j;
2584               constraint_t c;
2585               bitmap solution;
2586               VEC(constraint_t,heap) *complex = graph->complex[i];
2587               bool solution_empty;
2588
2589               RESET_BIT (changed, i);
2590               changed_count--;
2591
2592               /* Compute the changed set of solution bits.  */
2593               bitmap_and_compl (pts, get_varinfo (i)->solution,
2594                                 get_varinfo (i)->oldsolution);
2595
2596               if (bitmap_empty_p (pts))
2597                 continue;
2598
2599               bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2600
2601               solution = get_varinfo (i)->solution;
2602               solution_empty = bitmap_empty_p (solution);
2603
2604               /* Process the complex constraints */
2605               for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2606                 {
2607                   /* XXX: This is going to unsort the constraints in
2608                      some cases, which will occasionally add duplicate
2609                      constraints during unification.  This does not
2610                      affect correctness.  */
2611                   c->lhs.var = find (c->lhs.var);
2612                   c->rhs.var = find (c->rhs.var);
2613
2614                   /* The only complex constraint that can change our
2615                      solution to non-empty, given an empty solution,
2616                      is a constraint where the lhs side is receiving
2617                      some set from elsewhere.  */
2618                   if (!solution_empty || c->lhs.type != DEREF)
2619                     do_complex_constraint (graph, c, pts);
2620                 }
2621
2622               solution_empty = bitmap_empty_p (solution);
2623
2624               if (!solution_empty)
2625                 {
2626                   bitmap_iterator bi;
2627                   unsigned eff_escaped_id = find (escaped_id);
2628
2629                   /* Propagate solution to all successors.  */
2630                   EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2631                                                 0, j, bi)
2632                     {
2633                       bitmap tmp;
2634                       bool flag;
2635
2636                       unsigned int to = find (j);
2637                       tmp = get_varinfo (to)->solution;
2638                       flag = false;
2639
2640                       /* Don't try to propagate to ourselves.  */
2641                       if (to == i)
2642                         continue;
2643
2644                       /* If we propagate from ESCAPED use ESCAPED as
2645                          placeholder.  */
2646                       if (i == eff_escaped_id)
2647                         flag = bitmap_set_bit (tmp, escaped_id);
2648                       else
2649                         flag = set_union_with_increment (tmp, pts, 0);
2650
2651                       if (flag)
2652                         {
2653                           get_varinfo (to)->solution = tmp;
2654                           if (!TEST_BIT (changed, to))
2655                             {
2656                               SET_BIT (changed, to);
2657                               changed_count++;
2658                             }
2659                         }
2660                     }
2661                 }
2662             }
2663         }
2664       free_topo_info (ti);
2665       bitmap_obstack_release (&iteration_obstack);
2666     }
2667
2668   BITMAP_FREE (pts);
2669   sbitmap_free (changed);
2670   bitmap_obstack_release (&oldpta_obstack);
2671 }
2672
2673 /* Map from trees to variable infos.  */
2674 static struct pointer_map_t *vi_for_tree;
2675
2676
2677 /* Insert ID as the variable id for tree T in the vi_for_tree map.  */
2678
2679 static void
2680 insert_vi_for_tree (tree t, varinfo_t vi)
2681 {
2682   void **slot = pointer_map_insert (vi_for_tree, t);
2683   gcc_assert (vi);
2684   gcc_assert (*slot == NULL);
2685   *slot = vi;
2686 }
2687
2688 /* Find the variable info for tree T in VI_FOR_TREE.  If T does not
2689    exist in the map, return NULL, otherwise, return the varinfo we found.  */
2690
2691 static varinfo_t
2692 lookup_vi_for_tree (tree t)
2693 {
2694   void **slot = pointer_map_contains (vi_for_tree, t);
2695   if (slot == NULL)
2696     return NULL;
2697
2698   return (varinfo_t) *slot;
2699 }
2700
2701 /* Return a printable name for DECL  */
2702
2703 static const char *
2704 alias_get_name (tree decl)
2705 {
2706   const char *res = get_name (decl);
2707   char *temp;
2708   int num_printed = 0;
2709
2710   if (res != NULL)
2711     return res;
2712
2713   res = "NULL";
2714   if (!dump_file)
2715     return res;
2716
2717   if (TREE_CODE (decl) == SSA_NAME)
2718     {
2719       num_printed = asprintf (&temp, "%s_%u",
2720                               alias_get_name (SSA_NAME_VAR (decl)),
2721                               SSA_NAME_VERSION (decl));
2722     }
2723   else if (DECL_P (decl))
2724     {
2725       num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2726     }
2727   if (num_printed > 0)
2728     {
2729       res = ggc_strdup (temp);
2730       free (temp);
2731     }
2732   return res;
2733 }
2734
2735 /* Find the variable id for tree T in the map.
2736    If T doesn't exist in the map, create an entry for it and return it.  */
2737
2738 static varinfo_t
2739 get_vi_for_tree (tree t)
2740 {
2741   void **slot = pointer_map_contains (vi_for_tree, t);
2742   if (slot == NULL)
2743     return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2744
2745   return (varinfo_t) *slot;
2746 }
2747
2748 /* Get a scalar constraint expression for a new temporary variable.  */
2749
2750 static struct constraint_expr
2751 new_scalar_tmp_constraint_exp (const char *name)
2752 {
2753   struct constraint_expr tmp;
2754   varinfo_t vi;
2755
2756   vi = new_var_info (NULL_TREE, name);
2757   vi->offset = 0;
2758   vi->size = -1;
2759   vi->fullsize = -1;
2760   vi->is_full_var = 1;
2761
2762   tmp.var = vi->id;
2763   tmp.type = SCALAR;
2764   tmp.offset = 0;
2765
2766   return tmp;
2767 }
2768
2769 /* Get a constraint expression vector from an SSA_VAR_P node.
2770    If address_p is true, the result will be taken its address of.  */
2771
2772 static void
2773 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2774 {
2775   struct constraint_expr cexpr;
2776   varinfo_t vi;
2777
2778   /* We allow FUNCTION_DECLs here even though it doesn't make much sense.  */
2779   gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2780
2781   /* For parameters, get at the points-to set for the actual parm
2782      decl.  */
2783   if (TREE_CODE (t) == SSA_NAME
2784       && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2785       && SSA_NAME_IS_DEFAULT_DEF (t))
2786     {
2787       get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2788       return;
2789     }
2790
2791   vi = get_vi_for_tree (t);
2792   cexpr.var = vi->id;
2793   cexpr.type = SCALAR;
2794   cexpr.offset = 0;
2795   /* If we determine the result is "anything", and we know this is readonly,
2796      say it points to readonly memory instead.  */
2797   if (cexpr.var == anything_id && TREE_READONLY (t))
2798     {
2799       gcc_unreachable ();
2800       cexpr.type = ADDRESSOF;
2801       cexpr.var = readonly_id;
2802     }
2803
2804   /* If we are not taking the address of the constraint expr, add all
2805      sub-fiels of the variable as well.  */
2806   if (!address_p
2807       && !vi->is_full_var)
2808     {
2809       for (; vi; vi = vi->next)
2810         {
2811           cexpr.var = vi->id;
2812           VEC_safe_push (ce_s, heap, *results, &cexpr);
2813         }
2814       return;
2815     }
2816
2817   VEC_safe_push (ce_s, heap, *results, &cexpr);
2818 }
2819
2820 /* Process constraint T, performing various simplifications and then
2821    adding it to our list of overall constraints.  */
2822
2823 static void
2824 process_constraint (constraint_t t)
2825 {
2826   struct constraint_expr rhs = t->rhs;
2827   struct constraint_expr lhs = t->lhs;
2828
2829   gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2830   gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2831
2832   /* If we didn't get any useful constraint from the lhs we get
2833      &ANYTHING as fallback from get_constraint_for.  Deal with
2834      it here by turning it into *ANYTHING.  */
2835   if (lhs.type == ADDRESSOF
2836       && lhs.var == anything_id)
2837     lhs.type = DEREF;
2838
2839   /* ADDRESSOF on the lhs is invalid.  */
2840   gcc_assert (lhs.type != ADDRESSOF);
2841
2842   /* This can happen in our IR with things like n->a = *p */
2843   if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2844     {
2845       /* Split into tmp = *rhs, *lhs = tmp */
2846       struct constraint_expr tmplhs;
2847       tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
2848       process_constraint (new_constraint (tmplhs, rhs));
2849       process_constraint (new_constraint (lhs, tmplhs));
2850     }
2851   else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2852     {
2853       /* Split into tmp = &rhs, *lhs = tmp */
2854       struct constraint_expr tmplhs;
2855       tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
2856       process_constraint (new_constraint (tmplhs, rhs));
2857       process_constraint (new_constraint (lhs, tmplhs));
2858     }
2859   else
2860     {
2861       gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2862       VEC_safe_push (constraint_t, heap, constraints, t);
2863     }
2864 }
2865
2866 /* Return true if T is a type that could contain pointers.  */
2867
2868 static bool
2869 type_could_have_pointers (tree type)
2870 {
2871   if (POINTER_TYPE_P (type))
2872     return true;
2873
2874   if (TREE_CODE (type) == ARRAY_TYPE)
2875     return type_could_have_pointers (TREE_TYPE (type));
2876
2877   return AGGREGATE_TYPE_P (type);
2878 }
2879
2880 /* Return true if T is a variable of a type that could contain
2881    pointers.  */
2882
2883 static bool
2884 could_have_pointers (tree t)
2885 {
2886   return type_could_have_pointers (TREE_TYPE (t));
2887 }
2888
2889 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2890    structure.  */
2891
2892 static HOST_WIDE_INT
2893 bitpos_of_field (const tree fdecl)
2894 {
2895
2896   if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2897       || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2898     return -1;
2899
2900   return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2901           + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2902 }
2903
2904
2905 /* Get constraint expressions for offsetting PTR by OFFSET.  Stores the
2906    resulting constraint expressions in *RESULTS.  */
2907
2908 static void
2909 get_constraint_for_ptr_offset (tree ptr, tree offset,
2910                                VEC (ce_s, heap) **results)
2911 {
2912   struct constraint_expr c;
2913   unsigned int j, n;
2914   HOST_WIDE_INT rhsunitoffset, rhsoffset;
2915
2916   /* If we do not do field-sensitive PTA adding offsets to pointers
2917      does not change the points-to solution.  */
2918   if (!use_field_sensitive)
2919     {
2920       get_constraint_for (ptr, results);
2921       return;
2922     }
2923
2924   /* If the offset is not a non-negative integer constant that fits
2925      in a HOST_WIDE_INT, we have to fall back to a conservative
2926      solution which includes all sub-fields of all pointed-to
2927      variables of ptr.  */
2928   if (offset == NULL_TREE
2929       || !host_integerp (offset, 0))
2930     rhsoffset = UNKNOWN_OFFSET;
2931   else
2932     {
2933       /* Make sure the bit-offset also fits.  */
2934       rhsunitoffset = TREE_INT_CST_LOW (offset);
2935       rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2936       if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2937         rhsoffset = UNKNOWN_OFFSET;
2938     }
2939
2940   get_constraint_for (ptr, results);
2941   if (rhsoffset == 0)
2942     return;
2943
2944   /* As we are eventually appending to the solution do not use
2945      VEC_iterate here.  */
2946   n = VEC_length (ce_s, *results);
2947   for (j = 0; j < n; j++)
2948     {
2949       varinfo_t curr;
2950       c = *VEC_index (ce_s, *results, j);
2951       curr = get_varinfo (c.var);
2952
2953       if (c.type == ADDRESSOF
2954           /* If this varinfo represents a full variable just use it.  */
2955           && curr->is_full_var)
2956         c.offset = 0;
2957       else if (c.type == ADDRESSOF
2958                /* If we do not know the offset add all subfields.  */
2959                && rhsoffset == UNKNOWN_OFFSET)
2960         {
2961           varinfo_t temp = lookup_vi_for_tree (curr->decl);
2962           do
2963             {
2964               struct constraint_expr c2;
2965               c2.var = temp->id;
2966               c2.type = ADDRESSOF;
2967               c2.offset = 0;
2968               if (c2.var != c.var)
2969                 VEC_safe_push (ce_s, heap, *results, &c2);
2970               temp = temp->next;
2971             }
2972           while (temp);
2973         }
2974       else if (c.type == ADDRESSOF)
2975         {
2976           varinfo_t temp;
2977           unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
2978
2979           /* Search the sub-field which overlaps with the
2980              pointed-to offset.  If the result is outside of the variable
2981              we have to provide a conservative result, as the variable is
2982              still reachable from the resulting pointer (even though it
2983              technically cannot point to anything).  The last and first
2984              sub-fields are such conservative results.
2985              ???  If we always had a sub-field for &object + 1 then
2986              we could represent this in a more precise way.  */
2987           if (rhsoffset < 0
2988               && curr->offset < offset)
2989             offset = 0;
2990           temp = first_or_preceding_vi_for_offset (curr, offset);
2991
2992           /* If the found variable is not exactly at the pointed to
2993              result, we have to include the next variable in the
2994              solution as well.  Otherwise two increments by offset / 2
2995              do not result in the same or a conservative superset
2996              solution.  */
2997           if (temp->offset != offset
2998               && temp->next != NULL)
2999             {
3000               struct constraint_expr c2;
3001               c2.var = temp->next->id;
3002               c2.type = ADDRESSOF;
3003               c2.offset = 0;
3004               VEC_safe_push (ce_s, heap, *results, &c2);
3005             }
3006           c.var = temp->id;
3007           c.offset = 0;
3008         }
3009       else
3010         c.offset = rhsoffset;
3011
3012       VEC_replace (ce_s, *results, j, &c);
3013     }
3014 }
3015
3016
3017 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3018    If address_p is true the result will be taken its address of.  */
3019
3020 static void
3021 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
3022                                   bool address_p)
3023 {
3024   tree orig_t = t;
3025   HOST_WIDE_INT bitsize = -1;
3026   HOST_WIDE_INT bitmaxsize = -1;
3027   HOST_WIDE_INT bitpos;
3028   tree forzero;
3029   struct constraint_expr *result;
3030
3031   /* Some people like to do cute things like take the address of
3032      &0->a.b */
3033   forzero = t;
3034   while (handled_component_p (forzero)
3035          || INDIRECT_REF_P (forzero))
3036     forzero = TREE_OPERAND (forzero, 0);
3037
3038   if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3039     {
3040       struct constraint_expr temp;
3041
3042       temp.offset = 0;
3043       temp.var = integer_id;
3044       temp.type = SCALAR;
3045       VEC_safe_push (ce_s, heap, *results, &temp);
3046       return;
3047     }
3048
3049   t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
3050
3051   /* Pretend to take the address of the base, we'll take care of
3052      adding the required subset of sub-fields below.  */
3053   get_constraint_for_1 (t, results, true);
3054   gcc_assert (VEC_length (ce_s, *results) == 1);
3055   result = VEC_last (ce_s, *results);
3056
3057   if (result->type == SCALAR
3058       && get_varinfo (result->var)->is_full_var)
3059     /* For single-field vars do not bother about the offset.  */
3060     result->offset = 0;
3061   else if (result->type == SCALAR)
3062     {
3063       /* In languages like C, you can access one past the end of an
3064          array.  You aren't allowed to dereference it, so we can
3065          ignore this constraint. When we handle pointer subtraction,
3066          we may have to do something cute here.  */
3067
3068       if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
3069           && bitmaxsize != 0)
3070         {
3071           /* It's also not true that the constraint will actually start at the
3072              right offset, it may start in some padding.  We only care about
3073              setting the constraint to the first actual field it touches, so
3074              walk to find it.  */
3075           struct constraint_expr cexpr = *result;
3076           varinfo_t curr;
3077           VEC_pop (ce_s, *results);
3078           cexpr.offset = 0;
3079           for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
3080             {
3081               if (ranges_overlap_p (curr->offset, curr->size,
3082                                     bitpos, bitmaxsize))
3083                 {
3084                   cexpr.var = curr->id;
3085                   VEC_safe_push (ce_s, heap, *results, &cexpr);
3086                   if (address_p)
3087                     break;
3088                 }
3089             }
3090           /* If we are going to take the address of this field then
3091              to be able to compute reachability correctly add at least
3092              the last field of the variable.  */
3093           if (address_p
3094               && VEC_length (ce_s, *results) == 0)
3095             {
3096               curr = get_varinfo (cexpr.var);
3097               while (curr->next != NULL)
3098                 curr = curr->next;
3099               cexpr.var = curr->id;
3100               VEC_safe_push (ce_s, heap, *results, &cexpr);
3101             }
3102           else
3103             /* Assert that we found *some* field there. The user couldn't be
3104                accessing *only* padding.  */
3105             /* Still the user could access one past the end of an array
3106                embedded in a struct resulting in accessing *only* padding.  */
3107             gcc_assert (VEC_length (ce_s, *results) >= 1
3108                         || ref_contains_array_ref (orig_t));
3109         }
3110       else if (bitmaxsize == 0)
3111         {
3112           if (dump_file && (dump_flags & TDF_DETAILS))
3113             fprintf (dump_file, "Access to zero-sized part of variable,"
3114                      "ignoring\n");
3115         }
3116       else
3117         if (dump_file && (dump_flags & TDF_DETAILS))
3118           fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3119     }
3120   else if (result->type == DEREF)
3121     {
3122       /* If we do not know exactly where the access goes say so.  Note
3123          that only for non-structure accesses we know that we access
3124          at most one subfiled of any variable.  */
3125       if (bitpos == -1
3126           || bitsize != bitmaxsize
3127           || AGGREGATE_TYPE_P (TREE_TYPE (orig_t)))
3128         result->offset = UNKNOWN_OFFSET;
3129       else
3130         result->offset = bitpos;
3131     }
3132   else if (result->type == ADDRESSOF)
3133     {
3134       /* We can end up here for component references on a
3135          VIEW_CONVERT_EXPR <>(&foobar).  */
3136       result->type = SCALAR;
3137       result->var = anything_id;
3138       result->offset = 0;
3139     }
3140   else
3141     gcc_unreachable ();
3142 }
3143
3144
3145 /* Dereference the constraint expression CONS, and return the result.
3146    DEREF (ADDRESSOF) = SCALAR
3147    DEREF (SCALAR) = DEREF
3148    DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3149    This is needed so that we can handle dereferencing DEREF constraints.  */
3150
3151 static void
3152 do_deref (VEC (ce_s, heap) **constraints)
3153 {
3154   struct constraint_expr *c;
3155   unsigned int i = 0;
3156
3157   for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3158     {
3159       if (c->type == SCALAR)
3160         c->type = DEREF;
3161       else if (c->type == ADDRESSOF)
3162         c->type = SCALAR;
3163       else if (c->type == DEREF)
3164         {
3165           struct constraint_expr tmplhs;
3166           tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3167           process_constraint (new_constraint (tmplhs, *c));
3168           c->var = tmplhs.var;
3169         }
3170       else
3171         gcc_unreachable ();
3172     }
3173 }
3174
3175 static void get_constraint_for_1 (tree, VEC (ce_s, heap) **, bool);
3176
3177 /* Given a tree T, return the constraint expression for taking the
3178    address of it.  */
3179
3180 static void
3181 get_constraint_for_address_of (tree t, VEC (ce_s, heap) **results)
3182 {
3183   struct constraint_expr *c;
3184   unsigned int i;
3185
3186   get_constraint_for_1 (t, results, true);
3187
3188   for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3189     {
3190       if (c->type == DEREF)
3191         c->type = SCALAR;
3192       else
3193         c->type = ADDRESSOF;
3194     }
3195 }
3196
3197 /* Given a tree T, return the constraint expression for it.  */
3198
3199 static void
3200 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3201 {
3202   struct constraint_expr temp;
3203
3204   /* x = integer is all glommed to a single variable, which doesn't
3205      point to anything by itself.  That is, of course, unless it is an
3206      integer constant being treated as a pointer, in which case, we
3207      will return that this is really the addressof anything.  This
3208      happens below, since it will fall into the default case. The only
3209      case we know something about an integer treated like a pointer is
3210      when it is the NULL pointer, and then we just say it points to
3211      NULL.
3212
3213      Do not do that if -fno-delete-null-pointer-checks though, because
3214      in that case *NULL does not fail, so it _should_ alias *anything.
3215      It is not worth adding a new option or renaming the existing one,
3216      since this case is relatively obscure.  */
3217   if (flag_delete_null_pointer_checks
3218       && ((TREE_CODE (t) == INTEGER_CST
3219            && integer_zerop (t))
3220           /* The only valid CONSTRUCTORs in gimple with pointer typed
3221              elements are zero-initializer.  */
3222           || TREE_CODE (t) == CONSTRUCTOR))
3223     {
3224       temp.var = nothing_id;
3225       temp.type = ADDRESSOF;
3226       temp.offset = 0;
3227       VEC_safe_push (ce_s, heap, *results, &temp);
3228       return;
3229     }
3230
3231   /* String constants are read-only.  */
3232   if (TREE_CODE (t) == STRING_CST)
3233     {
3234       temp.var = readonly_id;
3235       temp.type = SCALAR;
3236       temp.offset = 0;
3237       VEC_safe_push (ce_s, heap, *results, &temp);
3238       return;
3239     }
3240
3241   switch (TREE_CODE_CLASS (TREE_CODE (t)))
3242     {
3243     case tcc_expression:
3244       {
3245         switch (TREE_CODE (t))
3246           {
3247           case ADDR_EXPR:
3248             get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3249             return;
3250           default:;
3251           }
3252         break;
3253       }
3254     case tcc_reference:
3255       {
3256         switch (TREE_CODE (t))
3257           {
3258           case INDIRECT_REF:
3259             {
3260               get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3261               do_deref (results);
3262               return;
3263             }
3264           case ARRAY_REF:
3265           case ARRAY_RANGE_REF:
3266           case COMPONENT_REF:
3267             get_constraint_for_component_ref (t, results, address_p);
3268             return;
3269           case VIEW_CONVERT_EXPR:
3270             get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3271             return;
3272           /* We are missing handling for TARGET_MEM_REF here.  */
3273           default:;
3274           }
3275         break;
3276       }
3277     case tcc_exceptional:
3278       {
3279         switch (TREE_CODE (t))
3280           {
3281           case SSA_NAME:
3282             {
3283               get_constraint_for_ssa_var (t, results, address_p);
3284               return;
3285             }
3286           default:;
3287           }
3288         break;
3289       }
3290     case tcc_declaration:
3291       {
3292         get_constraint_for_ssa_var (t, results, address_p);
3293         return;
3294       }
3295     default:;
3296     }
3297
3298   /* The default fallback is a constraint from anything.  */
3299   temp.type = ADDRESSOF;
3300   temp.var = anything_id;
3301   temp.offset = 0;
3302   VEC_safe_push (ce_s, heap, *results, &temp);
3303 }
3304
3305 /* Given a gimple tree T, return the constraint expression vector for it.  */
3306
3307 static void
3308 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3309 {
3310   gcc_assert (VEC_length (ce_s, *results) == 0);
3311
3312   get_constraint_for_1 (t, results, false);
3313 }
3314
3315
3316 /* Efficiently generates constraints from all entries in *RHSC to all
3317    entries in *LHSC.  */
3318
3319 static void
3320 process_all_all_constraints (VEC (ce_s, heap) *lhsc, VEC (ce_s, heap) *rhsc)
3321 {
3322   struct constraint_expr *lhsp, *rhsp;
3323   unsigned i, j;
3324
3325   if (VEC_length (ce_s, lhsc) <= 1
3326       || VEC_length (ce_s, rhsc) <= 1)
3327     {
3328       for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3329         for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); ++j)
3330           process_constraint (new_constraint (*lhsp, *rhsp));
3331     }
3332   else
3333     {
3334       struct constraint_expr tmp;
3335       tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3336       for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
3337         process_constraint (new_constraint (tmp, *rhsp));
3338       for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3339         process_constraint (new_constraint (*lhsp, tmp));
3340     }
3341 }
3342
3343 /* Handle aggregate copies by expanding into copies of the respective
3344    fields of the structures.  */
3345
3346 static void
3347 do_structure_copy (tree lhsop, tree rhsop)
3348 {
3349   struct constraint_expr *lhsp, *rhsp;
3350   VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3351   unsigned j;
3352
3353   get_constraint_for (lhsop, &lhsc);
3354   get_constraint_for (rhsop, &rhsc);
3355   lhsp = VEC_index (ce_s, lhsc, 0);
3356   rhsp = VEC_index (ce_s, rhsc, 0);
3357   if (lhsp->type == DEREF
3358       || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3359       || rhsp->type == DEREF)
3360     process_all_all_constraints (lhsc, rhsc);
3361   else if (lhsp->type == SCALAR
3362            && (rhsp->type == SCALAR
3363                || rhsp->type == ADDRESSOF))
3364     {
3365       HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3366       HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3367       unsigned k = 0;
3368       get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize);
3369       get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize);
3370       for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp);)
3371         {
3372           varinfo_t lhsv, rhsv;
3373           rhsp = VEC_index (ce_s, rhsc, k);
3374           lhsv = get_varinfo (lhsp->var);
3375           rhsv = get_varinfo (rhsp->var);
3376           if (lhsv->may_have_pointers
3377               && ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3378                                    rhsv->offset + lhsoffset, rhsv->size))
3379             process_constraint (new_constraint (*lhsp, *rhsp));
3380           if (lhsv->offset + rhsoffset + lhsv->size
3381               > rhsv->offset + lhsoffset + rhsv->size)
3382             {
3383               ++k;
3384               if (k >= VEC_length (ce_s, rhsc))
3385                 break;
3386             }
3387           else
3388             ++j;
3389         }
3390     }
3391   else
3392     gcc_unreachable ();
3393
3394   VEC_free (ce_s, heap, lhsc);
3395   VEC_free (ce_s, heap, rhsc);
3396 }
3397
3398 /* Create a constraint ID = OP.  */
3399
3400 static void
3401 make_constraint_to (unsigned id, tree op)
3402 {
3403   VEC(ce_s, heap) *rhsc = NULL;
3404   struct constraint_expr *c;
3405   struct constraint_expr includes;
3406   unsigned int j;
3407
3408   includes.var = id;
3409   includes.offset = 0;
3410   includes.type = SCALAR;
3411
3412   get_constraint_for (op, &rhsc);
3413   for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3414     process_constraint (new_constraint (includes, *c));
3415   VEC_free (ce_s, heap, rhsc);
3416 }
3417
3418 /* Create a constraint ID = &FROM.  */
3419
3420 static void
3421 make_constraint_from (varinfo_t vi, int from)
3422 {
3423   struct constraint_expr lhs, rhs;
3424
3425   lhs.var = vi->id;
3426   lhs.offset = 0;
3427   lhs.type = SCALAR;
3428
3429   rhs.var = from;
3430   rhs.offset = 0;
3431   rhs.type = ADDRESSOF;
3432   process_constraint (new_constraint (lhs, rhs));
3433 }
3434
3435 /* Create a constraint ID = FROM.  */
3436
3437 static void
3438 make_copy_constraint (varinfo_t vi, int from)
3439 {
3440   struct constraint_expr lhs, rhs;
3441
3442   lhs.var = vi->id;
3443   lhs.offset = 0;
3444   lhs.type = SCALAR;
3445
3446   rhs.var = from;
3447   rhs.offset = 0;
3448   rhs.type = SCALAR;
3449   process_constraint (new_constraint (lhs, rhs));
3450 }
3451
3452 /* Make constraints necessary to make OP escape.  */
3453
3454 static void
3455 make_escape_constraint (tree op)
3456 {
3457   make_constraint_to (escaped_id, op);
3458 }
3459
3460 /* Add constraints to that the solution of VI is transitively closed.  */
3461
3462 static void
3463 make_transitive_closure_constraints (varinfo_t vi)
3464 {
3465   struct constraint_expr lhs, rhs;
3466
3467   /* VAR = *VAR;  */
3468   lhs.type = SCALAR;
3469   lhs.var = vi->id;
3470   lhs.offset = 0;
3471   rhs.type = DEREF;
3472   rhs.var = vi->id;
3473   rhs.offset = 0;
3474   process_constraint (new_constraint (lhs, rhs));
3475
3476   /* VAR = VAR + UNKNOWN;  */
3477   lhs.type = SCALAR;
3478   lhs.var = vi->id;
3479   lhs.offset = 0;
3480   rhs.type = SCALAR;
3481   rhs.var = vi->id;
3482   rhs.offset = UNKNOWN_OFFSET;
3483   process_constraint (new_constraint (lhs, rhs));
3484 }
3485
3486 /* Create a new artificial heap variable with NAME and make a
3487    constraint from it to LHS.  Return the created variable.  */
3488
3489 static varinfo_t
3490 make_constraint_from_heapvar (varinfo_t lhs, const char *name)
3491 {
3492   varinfo_t vi;
3493   tree heapvar = heapvar_lookup (lhs->decl, lhs->offset);
3494
3495   if (heapvar == NULL_TREE)
3496     {
3497       var_ann_t ann;
3498       heapvar = create_tmp_var_raw (ptr_type_node, name);
3499       DECL_EXTERNAL (heapvar) = 1;
3500
3501       heapvar_insert (lhs->decl, lhs->offset, heapvar);
3502
3503       ann = get_var_ann (heapvar);
3504       ann->is_heapvar = 1;
3505     }
3506
3507   /* For global vars we need to add a heapvar to the list of referenced
3508      vars of a different function than it was created for originally.  */
3509   if (gimple_referenced_vars (cfun))
3510     add_referenced_var (heapvar);
3511