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