OSDN Git Service

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