OSDN Git Service

gcc/ChangeLog:
[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 "rtl.h"
31 #include "tm_p.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
34 #include "output.h"
35 #include "tree.h"
36 #include "tree-flow.h"
37 #include "tree-inline.h"
38 #include "diagnostic.h"
39 #include "toplev.h"
40 #include "gimple.h"
41 #include "hashtab.h"
42 #include "function.h"
43 #include "cgraph.h"
44 #include "tree-pass.h"
45 #include "timevar.h"
46 #include "alloc-pool.h"
47 #include "splay-tree.h"
48 #include "params.h"
49 #include "cgraph.h"
50 #include "alias.h"
51 #include "pointer-set.h"
52
53 /* The idea behind this analyzer is to generate set constraints from the
54    program, then solve the resulting constraints in order to generate the
55    points-to sets.
56
57    Set constraints are a way of modeling program analysis problems that
58    involve sets.  They consist of an inclusion constraint language,
59    describing the variables (each variable is a set) and operations that
60    are involved on the variables, and a set of rules that derive facts
61    from these operations.  To solve a system of set constraints, you derive
62    all possible facts under the rules, which gives you the correct sets
63    as a consequence.
64
65    See  "Efficient Field-sensitive pointer analysis for C" by "David
66    J. Pearce and Paul H. J. Kelly and Chris Hankin, at
67    http://citeseer.ist.psu.edu/pearce04efficient.html
68
69    Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
70    of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
71    http://citeseer.ist.psu.edu/heintze01ultrafast.html
72
73    There are three types of real constraint expressions, DEREF,
74    ADDRESSOF, and SCALAR.  Each constraint expression consists
75    of a constraint type, a variable, and an offset.
76
77    SCALAR is a constraint expression type used to represent x, whether
78    it appears on the LHS or the RHS of a statement.
79    DEREF is a constraint expression type used to represent *x, whether
80    it appears on the LHS or the RHS of a statement.
81    ADDRESSOF is a constraint expression used to represent &x, whether
82    it appears on the LHS or the RHS of a statement.
83
84    Each pointer variable in the program is assigned an integer id, and
85    each field of a structure variable is assigned an integer id as well.
86
87    Structure variables are linked to their list of fields through a "next
88    field" in each variable that points to the next field in offset
89    order.
90    Each variable for a structure field has
91
92    1. "size", that tells the size in bits of that field.
93    2. "fullsize, that tells the size in bits of the entire structure.
94    3. "offset", that tells the offset in bits from the beginning of the
95    structure to this field.
96
97    Thus,
98    struct f
99    {
100      int a;
101      int b;
102    } foo;
103    int *bar;
104
105    looks like
106
107    foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
108    foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
109    bar -> id 3, size 32, offset 0, fullsize 32, next NULL
110
111
112   In order to solve the system of set constraints, the following is
113   done:
114
115   1. Each constraint variable x has a solution set associated with it,
116   Sol(x).
117
118   2. Constraints are separated into direct, copy, and complex.
119   Direct constraints are ADDRESSOF constraints that require no extra
120   processing, such as P = &Q
121   Copy constraints are those of the form P = Q.
122   Complex constraints are all the constraints involving dereferences
123   and offsets (including offsetted copies).
124
125   3. All direct constraints of the form P = &Q are processed, such
126   that Q is added to Sol(P)
127
128   4. All complex constraints for a given constraint variable are stored in a
129   linked list attached to that variable's node.
130
131   5. A directed graph is built out of the copy constraints. Each
132   constraint variable is a node in the graph, and an edge from
133   Q to P is added for each copy constraint of the form P = Q
134
135   6. The graph is then walked, and solution sets are
136   propagated along the copy edges, such that an edge from Q to P
137   causes Sol(P) <- Sol(P) union Sol(Q).
138
139   7.  As we visit each node, all complex constraints associated with
140   that node are processed by adding appropriate copy edges to the graph, or the
141   appropriate variables to the solution set.
142
143   8. The process of walking the graph is iterated until no solution
144   sets change.
145
146   Prior to walking the graph in steps 6 and 7, We perform static
147   cycle elimination on the constraint graph, as well
148   as off-line variable substitution.
149
150   TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
151   on and turned into anything), but isn't.  You can just see what offset
152   inside the pointed-to struct it's going to access.
153
154   TODO: Constant bounded arrays can be handled as if they were structs of the
155   same number of elements.
156
157   TODO: Modeling heap and incoming pointers becomes much better if we
158   add fields to them as we discover them, which we could do.
159
160   TODO: We could handle unions, but to be honest, it's probably not
161   worth the pain or slowdown.  */
162
163 /* IPA-PTA optimizations possible.
164
165    When the indirect function called is ANYTHING we can add disambiguation
166    based on the function signatures (or simply the parameter count which
167    is the varinfo size).  We also do not need to consider functions that
168    do not have their address taken.
169
170    The is_global_var bit which marks escape points is overly conservative
171    in IPA mode.  Split it to is_escape_point and is_global_var - only
172    externally visible globals are escape points in IPA mode.  This is
173    also needed to fix the pt_solution_includes_global predicate
174    (and thus ptr_deref_may_alias_global_p).
175
176    The way we introduce DECL_PT_UID to avoid fixing up all points-to
177    sets in the translation unit when we copy a DECL during inlining
178    pessimizes precision.  The advantage is that the DECL_PT_UID keeps
179    compile-time and memory usage overhead low - the points-to sets
180    do not grow or get unshared as they would during a fixup phase.
181    An alternative solution is to delay IPA PTA until after all
182    inlining transformations have been applied.
183
184    The way we propagate clobber/use information isn't optimized.
185    It should use a new complex constraint that properly filters
186    out local variables of the callee (though that would make
187    the sets invalid after inlining).  OTOH we might as well
188    admit defeat to WHOPR and simply do all the clobber/use analysis
189    and propagation after PTA finished but before we threw away
190    points-to information for memory variables.  WHOPR and PTA
191    do not play along well anyway - the whole constraint solving
192    would need to be done in WPA phase and it will be very interesting
193    to apply the results to local SSA names during LTRANS phase.
194
195    We probably should compute a per-function unit-ESCAPE solution
196    propagating it simply like the clobber / uses solutions.  The
197    solution can go alongside the non-IPA espaced solution and be
198    used to query which vars escape the unit through a function.
199
200    We never put function decls in points-to sets so we do not
201    keep the set of called functions for indirect calls.
202
203    And probably more.  */
204
205 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
206 htab_t heapvar_for_stmt;
207
208 static bool use_field_sensitive = true;
209 static int in_ipa_mode = 0;
210
211 /* Used for predecessor bitmaps. */
212 static bitmap_obstack predbitmap_obstack;
213
214 /* Used for points-to sets.  */
215 static bitmap_obstack pta_obstack;
216
217 /* Used for oldsolution members of variables. */
218 static bitmap_obstack oldpta_obstack;
219
220 /* Used for per-solver-iteration bitmaps.  */
221 static bitmap_obstack iteration_obstack;
222
223 static unsigned int create_variable_info_for (tree, const char *);
224 typedef struct constraint_graph *constraint_graph_t;
225 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
226
227 struct constraint;
228 typedef struct constraint *constraint_t;
229
230 DEF_VEC_P(constraint_t);
231 DEF_VEC_ALLOC_P(constraint_t,heap);
232
233 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d)        \
234   if (a)                                                \
235     EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
236
237 static struct constraint_stats
238 {
239   unsigned int total_vars;
240   unsigned int nonpointer_vars;
241   unsigned int unified_vars_static;
242   unsigned int unified_vars_dynamic;
243   unsigned int iterations;
244   unsigned int num_edges;
245   unsigned int num_implicit_edges;
246   unsigned int points_to_sets_created;
247 } stats;
248
249 struct variable_info
250 {
251   /* ID of this variable  */
252   unsigned int id;
253
254   /* True if this is a variable created by the constraint analysis, such as
255      heap variables and constraints we had to break up.  */
256   unsigned int is_artificial_var : 1;
257
258   /* True if this is a special variable whose solution set should not be
259      changed.  */
260   unsigned int is_special_var : 1;
261
262   /* True for variables whose size is not known or variable.  */
263   unsigned int is_unknown_size_var : 1;
264
265   /* True for (sub-)fields that represent a whole variable.  */
266   unsigned int is_full_var : 1;
267
268   /* True if this is a heap variable.  */
269   unsigned int is_heap_var : 1;
270
271   /* True if this is a variable tracking a restrict pointer source.  */
272   unsigned int is_restrict_var : 1;
273
274   /* True if this field may contain pointers.  */
275   unsigned int may_have_pointers : 1;
276
277   /* True if this field has only restrict qualified pointers.  */
278   unsigned int only_restrict_pointers : 1;
279
280   /* True if this represents a global variable.  */
281   unsigned int is_global_var : 1;
282
283   /* True if this represents a IPA function info.  */
284   unsigned int is_fn_info : 1;
285
286   /* A link to the variable for the next field in this structure.  */
287   struct variable_info *next;
288
289   /* Offset of this variable, in bits, from the base variable  */
290   unsigned HOST_WIDE_INT offset;
291
292   /* Size of the variable, in bits.  */
293   unsigned HOST_WIDE_INT size;
294
295   /* Full size of the base variable, in bits.  */
296   unsigned HOST_WIDE_INT fullsize;
297
298   /* Name of this variable */
299   const char *name;
300
301   /* Tree that this variable is associated with.  */
302   tree decl;
303
304   /* Points-to set for this variable.  */
305   bitmap solution;
306
307   /* Old points-to set for this variable.  */
308   bitmap oldsolution;
309 };
310 typedef struct variable_info *varinfo_t;
311
312 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
313 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
314                                                    unsigned HOST_WIDE_INT);
315 static varinfo_t lookup_vi_for_tree (tree);
316
317 /* Pool of variable info structures.  */
318 static alloc_pool variable_info_pool;
319
320 DEF_VEC_P(varinfo_t);
321
322 DEF_VEC_ALLOC_P(varinfo_t, heap);
323
324 /* Table of variable info structures for constraint variables.
325    Indexed directly by variable info id.  */
326 static VEC(varinfo_t,heap) *varmap;
327
328 /* Return the varmap element N */
329
330 static inline varinfo_t
331 get_varinfo (unsigned int n)
332 {
333   return VEC_index (varinfo_t, varmap, n);
334 }
335
336 /* Static IDs for the special variables.  */
337 enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
338        escaped_id = 3, nonlocal_id = 4,
339        storedanything_id = 5, integer_id = 6 };
340
341 struct GTY(()) heapvar_map {
342   struct tree_map map;
343   unsigned HOST_WIDE_INT offset;
344 };
345
346 static int
347 heapvar_map_eq (const void *p1, const void *p2)
348 {
349   const struct heapvar_map *h1 = (const struct heapvar_map *)p1;
350   const struct heapvar_map *h2 = (const struct heapvar_map *)p2;
351   return (h1->map.base.from == h2->map.base.from
352           && h1->offset == h2->offset);
353 }
354
355 static unsigned int
356 heapvar_map_hash (struct heapvar_map *h)
357 {
358   return iterative_hash_host_wide_int (h->offset,
359                                        htab_hash_pointer (h->map.base.from));
360 }
361
362 /* Lookup a heap var for FROM, and return it if we find one.  */
363
364 static tree
365 heapvar_lookup (tree from, unsigned HOST_WIDE_INT offset)
366 {
367   struct heapvar_map *h, in;
368   in.map.base.from = from;
369   in.offset = offset;
370   h = (struct heapvar_map *) htab_find_with_hash (heapvar_for_stmt, &in,
371                                                   heapvar_map_hash (&in));
372   if (h)
373     return h->map.to;
374   return NULL_TREE;
375 }
376
377 /* Insert a mapping FROM->TO in the heap var for statement
378    hashtable.  */
379
380 static void
381 heapvar_insert (tree from, unsigned HOST_WIDE_INT offset, tree to)
382 {
383   struct heapvar_map *h;
384   void **loc;
385
386   h = GGC_NEW (struct heapvar_map);
387   h->map.base.from = from;
388   h->offset = offset;
389   h->map.hash = heapvar_map_hash (h);
390   h->map.to = to;
391   loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->map.hash, INSERT);
392   gcc_assert (*loc == NULL);
393   *(struct heapvar_map **) loc = h;
394 }
395
396 /* Return a new variable info structure consisting for a variable
397    named NAME, and using constraint graph node NODE.  Append it
398    to the vector of variable info structures.  */
399
400 static varinfo_t
401 new_var_info (tree t, const char *name)
402 {
403   unsigned index = VEC_length (varinfo_t, varmap);
404   varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
405
406   ret->id = index;
407   ret->name = name;
408   ret->decl = t;
409   /* Vars without decl are artificial and do not have sub-variables.  */
410   ret->is_artificial_var = (t == NULL_TREE);
411   ret->is_special_var = false;
412   ret->is_unknown_size_var = false;
413   ret->is_full_var = (t == NULL_TREE);
414   ret->is_heap_var = false;
415   ret->is_restrict_var = false;
416   ret->may_have_pointers = true;
417   ret->only_restrict_pointers = false;
418   ret->is_global_var = (t == NULL_TREE);
419   ret->is_fn_info = false;
420   if (t && DECL_P (t))
421     ret->is_global_var = is_global_var (t);
422   ret->solution = BITMAP_ALLOC (&pta_obstack);
423   ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
424   ret->next = NULL;
425
426   stats.total_vars++;
427
428   VEC_safe_push (varinfo_t, heap, varmap, ret);
429
430   return ret;
431 }
432
433
434 /* A map mapping call statements to per-stmt variables for uses
435    and clobbers specific to the call.  */
436 struct pointer_map_t *call_stmt_vars;
437
438 /* Lookup or create the variable for the call statement CALL.  */
439
440 static varinfo_t
441 get_call_vi (gimple call)
442 {
443   void **slot_p;
444   varinfo_t vi, vi2;
445
446   slot_p = pointer_map_insert (call_stmt_vars, call);
447   if (*slot_p)
448     return (varinfo_t) *slot_p;
449
450   vi = new_var_info (NULL_TREE, "CALLUSED");
451   vi->offset = 0;
452   vi->size = 1;
453   vi->fullsize = 2;
454   vi->is_full_var = true;
455
456   vi->next = vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
457   vi2->offset = 1;
458   vi2->size = 1;
459   vi2->fullsize = 2;
460   vi2->is_full_var = true;
461
462   *slot_p = (void *) vi;
463   return vi;
464 }
465
466 /* Lookup the variable for the call statement CALL representing
467    the uses.  Returns NULL if there is nothing special about this call.  */
468
469 static varinfo_t
470 lookup_call_use_vi (gimple call)
471 {
472   void **slot_p;
473
474   slot_p = pointer_map_contains (call_stmt_vars, call);
475   if (slot_p)
476     return (varinfo_t) *slot_p;
477
478   return NULL;
479 }
480
481 /* Lookup the variable for the call statement CALL representing
482    the clobbers.  Returns NULL if there is nothing special about this call.  */
483
484 static varinfo_t
485 lookup_call_clobber_vi (gimple call)
486 {
487   varinfo_t uses = lookup_call_use_vi (call);
488   if (!uses)
489     return NULL;
490
491   return uses->next;
492 }
493
494 /* Lookup or create the variable for the call statement CALL representing
495    the uses.  */
496
497 static varinfo_t
498 get_call_use_vi (gimple call)
499 {
500   return get_call_vi (call);
501 }
502
503 /* Lookup or create the variable for the call statement CALL representing
504    the clobbers.  */
505
506 static varinfo_t ATTRIBUTE_UNUSED
507 get_call_clobber_vi (gimple call)
508 {
509   return get_call_vi (call)->next;
510 }
511
512
513 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
514
515 /* An expression that appears in a constraint.  */
516
517 struct constraint_expr
518 {
519   /* Constraint type.  */
520   constraint_expr_type type;
521
522   /* Variable we are referring to in the constraint.  */
523   unsigned int var;
524
525   /* Offset, in bits, of this constraint from the beginning of
526      variables it ends up referring to.
527
528      IOW, in a deref constraint, we would deref, get the result set,
529      then add OFFSET to each member.   */
530   HOST_WIDE_INT offset;
531 };
532
533 /* Use 0x8000... as special unknown offset.  */
534 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
535
536 typedef struct constraint_expr ce_s;
537 DEF_VEC_O(ce_s);
538 DEF_VEC_ALLOC_O(ce_s, heap);
539 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
540 static void get_constraint_for (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 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 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 (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
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 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 (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
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 (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
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 (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
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 (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
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 (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
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 (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
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 (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
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 = get_name (decl);
2763   char *temp;
2764   int num_printed = 0;
2765
2766   if (res != NULL)
2767     return res;
2768
2769   res = "NULL";
2770   if (!dump_file)
2771     return res;
2772
2773   if (TREE_CODE (decl) == SSA_NAME)
2774     {
2775       num_printed = asprintf (&temp, "%s_%u",
2776                               alias_get_name (SSA_NAME_VAR (decl)),
2777                               SSA_NAME_VERSION (decl));
2778     }
2779   else if (DECL_P (decl))
2780     {
2781       num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2782     }
2783   if (num_printed > 0)
2784     {
2785       res = ggc_strdup (temp);
2786       free (temp);
2787     }
2788   return res;
2789 }
2790
2791 /* Find the variable id for tree T in the map.
2792    If T doesn't exist in the map, create an entry for it and return it.  */
2793
2794 static varinfo_t
2795 get_vi_for_tree (tree t)
2796 {
2797   void **slot = pointer_map_contains (vi_for_tree, t);
2798   if (slot == NULL)
2799     return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2800
2801   return (varinfo_t) *slot;
2802 }
2803
2804 /* Get a scalar constraint expression for a new temporary variable.  */
2805
2806 static struct constraint_expr
2807 new_scalar_tmp_constraint_exp (const char *name)
2808 {
2809   struct constraint_expr tmp;
2810   varinfo_t vi;
2811
2812   vi = new_var_info (NULL_TREE, name);
2813   vi->offset = 0;
2814   vi->size = -1;
2815   vi->fullsize = -1;
2816   vi->is_full_var = 1;
2817
2818   tmp.var = vi->id;
2819   tmp.type = SCALAR;
2820   tmp.offset = 0;
2821
2822   return tmp;
2823 }
2824
2825 /* Get a constraint expression vector from an SSA_VAR_P node.
2826    If address_p is true, the result will be taken its address of.  */
2827
2828 static void
2829 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2830 {
2831   struct constraint_expr cexpr;
2832   varinfo_t vi;
2833
2834   /* We allow FUNCTION_DECLs here even though it doesn't make much sense.  */
2835   gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2836
2837   /* For parameters, get at the points-to set for the actual parm
2838      decl.  */
2839   if (TREE_CODE (t) == SSA_NAME
2840       && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2841       && SSA_NAME_IS_DEFAULT_DEF (t))
2842     {
2843       get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2844       return;
2845     }
2846
2847   vi = get_vi_for_tree (t);
2848   cexpr.var = vi->id;
2849   cexpr.type = SCALAR;
2850   cexpr.offset = 0;
2851   /* If we determine the result is "anything", and we know this is readonly,
2852      say it points to readonly memory instead.  */
2853   if (cexpr.var == anything_id && TREE_READONLY (t))
2854     {
2855       gcc_unreachable ();
2856       cexpr.type = ADDRESSOF;
2857       cexpr.var = readonly_id;
2858     }
2859
2860   /* If we are not taking the address of the constraint expr, add all
2861      sub-fiels of the variable as well.  */
2862   if (!address_p
2863       && !vi->is_full_var)
2864     {
2865       for (; vi; vi = vi->next)
2866         {
2867           cexpr.var = vi->id;
2868           VEC_safe_push (ce_s, heap, *results, &cexpr);
2869         }
2870       return;
2871     }
2872
2873   VEC_safe_push (ce_s, heap, *results, &cexpr);
2874 }
2875
2876 /* Process constraint T, performing various simplifications and then
2877    adding it to our list of overall constraints.  */
2878
2879 static void
2880 process_constraint (constraint_t t)
2881 {
2882   struct constraint_expr rhs = t->rhs;
2883   struct constraint_expr lhs = t->lhs;
2884
2885   gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2886   gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2887
2888   /* If we didn't get any useful constraint from the lhs we get
2889      &ANYTHING as fallback from get_constraint_for.  Deal with
2890      it here by turning it into *ANYTHING.  */
2891   if (lhs.type == ADDRESSOF
2892       && lhs.var == anything_id)
2893     lhs.type = DEREF;
2894
2895   /* ADDRESSOF on the lhs is invalid.  */
2896   gcc_assert (lhs.type != ADDRESSOF);
2897
2898   /* We shouldn't add constraints from things that cannot have pointers.
2899      It's not completely trivial to avoid in the callers, so do it here.  */
2900   if (rhs.type != ADDRESSOF
2901       && !get_varinfo (rhs.var)->may_have_pointers)
2902     return;
2903
2904   /* Likewise adding to the solution of a non-pointer var isn't useful.  */
2905   if (!get_varinfo (lhs.var)->may_have_pointers)
2906     return;
2907
2908   /* This can happen in our IR with things like n->a = *p */
2909   if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2910     {
2911       /* Split into tmp = *rhs, *lhs = tmp */
2912       struct constraint_expr tmplhs;
2913       tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
2914       process_constraint (new_constraint (tmplhs, rhs));
2915       process_constraint (new_constraint (lhs, tmplhs));
2916     }
2917   else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2918     {
2919       /* Split into tmp = &rhs, *lhs = tmp */
2920       struct constraint_expr tmplhs;
2921       tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
2922       process_constraint (new_constraint (tmplhs, rhs));
2923       process_constraint (new_constraint (lhs, tmplhs));
2924     }
2925   else
2926     {
2927       gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2928       VEC_safe_push (constraint_t, heap, constraints, t);
2929     }
2930 }
2931
2932 /* Return true if T is a type that could contain pointers.  */
2933
2934 static bool
2935 type_could_have_pointers (tree type)
2936 {
2937   if (POINTER_TYPE_P (type))
2938     return true;
2939
2940   if (TREE_CODE (type) == ARRAY_TYPE)
2941     return type_could_have_pointers (TREE_TYPE (type));
2942
2943   return AGGREGATE_TYPE_P (type);
2944 }
2945
2946 /* Return true if T is a variable of a type that could contain
2947    pointers.  */
2948
2949 static bool
2950 could_have_pointers (tree t)
2951 {
2952   return type_could_have_pointers (TREE_TYPE (t));
2953 }
2954
2955 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2956    structure.  */
2957
2958 static HOST_WIDE_INT
2959 bitpos_of_field (const tree fdecl)
2960 {
2961
2962   if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2963       || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2964     return -1;
2965
2966   return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2967           + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2968 }
2969
2970
2971 /* Get constraint expressions for offsetting PTR by OFFSET.  Stores the
2972    resulting constraint expressions in *RESULTS.  */
2973
2974 static void
2975 get_constraint_for_ptr_offset (tree ptr, tree offset,
2976                                VEC (ce_s, heap) **results)
2977 {
2978   struct constraint_expr c;
2979   unsigned int j, n;
2980   HOST_WIDE_INT rhsunitoffset, rhsoffset;
2981
2982   /* If we do not do field-sensitive PTA adding offsets to pointers
2983      does not change the points-to solution.  */
2984   if (!use_field_sensitive)
2985     {
2986       get_constraint_for (ptr, results);
2987       return;
2988     }
2989
2990   /* If the offset is not a non-negative integer constant that fits
2991      in a HOST_WIDE_INT, we have to fall back to a conservative
2992      solution which includes all sub-fields of all pointed-to
2993      variables of ptr.  */
2994   if (offset == NULL_TREE
2995       || !host_integerp (offset, 0))
2996     rhsoffset = UNKNOWN_OFFSET;
2997   else
2998     {
2999       /* Make sure the bit-offset also fits.  */
3000       rhsunitoffset = TREE_INT_CST_LOW (offset);
3001       rhsoffset = rhsunitoffset * BITS_PER_UNIT;
3002       if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
3003         rhsoffset = UNKNOWN_OFFSET;
3004     }
3005
3006   get_constraint_for (ptr, results);
3007   if (rhsoffset == 0)
3008     return;
3009
3010   /* As we are eventually appending to the solution do not use
3011      VEC_iterate here.  */
3012   n = VEC_length (ce_s, *results);
3013   for (j = 0; j < n; j++)
3014     {
3015       varinfo_t curr;
3016       c = *VEC_index (ce_s, *results, j);
3017       curr = get_varinfo (c.var);
3018
3019       if (c.type == ADDRESSOF
3020           /* If this varinfo represents a full variable just use it.  */
3021           && curr->is_full_var)
3022         c.offset = 0;
3023       else if (c.type == ADDRESSOF
3024                /* If we do not know the offset add all subfields.  */
3025                && rhsoffset == UNKNOWN_OFFSET)
3026         {
3027           varinfo_t temp = lookup_vi_for_tree (curr->decl);
3028           do
3029             {
3030               struct constraint_expr c2;
3031               c2.var = temp->id;
3032               c2.type = ADDRESSOF;
3033               c2.offset = 0;
3034               if (c2.var != c.var)
3035                 VEC_safe_push (ce_s, heap, *results, &c2);
3036               temp = temp->next;
3037             }
3038           while (temp);
3039         }
3040       else if (c.type == ADDRESSOF)
3041         {
3042           varinfo_t temp;
3043           unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
3044
3045           /* Search the sub-field which overlaps with the
3046              pointed-to offset.  If the result is outside of the variable
3047              we have to provide a conservative result, as the variable is
3048              still reachable from the resulting pointer (even though it
3049              technically cannot point to anything).  The last and first
3050              sub-fields are such conservative results.
3051              ???  If we always had a sub-field for &object + 1 then
3052              we could represent this in a more precise way.  */
3053           if (rhsoffset < 0
3054               && curr->offset < offset)
3055             offset = 0;
3056           temp = first_or_preceding_vi_for_offset (curr, offset);
3057
3058           /* If the found variable is not exactly at the pointed to
3059              result, we have to include the next variable in the
3060              solution as well.  Otherwise two increments by offset / 2
3061              do not result in the same or a conservative superset
3062              solution.  */
3063           if (temp->offset != offset
3064               && temp->next != NULL)
3065             {
3066               struct constraint_expr c2;
3067               c2.var = temp->next->id;
3068               c2.type = ADDRESSOF;
3069               c2.offset = 0;
3070               VEC_safe_push (ce_s, heap, *results, &c2);
3071             }
3072           c.var = temp->id;
3073           c.offset = 0;
3074         }
3075       else
3076         c.offset = rhsoffset;
3077
3078       VEC_replace (ce_s, *results, j, &c);
3079     }
3080 }
3081
3082
3083 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3084    If address_p is true the result will be taken its address of.  */
3085
3086 static void
3087 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
3088                                   bool address_p)
3089 {
3090   tree orig_t = t;
3091   HOST_WIDE_INT bitsize = -1;
3092   HOST_WIDE_INT bitmaxsize = -1;
3093   HOST_WIDE_INT bitpos;
3094   tree forzero;
3095   struct constraint_expr *result;
3096
3097   /* Some people like to do cute things like take the address of
3098      &0->a.b */
3099   forzero = t;
3100   while (handled_component_p (forzero)
3101          || INDIRECT_REF_P (forzero))
3102     forzero = TREE_OPERAND (forzero, 0);
3103
3104   if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3105     {
3106       struct constraint_expr temp;
3107
3108       temp.offset = 0;
3109       temp.var = integer_id;
3110       temp.type = SCALAR;
3111       VEC_safe_push (ce_s, heap, *results, &temp);
3112       return;
3113     }
3114
3115   t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
3116
3117   /* Pretend to take the address of the base, we'll take care of
3118      adding the required subset of sub-fields below.  */
3119   get_constraint_for_1 (t, results, true);
3120   gcc_assert (VEC_length (ce_s, *results) == 1);
3121   result = VEC_last (ce_s, *results);
3122
3123   if (result->type == SCALAR
3124       && get_varinfo (result->var)->is_full_var)
3125     /* For single-field vars do not bother about the offset.  */
3126     result->offset = 0;
3127   else if (result->type == SCALAR)
3128     {
3129       /* In languages like C, you can access one past the end of an
3130          array.  You aren't allowed to dereference it, so we can
3131          ignore this constraint. When we handle pointer subtraction,
3132          we may have to do something cute here.  */
3133
3134       if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
3135           && bitmaxsize != 0)
3136         {
3137           /* It's also not true that the constraint will actually start at the
3138              right offset, it may start in some padding.  We only care about
3139              setting the constraint to the first actual field it touches, so
3140              walk to find it.  */
3141           struct constraint_expr cexpr = *result;
3142           varinfo_t curr;
3143           VEC_pop (ce_s, *results);
3144           cexpr.offset = 0;
3145           for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
3146             {
3147               if (ranges_overlap_p (curr->offset, curr->size,
3148                                     bitpos, bitmaxsize))
3149                 {
3150                   cexpr.var = curr->id;
3151                   VEC_safe_push (ce_s, heap, *results, &cexpr);
3152                   if (address_p)
3153                     break;
3154                 }
3155             }
3156           /* If we are going to take the address of this field then
3157              to be able to compute reachability correctly add at least
3158              the last field of the variable.  */
3159           if (address_p
3160               && VEC_length (ce_s, *results) == 0)
3161             {
3162               curr = get_varinfo (cexpr.var);
3163               while (curr->next != NULL)
3164                 curr = curr->next;
3165               cexpr.var = curr->id;
3166               VEC_safe_push (ce_s, heap, *results, &cexpr);
3167             }
3168           else
3169             /* Assert that we found *some* field there. The user couldn't be
3170                accessing *only* padding.  */
3171             /* Still the user could access one past the end of an array
3172                embedded in a struct resulting in accessing *only* padding.  */
3173             gcc_assert (VEC_length (ce_s, *results) >= 1
3174                         || ref_contains_array_ref (orig_t));
3175         }
3176       else if (bitmaxsize == 0)
3177         {
3178           if (dump_file && (dump_flags & TDF_DETAILS))
3179             fprintf (dump_file, "Access to zero-sized part of variable,"
3180                      "ignoring\n");
3181         }
3182       else
3183         if (dump_file && (dump_flags & TDF_DETAILS))
3184           fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3185     }
3186   else if (result->type == DEREF)
3187     {
3188       /* If we do not know exactly where the access goes say so.  Note
3189          that only for non-structure accesses we know that we access
3190          at most one subfiled of any variable.  */
3191       if (bitpos == -1
3192           || bitsize != bitmaxsize
3193           || AGGREGATE_TYPE_P (TREE_TYPE (orig_t)))
3194         result->offset = UNKNOWN_OFFSET;
3195       else
3196         result->offset = bitpos;
3197     }
3198   else if (result->type == ADDRESSOF)
3199     {
3200       /* We can end up here for component references on a
3201          VIEW_CONVERT_EXPR <>(&foobar).  */
3202       result->type = SCALAR;
3203       result->var = anything_id;
3204       result->offset = 0;
3205     }
3206   else
3207     gcc_unreachable ();
3208 }
3209
3210
3211 /* Dereference the constraint expression CONS, and return the result.
3212    DEREF (ADDRESSOF) = SCALAR
3213    DEREF (SCALAR) = DEREF
3214    DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3215    This is needed so that we can handle dereferencing DEREF constraints.  */
3216
3217 static void
3218 do_deref (VEC (ce_s, heap) **constraints)
3219 {
3220   struct constraint_expr *c;
3221   unsigned int i = 0;
3222
3223   for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3224     {
3225       if (c->type == SCALAR)
3226         c->type = DEREF;
3227       else if (c->type == ADDRESSOF)
3228         c->type = SCALAR;
3229       else if (c->type == DEREF)
3230         {
3231           struct constraint_expr tmplhs;
3232           tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3233           process_constraint (new_constraint (tmplhs, *c));
3234           c->var = tmplhs.var;
3235         }
3236       else
3237         gcc_unreachable ();
3238     }
3239 }
3240
3241 static void get_constraint_for_1 (tree, VEC (ce_s, heap) **, bool);
3242
3243 /* Given a tree T, return the constraint expression for taking the
3244    address of it.  */
3245
3246 static void
3247 get_constraint_for_address_of (tree t, VEC (ce_s, heap) **results)
3248 {
3249   struct constraint_expr *c;
3250   unsigned int i;
3251
3252   get_constraint_for_1 (t, results, true);
3253
3254   for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3255     {
3256       if (c->type == DEREF)
3257         c->type = SCALAR;
3258       else
3259         c->type = ADDRESSOF;
3260     }
3261 }
3262
3263 /* Given a tree T, return the constraint expression for it.  */
3264
3265 static void
3266 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3267 {
3268   struct constraint_expr temp;
3269
3270   /* x = integer is all glommed to a single variable, which doesn't
3271      point to anything by itself.  That is, of course, unless it is an
3272      integer constant being treated as a pointer, in which case, we
3273      will return that this is really the addressof anything.  This
3274      happens below, since it will fall into the default case. The only
3275      case we know something about an integer treated like a pointer is
3276      when it is the NULL pointer, and then we just say it points to
3277      NULL.
3278
3279      Do not do that if -fno-delete-null-pointer-checks though, because
3280      in that case *NULL does not fail, so it _should_ alias *anything.
3281      It is not worth adding a new option or renaming the existing one,
3282      since this case is relatively obscure.  */
3283   if (flag_delete_null_pointer_checks
3284       && ((TREE_CODE (t) == INTEGER_CST
3285            && integer_zerop (t))
3286           /* The only valid CONSTRUCTORs in gimple with pointer typed
3287              elements are zero-initializer.  But in IPA mode we also
3288              process global initializers, so verify at least.  */
3289           || (TREE_CODE (t) == CONSTRUCTOR
3290               && CONSTRUCTOR_NELTS (t) == 0)))
3291     {
3292       temp.var = nothing_id;
3293       temp.type = ADDRESSOF;
3294       temp.offset = 0;
3295       VEC_safe_push (ce_s, heap, *results, &temp);
3296       return;
3297     }
3298
3299   /* String constants are read-only.  */
3300   if (TREE_CODE (t) == STRING_CST)
3301     {
3302       temp.var = readonly_id;
3303       temp.type = SCALAR;
3304       temp.offset = 0;
3305       VEC_safe_push (ce_s, heap, *results, &temp);
3306       return;
3307     }
3308
3309   switch (TREE_CODE_CLASS (TREE_CODE (t)))
3310     {
3311     case tcc_expression:
3312       {
3313         switch (TREE_CODE (t))
3314           {
3315           case ADDR_EXPR:
3316             get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3317             return;
3318           default:;
3319           }
3320         break;
3321       }
3322     case tcc_reference:
3323       {
3324         switch (TREE_CODE (t))
3325           {
3326           case INDIRECT_REF:
3327             {
3328               get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3329               do_deref (results);
3330               return;
3331             }
3332           case ARRAY_REF:
3333           case ARRAY_RANGE_REF:
3334           case COMPONENT_REF:
3335             get_constraint_for_component_ref (t, results, address_p);
3336             return;
3337           case VIEW_CONVERT_EXPR:
3338             get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3339             return;
3340           /* We are missing handling for TARGET_MEM_REF here.  */
3341           default:;
3342           }
3343         break;
3344       }
3345     case tcc_exceptional:
3346       {
3347         switch (TREE_CODE (t))
3348           {
3349           case SSA_NAME:
3350             {
3351               get_constraint_for_ssa_var (t, results, address_p);
3352               return;
3353             }
3354           default:;
3355           }
3356         break;
3357       }
3358     case tcc_declaration:
3359       {
3360         get_constraint_for_ssa_var (t, results, address_p);
3361         return;
3362       }
3363     default:;
3364     }
3365
3366   /* The default fallback is a constraint from anything.  */
3367   temp.type = ADDRESSOF;
3368   temp.var = anything_id;
3369   temp.offset = 0;
3370   VEC_safe_push (ce_s, heap, *results, &temp);
3371 }
3372
3373 /* Given a gimple tree T, return the constraint expression vector for it.  */
3374
3375 static void
3376 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3377 {
3378   gcc_assert (VEC_length (ce_s, *results) == 0);
3379
3380   get_constraint_for_1 (t, results, false);
3381 }
3382
3383
3384 /* Efficiently generates constraints from all entries in *RHSC to all
3385    entries in *LHSC.  */
3386
3387 static void
3388 process_all_all_constraints (VEC (ce_s, heap) *lhsc, VEC (ce_s, heap) *rhsc)
3389 {
3390   struct constraint_expr *lhsp, *rhsp;
3391   unsigned i, j;
3392
3393   if (VEC_length (ce_s, lhsc) <= 1
3394       || VEC_length (ce_s, rhsc) <= 1)
3395     {
3396       for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3397         for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); ++j)
3398           process_constraint (new_constraint (*lhsp, *rhsp));
3399     }
3400   else
3401     {
3402       struct constraint_expr tmp;
3403       tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3404       for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
3405         process_constraint (new_constraint (tmp, *rhsp));
3406       for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3407         process_constraint (new_constraint (*lhsp, tmp));
3408     }
3409 }
3410
3411 /* Handle aggregate copies by expanding into copies of the respective
3412    fields of the structures.  */
3413
3414 static void
3415 do_structure_copy (tree lhsop, tree rhsop)
3416 {
3417   struct constraint_expr *lhsp, *rhsp;
3418   VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3419   unsigned j;
3420
3421   get_constraint_for (lhsop, &lhsc);
3422   get_constraint_for (rhsop, &rhsc);
3423   lhsp = VEC_index (ce_s, lhsc, 0);
3424   rhsp = VEC_index (ce_s, rhsc, 0);
3425   if (lhsp->type == DEREF
3426       || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3427       || rhsp->type == DEREF)
3428     {
3429       if (lhsp->type == DEREF)
3430         {
3431           gcc_assert (VEC_length (ce_s, lhsc) == 1);
3432           lhsp->offset = UNKNOWN_OFFSET;
3433         }
3434       if (rhsp->type == DEREF)
3435         {
3436           gcc_assert (VEC_length (ce_s, rhsc) == 1);
3437           rhsp->offset = UNKNOWN_OFFSET;
3438         }
3439       process_all_all_constraints (lhsc, rhsc);
3440     }
3441   else if (lhsp->type == SCALAR
3442            && (rhsp->type == SCALAR
3443                || rhsp->type == ADDRESSOF))
3444     {
3445       HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3446       HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3447       unsigned k = 0;
3448       get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize);
3449       get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize);
3450       for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp);)
3451         {
3452           varinfo_t lhsv, rhsv;
3453           rhsp = VEC_index (ce_s, rhsc, k);
3454           lhsv = get_varinfo (lhsp->var);
3455           rhsv = get_varinfo (rhsp->var);
3456           if (lhsv->may_have_pointers
3457               && ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3458                                    rhsv->offset + lhsoffset, rhsv->size))
3459             process_constraint (new_constraint (*lhsp, *rhsp));
3460           if (lhsv->offset + rhsoffset + lhsv->size
3461               > rhsv->offset + lhsoffset + rhsv->size)
3462             {
3463               ++k;
3464               if (k >= VEC_length (ce_s, rhsc))
3465                 break;
3466             }
3467           else
3468             ++j;
3469         }
3470     }
3471   else
3472     gcc_unreachable ();
3473
3474   VEC_free (ce_s, heap, lhsc);
3475   VEC_free (ce_s, heap, rhsc);
3476 }
3477
3478 /* Create a constraint ID = OP.  */
3479
3480 static void
3481 make_constraint_to (unsigned id, tree op)
3482 {
3483   VEC(ce_s, heap) *rhsc = NULL;
3484   struct constraint_expr *c;
3485   struct constraint_expr includes;
3486   unsigned int j;
3487
3488   includes.var = id;
3489   includes.offset = 0;
3490   includes.type = SCALAR;
3491
3492   get_constraint_for (op, &rhsc);
3493   for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3494     process_constraint (new_constraint (includes, *c));