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