OSDN Git Service

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