OSDN Git Service

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