OSDN Git Service

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