OSDN Git Service

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