OSDN Git Service

2009-10-26 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-structalias.c
1 /* Tree based points-to analysis
2    Copyright (C) 2005, 2006, 2007, 2008, 2009 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 struct GTY(()) heapvar_map {
294   struct tree_map map;
295   unsigned HOST_WIDE_INT offset;
296 };
297
298 static int
299 heapvar_map_eq (const void *p1, const void *p2)
300 {
301   const struct heapvar_map *h1 = (const struct heapvar_map *)p1;
302   const struct heapvar_map *h2 = (const struct heapvar_map *)p2;
303   return (h1->map.base.from == h2->map.base.from
304           && h1->offset == h2->offset);
305 }
306
307 static unsigned int
308 heapvar_map_hash (struct heapvar_map *h)
309 {
310   return iterative_hash_host_wide_int (h->offset,
311                                        htab_hash_pointer (h->map.base.from));
312 }
313
314 /* Lookup a heap var for FROM, and return it if we find one.  */
315
316 static tree
317 heapvar_lookup (tree from, unsigned HOST_WIDE_INT offset)
318 {
319   struct heapvar_map *h, in;
320   in.map.base.from = from;
321   in.offset = offset;
322   h = (struct heapvar_map *) htab_find_with_hash (heapvar_for_stmt, &in,
323                                                   heapvar_map_hash (&in));
324   if (h)
325     return h->map.to;
326   return NULL_TREE;
327 }
328
329 /* Insert a mapping FROM->TO in the heap var for statement
330    hashtable.  */
331
332 static void
333 heapvar_insert (tree from, unsigned HOST_WIDE_INT offset, tree to)
334 {
335   struct heapvar_map *h;
336   void **loc;
337
338   h = GGC_NEW (struct heapvar_map);
339   h->map.base.from = from;
340   h->offset = offset;
341   h->map.hash = heapvar_map_hash (h);
342   h->map.to = to;
343   loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->map.hash, INSERT);
344   gcc_assert (*loc == NULL);
345   *(struct heapvar_map **) loc = h;
346 }
347
348 /* Return a new variable info structure consisting for a variable
349    named NAME, and using constraint graph node NODE.  Append it
350    to the vector of variable info structures.  */
351
352 static varinfo_t
353 new_var_info (tree t, const char *name)
354 {
355   unsigned index = VEC_length (varinfo_t, varmap);
356   varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
357
358   ret->id = index;
359   ret->name = name;
360   ret->decl = t;
361   /* Vars without decl are artificial and do not have sub-variables.  */
362   ret->is_artificial_var = (t == NULL_TREE);
363   ret->is_special_var = false;
364   ret->is_unknown_size_var = false;
365   ret->is_full_var = (t == NULL_TREE);
366   ret->is_heap_var = false;
367   ret->is_restrict_var = false;
368   ret->may_have_pointers = true;
369   ret->is_global_var = (t == NULL_TREE);
370   if (t && DECL_P (t))
371     ret->is_global_var = is_global_var (t);
372   ret->solution = BITMAP_ALLOC (&pta_obstack);
373   ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
374   ret->next = NULL;
375
376   VEC_safe_push (varinfo_t, heap, varmap, ret);
377
378   return ret;
379 }
380
381 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
382
383 /* An expression that appears in a constraint.  */
384
385 struct constraint_expr
386 {
387   /* Constraint type.  */
388   constraint_expr_type type;
389
390   /* Variable we are referring to in the constraint.  */
391   unsigned int var;
392
393   /* Offset, in bits, of this constraint from the beginning of
394      variables it ends up referring to.
395
396      IOW, in a deref constraint, we would deref, get the result set,
397      then add OFFSET to each member.   */
398   HOST_WIDE_INT offset;
399 };
400
401 /* Use 0x8000... as special unknown offset.  */
402 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
403
404 typedef struct constraint_expr ce_s;
405 DEF_VEC_O(ce_s);
406 DEF_VEC_ALLOC_O(ce_s, heap);
407 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
408 static void get_constraint_for (tree, VEC(ce_s, heap) **);
409 static void do_deref (VEC (ce_s, heap) **);
410
411 /* Our set constraints are made up of two constraint expressions, one
412    LHS, and one RHS.
413
414    As described in the introduction, our set constraints each represent an
415    operation between set valued variables.
416 */
417 struct constraint
418 {
419   struct constraint_expr lhs;
420   struct constraint_expr rhs;
421 };
422
423 /* List of constraints that we use to build the constraint graph from.  */
424
425 static VEC(constraint_t,heap) *constraints;
426 static alloc_pool constraint_pool;
427
428 /* The constraint graph is represented as an array of bitmaps
429    containing successor nodes.  */
430
431 struct constraint_graph
432 {
433   /* Size of this graph, which may be different than the number of
434      nodes in the variable map.  */
435   unsigned int size;
436
437   /* Explicit successors of each node. */
438   bitmap *succs;
439
440   /* Implicit predecessors of each node (Used for variable
441      substitution). */
442   bitmap *implicit_preds;
443
444   /* Explicit predecessors of each node (Used for variable substitution).  */
445   bitmap *preds;
446
447   /* Indirect cycle representatives, or -1 if the node has no indirect
448      cycles.  */
449   int *indirect_cycles;
450
451   /* Representative node for a node.  rep[a] == a unless the node has
452      been unified. */
453   unsigned int *rep;
454
455   /* Equivalence class representative for a label.  This is used for
456      variable substitution.  */
457   int *eq_rep;
458
459   /* Pointer equivalence label for a node.  All nodes with the same
460      pointer equivalence label can be unified together at some point
461      (either during constraint optimization or after the constraint
462      graph is built).  */
463   unsigned int *pe;
464
465   /* Pointer equivalence representative for a label.  This is used to
466      handle nodes that are pointer equivalent but not location
467      equivalent.  We can unite these once the addressof constraints
468      are transformed into initial points-to sets.  */
469   int *pe_rep;
470
471   /* Pointer equivalence label for each node, used during variable
472      substitution.  */
473   unsigned int *pointer_label;
474
475   /* Location equivalence label for each node, used during location
476      equivalence finding.  */
477   unsigned int *loc_label;
478
479   /* Pointed-by set for each node, used during location equivalence
480      finding.  This is pointed-by rather than pointed-to, because it
481      is constructed using the predecessor graph.  */
482   bitmap *pointed_by;
483
484   /* Points to sets for pointer equivalence.  This is *not* the actual
485      points-to sets for nodes.  */
486   bitmap *points_to;
487
488   /* Bitmap of nodes where the bit is set if the node is a direct
489      node.  Used for variable substitution.  */
490   sbitmap direct_nodes;
491
492   /* Bitmap of nodes where the bit is set if the node is address
493      taken.  Used for variable substitution.  */
494   bitmap address_taken;
495
496   /* Vector of complex constraints for each graph node.  Complex
497      constraints are those involving dereferences or offsets that are
498      not 0.  */
499   VEC(constraint_t,heap) **complex;
500 };
501
502 static constraint_graph_t graph;
503
504 /* During variable substitution and the offline version of indirect
505    cycle finding, we create nodes to represent dereferences and
506    address taken constraints.  These represent where these start and
507    end.  */
508 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
509 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
510
511 /* Return the representative node for NODE, if NODE has been unioned
512    with another NODE.
513    This function performs path compression along the way to finding
514    the representative.  */
515
516 static unsigned int
517 find (unsigned int node)
518 {
519   gcc_assert (node < graph->size);
520   if (graph->rep[node] != node)
521     return graph->rep[node] = find (graph->rep[node]);
522   return node;
523 }
524
525 /* Union the TO and FROM nodes to the TO nodes.
526    Note that at some point in the future, we may want to do
527    union-by-rank, in which case we are going to have to return the
528    node we unified to.  */
529
530 static bool
531 unite (unsigned int to, unsigned int from)
532 {
533   gcc_assert (to < graph->size && from < graph->size);
534   if (to != from && graph->rep[from] != to)
535     {
536       graph->rep[from] = to;
537       return true;
538     }
539   return false;
540 }
541
542 /* Create a new constraint consisting of LHS and RHS expressions.  */
543
544 static constraint_t
545 new_constraint (const struct constraint_expr lhs,
546                 const struct constraint_expr rhs)
547 {
548   constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
549   ret->lhs = lhs;
550   ret->rhs = rhs;
551   return ret;
552 }
553
554 /* Print out constraint C to FILE.  */
555
556 static void
557 dump_constraint (FILE *file, constraint_t c)
558 {
559   if (c->lhs.type == ADDRESSOF)
560     fprintf (file, "&");
561   else if (c->lhs.type == DEREF)
562     fprintf (file, "*");
563   fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
564   if (c->lhs.offset == UNKNOWN_OFFSET)
565     fprintf (file, " + UNKNOWN");
566   else if (c->lhs.offset != 0)
567     fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
568   fprintf (file, " = ");
569   if (c->rhs.type == ADDRESSOF)
570     fprintf (file, "&");
571   else if (c->rhs.type == DEREF)
572     fprintf (file, "*");
573   fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
574   if (c->rhs.offset == UNKNOWN_OFFSET)
575     fprintf (file, " + UNKNOWN");
576   else if (c->rhs.offset != 0)
577     fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
578   fprintf (file, "\n");
579 }
580
581
582 void debug_constraint (constraint_t);
583 void debug_constraints (void);
584 void debug_constraint_graph (void);
585 void debug_solution_for_var (unsigned int);
586 void debug_sa_points_to_info (void);
587
588 /* Print out constraint C to stderr.  */
589
590 void
591 debug_constraint (constraint_t c)
592 {
593   dump_constraint (stderr, c);
594 }
595
596 /* Print out all constraints to FILE */
597
598 static void
599 dump_constraints (FILE *file)
600 {
601   int i;
602   constraint_t c;
603   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
604     dump_constraint (file, c);
605 }
606
607 /* Print out all constraints to stderr.  */
608
609 void
610 debug_constraints (void)
611 {
612   dump_constraints (stderr);
613 }
614
615 /* Print out to FILE the edge in the constraint graph that is created by
616    constraint c. The edge may have a label, depending on the type of
617    constraint that it represents. If complex1, e.g: a = *b, then the label
618    is "=*", if complex2, e.g: *a = b, then the label is "*=", if
619    complex with an offset, e.g: a = b + 8, then the label is "+".
620    Otherwise the edge has no label.  */
621
622 static void
623 dump_constraint_edge (FILE *file, constraint_t c)
624 {
625   if (c->rhs.type != ADDRESSOF)
626     {
627       const char *src = get_varinfo (c->rhs.var)->name;
628       const char *dst = get_varinfo (c->lhs.var)->name;
629       fprintf (file, "  \"%s\" -> \"%s\" ", src, dst);
630       /* Due to preprocessing of constraints, instructions like *a = *b are
631          illegal; thus, we do not have to handle such cases.  */
632       if (c->lhs.type == DEREF)
633         fprintf (file, " [ label=\"*=\" ] ;\n");
634       else if (c->rhs.type == DEREF)
635         fprintf (file, " [ label=\"=*\" ] ;\n");
636       else
637         {
638           /* We must check the case where the constraint is an offset.
639              In this case, it is treated as a complex constraint.  */
640           if (c->rhs.offset != c->lhs.offset)
641             fprintf (file, " [ label=\"+\" ] ;\n");
642           else
643             fprintf (file, " ;\n");
644         }
645     }
646 }
647
648 /* Print the constraint graph in dot format.  */
649
650 static void
651 dump_constraint_graph (FILE *file)
652 {
653   unsigned int i=0, size;
654   constraint_t c;
655
656   /* Only print the graph if it has already been initialized:  */
657   if (!graph)
658     return;
659
660   /* Print the constraints used to produce the constraint graph. The
661      constraints will be printed as comments in the dot file:  */
662   fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
663   dump_constraints (file);
664   fprintf (file, "*/\n");
665
666   /* Prints the header of the dot file:  */
667   fprintf (file, "\n\n// The constraint graph in dot format:\n");
668   fprintf (file, "strict digraph {\n");
669   fprintf (file, "  node [\n    shape = box\n  ]\n");
670   fprintf (file, "  edge [\n    fontsize = \"12\"\n  ]\n");
671   fprintf (file, "\n  // List of nodes in the constraint graph:\n");
672
673   /* The next lines print the nodes in the graph. In order to get the
674      number of nodes in the graph, we must choose the minimum between the
675      vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
676      yet been initialized, then graph->size == 0, otherwise we must only
677      read nodes that have an entry in VEC (varinfo_t, varmap).  */
678   size = VEC_length (varinfo_t, varmap);
679   size = size < graph->size ? size : graph->size;
680   for (i = 0; i < size; i++)
681     {
682       const char *name = get_varinfo (graph->rep[i])->name;
683       fprintf (file, "  \"%s\" ;\n", name);
684     }
685
686   /* Go over the list of constraints printing the edges in the constraint
687      graph.  */
688   fprintf (file, "\n  // The constraint edges:\n");
689   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
690     if (c)
691       dump_constraint_edge (file, c);
692
693   /* Prints the tail of the dot file. By now, only the closing bracket.  */
694   fprintf (file, "}\n\n\n");
695 }
696
697 /* Print out the constraint graph to stderr.  */
698
699 void
700 debug_constraint_graph (void)
701 {
702   dump_constraint_graph (stderr);
703 }
704
705 /* SOLVER FUNCTIONS
706
707    The solver is a simple worklist solver, that works on the following
708    algorithm:
709
710    sbitmap changed_nodes = all zeroes;
711    changed_count = 0;
712    For each node that is not already collapsed:
713        changed_count++;
714        set bit in changed nodes
715
716    while (changed_count > 0)
717    {
718      compute topological ordering for constraint graph
719
720      find and collapse cycles in the constraint graph (updating
721      changed if necessary)
722
723      for each node (n) in the graph in topological order:
724        changed_count--;
725
726        Process each complex constraint associated with the node,
727        updating changed if necessary.
728
729        For each outgoing edge from n, propagate the solution from n to
730        the destination of the edge, updating changed as necessary.
731
732    }  */
733
734 /* Return true if two constraint expressions A and B are equal.  */
735
736 static bool
737 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
738 {
739   return a.type == b.type && a.var == b.var && a.offset == b.offset;
740 }
741
742 /* Return true if constraint expression A is less than constraint expression
743    B.  This is just arbitrary, but consistent, in order to give them an
744    ordering.  */
745
746 static bool
747 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
748 {
749   if (a.type == b.type)
750     {
751       if (a.var == b.var)
752         return a.offset < b.offset;
753       else
754         return a.var < b.var;
755     }
756   else
757     return a.type < b.type;
758 }
759
760 /* Return true if constraint A is less than constraint B.  This is just
761    arbitrary, but consistent, in order to give them an ordering.  */
762
763 static bool
764 constraint_less (const constraint_t a, const constraint_t b)
765 {
766   if (constraint_expr_less (a->lhs, b->lhs))
767     return true;
768   else if (constraint_expr_less (b->lhs, a->lhs))
769     return false;
770   else
771     return constraint_expr_less (a->rhs, b->rhs);
772 }
773
774 /* Return true if two constraints A and B are equal.  */
775
776 static bool
777 constraint_equal (struct constraint a, struct constraint b)
778 {
779   return constraint_expr_equal (a.lhs, b.lhs)
780     && constraint_expr_equal (a.rhs, b.rhs);
781 }
782
783
784 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
785
786 static constraint_t
787 constraint_vec_find (VEC(constraint_t,heap) *vec,
788                      struct constraint lookfor)
789 {
790   unsigned int place;
791   constraint_t found;
792
793   if (vec == NULL)
794     return NULL;
795
796   place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
797   if (place >= VEC_length (constraint_t, vec))
798     return NULL;
799   found = VEC_index (constraint_t, vec, place);
800   if (!constraint_equal (*found, lookfor))
801     return NULL;
802   return found;
803 }
804
805 /* Union two constraint vectors, TO and FROM.  Put the result in TO.  */
806
807 static void
808 constraint_set_union (VEC(constraint_t,heap) **to,
809                       VEC(constraint_t,heap) **from)
810 {
811   int i;
812   constraint_t c;
813
814   for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
815     {
816       if (constraint_vec_find (*to, *c) == NULL)
817         {
818           unsigned int place = VEC_lower_bound (constraint_t, *to, c,
819                                                 constraint_less);
820           VEC_safe_insert (constraint_t, heap, *to, place, c);
821         }
822     }
823 }
824
825 /* Expands the solution in SET to all sub-fields of variables included.
826    Union the expanded result into RESULT.  */
827
828 static void
829 solution_set_expand (bitmap result, bitmap set)
830 {
831   bitmap_iterator bi;
832   bitmap vars = NULL;
833   unsigned j;
834
835   /* In a first pass record all variables we need to add all
836      sub-fields off.  This avoids quadratic behavior.  */
837   EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
838     {
839       varinfo_t v = get_varinfo (j);
840       if (v->is_artificial_var
841           || v->is_full_var)
842         continue;
843       v = lookup_vi_for_tree (v->decl);
844       if (vars == NULL)
845         vars = BITMAP_ALLOC (NULL);
846       bitmap_set_bit (vars, v->id);
847     }
848
849   /* In the second pass now do the addition to the solution and
850      to speed up solving add it to the delta as well.  */
851   if (vars != NULL)
852     {
853       EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
854         {
855           varinfo_t v = get_varinfo (j);
856           for (; v != NULL; v = v->next)
857             bitmap_set_bit (result, v->id);
858         }
859       BITMAP_FREE (vars);
860     }
861 }
862
863 /* Take a solution set SET, add OFFSET to each member of the set, and
864    overwrite SET with the result when done.  */
865
866 static void
867 solution_set_add (bitmap set, HOST_WIDE_INT offset)
868 {
869   bitmap result = BITMAP_ALLOC (&iteration_obstack);
870   unsigned int i;
871   bitmap_iterator bi;
872
873   /* If the offset is unknown we have to expand the solution to
874      all subfields.  */
875   if (offset == UNKNOWN_OFFSET)
876     {
877       solution_set_expand (set, set);
878       return;
879     }
880
881   EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
882     {
883       varinfo_t vi = get_varinfo (i);
884
885       /* If this is a variable with just one field just set its bit
886          in the result.  */
887       if (vi->is_artificial_var
888           || vi->is_unknown_size_var
889           || vi->is_full_var)
890         bitmap_set_bit (result, i);
891       else
892         {
893           unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
894
895           /* If the offset makes the pointer point to before the
896              variable use offset zero for the field lookup.  */
897           if (offset < 0
898               && fieldoffset > vi->offset)
899             fieldoffset = 0;
900
901           if (offset != 0)
902             vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
903
904           bitmap_set_bit (result, vi->id);
905           /* If the result is not exactly at fieldoffset include the next
906              field as well.  See get_constraint_for_ptr_offset for more
907              rationale.  */
908           if (vi->offset != fieldoffset
909               && vi->next != NULL)
910             bitmap_set_bit (result, vi->next->id);
911         }
912     }
913
914   bitmap_copy (set, result);
915   BITMAP_FREE (result);
916 }
917
918 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
919    process.  */
920
921 static bool
922 set_union_with_increment  (bitmap to, bitmap from, HOST_WIDE_INT inc)
923 {
924   if (inc == 0)
925     return bitmap_ior_into (to, from);
926   else
927     {
928       bitmap tmp;
929       bool res;
930
931       tmp = BITMAP_ALLOC (&iteration_obstack);
932       bitmap_copy (tmp, from);
933       solution_set_add (tmp, inc);
934       res = bitmap_ior_into (to, tmp);
935       BITMAP_FREE (tmp);
936       return res;
937     }
938 }
939
940 /* Insert constraint C into the list of complex constraints for graph
941    node VAR.  */
942
943 static void
944 insert_into_complex (constraint_graph_t graph,
945                      unsigned int var, constraint_t c)
946 {
947   VEC (constraint_t, heap) *complex = graph->complex[var];
948   unsigned int place = VEC_lower_bound (constraint_t, complex, c,
949                                         constraint_less);
950
951   /* Only insert constraints that do not already exist.  */
952   if (place >= VEC_length (constraint_t, complex)
953       || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
954     VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
955 }
956
957
958 /* Condense two variable nodes into a single variable node, by moving
959    all associated info from SRC to TO.  */
960
961 static void
962 merge_node_constraints (constraint_graph_t graph, unsigned int to,
963                         unsigned int from)
964 {
965   unsigned int i;
966   constraint_t c;
967
968   gcc_assert (find (from) == to);
969
970   /* Move all complex constraints from src node into to node  */
971   for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
972     {
973       /* In complex constraints for node src, we may have either
974          a = *src, and *src = a, or an offseted constraint which are
975          always added to the rhs node's constraints.  */
976
977       if (c->rhs.type == DEREF)
978         c->rhs.var = to;
979       else if (c->lhs.type == DEREF)
980         c->lhs.var = to;
981       else
982         c->rhs.var = to;
983     }
984   constraint_set_union (&graph->complex[to], &graph->complex[from]);
985   VEC_free (constraint_t, heap, graph->complex[from]);
986   graph->complex[from] = NULL;
987 }
988
989
990 /* Remove edges involving NODE from GRAPH.  */
991
992 static void
993 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
994 {
995   if (graph->succs[node])
996     BITMAP_FREE (graph->succs[node]);
997 }
998
999 /* Merge GRAPH nodes FROM and TO into node TO.  */
1000
1001 static void
1002 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1003                    unsigned int from)
1004 {
1005   if (graph->indirect_cycles[from] != -1)
1006     {
1007       /* If we have indirect cycles with the from node, and we have
1008          none on the to node, the to node has indirect cycles from the
1009          from node now that they are unified.
1010          If indirect cycles exist on both, unify the nodes that they
1011          are in a cycle with, since we know they are in a cycle with
1012          each other.  */
1013       if (graph->indirect_cycles[to] == -1)
1014         graph->indirect_cycles[to] = graph->indirect_cycles[from];
1015     }
1016
1017   /* Merge all the successor edges.  */
1018   if (graph->succs[from])
1019     {
1020       if (!graph->succs[to])
1021         graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1022       bitmap_ior_into (graph->succs[to],
1023                        graph->succs[from]);
1024     }
1025
1026   clear_edges_for_node (graph, from);
1027 }
1028
1029
1030 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1031    it doesn't exist in the graph already.  */
1032
1033 static void
1034 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1035                          unsigned int from)
1036 {
1037   if (to == from)
1038     return;
1039
1040   if (!graph->implicit_preds[to])
1041     graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1042
1043   if (bitmap_set_bit (graph->implicit_preds[to], from))
1044     stats.num_implicit_edges++;
1045 }
1046
1047 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1048    it doesn't exist in the graph already.
1049    Return false if the edge already existed, true otherwise.  */
1050
1051 static void
1052 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1053                      unsigned int from)
1054 {
1055   if (!graph->preds[to])
1056     graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1057   bitmap_set_bit (graph->preds[to], from);
1058 }
1059
1060 /* Add a graph edge to GRAPH, going from FROM to TO if
1061    it doesn't exist in the graph already.
1062    Return false if the edge already existed, true otherwise.  */
1063
1064 static bool
1065 add_graph_edge (constraint_graph_t graph, unsigned int to,
1066                 unsigned int from)
1067 {
1068   if (to == from)
1069     {
1070       return false;
1071     }
1072   else
1073     {
1074       bool r = false;
1075
1076       if (!graph->succs[from])
1077         graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1078       if (bitmap_set_bit (graph->succs[from], to))
1079         {
1080           r = true;
1081           if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1082             stats.num_edges++;
1083         }
1084       return r;
1085     }
1086 }
1087
1088
1089 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH.  */
1090
1091 static bool
1092 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1093                   unsigned int dest)
1094 {
1095   return (graph->succs[dest]
1096           && bitmap_bit_p (graph->succs[dest], src));
1097 }
1098
1099 /* Initialize the constraint graph structure to contain SIZE nodes.  */
1100
1101 static void
1102 init_graph (unsigned int size)
1103 {
1104   unsigned int j;
1105
1106   graph = XCNEW (struct constraint_graph);
1107   graph->size = size;
1108   graph->succs = XCNEWVEC (bitmap, graph->size);
1109   graph->indirect_cycles = XNEWVEC (int, graph->size);
1110   graph->rep = XNEWVEC (unsigned int, graph->size);
1111   graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1112   graph->pe = XCNEWVEC (unsigned int, graph->size);
1113   graph->pe_rep = XNEWVEC (int, graph->size);
1114
1115   for (j = 0; j < graph->size; j++)
1116     {
1117       graph->rep[j] = j;
1118       graph->pe_rep[j] = -1;
1119       graph->indirect_cycles[j] = -1;
1120     }
1121 }
1122
1123 /* Build the constraint graph, adding only predecessor edges right now.  */
1124
1125 static void
1126 build_pred_graph (void)
1127 {
1128   int i;
1129   constraint_t c;
1130   unsigned int j;
1131
1132   graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1133   graph->preds = XCNEWVEC (bitmap, graph->size);
1134   graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1135   graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1136   graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1137   graph->points_to = XCNEWVEC (bitmap, graph->size);
1138   graph->eq_rep = XNEWVEC (int, graph->size);
1139   graph->direct_nodes = sbitmap_alloc (graph->size);
1140   graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1141   sbitmap_zero (graph->direct_nodes);
1142
1143   for (j = 0; j < FIRST_REF_NODE; j++)
1144     {
1145       if (!get_varinfo (j)->is_special_var)
1146         SET_BIT (graph->direct_nodes, j);
1147     }
1148
1149   for (j = 0; j < graph->size; j++)
1150     graph->eq_rep[j] = -1;
1151
1152   for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1153     graph->indirect_cycles[j] = -1;
1154
1155   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1156     {
1157       struct constraint_expr lhs = c->lhs;
1158       struct constraint_expr rhs = c->rhs;
1159       unsigned int lhsvar = lhs.var;
1160       unsigned int rhsvar = rhs.var;
1161
1162       if (lhs.type == DEREF)
1163         {
1164           /* *x = y.  */
1165           if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1166             add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1167         }
1168       else if (rhs.type == DEREF)
1169         {
1170           /* x = *y */
1171           if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1172             add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1173           else
1174             RESET_BIT (graph->direct_nodes, lhsvar);
1175         }
1176       else if (rhs.type == ADDRESSOF)
1177         {
1178           varinfo_t v;
1179
1180           /* x = &y */
1181           if (graph->points_to[lhsvar] == NULL)
1182             graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1183           bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1184
1185           if (graph->pointed_by[rhsvar] == NULL)
1186             graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1187           bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1188
1189           /* Implicitly, *x = y */
1190           add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1191
1192           /* All related variables are no longer direct nodes.  */
1193           RESET_BIT (graph->direct_nodes, rhsvar);
1194           v = get_varinfo (rhsvar);
1195           if (!v->is_full_var)
1196             {
1197               v = lookup_vi_for_tree (v->decl);
1198               do
1199                 {
1200                   RESET_BIT (graph->direct_nodes, v->id);
1201                   v = v->next;
1202                 }
1203               while (v != NULL);
1204             }
1205           bitmap_set_bit (graph->address_taken, rhsvar);
1206         }
1207       else if (lhsvar > anything_id
1208                && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1209         {
1210           /* x = y */
1211           add_pred_graph_edge (graph, lhsvar, rhsvar);
1212           /* Implicitly, *x = *y */
1213           add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1214                                    FIRST_REF_NODE + rhsvar);
1215         }
1216       else if (lhs.offset != 0 || rhs.offset != 0)
1217         {
1218           if (rhs.offset != 0)
1219             RESET_BIT (graph->direct_nodes, lhs.var);
1220           else if (lhs.offset != 0)
1221             RESET_BIT (graph->direct_nodes, rhs.var);
1222         }
1223     }
1224 }
1225
1226 /* Build the constraint graph, adding successor edges.  */
1227
1228 static void
1229 build_succ_graph (void)
1230 {
1231   unsigned i, t;
1232   constraint_t c;
1233
1234   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1235     {
1236       struct constraint_expr lhs;
1237       struct constraint_expr rhs;
1238       unsigned int lhsvar;
1239       unsigned int rhsvar;
1240
1241       if (!c)
1242         continue;
1243
1244       lhs = c->lhs;
1245       rhs = c->rhs;
1246       lhsvar = find (lhs.var);
1247       rhsvar = find (rhs.var);
1248
1249       if (lhs.type == DEREF)
1250         {
1251           if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1252             add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1253         }
1254       else if (rhs.type == DEREF)
1255         {
1256           if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1257             add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1258         }
1259       else if (rhs.type == ADDRESSOF)
1260         {
1261           /* x = &y */
1262           gcc_assert (find (rhs.var) == rhs.var);
1263           bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1264         }
1265       else if (lhsvar > anything_id
1266                && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1267         {
1268           add_graph_edge (graph, lhsvar, rhsvar);
1269         }
1270     }
1271
1272   /* Add edges from STOREDANYTHING to all non-direct nodes.  */
1273   t = find (storedanything_id);
1274   for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1275     {
1276       if (!TEST_BIT (graph->direct_nodes, i))
1277         add_graph_edge (graph, find (i), t);
1278     }
1279 }
1280
1281
1282 /* Changed variables on the last iteration.  */
1283 static unsigned int changed_count;
1284 static sbitmap changed;
1285
1286 /* Strongly Connected Component visitation info.  */
1287
1288 struct scc_info
1289 {
1290   sbitmap visited;
1291   sbitmap deleted;
1292   unsigned int *dfs;
1293   unsigned int *node_mapping;
1294   int current_index;
1295   VEC(unsigned,heap) *scc_stack;
1296 };
1297
1298
1299 /* Recursive routine to find strongly connected components in GRAPH.
1300    SI is the SCC info to store the information in, and N is the id of current
1301    graph node we are processing.
1302
1303    This is Tarjan's strongly connected component finding algorithm, as
1304    modified by Nuutila to keep only non-root nodes on the stack.
1305    The algorithm can be found in "On finding the strongly connected
1306    connected components in a directed graph" by Esko Nuutila and Eljas
1307    Soisalon-Soininen, in Information Processing Letters volume 49,
1308    number 1, pages 9-14.  */
1309
1310 static void
1311 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1312 {
1313   unsigned int i;
1314   bitmap_iterator bi;
1315   unsigned int my_dfs;
1316
1317   SET_BIT (si->visited, n);
1318   si->dfs[n] = si->current_index ++;
1319   my_dfs = si->dfs[n];
1320
1321   /* Visit all the successors.  */
1322   EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1323     {
1324       unsigned int w;
1325
1326       if (i > LAST_REF_NODE)
1327         break;
1328
1329       w = find (i);
1330       if (TEST_BIT (si->deleted, w))
1331         continue;
1332
1333       if (!TEST_BIT (si->visited, w))
1334         scc_visit (graph, si, w);
1335       {
1336         unsigned int t = find (w);
1337         unsigned int nnode = find (n);
1338         gcc_assert (nnode == n);
1339
1340         if (si->dfs[t] < si->dfs[nnode])
1341           si->dfs[n] = si->dfs[t];
1342       }
1343     }
1344
1345   /* See if any components have been identified.  */
1346   if (si->dfs[n] == my_dfs)
1347     {
1348       if (VEC_length (unsigned, si->scc_stack) > 0
1349           && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1350         {
1351           bitmap scc = BITMAP_ALLOC (NULL);
1352           bool have_ref_node = n >= FIRST_REF_NODE;
1353           unsigned int lowest_node;
1354           bitmap_iterator bi;
1355
1356           bitmap_set_bit (scc, n);
1357
1358           while (VEC_length (unsigned, si->scc_stack) != 0
1359                  && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1360             {
1361               unsigned int w = VEC_pop (unsigned, si->scc_stack);
1362
1363               bitmap_set_bit (scc, w);
1364               if (w >= FIRST_REF_NODE)
1365                 have_ref_node = true;
1366             }
1367
1368           lowest_node = bitmap_first_set_bit (scc);
1369           gcc_assert (lowest_node < FIRST_REF_NODE);
1370
1371           /* Collapse the SCC nodes into a single node, and mark the
1372              indirect cycles.  */
1373           EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1374             {
1375               if (i < FIRST_REF_NODE)
1376                 {
1377                   if (unite (lowest_node, i))
1378                     unify_nodes (graph, lowest_node, i, false);
1379                 }
1380               else
1381                 {
1382                   unite (lowest_node, i);
1383                   graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1384                 }
1385             }
1386         }
1387       SET_BIT (si->deleted, n);
1388     }
1389   else
1390     VEC_safe_push (unsigned, heap, si->scc_stack, n);
1391 }
1392
1393 /* Unify node FROM into node TO, updating the changed count if
1394    necessary when UPDATE_CHANGED is true.  */
1395
1396 static void
1397 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1398              bool update_changed)
1399 {
1400
1401   gcc_assert (to != from && find (to) == to);
1402   if (dump_file && (dump_flags & TDF_DETAILS))
1403     fprintf (dump_file, "Unifying %s to %s\n",
1404              get_varinfo (from)->name,
1405              get_varinfo (to)->name);
1406
1407   if (update_changed)
1408     stats.unified_vars_dynamic++;
1409   else
1410     stats.unified_vars_static++;
1411
1412   merge_graph_nodes (graph, to, from);
1413   merge_node_constraints (graph, to, from);
1414
1415   /* Mark TO as changed if FROM was changed. If TO was already marked
1416      as changed, decrease the changed count.  */
1417
1418   if (update_changed && TEST_BIT (changed, from))
1419     {
1420       RESET_BIT (changed, from);
1421       if (!TEST_BIT (changed, to))
1422         SET_BIT (changed, to);
1423       else
1424         {
1425           gcc_assert (changed_count > 0);
1426           changed_count--;
1427         }
1428     }
1429   if (get_varinfo (from)->solution)
1430     {
1431       /* If the solution changes because of the merging, we need to mark
1432          the variable as changed.  */
1433       if (bitmap_ior_into (get_varinfo (to)->solution,
1434                            get_varinfo (from)->solution))
1435         {
1436           if (update_changed && !TEST_BIT (changed, to))
1437             {
1438               SET_BIT (changed, to);
1439               changed_count++;
1440             }
1441         }
1442       
1443       BITMAP_FREE (get_varinfo (from)->solution);
1444       BITMAP_FREE (get_varinfo (from)->oldsolution);
1445       
1446       if (stats.iterations > 0)
1447         {
1448           BITMAP_FREE (get_varinfo (to)->oldsolution);
1449           get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1450         }
1451     }
1452   if (valid_graph_edge (graph, to, to))
1453     {
1454       if (graph->succs[to])
1455         bitmap_clear_bit (graph->succs[to], to);
1456     }
1457 }
1458
1459 /* Information needed to compute the topological ordering of a graph.  */
1460
1461 struct topo_info
1462 {
1463   /* sbitmap of visited nodes.  */
1464   sbitmap visited;
1465   /* Array that stores the topological order of the graph, *in
1466      reverse*.  */
1467   VEC(unsigned,heap) *topo_order;
1468 };
1469
1470
1471 /* Initialize and return a topological info structure.  */
1472
1473 static struct topo_info *
1474 init_topo_info (void)
1475 {
1476   size_t size = graph->size;
1477   struct topo_info *ti = XNEW (struct topo_info);
1478   ti->visited = sbitmap_alloc (size);
1479   sbitmap_zero (ti->visited);
1480   ti->topo_order = VEC_alloc (unsigned, heap, 1);
1481   return ti;
1482 }
1483
1484
1485 /* Free the topological sort info pointed to by TI.  */
1486
1487 static void
1488 free_topo_info (struct topo_info *ti)
1489 {
1490   sbitmap_free (ti->visited);
1491   VEC_free (unsigned, heap, ti->topo_order);
1492   free (ti);
1493 }
1494
1495 /* Visit the graph in topological order, and store the order in the
1496    topo_info structure.  */
1497
1498 static void
1499 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1500             unsigned int n)
1501 {
1502   bitmap_iterator bi;
1503   unsigned int j;
1504
1505   SET_BIT (ti->visited, n);
1506
1507   if (graph->succs[n])
1508     EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1509       {
1510         if (!TEST_BIT (ti->visited, j))
1511           topo_visit (graph, ti, j);
1512       }
1513
1514   VEC_safe_push (unsigned, heap, ti->topo_order, n);
1515 }
1516
1517 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1518    starting solution for y.  */
1519
1520 static void
1521 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1522                   bitmap delta)
1523 {
1524   unsigned int lhs = c->lhs.var;
1525   bool flag = false;
1526   bitmap sol = get_varinfo (lhs)->solution;
1527   unsigned int j;
1528   bitmap_iterator bi;
1529   HOST_WIDE_INT roffset = c->rhs.offset;
1530
1531   /* Our IL does not allow this.  */
1532   gcc_assert (c->lhs.offset == 0);
1533
1534   /* If the solution of Y contains anything it is good enough to transfer
1535      this to the LHS.  */
1536   if (bitmap_bit_p (delta, anything_id))
1537     {
1538       flag |= bitmap_set_bit (sol, anything_id);
1539       goto done;
1540     }
1541
1542   /* If we do not know at with offset the rhs is dereferenced compute
1543      the reachability set of DELTA, conservatively assuming it is
1544      dereferenced at all valid offsets.  */
1545   if (roffset == UNKNOWN_OFFSET)
1546     {
1547       solution_set_expand (delta, delta);
1548       /* No further offset processing is necessary.  */
1549       roffset = 0;
1550     }
1551
1552   /* For each variable j in delta (Sol(y)), add
1553      an edge in the graph from j to x, and union Sol(j) into Sol(x).  */
1554   EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1555     {
1556       varinfo_t v = get_varinfo (j);
1557       HOST_WIDE_INT fieldoffset = v->offset + roffset;
1558       unsigned int t;
1559
1560       if (v->is_full_var)
1561         fieldoffset = v->offset;
1562       else if (roffset != 0)
1563         v = first_vi_for_offset (v, fieldoffset);
1564       /* If the access is outside of the variable we can ignore it.  */
1565       if (!v)
1566         continue;
1567
1568       do
1569         {
1570           t = find (v->id);
1571
1572           /* Adding edges from the special vars is pointless.
1573              They don't have sets that can change.  */
1574           if (get_varinfo (t)->is_special_var)
1575             flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1576           /* Merging the solution from ESCAPED needlessly increases
1577              the set.  Use ESCAPED as representative instead.  */
1578           else if (v->id == escaped_id)
1579             flag |= bitmap_set_bit (sol, escaped_id);
1580           else if (add_graph_edge (graph, lhs, t))
1581             flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1582
1583           /* If the variable is not exactly at the requested offset
1584              we have to include the next one.  */
1585           if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1586               || v->next == NULL)
1587             break;
1588
1589           v = v->next;
1590           fieldoffset = v->offset;
1591         }
1592       while (1);
1593     }
1594
1595 done:
1596   /* If the LHS solution changed, mark the var as changed.  */
1597   if (flag)
1598     {
1599       get_varinfo (lhs)->solution = sol;
1600       if (!TEST_BIT (changed, lhs))
1601         {
1602           SET_BIT (changed, lhs);
1603           changed_count++;
1604         }
1605     }
1606 }
1607
1608 /* Process a constraint C that represents *(x + off) = y using DELTA
1609    as the starting solution for x.  */
1610
1611 static void
1612 do_ds_constraint (constraint_t c, bitmap delta)
1613 {
1614   unsigned int rhs = c->rhs.var;
1615   bitmap sol = get_varinfo (rhs)->solution;
1616   unsigned int j;
1617   bitmap_iterator bi;
1618   HOST_WIDE_INT loff = c->lhs.offset;
1619
1620   /* Our IL does not allow this.  */
1621   gcc_assert (c->rhs.offset == 0);
1622
1623   /* If the solution of y contains ANYTHING simply use the ANYTHING
1624      solution.  This avoids needlessly increasing the points-to sets.  */
1625   if (bitmap_bit_p (sol, anything_id))
1626     sol = get_varinfo (find (anything_id))->solution;
1627
1628   /* If the solution for x contains ANYTHING we have to merge the
1629      solution of y into all pointer variables which we do via
1630      STOREDANYTHING.  */
1631   if (bitmap_bit_p (delta, anything_id))
1632     {
1633       unsigned t = find (storedanything_id);
1634       if (add_graph_edge (graph, t, rhs))
1635         {
1636           if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1637             {
1638               if (!TEST_BIT (changed, t))
1639                 {
1640                   SET_BIT (changed, t);
1641                   changed_count++;
1642                 }
1643             }
1644         }
1645       return;
1646     }
1647
1648   /* If we do not know at with offset the rhs is dereferenced compute
1649      the reachability set of DELTA, conservatively assuming it is
1650      dereferenced at all valid offsets.  */
1651   if (loff == UNKNOWN_OFFSET)
1652     {
1653       solution_set_expand (delta, delta);
1654       loff = 0;
1655     }
1656
1657   /* For each member j of delta (Sol(x)), add an edge from y to j and
1658      union Sol(y) into Sol(j) */
1659   EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1660     {
1661       varinfo_t v = get_varinfo (j);
1662       unsigned int t;
1663       HOST_WIDE_INT fieldoffset = v->offset + loff;
1664
1665       /* If v is a global variable then this is an escape point.  */
1666       if (v->is_global_var)
1667         {
1668           t = find (escaped_id);
1669           if (add_graph_edge (graph, t, rhs)
1670               && bitmap_ior_into (get_varinfo (t)->solution, sol)
1671               && !TEST_BIT (changed, t))
1672             {
1673               SET_BIT (changed, t);
1674               changed_count++;
1675             }
1676         }
1677
1678       if (v->is_special_var)
1679         continue;
1680
1681       if (v->is_full_var)
1682         fieldoffset = v->offset;
1683       else if (loff != 0)
1684         v = first_vi_for_offset (v, fieldoffset);
1685       /* If the access is outside of the variable we can ignore it.  */
1686       if (!v)
1687         continue;
1688
1689       do
1690         {
1691           if (v->may_have_pointers)
1692             {
1693               t = find (v->id);
1694               if (add_graph_edge (graph, t, rhs)
1695                   && bitmap_ior_into (get_varinfo (t)->solution, sol)
1696                   && !TEST_BIT (changed, t))
1697                 {
1698                   SET_BIT (changed, t);
1699                   changed_count++;
1700                 }
1701             }
1702
1703           /* If the variable is not exactly at the requested offset
1704              we have to include the next one.  */
1705           if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1706               || v->next == NULL)
1707             break;
1708
1709           v = v->next;
1710           fieldoffset = v->offset;
1711         }
1712       while (1);
1713     }
1714 }
1715
1716 /* Handle a non-simple (simple meaning requires no iteration),
1717    constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved).  */
1718
1719 static void
1720 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1721 {
1722   if (c->lhs.type == DEREF)
1723     {
1724       if (c->rhs.type == ADDRESSOF)
1725         {
1726           gcc_unreachable();
1727         }
1728       else
1729         {
1730           /* *x = y */
1731           do_ds_constraint (c, delta);
1732         }
1733     }
1734   else if (c->rhs.type == DEREF)
1735     {
1736       /* x = *y */
1737       if (!(get_varinfo (c->lhs.var)->is_special_var))
1738         do_sd_constraint (graph, c, delta);
1739     }
1740   else
1741     {
1742       bitmap tmp;
1743       bitmap solution;
1744       bool flag = false;
1745
1746       gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1747       solution = get_varinfo (c->rhs.var)->solution;
1748       tmp = get_varinfo (c->lhs.var)->solution;
1749
1750       flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1751
1752       if (flag)
1753         {
1754           get_varinfo (c->lhs.var)->solution = tmp;
1755           if (!TEST_BIT (changed, c->lhs.var))
1756             {
1757               SET_BIT (changed, c->lhs.var);
1758               changed_count++;
1759             }
1760         }
1761     }
1762 }
1763
1764 /* Initialize and return a new SCC info structure.  */
1765
1766 static struct scc_info *
1767 init_scc_info (size_t size)
1768 {
1769   struct scc_info *si = XNEW (struct scc_info);
1770   size_t i;
1771
1772   si->current_index = 0;
1773   si->visited = sbitmap_alloc (size);
1774   sbitmap_zero (si->visited);
1775   si->deleted = sbitmap_alloc (size);
1776   sbitmap_zero (si->deleted);
1777   si->node_mapping = XNEWVEC (unsigned int, size);
1778   si->dfs = XCNEWVEC (unsigned int, size);
1779
1780   for (i = 0; i < size; i++)
1781     si->node_mapping[i] = i;
1782
1783   si->scc_stack = VEC_alloc (unsigned, heap, 1);
1784   return si;
1785 }
1786
1787 /* Free an SCC info structure pointed to by SI */
1788
1789 static void
1790 free_scc_info (struct scc_info *si)
1791 {
1792   sbitmap_free (si->visited);
1793   sbitmap_free (si->deleted);
1794   free (si->node_mapping);
1795   free (si->dfs);
1796   VEC_free (unsigned, heap, si->scc_stack);
1797   free (si);
1798 }
1799
1800
1801 /* Find indirect cycles in GRAPH that occur, using strongly connected
1802    components, and note them in the indirect cycles map.
1803
1804    This technique comes from Ben Hardekopf and Calvin Lin,
1805    "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1806    Lines of Code", submitted to PLDI 2007.  */
1807
1808 static void
1809 find_indirect_cycles (constraint_graph_t graph)
1810 {
1811   unsigned int i;
1812   unsigned int size = graph->size;
1813   struct scc_info *si = init_scc_info (size);
1814
1815   for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1816     if (!TEST_BIT (si->visited, i) && find (i) == i)
1817       scc_visit (graph, si, i);
1818
1819   free_scc_info (si);
1820 }
1821
1822 /* Compute a topological ordering for GRAPH, and store the result in the
1823    topo_info structure TI.  */
1824
1825 static void
1826 compute_topo_order (constraint_graph_t graph,
1827                     struct topo_info *ti)
1828 {
1829   unsigned int i;
1830   unsigned int size = graph->size;
1831
1832   for (i = 0; i != size; ++i)
1833     if (!TEST_BIT (ti->visited, i) && find (i) == i)
1834       topo_visit (graph, ti, i);
1835 }
1836
1837 /* Structure used to for hash value numbering of pointer equivalence
1838    classes.  */
1839
1840 typedef struct equiv_class_label
1841 {
1842   hashval_t hashcode;
1843   unsigned int equivalence_class;
1844   bitmap labels;
1845 } *equiv_class_label_t;
1846 typedef const struct equiv_class_label *const_equiv_class_label_t;
1847
1848 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1849    classes.  */
1850 static htab_t pointer_equiv_class_table;
1851
1852 /* A hashtable for mapping a bitmap of labels->location equivalence
1853    classes.  */
1854 static htab_t location_equiv_class_table;
1855
1856 /* Hash function for a equiv_class_label_t */
1857
1858 static hashval_t
1859 equiv_class_label_hash (const void *p)
1860 {
1861   const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1862   return ecl->hashcode;
1863 }
1864
1865 /* Equality function for two equiv_class_label_t's.  */
1866
1867 static int
1868 equiv_class_label_eq (const void *p1, const void *p2)
1869 {
1870   const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1871   const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1872   return (eql1->hashcode == eql2->hashcode
1873           && bitmap_equal_p (eql1->labels, eql2->labels));
1874 }
1875
1876 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1877    contains.  */
1878
1879 static unsigned int
1880 equiv_class_lookup (htab_t table, bitmap labels)
1881 {
1882   void **slot;
1883   struct equiv_class_label ecl;
1884
1885   ecl.labels = labels;
1886   ecl.hashcode = bitmap_hash (labels);
1887
1888   slot = htab_find_slot_with_hash (table, &ecl,
1889                                    ecl.hashcode, NO_INSERT);
1890   if (!slot)
1891     return 0;
1892   else
1893     return ((equiv_class_label_t) *slot)->equivalence_class;
1894 }
1895
1896
1897 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1898    to TABLE.  */
1899
1900 static void
1901 equiv_class_add (htab_t table, unsigned int equivalence_class,
1902                  bitmap labels)
1903 {
1904   void **slot;
1905   equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1906
1907   ecl->labels = labels;
1908   ecl->equivalence_class = equivalence_class;
1909   ecl->hashcode = bitmap_hash (labels);
1910
1911   slot = htab_find_slot_with_hash (table, ecl,
1912                                    ecl->hashcode, INSERT);
1913   gcc_assert (!*slot);
1914   *slot = (void *) ecl;
1915 }
1916
1917 /* Perform offline variable substitution.
1918
1919    This is a worst case quadratic time way of identifying variables
1920    that must have equivalent points-to sets, including those caused by
1921    static cycles, and single entry subgraphs, in the constraint graph.
1922
1923    The technique is described in "Exploiting Pointer and Location
1924    Equivalence to Optimize Pointer Analysis. In the 14th International
1925    Static Analysis Symposium (SAS), August 2007."  It is known as the
1926    "HU" algorithm, and is equivalent to value numbering the collapsed
1927    constraint graph including evaluating unions.
1928
1929    The general method of finding equivalence classes is as follows:
1930    Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1931    Initialize all non-REF nodes to be direct nodes.
1932    For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1933    variable}
1934    For each constraint containing the dereference, we also do the same
1935    thing.
1936
1937    We then compute SCC's in the graph and unify nodes in the same SCC,
1938    including pts sets.
1939
1940    For each non-collapsed node x:
1941     Visit all unvisited explicit incoming edges.
1942     Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1943     where y->x.
1944     Lookup the equivalence class for pts(x).
1945      If we found one, equivalence_class(x) = found class.
1946      Otherwise, equivalence_class(x) = new class, and new_class is
1947     added to the lookup table.
1948
1949    All direct nodes with the same equivalence class can be replaced
1950    with a single representative node.
1951    All unlabeled nodes (label == 0) are not pointers and all edges
1952    involving them can be eliminated.
1953    We perform these optimizations during rewrite_constraints
1954
1955    In addition to pointer equivalence class finding, we also perform
1956    location equivalence class finding.  This is the set of variables
1957    that always appear together in points-to sets.  We use this to
1958    compress the size of the points-to sets.  */
1959
1960 /* Current maximum pointer equivalence class id.  */
1961 static int pointer_equiv_class;
1962
1963 /* Current maximum location equivalence class id.  */
1964 static int location_equiv_class;
1965
1966 /* Recursive routine to find strongly connected components in GRAPH,
1967    and label it's nodes with DFS numbers.  */
1968
1969 static void
1970 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1971 {
1972   unsigned int i;
1973   bitmap_iterator bi;
1974   unsigned int my_dfs;
1975
1976   gcc_assert (si->node_mapping[n] == n);
1977   SET_BIT (si->visited, n);
1978   si->dfs[n] = si->current_index ++;
1979   my_dfs = si->dfs[n];
1980
1981   /* Visit all the successors.  */
1982   EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1983     {
1984       unsigned int w = si->node_mapping[i];
1985
1986       if (TEST_BIT (si->deleted, w))
1987         continue;
1988
1989       if (!TEST_BIT (si->visited, w))
1990         condense_visit (graph, si, w);
1991       {
1992         unsigned int t = si->node_mapping[w];
1993         unsigned int nnode = si->node_mapping[n];
1994         gcc_assert (nnode == n);
1995
1996         if (si->dfs[t] < si->dfs[nnode])
1997           si->dfs[n] = si->dfs[t];
1998       }
1999     }
2000
2001   /* Visit all the implicit predecessors.  */
2002   EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2003     {
2004       unsigned int w = si->node_mapping[i];
2005
2006       if (TEST_BIT (si->deleted, w))
2007         continue;
2008
2009       if (!TEST_BIT (si->visited, w))
2010         condense_visit (graph, si, w);
2011       {
2012         unsigned int t = si->node_mapping[w];
2013         unsigned int nnode = si->node_mapping[n];
2014         gcc_assert (nnode == n);
2015
2016         if (si->dfs[t] < si->dfs[nnode])
2017           si->dfs[n] = si->dfs[t];
2018       }
2019     }
2020
2021   /* See if any components have been identified.  */
2022   if (si->dfs[n] == my_dfs)
2023     {
2024       while (VEC_length (unsigned, si->scc_stack) != 0
2025              && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
2026         {
2027           unsigned int w = VEC_pop (unsigned, si->scc_stack);
2028           si->node_mapping[w] = n;
2029
2030           if (!TEST_BIT (graph->direct_nodes, w))
2031             RESET_BIT (graph->direct_nodes, n);
2032
2033           /* Unify our nodes.  */
2034           if (graph->preds[w])
2035             {
2036               if (!graph->preds[n])
2037                 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2038               bitmap_ior_into (graph->preds[n], graph->preds[w]);
2039             }
2040           if (graph->implicit_preds[w])
2041             {
2042               if (!graph->implicit_preds[n])
2043                 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2044               bitmap_ior_into (graph->implicit_preds[n],
2045                                graph->implicit_preds[w]);
2046             }
2047           if (graph->points_to[w])
2048             {
2049               if (!graph->points_to[n])
2050                 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2051               bitmap_ior_into (graph->points_to[n],
2052                                graph->points_to[w]);
2053             }
2054         }
2055       SET_BIT (si->deleted, n);
2056     }
2057   else
2058     VEC_safe_push (unsigned, heap, si->scc_stack, n);
2059 }
2060
2061 /* Label pointer equivalences.  */
2062
2063 static void
2064 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2065 {
2066   unsigned int i;
2067   bitmap_iterator bi;
2068   SET_BIT (si->visited, n);
2069
2070   if (!graph->points_to[n])
2071     graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2072
2073   /* Label and union our incoming edges's points to sets.  */
2074   EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2075     {
2076       unsigned int w = si->node_mapping[i];
2077       if (!TEST_BIT (si->visited, w))
2078         label_visit (graph, si, w);
2079
2080       /* Skip unused edges  */
2081       if (w == n || graph->pointer_label[w] == 0)
2082         continue;
2083
2084       if (graph->points_to[w])
2085         bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2086     }
2087   /* Indirect nodes get fresh variables.  */
2088   if (!TEST_BIT (graph->direct_nodes, n))
2089     bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2090
2091   if (!bitmap_empty_p (graph->points_to[n]))
2092     {
2093       unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2094                                                graph->points_to[n]);
2095       if (!label)
2096         {
2097           label = pointer_equiv_class++;
2098           equiv_class_add (pointer_equiv_class_table,
2099                            label, graph->points_to[n]);
2100         }
2101       graph->pointer_label[n] = label;
2102     }
2103 }
2104
2105 /* Perform offline variable substitution, discovering equivalence
2106    classes, and eliminating non-pointer variables.  */
2107
2108 static struct scc_info *
2109 perform_var_substitution (constraint_graph_t graph)
2110 {
2111   unsigned int i;
2112   unsigned int size = graph->size;
2113   struct scc_info *si = init_scc_info (size);
2114
2115   bitmap_obstack_initialize (&iteration_obstack);
2116   pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2117                                            equiv_class_label_eq, free);
2118   location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2119                                             equiv_class_label_eq, free);
2120   pointer_equiv_class = 1;
2121   location_equiv_class = 1;
2122
2123   /* Condense the nodes, which means to find SCC's, count incoming
2124      predecessors, and unite nodes in SCC's.  */
2125   for (i = 0; i < FIRST_REF_NODE; i++)
2126     if (!TEST_BIT (si->visited, si->node_mapping[i]))
2127       condense_visit (graph, si, si->node_mapping[i]);
2128
2129   sbitmap_zero (si->visited);
2130   /* Actually the label the nodes for pointer equivalences  */
2131   for (i = 0; i < FIRST_REF_NODE; i++)
2132     if (!TEST_BIT (si->visited, si->node_mapping[i]))
2133       label_visit (graph, si, si->node_mapping[i]);
2134
2135   /* Calculate location equivalence labels.  */
2136   for (i = 0; i < FIRST_REF_NODE; i++)
2137     {
2138       bitmap pointed_by;
2139       bitmap_iterator bi;
2140       unsigned int j;
2141       unsigned int label;
2142
2143       if (!graph->pointed_by[i])
2144         continue;
2145       pointed_by = BITMAP_ALLOC (&iteration_obstack);
2146
2147       /* Translate the pointed-by mapping for pointer equivalence
2148          labels.  */
2149       EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2150         {
2151           bitmap_set_bit (pointed_by,
2152                           graph->pointer_label[si->node_mapping[j]]);
2153         }
2154       /* The original pointed_by is now dead.  */
2155       BITMAP_FREE (graph->pointed_by[i]);
2156
2157       /* Look up the location equivalence label if one exists, or make
2158          one otherwise.  */
2159       label = equiv_class_lookup (location_equiv_class_table,
2160                                   pointed_by);
2161       if (label == 0)
2162         {
2163           label = location_equiv_class++;
2164           equiv_class_add (location_equiv_class_table,
2165                            label, pointed_by);
2166         }
2167       else
2168         {
2169           if (dump_file && (dump_flags & TDF_DETAILS))
2170             fprintf (dump_file, "Found location equivalence for node %s\n",
2171                      get_varinfo (i)->name);
2172           BITMAP_FREE (pointed_by);
2173         }
2174       graph->loc_label[i] = label;
2175
2176     }
2177
2178   if (dump_file && (dump_flags & TDF_DETAILS))
2179     for (i = 0; i < FIRST_REF_NODE; i++)
2180       {
2181         bool direct_node = TEST_BIT (graph->direct_nodes, i);
2182         fprintf (dump_file,
2183                  "Equivalence classes for %s node id %d:%s are pointer: %d"
2184                  ", location:%d\n",
2185                  direct_node ? "Direct node" : "Indirect node", i,
2186                  get_varinfo (i)->name,
2187                  graph->pointer_label[si->node_mapping[i]],
2188                  graph->loc_label[si->node_mapping[i]]);
2189       }
2190
2191   /* Quickly eliminate our non-pointer variables.  */
2192
2193   for (i = 0; i < FIRST_REF_NODE; i++)
2194     {
2195       unsigned int node = si->node_mapping[i];
2196
2197       if (graph->pointer_label[node] == 0)
2198         {
2199           if (dump_file && (dump_flags & TDF_DETAILS))
2200             fprintf (dump_file,
2201                      "%s is a non-pointer variable, eliminating edges.\n",
2202                      get_varinfo (node)->name);
2203           stats.nonpointer_vars++;
2204           clear_edges_for_node (graph, node);
2205         }
2206     }
2207
2208   return si;
2209 }
2210
2211 /* Free information that was only necessary for variable
2212    substitution.  */
2213
2214 static void
2215 free_var_substitution_info (struct scc_info *si)
2216 {
2217   free_scc_info (si);
2218   free (graph->pointer_label);
2219   free (graph->loc_label);
2220   free (graph->pointed_by);
2221   free (graph->points_to);
2222   free (graph->eq_rep);
2223   sbitmap_free (graph->direct_nodes);
2224   htab_delete (pointer_equiv_class_table);
2225   htab_delete (location_equiv_class_table);
2226   bitmap_obstack_release (&iteration_obstack);
2227 }
2228
2229 /* Return an existing node that is equivalent to NODE, which has
2230    equivalence class LABEL, if one exists.  Return NODE otherwise.  */
2231
2232 static unsigned int
2233 find_equivalent_node (constraint_graph_t graph,
2234                       unsigned int node, unsigned int label)
2235 {
2236   /* If the address version of this variable is unused, we can
2237      substitute it for anything else with the same label.
2238      Otherwise, we know the pointers are equivalent, but not the
2239      locations, and we can unite them later.  */
2240
2241   if (!bitmap_bit_p (graph->address_taken, node))
2242     {
2243       gcc_assert (label < graph->size);
2244
2245       if (graph->eq_rep[label] != -1)
2246         {
2247           /* Unify the two variables since we know they are equivalent.  */
2248           if (unite (graph->eq_rep[label], node))
2249             unify_nodes (graph, graph->eq_rep[label], node, false);
2250           return graph->eq_rep[label];
2251         }
2252       else
2253         {
2254           graph->eq_rep[label] = node;
2255           graph->pe_rep[label] = node;
2256         }
2257     }
2258   else
2259     {
2260       gcc_assert (label < graph->size);
2261       graph->pe[node] = label;
2262       if (graph->pe_rep[label] == -1)
2263         graph->pe_rep[label] = node;
2264     }
2265
2266   return node;
2267 }
2268
2269 /* Unite pointer equivalent but not location equivalent nodes in
2270    GRAPH.  This may only be performed once variable substitution is
2271    finished.  */
2272
2273 static void
2274 unite_pointer_equivalences (constraint_graph_t graph)
2275 {
2276   unsigned int i;
2277
2278   /* Go through the pointer equivalences and unite them to their
2279      representative, if they aren't already.  */
2280   for (i = 0; i < FIRST_REF_NODE; i++)
2281     {
2282       unsigned int label = graph->pe[i];
2283       if (label)
2284         {
2285           int label_rep = graph->pe_rep[label];
2286           
2287           if (label_rep == -1)
2288             continue;
2289           
2290           label_rep = find (label_rep);
2291           if (label_rep >= 0 && unite (label_rep, find (i)))
2292             unify_nodes (graph, label_rep, i, false);
2293         }
2294     }
2295 }
2296
2297 /* Move complex constraints to the GRAPH nodes they belong to.  */
2298
2299 static void
2300 move_complex_constraints (constraint_graph_t graph)
2301 {
2302   int i;
2303   constraint_t c;
2304
2305   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2306     {
2307       if (c)
2308         {
2309           struct constraint_expr lhs = c->lhs;
2310           struct constraint_expr rhs = c->rhs;
2311
2312           if (lhs.type == DEREF)
2313             {
2314               insert_into_complex (graph, lhs.var, c);
2315             }
2316           else if (rhs.type == DEREF)
2317             {
2318               if (!(get_varinfo (lhs.var)->is_special_var))
2319                 insert_into_complex (graph, rhs.var, c);
2320             }
2321           else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2322                    && (lhs.offset != 0 || rhs.offset != 0))
2323             {
2324               insert_into_complex (graph, rhs.var, c);
2325             }
2326         }
2327     }
2328 }
2329
2330
2331 /* Optimize and rewrite complex constraints while performing
2332    collapsing of equivalent nodes.  SI is the SCC_INFO that is the
2333    result of perform_variable_substitution.  */
2334
2335 static void
2336 rewrite_constraints (constraint_graph_t graph,
2337                      struct scc_info *si)
2338 {
2339   int i;
2340   unsigned int j;
2341   constraint_t c;
2342
2343   for (j = 0; j < graph->size; j++)
2344     gcc_assert (find (j) == j);
2345
2346   for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2347     {
2348       struct constraint_expr lhs = c->lhs;
2349       struct constraint_expr rhs = c->rhs;
2350       unsigned int lhsvar = find (lhs.var);
2351       unsigned int rhsvar = find (rhs.var);
2352       unsigned int lhsnode, rhsnode;
2353       unsigned int lhslabel, rhslabel;
2354
2355       lhsnode = si->node_mapping[lhsvar];
2356       rhsnode = si->node_mapping[rhsvar];
2357       lhslabel = graph->pointer_label[lhsnode];
2358       rhslabel = graph->pointer_label[rhsnode];
2359
2360       /* See if it is really a non-pointer variable, and if so, ignore
2361          the constraint.  */
2362       if (lhslabel == 0)
2363         {
2364           if (dump_file && (dump_flags & TDF_DETAILS))
2365             {
2366               
2367               fprintf (dump_file, "%s is a non-pointer variable,"
2368                        "ignoring constraint:",
2369                        get_varinfo (lhs.var)->name);
2370               dump_constraint (dump_file, c);
2371             }
2372           VEC_replace (constraint_t, constraints, i, NULL);
2373           continue;
2374         }
2375
2376       if (rhslabel == 0)
2377         {
2378           if (dump_file && (dump_flags & TDF_DETAILS))
2379             {
2380               
2381               fprintf (dump_file, "%s is a non-pointer variable,"
2382                        "ignoring constraint:",
2383                        get_varinfo (rhs.var)->name);
2384               dump_constraint (dump_file, c);
2385             }
2386           VEC_replace (constraint_t, constraints, i, NULL);
2387           continue;
2388         }
2389
2390       lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2391       rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2392       c->lhs.var = lhsvar;
2393       c->rhs.var = rhsvar;
2394
2395     }
2396 }
2397
2398 /* Eliminate indirect cycles involving NODE.  Return true if NODE was
2399    part of an SCC, false otherwise.  */
2400
2401 static bool
2402 eliminate_indirect_cycles (unsigned int node)
2403 {
2404   if (graph->indirect_cycles[node] != -1
2405       && !bitmap_empty_p (get_varinfo (node)->solution))
2406     {
2407       unsigned int i;
2408       VEC(unsigned,heap) *queue = NULL;
2409       int queuepos;
2410       unsigned int to = find (graph->indirect_cycles[node]);
2411       bitmap_iterator bi;
2412
2413       /* We can't touch the solution set and call unify_nodes
2414          at the same time, because unify_nodes is going to do
2415          bitmap unions into it. */
2416
2417       EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2418         {
2419           if (find (i) == i && i != to)
2420             {
2421               if (unite (to, i))
2422                 VEC_safe_push (unsigned, heap, queue, i);
2423             }
2424         }
2425
2426       for (queuepos = 0;
2427            VEC_iterate (unsigned, queue, queuepos, i);
2428            queuepos++)
2429         {
2430           unify_nodes (graph, to, i, true);
2431         }
2432       VEC_free (unsigned, heap, queue);
2433       return true;
2434     }
2435   return false;
2436 }
2437
2438 /* Solve the constraint graph GRAPH using our worklist solver.
2439    This is based on the PW* family of solvers from the "Efficient Field
2440    Sensitive Pointer Analysis for C" paper.
2441    It works by iterating over all the graph nodes, processing the complex
2442    constraints and propagating the copy constraints, until everything stops
2443    changed.  This corresponds to steps 6-8 in the solving list given above.  */
2444
2445 static void
2446 solve_graph (constraint_graph_t graph)
2447 {
2448   unsigned int size = graph->size;
2449   unsigned int i;
2450   bitmap pts;
2451
2452   changed_count = 0;
2453   changed = sbitmap_alloc (size);
2454   sbitmap_zero (changed);
2455
2456   /* Mark all initial non-collapsed nodes as changed.  */
2457   for (i = 0; i < size; i++)
2458     {
2459       varinfo_t ivi = get_varinfo (i);
2460       if (find (i) == i && !bitmap_empty_p (ivi->solution)
2461           && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2462               || VEC_length (constraint_t, graph->complex[i]) > 0))
2463         {
2464           SET_BIT (changed, i);
2465           changed_count++;
2466         }
2467     }
2468
2469   /* Allocate a bitmap to be used to store the changed bits.  */
2470   pts = BITMAP_ALLOC (&pta_obstack);
2471
2472   while (changed_count > 0)
2473     {
2474       unsigned int i;
2475       struct topo_info *ti = init_topo_info ();
2476       stats.iterations++;
2477
2478       bitmap_obstack_initialize (&iteration_obstack);
2479
2480       compute_topo_order (graph, ti);
2481
2482       while (VEC_length (unsigned, ti->topo_order) != 0)
2483         {
2484
2485           i = VEC_pop (unsigned, ti->topo_order);
2486
2487           /* If this variable is not a representative, skip it.  */
2488           if (find (i) != i)
2489             continue;
2490
2491           /* In certain indirect cycle cases, we may merge this
2492              variable to another.  */
2493           if (eliminate_indirect_cycles (i) && find (i) != i)
2494             continue;
2495
2496           /* If the node has changed, we need to process the
2497              complex constraints and outgoing edges again.  */
2498           if (TEST_BIT (changed, i))
2499             {
2500               unsigned int j;
2501               constraint_t c;
2502               bitmap solution;
2503               VEC(constraint_t,heap) *complex = graph->complex[i];
2504               bool solution_empty;
2505
2506               RESET_BIT (changed, i);
2507               changed_count--;
2508
2509               /* Compute the changed set of solution bits.  */
2510               bitmap_and_compl (pts, get_varinfo (i)->solution,
2511                                 get_varinfo (i)->oldsolution);
2512
2513               if (bitmap_empty_p (pts))
2514                 continue;
2515
2516               bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2517
2518               solution = get_varinfo (i)->solution;
2519               solution_empty = bitmap_empty_p (solution);
2520
2521               /* Process the complex constraints */
2522               for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2523                 {
2524                   /* XXX: This is going to unsort the constraints in
2525                      some cases, which will occasionally add duplicate
2526                      constraints during unification.  This does not
2527                      affect correctness.  */
2528                   c->lhs.var = find (c->lhs.var);
2529                   c->rhs.var = find (c->rhs.var);
2530
2531                   /* The only complex constraint that can change our
2532                      solution to non-empty, given an empty solution,
2533                      is a constraint where the lhs side is receiving
2534                      some set from elsewhere.  */
2535                   if (!solution_empty || c->lhs.type != DEREF)
2536                     do_complex_constraint (graph, c, pts);
2537                 }
2538
2539               solution_empty = bitmap_empty_p (solution);
2540
2541               if (!solution_empty)
2542                 {
2543                   bitmap_iterator bi;
2544                   unsigned eff_escaped_id = find (escaped_id);
2545
2546                   /* Propagate solution to all successors.  */
2547                   EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2548                                                 0, j, bi)
2549                     {
2550                       bitmap tmp;
2551                       bool flag;
2552
2553                       unsigned int to = find (j);
2554                       tmp = get_varinfo (to)->solution;
2555                       flag = false;
2556
2557                       /* Don't try to propagate to ourselves.  */
2558                       if (to == i)
2559                         continue;
2560
2561                       /* If we propagate from ESCAPED use ESCAPED as
2562                          placeholder.  */
2563                       if (i == eff_escaped_id)
2564                         flag = bitmap_set_bit (tmp, escaped_id);
2565                       else
2566                         flag = set_union_with_increment (tmp, pts, 0);
2567
2568                       if (flag)
2569                         {
2570                           get_varinfo (to)->solution = tmp;
2571                           if (!TEST_BIT (changed, to))
2572                             {
2573                               SET_BIT (changed, to);
2574                               changed_count++;
2575                             }
2576                         }
2577                     }
2578                 }
2579             }
2580         }
2581       free_topo_info (ti);
2582       bitmap_obstack_release (&iteration_obstack);
2583     }
2584
2585   BITMAP_FREE (pts);
2586   sbitmap_free (changed);
2587   bitmap_obstack_release (&oldpta_obstack);
2588 }
2589
2590 /* Map from trees to variable infos.  */
2591 static struct pointer_map_t *vi_for_tree;
2592
2593
2594 /* Insert ID as the variable id for tree T in the vi_for_tree map.  */
2595
2596 static void
2597 insert_vi_for_tree (tree t, varinfo_t vi)
2598 {
2599   void **slot = pointer_map_insert (vi_for_tree, t);
2600   gcc_assert (vi);
2601   gcc_assert (*slot == NULL);
2602   *slot = vi;
2603 }
2604
2605 /* Find the variable info for tree T in VI_FOR_TREE.  If T does not
2606    exist in the map, return NULL, otherwise, return the varinfo we found.  */
2607
2608 static varinfo_t
2609 lookup_vi_for_tree (tree t)
2610 {
2611   void **slot = pointer_map_contains (vi_for_tree, t);
2612   if (slot == NULL)
2613     return NULL;
2614
2615   return (varinfo_t) *slot;
2616 }
2617
2618 /* Return a printable name for DECL  */
2619
2620 static const char *
2621 alias_get_name (tree decl)
2622 {
2623   const char *res = get_name (decl);
2624   char *temp;
2625   int num_printed = 0;
2626
2627   if (res != NULL)
2628     return res;
2629
2630   res = "NULL";
2631   if (!dump_file)
2632     return res;
2633
2634   if (TREE_CODE (decl) == SSA_NAME)
2635     {
2636       num_printed = asprintf (&temp, "%s_%u",
2637                               alias_get_name (SSA_NAME_VAR (decl)),
2638                               SSA_NAME_VERSION (decl));
2639     }
2640   else if (DECL_P (decl))
2641     {
2642       num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2643     }
2644   if (num_printed > 0)
2645     {
2646       res = ggc_strdup (temp);
2647       free (temp);
2648     }
2649   return res;
2650 }
2651
2652 /* Find the variable id for tree T in the map.
2653    If T doesn't exist in the map, create an entry for it and return it.  */
2654
2655 static varinfo_t
2656 get_vi_for_tree (tree t)
2657 {
2658   void **slot = pointer_map_contains (vi_for_tree, t);
2659   if (slot == NULL)
2660     return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2661
2662   return (varinfo_t) *slot;
2663 }
2664
2665 /* Get a scalar constraint expression for a new temporary variable.  */
2666
2667 static struct constraint_expr
2668 new_scalar_tmp_constraint_exp (const char *name)
2669 {
2670   struct constraint_expr tmp;
2671   varinfo_t vi;
2672
2673   vi = new_var_info (NULL_TREE, name);
2674   vi->offset = 0;
2675   vi->size = -1;
2676   vi->fullsize = -1;
2677   vi->is_full_var = 1;
2678
2679   tmp.var = vi->id;
2680   tmp.type = SCALAR;
2681   tmp.offset = 0;
2682
2683   return tmp;
2684 }
2685
2686 /* Get a constraint expression vector from an SSA_VAR_P node.
2687    If address_p is true, the result will be taken its address of.  */
2688
2689 static void
2690 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2691 {
2692   struct constraint_expr cexpr;
2693   varinfo_t vi;
2694
2695   /* We allow FUNCTION_DECLs here even though it doesn't make much sense.  */
2696   gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2697
2698   /* For parameters, get at the points-to set for the actual parm
2699      decl.  */
2700   if (TREE_CODE (t) == SSA_NAME
2701       && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2702       && SSA_NAME_IS_DEFAULT_DEF (t))
2703     {
2704       get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2705       return;
2706     }
2707
2708   vi = get_vi_for_tree (t);
2709   cexpr.var = vi->id;
2710   cexpr.type = SCALAR;
2711   cexpr.offset = 0;
2712   /* If we determine the result is "anything", and we know this is readonly,
2713      say it points to readonly memory instead.  */
2714   if (cexpr.var == anything_id && TREE_READONLY (t))
2715     {
2716       gcc_unreachable ();
2717       cexpr.type = ADDRESSOF;
2718       cexpr.var = readonly_id;
2719     }
2720
2721   /* If we are not taking the address of the constraint expr, add all
2722      sub-fiels of the variable as well.  */
2723   if (!address_p)
2724     {
2725       for (; vi; vi = vi->next)
2726         {
2727           cexpr.var = vi->id;
2728           VEC_safe_push (ce_s, heap, *results, &cexpr);
2729         }
2730       return;
2731     }
2732
2733   VEC_safe_push (ce_s, heap, *results, &cexpr);
2734 }
2735
2736 /* Process constraint T, performing various simplifications and then
2737    adding it to our list of overall constraints.  */
2738
2739 static void
2740 process_constraint (constraint_t t)
2741 {
2742   struct constraint_expr rhs = t->rhs;
2743   struct constraint_expr lhs = t->lhs;
2744
2745   gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2746   gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2747
2748   /* If we didn't get any useful constraint from the lhs we get
2749      &ANYTHING as fallback from get_constraint_for.  Deal with
2750      it here by turning it into *ANYTHING.  */
2751   if (lhs.type == ADDRESSOF
2752       && lhs.var == anything_id)
2753     lhs.type = DEREF;
2754
2755   /* ADDRESSOF on the lhs is invalid.  */
2756   gcc_assert (lhs.type != ADDRESSOF);
2757
2758   /* This can happen in our IR with things like n->a = *p */
2759   if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2760     {
2761       /* Split into tmp = *rhs, *lhs = tmp */
2762       struct constraint_expr tmplhs;
2763       tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
2764       process_constraint (new_constraint (tmplhs, rhs));
2765       process_constraint (new_constraint (lhs, tmplhs));
2766     }
2767   else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2768     {
2769       /* Split into tmp = &rhs, *lhs = tmp */
2770       struct constraint_expr tmplhs;
2771       tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
2772       process_constraint (new_constraint (tmplhs, rhs));
2773       process_constraint (new_constraint (lhs, tmplhs));
2774     }
2775   else
2776     {
2777       gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2778       VEC_safe_push (constraint_t, heap, constraints, t);
2779     }
2780 }
2781
2782 /* Return true if T is a type that could contain pointers.  */
2783
2784 static bool
2785 type_could_have_pointers (tree type)
2786 {
2787   if (POINTER_TYPE_P (type))
2788     return true;
2789
2790   if (TREE_CODE (type) == ARRAY_TYPE)
2791     return type_could_have_pointers (TREE_TYPE (type));
2792
2793   return AGGREGATE_TYPE_P (type);
2794 }
2795
2796 /* Return true if T is a variable of a type that could contain
2797    pointers.  */
2798
2799 static bool
2800 could_have_pointers (tree t)
2801 {
2802   return type_could_have_pointers (TREE_TYPE (t));
2803 }
2804
2805 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2806    structure.  */
2807
2808 static HOST_WIDE_INT
2809 bitpos_of_field (const tree fdecl)
2810 {
2811
2812   if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2813       || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2814     return -1;
2815
2816   return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2817           + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2818 }
2819
2820
2821 /* Get constraint expressions for offsetting PTR by OFFSET.  Stores the
2822    resulting constraint expressions in *RESULTS.  */
2823
2824 static void
2825 get_constraint_for_ptr_offset (tree ptr, tree offset,
2826                                VEC (ce_s, heap) **results)
2827 {
2828   struct constraint_expr c;
2829   unsigned int j, n;
2830   HOST_WIDE_INT rhsunitoffset, rhsoffset;
2831
2832   /* If we do not do field-sensitive PTA adding offsets to pointers
2833      does not change the points-to solution.  */
2834   if (!use_field_sensitive)
2835     {
2836       get_constraint_for (ptr, results);
2837       return;
2838     }
2839
2840   /* If the offset is not a non-negative integer constant that fits
2841      in a HOST_WIDE_INT, we have to fall back to a conservative
2842      solution which includes all sub-fields of all pointed-to
2843      variables of ptr.  */
2844   if (offset == NULL_TREE
2845       || !host_integerp (offset, 0))
2846     rhsoffset = UNKNOWN_OFFSET;
2847   else
2848     {
2849       /* Make sure the bit-offset also fits.  */
2850       rhsunitoffset = TREE_INT_CST_LOW (offset);
2851       rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2852       if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2853         rhsoffset = UNKNOWN_OFFSET;
2854     }
2855
2856   get_constraint_for (ptr, results);
2857   if (rhsoffset == 0)
2858     return;
2859
2860   /* As we are eventually appending to the solution do not use
2861      VEC_iterate here.  */
2862   n = VEC_length (ce_s, *results);
2863   for (j = 0; j < n; j++)
2864     {
2865       varinfo_t curr;
2866       c = *VEC_index (ce_s, *results, j);
2867       curr = get_varinfo (c.var);
2868
2869       if (c.type == ADDRESSOF
2870           /* If this varinfo represents a full variable just use it.  */
2871           && curr->is_full_var)
2872         c.offset = 0;
2873       else if (c.type == ADDRESSOF
2874                /* If we do not know the offset add all subfields.  */
2875                && rhsoffset == UNKNOWN_OFFSET)
2876         {
2877           varinfo_t temp = lookup_vi_for_tree (curr->decl);
2878           do
2879             {
2880               struct constraint_expr c2;
2881               c2.var = temp->id;
2882               c2.type = ADDRESSOF;
2883               c2.offset = 0;
2884               if (c2.var != c.var)
2885                 VEC_safe_push (ce_s, heap, *results, &c2);
2886               temp = temp->next;
2887             }
2888           while (temp);
2889         }
2890       else if (c.type == ADDRESSOF)
2891         {
2892           varinfo_t temp;
2893           unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
2894
2895           /* Search the sub-field which overlaps with the
2896              pointed-to offset.  If the result is outside of the variable
2897              we have to provide a conservative result, as the variable is
2898              still reachable from the resulting pointer (even though it
2899              technically cannot point to anything).  The last and first
2900              sub-fields are such conservative results.
2901              ???  If we always had a sub-field for &object + 1 then
2902              we could represent this in a more precise way.  */
2903           if (rhsoffset < 0
2904               && curr->offset < offset)
2905             offset = 0;
2906           temp = first_or_preceding_vi_for_offset (curr, offset);
2907
2908           /* If the found variable is not exactly at the pointed to
2909              result, we have to include the next variable in the
2910              solution as well.  Otherwise two increments by offset / 2
2911              do not result in the same or a conservative superset
2912              solution.  */
2913           if (temp->offset != offset
2914               && temp->next != NULL)
2915             {
2916               struct constraint_expr c2;
2917               c2.var = temp->next->id;
2918               c2.type = ADDRESSOF;
2919               c2.offset = 0;
2920               VEC_safe_push (ce_s, heap, *results, &c2);
2921             }
2922           c.var = temp->id;
2923           c.offset = 0;
2924         }
2925       else
2926         c.offset = rhsoffset;
2927
2928       VEC_replace (ce_s, *results, j, &c);
2929     }
2930 }
2931
2932
2933 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2934    If address_p is true the result will be taken its address of.  */
2935
2936 static void
2937 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2938                                   bool address_p)
2939 {
2940   tree orig_t = t;
2941   HOST_WIDE_INT bitsize = -1;
2942   HOST_WIDE_INT bitmaxsize = -1;
2943   HOST_WIDE_INT bitpos;
2944   tree forzero;
2945   struct constraint_expr *result;
2946
2947   /* Some people like to do cute things like take the address of
2948      &0->a.b */
2949   forzero = t;
2950   while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2951     forzero = TREE_OPERAND (forzero, 0);
2952
2953   if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2954     {
2955       struct constraint_expr temp;
2956
2957       temp.offset = 0;
2958       temp.var = integer_id;
2959       temp.type = SCALAR;
2960       VEC_safe_push (ce_s, heap, *results, &temp);
2961       return;
2962     }
2963
2964   t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2965
2966   /* Pretend to take the address of the base, we'll take care of
2967      adding the required subset of sub-fields below.  */
2968   get_constraint_for_1 (t, results, true);
2969   gcc_assert (VEC_length (ce_s, *results) == 1);
2970   result = VEC_last (ce_s, *results);
2971
2972   if (result->type == SCALAR
2973       && get_varinfo (result->var)->is_full_var)
2974     /* For single-field vars do not bother about the offset.  */
2975     result->offset = 0;
2976   else if (result->type == SCALAR)
2977     {
2978       /* In languages like C, you can access one past the end of an
2979          array.  You aren't allowed to dereference it, so we can
2980          ignore this constraint. When we handle pointer subtraction,
2981          we may have to do something cute here.  */
2982
2983       if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
2984           && bitmaxsize != 0)
2985         {
2986           /* It's also not true that the constraint will actually start at the
2987              right offset, it may start in some padding.  We only care about
2988              setting the constraint to the first actual field it touches, so
2989              walk to find it.  */
2990           struct constraint_expr cexpr = *result;
2991           varinfo_t curr;
2992           VEC_pop (ce_s, *results);
2993           cexpr.offset = 0;
2994           for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
2995             {
2996               if (ranges_overlap_p (curr->offset, curr->size,
2997                                     bitpos, bitmaxsize))
2998                 {
2999                   cexpr.var = curr->id;
3000                   VEC_safe_push (ce_s, heap, *results, &cexpr);
3001                   if (address_p)
3002                     break;
3003                 }
3004             }
3005           /* If we are going to take the address of this field then
3006              to be able to compute reachability correctly add at least
3007              the last field of the variable.  */
3008           if (address_p
3009               && VEC_length (ce_s, *results) == 0)
3010             {
3011               curr = get_varinfo (cexpr.var);
3012               while (curr->next != NULL)
3013                 curr = curr->next;
3014               cexpr.var = curr->id;
3015               VEC_safe_push (ce_s, heap, *results, &cexpr);
3016             }
3017           else
3018             /* Assert that we found *some* field there. The user couldn't be
3019                accessing *only* padding.  */
3020             /* Still the user could access one past the end of an array
3021                embedded in a struct resulting in accessing *only* padding.  */
3022             gcc_assert (VEC_length (ce_s, *results) >= 1
3023                         || ref_contains_array_ref (orig_t));
3024         }
3025       else if (bitmaxsize == 0)
3026         {
3027           if (dump_file && (dump_flags & TDF_DETAILS))
3028             fprintf (dump_file, "Access to zero-sized part of variable,"
3029                      "ignoring\n");
3030         }
3031       else
3032         if (dump_file && (dump_flags & TDF_DETAILS))
3033           fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3034     }
3035   else if (result->type == DEREF)
3036     {
3037       /* If we do not know exactly where the access goes say so.  Note
3038          that only for non-structure accesses we know that we access
3039          at most one subfiled of any variable.  */
3040       if (bitpos == -1
3041           || bitsize != bitmaxsize
3042           || AGGREGATE_TYPE_P (TREE_TYPE (orig_t)))
3043         result->offset = UNKNOWN_OFFSET;
3044       else
3045         result->offset = bitpos;
3046     }
3047   else if (result->type == ADDRESSOF)
3048     {
3049       /* We can end up here for component references on a
3050          VIEW_CONVERT_EXPR <>(&foobar).  */
3051       result->type = SCALAR;
3052       result->var = anything_id;
3053       result->offset = 0;
3054     }
3055   else
3056     gcc_unreachable ();
3057 }
3058
3059
3060 /* Dereference the constraint expression CONS, and return the result.
3061    DEREF (ADDRESSOF) = SCALAR
3062    DEREF (SCALAR) = DEREF
3063    DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3064    This is needed so that we can handle dereferencing DEREF constraints.  */
3065
3066 static void
3067 do_deref (VEC (ce_s, heap) **constraints)
3068 {
3069   struct constraint_expr *c;
3070   unsigned int i = 0;
3071
3072   for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3073     {
3074       if (c->type == SCALAR)
3075         c->type = DEREF;
3076       else if (c->type == ADDRESSOF)
3077         c->type = SCALAR;
3078       else if (c->type == DEREF)
3079         {
3080           struct constraint_expr tmplhs;
3081           tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3082           process_constraint (new_constraint (tmplhs, *c));
3083           c->var = tmplhs.var;
3084         }
3085       else
3086         gcc_unreachable ();
3087     }
3088 }
3089
3090 static void get_constraint_for_1 (tree, VEC (ce_s, heap) **, bool);
3091
3092 /* Given a tree T, return the constraint expression for taking the
3093    address of it.  */
3094
3095 static void
3096 get_constraint_for_address_of (tree t, VEC (ce_s, heap) **results)
3097 {
3098   struct constraint_expr *c;
3099   unsigned int i;
3100
3101   get_constraint_for_1 (t, results, true);
3102
3103   for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3104     {
3105       if (c->type == DEREF)
3106         c->type = SCALAR;
3107       else
3108         c->type = ADDRESSOF;
3109     }
3110 }
3111
3112 /* Given a tree T, return the constraint expression for it.  */
3113
3114 static void
3115 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3116 {
3117   struct constraint_expr temp;
3118
3119   /* x = integer is all glommed to a single variable, which doesn't
3120      point to anything by itself.  That is, of course, unless it is an
3121      integer constant being treated as a pointer, in which case, we
3122      will return that this is really the addressof anything.  This
3123      happens below, since it will fall into the default case. The only
3124      case we know something about an integer treated like a pointer is
3125      when it is the NULL pointer, and then we just say it points to
3126      NULL.
3127
3128      Do not do that if -fno-delete-null-pointer-checks though, because
3129      in that case *NULL does not fail, so it _should_ alias *anything.
3130      It is not worth adding a new option or renaming the existing one,
3131      since this case is relatively obscure.  */
3132   if (flag_delete_null_pointer_checks
3133       && ((TREE_CODE (t) == INTEGER_CST
3134            && integer_zerop (t))
3135           /* The only valid CONSTRUCTORs in gimple with pointer typed
3136              elements are zero-initializer.  */
3137           || TREE_CODE (t) == CONSTRUCTOR))
3138     {
3139       temp.var = nothing_id;
3140       temp.type = ADDRESSOF;
3141       temp.offset = 0;
3142       VEC_safe_push (ce_s, heap, *results, &temp);
3143       return;
3144     }
3145
3146   /* String constants are read-only.  */
3147   if (TREE_CODE (t) == STRING_CST)
3148     {
3149       temp.var = readonly_id;
3150       temp.type = SCALAR;
3151       temp.offset = 0;
3152       VEC_safe_push (ce_s, heap, *results, &temp);
3153       return;
3154     }
3155
3156   switch (TREE_CODE_CLASS (TREE_CODE (t)))
3157     {
3158     case tcc_expression:
3159       {
3160         switch (TREE_CODE (t))
3161           {
3162           case ADDR_EXPR:
3163             get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3164             return;
3165           default:;
3166           }
3167         break;
3168       }
3169     case tcc_reference:
3170       {
3171         switch (TREE_CODE (t))
3172           {
3173           case INDIRECT_REF:
3174             {
3175               get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3176               do_deref (results);
3177               return;
3178             }
3179           case ARRAY_REF:
3180           case ARRAY_RANGE_REF:
3181           case COMPONENT_REF:
3182             get_constraint_for_component_ref (t, results, address_p);
3183             return;
3184           case VIEW_CONVERT_EXPR:
3185             get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3186             return;
3187           /* We are missing handling for TARGET_MEM_REF here.  */
3188           default:;
3189           }
3190         break;
3191       }
3192     case tcc_exceptional:
3193       {
3194         switch (TREE_CODE (t))
3195           {
3196           case SSA_NAME:
3197             {
3198               get_constraint_for_ssa_var (t, results, address_p);
3199               return;
3200             }
3201           default:;
3202           }
3203         break;
3204       }
3205     case tcc_declaration:
3206       {
3207         get_constraint_for_ssa_var (t, results, address_p);
3208         return;
3209       }
3210     default:;
3211     }
3212
3213   /* The default fallback is a constraint from anything.  */
3214   temp.type = ADDRESSOF;
3215   temp.var = anything_id;
3216   temp.offset = 0;
3217   VEC_safe_push (ce_s, heap, *results, &temp);
3218 }
3219
3220 /* Given a gimple tree T, return the constraint expression vector for it.  */
3221
3222 static void
3223 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3224 {
3225   gcc_assert (VEC_length (ce_s, *results) == 0);
3226
3227   get_constraint_for_1 (t, results, false);
3228 }
3229
3230
3231 /* Efficiently generates constraints from all entries in *RHSC to all
3232    entries in *LHSC.  */
3233
3234 static void
3235 process_all_all_constraints (VEC (ce_s, heap) *lhsc, VEC (ce_s, heap) *rhsc)
3236 {
3237   struct constraint_expr *lhsp, *rhsp;
3238   unsigned i, j;
3239
3240   if (VEC_length (ce_s, lhsc) <= 1
3241       || VEC_length (ce_s, rhsc) <= 1)
3242     {
3243       for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3244         for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); ++j)
3245           process_constraint (new_constraint (*lhsp, *rhsp));
3246     }
3247   else
3248     {
3249       struct constraint_expr tmp;
3250       tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3251       for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
3252         process_constraint (new_constraint (tmp, *rhsp));
3253       for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3254         process_constraint (new_constraint (*lhsp, tmp));
3255     }
3256 }
3257
3258 /* Handle aggregate copies by expanding into copies of the respective
3259    fields of the structures.  */
3260
3261 static void
3262 do_structure_copy (tree lhsop, tree rhsop)
3263 {
3264   struct constraint_expr *lhsp, *rhsp;
3265   VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3266   unsigned j;
3267
3268   get_constraint_for (lhsop, &lhsc);
3269   get_constraint_for (rhsop, &rhsc);
3270   lhsp = VEC_index (ce_s, lhsc, 0);
3271   rhsp = VEC_index (ce_s, rhsc, 0);
3272   if (lhsp->type == DEREF
3273       || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3274       || rhsp->type == DEREF)
3275     process_all_all_constraints (lhsc, rhsc);
3276   else if (lhsp->type == SCALAR
3277            && (rhsp->type == SCALAR
3278                || rhsp->type == ADDRESSOF))
3279     {
3280       tree lhsbase, rhsbase;
3281       HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3282       HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3283       unsigned k = 0;
3284       lhsbase = get_ref_base_and_extent (lhsop, &lhsoffset,
3285                                          &lhssize, &lhsmaxsize);
3286       rhsbase = get_ref_base_and_extent (rhsop, &rhsoffset,
3287                                          &rhssize, &rhsmaxsize);
3288       for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp);)
3289         {
3290           varinfo_t lhsv, rhsv;
3291           rhsp = VEC_index (ce_s, rhsc, k);
3292           lhsv = get_varinfo (lhsp->var);
3293           rhsv = get_varinfo (rhsp->var);
3294           if (lhsv->may_have_pointers
3295               && ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3296                                    rhsv->offset + lhsoffset, rhsv->size))
3297             process_constraint (new_constraint (*lhsp, *rhsp));
3298           if (lhsv->offset + rhsoffset + lhsv->size
3299               > rhsv->offset + lhsoffset + rhsv->size)
3300             {
3301               ++k;
3302               if (k >= VEC_length (ce_s, rhsc))
3303                 break;
3304             }
3305           else
3306             ++j;
3307         }
3308     }
3309   else
3310     gcc_unreachable ();
3311
3312   VEC_free (ce_s, heap, lhsc);
3313   VEC_free (ce_s, heap, rhsc);
3314 }
3315
3316 /* Create a constraint ID = OP.  */
3317
3318 static void
3319 make_constraint_to (unsigned id, tree op)
3320 {
3321   VEC(ce_s, heap) *rhsc = NULL;
3322   struct constraint_expr *c;
3323   struct constraint_expr includes;
3324   unsigned int j;
3325
3326   includes.var = id;
3327   includes.offset = 0;
3328   includes.type = SCALAR;
3329
3330   get_constraint_for (op, &rhsc);
3331   for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3332     process_constraint (new_constraint (includes, *c));
3333   VEC_free (ce_s, heap, rhsc);
3334 }
3335
3336 /* Create a constraint ID = &FROM.  */
3337
3338 static void
3339 make_constraint_from (varinfo_t vi, int from)
3340 {
3341   struct constraint_expr lhs, rhs;
3342
3343   lhs.var = vi->id;
3344   lhs.offset = 0;
3345   lhs.type = SCALAR;
3346
3347   rhs.var = from;
3348   rhs.offset = 0;
3349   rhs.type = ADDRESSOF;
3350   process_constraint (new_constraint (lhs, rhs));
3351 }
3352
3353 /* Create a constraint ID = FROM.  */
3354
3355 static void
3356 make_copy_constraint (varinfo_t vi, int from)
3357 {
3358   struct constraint_expr lhs, rhs;
3359
3360   lhs.var = vi->id;
3361   lhs.offset = 0;
3362   lhs.type = SCALAR;
3363
3364   rhs.var = from;
3365   rhs.offset = 0;
3366   rhs.type = SCALAR;
3367   process_constraint (new_constraint (lhs, rhs));
3368 }
3369
3370 /* Make constraints necessary to make OP escape.  */
3371
3372 static void
3373 make_escape_constraint (tree op)
3374 {
3375   make_constraint_to (escaped_id, op);
3376 }
3377
3378 /* Create a new artificial heap variable with NAME and make a
3379    constraint from it to LHS.  Return the created variable.  */
3380
3381 static varinfo_t
3382 make_constraint_from_heapvar (varinfo_t lhs, const char *name)
3383 {
3384   varinfo_t vi;
3385   tree heapvar = heapvar_lookup (lhs->decl, lhs->offset);
3386
3387   if (heapvar == NULL_TREE)
3388     {
3389       var_ann_t ann;
3390       heapvar = create_tmp_var_raw (ptr_type_node, name);
3391       DECL_EXTERNAL (heapvar) = 1;
3392
3393       heapvar_insert (lhs->decl, lhs->offset, heapvar);
3394
3395       ann = get_var_ann (heapvar);
3396       ann->is_heapvar = 1;
3397     }
3398
3399   /* For global vars we need to add a heapvar to the list of referenced
3400      vars of a different function than it was created for originally.  */
3401   if (gimple_referenced_vars (cfun))
3402     add_referenced_var (heapvar);
3403
3404   vi = new_var_info (heapvar, name);
3405   vi->is_artificial_var = true;
3406   vi->is_heap_var = true;
3407   vi->is_unknown_size_var = true;
3408   vi->offset = 0;
3409   vi->fullsize = ~0;
3410   vi->size = ~0;
3411   vi->is_full_var = true;
3412   insert_vi_for_tree (heapvar, vi);
3413
3414   make_constraint_from (lhs, vi->id);
3415
3416   return vi;
3417 }
3418
3419 /* Create a new artificial heap variable with NAME and make a
3420    constraint from it to LHS.  Set flags according to a tag used
3421    for tracking restrict pointers.  */
3422
3423 static void
3424 make_constraint_from_restrict (varinfo_t lhs, const char *name)
3425 {
3426   varinfo_t vi;
3427   vi = make_constraint_from_heapvar (lhs, name);
3428   vi->is_restrict_var = 1;
3429   vi->is_global_var = 0;
3430   vi->is_special_var = 1;
3431   vi->may_have_pointers = 0;
3432 }
3433
3434 /* For non-IPA mode, generate constraints necessary for a call on the
3435    RHS.  */
3436
3437 static void
3438 handle_rhs_call (gimple stmt, VEC(ce_s, heap) **results)
3439 {
3440   struct constraint_expr rhsc;
3441   unsigned i;
3442
3443   for (i = 0; i < gimple_call_num_args (stmt); ++i)
3444     {
3445       tree arg = gimple_call_arg (stmt, i);
3446
3447       /* Find those pointers being passed, and make sure they end up
3448          pointing to anything.  */
3449       if (could_have_pointers (arg))
3450         make_escape_constraint (arg);
3451     }
3452
3453   /* The static chain escapes as well.  */
3454   if (gimple_call_chain (stmt))
3455     make_escape_constraint (gimple_call_chain (stmt));
3456
3457   /* And if we applied NRV the address of the return slot escapes as well.  */
3458   if (gimple_call_return_slot_opt_p (stmt)
3459       && gimple_call_lhs (stmt) != NULL_TREE
3460       && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
3461     {
3462       VEC(ce_s, heap) *tmpc = NULL;
3463       struct constraint_expr lhsc, *c;
3464       get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
3465       lhsc.var = escaped_id;
3466       lhsc.offset = 0;
3467       lhsc.type = SCALAR;
3468       for (i = 0; VEC_iterate (ce_s, tmpc, i, c); ++i)
3469         process_constraint (new_constraint (lhsc, *c));
3470       VEC_free(ce_s, heap, tmpc);
3471     }
3472
3473   /* Regular functions return nonlocal memory.  */
3474   rhsc.var = nonlocal_id;
3475   rhsc.offset = 0;
3476   rhsc.type = SCALAR;
3477   VEC_safe_push (ce_s, heap, *results, &rhsc);
3478 }
3479
3480 /* For non-IPA mode, generate constraints necessary for a call
3481    that returns a pointer and assigns it to LHS.  This simply makes
3482    the LHS point to global and escaped variables.  */
3483
3484 static void
3485 handle_lhs_call (tree lhs, int flags, VEC(ce_s, heap) *rhsc)
3486 {
3487   VEC(ce_s, heap) *lhsc = NULL;
3488
3489   get_constraint_for (lhs, &lhsc);
3490
3491   if (flags & ECF_MALLOC)
3492     {
3493       varinfo_t vi;
3494       vi = make_constraint_from_heapvar (get_vi_for_tree (lhs), "HEAP");
3495       /* We delay marking allocated storage global until we know if
3496          it escapes.  */
3497       DECL_EXTERNAL (vi->decl) = 0;
3498       vi->is_global_var = 0;
3499     }
3500   else if (VEC_length (ce_s, rhsc) > 0)
3501     {
3502       /* If the store is to a global decl make sure to
3503          add proper escape constraints.  */
3504       lhs = get_base_address (lhs);
3505       if (lhs
3506           && DECL_P (lhs)
3507           && is_global_var (lhs))
3508         {
3509           struct constraint_expr tmpc;
3510           tmpc.var = escaped_id;
3511           tmpc.offset = 0;
3512           tmpc.type = SCALAR;
3513           VEC_safe_push (ce_s, heap, lhsc, &tmpc);
3514         }
3515       process_all_all_constraints (lhsc, rhsc);
3516     }
3517   VEC_free (ce_s, heap, lhsc);
3518 }
3519
3520 /* For non-IPA mode, generate constraints necessary for a call of a
3521    const function that returns a pointer in the statement STMT.  */
3522
3523 static void
3524 handle_const_call (gimple stmt, VEC(ce_s, heap) **results)
3525 {
3526   struct constraint_expr rhsc;
3527   unsigned int k;
3528
3529   /* Treat nested const functions the same as pure functions as far
3530      as the static chain is concerned.  */
3531   if (gimple_call_chain (stmt))
3532     {
3533       make_constraint_to (callused_id, gimple_call_chain (stmt));
3534       rhsc.var = callused_id;
3535       rhsc.offset = 0;
3536       rhsc.type = SCALAR;
3537       VEC_safe_push (ce_s, heap, *results, &rhsc);
3538     }
3539
3540   /* May return arguments.  */
3541   for (k = 0; k < gimple_call_num_args (stmt); ++k)
3542     {
3543       tree arg = gimple_call_arg (stmt, k);
3544
3545       if (could_have_pointers (arg))
3546         {
3547           VEC(ce_s, heap) *argc = NULL;
3548           unsigned i;
3549           struct constraint_expr *argp;
3550           get_constraint_for (arg, &argc);
3551           for (i = 0; VEC_iterate (ce_s, argc, i, argp); ++i)
3552             VEC_safe_push (ce_s, heap, *results, argp);
3553           VEC_free(ce_s, heap, argc);
3554         }
3555     }
3556
3557   /* May return addresses of globals.  */
3558   rhsc.var = nonlocal_id;
3559   rhsc.offset = 0;
3560   rhsc.type = ADDRESSOF;
3561   VEC_safe_push (ce_s, heap, *results, &rhsc);
3562 }
3563
3564 /* For non-IPA mode, generate constraints necessary for a call to a
3565    pure function in statement STMT.  */
3566
3567 static void
3568 handle_pure_call (gimple stmt, VEC(ce_s, heap) **results)
3569 {
3570   struct constraint_expr rhsc;
3571   unsigned i;
3572   bool need_callused = false;
3573
3574   /* Memory reached from pointer arguments is call-used.  */
3575   for (i = 0; i < gimple_call_num_args (stmt); ++i)
3576     {
3577       tree arg = gimple_call_arg (stmt, i);
3578
3579       if (could_have_pointers (arg))
3580         {
3581           make_constraint_to (callused_id, arg);
3582           need_callused = true;
3583         }
3584     }
3585
3586   /* The static chain is used as well.  */
3587   if (gimple_call_chain (stmt))
3588     {
3589       make_constraint_to (callused_id, gimple_call_chain (stmt));
3590       need_callused = true;
3591     }
3592
3593   /* Pure functions may return callused and nonlocal memory.  */
3594   if (need_callused)
3595     {
3596       rhsc.var = callused_id;
3597       rhsc.offset = 0;
3598       rhsc.type = SCALAR;
3599       VEC_safe_push (ce_s, heap, *results, &rhsc);
3600     }
3601   rhsc.var = nonlocal_id;
3602   rhsc.offset = 0;
3603   rhsc.type = SCALAR;
3604   VEC_safe_push (ce_s, heap, *results, &rhsc);
3605 }
3606
3607 /* Walk statement T setting up aliasing constraints according to the
3608    references found in T.  This function is the main part of the
3609    constraint builder.  AI points to auxiliary alias information used
3610    when building alias sets and computing alias grouping heuristics.  */
3611
3612 static void
3613 find_func_aliases (gimple origt)
3614 {
3615   gimple t = origt;
3616   VEC(ce_s, heap) *lhsc = NULL;
3617   VEC(ce_s, heap) *rhsc = NULL;
3618   struct constraint_expr *c;
3619
3620   /* Now build constraints expressions.  */
3621   if (gimple_code (t) == GIMPLE_PHI)
3622     {
3623       gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3624
3625       /* Only care about pointers and structures containing
3626          pointers.  */
3627       if (could_have_pointers (gimple_phi_result (t)))
3628         {
3629           size_t i;
3630           unsigned int j;
3631
3632           /* For a phi node, assign all the arguments to
3633              the result.  */
3634           get_constraint_for (gimple_phi_result (t), &lhsc);
3635           for (i = 0; i < gimple_phi_num_args (t); i++)
3636             {
3637               tree rhstype;
3638               tree strippedrhs = PHI_ARG_DEF (t, i);
3639
3640               STRIP_NOPS (strippedrhs);
3641               rhstype = TREE_TYPE (strippedrhs);
3642               get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3643
3644               for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3645                 {
3646                   struct constraint_expr *c2;
3647                   while (VEC_length (ce_s, rhsc) > 0)
3648                     {
3649                       c2 = VEC_last (ce_s, rhsc);
3650                       process_constraint (new_constraint (*c, *c2));
3651                       VEC_pop (ce_s, rhsc);
3652                     }
3653                 }
3654             }
3655         }
3656     }
3657   /* In IPA mode, we need to generate constraints to pass call
3658      arguments through their calls.   There are two cases,
3659      either a GIMPLE_CALL returning a value, or just a plain
3660      GIMPLE_CALL when we are not.
3661
3662      In non-ipa mode, we need to generate constraints for each
3663      pointer passed by address.  */
3664   else if (is_gimple_call (t))
3665     {
3666       tree fndecl;
3667       if ((fndecl = gimple_call_fndecl (t)) != NULL_TREE
3668           && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
3669         /* ???  All builtins that are handled here need to be handled
3670            in the alias-oracle query functions explicitly!  */
3671         switch (DECL_FUNCTION_CODE (fndecl))
3672           {
3673           /* All the following functions return a pointer to the same object
3674              as their first argument points to.  The functions do not add
3675              to the ESCAPED solution.  The functions make the first argument
3676              pointed to memory point to what the second argument pointed to
3677              memory points to.  */
3678           case BUILT_IN_STRCPY:
3679           case BUILT_IN_STRNCPY:
3680           case BUILT_IN_BCOPY:
3681           case BUILT_IN_MEMCPY:
3682           case BUILT_IN_MEMMOVE:
3683           case BUILT_IN_MEMPCPY:
3684           case BUILT_IN_STPCPY:
3685           case BUILT_IN_STPNCPY:
3686           case BUILT_IN_STRCAT:
3687           case BUILT_IN_STRNCAT:
3688             {
3689               tree res = gimple_call_lhs (t);
3690               tree dest = gimple_call_arg (t, 0);
3691               tree src = gimple_call_arg (t, 1);
3692               if (res != NULL_TREE)
3693                 {
3694                   get_constraint_for (res, &lhsc);
3695                   if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
3696                       || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
3697                       || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY)
3698                     get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
3699                   else
3700                     get_constraint_for (dest, &rhsc);
3701                   process_all_all_constraints (lhsc, rhsc);
3702                   VEC_free (ce_s, heap, lhsc);
3703                   VEC_free (ce_s, heap, rhsc);
3704                 }
3705               get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3706               get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
3707               do_deref (&lhsc);
3708               do_deref (&rhsc);
3709               process_all_all_constraints (lhsc, rhsc);
3710               VEC_free (ce_s, heap, lhsc);
3711               VEC_free (ce_s, heap, rhsc);
3712               return;
3713             }
3714           case BUILT_IN_MEMSET:
3715             {
3716               tree res = gimple_call_lhs (t);
3717               tree dest = gimple_call_arg (t, 0);
3718               unsigned i;
3719               ce_s *lhsp;
3720               struct constraint_expr ac;
3721               if (res != NULL_TREE)
3722                 {
3723                   get_constraint_for (res, &lhsc);
3724                   get_constraint_for (dest, &rhsc);
3725                   process_all_all_constraints (lhsc, rhsc);
3726                   VEC_free (ce_s, heap, lhsc);
3727                   VEC_free (ce_s, heap, rhsc);
3728                 }
3729               get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3730               do_deref (&lhsc);
3731               if (flag_delete_null_pointer_checks
3732                   && integer_zerop (gimple_call_arg (t, 1)))
3733                 {
3734                   ac.type = ADDRESSOF;
3735                   ac.var = nothing_id;
3736                 }
3737               else
3738                 {
3739                   ac.type = SCALAR;
3740                   ac.var = integer_id;
3741                 }
3742               ac.offset = 0;
3743               for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3744                 process_constraint (new_constraint (*lhsp, ac));
3745               VEC_free (ce_s, heap, lhsc);
3746               return;
3747             }
3748           /* All the following functions do not return pointers, do not
3749              modify the points-to sets of memory reachable from their
3750              arguments and do not add to the ESCAPED solution.  */
3751           case BUILT_IN_SINCOS:
3752           case BUILT_IN_SINCOSF:
3753           case BUILT_IN_SINCOSL:
3754           case BUILT_IN_FREXP:
3755           case BUILT_IN_FREXPF:
3756           case BUILT_IN_FREXPL:
3757           case BUILT_IN_GAMMA_R:
3758           case BUILT_IN_GAMMAF_R:
3759           case BUILT_IN_GAMMAL_R:
3760           case BUILT_IN_LGAMMA_R:
3761           case BUILT_IN_LGAMMAF_R:
3762           case BUILT_IN_LGAMMAL_R:
3763           case BUILT_IN_MODF:
3764           case BUILT_IN_MODFF:
3765           case BUILT_IN_MODFL:
3766           case BUILT_IN_REMQUO:
3767           case BUILT_IN_REMQUOF:
3768           case BUILT_IN_REMQUOL:
3769           case BUILT_IN_FREE:
3770             return;
3771           /* printf-style functions may have hooks to set pointers to
3772              point to somewhere into the generated string.  Leave them
3773              for a later excercise...  */
3774           default:
3775             /* Fallthru to general call handling.  */;
3776           }
3777       if (!in_ipa_mode)
3778         {
3779           VEC(ce_s, heap) *rhsc = NULL;
3780           int flags = gimple_call_flags (t);
3781
3782           /* Const functions can return their arguments and addresses
3783              of global memory but not of escaped memory.  */
3784           if (flags & (ECF_CONST|ECF_NOVOPS))
3785             {
3786               if (gimple_call_lhs (t)
3787                   && could_have_pointers (gimple_call_lhs (t)))
3788                 handle_const_call (t, &rhsc);
3789             }
3790           /* Pure functions can return addresses in and of memory
3791              reachable from their arguments, but they are not an escape
3792              point for reachable memory of their arguments.  */
3793           else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
3794             handle_pure_call (t, &rhsc);
3795           else
3796             handle_rhs_call (t, &rhsc);
3797           if (gimple_call_lhs (t)
3798               && could_have_pointers (gimple_call_lhs (t)))
3799             handle_lhs_call (gimple_call_lhs (t), flags, rhsc);
3800           VEC_free (ce_s, heap, rhsc);
3801         }
3802       else
3803         {
3804           tree lhsop;
3805           varinfo_t fi;
3806           int i = 1;
3807           size_t j;
3808           tree decl;
3809
3810           lhsop = gimple_call_lhs (t);
3811           decl = gimple_call_fndecl (t);
3812
3813           /* If we can directly resolve the function being called, do so.
3814              Otherwise, it must be some sort of indirect expression that
3815              we should still be able to handle.  */
3816           if (decl)
3817             fi = get_vi_for_tree (decl);
3818           else
3819             {
3820               decl = gimple_call_fn (t);
3821               fi = get_vi_for_tree (decl);
3822             }
3823
3824           /* Assign all the passed arguments to the appropriate incoming
3825              parameters of the function.  */
3826           for (j = 0; j < gimple_call_num_args (t); j++)
3827             {
3828               struct constraint_expr lhs ;
3829               struct constraint_expr *rhsp;
3830               tree arg = gimple_call_arg (t, j);
3831
3832               get_constraint_for (arg, &rhsc);
3833               if (TREE_CODE (decl) != FUNCTION_DECL)
3834                 {
3835                   lhs.type = DEREF;
3836                   lhs.var = fi->id;
3837                   lhs.offset = i;
3838                 }
3839               else
3840                 {
3841                   lhs.type = SCALAR;
3842                   lhs.var = first_vi_for_offset (fi, i)->id;
3843                   lhs.offset = 0;
3844                 }
3845               while (VEC_length (ce_s, rhsc) != 0)
3846                 {
3847                   rhsp = VEC_last (ce_s, rhsc);
3848                   process_constraint (new_constraint (lhs, *rhsp));
3849                   VEC_pop (ce_s, rhsc);
3850                 }
3851               i++;
3852             }
3853
3854           /* If we are returning a value, assign it to the result.  */
3855           if (lhsop)
3856             {
3857               struct constraint_expr rhs;
3858               struct constraint_expr *lhsp;
3859               unsigned int j = 0;
3860
3861               get_constraint_for (lhsop, &lhsc);
3862               if (TREE_CODE (decl) != FUNCTION_DECL)
3863                 {
3864                   rhs.type = DEREF;
3865                   rhs.var = fi->id;
3866                   rhs.offset = i;
3867                 }
3868               else
3869                 {
3870                   rhs.type = SCALAR;
3871                   rhs.var = first_vi_for_offset (fi, i)->id;
3872                   rhs.offset = 0;
3873                 }
3874               for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3875                 process_constraint (new_constraint (*lhsp, rhs));
3876             }
3877         }
3878     }
3879   /* Otherwise, just a regular assignment statement.  Only care about
3880      operations with pointer result, others are dealt with as escape
3881      points if they have pointer operands.  */
3882   else if (is_gimple_assign (t)
3883            && could_have_pointers (gimple_assign_lhs (t)))
3884     {
3885       /* Otherwise, just a regular assignment statement.  */
3886       tree lhsop = gimple_assign_lhs (t);
3887       tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
3888
3889       if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
3890         do_structure_copy (lhsop, rhsop);
3891       else
3892         {
3893           struct constraint_expr temp;
3894           get_constraint_for (lhsop, &lhsc);
3895
3896           if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
3897             get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
3898                                            gimple_assign_rhs2 (t), &rhsc);
3899           else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3900                     && !(POINTER_TYPE_P (gimple_expr_type (t))
3901                          && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
3902                    || gimple_assign_single_p (t))
3903             get_constraint_for (rhsop, &rhsc);
3904           else
3905             {
3906               temp.type = ADDRESSOF;
3907               temp.var = anything_id;
3908               temp.offset = 0;
3909               VEC_safe_push (ce_s, heap, rhsc, &temp);
3910             }
3911           process_all_all_constraints (lhsc, rhsc);
3912         }
3913       /* If there is a store to a global variable the rhs escapes.  */
3914       if ((lhsop = get_base_address (lhsop)) != NULL_TREE
3915           && DECL_P (lhsop)
3916           && is_global_var (lhsop))
3917         make_escape_constraint (rhsop);
3918       /* If this is a conversion of a non-restrict pointer to a
3919          restrict pointer track it with a new heapvar.  */
3920       else if (gimple_assign_cast_p (t)
3921                && POINTER_TYPE_P (TREE_TYPE (rhsop))
3922                && POINTER_TYPE_P (TREE_TYPE (lhsop))
3923                && !TYPE_RESTRICT (TREE_TYPE (rhsop))
3924                && TYPE_RESTRICT (TREE_TYPE (lhsop)))
3925         make_constraint_from_restrict (get_vi_for_tree (lhsop),
3926                                        "CAST_RESTRICT");
3927     }
3928   /* For conversions of pointers to non-pointers the pointer escapes.  */
3929   else if (gimple_assign_cast_p (t)
3930            && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (t)))
3931            && !POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (t))))
3932     {
3933       make_escape_constraint (gimple_assign_rhs1 (t));
3934     }
3935   /* Handle escapes through return.  */
3936   else if (gimple_code (t) == GIMPLE_RETURN
3937            && gimple_return_retval (t) != NULL_TREE
3938            && could_have_pointers (gimple_return_retval (t)))
3939     {
3940       make_escape_constraint (gimple_return_retval (t));
3941     }
3942   /* Handle asms conservatively by adding escape constraints to everything.  */
3943   else if (gimple_code (t) == GIMPLE_ASM)
3944     {
3945       unsigned i, noutputs;
3946       const char **oconstraints;
3947       const char *constraint;
3948       bool allows_mem, allows_reg, is_inout;
3949
3950       noutputs = gimple_asm_noutputs (t);
3951       oconstraints = XALLOCAVEC (const char *, noutputs);
3952
3953       for (i = 0; i < noutputs; ++i)
3954         {
3955           tree link = gimple_asm_output_op (t, i);
3956           tree op = TREE_VALUE (link);
3957
3958           constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
3959           oconstraints[i] = constraint;
3960           parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
3961                                    &allows_reg, &is_inout);
3962
3963           /* A memory constraint makes the address of the operand escape.  */
3964           if (!allows_reg && allows_mem)
3965             make_escape_constraint (build_fold_addr_expr (op));
3966
3967           /* The asm may read global memory, so outputs may point to
3968              any global memory.  */
3969           if (op && could_have_pointers (op))
3970             {
3971               VEC(ce_s, heap) *lhsc = NULL;
3972               struct constraint_expr rhsc, *lhsp;
3973               unsigned j;
3974               get_constraint_for (op, &lhsc);
3975               rhsc.var = nonlocal_id;
3976               rhsc.offset = 0;
3977               rhsc.type = SCALAR;
3978               for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3979                 process_constraint (new_constraint (*lhsp, rhsc));
3980               VEC_free (ce_s, heap, lhsc);
3981             }
3982         }
3983       for (i = 0; i < gimple_asm_ninputs (t); ++i)
3984         {
3985           tree link = gimple_asm_input_op (t, i);
3986           tree op = TREE_VALUE (link);
3987
3988           constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
3989
3990           parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
3991                                   &allows_mem, &allows_reg);
3992
3993           /* A memory constraint makes the address of the operand escape.  */
3994           if (!allows_reg && allows_mem)
3995             make_escape_constraint (build_fold_addr_expr (op));
3996           /* Strictly we'd only need the constraint to ESCAPED if
3997              the asm clobbers memory, otherwise using CALLUSED
3998              would be enough.  */
3999           else if (op && could_have_pointers (op))
4000             make_escape_constraint (op);
4001         }
4002     }
4003
4004   VEC_free (ce_s, heap, rhsc);
4005   VEC_free (ce_s, heap, lhsc);
4006 }
4007
4008
4009 /* Find the first varinfo in the same variable as START that overlaps with
4010    OFFSET.  Return NULL if we can't find one.  */
4011
4012 static varinfo_t
4013 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
4014 {
4015   /* If the offset is outside of the variable, bail out.  */
4016   if (offset >= start->fullsize)
4017     return NULL;
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   while (start)
4025     {
4026       /* We may not find a variable in the field list with the actual
4027          offset when when we have glommed a structure to a variable.
4028          In that case, however, offset should still be within the size
4029          of the variable. */
4030       if (offset >= start->offset
4031           && offset < (start->offset + start->size))
4032         return start;
4033
4034       start= start->next;
4035     }
4036
4037   return NULL;
4038 }
4039
4040 /* Find the first varinfo in the same variable as START that overlaps with
4041    OFFSET.  If there is no such varinfo the varinfo directly preceding
4042    OFFSET is returned.  */
4043
4044 static varinfo_t
4045 first_or_preceding_vi_for_offset (varinfo_t start,
4046                                   unsigned HOST_WIDE_INT offset)
4047 {
4048   /* If we cannot reach offset from start, lookup the first field
4049      and start from there.  */
4050   if (start->offset > offset)
4051     start = lookup_vi_for_tree (start->decl);
4052
4053   /* We may not find a variable in the field list with the actual
4054      offset when when we have glommed a structure to a variable.
4055      In that case, however, offset should still be within the size
4056      of the variable.
4057      If we got beyond the offset we look for return the field
4058      directly preceding offset which may be the last field.  */
4059   while (start->next
4060          && offset >= start->offset
4061          && !(offset < (start->offset + start->size)))
4062     start = start->next;
4063
4064   return start;
4065 }
4066
4067
4068 /* Insert the varinfo FIELD into the field list for BASE, at the front
4069    of the list.  */
4070
4071 static void
4072 insert_into_field_list (varinfo_t base, varinfo_t field)
4073 {
4074   varinfo_t prev = base;
4075   varinfo_t curr = base->next;
4076
4077   field->next = curr;
4078   prev->next = field;
4079 }
4080
4081 /* Insert the varinfo FIELD into the field list for BASE, ordered by
4082    offset.  */
4083
4084 static void
4085 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
4086 {
4087   varinfo_t prev = base;
4088   varinfo_t curr = base->next;
4089
4090   if (curr == NULL)
4091     {
4092       prev->next = field;
4093       field->next = NULL;
4094     }
4095   else
4096     {
4097       while (curr)
4098         {
4099           if (field->offset <= curr->offset)
4100             break;
4101           prev = curr;
4102           curr = curr->next;
4103         }
4104       field->next = prev->next;
4105       prev->next = field;
4106     }
4107 }
4108
4109 /* This structure is used during pushing fields onto the fieldstack
4110    to track the offset of the field, since bitpos_of_field gives it
4111    relative to its immediate containing type, and we want it relative
4112    to the ultimate containing object.  */
4113
4114 struct fieldoff
4115 {
4116   /* Offset from the base of the base containing object to this field.  */
4117   HOST_WIDE_INT offset;
4118
4119   /* Size, in bits, of the field.  */
4120   unsigned HOST_WIDE_INT size;
4121
4122   unsigned has_unknown_size : 1;
4123
4124   unsigned may_have_pointers : 1;
4125
4126   unsigned only_restrict_pointers : 1;
4127 };
4128 typedef struct fieldoff fieldoff_s;
4129
4130 DEF_VEC_O(fieldoff_s);
4131 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4132
4133 /* qsort comparison function for two fieldoff's PA and PB */
4134
4135 static int
4136 fieldoff_compare (const void *pa, const void *pb)
4137 {
4138   const fieldoff_s *foa = (const fieldoff_s *)pa;
4139   const fieldoff_s *fob = (const fieldoff_s *)pb;
4140   unsigned HOST_WIDE_INT foasize, fobsize;
4141
4142   if (foa->offset < fob->offset)
4143     return -1;
4144   else if (foa->offset > fob->offset)
4145     return 1;
4146
4147   foasize = foa->size;
4148   fobsize = fob->size;
4149   if (foasize < fobsize)
4150     return -1;
4151   else if (foasize > fobsize)
4152     return 1;
4153   return 0;
4154 }
4155
4156 /* Sort a fieldstack according to the field offset and sizes.  */
4157 static void
4158 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4159 {
4160   qsort (VEC_address (fieldoff_s, fieldstack),
4161          VEC_length (fieldoff_s, fieldstack),
4162          sizeof (fieldoff_s),
4163          fieldoff_compare);
4164 }
4165
4166 /* Return true if V is a tree that we can have subvars for.
4167    Normally, this is any aggregate type.  Also complex
4168    types which are not gimple registers can have subvars.  */
4169
4170 static inline bool
4171 var_can_have_subvars (const_tree v)
4172 {
4173   /* Volatile variables should never have subvars.  */
4174   if (TREE_THIS_VOLATILE (v))
4175     return false;
4176
4177   /* Non decls or memory tags can never have subvars.  */
4178   if (!DECL_P (v))
4179     return false;
4180
4181   /* Aggregates without overlapping fields can have subvars.  */
4182   if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4183     return true;
4184
4185   return false;
4186 }
4187
4188 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4189    the fields of TYPE onto fieldstack, recording their offsets along
4190    the way.
4191
4192    OFFSET is used to keep track of the offset in this entire
4193    structure, rather than just the immediately containing structure.
4194    Returns the number of fields pushed.  */
4195
4196 static int
4197 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4198                              HOST_WIDE_INT offset)
4199 {
4200   tree field;
4201   int count = 0;
4202
4203   if (TREE_CODE (type) != RECORD_TYPE)
4204     return 0;
4205
4206   /* If the vector of fields is growing too big, bail out early.
4207      Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4208      sure this fails.  */
4209   if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4210     return 0;
4211
4212   for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4213     if (TREE_CODE (field) == FIELD_DECL)
4214       {
4215         bool push = false;
4216         int pushed = 0;
4217         HOST_WIDE_INT foff = bitpos_of_field (field);
4218
4219         if (!var_can_have_subvars (field)
4220             || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4221             || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4222           push = true;
4223         else if (!(pushed = push_fields_onto_fieldstack
4224                    (TREE_TYPE (field), fieldstack, offset + foff))
4225                  && (DECL_SIZE (field)
4226                      && !integer_zerop (DECL_SIZE (field))))
4227           /* Empty structures may have actual size, like in C++.  So
4228              see if we didn't push any subfields and the size is
4229              nonzero, push the field onto the stack.  */
4230           push = true;
4231
4232         if (push)
4233           {
4234             fieldoff_s *pair = NULL;
4235             bool has_unknown_size = false;
4236
4237             if (!VEC_empty (fieldoff_s, *fieldstack))
4238               pair = VEC_last (fieldoff_s, *fieldstack);
4239
4240             if (!DECL_SIZE (field)
4241                 || !host_integerp (DECL_SIZE (field), 1))
4242               has_unknown_size = true;
4243
4244             /* If adjacent fields do not contain pointers merge them.  */
4245             if (pair
4246                 && !pair->may_have_pointers
4247                 && !could_have_pointers (field)
4248                 && !pair->has_unknown_size
4249                 && !has_unknown_size
4250                 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4251               {
4252                 pair = VEC_last (fieldoff_s, *fieldstack);
4253                 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4254               }
4255             else
4256               {
4257                 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4258                 pair->offset = offset + foff;
4259                 pair->has_unknown_size = has_unknown_size;
4260                 if (!has_unknown_size)
4261                   pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4262                 else
4263                   pair->size = -1;
4264                 pair->may_have_pointers = could_have_pointers (field);
4265                 pair->only_restrict_pointers
4266                   = (!has_unknown_size
4267                      && POINTER_TYPE_P (TREE_TYPE (field))
4268                      && TYPE_RESTRICT (TREE_TYPE (field)));
4269                 count++;
4270               }
4271           }
4272         else
4273           count += pushed;
4274       }
4275
4276   return count;
4277 }
4278
4279 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4280    if it is a varargs function.  */
4281
4282 static unsigned int
4283 count_num_arguments (tree decl, bool *is_varargs)
4284 {
4285   unsigned int i = 0;
4286   tree t;
4287
4288   for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
4289        t;
4290        t = TREE_CHAIN (t))
4291     {
4292       if (TREE_VALUE (t) == void_type_node)
4293         break;
4294       i++;
4295     }
4296
4297   if (!t)
4298     *is_varargs = true;
4299   return i;
4300 }
4301
4302 /* Creation function node for DECL, using NAME, and return the index
4303    of the variable we've created for the function.  */
4304
4305 static unsigned int
4306 create_function_info_for (tree decl, const char *name)
4307 {
4308   varinfo_t vi;
4309   tree arg;
4310   unsigned int i;
4311   bool is_varargs = false;
4312
4313   /* Create the variable info.  */
4314
4315   vi = new_var_info (decl, name);
4316   vi->offset = 0;
4317   vi->size = 1;
4318   vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4319   insert_vi_for_tree (vi->decl, vi);
4320
4321   stats.total_vars++;
4322
4323   /* If it's varargs, we don't know how many arguments it has, so we
4324      can't do much.  */
4325   if (is_varargs)
4326     {
4327       vi->fullsize = ~0;
4328       vi->size = ~0;
4329       vi->is_unknown_size_var = true;
4330       return vi->id;
4331     }
4332
4333   arg = DECL_ARGUMENTS (decl);
4334
4335   /* Set up variables for each argument.  */
4336   for (i = 1; i < vi->fullsize; i++)
4337     {
4338       varinfo_t argvi;
4339       const char *newname;
4340       char *tempname;
4341       tree argdecl = decl;
4342
4343       if (arg)
4344         argdecl = arg;
4345
4346       asprintf (&tempname, "%s.arg%d", name, i-1);
4347       newname = ggc_strdup (tempname);
4348       free (tempname);
4349
4350       argvi = new_var_info (argdecl, newname);
4351       argvi->offset = i;
4352       argvi->size = 1;
4353       argvi->is_full_var = true;
4354       argvi->fullsize = vi->fullsize;
4355       insert_into_field_list_sorted (vi, argvi);
4356       stats.total_vars ++;
4357       if (arg)
4358         {
4359           insert_vi_for_tree (arg, argvi);
4360           arg = TREE_CHAIN (arg);
4361         }
4362     }
4363
4364   /* Create a variable for the return var.  */
4365   if (DECL_RESULT (decl) != NULL
4366       || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4367     {
4368       varinfo_t resultvi;
4369       const char *newname;
4370       char *tempname;
4371       tree resultdecl = decl;
4372
4373       vi->fullsize ++;
4374
4375       if (DECL_RESULT (decl))
4376         resultdecl = DECL_RESULT (decl);
4377
4378       asprintf (&tempname, "%s.result", name);
4379       newname = ggc_strdup (tempname);
4380       free (tempname);
4381
4382       resultvi = new_var_info (resultdecl, newname);
4383       resultvi->offset = i;
4384       resultvi->size = 1;
4385       resultvi->fullsize = vi->fullsize;
4386       resultvi->is_full_var = true;
4387       insert_into_field_list_sorted (vi, resultvi);
4388       stats.total_vars ++;
4389       if (DECL_RESULT (decl))
4390         insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4391     }
4392
4393   return vi->id;
4394 }
4395
4396
4397 /* Return true if FIELDSTACK contains fields that overlap.
4398    FIELDSTACK is assumed to be sorted by offset.  */
4399
4400 static bool
4401 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4402 {
4403   fieldoff_s *fo = NULL;
4404   unsigned int i;
4405   HOST_WIDE_INT lastoffset = -1;
4406
4407   for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4408     {
4409       if (fo->offset == lastoffset)
4410         return true;
4411       lastoffset = fo->offset;
4412     }
4413   return false;
4414 }
4415
4416 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4417    This will also create any varinfo structures necessary for fields
4418    of DECL.  */
4419
4420 static unsigned int
4421 create_variable_info_for (tree decl, const char *name)
4422 {
4423   varinfo_t vi;
4424   tree decl_type = TREE_TYPE (decl);
4425   tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
4426   VEC (fieldoff_s,heap) *fieldstack = NULL;
4427
4428   if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4429     return create_function_info_for (decl, name);
4430
4431   if (var_can_have_subvars (decl) && use_field_sensitive)
4432     push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
4433
4434   /* If the variable doesn't have subvars, we may end up needing to
4435      sort the field list and create fake variables for all the
4436      fields.  */
4437   vi = new_var_info (decl, name);
4438   vi->offset = 0;
4439   vi->may_have_pointers = could_have_pointers (decl);
4440   if (!declsize
4441       || !host_integerp (declsize, 1))
4442     {
4443       vi->is_unknown_size_var = true;
4444       vi->fullsize = ~0;
4445       vi->size = ~0;
4446     }
4447   else
4448     {
4449       vi->fullsize = TREE_INT_CST_LOW (declsize);
4450       vi->size = vi->fullsize;
4451     }
4452
4453   insert_vi_for_tree (vi->decl, vi);
4454   if (vi->is_global_var
4455       && (!flag_whole_program || !in_ipa_mode)
4456       && vi->may_have_pointers)
4457     {
4458       if (POINTER_TYPE_P (TREE_TYPE (decl))
4459           && TYPE_RESTRICT (TREE_TYPE (decl)))
4460         make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
4461       make_copy_constraint (vi, nonlocal_id);
4462     }
4463
4464   stats.total_vars++;
4465   if (use_field_sensitive
4466       && !vi->is_unknown_size_var
4467       && var_can_have_subvars (decl)
4468       && VEC_length (fieldoff_s, fieldstack) > 1
4469       && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4470     {
4471       fieldoff_s *fo = NULL;
4472       bool notokay = false;
4473       unsigned int i;
4474
4475       for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4476         {
4477           if (fo->has_unknown_size
4478               || fo->offset < 0)
4479             {
4480               notokay = true;
4481               break;
4482             }
4483         }
4484
4485       /* We can't sort them if we have a field with a variable sized type,
4486          which will make notokay = true.  In that case, we are going to return
4487          without creating varinfos for the fields anyway, so sorting them is a
4488          waste to boot.  */
4489       if (!notokay)
4490         {
4491           sort_fieldstack (fieldstack);
4492           /* Due to some C++ FE issues, like PR 22488, we might end up
4493              what appear to be overlapping fields even though they,
4494              in reality, do not overlap.  Until the C++ FE is fixed,
4495              we will simply disable field-sensitivity for these cases.  */
4496           notokay = check_for_overlaps (fieldstack);
4497         }
4498
4499
4500       if (VEC_length (fieldoff_s, fieldstack) != 0)
4501         fo = VEC_index (fieldoff_s, fieldstack, 0);
4502
4503       if (fo == NULL || notokay)
4504         {
4505           vi->is_unknown_size_var = 1;
4506           vi->fullsize = ~0;
4507           vi->size = ~0;
4508           vi->is_full_var = true;
4509           VEC_free (fieldoff_s, heap, fieldstack);
4510           return vi->id;
4511         }
4512
4513       vi->size = fo->size;
4514       vi->offset = fo->offset;
4515       vi->may_have_pointers = fo->may_have_pointers;
4516       if (vi->is_global_var
4517           && (!flag_whole_program || !in_ipa_mode)
4518           && vi->may_have_pointers)
4519         {
4520           if (fo->only_restrict_pointers)
4521             make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
4522         }
4523       for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4524            i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4525            i--)
4526         {
4527           varinfo_t newvi;
4528           const char *newname = "NULL";
4529           char *tempname;
4530
4531           if (dump_file)
4532             {
4533               asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4534                         "+" HOST_WIDE_INT_PRINT_DEC,
4535                         vi->name, fo->offset, fo->size);
4536               newname = ggc_strdup (tempname);
4537               free (tempname);
4538             }
4539           newvi = new_var_info (decl, newname);
4540           newvi->offset = fo->offset;
4541           newvi->size = fo->size;
4542           newvi->fullsize = vi->fullsize;
4543           newvi->may_have_pointers = fo->may_have_pointers;
4544           insert_into_field_list (vi, newvi);
4545           if ((newvi->is_global_var || TREE_CODE (decl) == PARM_DECL)
4546               && newvi->may_have_pointers)
4547             {
4548                if (fo->only_restrict_pointers)
4549                  make_constraint_from_restrict (newvi, "GLOBAL_RESTRICT");
4550                if (newvi->is_global_var && !in_ipa_mode)
4551                  make_copy_constraint (newvi, nonlocal_id);
4552             }
4553
4554           stats.total_vars++;
4555         }
4556     }
4557   else
4558     vi->is_full_var = true;
4559
4560   VEC_free (fieldoff_s, heap, fieldstack);
4561
4562   return vi->id;
4563 }
4564
4565 /* Print out the points-to solution for VAR to FILE.  */
4566
4567 static void
4568 dump_solution_for_var (FILE *file, unsigned int var)
4569 {
4570   varinfo_t vi = get_varinfo (var);
4571   unsigned int i;
4572   bitmap_iterator bi;
4573
4574   if (find (var) != var)
4575     {
4576       varinfo_t vipt = get_varinfo (find (var));
4577       fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4578     }
4579   else
4580     {
4581       fprintf (file, "%s = { ", vi->name);
4582       EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4583         {
4584           fprintf (file, "%s ", get_varinfo (i)->name);
4585         }
4586       fprintf (file, "}\n");
4587     }
4588 }
4589
4590 /* Print the points-to solution for VAR to stdout.  */
4591
4592 void
4593 debug_solution_for_var (unsigned int var)
4594 {
4595   dump_solution_for_var (stdout, var);
4596 }
4597
4598 /* Create varinfo structures for all of the variables in the
4599    function for intraprocedural mode.  */
4600
4601 static void
4602 intra_create_variable_infos (void)
4603 {
4604   tree t;
4605
4606   /* For each incoming pointer argument arg, create the constraint ARG
4607      = NONLOCAL or a dummy variable if flag_argument_noalias is set.  */
4608   for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4609     {
4610       varinfo_t p;
4611
4612       if (!could_have_pointers (t))
4613         continue;
4614
4615       /* For restrict qualified pointers to objects passed by
4616          reference build a real representative for the pointed-to object.  */
4617       if (DECL_BY_REFERENCE (t)
4618           && POINTER_TYPE_P (TREE_TYPE (t))
4619           && TYPE_RESTRICT (TREE_TYPE (t)))
4620         {
4621           struct constraint_expr lhsc, rhsc;
4622           varinfo_t vi;
4623           tree heapvar = heapvar_lookup (t, 0);
4624           if (heapvar == NULL_TREE)
4625             {
4626               var_ann_t ann;
4627               heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4628                                             "PARM_NOALIAS");
4629               DECL_EXTERNAL (heapvar) = 1;
4630               heapvar_insert (t, 0, heapvar);
4631               ann = get_var_ann (heapvar);
4632               ann->is_heapvar = 1;
4633             }
4634           if (gimple_referenced_vars (cfun))
4635             add_referenced_var (heapvar);
4636           lhsc.var = get_vi_for_tree (t)->id;
4637           lhsc.type = SCALAR;
4638           lhsc.offset = 0;
4639           rhsc.var = (vi = get_vi_for_tree (heapvar))->id;
4640           rhsc.type = ADDRESSOF;
4641           rhsc.offset = 0;
4642           process_constraint (new_constraint (lhsc, rhsc));
4643           vi->is_restrict_var = 1;
4644           continue;
4645         }
4646
4647       for (p = get_vi_for_tree (t); p; p = p->next)
4648         if (p->may_have_pointers)
4649           make_constraint_from (p, nonlocal_id);
4650       if (POINTER_TYPE_P (TREE_TYPE (t))
4651           && TYPE_RESTRICT (TREE_TYPE (t)))
4652         make_constraint_from_restrict (get_vi_for_tree (t), "PARM_RESTRICT");
4653     }
4654
4655   /* Add a constraint for a result decl that is passed by reference.  */
4656   if (DECL_RESULT (cfun->decl)
4657       && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
4658     {
4659       varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
4660
4661       for (p = result_vi; p; p = p->next)
4662         make_constraint_from (p, nonlocal_id);
4663     }
4664
4665   /* Add a constraint for the incoming static chain parameter.  */
4666   if (cfun->static_chain_decl != NULL_TREE)
4667     {
4668       varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
4669
4670       for (p = chain_vi; p; p = p->next)
4671         make_constraint_from (p, nonlocal_id);
4672     }
4673 }
4674
4675 /* Structure used to put solution bitmaps in a hashtable so they can
4676    be shared among variables with the same points-to set.  */
4677
4678 typedef struct shared_bitmap_info
4679 {
4680   bitmap pt_vars;
4681   hashval_t hashcode;
4682 } *shared_bitmap_info_t;
4683 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4684
4685 static htab_t shared_bitmap_table;
4686
4687 /* Hash function for a shared_bitmap_info_t */
4688
4689 static hashval_t
4690 shared_bitmap_hash (const void *p)
4691 {
4692   const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4693   return bi->hashcode;
4694 }
4695
4696 /* Equality function for two shared_bitmap_info_t's. */
4697
4698 static int
4699 shared_bitmap_eq (const void *p1, const void *p2)
4700 {
4701   const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4702   const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4703   return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4704 }
4705
4706 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4707    existing instance if there is one, NULL otherwise.  */
4708
4709 static bitmap
4710 shared_bitmap_lookup (bitmap pt_vars)
4711 {
4712   void **slot;
4713   struct shared_bitmap_info sbi;
4714
4715   sbi.pt_vars = pt_vars;
4716   sbi.hashcode = bitmap_hash (pt_vars);
4717
4718   slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4719                                    sbi.hashcode, NO_INSERT);
4720   if (!slot)
4721     return NULL;
4722   else
4723     return ((shared_bitmap_info_t) *slot)->pt_vars;
4724 }
4725
4726
4727 /* Add a bitmap to the shared bitmap hashtable.  */
4728
4729 static void
4730 shared_bitmap_add (bitmap pt_vars)
4731 {
4732   void **slot;
4733   shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4734
4735   sbi->pt_vars = pt_vars;
4736   sbi->hashcode = bitmap_hash (pt_vars);
4737
4738   slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4739                                    sbi->hashcode, INSERT);
4740   gcc_assert (!*slot);
4741   *slot = (void *) sbi;
4742 }
4743
4744
4745 /* Set bits in INTO corresponding to the variable uids in solution set FROM.  */
4746
4747 static void 
4748 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt)
4749 {
4750   unsigned int i;
4751   bitmap_iterator bi;
4752
4753   EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4754     {
4755       varinfo_t vi = get_varinfo (i);
4756
4757       /* The only artificial variables that are allowed in a may-alias
4758          set are heap variables.  */
4759       if (vi->is_artificial_var && !vi->is_heap_var)
4760         continue;
4761
4762       if (TREE_CODE (vi->decl) == VAR_DECL
4763           || TREE_CODE (vi->decl) == PARM_DECL
4764           || TREE_CODE (vi->decl) == RESULT_DECL)
4765         {
4766           /* Add the decl to the points-to set.  Note that the points-to
4767              set contains global variables.  */
4768           bitmap_set_bit (into, DECL_UID (vi->decl));
4769           if (vi->is_global_var)
4770             pt->vars_contains_global = true;
4771         }
4772     }
4773 }
4774
4775
4776 static bool have_alias_info = false;
4777
4778 /* Compute the points-to solution *PT for the variable VI.  */
4779
4780 static void
4781 find_what_var_points_to (varinfo_t vi, struct pt_solution *pt)
4782 {
4783   unsigned int i;
4784   bitmap_iterator bi;
4785   bitmap finished_solution;
4786   bitmap result;
4787
4788   memset (pt, 0, sizeof (struct pt_solution));
4789
4790   /* This variable may have been collapsed, let's get the real
4791      variable.  */
4792   vi = get_varinfo (find (vi->id));
4793
4794   /* Translate artificial variables into SSA_NAME_PTR_INFO
4795      attributes.  */
4796   EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4797     {
4798       varinfo_t vi = get_varinfo (i);
4799
4800       if (vi->is_artificial_var)
4801         {
4802           if (vi->id == nothing_id)
4803             pt->null = 1;
4804           else if (vi->id == escaped_id)
4805             pt->escaped = 1;
4806           else if (vi->id == callused_id)
4807             gcc_unreachable ();
4808           else if (vi->id == nonlocal_id)
4809             pt->nonlocal = 1;
4810           else if (vi->is_heap_var)
4811             /* We represent heapvars in the points-to set properly.  */
4812             ;
4813           else if (vi->id == readonly_id)
4814             /* Nobody cares.  */
4815             ;
4816           else if (vi->id == anything_id
4817                    || vi->id == integer_id)
4818             pt->anything = 1;
4819         }
4820       if (vi->is_restrict_var)
4821         pt->vars_contains_restrict = true;
4822     }
4823
4824   /* Instead of doing extra work, simply do not create
4825      elaborate points-to information for pt_anything pointers.  */
4826   if (pt->anything
4827       && (vi->is_artificial_var
4828           || !pt->vars_contains_restrict))
4829     return;
4830
4831   /* Share the final set of variables when possible.  */
4832   finished_solution = BITMAP_GGC_ALLOC ();
4833   stats.points_to_sets_created++;
4834
4835   set_uids_in_ptset (finished_solution, vi->solution, pt);
4836   result = shared_bitmap_lookup (finished_solution);
4837   if (!result)
4838     {
4839       shared_bitmap_add (finished_solution);
4840       pt->vars = finished_solution;
4841     }
4842   else
4843     {
4844       pt->vars = result;
4845       bitmap_clear (finished_solution);
4846     }
4847 }
4848
4849 /* Given a pointer variable P, fill in its points-to set.  */
4850
4851 static void
4852 find_what_p_points_to (tree p)
4853 {
4854   struct ptr_info_def *pi;
4855   tree lookup_p = p;
4856   varinfo_t vi;
4857
4858   /* For parameters, get at the points-to set for the actual parm
4859      decl.  */
4860   if (TREE_CODE (p) == SSA_NAME
4861       && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4862       && SSA_NAME_IS_DEFAULT_DEF (p))
4863     lookup_p = SSA_NAME_VAR (p);
4864
4865   vi = lookup_vi_for_tree (lookup_p);
4866   if (!vi)
4867     return;
4868
4869   pi = get_ptr_info (p);
4870   find_what_var_points_to (vi, &pi->pt);
4871 }
4872
4873
4874 /* Query statistics for points-to solutions.  */
4875
4876 static struct {
4877   unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
4878   unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
4879   unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
4880   unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
4881 } pta_stats;
4882
4883 void
4884 dump_pta_stats (FILE *s)
4885 {
4886   fprintf (s, "\nPTA query stats:\n");
4887   fprintf (s, "  pt_solution_includes: "
4888            HOST_WIDE_INT_PRINT_DEC" disambiguations, "
4889            HOST_WIDE_INT_PRINT_DEC" queries\n",
4890            pta_stats.pt_solution_includes_no_alias,
4891            pta_stats.pt_solution_includes_no_alias
4892            + pta_stats.pt_solution_includes_may_alias);
4893   fprintf (s, "  pt_solutions_intersect: "
4894            HOST_WIDE_INT_PRINT_DEC" disambiguations, "
4895            HOST_WIDE_INT_PRINT_DEC" queries\n",
4896            pta_stats.pt_solutions_intersect_no_alias,
4897            pta_stats.pt_solutions_intersect_no_alias
4898            + pta_stats.pt_solutions_intersect_may_alias);
4899 }
4900
4901
4902 /* Reset the points-to solution *PT to a conservative default
4903    (point to anything).  */
4904
4905 void
4906 pt_solution_reset (struct pt_solution *pt)
4907 {
4908   memset (pt, 0, sizeof (struct pt_solution));
4909   pt->anything = true;
4910 }
4911
4912 /* Set the points-to solution *PT to point only to the variables
4913    in VARS.  */
4914
4915 void
4916 pt_solution_set (struct pt_solution *pt, bitmap vars)
4917 {
4918   bitmap_iterator bi;
4919   unsigned i;
4920
4921   memset (pt, 0, sizeof (struct pt_solution));
4922   pt->vars = vars;
4923   EXECUTE_IF_SET_IN_BITMAP (vars, 0, i, bi)
4924     {
4925       tree var = referenced_var_lookup (i);
4926       if (is_global_var (var))
4927         {
4928           pt->vars_contains_global = true;
4929           break;
4930         }
4931     }
4932 }
4933
4934 /* Return true if the points-to solution *PT is empty.  */
4935
4936 static bool
4937 pt_solution_empty_p (struct pt_solution *pt)
4938 {
4939   if (pt->anything
4940       || pt->nonlocal)
4941     return false;
4942
4943   if (pt->vars
4944       && !bitmap_empty_p (pt->vars))
4945     return false;
4946
4947   /* If the solution includes ESCAPED, check if that is empty.  */
4948   if (pt->escaped
4949       && !pt_solution_empty_p (&cfun->gimple_df->escaped))
4950     return false;
4951
4952   return true;
4953 }
4954
4955 /* Return true if the points-to solution *PT includes global memory.  */
4956
4957 bool
4958 pt_solution_includes_global (struct pt_solution *pt)
4959 {
4960   if (pt->anything
4961       || pt->nonlocal
4962       || pt->vars_contains_global)
4963     return true;
4964
4965   if (pt->escaped)
4966     return pt_solution_includes_global (&cfun->gimple_df->escaped);
4967
4968   return false;
4969 }
4970
4971 /* Return true if the points-to solution *PT includes the variable
4972    declaration DECL.  */
4973
4974 static bool
4975 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
4976 {
4977   if (pt->anything)
4978     return true;
4979
4980   if (pt->nonlocal
4981       && is_global_var (decl))
4982     return true;
4983
4984   if (pt->vars
4985       && bitmap_bit_p (pt->vars, DECL_UID (decl)))
4986     return true;
4987
4988   /* If the solution includes ESCAPED, check it.  */
4989   if (pt->escaped
4990       && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
4991     return true;
4992
4993   return false;
4994 }
4995
4996 bool
4997 pt_solution_includes (struct pt_solution *pt, const_tree decl)
4998 {
4999   bool res = pt_solution_includes_1 (pt, decl);
5000   if (res)
5001     ++pta_stats.pt_solution_includes_may_alias;
5002   else
5003     ++pta_stats.pt_solution_includes_no_alias;
5004   return res;
5005 }
5006
5007 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
5008    intersection.  */
5009
5010 static bool
5011 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
5012 {
5013   if (pt1->anything || pt2->anything)
5014     return true;
5015
5016   /* If either points to unknown global memory and the other points to
5017      any global memory they alias.  */
5018   if ((pt1->nonlocal
5019        && (pt2->nonlocal
5020            || pt2->vars_contains_global))
5021       || (pt2->nonlocal
5022           && pt1->vars_contains_global))
5023     return true;
5024
5025   /* Check the escaped solution if required.  */
5026   if ((pt1->escaped || pt2->escaped)
5027       && !pt_solution_empty_p (&cfun->gimple_df->escaped))
5028     {
5029       /* If both point to escaped memory and that solution
5030          is not empty they alias.  */
5031       if (pt1->escaped && pt2->escaped)
5032         return true;
5033
5034       /* If either points to escaped memory see if the escaped solution
5035          intersects with the other.  */
5036       if ((pt1->escaped
5037            && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt2))
5038           || (pt2->escaped
5039               && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt1)))
5040         return true;
5041     }
5042
5043   /* Now both pointers alias if their points-to solution intersects.  */
5044   return (pt1->vars
5045           && pt2->vars
5046           && bitmap_intersect_p (pt1->vars, pt2->vars));
5047 }
5048
5049 bool
5050 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
5051 {
5052   bool res = pt_solutions_intersect_1 (pt1, pt2);
5053   if (res)
5054     ++pta_stats.pt_solutions_intersect_may_alias;
5055   else
5056     ++pta_stats.pt_solutions_intersect_no_alias;
5057   return res;
5058 }
5059
5060 /* Return true if both points-to solutions PT1 and PT2 for two restrict
5061    qualified pointers are possibly based on the same pointer.  */
5062
5063 bool
5064 pt_solutions_same_restrict_base (struct pt_solution *pt1,
5065                                  struct pt_solution *pt2)
5066 {
5067   /* If we deal with points-to solutions of two restrict qualified
5068      pointers solely rely on the pointed-to variable bitmap intersection.
5069      For two pointers that are based on each other the bitmaps will
5070      intersect.  */
5071   if (pt1->vars_contains_restrict
5072       && pt2->vars_contains_restrict)
5073     {
5074       gcc_assert (pt1->vars && pt2->vars);
5075       return bitmap_intersect_p (pt1->vars, pt2->vars);
5076     }
5077
5078   return true;
5079 }
5080
5081
5082 /* Dump points-to information to OUTFILE.  */
5083
5084 static void
5085 dump_sa_points_to_info (FILE *outfile)
5086 {
5087   unsigned int i;
5088
5089   fprintf (outfile, "\nPoints-to sets\n\n");
5090
5091   if (dump_flags & TDF_STATS)
5092     {
5093       fprintf (outfile, "Stats:\n");
5094       fprintf (outfile, "Total vars:               %d\n", stats.total_vars);
5095       fprintf (outfile, "Non-pointer vars:          %d\n",
5096                stats.nonpointer_vars);
5097       fprintf (outfile, "Statically unified vars:  %d\n",
5098                stats.unified_vars_static);
5099       fprintf (outfile, "Dynamically unified vars: %d\n",
5100                stats.unified_vars_dynamic);
5101       fprintf (outfile, "Iterations:               %d\n", stats.iterations);
5102       fprintf (outfile, "Number of edges:          %d\n", stats.num_edges);
5103       fprintf (outfile, "Number of implicit edges: %d\n",
5104                stats.num_implicit_edges);
5105     }
5106
5107   for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5108     dump_solution_for_var (outfile, i);
5109 }
5110
5111
5112 /* Debug points-to information to stderr.  */
5113
5114 void
5115 debug_sa_points_to_info (void)
5116 {
5117   dump_sa_points_to_info (stderr);
5118 }
5119
5120
5121 /* Initialize the always-existing constraint variables for NULL
5122    ANYTHING, READONLY, and INTEGER */
5123
5124 static void
5125 init_base_vars (void)
5126 {
5127   struct constraint_expr lhs, rhs;
5128   varinfo_t var_anything;
5129   varinfo_t var_nothing;
5130   varinfo_t var_readonly;
5131   varinfo_t var_escaped;
5132   varinfo_t var_nonlocal;
5133   varinfo_t var_callused;
5134   varinfo_t var_storedanything;
5135   varinfo_t var_integer;
5136
5137   /* Create the NULL variable, used to represent that a variable points
5138      to NULL.  */
5139   var_nothing = new_var_info (NULL_TREE, "NULL");
5140   gcc_assert (var_nothing->id == nothing_id);
5141   var_nothing->is_artificial_var = 1;
5142   var_nothing->offset = 0;
5143   var_nothing->size = ~0;
5144   var_nothing->fullsize = ~0;
5145   var_nothing->is_special_var = 1;
5146
5147   /* Create the ANYTHING variable, used to represent that a variable
5148      points to some unknown piece of memory.  */
5149   var_anything = new_var_info (NULL_TREE, "ANYTHING");
5150   gcc_assert (var_anything->id == anything_id);
5151   var_anything->is_artificial_var = 1;
5152   var_anything->size = ~0;
5153   var_anything->offset = 0;
5154   var_anything->next = NULL;
5155   var_anything->fullsize = ~0;
5156   var_anything->is_special_var = 1;
5157
5158   /* Anything points to anything.  This makes deref constraints just
5159      work in the presence of linked list and other p = *p type loops,
5160      by saying that *ANYTHING = ANYTHING. */
5161   lhs.type = SCALAR;
5162   lhs.var = anything_id;
5163   lhs.offset = 0;
5164   rhs.type = ADDRESSOF;
5165   rhs.var = anything_id;
5166   rhs.offset = 0;
5167
5168   /* This specifically does not use process_constraint because
5169      process_constraint ignores all anything = anything constraints, since all
5170      but this one are redundant.  */
5171   VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5172
5173   /* Create the READONLY variable, used to represent that a variable
5174      points to readonly memory.  */
5175   var_readonly = new_var_info (NULL_TREE, "READONLY");
5176   gcc_assert (var_readonly->id == readonly_id);
5177   var_readonly->is_artificial_var = 1;
5178   var_readonly->offset = 0;
5179   var_readonly->size = ~0;
5180   var_readonly->fullsize = ~0;
5181   var_readonly->next = NULL;
5182   var_readonly->is_special_var = 1;
5183
5184   /* readonly memory points to anything, in order to make deref
5185      easier.  In reality, it points to anything the particular
5186      readonly variable can point to, but we don't track this
5187      separately. */
5188   lhs.type = SCALAR;
5189   lhs.var = readonly_id;
5190   lhs.offset = 0;
5191   rhs.type = ADDRESSOF;
5192   rhs.var = readonly_id;  /* FIXME */
5193   rhs.offset = 0;
5194   process_constraint (new_constraint (lhs, rhs));
5195
5196   /* Create the ESCAPED variable, used to represent the set of escaped
5197      memory.  */
5198   var_escaped = new_var_info (NULL_TREE, "ESCAPED");
5199   gcc_assert (var_escaped->id == escaped_id);
5200   var_escaped->is_artificial_var = 1;
5201   var_escaped->offset = 0;
5202   var_escaped->size = ~0;
5203   var_escaped->fullsize = ~0;
5204   var_escaped->is_special_var = 0;
5205
5206   /* Create the NONLOCAL variable, used to represent the set of nonlocal
5207      memory.  */
5208   var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL");
5209   gcc_assert (var_nonlocal->id == nonlocal_id);
5210   var_nonlocal->is_artificial_var = 1;
5211   var_nonlocal->offset = 0;
5212   var_nonlocal->size = ~0;
5213   var_nonlocal->fullsize = ~0;
5214   var_nonlocal->is_special_var = 1;
5215
5216   /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc.  */
5217   lhs.type = SCALAR;
5218   lhs.var = escaped_id;
5219   lhs.offset = 0;
5220   rhs.type = DEREF;
5221   rhs.var = escaped_id;
5222   rhs.offset = 0;
5223   process_constraint (new_constraint (lhs, rhs));
5224
5225   /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
5226      whole variable escapes.  */
5227   lhs.type = SCALAR;
5228   lhs.var = escaped_id;
5229   lhs.offset = 0;
5230   rhs.type = SCALAR;
5231   rhs.var = escaped_id;
5232   rhs.offset = UNKNOWN_OFFSET;
5233   process_constraint (new_constraint (lhs, rhs));
5234
5235   /* *ESCAPED = NONLOCAL.  This is true because we have to assume
5236      everything pointed to by escaped points to what global memory can
5237      point to.  */
5238   lhs.type = DEREF;
5239   lhs.var = escaped_id;
5240   lhs.offset = 0;
5241   rhs.type = SCALAR;
5242   rhs.var = nonlocal_id;
5243   rhs.offset = 0;
5244   process_constraint (new_constraint (lhs, rhs));
5245
5246   /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED.  This is true because
5247      global memory may point to global memory and escaped memory.  */
5248   lhs.type = SCALAR;
5249   lhs.var = nonlocal_id;
5250   lhs.offset = 0;
5251   rhs.type = ADDRESSOF;
5252   rhs.var = nonlocal_id;
5253   rhs.offset = 0;
5254   process_constraint (new_constraint (lhs, rhs));
5255   rhs.type = ADDRESSOF;
5256   rhs.var = escaped_id;
5257   rhs.offset = 0;
5258   process_constraint (new_constraint (lhs, rhs));
5259
5260   /* Create the CALLUSED variable, used to represent the set of call-used
5261      memory.  */
5262   var_callused = new_var_info (NULL_TREE, "CALLUSED");
5263   gcc_assert (var_callused->id == callused_id);
5264   var_callused->is_artificial_var = 1;
5265   var_callused->offset = 0;
5266   var_callused->size = ~0;
5267   var_callused->fullsize = ~0;
5268   var_callused->is_special_var = 0;
5269
5270   /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc.  */
5271   lhs.type = SCALAR;
5272   lhs.var = callused_id;
5273   lhs.offset = 0;
5274   rhs.type = DEREF;
5275   rhs.var = callused_id;
5276   rhs.offset = 0;
5277   process_constraint (new_constraint (lhs, rhs));
5278
5279   /* CALLUSED = CALLUSED + UNKNOWN, because if a sub-field is call-used the
5280      whole variable is call-used.  */
5281   lhs.type = SCALAR;
5282   lhs.var = callused_id;
5283   lhs.offset = 0;
5284   rhs.type = SCALAR;
5285   rhs.var = callused_id;
5286   rhs.offset = UNKNOWN_OFFSET;
5287   process_constraint (new_constraint (lhs, rhs));
5288
5289   /* Create the STOREDANYTHING variable, used to represent the set of
5290      variables stored to *ANYTHING.  */
5291   var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING");
5292   gcc_assert (var_storedanything->id == storedanything_id);
5293   var_storedanything->is_artificial_var = 1;
5294   var_storedanything->offset = 0;
5295   var_storedanything->size = ~0;
5296   var_storedanything->fullsize = ~0;
5297   var_storedanything->is_special_var = 0;
5298
5299   /* Create the INTEGER variable, used to represent that a variable points
5300      to what an INTEGER "points to".  */
5301   var_integer = new_var_info (NULL_TREE, "INTEGER");
5302   gcc_assert (var_integer->id == integer_id);
5303   var_integer->is_artificial_var = 1;
5304   var_integer->size = ~0;
5305   var_integer->fullsize = ~0;
5306   var_integer->offset = 0;
5307   var_integer->next = NULL;
5308   var_integer->is_special_var = 1;
5309
5310   /* INTEGER = ANYTHING, because we don't know where a dereference of
5311      a random integer will point to.  */
5312   lhs.type = SCALAR;
5313   lhs.var = integer_id;
5314   lhs.offset = 0;
5315   rhs.type = ADDRESSOF;
5316   rhs.var = anything_id;
5317   rhs.offset = 0;
5318   process_constraint (new_constraint (lhs, rhs));
5319 }
5320
5321 /* Initialize things necessary to perform PTA */
5322
5323 static void
5324 init_alias_vars (void)
5325 {
5326   use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5327
5328   bitmap_obstack_initialize (&pta_obstack);
5329   bitmap_obstack_initialize (&oldpta_obstack);
5330   bitmap_obstack_initialize (&predbitmap_obstack);
5331
5332   constraint_pool = create_alloc_pool ("Constraint pool",
5333                                        sizeof (struct constraint), 30);
5334   variable_info_pool = create_alloc_pool ("Variable info pool",
5335                                           sizeof (struct variable_info), 30);
5336   constraints = VEC_alloc (constraint_t, heap, 8);
5337   varmap = VEC_alloc (varinfo_t, heap, 8);
5338   vi_for_tree = pointer_map_create ();
5339
5340   memset (&stats, 0, sizeof (stats));
5341   shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5342                                      shared_bitmap_eq, free);
5343   init_base_vars ();
5344 }
5345
5346 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5347    predecessor edges.  */
5348
5349 static void
5350 remove_preds_and_fake_succs (constraint_graph_t graph)
5351 {
5352   unsigned int i;
5353
5354   /* Clear the implicit ref and address nodes from the successor
5355      lists.  */
5356   for (i = 0; i < FIRST_REF_NODE; i++)
5357     {
5358       if (graph->succs[i])
5359         bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5360                             FIRST_REF_NODE * 2);
5361     }
5362
5363   /* Free the successor list for the non-ref nodes.  */
5364   for (i = FIRST_REF_NODE; i < graph->size; i++)
5365     {
5366       if (graph->succs[i])
5367         BITMAP_FREE (graph->succs[i]);
5368     }
5369
5370   /* Now reallocate the size of the successor list as, and blow away
5371      the predecessor bitmaps.  */
5372   graph->size = VEC_length (varinfo_t, varmap);
5373   graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5374
5375   free (graph->implicit_preds);
5376   graph->implicit_preds = NULL;
5377   free (graph->preds);
5378   graph->preds = NULL;
5379   bitmap_obstack_release (&predbitmap_obstack);
5380 }
5381
5382 /* Initialize the heapvar for statement mapping.  */
5383
5384 static void
5385 init_alias_heapvars (void)
5386 {
5387   if (!heapvar_for_stmt)
5388     heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, heapvar_map_eq,
5389                                         NULL);
5390 }
5391
5392 /* Delete the heapvar for statement mapping.  */
5393
5394 void
5395 delete_alias_heapvars (void)
5396 {
5397   if (heapvar_for_stmt)
5398     htab_delete (heapvar_for_stmt);
5399   heapvar_for_stmt = NULL;
5400 }
5401
5402 /* Create points-to sets for the current function.  See the comments
5403    at the start of the file for an algorithmic overview.  */
5404
5405 static void
5406 compute_points_to_sets (void)
5407 {
5408   struct scc_info *si;
5409   basic_block bb;
5410   unsigned i;
5411   varinfo_t vi;
5412
5413   timevar_push (TV_TREE_PTA);
5414
5415   init_alias_vars ();
5416   init_alias_heapvars ();
5417
5418   intra_create_variable_infos ();
5419
5420   /* Now walk all statements and derive aliases.  */
5421   FOR_EACH_BB (bb)
5422     {
5423       gimple_stmt_iterator gsi;
5424
5425       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5426         {
5427           gimple phi = gsi_stmt (gsi);
5428
5429           if (is_gimple_reg (gimple_phi_result (phi)))
5430             find_func_aliases (phi);
5431         }
5432
5433       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5434         {
5435           gimple stmt = gsi_stmt (gsi);
5436
5437           find_func_aliases (stmt);
5438         }
5439     }
5440
5441   if (dump_file)
5442     {
5443       fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5444       dump_constraints (dump_file);
5445     }
5446
5447   if (dump_file)
5448     fprintf (dump_file,
5449              "\nCollapsing static cycles and doing variable "
5450              "substitution\n");
5451
5452   init_graph (VEC_length (varinfo_t, varmap) * 2);
5453   
5454   if (dump_file)
5455     fprintf (dump_file, "Building predecessor graph\n");
5456   build_pred_graph ();
5457   
5458   if (dump_file)
5459     fprintf (dump_file, "Detecting pointer and location "
5460              "equivalences\n");
5461   si = perform_var_substitution (graph);
5462   
5463   if (dump_file)
5464     fprintf (dump_file, "Rewriting constraints and unifying "
5465              "variables\n");
5466   rewrite_constraints (graph, si);
5467
5468   build_succ_graph ();
5469   free_var_substitution_info (si);
5470
5471   if (dump_file && (dump_flags & TDF_GRAPH))
5472     dump_constraint_graph (dump_file);
5473
5474   move_complex_constraints (graph);
5475
5476   if (dump_file)
5477     fprintf (dump_file, "Uniting pointer but not location equivalent "
5478              "variables\n");
5479   unite_pointer_equivalences (graph);
5480
5481   if (dump_file)
5482     fprintf (dump_file, "Finding indirect cycles\n");
5483   find_indirect_cycles (graph);
5484
5485   /* Implicit nodes and predecessors are no longer necessary at this
5486      point. */
5487   remove_preds_and_fake_succs (graph);
5488
5489   if (dump_file)
5490     fprintf (dump_file, "Solving graph\n");
5491
5492   solve_graph (graph);
5493
5494   if (dump_file)
5495     dump_sa_points_to_info (dump_file);
5496
5497   /* Compute the points-to sets for ESCAPED and CALLUSED used for
5498      call-clobber analysis.  */
5499   find_what_var_points_to (get_varinfo (escaped_id),
5500                            &cfun->gimple_df->escaped);
5501   find_what_var_points_to (get_varinfo (callused_id),
5502                            &cfun->gimple_df->callused);
5503
5504   /* Make sure the ESCAPED solution (which is used as placeholder in
5505      other solutions) does not reference itself.  This simplifies
5506      points-to solution queries.  */
5507   cfun->gimple_df->escaped.escaped = 0;
5508
5509   /* Mark escaped HEAP variables as global.  */
5510   for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); ++i)
5511     if (vi->is_heap_var
5512         && !vi->is_restrict_var
5513         && !vi->is_global_var)
5514       DECL_EXTERNAL (vi->decl) = vi->is_global_var
5515         = pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);
5516
5517   /* Compute the points-to sets for pointer SSA_NAMEs.  */
5518   for (i = 0; i < num_ssa_names; ++i)
5519     {
5520       tree ptr = ssa_name (i);
5521       if (ptr
5522           && POINTER_TYPE_P (TREE_TYPE (ptr)))
5523         find_what_p_points_to (ptr);
5524     }
5525
5526   timevar_pop (TV_TREE_PTA);
5527
5528   have_alias_info = true;
5529 }
5530
5531
5532 /* Delete created points-to sets.  */
5533
5534 static void
5535 delete_points_to_sets (void)
5536 {
5537   unsigned int i;
5538
5539   htab_delete (shared_bitmap_table);
5540   if (dump_file && (dump_flags & TDF_STATS))
5541     fprintf (dump_file, "Points to sets created:%d\n",
5542              stats.points_to_sets_created);
5543
5544   pointer_map_destroy (vi_for_tree);
5545   bitmap_obstack_release (&pta_obstack);
5546   VEC_free (constraint_t, heap, constraints);
5547
5548   for (i = 0; i < graph->size; i++)
5549     VEC_free (constraint_t, heap, graph->complex[i]);
5550   free (graph->complex);
5551
5552   free (graph->rep);
5553   free (graph->succs);
5554   free (graph->pe);
5555   free (graph->pe_rep);
5556   free (graph->indirect_cycles);
5557   free (graph);
5558
5559   VEC_free (varinfo_t, heap, varmap);
5560   free_alloc_pool (variable_info_pool);
5561   free_alloc_pool (constraint_pool);
5562   have_alias_info = false;
5563 }
5564
5565
5566 /* Compute points-to information for every SSA_NAME pointer in the
5567    current function and compute the transitive closure of escaped
5568    variables to re-initialize the call-clobber states of local variables.  */
5569
5570 unsigned int
5571 compute_may_aliases (void)
5572 {
5573   /* For each pointer P_i, determine the sets of variables that P_i may
5574      point-to.  Compute the reachability set of escaped and call-used
5575      variables.  */
5576   compute_points_to_sets ();
5577
5578   /* Debugging dumps.  */
5579   if (dump_file)
5580     {
5581       dump_alias_info (dump_file);
5582
5583       if (dump_flags & TDF_DETAILS)
5584         dump_referenced_vars (dump_file);
5585     }
5586
5587   /* Deallocate memory used by aliasing data structures and the internal
5588      points-to solution.  */
5589   delete_points_to_sets ();
5590
5591   gcc_assert (!need_ssa_update_p (cfun));
5592
5593   return 0;
5594 }
5595
5596 static bool
5597 gate_tree_pta (void)
5598 {
5599   return flag_tree_pta;
5600 }
5601
5602 /* A dummy pass to cause points-to information to be computed via
5603    TODO_rebuild_alias.  */
5604
5605 struct gimple_opt_pass pass_build_alias =
5606 {
5607  {
5608   GIMPLE_PASS,
5609   "alias",                  /* name */
5610   gate_tree_pta,            /* gate */
5611   NULL,                     /* execute */
5612   NULL,                     /* sub */
5613   NULL,                     /* next */
5614   0,                        /* static_pass_number */
5615   TV_NONE,                  /* tv_id */
5616   PROP_cfg | PROP_ssa,      /* properties_required */
5617   0,                        /* properties_provided */
5618   0,                        /* properties_destroyed */
5619   0,                        /* todo_flags_start */
5620   TODO_rebuild_alias | TODO_dump_func  /* todo_flags_finish */
5621  }
5622 };
5623
5624 /* A dummy pass to cause points-to information to be computed via
5625    TODO_rebuild_alias.  */
5626
5627 struct gimple_opt_pass pass_build_ealias =
5628 {
5629  {
5630   GIMPLE_PASS,
5631   "ealias",                 /* name */
5632   gate_tree_pta,            /* gate */
5633   NULL,                     /* execute */
5634   NULL,                     /* sub */
5635   NULL,                     /* next */
5636   0,                        /* static_pass_number */
5637   TV_NONE,                  /* tv_id */
5638   PROP_cfg | PROP_ssa,      /* properties_required */
5639   0,                        /* properties_provided */
5640   0,                        /* properties_destroyed */
5641   0,                        /* todo_flags_start */
5642   TODO_rebuild_alias | TODO_dump_func  /* todo_flags_finish */
5643  }
5644 };
5645
5646
5647 /* Return true if we should execute IPA PTA.  */
5648 static bool
5649 gate_ipa_pta (void)
5650 {
5651   return (flag_ipa_pta
5652           /* Don't bother doing anything if the program has errors.  */
5653           && !(errorcount || sorrycount));
5654 }
5655
5656 /* Execute the driver for IPA PTA.  */
5657 static unsigned int
5658 ipa_pta_execute (void)
5659 {
5660   struct cgraph_node *node;
5661   struct scc_info *si;
5662
5663   in_ipa_mode = 1;
5664   init_alias_heapvars ();
5665   init_alias_vars ();
5666
5667   for (node = cgraph_nodes; node; node = node->next)
5668     {
5669       unsigned int varid;
5670
5671       varid = create_function_info_for (node->decl,
5672                                         cgraph_node_name (node));
5673       if (node->local.externally_visible)
5674         {
5675           varinfo_t fi = get_varinfo (varid);
5676           for (; fi; fi = fi->next)
5677             make_constraint_from (fi, anything_id);
5678         }
5679     }
5680   for (node = cgraph_nodes; node; node = node->next)
5681     {
5682       if (node->analyzed)
5683         {
5684           struct function *func = DECL_STRUCT_FUNCTION (node->decl);
5685           basic_block bb;
5686           tree old_func_decl = current_function_decl;
5687           if (dump_file)
5688             fprintf (dump_file,
5689                      "Generating constraints for %s\n",
5690                      cgraph_node_name (node));
5691           push_cfun (func);
5692           current_function_decl = node->decl;
5693
5694           FOR_EACH_BB_FN (bb, func)
5695             {
5696               gimple_stmt_iterator gsi;
5697
5698               for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
5699                    gsi_next (&gsi))
5700                 {
5701                   gimple phi = gsi_stmt (gsi);
5702
5703                   if (is_gimple_reg (gimple_phi_result (phi)))
5704                     find_func_aliases (phi);
5705                 }
5706
5707               for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5708                 find_func_aliases (gsi_stmt (gsi));
5709             }
5710           current_function_decl = old_func_decl;
5711           pop_cfun ();
5712         }
5713       else
5714         {
5715           /* Make point to anything.  */
5716         }
5717     }
5718
5719   if (dump_file)
5720     {
5721       fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5722       dump_constraints (dump_file);
5723     }
5724
5725   if (dump_file)
5726     fprintf (dump_file,
5727              "\nCollapsing static cycles and doing variable "
5728              "substitution:\n");
5729
5730   init_graph (VEC_length (varinfo_t, varmap) * 2);
5731   build_pred_graph ();
5732   si = perform_var_substitution (graph);
5733   rewrite_constraints (graph, si);
5734
5735   build_succ_graph ();
5736   free_var_substitution_info (si);
5737   move_complex_constraints (graph);
5738   unite_pointer_equivalences (graph);
5739   find_indirect_cycles (graph);
5740
5741   /* Implicit nodes and predecessors are no longer necessary at this
5742      point. */
5743   remove_preds_and_fake_succs (graph);
5744
5745   if (dump_file)
5746     fprintf (dump_file, "\nSolving graph\n");
5747
5748   solve_graph (graph);
5749
5750   if (dump_file)
5751     dump_sa_points_to_info (dump_file);
5752
5753   in_ipa_mode = 0;
5754   delete_alias_heapvars ();
5755   delete_points_to_sets ();
5756   return 0;
5757 }
5758
5759 struct simple_ipa_opt_pass pass_ipa_pta =
5760 {
5761  {
5762   SIMPLE_IPA_PASS,
5763   "pta",                                /* name */
5764   gate_ipa_pta,                 /* gate */
5765   ipa_pta_execute,                      /* execute */
5766   NULL,                                 /* sub */
5767   NULL,                                 /* next */
5768   0,                                    /* static_pass_number */
5769   TV_IPA_PTA,                   /* tv_id */
5770   0,                                    /* properties_required */
5771   0,                                    /* properties_provided */
5772   0,                                    /* properties_destroyed */
5773   0,                                    /* todo_flags_start */
5774   TODO_update_ssa                       /* todo_flags_finish */
5775  }
5776 };
5777
5778
5779 #include "gt-tree-ssa-structalias.h"