OSDN Git Service

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