OSDN Git Service

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