OSDN Git Service

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