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