OSDN Git Service

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