OSDN Git Service

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