* config/i386/i386.md (fmodxf3): Enable for flag_finite_math_only only.
[official-gcc.git] / gcc / tree-ssa-structalias.c
blob01690872b9d391ef6965d8cdcbc42228c4ee14d5
1 /* Tree based points-to analysis
2 Copyright (C) 2005-2014 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "obstack.h"
26 #include "bitmap.h"
27 #include "sbitmap.h"
28 #include "flags.h"
29 #include "basic-block.h"
30 #include "tree.h"
31 #include "stor-layout.h"
32 #include "stmt.h"
33 #include "hash-table.h"
34 #include "tree-ssa-alias.h"
35 #include "internal-fn.h"
36 #include "gimple-expr.h"
37 #include "is-a.h"
38 #include "gimple.h"
39 #include "gimple-iterator.h"
40 #include "gimple-ssa.h"
41 #include "cgraph.h"
42 #include "stringpool.h"
43 #include "tree-ssanames.h"
44 #include "tree-into-ssa.h"
45 #include "expr.h"
46 #include "tree-dfa.h"
47 #include "tree-inline.h"
48 #include "diagnostic-core.h"
49 #include "function.h"
50 #include "tree-pass.h"
51 #include "alloc-pool.h"
52 #include "splay-tree.h"
53 #include "params.h"
54 #include "alias.h"
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.
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.
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
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
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.
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.
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.
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
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.
100 Thus,
101 struct f
103 int a;
104 int b;
105 } foo;
106 int *bar;
108 looks like
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
115 In order to solve the system of set constraints, the following is
116 done:
118 1. Each constraint variable x has a solution set associated with it,
119 Sol(x).
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).
128 3. All direct constraints of the form P = &Q are processed, such
129 that Q is added to Sol(P)
131 4. All complex constraints for a given constraint variable are stored in a
132 linked list attached to that variable's node.
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
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).
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.
146 8. The process of walking the graph is iterated until no solution
147 sets change.
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.
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.
157 TODO: Constant bounded arrays can be handled as if they were structs of the
158 same number of elements.
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.
163 TODO: We could handle unions, but to be honest, it's probably not
164 worth the pain or slowdown. */
166 /* IPA-PTA optimizations possible.
168 When the indirect function called is ANYTHING we can add disambiguation
169 based on the function signatures (or simply the parameter count which
170 is the varinfo size). We also do not need to consider functions that
171 do not have their address taken.
173 The is_global_var bit which marks escape points is overly conservative
174 in IPA mode. Split it to is_escape_point and is_global_var - only
175 externally visible globals are escape points in IPA mode. This is
176 also needed to fix the pt_solution_includes_global predicate
177 (and thus ptr_deref_may_alias_global_p).
179 The way we introduce DECL_PT_UID to avoid fixing up all points-to
180 sets in the translation unit when we copy a DECL during inlining
181 pessimizes precision. The advantage is that the DECL_PT_UID keeps
182 compile-time and memory usage overhead low - the points-to sets
183 do not grow or get unshared as they would during a fixup phase.
184 An alternative solution is to delay IPA PTA until after all
185 inlining transformations have been applied.
187 The way we propagate clobber/use information isn't optimized.
188 It should use a new complex constraint that properly filters
189 out local variables of the callee (though that would make
190 the sets invalid after inlining). OTOH we might as well
191 admit defeat to WHOPR and simply do all the clobber/use analysis
192 and propagation after PTA finished but before we threw away
193 points-to information for memory variables. WHOPR and PTA
194 do not play along well anyway - the whole constraint solving
195 would need to be done in WPA phase and it will be very interesting
196 to apply the results to local SSA names during LTRANS phase.
198 We probably should compute a per-function unit-ESCAPE solution
199 propagating it simply like the clobber / uses solutions. The
200 solution can go alongside the non-IPA espaced solution and be
201 used to query which vars escape the unit through a function.
203 We never put function decls in points-to sets so we do not
204 keep the set of called functions for indirect calls.
206 And probably more. */
208 static bool use_field_sensitive = true;
209 static int in_ipa_mode = 0;
211 /* Used for predecessor bitmaps. */
212 static bitmap_obstack predbitmap_obstack;
214 /* Used for points-to sets. */
215 static bitmap_obstack pta_obstack;
217 /* Used for oldsolution members of variables. */
218 static bitmap_obstack oldpta_obstack;
220 /* Used for per-solver-iteration bitmaps. */
221 static bitmap_obstack iteration_obstack;
223 static unsigned int create_variable_info_for (tree, const char *);
224 typedef struct constraint_graph *constraint_graph_t;
225 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
227 struct constraint;
228 typedef struct constraint *constraint_t;
231 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
232 if (a) \
233 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
235 static struct constraint_stats
237 unsigned int total_vars;
238 unsigned int nonpointer_vars;
239 unsigned int unified_vars_static;
240 unsigned int unified_vars_dynamic;
241 unsigned int iterations;
242 unsigned int num_edges;
243 unsigned int num_implicit_edges;
244 unsigned int points_to_sets_created;
245 } stats;
247 struct variable_info
249 /* ID of this variable */
250 unsigned int id;
252 /* True if this is a variable created by the constraint analysis, such as
253 heap variables and constraints we had to break up. */
254 unsigned int is_artificial_var : 1;
256 /* True if this is a special variable whose solution set should not be
257 changed. */
258 unsigned int is_special_var : 1;
260 /* True for variables whose size is not known or variable. */
261 unsigned int is_unknown_size_var : 1;
263 /* True for (sub-)fields that represent a whole variable. */
264 unsigned int is_full_var : 1;
266 /* True if this is a heap variable. */
267 unsigned int is_heap_var : 1;
269 /* True if this field may contain pointers. */
270 unsigned int may_have_pointers : 1;
272 /* True if this field has only restrict qualified pointers. */
273 unsigned int only_restrict_pointers : 1;
275 /* True if this represents a global variable. */
276 unsigned int is_global_var : 1;
278 /* True if this represents a IPA function info. */
279 unsigned int is_fn_info : 1;
281 /* The ID of the variable for the next field in this structure
282 or zero for the last field in this structure. */
283 unsigned next;
285 /* The ID of the variable for the first field in this structure. */
286 unsigned head;
288 /* Offset of this variable, in bits, from the base variable */
289 unsigned HOST_WIDE_INT offset;
291 /* Size of the variable, in bits. */
292 unsigned HOST_WIDE_INT size;
294 /* Full size of the base variable, in bits. */
295 unsigned HOST_WIDE_INT fullsize;
297 /* Name of this variable */
298 const char *name;
300 /* Tree that this variable is associated with. */
301 tree decl;
303 /* Points-to set for this variable. */
304 bitmap solution;
306 /* Old points-to set for this variable. */
307 bitmap oldsolution;
309 typedef struct variable_info *varinfo_t;
311 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
312 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
313 unsigned HOST_WIDE_INT);
314 static varinfo_t lookup_vi_for_tree (tree);
315 static inline bool type_can_have_subvars (const_tree);
317 /* Pool of variable info structures. */
318 static alloc_pool variable_info_pool;
320 /* Map varinfo to final pt_solution. */
321 static hash_map<varinfo_t, pt_solution *> *final_solutions;
322 struct obstack final_solutions_obstack;
324 /* Table of variable info structures for constraint variables.
325 Indexed directly by variable info id. */
326 static vec<varinfo_t> varmap;
328 /* Return the varmap element N */
330 static inline varinfo_t
331 get_varinfo (unsigned int n)
333 return varmap[n];
336 /* Return the next variable in the list of sub-variables of VI
337 or NULL if VI is the last sub-variable. */
339 static inline varinfo_t
340 vi_next (varinfo_t vi)
342 return get_varinfo (vi->next);
345 /* Static IDs for the special variables. Variable ID zero is unused
346 and used as terminator for the sub-variable chain. */
347 enum { nothing_id = 1, anything_id = 2, string_id = 3,
348 escaped_id = 4, nonlocal_id = 5,
349 storedanything_id = 6, integer_id = 7 };
351 /* Return a new variable info structure consisting for a variable
352 named NAME, and using constraint graph node NODE. Append it
353 to the vector of variable info structures. */
355 static varinfo_t
356 new_var_info (tree t, const char *name)
358 unsigned index = varmap.length ();
359 varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
361 ret->id = index;
362 ret->name = name;
363 ret->decl = t;
364 /* Vars without decl are artificial and do not have sub-variables. */
365 ret->is_artificial_var = (t == NULL_TREE);
366 ret->is_special_var = false;
367 ret->is_unknown_size_var = false;
368 ret->is_full_var = (t == NULL_TREE);
369 ret->is_heap_var = false;
370 ret->may_have_pointers = true;
371 ret->only_restrict_pointers = false;
372 ret->is_global_var = (t == NULL_TREE);
373 ret->is_fn_info = false;
374 if (t && DECL_P (t))
375 ret->is_global_var = (is_global_var (t)
376 /* We have to treat even local register variables
377 as escape points. */
378 || (TREE_CODE (t) == VAR_DECL
379 && DECL_HARD_REGISTER (t)));
380 ret->solution = BITMAP_ALLOC (&pta_obstack);
381 ret->oldsolution = NULL;
382 ret->next = 0;
383 ret->head = ret->id;
385 stats.total_vars++;
387 varmap.safe_push (ret);
389 return ret;
393 /* A map mapping call statements to per-stmt variables for uses
394 and clobbers specific to the call. */
395 static hash_map<gimple, varinfo_t> *call_stmt_vars;
397 /* Lookup or create the variable for the call statement CALL. */
399 static varinfo_t
400 get_call_vi (gimple call)
402 varinfo_t vi, vi2;
404 bool existed;
405 varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed);
406 if (existed)
407 return *slot_p;
409 vi = new_var_info (NULL_TREE, "CALLUSED");
410 vi->offset = 0;
411 vi->size = 1;
412 vi->fullsize = 2;
413 vi->is_full_var = true;
415 vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
416 vi2->offset = 1;
417 vi2->size = 1;
418 vi2->fullsize = 2;
419 vi2->is_full_var = true;
421 vi->next = vi2->id;
423 *slot_p = vi;
424 return vi;
427 /* Lookup the variable for the call statement CALL representing
428 the uses. Returns NULL if there is nothing special about this call. */
430 static varinfo_t
431 lookup_call_use_vi (gimple call)
433 varinfo_t *slot_p = call_stmt_vars->get (call);
434 if (slot_p)
435 return *slot_p;
437 return NULL;
440 /* Lookup the variable for the call statement CALL representing
441 the clobbers. Returns NULL if there is nothing special about this call. */
443 static varinfo_t
444 lookup_call_clobber_vi (gimple call)
446 varinfo_t uses = lookup_call_use_vi (call);
447 if (!uses)
448 return NULL;
450 return vi_next (uses);
453 /* Lookup or create the variable for the call statement CALL representing
454 the uses. */
456 static varinfo_t
457 get_call_use_vi (gimple call)
459 return get_call_vi (call);
462 /* Lookup or create the variable for the call statement CALL representing
463 the clobbers. */
465 static varinfo_t ATTRIBUTE_UNUSED
466 get_call_clobber_vi (gimple call)
468 return vi_next (get_call_vi (call));
472 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
474 /* An expression that appears in a constraint. */
476 struct constraint_expr
478 /* Constraint type. */
479 constraint_expr_type type;
481 /* Variable we are referring to in the constraint. */
482 unsigned int var;
484 /* Offset, in bits, of this constraint from the beginning of
485 variables it ends up referring to.
487 IOW, in a deref constraint, we would deref, get the result set,
488 then add OFFSET to each member. */
489 HOST_WIDE_INT offset;
492 /* Use 0x8000... as special unknown offset. */
493 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
495 typedef struct constraint_expr ce_s;
496 static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool);
497 static void get_constraint_for (tree, vec<ce_s> *);
498 static void get_constraint_for_rhs (tree, vec<ce_s> *);
499 static void do_deref (vec<ce_s> *);
501 /* Our set constraints are made up of two constraint expressions, one
502 LHS, and one RHS.
504 As described in the introduction, our set constraints each represent an
505 operation between set valued variables.
507 struct constraint
509 struct constraint_expr lhs;
510 struct constraint_expr rhs;
513 /* List of constraints that we use to build the constraint graph from. */
515 static vec<constraint_t> constraints;
516 static alloc_pool constraint_pool;
518 /* The constraint graph is represented as an array of bitmaps
519 containing successor nodes. */
521 struct constraint_graph
523 /* Size of this graph, which may be different than the number of
524 nodes in the variable map. */
525 unsigned int size;
527 /* Explicit successors of each node. */
528 bitmap *succs;
530 /* Implicit predecessors of each node (Used for variable
531 substitution). */
532 bitmap *implicit_preds;
534 /* Explicit predecessors of each node (Used for variable substitution). */
535 bitmap *preds;
537 /* Indirect cycle representatives, or -1 if the node has no indirect
538 cycles. */
539 int *indirect_cycles;
541 /* Representative node for a node. rep[a] == a unless the node has
542 been unified. */
543 unsigned int *rep;
545 /* Equivalence class representative for a label. This is used for
546 variable substitution. */
547 int *eq_rep;
549 /* Pointer equivalence label for a node. All nodes with the same
550 pointer equivalence label can be unified together at some point
551 (either during constraint optimization or after the constraint
552 graph is built). */
553 unsigned int *pe;
555 /* Pointer equivalence representative for a label. This is used to
556 handle nodes that are pointer equivalent but not location
557 equivalent. We can unite these once the addressof constraints
558 are transformed into initial points-to sets. */
559 int *pe_rep;
561 /* Pointer equivalence label for each node, used during variable
562 substitution. */
563 unsigned int *pointer_label;
565 /* Location equivalence label for each node, used during location
566 equivalence finding. */
567 unsigned int *loc_label;
569 /* Pointed-by set for each node, used during location equivalence
570 finding. This is pointed-by rather than pointed-to, because it
571 is constructed using the predecessor graph. */
572 bitmap *pointed_by;
574 /* Points to sets for pointer equivalence. This is *not* the actual
575 points-to sets for nodes. */
576 bitmap *points_to;
578 /* Bitmap of nodes where the bit is set if the node is a direct
579 node. Used for variable substitution. */
580 sbitmap direct_nodes;
582 /* Bitmap of nodes where the bit is set if the node is address
583 taken. Used for variable substitution. */
584 bitmap address_taken;
586 /* Vector of complex constraints for each graph node. Complex
587 constraints are those involving dereferences or offsets that are
588 not 0. */
589 vec<constraint_t> *complex;
592 static constraint_graph_t graph;
594 /* During variable substitution and the offline version of indirect
595 cycle finding, we create nodes to represent dereferences and
596 address taken constraints. These represent where these start and
597 end. */
598 #define FIRST_REF_NODE (varmap).length ()
599 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
601 /* Return the representative node for NODE, if NODE has been unioned
602 with another NODE.
603 This function performs path compression along the way to finding
604 the representative. */
606 static unsigned int
607 find (unsigned int node)
609 gcc_checking_assert (node < graph->size);
610 if (graph->rep[node] != node)
611 return graph->rep[node] = find (graph->rep[node]);
612 return node;
615 /* Union the TO and FROM nodes to the TO nodes.
616 Note that at some point in the future, we may want to do
617 union-by-rank, in which case we are going to have to return the
618 node we unified to. */
620 static bool
621 unite (unsigned int to, unsigned int from)
623 gcc_checking_assert (to < graph->size && from < graph->size);
624 if (to != from && graph->rep[from] != to)
626 graph->rep[from] = to;
627 return true;
629 return false;
632 /* Create a new constraint consisting of LHS and RHS expressions. */
634 static constraint_t
635 new_constraint (const struct constraint_expr lhs,
636 const struct constraint_expr rhs)
638 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
639 ret->lhs = lhs;
640 ret->rhs = rhs;
641 return ret;
644 /* Print out constraint C to FILE. */
646 static void
647 dump_constraint (FILE *file, constraint_t c)
649 if (c->lhs.type == ADDRESSOF)
650 fprintf (file, "&");
651 else if (c->lhs.type == DEREF)
652 fprintf (file, "*");
653 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
654 if (c->lhs.offset == UNKNOWN_OFFSET)
655 fprintf (file, " + UNKNOWN");
656 else if (c->lhs.offset != 0)
657 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
658 fprintf (file, " = ");
659 if (c->rhs.type == ADDRESSOF)
660 fprintf (file, "&");
661 else if (c->rhs.type == DEREF)
662 fprintf (file, "*");
663 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
664 if (c->rhs.offset == UNKNOWN_OFFSET)
665 fprintf (file, " + UNKNOWN");
666 else if (c->rhs.offset != 0)
667 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
671 void debug_constraint (constraint_t);
672 void debug_constraints (void);
673 void debug_constraint_graph (void);
674 void debug_solution_for_var (unsigned int);
675 void debug_sa_points_to_info (void);
677 /* Print out constraint C to stderr. */
679 DEBUG_FUNCTION void
680 debug_constraint (constraint_t c)
682 dump_constraint (stderr, c);
683 fprintf (stderr, "\n");
686 /* Print out all constraints to FILE */
688 static void
689 dump_constraints (FILE *file, int from)
691 int i;
692 constraint_t c;
693 for (i = from; constraints.iterate (i, &c); i++)
694 if (c)
696 dump_constraint (file, c);
697 fprintf (file, "\n");
701 /* Print out all constraints to stderr. */
703 DEBUG_FUNCTION void
704 debug_constraints (void)
706 dump_constraints (stderr, 0);
709 /* Print the constraint graph in dot format. */
711 static void
712 dump_constraint_graph (FILE *file)
714 unsigned int i;
716 /* Only print the graph if it has already been initialized: */
717 if (!graph)
718 return;
720 /* Prints the header of the dot file: */
721 fprintf (file, "strict digraph {\n");
722 fprintf (file, " node [\n shape = box\n ]\n");
723 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
724 fprintf (file, "\n // List of nodes and complex constraints in "
725 "the constraint graph:\n");
727 /* The next lines print the nodes in the graph together with the
728 complex constraints attached to them. */
729 for (i = 1; i < graph->size; i++)
731 if (i == FIRST_REF_NODE)
732 continue;
733 if (find (i) != i)
734 continue;
735 if (i < FIRST_REF_NODE)
736 fprintf (file, "\"%s\"", get_varinfo (i)->name);
737 else
738 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
739 if (graph->complex[i].exists ())
741 unsigned j;
742 constraint_t c;
743 fprintf (file, " [label=\"\\N\\n");
744 for (j = 0; graph->complex[i].iterate (j, &c); ++j)
746 dump_constraint (file, c);
747 fprintf (file, "\\l");
749 fprintf (file, "\"]");
751 fprintf (file, ";\n");
754 /* Go over the edges. */
755 fprintf (file, "\n // Edges in the constraint graph:\n");
756 for (i = 1; i < graph->size; i++)
758 unsigned j;
759 bitmap_iterator bi;
760 if (find (i) != i)
761 continue;
762 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
764 unsigned to = find (j);
765 if (i == to)
766 continue;
767 if (i < FIRST_REF_NODE)
768 fprintf (file, "\"%s\"", get_varinfo (i)->name);
769 else
770 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
771 fprintf (file, " -> ");
772 if (to < FIRST_REF_NODE)
773 fprintf (file, "\"%s\"", get_varinfo (to)->name);
774 else
775 fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
776 fprintf (file, ";\n");
780 /* Prints the tail of the dot file. */
781 fprintf (file, "}\n");
784 /* Print out the constraint graph to stderr. */
786 DEBUG_FUNCTION void
787 debug_constraint_graph (void)
789 dump_constraint_graph (stderr);
792 /* SOLVER FUNCTIONS
794 The solver is a simple worklist solver, that works on the following
795 algorithm:
797 sbitmap changed_nodes = all zeroes;
798 changed_count = 0;
799 For each node that is not already collapsed:
800 changed_count++;
801 set bit in changed nodes
803 while (changed_count > 0)
805 compute topological ordering for constraint graph
807 find and collapse cycles in the constraint graph (updating
808 changed if necessary)
810 for each node (n) in the graph in topological order:
811 changed_count--;
813 Process each complex constraint associated with the node,
814 updating changed if necessary.
816 For each outgoing edge from n, propagate the solution from n to
817 the destination of the edge, updating changed as necessary.
819 } */
821 /* Return true if two constraint expressions A and B are equal. */
823 static bool
824 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
826 return a.type == b.type && a.var == b.var && a.offset == b.offset;
829 /* Return true if constraint expression A is less than constraint expression
830 B. This is just arbitrary, but consistent, in order to give them an
831 ordering. */
833 static bool
834 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
836 if (a.type == b.type)
838 if (a.var == b.var)
839 return a.offset < b.offset;
840 else
841 return a.var < b.var;
843 else
844 return a.type < b.type;
847 /* Return true if constraint A is less than constraint B. This is just
848 arbitrary, but consistent, in order to give them an ordering. */
850 static bool
851 constraint_less (const constraint_t &a, const constraint_t &b)
853 if (constraint_expr_less (a->lhs, b->lhs))
854 return true;
855 else if (constraint_expr_less (b->lhs, a->lhs))
856 return false;
857 else
858 return constraint_expr_less (a->rhs, b->rhs);
861 /* Return true if two constraints A and B are equal. */
863 static bool
864 constraint_equal (struct constraint a, struct constraint b)
866 return constraint_expr_equal (a.lhs, b.lhs)
867 && constraint_expr_equal (a.rhs, b.rhs);
871 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
873 static constraint_t
874 constraint_vec_find (vec<constraint_t> vec,
875 struct constraint lookfor)
877 unsigned int place;
878 constraint_t found;
880 if (!vec.exists ())
881 return NULL;
883 place = vec.lower_bound (&lookfor, constraint_less);
884 if (place >= vec.length ())
885 return NULL;
886 found = vec[place];
887 if (!constraint_equal (*found, lookfor))
888 return NULL;
889 return found;
892 /* Union two constraint vectors, TO and FROM. Put the result in TO.
893 Returns true of TO set is changed. */
895 static bool
896 constraint_set_union (vec<constraint_t> *to,
897 vec<constraint_t> *from)
899 int i;
900 constraint_t c;
901 bool any_change = false;
903 FOR_EACH_VEC_ELT (*from, i, c)
905 if (constraint_vec_find (*to, *c) == NULL)
907 unsigned int place = to->lower_bound (c, constraint_less);
908 to->safe_insert (place, c);
909 any_change = true;
912 return any_change;
915 /* Expands the solution in SET to all sub-fields of variables included. */
917 static bitmap
918 solution_set_expand (bitmap set, bitmap *expanded)
920 bitmap_iterator bi;
921 unsigned j;
923 if (*expanded)
924 return *expanded;
926 *expanded = BITMAP_ALLOC (&iteration_obstack);
928 /* In a first pass expand to the head of the variables we need to
929 add all sub-fields off. This avoids quadratic behavior. */
930 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
932 varinfo_t v = get_varinfo (j);
933 if (v->is_artificial_var
934 || v->is_full_var)
935 continue;
936 bitmap_set_bit (*expanded, v->head);
939 /* In the second pass now expand all head variables with subfields. */
940 EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi)
942 varinfo_t v = get_varinfo (j);
943 if (v->head != j)
944 continue;
945 for (v = vi_next (v); v != NULL; v = vi_next (v))
946 bitmap_set_bit (*expanded, v->id);
949 /* And finally set the rest of the bits from SET. */
950 bitmap_ior_into (*expanded, set);
952 return *expanded;
955 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
956 process. */
958 static bool
959 set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
960 bitmap *expanded_delta)
962 bool changed = false;
963 bitmap_iterator bi;
964 unsigned int i;
966 /* If the solution of DELTA contains anything it is good enough to transfer
967 this to TO. */
968 if (bitmap_bit_p (delta, anything_id))
969 return bitmap_set_bit (to, anything_id);
971 /* If the offset is unknown we have to expand the solution to
972 all subfields. */
973 if (inc == UNKNOWN_OFFSET)
975 delta = solution_set_expand (delta, expanded_delta);
976 changed |= bitmap_ior_into (to, delta);
977 return changed;
980 /* For non-zero offset union the offsetted solution into the destination. */
981 EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
983 varinfo_t vi = get_varinfo (i);
985 /* If this is a variable with just one field just set its bit
986 in the result. */
987 if (vi->is_artificial_var
988 || vi->is_unknown_size_var
989 || vi->is_full_var)
990 changed |= bitmap_set_bit (to, i);
991 else
993 HOST_WIDE_INT fieldoffset = vi->offset + inc;
994 unsigned HOST_WIDE_INT size = vi->size;
996 /* If the offset makes the pointer point to before the
997 variable use offset zero for the field lookup. */
998 if (fieldoffset < 0)
999 vi = get_varinfo (vi->head);
1000 else
1001 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
1005 changed |= bitmap_set_bit (to, vi->id);
1006 if (vi->is_full_var
1007 || vi->next == 0)
1008 break;
1010 /* We have to include all fields that overlap the current field
1011 shifted by inc. */
1012 vi = vi_next (vi);
1014 while (vi->offset < fieldoffset + size);
1018 return changed;
1021 /* Insert constraint C into the list of complex constraints for graph
1022 node VAR. */
1024 static void
1025 insert_into_complex (constraint_graph_t graph,
1026 unsigned int var, constraint_t c)
1028 vec<constraint_t> complex = graph->complex[var];
1029 unsigned int place = complex.lower_bound (c, constraint_less);
1031 /* Only insert constraints that do not already exist. */
1032 if (place >= complex.length ()
1033 || !constraint_equal (*c, *complex[place]))
1034 graph->complex[var].safe_insert (place, c);
1038 /* Condense two variable nodes into a single variable node, by moving
1039 all associated info from FROM to TO. Returns true if TO node's
1040 constraint set changes after the merge. */
1042 static bool
1043 merge_node_constraints (constraint_graph_t graph, unsigned int to,
1044 unsigned int from)
1046 unsigned int i;
1047 constraint_t c;
1048 bool any_change = false;
1050 gcc_checking_assert (find (from) == to);
1052 /* Move all complex constraints from src node into to node */
1053 FOR_EACH_VEC_ELT (graph->complex[from], i, c)
1055 /* In complex constraints for node FROM, we may have either
1056 a = *FROM, and *FROM = a, or an offseted constraint which are
1057 always added to the rhs node's constraints. */
1059 if (c->rhs.type == DEREF)
1060 c->rhs.var = to;
1061 else if (c->lhs.type == DEREF)
1062 c->lhs.var = to;
1063 else
1064 c->rhs.var = to;
1067 any_change = constraint_set_union (&graph->complex[to],
1068 &graph->complex[from]);
1069 graph->complex[from].release ();
1070 return any_change;
1074 /* Remove edges involving NODE from GRAPH. */
1076 static void
1077 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1079 if (graph->succs[node])
1080 BITMAP_FREE (graph->succs[node]);
1083 /* Merge GRAPH nodes FROM and TO into node TO. */
1085 static void
1086 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1087 unsigned int from)
1089 if (graph->indirect_cycles[from] != -1)
1091 /* If we have indirect cycles with the from node, and we have
1092 none on the to node, the to node has indirect cycles from the
1093 from node now that they are unified.
1094 If indirect cycles exist on both, unify the nodes that they
1095 are in a cycle with, since we know they are in a cycle with
1096 each other. */
1097 if (graph->indirect_cycles[to] == -1)
1098 graph->indirect_cycles[to] = graph->indirect_cycles[from];
1101 /* Merge all the successor edges. */
1102 if (graph->succs[from])
1104 if (!graph->succs[to])
1105 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1106 bitmap_ior_into (graph->succs[to],
1107 graph->succs[from]);
1110 clear_edges_for_node (graph, from);
1114 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1115 it doesn't exist in the graph already. */
1117 static void
1118 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1119 unsigned int from)
1121 if (to == from)
1122 return;
1124 if (!graph->implicit_preds[to])
1125 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1127 if (bitmap_set_bit (graph->implicit_preds[to], from))
1128 stats.num_implicit_edges++;
1131 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1132 it doesn't exist in the graph already.
1133 Return false if the edge already existed, true otherwise. */
1135 static void
1136 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1137 unsigned int from)
1139 if (!graph->preds[to])
1140 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1141 bitmap_set_bit (graph->preds[to], from);
1144 /* Add a graph edge to GRAPH, going from FROM to TO if
1145 it doesn't exist in the graph already.
1146 Return false if the edge already existed, true otherwise. */
1148 static bool
1149 add_graph_edge (constraint_graph_t graph, unsigned int to,
1150 unsigned int from)
1152 if (to == from)
1154 return false;
1156 else
1158 bool r = false;
1160 if (!graph->succs[from])
1161 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1162 if (bitmap_set_bit (graph->succs[from], to))
1164 r = true;
1165 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1166 stats.num_edges++;
1168 return r;
1173 /* Initialize the constraint graph structure to contain SIZE nodes. */
1175 static void
1176 init_graph (unsigned int size)
1178 unsigned int j;
1180 graph = XCNEW (struct constraint_graph);
1181 graph->size = size;
1182 graph->succs = XCNEWVEC (bitmap, graph->size);
1183 graph->indirect_cycles = XNEWVEC (int, graph->size);
1184 graph->rep = XNEWVEC (unsigned int, graph->size);
1185 /* ??? Macros do not support template types with multiple arguments,
1186 so we use a typedef to work around it. */
1187 typedef vec<constraint_t> vec_constraint_t_heap;
1188 graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
1189 graph->pe = XCNEWVEC (unsigned int, graph->size);
1190 graph->pe_rep = XNEWVEC (int, graph->size);
1192 for (j = 0; j < graph->size; j++)
1194 graph->rep[j] = j;
1195 graph->pe_rep[j] = -1;
1196 graph->indirect_cycles[j] = -1;
1200 /* Build the constraint graph, adding only predecessor edges right now. */
1202 static void
1203 build_pred_graph (void)
1205 int i;
1206 constraint_t c;
1207 unsigned int j;
1209 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1210 graph->preds = XCNEWVEC (bitmap, graph->size);
1211 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1212 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1213 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1214 graph->points_to = XCNEWVEC (bitmap, graph->size);
1215 graph->eq_rep = XNEWVEC (int, graph->size);
1216 graph->direct_nodes = sbitmap_alloc (graph->size);
1217 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1218 bitmap_clear (graph->direct_nodes);
1220 for (j = 1; j < FIRST_REF_NODE; j++)
1222 if (!get_varinfo (j)->is_special_var)
1223 bitmap_set_bit (graph->direct_nodes, j);
1226 for (j = 0; j < graph->size; j++)
1227 graph->eq_rep[j] = -1;
1229 for (j = 0; j < varmap.length (); j++)
1230 graph->indirect_cycles[j] = -1;
1232 FOR_EACH_VEC_ELT (constraints, i, c)
1234 struct constraint_expr lhs = c->lhs;
1235 struct constraint_expr rhs = c->rhs;
1236 unsigned int lhsvar = lhs.var;
1237 unsigned int rhsvar = rhs.var;
1239 if (lhs.type == DEREF)
1241 /* *x = y. */
1242 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1243 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1245 else if (rhs.type == DEREF)
1247 /* x = *y */
1248 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1249 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1250 else
1251 bitmap_clear_bit (graph->direct_nodes, lhsvar);
1253 else if (rhs.type == ADDRESSOF)
1255 varinfo_t v;
1257 /* x = &y */
1258 if (graph->points_to[lhsvar] == NULL)
1259 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1260 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1262 if (graph->pointed_by[rhsvar] == NULL)
1263 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1264 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1266 /* Implicitly, *x = y */
1267 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1269 /* All related variables are no longer direct nodes. */
1270 bitmap_clear_bit (graph->direct_nodes, rhsvar);
1271 v = get_varinfo (rhsvar);
1272 if (!v->is_full_var)
1274 v = get_varinfo (v->head);
1277 bitmap_clear_bit (graph->direct_nodes, v->id);
1278 v = vi_next (v);
1280 while (v != NULL);
1282 bitmap_set_bit (graph->address_taken, rhsvar);
1284 else if (lhsvar > anything_id
1285 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1287 /* x = y */
1288 add_pred_graph_edge (graph, lhsvar, rhsvar);
1289 /* Implicitly, *x = *y */
1290 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1291 FIRST_REF_NODE + rhsvar);
1293 else if (lhs.offset != 0 || rhs.offset != 0)
1295 if (rhs.offset != 0)
1296 bitmap_clear_bit (graph->direct_nodes, lhs.var);
1297 else if (lhs.offset != 0)
1298 bitmap_clear_bit (graph->direct_nodes, rhs.var);
1303 /* Build the constraint graph, adding successor edges. */
1305 static void
1306 build_succ_graph (void)
1308 unsigned i, t;
1309 constraint_t c;
1311 FOR_EACH_VEC_ELT (constraints, i, c)
1313 struct constraint_expr lhs;
1314 struct constraint_expr rhs;
1315 unsigned int lhsvar;
1316 unsigned int rhsvar;
1318 if (!c)
1319 continue;
1321 lhs = c->lhs;
1322 rhs = c->rhs;
1323 lhsvar = find (lhs.var);
1324 rhsvar = find (rhs.var);
1326 if (lhs.type == DEREF)
1328 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1329 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1331 else if (rhs.type == DEREF)
1333 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1334 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1336 else if (rhs.type == ADDRESSOF)
1338 /* x = &y */
1339 gcc_checking_assert (find (rhs.var) == rhs.var);
1340 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1342 else if (lhsvar > anything_id
1343 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1345 add_graph_edge (graph, lhsvar, rhsvar);
1349 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1350 receive pointers. */
1351 t = find (storedanything_id);
1352 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1354 if (!bitmap_bit_p (graph->direct_nodes, i)
1355 && get_varinfo (i)->may_have_pointers)
1356 add_graph_edge (graph, find (i), t);
1359 /* Everything stored to ANYTHING also potentially escapes. */
1360 add_graph_edge (graph, find (escaped_id), t);
1364 /* Changed variables on the last iteration. */
1365 static bitmap changed;
1367 /* Strongly Connected Component visitation info. */
1369 struct scc_info
1371 sbitmap visited;
1372 sbitmap deleted;
1373 unsigned int *dfs;
1374 unsigned int *node_mapping;
1375 int current_index;
1376 vec<unsigned> scc_stack;
1380 /* Recursive routine to find strongly connected components in GRAPH.
1381 SI is the SCC info to store the information in, and N is the id of current
1382 graph node we are processing.
1384 This is Tarjan's strongly connected component finding algorithm, as
1385 modified by Nuutila to keep only non-root nodes on the stack.
1386 The algorithm can be found in "On finding the strongly connected
1387 connected components in a directed graph" by Esko Nuutila and Eljas
1388 Soisalon-Soininen, in Information Processing Letters volume 49,
1389 number 1, pages 9-14. */
1391 static void
1392 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1394 unsigned int i;
1395 bitmap_iterator bi;
1396 unsigned int my_dfs;
1398 bitmap_set_bit (si->visited, n);
1399 si->dfs[n] = si->current_index ++;
1400 my_dfs = si->dfs[n];
1402 /* Visit all the successors. */
1403 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1405 unsigned int w;
1407 if (i > LAST_REF_NODE)
1408 break;
1410 w = find (i);
1411 if (bitmap_bit_p (si->deleted, w))
1412 continue;
1414 if (!bitmap_bit_p (si->visited, w))
1415 scc_visit (graph, si, w);
1417 unsigned int t = find (w);
1418 gcc_checking_assert (find (n) == n);
1419 if (si->dfs[t] < si->dfs[n])
1420 si->dfs[n] = si->dfs[t];
1423 /* See if any components have been identified. */
1424 if (si->dfs[n] == my_dfs)
1426 if (si->scc_stack.length () > 0
1427 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1429 bitmap scc = BITMAP_ALLOC (NULL);
1430 unsigned int lowest_node;
1431 bitmap_iterator bi;
1433 bitmap_set_bit (scc, n);
1435 while (si->scc_stack.length () != 0
1436 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1438 unsigned int w = si->scc_stack.pop ();
1440 bitmap_set_bit (scc, w);
1443 lowest_node = bitmap_first_set_bit (scc);
1444 gcc_assert (lowest_node < FIRST_REF_NODE);
1446 /* Collapse the SCC nodes into a single node, and mark the
1447 indirect cycles. */
1448 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1450 if (i < FIRST_REF_NODE)
1452 if (unite (lowest_node, i))
1453 unify_nodes (graph, lowest_node, i, false);
1455 else
1457 unite (lowest_node, i);
1458 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1462 bitmap_set_bit (si->deleted, n);
1464 else
1465 si->scc_stack.safe_push (n);
1468 /* Unify node FROM into node TO, updating the changed count if
1469 necessary when UPDATE_CHANGED is true. */
1471 static void
1472 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1473 bool update_changed)
1475 gcc_checking_assert (to != from && find (to) == to);
1477 if (dump_file && (dump_flags & TDF_DETAILS))
1478 fprintf (dump_file, "Unifying %s to %s\n",
1479 get_varinfo (from)->name,
1480 get_varinfo (to)->name);
1482 if (update_changed)
1483 stats.unified_vars_dynamic++;
1484 else
1485 stats.unified_vars_static++;
1487 merge_graph_nodes (graph, to, from);
1488 if (merge_node_constraints (graph, to, from))
1490 if (update_changed)
1491 bitmap_set_bit (changed, to);
1494 /* Mark TO as changed if FROM was changed. If TO was already marked
1495 as changed, decrease the changed count. */
1497 if (update_changed
1498 && bitmap_clear_bit (changed, from))
1499 bitmap_set_bit (changed, to);
1500 varinfo_t fromvi = get_varinfo (from);
1501 if (fromvi->solution)
1503 /* If the solution changes because of the merging, we need to mark
1504 the variable as changed. */
1505 varinfo_t tovi = get_varinfo (to);
1506 if (bitmap_ior_into (tovi->solution, fromvi->solution))
1508 if (update_changed)
1509 bitmap_set_bit (changed, to);
1512 BITMAP_FREE (fromvi->solution);
1513 if (fromvi->oldsolution)
1514 BITMAP_FREE (fromvi->oldsolution);
1516 if (stats.iterations > 0
1517 && tovi->oldsolution)
1518 BITMAP_FREE (tovi->oldsolution);
1520 if (graph->succs[to])
1521 bitmap_clear_bit (graph->succs[to], to);
1524 /* Information needed to compute the topological ordering of a graph. */
1526 struct topo_info
1528 /* sbitmap of visited nodes. */
1529 sbitmap visited;
1530 /* Array that stores the topological order of the graph, *in
1531 reverse*. */
1532 vec<unsigned> topo_order;
1536 /* Initialize and return a topological info structure. */
1538 static struct topo_info *
1539 init_topo_info (void)
1541 size_t size = graph->size;
1542 struct topo_info *ti = XNEW (struct topo_info);
1543 ti->visited = sbitmap_alloc (size);
1544 bitmap_clear (ti->visited);
1545 ti->topo_order.create (1);
1546 return ti;
1550 /* Free the topological sort info pointed to by TI. */
1552 static void
1553 free_topo_info (struct topo_info *ti)
1555 sbitmap_free (ti->visited);
1556 ti->topo_order.release ();
1557 free (ti);
1560 /* Visit the graph in topological order, and store the order in the
1561 topo_info structure. */
1563 static void
1564 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1565 unsigned int n)
1567 bitmap_iterator bi;
1568 unsigned int j;
1570 bitmap_set_bit (ti->visited, n);
1572 if (graph->succs[n])
1573 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1575 if (!bitmap_bit_p (ti->visited, j))
1576 topo_visit (graph, ti, j);
1579 ti->topo_order.safe_push (n);
1582 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1583 starting solution for y. */
1585 static void
1586 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1587 bitmap delta, bitmap *expanded_delta)
1589 unsigned int lhs = c->lhs.var;
1590 bool flag = false;
1591 bitmap sol = get_varinfo (lhs)->solution;
1592 unsigned int j;
1593 bitmap_iterator bi;
1594 HOST_WIDE_INT roffset = c->rhs.offset;
1596 /* Our IL does not allow this. */
1597 gcc_checking_assert (c->lhs.offset == 0);
1599 /* If the solution of Y contains anything it is good enough to transfer
1600 this to the LHS. */
1601 if (bitmap_bit_p (delta, anything_id))
1603 flag |= bitmap_set_bit (sol, anything_id);
1604 goto done;
1607 /* If we do not know at with offset the rhs is dereferenced compute
1608 the reachability set of DELTA, conservatively assuming it is
1609 dereferenced at all valid offsets. */
1610 if (roffset == UNKNOWN_OFFSET)
1612 delta = solution_set_expand (delta, expanded_delta);
1613 /* No further offset processing is necessary. */
1614 roffset = 0;
1617 /* For each variable j in delta (Sol(y)), add
1618 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1619 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1621 varinfo_t v = get_varinfo (j);
1622 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1623 unsigned HOST_WIDE_INT size = v->size;
1624 unsigned int t;
1626 if (v->is_full_var)
1628 else if (roffset != 0)
1630 if (fieldoffset < 0)
1631 v = get_varinfo (v->head);
1632 else
1633 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1636 /* We have to include all fields that overlap the current field
1637 shifted by roffset. */
1640 t = find (v->id);
1642 /* Adding edges from the special vars is pointless.
1643 They don't have sets that can change. */
1644 if (get_varinfo (t)->is_special_var)
1645 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1646 /* Merging the solution from ESCAPED needlessly increases
1647 the set. Use ESCAPED as representative instead. */
1648 else if (v->id == escaped_id)
1649 flag |= bitmap_set_bit (sol, escaped_id);
1650 else if (v->may_have_pointers
1651 && add_graph_edge (graph, lhs, t))
1652 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1654 if (v->is_full_var
1655 || v->next == 0)
1656 break;
1658 v = vi_next (v);
1660 while (v->offset < fieldoffset + size);
1663 done:
1664 /* If the LHS solution changed, mark the var as changed. */
1665 if (flag)
1667 get_varinfo (lhs)->solution = sol;
1668 bitmap_set_bit (changed, lhs);
1672 /* Process a constraint C that represents *(x + off) = y using DELTA
1673 as the starting solution for x. */
1675 static void
1676 do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1678 unsigned int rhs = c->rhs.var;
1679 bitmap sol = get_varinfo (rhs)->solution;
1680 unsigned int j;
1681 bitmap_iterator bi;
1682 HOST_WIDE_INT loff = c->lhs.offset;
1683 bool escaped_p = false;
1685 /* Our IL does not allow this. */
1686 gcc_checking_assert (c->rhs.offset == 0);
1688 /* If the solution of y contains ANYTHING simply use the ANYTHING
1689 solution. This avoids needlessly increasing the points-to sets. */
1690 if (bitmap_bit_p (sol, anything_id))
1691 sol = get_varinfo (find (anything_id))->solution;
1693 /* If the solution for x contains ANYTHING we have to merge the
1694 solution of y into all pointer variables which we do via
1695 STOREDANYTHING. */
1696 if (bitmap_bit_p (delta, anything_id))
1698 unsigned t = find (storedanything_id);
1699 if (add_graph_edge (graph, t, rhs))
1701 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1702 bitmap_set_bit (changed, t);
1704 return;
1707 /* If we do not know at with offset the rhs is dereferenced compute
1708 the reachability set of DELTA, conservatively assuming it is
1709 dereferenced at all valid offsets. */
1710 if (loff == UNKNOWN_OFFSET)
1712 delta = solution_set_expand (delta, expanded_delta);
1713 loff = 0;
1716 /* For each member j of delta (Sol(x)), add an edge from y to j and
1717 union Sol(y) into Sol(j) */
1718 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1720 varinfo_t v = get_varinfo (j);
1721 unsigned int t;
1722 HOST_WIDE_INT fieldoffset = v->offset + loff;
1723 unsigned HOST_WIDE_INT size = v->size;
1725 if (v->is_full_var)
1727 else if (loff != 0)
1729 if (fieldoffset < 0)
1730 v = get_varinfo (v->head);
1731 else
1732 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1735 /* We have to include all fields that overlap the current field
1736 shifted by loff. */
1739 if (v->may_have_pointers)
1741 /* If v is a global variable then this is an escape point. */
1742 if (v->is_global_var
1743 && !escaped_p)
1745 t = find (escaped_id);
1746 if (add_graph_edge (graph, t, rhs)
1747 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1748 bitmap_set_bit (changed, t);
1749 /* Enough to let rhs escape once. */
1750 escaped_p = true;
1753 if (v->is_special_var)
1754 break;
1756 t = find (v->id);
1757 if (add_graph_edge (graph, t, rhs)
1758 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1759 bitmap_set_bit (changed, t);
1762 if (v->is_full_var
1763 || v->next == 0)
1764 break;
1766 v = vi_next (v);
1768 while (v->offset < fieldoffset + size);
1772 /* Handle a non-simple (simple meaning requires no iteration),
1773 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1775 static void
1776 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1777 bitmap *expanded_delta)
1779 if (c->lhs.type == DEREF)
1781 if (c->rhs.type == ADDRESSOF)
1783 gcc_unreachable ();
1785 else
1787 /* *x = y */
1788 do_ds_constraint (c, delta, expanded_delta);
1791 else if (c->rhs.type == DEREF)
1793 /* x = *y */
1794 if (!(get_varinfo (c->lhs.var)->is_special_var))
1795 do_sd_constraint (graph, c, delta, expanded_delta);
1797 else
1799 bitmap tmp;
1800 bool flag = false;
1802 gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1803 && c->rhs.offset != 0 && c->lhs.offset == 0);
1804 tmp = get_varinfo (c->lhs.var)->solution;
1806 flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1807 expanded_delta);
1809 if (flag)
1810 bitmap_set_bit (changed, c->lhs.var);
1814 /* Initialize and return a new SCC info structure. */
1816 static struct scc_info *
1817 init_scc_info (size_t size)
1819 struct scc_info *si = XNEW (struct scc_info);
1820 size_t i;
1822 si->current_index = 0;
1823 si->visited = sbitmap_alloc (size);
1824 bitmap_clear (si->visited);
1825 si->deleted = sbitmap_alloc (size);
1826 bitmap_clear (si->deleted);
1827 si->node_mapping = XNEWVEC (unsigned int, size);
1828 si->dfs = XCNEWVEC (unsigned int, size);
1830 for (i = 0; i < size; i++)
1831 si->node_mapping[i] = i;
1833 si->scc_stack.create (1);
1834 return si;
1837 /* Free an SCC info structure pointed to by SI */
1839 static void
1840 free_scc_info (struct scc_info *si)
1842 sbitmap_free (si->visited);
1843 sbitmap_free (si->deleted);
1844 free (si->node_mapping);
1845 free (si->dfs);
1846 si->scc_stack.release ();
1847 free (si);
1851 /* Find indirect cycles in GRAPH that occur, using strongly connected
1852 components, and note them in the indirect cycles map.
1854 This technique comes from Ben Hardekopf and Calvin Lin,
1855 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1856 Lines of Code", submitted to PLDI 2007. */
1858 static void
1859 find_indirect_cycles (constraint_graph_t graph)
1861 unsigned int i;
1862 unsigned int size = graph->size;
1863 struct scc_info *si = init_scc_info (size);
1865 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1866 if (!bitmap_bit_p (si->visited, i) && find (i) == i)
1867 scc_visit (graph, si, i);
1869 free_scc_info (si);
1872 /* Compute a topological ordering for GRAPH, and store the result in the
1873 topo_info structure TI. */
1875 static void
1876 compute_topo_order (constraint_graph_t graph,
1877 struct topo_info *ti)
1879 unsigned int i;
1880 unsigned int size = graph->size;
1882 for (i = 0; i != size; ++i)
1883 if (!bitmap_bit_p (ti->visited, i) && find (i) == i)
1884 topo_visit (graph, ti, i);
1887 /* Structure used to for hash value numbering of pointer equivalence
1888 classes. */
1890 typedef struct equiv_class_label
1892 hashval_t hashcode;
1893 unsigned int equivalence_class;
1894 bitmap labels;
1895 } *equiv_class_label_t;
1896 typedef const struct equiv_class_label *const_equiv_class_label_t;
1898 /* Equiv_class_label hashtable helpers. */
1900 struct equiv_class_hasher : typed_free_remove <equiv_class_label>
1902 typedef equiv_class_label value_type;
1903 typedef equiv_class_label compare_type;
1904 static inline hashval_t hash (const value_type *);
1905 static inline bool equal (const value_type *, const compare_type *);
1908 /* Hash function for a equiv_class_label_t */
1910 inline hashval_t
1911 equiv_class_hasher::hash (const value_type *ecl)
1913 return ecl->hashcode;
1916 /* Equality function for two equiv_class_label_t's. */
1918 inline bool
1919 equiv_class_hasher::equal (const value_type *eql1, const compare_type *eql2)
1921 return (eql1->hashcode == eql2->hashcode
1922 && bitmap_equal_p (eql1->labels, eql2->labels));
1925 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1926 classes. */
1927 static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
1929 /* A hashtable for mapping a bitmap of labels->location equivalence
1930 classes. */
1931 static hash_table<equiv_class_hasher> *location_equiv_class_table;
1933 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1934 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1935 is equivalent to. */
1937 static equiv_class_label *
1938 equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1939 bitmap labels)
1941 equiv_class_label **slot;
1942 equiv_class_label ecl;
1944 ecl.labels = labels;
1945 ecl.hashcode = bitmap_hash (labels);
1946 slot = table->find_slot (&ecl, INSERT);
1947 if (!*slot)
1949 *slot = XNEW (struct equiv_class_label);
1950 (*slot)->labels = labels;
1951 (*slot)->hashcode = ecl.hashcode;
1952 (*slot)->equivalence_class = 0;
1955 return *slot;
1958 /* Perform offline variable substitution.
1960 This is a worst case quadratic time way of identifying variables
1961 that must have equivalent points-to sets, including those caused by
1962 static cycles, and single entry subgraphs, in the constraint graph.
1964 The technique is described in "Exploiting Pointer and Location
1965 Equivalence to Optimize Pointer Analysis. In the 14th International
1966 Static Analysis Symposium (SAS), August 2007." It is known as the
1967 "HU" algorithm, and is equivalent to value numbering the collapsed
1968 constraint graph including evaluating unions.
1970 The general method of finding equivalence classes is as follows:
1971 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1972 Initialize all non-REF nodes to be direct nodes.
1973 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1974 variable}
1975 For each constraint containing the dereference, we also do the same
1976 thing.
1978 We then compute SCC's in the graph and unify nodes in the same SCC,
1979 including pts sets.
1981 For each non-collapsed node x:
1982 Visit all unvisited explicit incoming edges.
1983 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1984 where y->x.
1985 Lookup the equivalence class for pts(x).
1986 If we found one, equivalence_class(x) = found class.
1987 Otherwise, equivalence_class(x) = new class, and new_class is
1988 added to the lookup table.
1990 All direct nodes with the same equivalence class can be replaced
1991 with a single representative node.
1992 All unlabeled nodes (label == 0) are not pointers and all edges
1993 involving them can be eliminated.
1994 We perform these optimizations during rewrite_constraints
1996 In addition to pointer equivalence class finding, we also perform
1997 location equivalence class finding. This is the set of variables
1998 that always appear together in points-to sets. We use this to
1999 compress the size of the points-to sets. */
2001 /* Current maximum pointer equivalence class id. */
2002 static int pointer_equiv_class;
2004 /* Current maximum location equivalence class id. */
2005 static int location_equiv_class;
2007 /* Recursive routine to find strongly connected components in GRAPH,
2008 and label it's nodes with DFS numbers. */
2010 static void
2011 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2013 unsigned int i;
2014 bitmap_iterator bi;
2015 unsigned int my_dfs;
2017 gcc_checking_assert (si->node_mapping[n] == n);
2018 bitmap_set_bit (si->visited, n);
2019 si->dfs[n] = si->current_index ++;
2020 my_dfs = si->dfs[n];
2022 /* Visit all the successors. */
2023 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2025 unsigned int w = si->node_mapping[i];
2027 if (bitmap_bit_p (si->deleted, w))
2028 continue;
2030 if (!bitmap_bit_p (si->visited, w))
2031 condense_visit (graph, si, w);
2033 unsigned int t = si->node_mapping[w];
2034 gcc_checking_assert (si->node_mapping[n] == n);
2035 if (si->dfs[t] < si->dfs[n])
2036 si->dfs[n] = si->dfs[t];
2039 /* Visit all the implicit predecessors. */
2040 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2042 unsigned int w = si->node_mapping[i];
2044 if (bitmap_bit_p (si->deleted, w))
2045 continue;
2047 if (!bitmap_bit_p (si->visited, w))
2048 condense_visit (graph, si, w);
2050 unsigned int t = si->node_mapping[w];
2051 gcc_assert (si->node_mapping[n] == n);
2052 if (si->dfs[t] < si->dfs[n])
2053 si->dfs[n] = si->dfs[t];
2056 /* See if any components have been identified. */
2057 if (si->dfs[n] == my_dfs)
2059 while (si->scc_stack.length () != 0
2060 && si->dfs[si->scc_stack.last ()] >= my_dfs)
2062 unsigned int w = si->scc_stack.pop ();
2063 si->node_mapping[w] = n;
2065 if (!bitmap_bit_p (graph->direct_nodes, w))
2066 bitmap_clear_bit (graph->direct_nodes, n);
2068 /* Unify our nodes. */
2069 if (graph->preds[w])
2071 if (!graph->preds[n])
2072 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2073 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2075 if (graph->implicit_preds[w])
2077 if (!graph->implicit_preds[n])
2078 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2079 bitmap_ior_into (graph->implicit_preds[n],
2080 graph->implicit_preds[w]);
2082 if (graph->points_to[w])
2084 if (!graph->points_to[n])
2085 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2086 bitmap_ior_into (graph->points_to[n],
2087 graph->points_to[w]);
2090 bitmap_set_bit (si->deleted, n);
2092 else
2093 si->scc_stack.safe_push (n);
2096 /* Label pointer equivalences.
2098 This performs a value numbering of the constraint graph to
2099 discover which variables will always have the same points-to sets
2100 under the current set of constraints.
2102 The way it value numbers is to store the set of points-to bits
2103 generated by the constraints and graph edges. This is just used as a
2104 hash and equality comparison. The *actual set of points-to bits* is
2105 completely irrelevant, in that we don't care about being able to
2106 extract them later.
2108 The equality values (currently bitmaps) just have to satisfy a few
2109 constraints, the main ones being:
2110 1. The combining operation must be order independent.
2111 2. The end result of a given set of operations must be unique iff the
2112 combination of input values is unique
2113 3. Hashable. */
2115 static void
2116 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2118 unsigned int i, first_pred;
2119 bitmap_iterator bi;
2121 bitmap_set_bit (si->visited, n);
2123 /* Label and union our incoming edges's points to sets. */
2124 first_pred = -1U;
2125 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2127 unsigned int w = si->node_mapping[i];
2128 if (!bitmap_bit_p (si->visited, w))
2129 label_visit (graph, si, w);
2131 /* Skip unused edges */
2132 if (w == n || graph->pointer_label[w] == 0)
2133 continue;
2135 if (graph->points_to[w])
2137 if (!graph->points_to[n])
2139 if (first_pred == -1U)
2140 first_pred = w;
2141 else
2143 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2144 bitmap_ior (graph->points_to[n],
2145 graph->points_to[first_pred],
2146 graph->points_to[w]);
2149 else
2150 bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
2154 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2155 if (!bitmap_bit_p (graph->direct_nodes, n))
2157 if (!graph->points_to[n])
2159 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2160 if (first_pred != -1U)
2161 bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
2163 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2164 graph->pointer_label[n] = pointer_equiv_class++;
2165 equiv_class_label_t ecl;
2166 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2167 graph->points_to[n]);
2168 ecl->equivalence_class = graph->pointer_label[n];
2169 return;
2172 /* If there was only a single non-empty predecessor the pointer equiv
2173 class is the same. */
2174 if (!graph->points_to[n])
2176 if (first_pred != -1U)
2178 graph->pointer_label[n] = graph->pointer_label[first_pred];
2179 graph->points_to[n] = graph->points_to[first_pred];
2181 return;
2184 if (!bitmap_empty_p (graph->points_to[n]))
2186 equiv_class_label_t ecl;
2187 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2188 graph->points_to[n]);
2189 if (ecl->equivalence_class == 0)
2190 ecl->equivalence_class = pointer_equiv_class++;
2191 else
2193 BITMAP_FREE (graph->points_to[n]);
2194 graph->points_to[n] = ecl->labels;
2196 graph->pointer_label[n] = ecl->equivalence_class;
2200 /* Print the pred graph in dot format. */
2202 static void
2203 dump_pred_graph (struct scc_info *si, FILE *file)
2205 unsigned int i;
2207 /* Only print the graph if it has already been initialized: */
2208 if (!graph)
2209 return;
2211 /* Prints the header of the dot file: */
2212 fprintf (file, "strict digraph {\n");
2213 fprintf (file, " node [\n shape = box\n ]\n");
2214 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
2215 fprintf (file, "\n // List of nodes and complex constraints in "
2216 "the constraint graph:\n");
2218 /* The next lines print the nodes in the graph together with the
2219 complex constraints attached to them. */
2220 for (i = 1; i < graph->size; i++)
2222 if (i == FIRST_REF_NODE)
2223 continue;
2224 if (si->node_mapping[i] != i)
2225 continue;
2226 if (i < FIRST_REF_NODE)
2227 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2228 else
2229 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2230 if (graph->points_to[i]
2231 && !bitmap_empty_p (graph->points_to[i]))
2233 fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
2234 unsigned j;
2235 bitmap_iterator bi;
2236 EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
2237 fprintf (file, " %d", j);
2238 fprintf (file, " }\"]");
2240 fprintf (file, ";\n");
2243 /* Go over the edges. */
2244 fprintf (file, "\n // Edges in the constraint graph:\n");
2245 for (i = 1; i < graph->size; i++)
2247 unsigned j;
2248 bitmap_iterator bi;
2249 if (si->node_mapping[i] != i)
2250 continue;
2251 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
2253 unsigned from = si->node_mapping[j];
2254 if (from < FIRST_REF_NODE)
2255 fprintf (file, "\"%s\"", get_varinfo (from)->name);
2256 else
2257 fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name);
2258 fprintf (file, " -> ");
2259 if (i < FIRST_REF_NODE)
2260 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2261 else
2262 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2263 fprintf (file, ";\n");
2267 /* Prints the tail of the dot file. */
2268 fprintf (file, "}\n");
2271 /* Perform offline variable substitution, discovering equivalence
2272 classes, and eliminating non-pointer variables. */
2274 static struct scc_info *
2275 perform_var_substitution (constraint_graph_t graph)
2277 unsigned int i;
2278 unsigned int size = graph->size;
2279 struct scc_info *si = init_scc_info (size);
2281 bitmap_obstack_initialize (&iteration_obstack);
2282 pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
2283 location_equiv_class_table
2284 = new hash_table<equiv_class_hasher> (511);
2285 pointer_equiv_class = 1;
2286 location_equiv_class = 1;
2288 /* Condense the nodes, which means to find SCC's, count incoming
2289 predecessors, and unite nodes in SCC's. */
2290 for (i = 1; i < FIRST_REF_NODE; i++)
2291 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2292 condense_visit (graph, si, si->node_mapping[i]);
2294 if (dump_file && (dump_flags & TDF_GRAPH))
2296 fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
2297 "in dot format:\n");
2298 dump_pred_graph (si, dump_file);
2299 fprintf (dump_file, "\n\n");
2302 bitmap_clear (si->visited);
2303 /* Actually the label the nodes for pointer equivalences */
2304 for (i = 1; i < FIRST_REF_NODE; i++)
2305 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2306 label_visit (graph, si, si->node_mapping[i]);
2308 /* Calculate location equivalence labels. */
2309 for (i = 1; i < FIRST_REF_NODE; i++)
2311 bitmap pointed_by;
2312 bitmap_iterator bi;
2313 unsigned int j;
2315 if (!graph->pointed_by[i])
2316 continue;
2317 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2319 /* Translate the pointed-by mapping for pointer equivalence
2320 labels. */
2321 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2323 bitmap_set_bit (pointed_by,
2324 graph->pointer_label[si->node_mapping[j]]);
2326 /* The original pointed_by is now dead. */
2327 BITMAP_FREE (graph->pointed_by[i]);
2329 /* Look up the location equivalence label if one exists, or make
2330 one otherwise. */
2331 equiv_class_label_t ecl;
2332 ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
2333 if (ecl->equivalence_class == 0)
2334 ecl->equivalence_class = location_equiv_class++;
2335 else
2337 if (dump_file && (dump_flags & TDF_DETAILS))
2338 fprintf (dump_file, "Found location equivalence for node %s\n",
2339 get_varinfo (i)->name);
2340 BITMAP_FREE (pointed_by);
2342 graph->loc_label[i] = ecl->equivalence_class;
2346 if (dump_file && (dump_flags & TDF_DETAILS))
2347 for (i = 1; i < FIRST_REF_NODE; i++)
2349 unsigned j = si->node_mapping[i];
2350 if (j != i)
2352 fprintf (dump_file, "%s node id %d ",
2353 bitmap_bit_p (graph->direct_nodes, i)
2354 ? "Direct" : "Indirect", i);
2355 if (i < FIRST_REF_NODE)
2356 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2357 else
2358 fprintf (dump_file, "\"*%s\"",
2359 get_varinfo (i - FIRST_REF_NODE)->name);
2360 fprintf (dump_file, " mapped to SCC leader node id %d ", j);
2361 if (j < FIRST_REF_NODE)
2362 fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
2363 else
2364 fprintf (dump_file, "\"*%s\"\n",
2365 get_varinfo (j - FIRST_REF_NODE)->name);
2367 else
2369 fprintf (dump_file,
2370 "Equivalence classes for %s node id %d ",
2371 bitmap_bit_p (graph->direct_nodes, i)
2372 ? "direct" : "indirect", i);
2373 if (i < FIRST_REF_NODE)
2374 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2375 else
2376 fprintf (dump_file, "\"*%s\"",
2377 get_varinfo (i - FIRST_REF_NODE)->name);
2378 fprintf (dump_file,
2379 ": pointer %d, location %d\n",
2380 graph->pointer_label[i], graph->loc_label[i]);
2384 /* Quickly eliminate our non-pointer variables. */
2386 for (i = 1; i < FIRST_REF_NODE; i++)
2388 unsigned int node = si->node_mapping[i];
2390 if (graph->pointer_label[node] == 0)
2392 if (dump_file && (dump_flags & TDF_DETAILS))
2393 fprintf (dump_file,
2394 "%s is a non-pointer variable, eliminating edges.\n",
2395 get_varinfo (node)->name);
2396 stats.nonpointer_vars++;
2397 clear_edges_for_node (graph, node);
2401 return si;
2404 /* Free information that was only necessary for variable
2405 substitution. */
2407 static void
2408 free_var_substitution_info (struct scc_info *si)
2410 free_scc_info (si);
2411 free (graph->pointer_label);
2412 free (graph->loc_label);
2413 free (graph->pointed_by);
2414 free (graph->points_to);
2415 free (graph->eq_rep);
2416 sbitmap_free (graph->direct_nodes);
2417 delete pointer_equiv_class_table;
2418 pointer_equiv_class_table = NULL;
2419 delete location_equiv_class_table;
2420 location_equiv_class_table = NULL;
2421 bitmap_obstack_release (&iteration_obstack);
2424 /* Return an existing node that is equivalent to NODE, which has
2425 equivalence class LABEL, if one exists. Return NODE otherwise. */
2427 static unsigned int
2428 find_equivalent_node (constraint_graph_t graph,
2429 unsigned int node, unsigned int label)
2431 /* If the address version of this variable is unused, we can
2432 substitute it for anything else with the same label.
2433 Otherwise, we know the pointers are equivalent, but not the
2434 locations, and we can unite them later. */
2436 if (!bitmap_bit_p (graph->address_taken, node))
2438 gcc_checking_assert (label < graph->size);
2440 if (graph->eq_rep[label] != -1)
2442 /* Unify the two variables since we know they are equivalent. */
2443 if (unite (graph->eq_rep[label], node))
2444 unify_nodes (graph, graph->eq_rep[label], node, false);
2445 return graph->eq_rep[label];
2447 else
2449 graph->eq_rep[label] = node;
2450 graph->pe_rep[label] = node;
2453 else
2455 gcc_checking_assert (label < graph->size);
2456 graph->pe[node] = label;
2457 if (graph->pe_rep[label] == -1)
2458 graph->pe_rep[label] = node;
2461 return node;
2464 /* Unite pointer equivalent but not location equivalent nodes in
2465 GRAPH. This may only be performed once variable substitution is
2466 finished. */
2468 static void
2469 unite_pointer_equivalences (constraint_graph_t graph)
2471 unsigned int i;
2473 /* Go through the pointer equivalences and unite them to their
2474 representative, if they aren't already. */
2475 for (i = 1; i < FIRST_REF_NODE; i++)
2477 unsigned int label = graph->pe[i];
2478 if (label)
2480 int label_rep = graph->pe_rep[label];
2482 if (label_rep == -1)
2483 continue;
2485 label_rep = find (label_rep);
2486 if (label_rep >= 0 && unite (label_rep, find (i)))
2487 unify_nodes (graph, label_rep, i, false);
2492 /* Move complex constraints to the GRAPH nodes they belong to. */
2494 static void
2495 move_complex_constraints (constraint_graph_t graph)
2497 int i;
2498 constraint_t c;
2500 FOR_EACH_VEC_ELT (constraints, i, c)
2502 if (c)
2504 struct constraint_expr lhs = c->lhs;
2505 struct constraint_expr rhs = c->rhs;
2507 if (lhs.type == DEREF)
2509 insert_into_complex (graph, lhs.var, c);
2511 else if (rhs.type == DEREF)
2513 if (!(get_varinfo (lhs.var)->is_special_var))
2514 insert_into_complex (graph, rhs.var, c);
2516 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2517 && (lhs.offset != 0 || rhs.offset != 0))
2519 insert_into_complex (graph, rhs.var, c);
2526 /* Optimize and rewrite complex constraints while performing
2527 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2528 result of perform_variable_substitution. */
2530 static void
2531 rewrite_constraints (constraint_graph_t graph,
2532 struct scc_info *si)
2534 int i;
2535 constraint_t c;
2537 #ifdef ENABLE_CHECKING
2538 for (unsigned int j = 0; j < graph->size; j++)
2539 gcc_assert (find (j) == j);
2540 #endif
2542 FOR_EACH_VEC_ELT (constraints, i, c)
2544 struct constraint_expr lhs = c->lhs;
2545 struct constraint_expr rhs = c->rhs;
2546 unsigned int lhsvar = find (lhs.var);
2547 unsigned int rhsvar = find (rhs.var);
2548 unsigned int lhsnode, rhsnode;
2549 unsigned int lhslabel, rhslabel;
2551 lhsnode = si->node_mapping[lhsvar];
2552 rhsnode = si->node_mapping[rhsvar];
2553 lhslabel = graph->pointer_label[lhsnode];
2554 rhslabel = graph->pointer_label[rhsnode];
2556 /* See if it is really a non-pointer variable, and if so, ignore
2557 the constraint. */
2558 if (lhslabel == 0)
2560 if (dump_file && (dump_flags & TDF_DETAILS))
2563 fprintf (dump_file, "%s is a non-pointer variable,"
2564 "ignoring constraint:",
2565 get_varinfo (lhs.var)->name);
2566 dump_constraint (dump_file, c);
2567 fprintf (dump_file, "\n");
2569 constraints[i] = NULL;
2570 continue;
2573 if (rhslabel == 0)
2575 if (dump_file && (dump_flags & TDF_DETAILS))
2578 fprintf (dump_file, "%s is a non-pointer variable,"
2579 "ignoring constraint:",
2580 get_varinfo (rhs.var)->name);
2581 dump_constraint (dump_file, c);
2582 fprintf (dump_file, "\n");
2584 constraints[i] = NULL;
2585 continue;
2588 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2589 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2590 c->lhs.var = lhsvar;
2591 c->rhs.var = rhsvar;
2595 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2596 part of an SCC, false otherwise. */
2598 static bool
2599 eliminate_indirect_cycles (unsigned int node)
2601 if (graph->indirect_cycles[node] != -1
2602 && !bitmap_empty_p (get_varinfo (node)->solution))
2604 unsigned int i;
2605 auto_vec<unsigned> queue;
2606 int queuepos;
2607 unsigned int to = find (graph->indirect_cycles[node]);
2608 bitmap_iterator bi;
2610 /* We can't touch the solution set and call unify_nodes
2611 at the same time, because unify_nodes is going to do
2612 bitmap unions into it. */
2614 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2616 if (find (i) == i && i != to)
2618 if (unite (to, i))
2619 queue.safe_push (i);
2623 for (queuepos = 0;
2624 queue.iterate (queuepos, &i);
2625 queuepos++)
2627 unify_nodes (graph, to, i, true);
2629 return true;
2631 return false;
2634 /* Solve the constraint graph GRAPH using our worklist solver.
2635 This is based on the PW* family of solvers from the "Efficient Field
2636 Sensitive Pointer Analysis for C" paper.
2637 It works by iterating over all the graph nodes, processing the complex
2638 constraints and propagating the copy constraints, until everything stops
2639 changed. This corresponds to steps 6-8 in the solving list given above. */
2641 static void
2642 solve_graph (constraint_graph_t graph)
2644 unsigned int size = graph->size;
2645 unsigned int i;
2646 bitmap pts;
2648 changed = BITMAP_ALLOC (NULL);
2650 /* Mark all initial non-collapsed nodes as changed. */
2651 for (i = 1; i < size; i++)
2653 varinfo_t ivi = get_varinfo (i);
2654 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2655 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2656 || graph->complex[i].length () > 0))
2657 bitmap_set_bit (changed, i);
2660 /* Allocate a bitmap to be used to store the changed bits. */
2661 pts = BITMAP_ALLOC (&pta_obstack);
2663 while (!bitmap_empty_p (changed))
2665 unsigned int i;
2666 struct topo_info *ti = init_topo_info ();
2667 stats.iterations++;
2669 bitmap_obstack_initialize (&iteration_obstack);
2671 compute_topo_order (graph, ti);
2673 while (ti->topo_order.length () != 0)
2676 i = ti->topo_order.pop ();
2678 /* If this variable is not a representative, skip it. */
2679 if (find (i) != i)
2680 continue;
2682 /* In certain indirect cycle cases, we may merge this
2683 variable to another. */
2684 if (eliminate_indirect_cycles (i) && find (i) != i)
2685 continue;
2687 /* If the node has changed, we need to process the
2688 complex constraints and outgoing edges again. */
2689 if (bitmap_clear_bit (changed, i))
2691 unsigned int j;
2692 constraint_t c;
2693 bitmap solution;
2694 vec<constraint_t> complex = graph->complex[i];
2695 varinfo_t vi = get_varinfo (i);
2696 bool solution_empty;
2698 /* Compute the changed set of solution bits. If anything
2699 is in the solution just propagate that. */
2700 if (bitmap_bit_p (vi->solution, anything_id))
2702 /* If anything is also in the old solution there is
2703 nothing to do.
2704 ??? But we shouldn't ended up with "changed" set ... */
2705 if (vi->oldsolution
2706 && bitmap_bit_p (vi->oldsolution, anything_id))
2707 continue;
2708 bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2710 else if (vi->oldsolution)
2711 bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2712 else
2713 bitmap_copy (pts, vi->solution);
2715 if (bitmap_empty_p (pts))
2716 continue;
2718 if (vi->oldsolution)
2719 bitmap_ior_into (vi->oldsolution, pts);
2720 else
2722 vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2723 bitmap_copy (vi->oldsolution, pts);
2726 solution = vi->solution;
2727 solution_empty = bitmap_empty_p (solution);
2729 /* Process the complex constraints */
2730 bitmap expanded_pts = NULL;
2731 FOR_EACH_VEC_ELT (complex, j, c)
2733 /* XXX: This is going to unsort the constraints in
2734 some cases, which will occasionally add duplicate
2735 constraints during unification. This does not
2736 affect correctness. */
2737 c->lhs.var = find (c->lhs.var);
2738 c->rhs.var = find (c->rhs.var);
2740 /* The only complex constraint that can change our
2741 solution to non-empty, given an empty solution,
2742 is a constraint where the lhs side is receiving
2743 some set from elsewhere. */
2744 if (!solution_empty || c->lhs.type != DEREF)
2745 do_complex_constraint (graph, c, pts, &expanded_pts);
2747 BITMAP_FREE (expanded_pts);
2749 solution_empty = bitmap_empty_p (solution);
2751 if (!solution_empty)
2753 bitmap_iterator bi;
2754 unsigned eff_escaped_id = find (escaped_id);
2756 /* Propagate solution to all successors. */
2757 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2758 0, j, bi)
2760 bitmap tmp;
2761 bool flag;
2763 unsigned int to = find (j);
2764 tmp = get_varinfo (to)->solution;
2765 flag = false;
2767 /* Don't try to propagate to ourselves. */
2768 if (to == i)
2769 continue;
2771 /* If we propagate from ESCAPED use ESCAPED as
2772 placeholder. */
2773 if (i == eff_escaped_id)
2774 flag = bitmap_set_bit (tmp, escaped_id);
2775 else
2776 flag = bitmap_ior_into (tmp, pts);
2778 if (flag)
2779 bitmap_set_bit (changed, to);
2784 free_topo_info (ti);
2785 bitmap_obstack_release (&iteration_obstack);
2788 BITMAP_FREE (pts);
2789 BITMAP_FREE (changed);
2790 bitmap_obstack_release (&oldpta_obstack);
2793 /* Map from trees to variable infos. */
2794 static hash_map<tree, varinfo_t> *vi_for_tree;
2797 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2799 static void
2800 insert_vi_for_tree (tree t, varinfo_t vi)
2802 gcc_assert (vi);
2803 gcc_assert (!vi_for_tree->put (t, vi));
2806 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2807 exist in the map, return NULL, otherwise, return the varinfo we found. */
2809 static varinfo_t
2810 lookup_vi_for_tree (tree t)
2812 varinfo_t *slot = vi_for_tree->get (t);
2813 if (slot == NULL)
2814 return NULL;
2816 return *slot;
2819 /* Return a printable name for DECL */
2821 static const char *
2822 alias_get_name (tree decl)
2824 const char *res = NULL;
2825 char *temp;
2826 int num_printed = 0;
2828 if (!dump_file)
2829 return "NULL";
2831 if (TREE_CODE (decl) == SSA_NAME)
2833 res = get_name (decl);
2834 if (res)
2835 num_printed = asprintf (&temp, "%s_%u", res, SSA_NAME_VERSION (decl));
2836 else
2837 num_printed = asprintf (&temp, "_%u", SSA_NAME_VERSION (decl));
2838 if (num_printed > 0)
2840 res = ggc_strdup (temp);
2841 free (temp);
2844 else if (DECL_P (decl))
2846 if (DECL_ASSEMBLER_NAME_SET_P (decl))
2847 res = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
2848 else
2850 res = get_name (decl);
2851 if (!res)
2853 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2854 if (num_printed > 0)
2856 res = ggc_strdup (temp);
2857 free (temp);
2862 if (res != NULL)
2863 return res;
2865 return "NULL";
2868 /* Find the variable id for tree T in the map.
2869 If T doesn't exist in the map, create an entry for it and return it. */
2871 static varinfo_t
2872 get_vi_for_tree (tree t)
2874 varinfo_t *slot = vi_for_tree->get (t);
2875 if (slot == NULL)
2876 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2878 return *slot;
2881 /* Get a scalar constraint expression for a new temporary variable. */
2883 static struct constraint_expr
2884 new_scalar_tmp_constraint_exp (const char *name)
2886 struct constraint_expr tmp;
2887 varinfo_t vi;
2889 vi = new_var_info (NULL_TREE, name);
2890 vi->offset = 0;
2891 vi->size = -1;
2892 vi->fullsize = -1;
2893 vi->is_full_var = 1;
2895 tmp.var = vi->id;
2896 tmp.type = SCALAR;
2897 tmp.offset = 0;
2899 return tmp;
2902 /* Get a constraint expression vector from an SSA_VAR_P node.
2903 If address_p is true, the result will be taken its address of. */
2905 static void
2906 get_constraint_for_ssa_var (tree t, vec<ce_s> *results, bool address_p)
2908 struct constraint_expr cexpr;
2909 varinfo_t vi;
2911 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2912 gcc_assert (TREE_CODE (t) == SSA_NAME || DECL_P (t));
2914 /* For parameters, get at the points-to set for the actual parm
2915 decl. */
2916 if (TREE_CODE (t) == SSA_NAME
2917 && SSA_NAME_IS_DEFAULT_DEF (t)
2918 && (TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2919 || TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL))
2921 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2922 return;
2925 /* For global variables resort to the alias target. */
2926 if (TREE_CODE (t) == VAR_DECL
2927 && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
2929 varpool_node *node = varpool_node::get (t);
2930 if (node && node->alias && node->analyzed)
2932 node = node->ultimate_alias_target ();
2933 t = node->decl;
2937 vi = get_vi_for_tree (t);
2938 cexpr.var = vi->id;
2939 cexpr.type = SCALAR;
2940 cexpr.offset = 0;
2942 /* If we are not taking the address of the constraint expr, add all
2943 sub-fiels of the variable as well. */
2944 if (!address_p
2945 && !vi->is_full_var)
2947 for (; vi; vi = vi_next (vi))
2949 cexpr.var = vi->id;
2950 results->safe_push (cexpr);
2952 return;
2955 results->safe_push (cexpr);
2958 /* Process constraint T, performing various simplifications and then
2959 adding it to our list of overall constraints. */
2961 static void
2962 process_constraint (constraint_t t)
2964 struct constraint_expr rhs = t->rhs;
2965 struct constraint_expr lhs = t->lhs;
2967 gcc_assert (rhs.var < varmap.length ());
2968 gcc_assert (lhs.var < varmap.length ());
2970 /* If we didn't get any useful constraint from the lhs we get
2971 &ANYTHING as fallback from get_constraint_for. Deal with
2972 it here by turning it into *ANYTHING. */
2973 if (lhs.type == ADDRESSOF
2974 && lhs.var == anything_id)
2975 lhs.type = DEREF;
2977 /* ADDRESSOF on the lhs is invalid. */
2978 gcc_assert (lhs.type != ADDRESSOF);
2980 /* We shouldn't add constraints from things that cannot have pointers.
2981 It's not completely trivial to avoid in the callers, so do it here. */
2982 if (rhs.type != ADDRESSOF
2983 && !get_varinfo (rhs.var)->may_have_pointers)
2984 return;
2986 /* Likewise adding to the solution of a non-pointer var isn't useful. */
2987 if (!get_varinfo (lhs.var)->may_have_pointers)
2988 return;
2990 /* This can happen in our IR with things like n->a = *p */
2991 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2993 /* Split into tmp = *rhs, *lhs = tmp */
2994 struct constraint_expr tmplhs;
2995 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
2996 process_constraint (new_constraint (tmplhs, rhs));
2997 process_constraint (new_constraint (lhs, tmplhs));
2999 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
3001 /* Split into tmp = &rhs, *lhs = tmp */
3002 struct constraint_expr tmplhs;
3003 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
3004 process_constraint (new_constraint (tmplhs, rhs));
3005 process_constraint (new_constraint (lhs, tmplhs));
3007 else
3009 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
3010 constraints.safe_push (t);
3015 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3016 structure. */
3018 static HOST_WIDE_INT
3019 bitpos_of_field (const tree fdecl)
3021 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl))
3022 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl)))
3023 return -1;
3025 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT
3026 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl)));
3030 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3031 resulting constraint expressions in *RESULTS. */
3033 static void
3034 get_constraint_for_ptr_offset (tree ptr, tree offset,
3035 vec<ce_s> *results)
3037 struct constraint_expr c;
3038 unsigned int j, n;
3039 HOST_WIDE_INT rhsoffset;
3041 /* If we do not do field-sensitive PTA adding offsets to pointers
3042 does not change the points-to solution. */
3043 if (!use_field_sensitive)
3045 get_constraint_for_rhs (ptr, results);
3046 return;
3049 /* If the offset is not a non-negative integer constant that fits
3050 in a HOST_WIDE_INT, we have to fall back to a conservative
3051 solution which includes all sub-fields of all pointed-to
3052 variables of ptr. */
3053 if (offset == NULL_TREE
3054 || TREE_CODE (offset) != INTEGER_CST)
3055 rhsoffset = UNKNOWN_OFFSET;
3056 else
3058 /* Sign-extend the offset. */
3059 offset_int soffset = offset_int::from (offset, SIGNED);
3060 if (!wi::fits_shwi_p (soffset))
3061 rhsoffset = UNKNOWN_OFFSET;
3062 else
3064 /* Make sure the bit-offset also fits. */
3065 HOST_WIDE_INT rhsunitoffset = soffset.to_shwi ();
3066 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
3067 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
3068 rhsoffset = UNKNOWN_OFFSET;
3072 get_constraint_for_rhs (ptr, results);
3073 if (rhsoffset == 0)
3074 return;
3076 /* As we are eventually appending to the solution do not use
3077 vec::iterate here. */
3078 n = results->length ();
3079 for (j = 0; j < n; j++)
3081 varinfo_t curr;
3082 c = (*results)[j];
3083 curr = get_varinfo (c.var);
3085 if (c.type == ADDRESSOF
3086 /* If this varinfo represents a full variable just use it. */
3087 && curr->is_full_var)
3089 else if (c.type == ADDRESSOF
3090 /* If we do not know the offset add all subfields. */
3091 && rhsoffset == UNKNOWN_OFFSET)
3093 varinfo_t temp = get_varinfo (curr->head);
3096 struct constraint_expr c2;
3097 c2.var = temp->id;
3098 c2.type = ADDRESSOF;
3099 c2.offset = 0;
3100 if (c2.var != c.var)
3101 results->safe_push (c2);
3102 temp = vi_next (temp);
3104 while (temp);
3106 else if (c.type == ADDRESSOF)
3108 varinfo_t temp;
3109 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
3111 /* If curr->offset + rhsoffset is less than zero adjust it. */
3112 if (rhsoffset < 0
3113 && curr->offset < offset)
3114 offset = 0;
3116 /* We have to include all fields that overlap the current
3117 field shifted by rhsoffset. And we include at least
3118 the last or the first field of the variable to represent
3119 reachability of off-bound addresses, in particular &object + 1,
3120 conservatively correct. */
3121 temp = first_or_preceding_vi_for_offset (curr, offset);
3122 c.var = temp->id;
3123 c.offset = 0;
3124 temp = vi_next (temp);
3125 while (temp
3126 && temp->offset < offset + curr->size)
3128 struct constraint_expr c2;
3129 c2.var = temp->id;
3130 c2.type = ADDRESSOF;
3131 c2.offset = 0;
3132 results->safe_push (c2);
3133 temp = vi_next (temp);
3136 else if (c.type == SCALAR)
3138 gcc_assert (c.offset == 0);
3139 c.offset = rhsoffset;
3141 else
3142 /* We shouldn't get any DEREFs here. */
3143 gcc_unreachable ();
3145 (*results)[j] = c;
3150 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3151 If address_p is true the result will be taken its address of.
3152 If lhs_p is true then the constraint expression is assumed to be used
3153 as the lhs. */
3155 static void
3156 get_constraint_for_component_ref (tree t, vec<ce_s> *results,
3157 bool address_p, bool lhs_p)
3159 tree orig_t = t;
3160 HOST_WIDE_INT bitsize = -1;
3161 HOST_WIDE_INT bitmaxsize = -1;
3162 HOST_WIDE_INT bitpos;
3163 tree forzero;
3165 /* Some people like to do cute things like take the address of
3166 &0->a.b */
3167 forzero = t;
3168 while (handled_component_p (forzero)
3169 || INDIRECT_REF_P (forzero)
3170 || TREE_CODE (forzero) == MEM_REF)
3171 forzero = TREE_OPERAND (forzero, 0);
3173 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3175 struct constraint_expr temp;
3177 temp.offset = 0;
3178 temp.var = integer_id;
3179 temp.type = SCALAR;
3180 results->safe_push (temp);
3181 return;
3184 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
3186 /* Pretend to take the address of the base, we'll take care of
3187 adding the required subset of sub-fields below. */
3188 get_constraint_for_1 (t, results, true, lhs_p);
3189 gcc_assert (results->length () == 1);
3190 struct constraint_expr &result = results->last ();
3192 if (result.type == SCALAR
3193 && get_varinfo (result.var)->is_full_var)
3194 /* For single-field vars do not bother about the offset. */
3195 result.offset = 0;
3196 else if (result.type == SCALAR)
3198 /* In languages like C, you can access one past the end of an
3199 array. You aren't allowed to dereference it, so we can
3200 ignore this constraint. When we handle pointer subtraction,
3201 we may have to do something cute here. */
3203 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result.var)->fullsize
3204 && bitmaxsize != 0)
3206 /* It's also not true that the constraint will actually start at the
3207 right offset, it may start in some padding. We only care about
3208 setting the constraint to the first actual field it touches, so
3209 walk to find it. */
3210 struct constraint_expr cexpr = result;
3211 varinfo_t curr;
3212 results->pop ();
3213 cexpr.offset = 0;
3214 for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr))
3216 if (ranges_overlap_p (curr->offset, curr->size,
3217 bitpos, bitmaxsize))
3219 cexpr.var = curr->id;
3220 results->safe_push (cexpr);
3221 if (address_p)
3222 break;
3225 /* If we are going to take the address of this field then
3226 to be able to compute reachability correctly add at least
3227 the last field of the variable. */
3228 if (address_p && results->length () == 0)
3230 curr = get_varinfo (cexpr.var);
3231 while (curr->next != 0)
3232 curr = vi_next (curr);
3233 cexpr.var = curr->id;
3234 results->safe_push (cexpr);
3236 else if (results->length () == 0)
3237 /* Assert that we found *some* field there. The user couldn't be
3238 accessing *only* padding. */
3239 /* Still the user could access one past the end of an array
3240 embedded in a struct resulting in accessing *only* padding. */
3241 /* Or accessing only padding via type-punning to a type
3242 that has a filed just in padding space. */
3244 cexpr.type = SCALAR;
3245 cexpr.var = anything_id;
3246 cexpr.offset = 0;
3247 results->safe_push (cexpr);
3250 else if (bitmaxsize == 0)
3252 if (dump_file && (dump_flags & TDF_DETAILS))
3253 fprintf (dump_file, "Access to zero-sized part of variable,"
3254 "ignoring\n");
3256 else
3257 if (dump_file && (dump_flags & TDF_DETAILS))
3258 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3260 else if (result.type == DEREF)
3262 /* If we do not know exactly where the access goes say so. Note
3263 that only for non-structure accesses we know that we access
3264 at most one subfiled of any variable. */
3265 if (bitpos == -1
3266 || bitsize != bitmaxsize
3267 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t))
3268 || result.offset == UNKNOWN_OFFSET)
3269 result.offset = UNKNOWN_OFFSET;
3270 else
3271 result.offset += bitpos;
3273 else if (result.type == ADDRESSOF)
3275 /* We can end up here for component references on a
3276 VIEW_CONVERT_EXPR <>(&foobar). */
3277 result.type = SCALAR;
3278 result.var = anything_id;
3279 result.offset = 0;
3281 else
3282 gcc_unreachable ();
3286 /* Dereference the constraint expression CONS, and return the result.
3287 DEREF (ADDRESSOF) = SCALAR
3288 DEREF (SCALAR) = DEREF
3289 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3290 This is needed so that we can handle dereferencing DEREF constraints. */
3292 static void
3293 do_deref (vec<ce_s> *constraints)
3295 struct constraint_expr *c;
3296 unsigned int i = 0;
3298 FOR_EACH_VEC_ELT (*constraints, i, c)
3300 if (c->type == SCALAR)
3301 c->type = DEREF;
3302 else if (c->type == ADDRESSOF)
3303 c->type = SCALAR;
3304 else if (c->type == DEREF)
3306 struct constraint_expr tmplhs;
3307 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3308 process_constraint (new_constraint (tmplhs, *c));
3309 c->var = tmplhs.var;
3311 else
3312 gcc_unreachable ();
3316 /* Given a tree T, return the constraint expression for taking the
3317 address of it. */
3319 static void
3320 get_constraint_for_address_of (tree t, vec<ce_s> *results)
3322 struct constraint_expr *c;
3323 unsigned int i;
3325 get_constraint_for_1 (t, results, true, true);
3327 FOR_EACH_VEC_ELT (*results, i, c)
3329 if (c->type == DEREF)
3330 c->type = SCALAR;
3331 else
3332 c->type = ADDRESSOF;
3336 /* Given a tree T, return the constraint expression for it. */
3338 static void
3339 get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p,
3340 bool lhs_p)
3342 struct constraint_expr temp;
3344 /* x = integer is all glommed to a single variable, which doesn't
3345 point to anything by itself. That is, of course, unless it is an
3346 integer constant being treated as a pointer, in which case, we
3347 will return that this is really the addressof anything. This
3348 happens below, since it will fall into the default case. The only
3349 case we know something about an integer treated like a pointer is
3350 when it is the NULL pointer, and then we just say it points to
3351 NULL.
3353 Do not do that if -fno-delete-null-pointer-checks though, because
3354 in that case *NULL does not fail, so it _should_ alias *anything.
3355 It is not worth adding a new option or renaming the existing one,
3356 since this case is relatively obscure. */
3357 if ((TREE_CODE (t) == INTEGER_CST
3358 && integer_zerop (t))
3359 /* The only valid CONSTRUCTORs in gimple with pointer typed
3360 elements are zero-initializer. But in IPA mode we also
3361 process global initializers, so verify at least. */
3362 || (TREE_CODE (t) == CONSTRUCTOR
3363 && CONSTRUCTOR_NELTS (t) == 0))
3365 if (flag_delete_null_pointer_checks)
3366 temp.var = nothing_id;
3367 else
3368 temp.var = nonlocal_id;
3369 temp.type = ADDRESSOF;
3370 temp.offset = 0;
3371 results->safe_push (temp);
3372 return;
3375 /* String constants are read-only, ideally we'd have a CONST_DECL
3376 for those. */
3377 if (TREE_CODE (t) == STRING_CST)
3379 temp.var = string_id;
3380 temp.type = SCALAR;
3381 temp.offset = 0;
3382 results->safe_push (temp);
3383 return;
3386 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3388 case tcc_expression:
3390 switch (TREE_CODE (t))
3392 case ADDR_EXPR:
3393 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3394 return;
3395 default:;
3397 break;
3399 case tcc_reference:
3401 switch (TREE_CODE (t))
3403 case MEM_REF:
3405 struct constraint_expr cs;
3406 varinfo_t vi, curr;
3407 get_constraint_for_ptr_offset (TREE_OPERAND (t, 0),
3408 TREE_OPERAND (t, 1), results);
3409 do_deref (results);
3411 /* If we are not taking the address then make sure to process
3412 all subvariables we might access. */
3413 if (address_p)
3414 return;
3416 cs = results->last ();
3417 if (cs.type == DEREF
3418 && type_can_have_subvars (TREE_TYPE (t)))
3420 /* For dereferences this means we have to defer it
3421 to solving time. */
3422 results->last ().offset = UNKNOWN_OFFSET;
3423 return;
3425 if (cs.type != SCALAR)
3426 return;
3428 vi = get_varinfo (cs.var);
3429 curr = vi_next (vi);
3430 if (!vi->is_full_var
3431 && curr)
3433 unsigned HOST_WIDE_INT size;
3434 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t))))
3435 size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t)));
3436 else
3437 size = -1;
3438 for (; curr; curr = vi_next (curr))
3440 if (curr->offset - vi->offset < size)
3442 cs.var = curr->id;
3443 results->safe_push (cs);
3445 else
3446 break;
3449 return;
3451 case ARRAY_REF:
3452 case ARRAY_RANGE_REF:
3453 case COMPONENT_REF:
3454 get_constraint_for_component_ref (t, results, address_p, lhs_p);
3455 return;
3456 case VIEW_CONVERT_EXPR:
3457 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p,
3458 lhs_p);
3459 return;
3460 /* We are missing handling for TARGET_MEM_REF here. */
3461 default:;
3463 break;
3465 case tcc_exceptional:
3467 switch (TREE_CODE (t))
3469 case SSA_NAME:
3471 get_constraint_for_ssa_var (t, results, address_p);
3472 return;
3474 case CONSTRUCTOR:
3476 unsigned int i;
3477 tree val;
3478 auto_vec<ce_s> tmp;
3479 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val)
3481 struct constraint_expr *rhsp;
3482 unsigned j;
3483 get_constraint_for_1 (val, &tmp, address_p, lhs_p);
3484 FOR_EACH_VEC_ELT (tmp, j, rhsp)
3485 results->safe_push (*rhsp);
3486 tmp.truncate (0);
3488 /* We do not know whether the constructor was complete,
3489 so technically we have to add &NOTHING or &ANYTHING
3490 like we do for an empty constructor as well. */
3491 return;
3493 default:;
3495 break;
3497 case tcc_declaration:
3499 get_constraint_for_ssa_var (t, results, address_p);
3500 return;
3502 case tcc_constant:
3504 /* We cannot refer to automatic variables through constants. */
3505 temp.type = ADDRESSOF;
3506 temp.var = nonlocal_id;
3507 temp.offset = 0;
3508 results->safe_push (temp);
3509 return;
3511 default:;
3514 /* The default fallback is a constraint from anything. */
3515 temp.type = ADDRESSOF;
3516 temp.var = anything_id;
3517 temp.offset = 0;
3518 results->safe_push (temp);
3521 /* Given a gimple tree T, return the constraint expression vector for it. */
3523 static void
3524 get_constraint_for (tree t, vec<ce_s> *results)
3526 gcc_assert (results->length () == 0);
3528 get_constraint_for_1 (t, results, false, true);
3531 /* Given a gimple tree T, return the constraint expression vector for it
3532 to be used as the rhs of a constraint. */
3534 static void
3535 get_constraint_for_rhs (tree t, vec<ce_s> *results)
3537 gcc_assert (results->length () == 0);
3539 get_constraint_for_1 (t, results, false, false);
3543 /* Efficiently generates constraints from all entries in *RHSC to all
3544 entries in *LHSC. */
3546 static void
3547 process_all_all_constraints (vec<ce_s> lhsc,
3548 vec<ce_s> rhsc)
3550 struct constraint_expr *lhsp, *rhsp;
3551 unsigned i, j;
3553 if (lhsc.length () <= 1 || rhsc.length () <= 1)
3555 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3556 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
3557 process_constraint (new_constraint (*lhsp, *rhsp));
3559 else
3561 struct constraint_expr tmp;
3562 tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3563 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
3564 process_constraint (new_constraint (tmp, *rhsp));
3565 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3566 process_constraint (new_constraint (*lhsp, tmp));
3570 /* Handle aggregate copies by expanding into copies of the respective
3571 fields of the structures. */
3573 static void
3574 do_structure_copy (tree lhsop, tree rhsop)
3576 struct constraint_expr *lhsp, *rhsp;
3577 auto_vec<ce_s> lhsc;
3578 auto_vec<ce_s> rhsc;
3579 unsigned j;
3581 get_constraint_for (lhsop, &lhsc);
3582 get_constraint_for_rhs (rhsop, &rhsc);
3583 lhsp = &lhsc[0];
3584 rhsp = &rhsc[0];
3585 if (lhsp->type == DEREF
3586 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3587 || rhsp->type == DEREF)
3589 if (lhsp->type == DEREF)
3591 gcc_assert (lhsc.length () == 1);
3592 lhsp->offset = UNKNOWN_OFFSET;
3594 if (rhsp->type == DEREF)
3596 gcc_assert (rhsc.length () == 1);
3597 rhsp->offset = UNKNOWN_OFFSET;
3599 process_all_all_constraints (lhsc, rhsc);
3601 else if (lhsp->type == SCALAR
3602 && (rhsp->type == SCALAR
3603 || rhsp->type == ADDRESSOF))
3605 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3606 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3607 unsigned k = 0;
3608 get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize);
3609 get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize);
3610 for (j = 0; lhsc.iterate (j, &lhsp);)
3612 varinfo_t lhsv, rhsv;
3613 rhsp = &rhsc[k];
3614 lhsv = get_varinfo (lhsp->var);
3615 rhsv = get_varinfo (rhsp->var);
3616 if (lhsv->may_have_pointers
3617 && (lhsv->is_full_var
3618 || rhsv->is_full_var
3619 || ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3620 rhsv->offset + lhsoffset, rhsv->size)))
3621 process_constraint (new_constraint (*lhsp, *rhsp));
3622 if (!rhsv->is_full_var
3623 && (lhsv->is_full_var
3624 || (lhsv->offset + rhsoffset + lhsv->size
3625 > rhsv->offset + lhsoffset + rhsv->size)))
3627 ++k;
3628 if (k >= rhsc.length ())
3629 break;
3631 else
3632 ++j;
3635 else
3636 gcc_unreachable ();
3639 /* Create constraints ID = { rhsc }. */
3641 static void
3642 make_constraints_to (unsigned id, vec<ce_s> rhsc)
3644 struct constraint_expr *c;
3645 struct constraint_expr includes;
3646 unsigned int j;
3648 includes.var = id;
3649 includes.offset = 0;
3650 includes.type = SCALAR;
3652 FOR_EACH_VEC_ELT (rhsc, j, c)
3653 process_constraint (new_constraint (includes, *c));
3656 /* Create a constraint ID = OP. */
3658 static void
3659 make_constraint_to (unsigned id, tree op)
3661 auto_vec<ce_s> rhsc;
3662 get_constraint_for_rhs (op, &rhsc);
3663 make_constraints_to (id, rhsc);
3666 /* Create a constraint ID = &FROM. */
3668 static void
3669 make_constraint_from (varinfo_t vi, int from)
3671 struct constraint_expr lhs, rhs;
3673 lhs.var = vi->id;
3674 lhs.offset = 0;
3675 lhs.type = SCALAR;
3677 rhs.var = from;
3678 rhs.offset = 0;
3679 rhs.type = ADDRESSOF;
3680 process_constraint (new_constraint (lhs, rhs));
3683 /* Create a constraint ID = FROM. */
3685 static void
3686 make_copy_constraint (varinfo_t vi, int from)
3688 struct constraint_expr lhs, rhs;
3690 lhs.var = vi->id;
3691 lhs.offset = 0;
3692 lhs.type = SCALAR;
3694 rhs.var = from;
3695 rhs.offset = 0;
3696 rhs.type = SCALAR;
3697 process_constraint (new_constraint (lhs, rhs));
3700 /* Make constraints necessary to make OP escape. */
3702 static void
3703 make_escape_constraint (tree op)
3705 make_constraint_to (escaped_id, op);
3708 /* Add constraints to that the solution of VI is transitively closed. */
3710 static void
3711 make_transitive_closure_constraints (varinfo_t vi)
3713 struct constraint_expr lhs, rhs;
3715 /* VAR = *VAR; */
3716 lhs.type = SCALAR;
3717 lhs.var = vi->id;
3718 lhs.offset = 0;
3719 rhs.type = DEREF;
3720 rhs.var = vi->id;
3721 rhs.offset = UNKNOWN_OFFSET;
3722 process_constraint (new_constraint (lhs, rhs));
3725 /* Temporary storage for fake var decls. */
3726 struct obstack fake_var_decl_obstack;
3728 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3730 static tree
3731 build_fake_var_decl (tree type)
3733 tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
3734 memset (decl, 0, sizeof (struct tree_var_decl));
3735 TREE_SET_CODE (decl, VAR_DECL);
3736 TREE_TYPE (decl) = type;
3737 DECL_UID (decl) = allocate_decl_uid ();
3738 SET_DECL_PT_UID (decl, -1);
3739 layout_decl (decl, 0);
3740 return decl;
3743 /* Create a new artificial heap variable with NAME.
3744 Return the created variable. */
3746 static varinfo_t
3747 make_heapvar (const char *name)
3749 varinfo_t vi;
3750 tree heapvar;
3752 heapvar = build_fake_var_decl (ptr_type_node);
3753 DECL_EXTERNAL (heapvar) = 1;
3755 vi = new_var_info (heapvar, name);
3756 vi->is_artificial_var = true;
3757 vi->is_heap_var = true;
3758 vi->is_unknown_size_var = true;
3759 vi->offset = 0;
3760 vi->fullsize = ~0;
3761 vi->size = ~0;
3762 vi->is_full_var = true;
3763 insert_vi_for_tree (heapvar, vi);
3765 return vi;
3768 /* Create a new artificial heap variable with NAME and make a
3769 constraint from it to LHS. Set flags according to a tag used
3770 for tracking restrict pointers. */
3772 static varinfo_t
3773 make_constraint_from_restrict (varinfo_t lhs, const char *name)
3775 varinfo_t vi = make_heapvar (name);
3776 vi->is_global_var = 1;
3777 vi->may_have_pointers = 1;
3778 make_constraint_from (lhs, vi->id);
3779 return vi;
3782 /* Create a new artificial heap variable with NAME and make a
3783 constraint from it to LHS. Set flags according to a tag used
3784 for tracking restrict pointers and make the artificial heap
3785 point to global memory. */
3787 static varinfo_t
3788 make_constraint_from_global_restrict (varinfo_t lhs, const char *name)
3790 varinfo_t vi = make_constraint_from_restrict (lhs, name);
3791 make_copy_constraint (vi, nonlocal_id);
3792 return vi;
3795 /* In IPA mode there are varinfos for different aspects of reach
3796 function designator. One for the points-to set of the return
3797 value, one for the variables that are clobbered by the function,
3798 one for its uses and one for each parameter (including a single
3799 glob for remaining variadic arguments). */
3801 enum { fi_clobbers = 1, fi_uses = 2,
3802 fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 };
3804 /* Get a constraint for the requested part of a function designator FI
3805 when operating in IPA mode. */
3807 static struct constraint_expr
3808 get_function_part_constraint (varinfo_t fi, unsigned part)
3810 struct constraint_expr c;
3812 gcc_assert (in_ipa_mode);
3814 if (fi->id == anything_id)
3816 /* ??? We probably should have a ANYFN special variable. */
3817 c.var = anything_id;
3818 c.offset = 0;
3819 c.type = SCALAR;
3821 else if (TREE_CODE (fi->decl) == FUNCTION_DECL)
3823 varinfo_t ai = first_vi_for_offset (fi, part);
3824 if (ai)
3825 c.var = ai->id;
3826 else
3827 c.var = anything_id;
3828 c.offset = 0;
3829 c.type = SCALAR;
3831 else
3833 c.var = fi->id;
3834 c.offset = part;
3835 c.type = DEREF;
3838 return c;
3841 /* For non-IPA mode, generate constraints necessary for a call on the
3842 RHS. */
3844 static void
3845 handle_rhs_call (gimple stmt, vec<ce_s> *results)
3847 struct constraint_expr rhsc;
3848 unsigned i;
3849 bool returns_uses = false;
3851 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3853 tree arg = gimple_call_arg (stmt, i);
3854 int flags = gimple_call_arg_flags (stmt, i);
3856 /* If the argument is not used we can ignore it. */
3857 if (flags & EAF_UNUSED)
3858 continue;
3860 /* As we compute ESCAPED context-insensitive we do not gain
3861 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3862 set. The argument would still get clobbered through the
3863 escape solution. */
3864 if ((flags & EAF_NOCLOBBER)
3865 && (flags & EAF_NOESCAPE))
3867 varinfo_t uses = get_call_use_vi (stmt);
3868 if (!(flags & EAF_DIRECT))
3870 varinfo_t tem = new_var_info (NULL_TREE, "callarg");
3871 make_constraint_to (tem->id, arg);
3872 make_transitive_closure_constraints (tem);
3873 make_copy_constraint (uses, tem->id);
3875 else
3876 make_constraint_to (uses->id, arg);
3877 returns_uses = true;
3879 else if (flags & EAF_NOESCAPE)
3881 struct constraint_expr lhs, rhs;
3882 varinfo_t uses = get_call_use_vi (stmt);
3883 varinfo_t clobbers = get_call_clobber_vi (stmt);
3884 varinfo_t tem = new_var_info (NULL_TREE, "callarg");
3885 make_constraint_to (tem->id, arg);
3886 if (!(flags & EAF_DIRECT))
3887 make_transitive_closure_constraints (tem);
3888 make_copy_constraint (uses, tem->id);
3889 make_copy_constraint (clobbers, tem->id);
3890 /* Add *tem = nonlocal, do not add *tem = callused as
3891 EAF_NOESCAPE parameters do not escape to other parameters
3892 and all other uses appear in NONLOCAL as well. */
3893 lhs.type = DEREF;
3894 lhs.var = tem->id;
3895 lhs.offset = 0;
3896 rhs.type = SCALAR;
3897 rhs.var = nonlocal_id;
3898 rhs.offset = 0;
3899 process_constraint (new_constraint (lhs, rhs));
3900 returns_uses = true;
3902 else
3903 make_escape_constraint (arg);
3906 /* If we added to the calls uses solution make sure we account for
3907 pointers to it to be returned. */
3908 if (returns_uses)
3910 rhsc.var = get_call_use_vi (stmt)->id;
3911 rhsc.offset = 0;
3912 rhsc.type = SCALAR;
3913 results->safe_push (rhsc);
3916 /* The static chain escapes as well. */
3917 if (gimple_call_chain (stmt))
3918 make_escape_constraint (gimple_call_chain (stmt));
3920 /* And if we applied NRV the address of the return slot escapes as well. */
3921 if (gimple_call_return_slot_opt_p (stmt)
3922 && gimple_call_lhs (stmt) != NULL_TREE
3923 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
3925 auto_vec<ce_s> tmpc;
3926 struct constraint_expr lhsc, *c;
3927 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
3928 lhsc.var = escaped_id;
3929 lhsc.offset = 0;
3930 lhsc.type = SCALAR;
3931 FOR_EACH_VEC_ELT (tmpc, i, c)
3932 process_constraint (new_constraint (lhsc, *c));
3935 /* Regular functions return nonlocal memory. */
3936 rhsc.var = nonlocal_id;
3937 rhsc.offset = 0;
3938 rhsc.type = SCALAR;
3939 results->safe_push (rhsc);
3942 /* For non-IPA mode, generate constraints necessary for a call
3943 that returns a pointer and assigns it to LHS. This simply makes
3944 the LHS point to global and escaped variables. */
3946 static void
3947 handle_lhs_call (gimple stmt, tree lhs, int flags, vec<ce_s> rhsc,
3948 tree fndecl)
3950 auto_vec<ce_s> lhsc;
3952 get_constraint_for (lhs, &lhsc);
3953 /* If the store is to a global decl make sure to
3954 add proper escape constraints. */
3955 lhs = get_base_address (lhs);
3956 if (lhs
3957 && DECL_P (lhs)
3958 && is_global_var (lhs))
3960 struct constraint_expr tmpc;
3961 tmpc.var = escaped_id;
3962 tmpc.offset = 0;
3963 tmpc.type = SCALAR;
3964 lhsc.safe_push (tmpc);
3967 /* If the call returns an argument unmodified override the rhs
3968 constraints. */
3969 if (flags & ERF_RETURNS_ARG
3970 && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
3972 tree arg;
3973 rhsc.create (0);
3974 arg = gimple_call_arg (stmt, flags & ERF_RETURN_ARG_MASK);
3975 get_constraint_for (arg, &rhsc);
3976 process_all_all_constraints (lhsc, rhsc);
3977 rhsc.release ();
3979 else if (flags & ERF_NOALIAS)
3981 varinfo_t vi;
3982 struct constraint_expr tmpc;
3983 rhsc.create (0);
3984 vi = make_heapvar ("HEAP");
3985 /* We are marking allocated storage local, we deal with it becoming
3986 global by escaping and setting of vars_contains_escaped_heap. */
3987 DECL_EXTERNAL (vi->decl) = 0;
3988 vi->is_global_var = 0;
3989 /* If this is not a real malloc call assume the memory was
3990 initialized and thus may point to global memory. All
3991 builtin functions with the malloc attribute behave in a sane way. */
3992 if (!fndecl
3993 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
3994 make_constraint_from (vi, nonlocal_id);
3995 tmpc.var = vi->id;
3996 tmpc.offset = 0;
3997 tmpc.type = ADDRESSOF;
3998 rhsc.safe_push (tmpc);
3999 process_all_all_constraints (lhsc, rhsc);
4000 rhsc.release ();
4002 else
4003 process_all_all_constraints (lhsc, rhsc);
4006 /* For non-IPA mode, generate constraints necessary for a call of a
4007 const function that returns a pointer in the statement STMT. */
4009 static void
4010 handle_const_call (gimple stmt, vec<ce_s> *results)
4012 struct constraint_expr rhsc;
4013 unsigned int k;
4015 /* Treat nested const functions the same as pure functions as far
4016 as the static chain is concerned. */
4017 if (gimple_call_chain (stmt))
4019 varinfo_t uses = get_call_use_vi (stmt);
4020 make_transitive_closure_constraints (uses);
4021 make_constraint_to (uses->id, gimple_call_chain (stmt));
4022 rhsc.var = uses->id;
4023 rhsc.offset = 0;
4024 rhsc.type = SCALAR;
4025 results->safe_push (rhsc);
4028 /* May return arguments. */
4029 for (k = 0; k < gimple_call_num_args (stmt); ++k)
4031 tree arg = gimple_call_arg (stmt, k);
4032 auto_vec<ce_s> argc;
4033 unsigned i;
4034 struct constraint_expr *argp;
4035 get_constraint_for_rhs (arg, &argc);
4036 FOR_EACH_VEC_ELT (argc, i, argp)
4037 results->safe_push (*argp);
4040 /* May return addresses of globals. */
4041 rhsc.var = nonlocal_id;
4042 rhsc.offset = 0;
4043 rhsc.type = ADDRESSOF;
4044 results->safe_push (rhsc);
4047 /* For non-IPA mode, generate constraints necessary for a call to a
4048 pure function in statement STMT. */
4050 static void
4051 handle_pure_call (gimple stmt, vec<ce_s> *results)
4053 struct constraint_expr rhsc;
4054 unsigned i;
4055 varinfo_t uses = NULL;
4057 /* Memory reached from pointer arguments is call-used. */
4058 for (i = 0; i < gimple_call_num_args (stmt); ++i)
4060 tree arg = gimple_call_arg (stmt, i);
4061 if (!uses)
4063 uses = get_call_use_vi (stmt);
4064 make_transitive_closure_constraints (uses);
4066 make_constraint_to (uses->id, arg);
4069 /* The static chain is used as well. */
4070 if (gimple_call_chain (stmt))
4072 if (!uses)
4074 uses = get_call_use_vi (stmt);
4075 make_transitive_closure_constraints (uses);
4077 make_constraint_to (uses->id, gimple_call_chain (stmt));
4080 /* Pure functions may return call-used and nonlocal memory. */
4081 if (uses)
4083 rhsc.var = uses->id;
4084 rhsc.offset = 0;
4085 rhsc.type = SCALAR;
4086 results->safe_push (rhsc);
4088 rhsc.var = nonlocal_id;
4089 rhsc.offset = 0;
4090 rhsc.type = SCALAR;
4091 results->safe_push (rhsc);
4095 /* Return the varinfo for the callee of CALL. */
4097 static varinfo_t
4098 get_fi_for_callee (gimple call)
4100 tree decl, fn = gimple_call_fn (call);
4102 if (fn && TREE_CODE (fn) == OBJ_TYPE_REF)
4103 fn = OBJ_TYPE_REF_EXPR (fn);
4105 /* If we can directly resolve the function being called, do so.
4106 Otherwise, it must be some sort of indirect expression that
4107 we should still be able to handle. */
4108 decl = gimple_call_addr_fndecl (fn);
4109 if (decl)
4110 return get_vi_for_tree (decl);
4112 /* If the function is anything other than a SSA name pointer we have no
4113 clue and should be getting ANYFN (well, ANYTHING for now). */
4114 if (!fn || TREE_CODE (fn) != SSA_NAME)
4115 return get_varinfo (anything_id);
4117 if (SSA_NAME_IS_DEFAULT_DEF (fn)
4118 && (TREE_CODE (SSA_NAME_VAR (fn)) == PARM_DECL
4119 || TREE_CODE (SSA_NAME_VAR (fn)) == RESULT_DECL))
4120 fn = SSA_NAME_VAR (fn);
4122 return get_vi_for_tree (fn);
4125 /* Create constraints for the builtin call T. Return true if the call
4126 was handled, otherwise false. */
4128 static bool
4129 find_func_aliases_for_builtin_call (struct function *fn, gimple t)
4131 tree fndecl = gimple_call_fndecl (t);
4132 auto_vec<ce_s, 2> lhsc;
4133 auto_vec<ce_s, 4> rhsc;
4134 varinfo_t fi;
4136 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
4137 /* ??? All builtins that are handled here need to be handled
4138 in the alias-oracle query functions explicitly! */
4139 switch (DECL_FUNCTION_CODE (fndecl))
4141 /* All the following functions return a pointer to the same object
4142 as their first argument points to. The functions do not add
4143 to the ESCAPED solution. The functions make the first argument
4144 pointed to memory point to what the second argument pointed to
4145 memory points to. */
4146 case BUILT_IN_STRCPY:
4147 case BUILT_IN_STRNCPY:
4148 case BUILT_IN_BCOPY:
4149 case BUILT_IN_MEMCPY:
4150 case BUILT_IN_MEMMOVE:
4151 case BUILT_IN_MEMPCPY:
4152 case BUILT_IN_STPCPY:
4153 case BUILT_IN_STPNCPY:
4154 case BUILT_IN_STRCAT:
4155 case BUILT_IN_STRNCAT:
4156 case BUILT_IN_STRCPY_CHK:
4157 case BUILT_IN_STRNCPY_CHK:
4158 case BUILT_IN_MEMCPY_CHK:
4159 case BUILT_IN_MEMMOVE_CHK:
4160 case BUILT_IN_MEMPCPY_CHK:
4161 case BUILT_IN_STPCPY_CHK:
4162 case BUILT_IN_STPNCPY_CHK:
4163 case BUILT_IN_STRCAT_CHK:
4164 case BUILT_IN_STRNCAT_CHK:
4165 case BUILT_IN_TM_MEMCPY:
4166 case BUILT_IN_TM_MEMMOVE:
4168 tree res = gimple_call_lhs (t);
4169 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4170 == BUILT_IN_BCOPY ? 1 : 0));
4171 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4172 == BUILT_IN_BCOPY ? 0 : 1));
4173 if (res != NULL_TREE)
4175 get_constraint_for (res, &lhsc);
4176 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
4177 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
4178 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY
4179 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHK
4180 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY_CHK
4181 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY_CHK)
4182 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
4183 else
4184 get_constraint_for (dest, &rhsc);
4185 process_all_all_constraints (lhsc, rhsc);
4186 lhsc.truncate (0);
4187 rhsc.truncate (0);
4189 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4190 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4191 do_deref (&lhsc);
4192 do_deref (&rhsc);
4193 process_all_all_constraints (lhsc, rhsc);
4194 return true;
4196 case BUILT_IN_MEMSET:
4197 case BUILT_IN_MEMSET_CHK:
4198 case BUILT_IN_TM_MEMSET:
4200 tree res = gimple_call_lhs (t);
4201 tree dest = gimple_call_arg (t, 0);
4202 unsigned i;
4203 ce_s *lhsp;
4204 struct constraint_expr ac;
4205 if (res != NULL_TREE)
4207 get_constraint_for (res, &lhsc);
4208 get_constraint_for (dest, &rhsc);
4209 process_all_all_constraints (lhsc, rhsc);
4210 lhsc.truncate (0);
4212 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4213 do_deref (&lhsc);
4214 if (flag_delete_null_pointer_checks
4215 && integer_zerop (gimple_call_arg (t, 1)))
4217 ac.type = ADDRESSOF;
4218 ac.var = nothing_id;
4220 else
4222 ac.type = SCALAR;
4223 ac.var = integer_id;
4225 ac.offset = 0;
4226 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4227 process_constraint (new_constraint (*lhsp, ac));
4228 return true;
4230 case BUILT_IN_POSIX_MEMALIGN:
4232 tree ptrptr = gimple_call_arg (t, 0);
4233 get_constraint_for (ptrptr, &lhsc);
4234 do_deref (&lhsc);
4235 varinfo_t vi = make_heapvar ("HEAP");
4236 /* We are marking allocated storage local, we deal with it becoming
4237 global by escaping and setting of vars_contains_escaped_heap. */
4238 DECL_EXTERNAL (vi->decl) = 0;
4239 vi->is_global_var = 0;
4240 struct constraint_expr tmpc;
4241 tmpc.var = vi->id;
4242 tmpc.offset = 0;
4243 tmpc.type = ADDRESSOF;
4244 rhsc.safe_push (tmpc);
4245 process_all_all_constraints (lhsc, rhsc);
4246 return true;
4248 case BUILT_IN_ASSUME_ALIGNED:
4250 tree res = gimple_call_lhs (t);
4251 tree dest = gimple_call_arg (t, 0);
4252 if (res != NULL_TREE)
4254 get_constraint_for (res, &lhsc);
4255 get_constraint_for (dest, &rhsc);
4256 process_all_all_constraints (lhsc, rhsc);
4258 return true;
4260 /* All the following functions do not return pointers, do not
4261 modify the points-to sets of memory reachable from their
4262 arguments and do not add to the ESCAPED solution. */
4263 case BUILT_IN_SINCOS:
4264 case BUILT_IN_SINCOSF:
4265 case BUILT_IN_SINCOSL:
4266 case BUILT_IN_FREXP:
4267 case BUILT_IN_FREXPF:
4268 case BUILT_IN_FREXPL:
4269 case BUILT_IN_GAMMA_R:
4270 case BUILT_IN_GAMMAF_R:
4271 case BUILT_IN_GAMMAL_R:
4272 case BUILT_IN_LGAMMA_R:
4273 case BUILT_IN_LGAMMAF_R:
4274 case BUILT_IN_LGAMMAL_R:
4275 case BUILT_IN_MODF:
4276 case BUILT_IN_MODFF:
4277 case BUILT_IN_MODFL:
4278 case BUILT_IN_REMQUO:
4279 case BUILT_IN_REMQUOF:
4280 case BUILT_IN_REMQUOL:
4281 case BUILT_IN_FREE:
4282 return true;
4283 case BUILT_IN_STRDUP:
4284 case BUILT_IN_STRNDUP:
4285 case BUILT_IN_REALLOC:
4286 if (gimple_call_lhs (t))
4288 handle_lhs_call (t, gimple_call_lhs (t),
4289 gimple_call_return_flags (t) | ERF_NOALIAS,
4290 vNULL, fndecl);
4291 get_constraint_for_ptr_offset (gimple_call_lhs (t),
4292 NULL_TREE, &lhsc);
4293 get_constraint_for_ptr_offset (gimple_call_arg (t, 0),
4294 NULL_TREE, &rhsc);
4295 do_deref (&lhsc);
4296 do_deref (&rhsc);
4297 process_all_all_constraints (lhsc, rhsc);
4298 lhsc.truncate (0);
4299 rhsc.truncate (0);
4300 /* For realloc the resulting pointer can be equal to the
4301 argument as well. But only doing this wouldn't be
4302 correct because with ptr == 0 realloc behaves like malloc. */
4303 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_REALLOC)
4305 get_constraint_for (gimple_call_lhs (t), &lhsc);
4306 get_constraint_for (gimple_call_arg (t, 0), &rhsc);
4307 process_all_all_constraints (lhsc, rhsc);
4309 return true;
4311 break;
4312 /* String / character search functions return a pointer into the
4313 source string or NULL. */
4314 case BUILT_IN_INDEX:
4315 case BUILT_IN_STRCHR:
4316 case BUILT_IN_STRRCHR:
4317 case BUILT_IN_MEMCHR:
4318 case BUILT_IN_STRSTR:
4319 case BUILT_IN_STRPBRK:
4320 if (gimple_call_lhs (t))
4322 tree src = gimple_call_arg (t, 0);
4323 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4324 constraint_expr nul;
4325 nul.var = nothing_id;
4326 nul.offset = 0;
4327 nul.type = ADDRESSOF;
4328 rhsc.safe_push (nul);
4329 get_constraint_for (gimple_call_lhs (t), &lhsc);
4330 process_all_all_constraints (lhsc, rhsc);
4332 return true;
4333 /* Trampolines are special - they set up passing the static
4334 frame. */
4335 case BUILT_IN_INIT_TRAMPOLINE:
4337 tree tramp = gimple_call_arg (t, 0);
4338 tree nfunc = gimple_call_arg (t, 1);
4339 tree frame = gimple_call_arg (t, 2);
4340 unsigned i;
4341 struct constraint_expr lhs, *rhsp;
4342 if (in_ipa_mode)
4344 varinfo_t nfi = NULL;
4345 gcc_assert (TREE_CODE (nfunc) == ADDR_EXPR);
4346 nfi = lookup_vi_for_tree (TREE_OPERAND (nfunc, 0));
4347 if (nfi)
4349 lhs = get_function_part_constraint (nfi, fi_static_chain);
4350 get_constraint_for (frame, &rhsc);
4351 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4352 process_constraint (new_constraint (lhs, *rhsp));
4353 rhsc.truncate (0);
4355 /* Make the frame point to the function for
4356 the trampoline adjustment call. */
4357 get_constraint_for (tramp, &lhsc);
4358 do_deref (&lhsc);
4359 get_constraint_for (nfunc, &rhsc);
4360 process_all_all_constraints (lhsc, rhsc);
4362 return true;
4365 /* Else fallthru to generic handling which will let
4366 the frame escape. */
4367 break;
4369 case BUILT_IN_ADJUST_TRAMPOLINE:
4371 tree tramp = gimple_call_arg (t, 0);
4372 tree res = gimple_call_lhs (t);
4373 if (in_ipa_mode && res)
4375 get_constraint_for (res, &lhsc);
4376 get_constraint_for (tramp, &rhsc);
4377 do_deref (&rhsc);
4378 process_all_all_constraints (lhsc, rhsc);
4380 return true;
4382 CASE_BUILT_IN_TM_STORE (1):
4383 CASE_BUILT_IN_TM_STORE (2):
4384 CASE_BUILT_IN_TM_STORE (4):
4385 CASE_BUILT_IN_TM_STORE (8):
4386 CASE_BUILT_IN_TM_STORE (FLOAT):
4387 CASE_BUILT_IN_TM_STORE (DOUBLE):
4388 CASE_BUILT_IN_TM_STORE (LDOUBLE):
4389 CASE_BUILT_IN_TM_STORE (M64):
4390 CASE_BUILT_IN_TM_STORE (M128):
4391 CASE_BUILT_IN_TM_STORE (M256):
4393 tree addr = gimple_call_arg (t, 0);
4394 tree src = gimple_call_arg (t, 1);
4396 get_constraint_for (addr, &lhsc);
4397 do_deref (&lhsc);
4398 get_constraint_for (src, &rhsc);
4399 process_all_all_constraints (lhsc, rhsc);
4400 return true;
4402 CASE_BUILT_IN_TM_LOAD (1):
4403 CASE_BUILT_IN_TM_LOAD (2):
4404 CASE_BUILT_IN_TM_LOAD (4):
4405 CASE_BUILT_IN_TM_LOAD (8):
4406 CASE_BUILT_IN_TM_LOAD (FLOAT):
4407 CASE_BUILT_IN_TM_LOAD (DOUBLE):
4408 CASE_BUILT_IN_TM_LOAD (LDOUBLE):
4409 CASE_BUILT_IN_TM_LOAD (M64):
4410 CASE_BUILT_IN_TM_LOAD (M128):
4411 CASE_BUILT_IN_TM_LOAD (M256):
4413 tree dest = gimple_call_lhs (t);
4414 tree addr = gimple_call_arg (t, 0);
4416 get_constraint_for (dest, &lhsc);
4417 get_constraint_for (addr, &rhsc);
4418 do_deref (&rhsc);
4419 process_all_all_constraints (lhsc, rhsc);
4420 return true;
4422 /* Variadic argument handling needs to be handled in IPA
4423 mode as well. */
4424 case BUILT_IN_VA_START:
4426 tree valist = gimple_call_arg (t, 0);
4427 struct constraint_expr rhs, *lhsp;
4428 unsigned i;
4429 get_constraint_for (valist, &lhsc);
4430 do_deref (&lhsc);
4431 /* The va_list gets access to pointers in variadic
4432 arguments. Which we know in the case of IPA analysis
4433 and otherwise are just all nonlocal variables. */
4434 if (in_ipa_mode)
4436 fi = lookup_vi_for_tree (fn->decl);
4437 rhs = get_function_part_constraint (fi, ~0);
4438 rhs.type = ADDRESSOF;
4440 else
4442 rhs.var = nonlocal_id;
4443 rhs.type = ADDRESSOF;
4444 rhs.offset = 0;
4446 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4447 process_constraint (new_constraint (*lhsp, rhs));
4448 /* va_list is clobbered. */
4449 make_constraint_to (get_call_clobber_vi (t)->id, valist);
4450 return true;
4452 /* va_end doesn't have any effect that matters. */
4453 case BUILT_IN_VA_END:
4454 return true;
4455 /* Alternate return. Simply give up for now. */
4456 case BUILT_IN_RETURN:
4458 fi = NULL;
4459 if (!in_ipa_mode
4460 || !(fi = get_vi_for_tree (fn->decl)))
4461 make_constraint_from (get_varinfo (escaped_id), anything_id);
4462 else if (in_ipa_mode
4463 && fi != NULL)
4465 struct constraint_expr lhs, rhs;
4466 lhs = get_function_part_constraint (fi, fi_result);
4467 rhs.var = anything_id;
4468 rhs.offset = 0;
4469 rhs.type = SCALAR;
4470 process_constraint (new_constraint (lhs, rhs));
4472 return true;
4474 /* printf-style functions may have hooks to set pointers to
4475 point to somewhere into the generated string. Leave them
4476 for a later exercise... */
4477 default:
4478 /* Fallthru to general call handling. */;
4481 return false;
4484 /* Create constraints for the call T. */
4486 static void
4487 find_func_aliases_for_call (struct function *fn, gimple t)
4489 tree fndecl = gimple_call_fndecl (t);
4490 varinfo_t fi;
4492 if (fndecl != NULL_TREE
4493 && DECL_BUILT_IN (fndecl)
4494 && find_func_aliases_for_builtin_call (fn, t))
4495 return;
4497 fi = get_fi_for_callee (t);
4498 if (!in_ipa_mode
4499 || (fndecl && !fi->is_fn_info))
4501 auto_vec<ce_s, 16> rhsc;
4502 int flags = gimple_call_flags (t);
4504 /* Const functions can return their arguments and addresses
4505 of global memory but not of escaped memory. */
4506 if (flags & (ECF_CONST|ECF_NOVOPS))
4508 if (gimple_call_lhs (t))
4509 handle_const_call (t, &rhsc);
4511 /* Pure functions can return addresses in and of memory
4512 reachable from their arguments, but they are not an escape
4513 point for reachable memory of their arguments. */
4514 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
4515 handle_pure_call (t, &rhsc);
4516 else
4517 handle_rhs_call (t, &rhsc);
4518 if (gimple_call_lhs (t))
4519 handle_lhs_call (t, gimple_call_lhs (t),
4520 gimple_call_return_flags (t), rhsc, fndecl);
4522 else
4524 auto_vec<ce_s, 2> rhsc;
4525 tree lhsop;
4526 unsigned j;
4528 /* Assign all the passed arguments to the appropriate incoming
4529 parameters of the function. */
4530 for (j = 0; j < gimple_call_num_args (t); j++)
4532 struct constraint_expr lhs ;
4533 struct constraint_expr *rhsp;
4534 tree arg = gimple_call_arg (t, j);
4536 get_constraint_for_rhs (arg, &rhsc);
4537 lhs = get_function_part_constraint (fi, fi_parm_base + j);
4538 while (rhsc.length () != 0)
4540 rhsp = &rhsc.last ();
4541 process_constraint (new_constraint (lhs, *rhsp));
4542 rhsc.pop ();
4546 /* If we are returning a value, assign it to the result. */
4547 lhsop = gimple_call_lhs (t);
4548 if (lhsop)
4550 auto_vec<ce_s, 2> lhsc;
4551 struct constraint_expr rhs;
4552 struct constraint_expr *lhsp;
4554 get_constraint_for (lhsop, &lhsc);
4555 rhs = get_function_part_constraint (fi, fi_result);
4556 if (fndecl
4557 && DECL_RESULT (fndecl)
4558 && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
4560 auto_vec<ce_s, 2> tem;
4561 tem.quick_push (rhs);
4562 do_deref (&tem);
4563 gcc_checking_assert (tem.length () == 1);
4564 rhs = tem[0];
4566 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
4567 process_constraint (new_constraint (*lhsp, rhs));
4570 /* If we pass the result decl by reference, honor that. */
4571 if (lhsop
4572 && fndecl
4573 && DECL_RESULT (fndecl)
4574 && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
4576 struct constraint_expr lhs;
4577 struct constraint_expr *rhsp;
4579 get_constraint_for_address_of (lhsop, &rhsc);
4580 lhs = get_function_part_constraint (fi, fi_result);
4581 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4582 process_constraint (new_constraint (lhs, *rhsp));
4583 rhsc.truncate (0);
4586 /* If we use a static chain, pass it along. */
4587 if (gimple_call_chain (t))
4589 struct constraint_expr lhs;
4590 struct constraint_expr *rhsp;
4592 get_constraint_for (gimple_call_chain (t), &rhsc);
4593 lhs = get_function_part_constraint (fi, fi_static_chain);
4594 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4595 process_constraint (new_constraint (lhs, *rhsp));
4600 /* Walk statement T setting up aliasing constraints according to the
4601 references found in T. This function is the main part of the
4602 constraint builder. AI points to auxiliary alias information used
4603 when building alias sets and computing alias grouping heuristics. */
4605 static void
4606 find_func_aliases (struct function *fn, gimple origt)
4608 gimple t = origt;
4609 auto_vec<ce_s, 16> lhsc;
4610 auto_vec<ce_s, 16> rhsc;
4611 struct constraint_expr *c;
4612 varinfo_t fi;
4614 /* Now build constraints expressions. */
4615 if (gimple_code (t) == GIMPLE_PHI)
4617 size_t i;
4618 unsigned int j;
4620 /* For a phi node, assign all the arguments to
4621 the result. */
4622 get_constraint_for (gimple_phi_result (t), &lhsc);
4623 for (i = 0; i < gimple_phi_num_args (t); i++)
4625 tree strippedrhs = PHI_ARG_DEF (t, i);
4627 STRIP_NOPS (strippedrhs);
4628 get_constraint_for_rhs (gimple_phi_arg_def (t, i), &rhsc);
4630 FOR_EACH_VEC_ELT (lhsc, j, c)
4632 struct constraint_expr *c2;
4633 while (rhsc.length () > 0)
4635 c2 = &rhsc.last ();
4636 process_constraint (new_constraint (*c, *c2));
4637 rhsc.pop ();
4642 /* In IPA mode, we need to generate constraints to pass call
4643 arguments through their calls. There are two cases,
4644 either a GIMPLE_CALL returning a value, or just a plain
4645 GIMPLE_CALL when we are not.
4647 In non-ipa mode, we need to generate constraints for each
4648 pointer passed by address. */
4649 else if (is_gimple_call (t))
4650 find_func_aliases_for_call (fn, t);
4652 /* Otherwise, just a regular assignment statement. Only care about
4653 operations with pointer result, others are dealt with as escape
4654 points if they have pointer operands. */
4655 else if (is_gimple_assign (t))
4657 /* Otherwise, just a regular assignment statement. */
4658 tree lhsop = gimple_assign_lhs (t);
4659 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
4661 if (rhsop && TREE_CLOBBER_P (rhsop))
4662 /* Ignore clobbers, they don't actually store anything into
4663 the LHS. */
4665 else if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
4666 do_structure_copy (lhsop, rhsop);
4667 else
4669 enum tree_code code = gimple_assign_rhs_code (t);
4671 get_constraint_for (lhsop, &lhsc);
4673 if (FLOAT_TYPE_P (TREE_TYPE (lhsop)))
4674 /* If the operation produces a floating point result then
4675 assume the value is not produced to transfer a pointer. */
4677 else if (code == POINTER_PLUS_EXPR)
4678 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4679 gimple_assign_rhs2 (t), &rhsc);
4680 else if (code == BIT_AND_EXPR
4681 && TREE_CODE (gimple_assign_rhs2 (t)) == INTEGER_CST)
4683 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4684 the pointer. Handle it by offsetting it by UNKNOWN. */
4685 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4686 NULL_TREE, &rhsc);
4688 else if ((CONVERT_EXPR_CODE_P (code)
4689 && !(POINTER_TYPE_P (gimple_expr_type (t))
4690 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
4691 || gimple_assign_single_p (t))
4692 get_constraint_for_rhs (rhsop, &rhsc);
4693 else if (code == COND_EXPR)
4695 /* The result is a merge of both COND_EXPR arms. */
4696 auto_vec<ce_s, 2> tmp;
4697 struct constraint_expr *rhsp;
4698 unsigned i;
4699 get_constraint_for_rhs (gimple_assign_rhs2 (t), &rhsc);
4700 get_constraint_for_rhs (gimple_assign_rhs3 (t), &tmp);
4701 FOR_EACH_VEC_ELT (tmp, i, rhsp)
4702 rhsc.safe_push (*rhsp);
4704 else if (truth_value_p (code))
4705 /* Truth value results are not pointer (parts). Or at least
4706 very very unreasonable obfuscation of a part. */
4708 else
4710 /* All other operations are merges. */
4711 auto_vec<ce_s, 4> tmp;
4712 struct constraint_expr *rhsp;
4713 unsigned i, j;
4714 get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
4715 for (i = 2; i < gimple_num_ops (t); ++i)
4717 get_constraint_for_rhs (gimple_op (t, i), &tmp);
4718 FOR_EACH_VEC_ELT (tmp, j, rhsp)
4719 rhsc.safe_push (*rhsp);
4720 tmp.truncate (0);
4723 process_all_all_constraints (lhsc, rhsc);
4725 /* If there is a store to a global variable the rhs escapes. */
4726 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
4727 && DECL_P (lhsop)
4728 && is_global_var (lhsop)
4729 && (!in_ipa_mode
4730 || DECL_EXTERNAL (lhsop) || TREE_PUBLIC (lhsop)))
4731 make_escape_constraint (rhsop);
4733 /* Handle escapes through return. */
4734 else if (gimple_code (t) == GIMPLE_RETURN
4735 && gimple_return_retval (t) != NULL_TREE)
4737 fi = NULL;
4738 if (!in_ipa_mode
4739 || !(fi = get_vi_for_tree (fn->decl)))
4740 make_escape_constraint (gimple_return_retval (t));
4741 else if (in_ipa_mode
4742 && fi != NULL)
4744 struct constraint_expr lhs ;
4745 struct constraint_expr *rhsp;
4746 unsigned i;
4748 lhs = get_function_part_constraint (fi, fi_result);
4749 get_constraint_for_rhs (gimple_return_retval (t), &rhsc);
4750 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4751 process_constraint (new_constraint (lhs, *rhsp));
4754 /* Handle asms conservatively by adding escape constraints to everything. */
4755 else if (gimple_code (t) == GIMPLE_ASM)
4757 unsigned i, noutputs;
4758 const char **oconstraints;
4759 const char *constraint;
4760 bool allows_mem, allows_reg, is_inout;
4762 noutputs = gimple_asm_noutputs (t);
4763 oconstraints = XALLOCAVEC (const char *, noutputs);
4765 for (i = 0; i < noutputs; ++i)
4767 tree link = gimple_asm_output_op (t, i);
4768 tree op = TREE_VALUE (link);
4770 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4771 oconstraints[i] = constraint;
4772 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4773 &allows_reg, &is_inout);
4775 /* A memory constraint makes the address of the operand escape. */
4776 if (!allows_reg && allows_mem)
4777 make_escape_constraint (build_fold_addr_expr (op));
4779 /* The asm may read global memory, so outputs may point to
4780 any global memory. */
4781 if (op)
4783 auto_vec<ce_s, 2> lhsc;
4784 struct constraint_expr rhsc, *lhsp;
4785 unsigned j;
4786 get_constraint_for (op, &lhsc);
4787 rhsc.var = nonlocal_id;
4788 rhsc.offset = 0;
4789 rhsc.type = SCALAR;
4790 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
4791 process_constraint (new_constraint (*lhsp, rhsc));
4794 for (i = 0; i < gimple_asm_ninputs (t); ++i)
4796 tree link = gimple_asm_input_op (t, i);
4797 tree op = TREE_VALUE (link);
4799 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4801 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
4802 &allows_mem, &allows_reg);
4804 /* A memory constraint makes the address of the operand escape. */
4805 if (!allows_reg && allows_mem)
4806 make_escape_constraint (build_fold_addr_expr (op));
4807 /* Strictly we'd only need the constraint to ESCAPED if
4808 the asm clobbers memory, otherwise using something
4809 along the lines of per-call clobbers/uses would be enough. */
4810 else if (op)
4811 make_escape_constraint (op);
4817 /* Create a constraint adding to the clobber set of FI the memory
4818 pointed to by PTR. */
4820 static void
4821 process_ipa_clobber (varinfo_t fi, tree ptr)
4823 vec<ce_s> ptrc = vNULL;
4824 struct constraint_expr *c, lhs;
4825 unsigned i;
4826 get_constraint_for_rhs (ptr, &ptrc);
4827 lhs = get_function_part_constraint (fi, fi_clobbers);
4828 FOR_EACH_VEC_ELT (ptrc, i, c)
4829 process_constraint (new_constraint (lhs, *c));
4830 ptrc.release ();
4833 /* Walk statement T setting up clobber and use constraints according to the
4834 references found in T. This function is a main part of the
4835 IPA constraint builder. */
4837 static void
4838 find_func_clobbers (struct function *fn, gimple origt)
4840 gimple t = origt;
4841 auto_vec<ce_s, 16> lhsc;
4842 auto_vec<ce_s, 16> rhsc;
4843 varinfo_t fi;
4845 /* Add constraints for clobbered/used in IPA mode.
4846 We are not interested in what automatic variables are clobbered
4847 or used as we only use the information in the caller to which
4848 they do not escape. */
4849 gcc_assert (in_ipa_mode);
4851 /* If the stmt refers to memory in any way it better had a VUSE. */
4852 if (gimple_vuse (t) == NULL_TREE)
4853 return;
4855 /* We'd better have function information for the current function. */
4856 fi = lookup_vi_for_tree (fn->decl);
4857 gcc_assert (fi != NULL);
4859 /* Account for stores in assignments and calls. */
4860 if (gimple_vdef (t) != NULL_TREE
4861 && gimple_has_lhs (t))
4863 tree lhs = gimple_get_lhs (t);
4864 tree tem = lhs;
4865 while (handled_component_p (tem))
4866 tem = TREE_OPERAND (tem, 0);
4867 if ((DECL_P (tem)
4868 && !auto_var_in_fn_p (tem, fn->decl))
4869 || INDIRECT_REF_P (tem)
4870 || (TREE_CODE (tem) == MEM_REF
4871 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
4872 && auto_var_in_fn_p
4873 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
4875 struct constraint_expr lhsc, *rhsp;
4876 unsigned i;
4877 lhsc = get_function_part_constraint (fi, fi_clobbers);
4878 get_constraint_for_address_of (lhs, &rhsc);
4879 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4880 process_constraint (new_constraint (lhsc, *rhsp));
4881 rhsc.truncate (0);
4885 /* Account for uses in assigments and returns. */
4886 if (gimple_assign_single_p (t)
4887 || (gimple_code (t) == GIMPLE_RETURN
4888 && gimple_return_retval (t) != NULL_TREE))
4890 tree rhs = (gimple_assign_single_p (t)
4891 ? gimple_assign_rhs1 (t) : gimple_return_retval (t));
4892 tree tem = rhs;
4893 while (handled_component_p (tem))
4894 tem = TREE_OPERAND (tem, 0);
4895 if ((DECL_P (tem)
4896 && !auto_var_in_fn_p (tem, fn->decl))
4897 || INDIRECT_REF_P (tem)
4898 || (TREE_CODE (tem) == MEM_REF
4899 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
4900 && auto_var_in_fn_p
4901 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
4903 struct constraint_expr lhs, *rhsp;
4904 unsigned i;
4905 lhs = get_function_part_constraint (fi, fi_uses);
4906 get_constraint_for_address_of (rhs, &rhsc);
4907 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4908 process_constraint (new_constraint (lhs, *rhsp));
4909 rhsc.truncate (0);
4913 if (is_gimple_call (t))
4915 varinfo_t cfi = NULL;
4916 tree decl = gimple_call_fndecl (t);
4917 struct constraint_expr lhs, rhs;
4918 unsigned i, j;
4920 /* For builtins we do not have separate function info. For those
4921 we do not generate escapes for we have to generate clobbers/uses. */
4922 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
4923 switch (DECL_FUNCTION_CODE (decl))
4925 /* The following functions use and clobber memory pointed to
4926 by their arguments. */
4927 case BUILT_IN_STRCPY:
4928 case BUILT_IN_STRNCPY:
4929 case BUILT_IN_BCOPY:
4930 case BUILT_IN_MEMCPY:
4931 case BUILT_IN_MEMMOVE:
4932 case BUILT_IN_MEMPCPY:
4933 case BUILT_IN_STPCPY:
4934 case BUILT_IN_STPNCPY:
4935 case BUILT_IN_STRCAT:
4936 case BUILT_IN_STRNCAT:
4937 case BUILT_IN_STRCPY_CHK:
4938 case BUILT_IN_STRNCPY_CHK:
4939 case BUILT_IN_MEMCPY_CHK:
4940 case BUILT_IN_MEMMOVE_CHK:
4941 case BUILT_IN_MEMPCPY_CHK:
4942 case BUILT_IN_STPCPY_CHK:
4943 case BUILT_IN_STPNCPY_CHK:
4944 case BUILT_IN_STRCAT_CHK:
4945 case BUILT_IN_STRNCAT_CHK:
4947 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
4948 == BUILT_IN_BCOPY ? 1 : 0));
4949 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
4950 == BUILT_IN_BCOPY ? 0 : 1));
4951 unsigned i;
4952 struct constraint_expr *rhsp, *lhsp;
4953 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4954 lhs = get_function_part_constraint (fi, fi_clobbers);
4955 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4956 process_constraint (new_constraint (lhs, *lhsp));
4957 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4958 lhs = get_function_part_constraint (fi, fi_uses);
4959 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4960 process_constraint (new_constraint (lhs, *rhsp));
4961 return;
4963 /* The following function clobbers memory pointed to by
4964 its argument. */
4965 case BUILT_IN_MEMSET:
4966 case BUILT_IN_MEMSET_CHK:
4967 case BUILT_IN_POSIX_MEMALIGN:
4969 tree dest = gimple_call_arg (t, 0);
4970 unsigned i;
4971 ce_s *lhsp;
4972 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4973 lhs = get_function_part_constraint (fi, fi_clobbers);
4974 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4975 process_constraint (new_constraint (lhs, *lhsp));
4976 return;
4978 /* The following functions clobber their second and third
4979 arguments. */
4980 case BUILT_IN_SINCOS:
4981 case BUILT_IN_SINCOSF:
4982 case BUILT_IN_SINCOSL:
4984 process_ipa_clobber (fi, gimple_call_arg (t, 1));
4985 process_ipa_clobber (fi, gimple_call_arg (t, 2));
4986 return;
4988 /* The following functions clobber their second argument. */
4989 case BUILT_IN_FREXP:
4990 case BUILT_IN_FREXPF:
4991 case BUILT_IN_FREXPL:
4992 case BUILT_IN_LGAMMA_R:
4993 case BUILT_IN_LGAMMAF_R:
4994 case BUILT_IN_LGAMMAL_R:
4995 case BUILT_IN_GAMMA_R:
4996 case BUILT_IN_GAMMAF_R:
4997 case BUILT_IN_GAMMAL_R:
4998 case BUILT_IN_MODF:
4999 case BUILT_IN_MODFF:
5000 case BUILT_IN_MODFL:
5002 process_ipa_clobber (fi, gimple_call_arg (t, 1));
5003 return;
5005 /* The following functions clobber their third argument. */
5006 case BUILT_IN_REMQUO:
5007 case BUILT_IN_REMQUOF:
5008 case BUILT_IN_REMQUOL:
5010 process_ipa_clobber (fi, gimple_call_arg (t, 2));
5011 return;
5013 /* The following functions neither read nor clobber memory. */
5014 case BUILT_IN_ASSUME_ALIGNED:
5015 case BUILT_IN_FREE:
5016 return;
5017 /* Trampolines are of no interest to us. */
5018 case BUILT_IN_INIT_TRAMPOLINE:
5019 case BUILT_IN_ADJUST_TRAMPOLINE:
5020 return;
5021 case BUILT_IN_VA_START:
5022 case BUILT_IN_VA_END:
5023 return;
5024 /* printf-style functions may have hooks to set pointers to
5025 point to somewhere into the generated string. Leave them
5026 for a later exercise... */
5027 default:
5028 /* Fallthru to general call handling. */;
5031 /* Parameters passed by value are used. */
5032 lhs = get_function_part_constraint (fi, fi_uses);
5033 for (i = 0; i < gimple_call_num_args (t); i++)
5035 struct constraint_expr *rhsp;
5036 tree arg = gimple_call_arg (t, i);
5038 if (TREE_CODE (arg) == SSA_NAME
5039 || is_gimple_min_invariant (arg))
5040 continue;
5042 get_constraint_for_address_of (arg, &rhsc);
5043 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5044 process_constraint (new_constraint (lhs, *rhsp));
5045 rhsc.truncate (0);
5048 /* Build constraints for propagating clobbers/uses along the
5049 callgraph edges. */
5050 cfi = get_fi_for_callee (t);
5051 if (cfi->id == anything_id)
5053 if (gimple_vdef (t))
5054 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5055 anything_id);
5056 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5057 anything_id);
5058 return;
5061 /* For callees without function info (that's external functions),
5062 ESCAPED is clobbered and used. */
5063 if (gimple_call_fndecl (t)
5064 && !cfi->is_fn_info)
5066 varinfo_t vi;
5068 if (gimple_vdef (t))
5069 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5070 escaped_id);
5071 make_copy_constraint (first_vi_for_offset (fi, fi_uses), escaped_id);
5073 /* Also honor the call statement use/clobber info. */
5074 if ((vi = lookup_call_clobber_vi (t)) != NULL)
5075 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5076 vi->id);
5077 if ((vi = lookup_call_use_vi (t)) != NULL)
5078 make_copy_constraint (first_vi_for_offset (fi, fi_uses),
5079 vi->id);
5080 return;
5083 /* Otherwise the caller clobbers and uses what the callee does.
5084 ??? This should use a new complex constraint that filters
5085 local variables of the callee. */
5086 if (gimple_vdef (t))
5088 lhs = get_function_part_constraint (fi, fi_clobbers);
5089 rhs = get_function_part_constraint (cfi, fi_clobbers);
5090 process_constraint (new_constraint (lhs, rhs));
5092 lhs = get_function_part_constraint (fi, fi_uses);
5093 rhs = get_function_part_constraint (cfi, fi_uses);
5094 process_constraint (new_constraint (lhs, rhs));
5096 else if (gimple_code (t) == GIMPLE_ASM)
5098 /* ??? Ick. We can do better. */
5099 if (gimple_vdef (t))
5100 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5101 anything_id);
5102 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5103 anything_id);
5108 /* Find the first varinfo in the same variable as START that overlaps with
5109 OFFSET. Return NULL if we can't find one. */
5111 static varinfo_t
5112 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
5114 /* If the offset is outside of the variable, bail out. */
5115 if (offset >= start->fullsize)
5116 return NULL;
5118 /* If we cannot reach offset from start, lookup the first field
5119 and start from there. */
5120 if (start->offset > offset)
5121 start = get_varinfo (start->head);
5123 while (start)
5125 /* We may not find a variable in the field list with the actual
5126 offset when when we have glommed a structure to a variable.
5127 In that case, however, offset should still be within the size
5128 of the variable. */
5129 if (offset >= start->offset
5130 && (offset - start->offset) < start->size)
5131 return start;
5133 start = vi_next (start);
5136 return NULL;
5139 /* Find the first varinfo in the same variable as START that overlaps with
5140 OFFSET. If there is no such varinfo the varinfo directly preceding
5141 OFFSET is returned. */
5143 static varinfo_t
5144 first_or_preceding_vi_for_offset (varinfo_t start,
5145 unsigned HOST_WIDE_INT offset)
5147 /* If we cannot reach offset from start, lookup the first field
5148 and start from there. */
5149 if (start->offset > offset)
5150 start = get_varinfo (start->head);
5152 /* We may not find a variable in the field list with the actual
5153 offset when when we have glommed a structure to a variable.
5154 In that case, however, offset should still be within the size
5155 of the variable.
5156 If we got beyond the offset we look for return the field
5157 directly preceding offset which may be the last field. */
5158 while (start->next
5159 && offset >= start->offset
5160 && !((offset - start->offset) < start->size))
5161 start = vi_next (start);
5163 return start;
5167 /* This structure is used during pushing fields onto the fieldstack
5168 to track the offset of the field, since bitpos_of_field gives it
5169 relative to its immediate containing type, and we want it relative
5170 to the ultimate containing object. */
5172 struct fieldoff
5174 /* Offset from the base of the base containing object to this field. */
5175 HOST_WIDE_INT offset;
5177 /* Size, in bits, of the field. */
5178 unsigned HOST_WIDE_INT size;
5180 unsigned has_unknown_size : 1;
5182 unsigned must_have_pointers : 1;
5184 unsigned may_have_pointers : 1;
5186 unsigned only_restrict_pointers : 1;
5188 typedef struct fieldoff fieldoff_s;
5191 /* qsort comparison function for two fieldoff's PA and PB */
5193 static int
5194 fieldoff_compare (const void *pa, const void *pb)
5196 const fieldoff_s *foa = (const fieldoff_s *)pa;
5197 const fieldoff_s *fob = (const fieldoff_s *)pb;
5198 unsigned HOST_WIDE_INT foasize, fobsize;
5200 if (foa->offset < fob->offset)
5201 return -1;
5202 else if (foa->offset > fob->offset)
5203 return 1;
5205 foasize = foa->size;
5206 fobsize = fob->size;
5207 if (foasize < fobsize)
5208 return -1;
5209 else if (foasize > fobsize)
5210 return 1;
5211 return 0;
5214 /* Sort a fieldstack according to the field offset and sizes. */
5215 static void
5216 sort_fieldstack (vec<fieldoff_s> fieldstack)
5218 fieldstack.qsort (fieldoff_compare);
5221 /* Return true if T is a type that can have subvars. */
5223 static inline bool
5224 type_can_have_subvars (const_tree t)
5226 /* Aggregates without overlapping fields can have subvars. */
5227 return TREE_CODE (t) == RECORD_TYPE;
5230 /* Return true if V is a tree that we can have subvars for.
5231 Normally, this is any aggregate type. Also complex
5232 types which are not gimple registers can have subvars. */
5234 static inline bool
5235 var_can_have_subvars (const_tree v)
5237 /* Volatile variables should never have subvars. */
5238 if (TREE_THIS_VOLATILE (v))
5239 return false;
5241 /* Non decls or memory tags can never have subvars. */
5242 if (!DECL_P (v))
5243 return false;
5245 return type_can_have_subvars (TREE_TYPE (v));
5248 /* Return true if T is a type that does contain pointers. */
5250 static bool
5251 type_must_have_pointers (tree type)
5253 if (POINTER_TYPE_P (type))
5254 return true;
5256 if (TREE_CODE (type) == ARRAY_TYPE)
5257 return type_must_have_pointers (TREE_TYPE (type));
5259 /* A function or method can have pointers as arguments, so track
5260 those separately. */
5261 if (TREE_CODE (type) == FUNCTION_TYPE
5262 || TREE_CODE (type) == METHOD_TYPE)
5263 return true;
5265 return false;
5268 static bool
5269 field_must_have_pointers (tree t)
5271 return type_must_have_pointers (TREE_TYPE (t));
5274 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5275 the fields of TYPE onto fieldstack, recording their offsets along
5276 the way.
5278 OFFSET is used to keep track of the offset in this entire
5279 structure, rather than just the immediately containing structure.
5280 Returns false if the caller is supposed to handle the field we
5281 recursed for. */
5283 static bool
5284 push_fields_onto_fieldstack (tree type, vec<fieldoff_s> *fieldstack,
5285 HOST_WIDE_INT offset)
5287 tree field;
5288 bool empty_p = true;
5290 if (TREE_CODE (type) != RECORD_TYPE)
5291 return false;
5293 /* If the vector of fields is growing too big, bail out early.
5294 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5295 sure this fails. */
5296 if (fieldstack->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
5297 return false;
5299 for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
5300 if (TREE_CODE (field) == FIELD_DECL)
5302 bool push = false;
5303 HOST_WIDE_INT foff = bitpos_of_field (field);
5305 if (!var_can_have_subvars (field)
5306 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
5307 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
5308 push = true;
5309 else if (!push_fields_onto_fieldstack
5310 (TREE_TYPE (field), fieldstack, offset + foff)
5311 && (DECL_SIZE (field)
5312 && !integer_zerop (DECL_SIZE (field))))
5313 /* Empty structures may have actual size, like in C++. So
5314 see if we didn't push any subfields and the size is
5315 nonzero, push the field onto the stack. */
5316 push = true;
5318 if (push)
5320 fieldoff_s *pair = NULL;
5321 bool has_unknown_size = false;
5322 bool must_have_pointers_p;
5324 if (!fieldstack->is_empty ())
5325 pair = &fieldstack->last ();
5327 /* If there isn't anything at offset zero, create sth. */
5328 if (!pair
5329 && offset + foff != 0)
5331 fieldoff_s e = {0, offset + foff, false, false, false, false};
5332 pair = fieldstack->safe_push (e);
5335 if (!DECL_SIZE (field)
5336 || !tree_fits_uhwi_p (DECL_SIZE (field)))
5337 has_unknown_size = true;
5339 /* If adjacent fields do not contain pointers merge them. */
5340 must_have_pointers_p = field_must_have_pointers (field);
5341 if (pair
5342 && !has_unknown_size
5343 && !must_have_pointers_p
5344 && !pair->must_have_pointers
5345 && !pair->has_unknown_size
5346 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
5348 pair->size += tree_to_uhwi (DECL_SIZE (field));
5350 else
5352 fieldoff_s e;
5353 e.offset = offset + foff;
5354 e.has_unknown_size = has_unknown_size;
5355 if (!has_unknown_size)
5356 e.size = tree_to_uhwi (DECL_SIZE (field));
5357 else
5358 e.size = -1;
5359 e.must_have_pointers = must_have_pointers_p;
5360 e.may_have_pointers = true;
5361 e.only_restrict_pointers
5362 = (!has_unknown_size
5363 && POINTER_TYPE_P (TREE_TYPE (field))
5364 && TYPE_RESTRICT (TREE_TYPE (field)));
5365 fieldstack->safe_push (e);
5369 empty_p = false;
5372 return !empty_p;
5375 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5376 if it is a varargs function. */
5378 static unsigned int
5379 count_num_arguments (tree decl, bool *is_varargs)
5381 unsigned int num = 0;
5382 tree t;
5384 /* Capture named arguments for K&R functions. They do not
5385 have a prototype and thus no TYPE_ARG_TYPES. */
5386 for (t = DECL_ARGUMENTS (decl); t; t = DECL_CHAIN (t))
5387 ++num;
5389 /* Check if the function has variadic arguments. */
5390 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
5391 if (TREE_VALUE (t) == void_type_node)
5392 break;
5393 if (!t)
5394 *is_varargs = true;
5396 return num;
5399 /* Creation function node for DECL, using NAME, and return the index
5400 of the variable we've created for the function. */
5402 static varinfo_t
5403 create_function_info_for (tree decl, const char *name)
5405 struct function *fn = DECL_STRUCT_FUNCTION (decl);
5406 varinfo_t vi, prev_vi;
5407 tree arg;
5408 unsigned int i;
5409 bool is_varargs = false;
5410 unsigned int num_args = count_num_arguments (decl, &is_varargs);
5412 /* Create the variable info. */
5414 vi = new_var_info (decl, name);
5415 vi->offset = 0;
5416 vi->size = 1;
5417 vi->fullsize = fi_parm_base + num_args;
5418 vi->is_fn_info = 1;
5419 vi->may_have_pointers = false;
5420 if (is_varargs)
5421 vi->fullsize = ~0;
5422 insert_vi_for_tree (vi->decl, vi);
5424 prev_vi = vi;
5426 /* Create a variable for things the function clobbers and one for
5427 things the function uses. */
5429 varinfo_t clobbervi, usevi;
5430 const char *newname;
5431 char *tempname;
5433 asprintf (&tempname, "%s.clobber", name);
5434 newname = ggc_strdup (tempname);
5435 free (tempname);
5437 clobbervi = new_var_info (NULL, newname);
5438 clobbervi->offset = fi_clobbers;
5439 clobbervi->size = 1;
5440 clobbervi->fullsize = vi->fullsize;
5441 clobbervi->is_full_var = true;
5442 clobbervi->is_global_var = false;
5443 gcc_assert (prev_vi->offset < clobbervi->offset);
5444 prev_vi->next = clobbervi->id;
5445 prev_vi = clobbervi;
5447 asprintf (&tempname, "%s.use", name);
5448 newname = ggc_strdup (tempname);
5449 free (tempname);
5451 usevi = new_var_info (NULL, newname);
5452 usevi->offset = fi_uses;
5453 usevi->size = 1;
5454 usevi->fullsize = vi->fullsize;
5455 usevi->is_full_var = true;
5456 usevi->is_global_var = false;
5457 gcc_assert (prev_vi->offset < usevi->offset);
5458 prev_vi->next = usevi->id;
5459 prev_vi = usevi;
5462 /* And one for the static chain. */
5463 if (fn->static_chain_decl != NULL_TREE)
5465 varinfo_t chainvi;
5466 const char *newname;
5467 char *tempname;
5469 asprintf (&tempname, "%s.chain", name);
5470 newname = ggc_strdup (tempname);
5471 free (tempname);
5473 chainvi = new_var_info (fn->static_chain_decl, newname);
5474 chainvi->offset = fi_static_chain;
5475 chainvi->size = 1;
5476 chainvi->fullsize = vi->fullsize;
5477 chainvi->is_full_var = true;
5478 chainvi->is_global_var = false;
5479 gcc_assert (prev_vi->offset < chainvi->offset);
5480 prev_vi->next = chainvi->id;
5481 prev_vi = chainvi;
5482 insert_vi_for_tree (fn->static_chain_decl, chainvi);
5485 /* Create a variable for the return var. */
5486 if (DECL_RESULT (decl) != NULL
5487 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
5489 varinfo_t resultvi;
5490 const char *newname;
5491 char *tempname;
5492 tree resultdecl = decl;
5494 if (DECL_RESULT (decl))
5495 resultdecl = DECL_RESULT (decl);
5497 asprintf (&tempname, "%s.result", name);
5498 newname = ggc_strdup (tempname);
5499 free (tempname);
5501 resultvi = new_var_info (resultdecl, newname);
5502 resultvi->offset = fi_result;
5503 resultvi->size = 1;
5504 resultvi->fullsize = vi->fullsize;
5505 resultvi->is_full_var = true;
5506 if (DECL_RESULT (decl))
5507 resultvi->may_have_pointers = true;
5508 gcc_assert (prev_vi->offset < resultvi->offset);
5509 prev_vi->next = resultvi->id;
5510 prev_vi = resultvi;
5511 if (DECL_RESULT (decl))
5512 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
5515 /* Set up variables for each argument. */
5516 arg = DECL_ARGUMENTS (decl);
5517 for (i = 0; i < num_args; i++)
5519 varinfo_t argvi;
5520 const char *newname;
5521 char *tempname;
5522 tree argdecl = decl;
5524 if (arg)
5525 argdecl = arg;
5527 asprintf (&tempname, "%s.arg%d", name, i);
5528 newname = ggc_strdup (tempname);
5529 free (tempname);
5531 argvi = new_var_info (argdecl, newname);
5532 argvi->offset = fi_parm_base + i;
5533 argvi->size = 1;
5534 argvi->is_full_var = true;
5535 argvi->fullsize = vi->fullsize;
5536 if (arg)
5537 argvi->may_have_pointers = true;
5538 gcc_assert (prev_vi->offset < argvi->offset);
5539 prev_vi->next = argvi->id;
5540 prev_vi = argvi;
5541 if (arg)
5543 insert_vi_for_tree (arg, argvi);
5544 arg = DECL_CHAIN (arg);
5548 /* Add one representative for all further args. */
5549 if (is_varargs)
5551 varinfo_t argvi;
5552 const char *newname;
5553 char *tempname;
5554 tree decl;
5556 asprintf (&tempname, "%s.varargs", name);
5557 newname = ggc_strdup (tempname);
5558 free (tempname);
5560 /* We need sth that can be pointed to for va_start. */
5561 decl = build_fake_var_decl (ptr_type_node);
5563 argvi = new_var_info (decl, newname);
5564 argvi->offset = fi_parm_base + num_args;
5565 argvi->size = ~0;
5566 argvi->is_full_var = true;
5567 argvi->is_heap_var = true;
5568 argvi->fullsize = vi->fullsize;
5569 gcc_assert (prev_vi->offset < argvi->offset);
5570 prev_vi->next = argvi->id;
5571 prev_vi = argvi;
5574 return vi;
5578 /* Return true if FIELDSTACK contains fields that overlap.
5579 FIELDSTACK is assumed to be sorted by offset. */
5581 static bool
5582 check_for_overlaps (vec<fieldoff_s> fieldstack)
5584 fieldoff_s *fo = NULL;
5585 unsigned int i;
5586 HOST_WIDE_INT lastoffset = -1;
5588 FOR_EACH_VEC_ELT (fieldstack, i, fo)
5590 if (fo->offset == lastoffset)
5591 return true;
5592 lastoffset = fo->offset;
5594 return false;
5597 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5598 This will also create any varinfo structures necessary for fields
5599 of DECL. */
5601 static varinfo_t
5602 create_variable_info_for_1 (tree decl, const char *name)
5604 varinfo_t vi, newvi;
5605 tree decl_type = TREE_TYPE (decl);
5606 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
5607 auto_vec<fieldoff_s> fieldstack;
5608 fieldoff_s *fo;
5609 unsigned int i;
5610 varpool_node *vnode;
5612 if (!declsize
5613 || !tree_fits_uhwi_p (declsize))
5615 vi = new_var_info (decl, name);
5616 vi->offset = 0;
5617 vi->size = ~0;
5618 vi->fullsize = ~0;
5619 vi->is_unknown_size_var = true;
5620 vi->is_full_var = true;
5621 vi->may_have_pointers = true;
5622 return vi;
5625 /* Collect field information. */
5626 if (use_field_sensitive
5627 && var_can_have_subvars (decl)
5628 /* ??? Force us to not use subfields for global initializers
5629 in IPA mode. Else we'd have to parse arbitrary initializers. */
5630 && !(in_ipa_mode
5631 && is_global_var (decl)
5632 && (vnode = varpool_node::get (decl))
5633 && vnode->get_constructor ()))
5635 fieldoff_s *fo = NULL;
5636 bool notokay = false;
5637 unsigned int i;
5639 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
5641 for (i = 0; !notokay && fieldstack.iterate (i, &fo); i++)
5642 if (fo->has_unknown_size
5643 || fo->offset < 0)
5645 notokay = true;
5646 break;
5649 /* We can't sort them if we have a field with a variable sized type,
5650 which will make notokay = true. In that case, we are going to return
5651 without creating varinfos for the fields anyway, so sorting them is a
5652 waste to boot. */
5653 if (!notokay)
5655 sort_fieldstack (fieldstack);
5656 /* Due to some C++ FE issues, like PR 22488, we might end up
5657 what appear to be overlapping fields even though they,
5658 in reality, do not overlap. Until the C++ FE is fixed,
5659 we will simply disable field-sensitivity for these cases. */
5660 notokay = check_for_overlaps (fieldstack);
5663 if (notokay)
5664 fieldstack.release ();
5667 /* If we didn't end up collecting sub-variables create a full
5668 variable for the decl. */
5669 if (fieldstack.length () <= 1
5670 || fieldstack.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
5672 vi = new_var_info (decl, name);
5673 vi->offset = 0;
5674 vi->may_have_pointers = true;
5675 vi->fullsize = tree_to_uhwi (declsize);
5676 vi->size = vi->fullsize;
5677 vi->is_full_var = true;
5678 fieldstack.release ();
5679 return vi;
5682 vi = new_var_info (decl, name);
5683 vi->fullsize = tree_to_uhwi (declsize);
5684 for (i = 0, newvi = vi;
5685 fieldstack.iterate (i, &fo);
5686 ++i, newvi = vi_next (newvi))
5688 const char *newname = "NULL";
5689 char *tempname;
5691 if (dump_file)
5693 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
5694 "+" HOST_WIDE_INT_PRINT_DEC, name, fo->offset, fo->size);
5695 newname = ggc_strdup (tempname);
5696 free (tempname);
5698 newvi->name = newname;
5699 newvi->offset = fo->offset;
5700 newvi->size = fo->size;
5701 newvi->fullsize = vi->fullsize;
5702 newvi->may_have_pointers = fo->may_have_pointers;
5703 newvi->only_restrict_pointers = fo->only_restrict_pointers;
5704 if (i + 1 < fieldstack.length ())
5706 varinfo_t tem = new_var_info (decl, name);
5707 newvi->next = tem->id;
5708 tem->head = vi->id;
5712 return vi;
5715 static unsigned int
5716 create_variable_info_for (tree decl, const char *name)
5718 varinfo_t vi = create_variable_info_for_1 (decl, name);
5719 unsigned int id = vi->id;
5721 insert_vi_for_tree (decl, vi);
5723 if (TREE_CODE (decl) != VAR_DECL)
5724 return id;
5726 /* Create initial constraints for globals. */
5727 for (; vi; vi = vi_next (vi))
5729 if (!vi->may_have_pointers
5730 || !vi->is_global_var)
5731 continue;
5733 /* Mark global restrict qualified pointers. */
5734 if ((POINTER_TYPE_P (TREE_TYPE (decl))
5735 && TYPE_RESTRICT (TREE_TYPE (decl)))
5736 || vi->only_restrict_pointers)
5738 make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
5739 continue;
5742 /* In non-IPA mode the initializer from nonlocal is all we need. */
5743 if (!in_ipa_mode
5744 || DECL_HARD_REGISTER (decl))
5745 make_copy_constraint (vi, nonlocal_id);
5747 /* In IPA mode parse the initializer and generate proper constraints
5748 for it. */
5749 else
5751 varpool_node *vnode = varpool_node::get (decl);
5753 /* For escaped variables initialize them from nonlocal. */
5754 if (!vnode->all_refs_explicit_p ())
5755 make_copy_constraint (vi, nonlocal_id);
5757 /* If this is a global variable with an initializer and we are in
5758 IPA mode generate constraints for it. */
5759 if (vnode->get_constructor ()
5760 && vnode->definition)
5762 auto_vec<ce_s> rhsc;
5763 struct constraint_expr lhs, *rhsp;
5764 unsigned i;
5765 get_constraint_for_rhs (vnode->get_constructor (), &rhsc);
5766 lhs.var = vi->id;
5767 lhs.offset = 0;
5768 lhs.type = SCALAR;
5769 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5770 process_constraint (new_constraint (lhs, *rhsp));
5771 /* If this is a variable that escapes from the unit
5772 the initializer escapes as well. */
5773 if (!vnode->all_refs_explicit_p ())
5775 lhs.var = escaped_id;
5776 lhs.offset = 0;
5777 lhs.type = SCALAR;
5778 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5779 process_constraint (new_constraint (lhs, *rhsp));
5785 return id;
5788 /* Print out the points-to solution for VAR to FILE. */
5790 static void
5791 dump_solution_for_var (FILE *file, unsigned int var)
5793 varinfo_t vi = get_varinfo (var);
5794 unsigned int i;
5795 bitmap_iterator bi;
5797 /* Dump the solution for unified vars anyway, this avoids difficulties
5798 in scanning dumps in the testsuite. */
5799 fprintf (file, "%s = { ", vi->name);
5800 vi = get_varinfo (find (var));
5801 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5802 fprintf (file, "%s ", get_varinfo (i)->name);
5803 fprintf (file, "}");
5805 /* But note when the variable was unified. */
5806 if (vi->id != var)
5807 fprintf (file, " same as %s", vi->name);
5809 fprintf (file, "\n");
5812 /* Print the points-to solution for VAR to stderr. */
5814 DEBUG_FUNCTION void
5815 debug_solution_for_var (unsigned int var)
5817 dump_solution_for_var (stderr, var);
5820 /* Create varinfo structures for all of the variables in the
5821 function for intraprocedural mode. */
5823 static void
5824 intra_create_variable_infos (struct function *fn)
5826 tree t;
5828 /* For each incoming pointer argument arg, create the constraint ARG
5829 = NONLOCAL or a dummy variable if it is a restrict qualified
5830 passed-by-reference argument. */
5831 for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t))
5833 varinfo_t p = get_vi_for_tree (t);
5835 /* For restrict qualified pointers to objects passed by
5836 reference build a real representative for the pointed-to object.
5837 Treat restrict qualified references the same. */
5838 if (TYPE_RESTRICT (TREE_TYPE (t))
5839 && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
5840 || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
5841 && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
5843 struct constraint_expr lhsc, rhsc;
5844 varinfo_t vi;
5845 tree heapvar = build_fake_var_decl (TREE_TYPE (TREE_TYPE (t)));
5846 DECL_EXTERNAL (heapvar) = 1;
5847 vi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS");
5848 insert_vi_for_tree (heapvar, vi);
5849 lhsc.var = p->id;
5850 lhsc.type = SCALAR;
5851 lhsc.offset = 0;
5852 rhsc.var = vi->id;
5853 rhsc.type = ADDRESSOF;
5854 rhsc.offset = 0;
5855 process_constraint (new_constraint (lhsc, rhsc));
5856 for (; vi; vi = vi_next (vi))
5857 if (vi->may_have_pointers)
5859 if (vi->only_restrict_pointers)
5860 make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
5861 else
5862 make_copy_constraint (vi, nonlocal_id);
5864 continue;
5867 if (POINTER_TYPE_P (TREE_TYPE (t))
5868 && TYPE_RESTRICT (TREE_TYPE (t)))
5869 make_constraint_from_global_restrict (p, "PARM_RESTRICT");
5870 else
5872 for (; p; p = vi_next (p))
5874 if (p->only_restrict_pointers)
5875 make_constraint_from_global_restrict (p, "PARM_RESTRICT");
5876 else if (p->may_have_pointers)
5877 make_constraint_from (p, nonlocal_id);
5882 /* Add a constraint for a result decl that is passed by reference. */
5883 if (DECL_RESULT (fn->decl)
5884 && DECL_BY_REFERENCE (DECL_RESULT (fn->decl)))
5886 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (fn->decl));
5888 for (p = result_vi; p; p = vi_next (p))
5889 make_constraint_from (p, nonlocal_id);
5892 /* Add a constraint for the incoming static chain parameter. */
5893 if (fn->static_chain_decl != NULL_TREE)
5895 varinfo_t p, chain_vi = get_vi_for_tree (fn->static_chain_decl);
5897 for (p = chain_vi; p; p = vi_next (p))
5898 make_constraint_from (p, nonlocal_id);
5902 /* Structure used to put solution bitmaps in a hashtable so they can
5903 be shared among variables with the same points-to set. */
5905 typedef struct shared_bitmap_info
5907 bitmap pt_vars;
5908 hashval_t hashcode;
5909 } *shared_bitmap_info_t;
5910 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
5912 /* Shared_bitmap hashtable helpers. */
5914 struct shared_bitmap_hasher : typed_free_remove <shared_bitmap_info>
5916 typedef shared_bitmap_info value_type;
5917 typedef shared_bitmap_info compare_type;
5918 static inline hashval_t hash (const value_type *);
5919 static inline bool equal (const value_type *, const compare_type *);
5922 /* Hash function for a shared_bitmap_info_t */
5924 inline hashval_t
5925 shared_bitmap_hasher::hash (const value_type *bi)
5927 return bi->hashcode;
5930 /* Equality function for two shared_bitmap_info_t's. */
5932 inline bool
5933 shared_bitmap_hasher::equal (const value_type *sbi1, const compare_type *sbi2)
5935 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
5938 /* Shared_bitmap hashtable. */
5940 static hash_table<shared_bitmap_hasher> *shared_bitmap_table;
5942 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
5943 existing instance if there is one, NULL otherwise. */
5945 static bitmap
5946 shared_bitmap_lookup (bitmap pt_vars)
5948 shared_bitmap_info **slot;
5949 struct shared_bitmap_info sbi;
5951 sbi.pt_vars = pt_vars;
5952 sbi.hashcode = bitmap_hash (pt_vars);
5954 slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
5955 if (!slot)
5956 return NULL;
5957 else
5958 return (*slot)->pt_vars;
5962 /* Add a bitmap to the shared bitmap hashtable. */
5964 static void
5965 shared_bitmap_add (bitmap pt_vars)
5967 shared_bitmap_info **slot;
5968 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
5970 sbi->pt_vars = pt_vars;
5971 sbi->hashcode = bitmap_hash (pt_vars);
5973 slot = shared_bitmap_table->find_slot (sbi, INSERT);
5974 gcc_assert (!*slot);
5975 *slot = sbi;
5979 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
5981 static void
5982 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt)
5984 unsigned int i;
5985 bitmap_iterator bi;
5986 varinfo_t escaped_vi = get_varinfo (find (escaped_id));
5987 bool everything_escaped
5988 = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
5990 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
5992 varinfo_t vi = get_varinfo (i);
5994 /* The only artificial variables that are allowed in a may-alias
5995 set are heap variables. */
5996 if (vi->is_artificial_var && !vi->is_heap_var)
5997 continue;
5999 if (everything_escaped
6000 || (escaped_vi->solution
6001 && bitmap_bit_p (escaped_vi->solution, i)))
6003 pt->vars_contains_escaped = true;
6004 pt->vars_contains_escaped_heap = vi->is_heap_var;
6007 if (TREE_CODE (vi->decl) == VAR_DECL
6008 || TREE_CODE (vi->decl) == PARM_DECL
6009 || TREE_CODE (vi->decl) == RESULT_DECL)
6011 /* If we are in IPA mode we will not recompute points-to
6012 sets after inlining so make sure they stay valid. */
6013 if (in_ipa_mode
6014 && !DECL_PT_UID_SET_P (vi->decl))
6015 SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
6017 /* Add the decl to the points-to set. Note that the points-to
6018 set contains global variables. */
6019 bitmap_set_bit (into, DECL_PT_UID (vi->decl));
6020 if (vi->is_global_var)
6021 pt->vars_contains_nonlocal = true;
6027 /* Compute the points-to solution *PT for the variable VI. */
6029 static struct pt_solution
6030 find_what_var_points_to (varinfo_t orig_vi)
6032 unsigned int i;
6033 bitmap_iterator bi;
6034 bitmap finished_solution;
6035 bitmap result;
6036 varinfo_t vi;
6037 struct pt_solution *pt;
6039 /* This variable may have been collapsed, let's get the real
6040 variable. */
6041 vi = get_varinfo (find (orig_vi->id));
6043 /* See if we have already computed the solution and return it. */
6044 pt_solution **slot = &final_solutions->get_or_insert (vi);
6045 if (*slot != NULL)
6046 return **slot;
6048 *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
6049 memset (pt, 0, sizeof (struct pt_solution));
6051 /* Translate artificial variables into SSA_NAME_PTR_INFO
6052 attributes. */
6053 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
6055 varinfo_t vi = get_varinfo (i);
6057 if (vi->is_artificial_var)
6059 if (vi->id == nothing_id)
6060 pt->null = 1;
6061 else if (vi->id == escaped_id)
6063 if (in_ipa_mode)
6064 pt->ipa_escaped = 1;
6065 else
6066 pt->escaped = 1;
6067 /* Expand some special vars of ESCAPED in-place here. */
6068 varinfo_t evi = get_varinfo (find (escaped_id));
6069 if (bitmap_bit_p (evi->solution, nonlocal_id))
6070 pt->nonlocal = 1;
6072 else if (vi->id == nonlocal_id)
6073 pt->nonlocal = 1;
6074 else if (vi->is_heap_var)
6075 /* We represent heapvars in the points-to set properly. */
6077 else if (vi->id == string_id)
6078 /* Nobody cares - STRING_CSTs are read-only entities. */
6080 else if (vi->id == anything_id
6081 || vi->id == integer_id)
6082 pt->anything = 1;
6086 /* Instead of doing extra work, simply do not create
6087 elaborate points-to information for pt_anything pointers. */
6088 if (pt->anything)
6089 return *pt;
6091 /* Share the final set of variables when possible. */
6092 finished_solution = BITMAP_GGC_ALLOC ();
6093 stats.points_to_sets_created++;
6095 set_uids_in_ptset (finished_solution, vi->solution, pt);
6096 result = shared_bitmap_lookup (finished_solution);
6097 if (!result)
6099 shared_bitmap_add (finished_solution);
6100 pt->vars = finished_solution;
6102 else
6104 pt->vars = result;
6105 bitmap_clear (finished_solution);
6108 return *pt;
6111 /* Given a pointer variable P, fill in its points-to set. */
6113 static void
6114 find_what_p_points_to (tree p)
6116 struct ptr_info_def *pi;
6117 tree lookup_p = p;
6118 varinfo_t vi;
6120 /* For parameters, get at the points-to set for the actual parm
6121 decl. */
6122 if (TREE_CODE (p) == SSA_NAME
6123 && SSA_NAME_IS_DEFAULT_DEF (p)
6124 && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
6125 || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
6126 lookup_p = SSA_NAME_VAR (p);
6128 vi = lookup_vi_for_tree (lookup_p);
6129 if (!vi)
6130 return;
6132 pi = get_ptr_info (p);
6133 pi->pt = find_what_var_points_to (vi);
6137 /* Query statistics for points-to solutions. */
6139 static struct {
6140 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
6141 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
6142 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
6143 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
6144 } pta_stats;
6146 void
6147 dump_pta_stats (FILE *s)
6149 fprintf (s, "\nPTA query stats:\n");
6150 fprintf (s, " pt_solution_includes: "
6151 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6152 HOST_WIDE_INT_PRINT_DEC" queries\n",
6153 pta_stats.pt_solution_includes_no_alias,
6154 pta_stats.pt_solution_includes_no_alias
6155 + pta_stats.pt_solution_includes_may_alias);
6156 fprintf (s, " pt_solutions_intersect: "
6157 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6158 HOST_WIDE_INT_PRINT_DEC" queries\n",
6159 pta_stats.pt_solutions_intersect_no_alias,
6160 pta_stats.pt_solutions_intersect_no_alias
6161 + pta_stats.pt_solutions_intersect_may_alias);
6165 /* Reset the points-to solution *PT to a conservative default
6166 (point to anything). */
6168 void
6169 pt_solution_reset (struct pt_solution *pt)
6171 memset (pt, 0, sizeof (struct pt_solution));
6172 pt->anything = true;
6175 /* Set the points-to solution *PT to point only to the variables
6176 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6177 global variables and VARS_CONTAINS_RESTRICT specifies whether
6178 it contains restrict tag variables. */
6180 void
6181 pt_solution_set (struct pt_solution *pt, bitmap vars,
6182 bool vars_contains_nonlocal)
6184 memset (pt, 0, sizeof (struct pt_solution));
6185 pt->vars = vars;
6186 pt->vars_contains_nonlocal = vars_contains_nonlocal;
6187 pt->vars_contains_escaped
6188 = (cfun->gimple_df->escaped.anything
6189 || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
6192 /* Set the points-to solution *PT to point only to the variable VAR. */
6194 void
6195 pt_solution_set_var (struct pt_solution *pt, tree var)
6197 memset (pt, 0, sizeof (struct pt_solution));
6198 pt->vars = BITMAP_GGC_ALLOC ();
6199 bitmap_set_bit (pt->vars, DECL_PT_UID (var));
6200 pt->vars_contains_nonlocal = is_global_var (var);
6201 pt->vars_contains_escaped
6202 = (cfun->gimple_df->escaped.anything
6203 || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
6206 /* Computes the union of the points-to solutions *DEST and *SRC and
6207 stores the result in *DEST. This changes the points-to bitmap
6208 of *DEST and thus may not be used if that might be shared.
6209 The points-to bitmap of *SRC and *DEST will not be shared after
6210 this function if they were not before. */
6212 static void
6213 pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
6215 dest->anything |= src->anything;
6216 if (dest->anything)
6218 pt_solution_reset (dest);
6219 return;
6222 dest->nonlocal |= src->nonlocal;
6223 dest->escaped |= src->escaped;
6224 dest->ipa_escaped |= src->ipa_escaped;
6225 dest->null |= src->null;
6226 dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
6227 dest->vars_contains_escaped |= src->vars_contains_escaped;
6228 dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
6229 if (!src->vars)
6230 return;
6232 if (!dest->vars)
6233 dest->vars = BITMAP_GGC_ALLOC ();
6234 bitmap_ior_into (dest->vars, src->vars);
6237 /* Return true if the points-to solution *PT is empty. */
6239 bool
6240 pt_solution_empty_p (struct pt_solution *pt)
6242 if (pt->anything
6243 || pt->nonlocal)
6244 return false;
6246 if (pt->vars
6247 && !bitmap_empty_p (pt->vars))
6248 return false;
6250 /* If the solution includes ESCAPED, check if that is empty. */
6251 if (pt->escaped
6252 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
6253 return false;
6255 /* If the solution includes ESCAPED, check if that is empty. */
6256 if (pt->ipa_escaped
6257 && !pt_solution_empty_p (&ipa_escaped_pt))
6258 return false;
6260 return true;
6263 /* Return true if the points-to solution *PT only point to a single var, and
6264 return the var uid in *UID. */
6266 bool
6267 pt_solution_singleton_p (struct pt_solution *pt, unsigned *uid)
6269 if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
6270 || pt->null || pt->vars == NULL
6271 || !bitmap_single_bit_set_p (pt->vars))
6272 return false;
6274 *uid = bitmap_first_set_bit (pt->vars);
6275 return true;
6278 /* Return true if the points-to solution *PT includes global memory. */
6280 bool
6281 pt_solution_includes_global (struct pt_solution *pt)
6283 if (pt->anything
6284 || pt->nonlocal
6285 || pt->vars_contains_nonlocal
6286 /* The following is a hack to make the malloc escape hack work.
6287 In reality we'd need different sets for escaped-through-return
6288 and escaped-to-callees and passes would need to be updated. */
6289 || pt->vars_contains_escaped_heap)
6290 return true;
6292 /* 'escaped' is also a placeholder so we have to look into it. */
6293 if (pt->escaped)
6294 return pt_solution_includes_global (&cfun->gimple_df->escaped);
6296 if (pt->ipa_escaped)
6297 return pt_solution_includes_global (&ipa_escaped_pt);
6299 /* ??? This predicate is not correct for the IPA-PTA solution
6300 as we do not properly distinguish between unit escape points
6301 and global variables. */
6302 if (cfun->gimple_df->ipa_pta)
6303 return true;
6305 return false;
6308 /* Return true if the points-to solution *PT includes the variable
6309 declaration DECL. */
6311 static bool
6312 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
6314 if (pt->anything)
6315 return true;
6317 if (pt->nonlocal
6318 && is_global_var (decl))
6319 return true;
6321 if (pt->vars
6322 && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
6323 return true;
6325 /* If the solution includes ESCAPED, check it. */
6326 if (pt->escaped
6327 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
6328 return true;
6330 /* If the solution includes ESCAPED, check it. */
6331 if (pt->ipa_escaped
6332 && pt_solution_includes_1 (&ipa_escaped_pt, decl))
6333 return true;
6335 return false;
6338 bool
6339 pt_solution_includes (struct pt_solution *pt, const_tree decl)
6341 bool res = pt_solution_includes_1 (pt, decl);
6342 if (res)
6343 ++pta_stats.pt_solution_includes_may_alias;
6344 else
6345 ++pta_stats.pt_solution_includes_no_alias;
6346 return res;
6349 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6350 intersection. */
6352 static bool
6353 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
6355 if (pt1->anything || pt2->anything)
6356 return true;
6358 /* If either points to unknown global memory and the other points to
6359 any global memory they alias. */
6360 if ((pt1->nonlocal
6361 && (pt2->nonlocal
6362 || pt2->vars_contains_nonlocal))
6363 || (pt2->nonlocal
6364 && pt1->vars_contains_nonlocal))
6365 return true;
6367 /* If either points to all escaped memory and the other points to
6368 any escaped memory they alias. */
6369 if ((pt1->escaped
6370 && (pt2->escaped
6371 || pt2->vars_contains_escaped))
6372 || (pt2->escaped
6373 && pt1->vars_contains_escaped))
6374 return true;
6376 /* Check the escaped solution if required.
6377 ??? Do we need to check the local against the IPA escaped sets? */
6378 if ((pt1->ipa_escaped || pt2->ipa_escaped)
6379 && !pt_solution_empty_p (&ipa_escaped_pt))
6381 /* If both point to escaped memory and that solution
6382 is not empty they alias. */
6383 if (pt1->ipa_escaped && pt2->ipa_escaped)
6384 return true;
6386 /* If either points to escaped memory see if the escaped solution
6387 intersects with the other. */
6388 if ((pt1->ipa_escaped
6389 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
6390 || (pt2->ipa_escaped
6391 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
6392 return true;
6395 /* Now both pointers alias if their points-to solution intersects. */
6396 return (pt1->vars
6397 && pt2->vars
6398 && bitmap_intersect_p (pt1->vars, pt2->vars));
6401 bool
6402 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
6404 bool res = pt_solutions_intersect_1 (pt1, pt2);
6405 if (res)
6406 ++pta_stats.pt_solutions_intersect_may_alias;
6407 else
6408 ++pta_stats.pt_solutions_intersect_no_alias;
6409 return res;
6413 /* Dump points-to information to OUTFILE. */
6415 static void
6416 dump_sa_points_to_info (FILE *outfile)
6418 unsigned int i;
6420 fprintf (outfile, "\nPoints-to sets\n\n");
6422 if (dump_flags & TDF_STATS)
6424 fprintf (outfile, "Stats:\n");
6425 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
6426 fprintf (outfile, "Non-pointer vars: %d\n",
6427 stats.nonpointer_vars);
6428 fprintf (outfile, "Statically unified vars: %d\n",
6429 stats.unified_vars_static);
6430 fprintf (outfile, "Dynamically unified vars: %d\n",
6431 stats.unified_vars_dynamic);
6432 fprintf (outfile, "Iterations: %d\n", stats.iterations);
6433 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
6434 fprintf (outfile, "Number of implicit edges: %d\n",
6435 stats.num_implicit_edges);
6438 for (i = 1; i < varmap.length (); i++)
6440 varinfo_t vi = get_varinfo (i);
6441 if (!vi->may_have_pointers)
6442 continue;
6443 dump_solution_for_var (outfile, i);
6448 /* Debug points-to information to stderr. */
6450 DEBUG_FUNCTION void
6451 debug_sa_points_to_info (void)
6453 dump_sa_points_to_info (stderr);
6457 /* Initialize the always-existing constraint variables for NULL
6458 ANYTHING, READONLY, and INTEGER */
6460 static void
6461 init_base_vars (void)
6463 struct constraint_expr lhs, rhs;
6464 varinfo_t var_anything;
6465 varinfo_t var_nothing;
6466 varinfo_t var_string;
6467 varinfo_t var_escaped;
6468 varinfo_t var_nonlocal;
6469 varinfo_t var_storedanything;
6470 varinfo_t var_integer;
6472 /* Variable ID zero is reserved and should be NULL. */
6473 varmap.safe_push (NULL);
6475 /* Create the NULL variable, used to represent that a variable points
6476 to NULL. */
6477 var_nothing = new_var_info (NULL_TREE, "NULL");
6478 gcc_assert (var_nothing->id == nothing_id);
6479 var_nothing->is_artificial_var = 1;
6480 var_nothing->offset = 0;
6481 var_nothing->size = ~0;
6482 var_nothing->fullsize = ~0;
6483 var_nothing->is_special_var = 1;
6484 var_nothing->may_have_pointers = 0;
6485 var_nothing->is_global_var = 0;
6487 /* Create the ANYTHING variable, used to represent that a variable
6488 points to some unknown piece of memory. */
6489 var_anything = new_var_info (NULL_TREE, "ANYTHING");
6490 gcc_assert (var_anything->id == anything_id);
6491 var_anything->is_artificial_var = 1;
6492 var_anything->size = ~0;
6493 var_anything->offset = 0;
6494 var_anything->fullsize = ~0;
6495 var_anything->is_special_var = 1;
6497 /* Anything points to anything. This makes deref constraints just
6498 work in the presence of linked list and other p = *p type loops,
6499 by saying that *ANYTHING = ANYTHING. */
6500 lhs.type = SCALAR;
6501 lhs.var = anything_id;
6502 lhs.offset = 0;
6503 rhs.type = ADDRESSOF;
6504 rhs.var = anything_id;
6505 rhs.offset = 0;
6507 /* This specifically does not use process_constraint because
6508 process_constraint ignores all anything = anything constraints, since all
6509 but this one are redundant. */
6510 constraints.safe_push (new_constraint (lhs, rhs));
6512 /* Create the STRING variable, used to represent that a variable
6513 points to a string literal. String literals don't contain
6514 pointers so STRING doesn't point to anything. */
6515 var_string = new_var_info (NULL_TREE, "STRING");
6516 gcc_assert (var_string->id == string_id);
6517 var_string->is_artificial_var = 1;
6518 var_string->offset = 0;
6519 var_string->size = ~0;
6520 var_string->fullsize = ~0;
6521 var_string->is_special_var = 1;
6522 var_string->may_have_pointers = 0;
6524 /* Create the ESCAPED variable, used to represent the set of escaped
6525 memory. */
6526 var_escaped = new_var_info (NULL_TREE, "ESCAPED");
6527 gcc_assert (var_escaped->id == escaped_id);
6528 var_escaped->is_artificial_var = 1;
6529 var_escaped->offset = 0;
6530 var_escaped->size = ~0;
6531 var_escaped->fullsize = ~0;
6532 var_escaped->is_special_var = 0;
6534 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6535 memory. */
6536 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL");
6537 gcc_assert (var_nonlocal->id == nonlocal_id);
6538 var_nonlocal->is_artificial_var = 1;
6539 var_nonlocal->offset = 0;
6540 var_nonlocal->size = ~0;
6541 var_nonlocal->fullsize = ~0;
6542 var_nonlocal->is_special_var = 1;
6544 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6545 lhs.type = SCALAR;
6546 lhs.var = escaped_id;
6547 lhs.offset = 0;
6548 rhs.type = DEREF;
6549 rhs.var = escaped_id;
6550 rhs.offset = 0;
6551 process_constraint (new_constraint (lhs, rhs));
6553 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6554 whole variable escapes. */
6555 lhs.type = SCALAR;
6556 lhs.var = escaped_id;
6557 lhs.offset = 0;
6558 rhs.type = SCALAR;
6559 rhs.var = escaped_id;
6560 rhs.offset = UNKNOWN_OFFSET;
6561 process_constraint (new_constraint (lhs, rhs));
6563 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6564 everything pointed to by escaped points to what global memory can
6565 point to. */
6566 lhs.type = DEREF;
6567 lhs.var = escaped_id;
6568 lhs.offset = 0;
6569 rhs.type = SCALAR;
6570 rhs.var = nonlocal_id;
6571 rhs.offset = 0;
6572 process_constraint (new_constraint (lhs, rhs));
6574 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6575 global memory may point to global memory and escaped memory. */
6576 lhs.type = SCALAR;
6577 lhs.var = nonlocal_id;
6578 lhs.offset = 0;
6579 rhs.type = ADDRESSOF;
6580 rhs.var = nonlocal_id;
6581 rhs.offset = 0;
6582 process_constraint (new_constraint (lhs, rhs));
6583 rhs.type = ADDRESSOF;
6584 rhs.var = escaped_id;
6585 rhs.offset = 0;
6586 process_constraint (new_constraint (lhs, rhs));
6588 /* Create the STOREDANYTHING variable, used to represent the set of
6589 variables stored to *ANYTHING. */
6590 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING");
6591 gcc_assert (var_storedanything->id == storedanything_id);
6592 var_storedanything->is_artificial_var = 1;
6593 var_storedanything->offset = 0;
6594 var_storedanything->size = ~0;
6595 var_storedanything->fullsize = ~0;
6596 var_storedanything->is_special_var = 0;
6598 /* Create the INTEGER variable, used to represent that a variable points
6599 to what an INTEGER "points to". */
6600 var_integer = new_var_info (NULL_TREE, "INTEGER");
6601 gcc_assert (var_integer->id == integer_id);
6602 var_integer->is_artificial_var = 1;
6603 var_integer->size = ~0;
6604 var_integer->fullsize = ~0;
6605 var_integer->offset = 0;
6606 var_integer->is_special_var = 1;
6608 /* INTEGER = ANYTHING, because we don't know where a dereference of
6609 a random integer will point to. */
6610 lhs.type = SCALAR;
6611 lhs.var = integer_id;
6612 lhs.offset = 0;
6613 rhs.type = ADDRESSOF;
6614 rhs.var = anything_id;
6615 rhs.offset = 0;
6616 process_constraint (new_constraint (lhs, rhs));
6619 /* Initialize things necessary to perform PTA */
6621 static void
6622 init_alias_vars (void)
6624 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
6626 bitmap_obstack_initialize (&pta_obstack);
6627 bitmap_obstack_initialize (&oldpta_obstack);
6628 bitmap_obstack_initialize (&predbitmap_obstack);
6630 constraint_pool = create_alloc_pool ("Constraint pool",
6631 sizeof (struct constraint), 30);
6632 variable_info_pool = create_alloc_pool ("Variable info pool",
6633 sizeof (struct variable_info), 30);
6634 constraints.create (8);
6635 varmap.create (8);
6636 vi_for_tree = new hash_map<tree, varinfo_t>;
6637 call_stmt_vars = new hash_map<gimple, varinfo_t>;
6639 memset (&stats, 0, sizeof (stats));
6640 shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
6641 init_base_vars ();
6643 gcc_obstack_init (&fake_var_decl_obstack);
6645 final_solutions = new hash_map<varinfo_t, pt_solution *>;
6646 gcc_obstack_init (&final_solutions_obstack);
6649 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6650 predecessor edges. */
6652 static void
6653 remove_preds_and_fake_succs (constraint_graph_t graph)
6655 unsigned int i;
6657 /* Clear the implicit ref and address nodes from the successor
6658 lists. */
6659 for (i = 1; i < FIRST_REF_NODE; i++)
6661 if (graph->succs[i])
6662 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
6663 FIRST_REF_NODE * 2);
6666 /* Free the successor list for the non-ref nodes. */
6667 for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
6669 if (graph->succs[i])
6670 BITMAP_FREE (graph->succs[i]);
6673 /* Now reallocate the size of the successor list as, and blow away
6674 the predecessor bitmaps. */
6675 graph->size = varmap.length ();
6676 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
6678 free (graph->implicit_preds);
6679 graph->implicit_preds = NULL;
6680 free (graph->preds);
6681 graph->preds = NULL;
6682 bitmap_obstack_release (&predbitmap_obstack);
6685 /* Solve the constraint set. */
6687 static void
6688 solve_constraints (void)
6690 struct scc_info *si;
6692 if (dump_file)
6693 fprintf (dump_file,
6694 "\nCollapsing static cycles and doing variable "
6695 "substitution\n");
6697 init_graph (varmap.length () * 2);
6699 if (dump_file)
6700 fprintf (dump_file, "Building predecessor graph\n");
6701 build_pred_graph ();
6703 if (dump_file)
6704 fprintf (dump_file, "Detecting pointer and location "
6705 "equivalences\n");
6706 si = perform_var_substitution (graph);
6708 if (dump_file)
6709 fprintf (dump_file, "Rewriting constraints and unifying "
6710 "variables\n");
6711 rewrite_constraints (graph, si);
6713 build_succ_graph ();
6715 free_var_substitution_info (si);
6717 /* Attach complex constraints to graph nodes. */
6718 move_complex_constraints (graph);
6720 if (dump_file)
6721 fprintf (dump_file, "Uniting pointer but not location equivalent "
6722 "variables\n");
6723 unite_pointer_equivalences (graph);
6725 if (dump_file)
6726 fprintf (dump_file, "Finding indirect cycles\n");
6727 find_indirect_cycles (graph);
6729 /* Implicit nodes and predecessors are no longer necessary at this
6730 point. */
6731 remove_preds_and_fake_succs (graph);
6733 if (dump_file && (dump_flags & TDF_GRAPH))
6735 fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
6736 "in dot format:\n");
6737 dump_constraint_graph (dump_file);
6738 fprintf (dump_file, "\n\n");
6741 if (dump_file)
6742 fprintf (dump_file, "Solving graph\n");
6744 solve_graph (graph);
6746 if (dump_file && (dump_flags & TDF_GRAPH))
6748 fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
6749 "in dot format:\n");
6750 dump_constraint_graph (dump_file);
6751 fprintf (dump_file, "\n\n");
6754 if (dump_file)
6755 dump_sa_points_to_info (dump_file);
6758 /* Create points-to sets for the current function. See the comments
6759 at the start of the file for an algorithmic overview. */
6761 static void
6762 compute_points_to_sets (void)
6764 basic_block bb;
6765 unsigned i;
6766 varinfo_t vi;
6768 timevar_push (TV_TREE_PTA);
6770 init_alias_vars ();
6772 intra_create_variable_infos (cfun);
6774 /* Now walk all statements and build the constraint set. */
6775 FOR_EACH_BB_FN (bb, cfun)
6777 gimple_stmt_iterator gsi;
6779 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6781 gimple phi = gsi_stmt (gsi);
6783 if (! virtual_operand_p (gimple_phi_result (phi)))
6784 find_func_aliases (cfun, phi);
6787 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6789 gimple stmt = gsi_stmt (gsi);
6791 find_func_aliases (cfun, stmt);
6795 if (dump_file)
6797 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
6798 dump_constraints (dump_file, 0);
6801 /* From the constraints compute the points-to sets. */
6802 solve_constraints ();
6804 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
6805 cfun->gimple_df->escaped = find_what_var_points_to (get_varinfo (escaped_id));
6807 /* Make sure the ESCAPED solution (which is used as placeholder in
6808 other solutions) does not reference itself. This simplifies
6809 points-to solution queries. */
6810 cfun->gimple_df->escaped.escaped = 0;
6812 /* Compute the points-to sets for pointer SSA_NAMEs. */
6813 for (i = 0; i < num_ssa_names; ++i)
6815 tree ptr = ssa_name (i);
6816 if (ptr
6817 && POINTER_TYPE_P (TREE_TYPE (ptr)))
6818 find_what_p_points_to (ptr);
6821 /* Compute the call-used/clobbered sets. */
6822 FOR_EACH_BB_FN (bb, cfun)
6824 gimple_stmt_iterator gsi;
6826 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6828 gimple stmt = gsi_stmt (gsi);
6829 struct pt_solution *pt;
6830 if (!is_gimple_call (stmt))
6831 continue;
6833 pt = gimple_call_use_set (stmt);
6834 if (gimple_call_flags (stmt) & ECF_CONST)
6835 memset (pt, 0, sizeof (struct pt_solution));
6836 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
6838 *pt = find_what_var_points_to (vi);
6839 /* Escaped (and thus nonlocal) variables are always
6840 implicitly used by calls. */
6841 /* ??? ESCAPED can be empty even though NONLOCAL
6842 always escaped. */
6843 pt->nonlocal = 1;
6844 pt->escaped = 1;
6846 else
6848 /* If there is nothing special about this call then
6849 we have made everything that is used also escape. */
6850 *pt = cfun->gimple_df->escaped;
6851 pt->nonlocal = 1;
6854 pt = gimple_call_clobber_set (stmt);
6855 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
6856 memset (pt, 0, sizeof (struct pt_solution));
6857 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
6859 *pt = find_what_var_points_to (vi);
6860 /* Escaped (and thus nonlocal) variables are always
6861 implicitly clobbered by calls. */
6862 /* ??? ESCAPED can be empty even though NONLOCAL
6863 always escaped. */
6864 pt->nonlocal = 1;
6865 pt->escaped = 1;
6867 else
6869 /* If there is nothing special about this call then
6870 we have made everything that is used also escape. */
6871 *pt = cfun->gimple_df->escaped;
6872 pt->nonlocal = 1;
6877 timevar_pop (TV_TREE_PTA);
6881 /* Delete created points-to sets. */
6883 static void
6884 delete_points_to_sets (void)
6886 unsigned int i;
6888 delete shared_bitmap_table;
6889 shared_bitmap_table = NULL;
6890 if (dump_file && (dump_flags & TDF_STATS))
6891 fprintf (dump_file, "Points to sets created:%d\n",
6892 stats.points_to_sets_created);
6894 delete vi_for_tree;
6895 delete call_stmt_vars;
6896 bitmap_obstack_release (&pta_obstack);
6897 constraints.release ();
6899 for (i = 0; i < graph->size; i++)
6900 graph->complex[i].release ();
6901 free (graph->complex);
6903 free (graph->rep);
6904 free (graph->succs);
6905 free (graph->pe);
6906 free (graph->pe_rep);
6907 free (graph->indirect_cycles);
6908 free (graph);
6910 varmap.release ();
6911 free_alloc_pool (variable_info_pool);
6912 free_alloc_pool (constraint_pool);
6914 obstack_free (&fake_var_decl_obstack, NULL);
6916 delete final_solutions;
6917 obstack_free (&final_solutions_obstack, NULL);
6921 /* Compute points-to information for every SSA_NAME pointer in the
6922 current function and compute the transitive closure of escaped
6923 variables to re-initialize the call-clobber states of local variables. */
6925 unsigned int
6926 compute_may_aliases (void)
6928 if (cfun->gimple_df->ipa_pta)
6930 if (dump_file)
6932 fprintf (dump_file, "\nNot re-computing points-to information "
6933 "because IPA points-to information is available.\n\n");
6935 /* But still dump what we have remaining it. */
6936 dump_alias_info (dump_file);
6939 return 0;
6942 /* For each pointer P_i, determine the sets of variables that P_i may
6943 point-to. Compute the reachability set of escaped and call-used
6944 variables. */
6945 compute_points_to_sets ();
6947 /* Debugging dumps. */
6948 if (dump_file)
6949 dump_alias_info (dump_file);
6951 /* Deallocate memory used by aliasing data structures and the internal
6952 points-to solution. */
6953 delete_points_to_sets ();
6955 gcc_assert (!need_ssa_update_p (cfun));
6957 return 0;
6960 /* A dummy pass to cause points-to information to be computed via
6961 TODO_rebuild_alias. */
6963 namespace {
6965 const pass_data pass_data_build_alias =
6967 GIMPLE_PASS, /* type */
6968 "alias", /* name */
6969 OPTGROUP_NONE, /* optinfo_flags */
6970 TV_NONE, /* tv_id */
6971 ( PROP_cfg | PROP_ssa ), /* properties_required */
6972 0, /* properties_provided */
6973 0, /* properties_destroyed */
6974 0, /* todo_flags_start */
6975 TODO_rebuild_alias, /* todo_flags_finish */
6978 class pass_build_alias : public gimple_opt_pass
6980 public:
6981 pass_build_alias (gcc::context *ctxt)
6982 : gimple_opt_pass (pass_data_build_alias, ctxt)
6985 /* opt_pass methods: */
6986 virtual bool gate (function *) { return flag_tree_pta; }
6988 }; // class pass_build_alias
6990 } // anon namespace
6992 gimple_opt_pass *
6993 make_pass_build_alias (gcc::context *ctxt)
6995 return new pass_build_alias (ctxt);
6998 /* A dummy pass to cause points-to information to be computed via
6999 TODO_rebuild_alias. */
7001 namespace {
7003 const pass_data pass_data_build_ealias =
7005 GIMPLE_PASS, /* type */
7006 "ealias", /* name */
7007 OPTGROUP_NONE, /* optinfo_flags */
7008 TV_NONE, /* tv_id */
7009 ( PROP_cfg | PROP_ssa ), /* properties_required */
7010 0, /* properties_provided */
7011 0, /* properties_destroyed */
7012 0, /* todo_flags_start */
7013 TODO_rebuild_alias, /* todo_flags_finish */
7016 class pass_build_ealias : public gimple_opt_pass
7018 public:
7019 pass_build_ealias (gcc::context *ctxt)
7020 : gimple_opt_pass (pass_data_build_ealias, ctxt)
7023 /* opt_pass methods: */
7024 virtual bool gate (function *) { return flag_tree_pta; }
7026 }; // class pass_build_ealias
7028 } // anon namespace
7030 gimple_opt_pass *
7031 make_pass_build_ealias (gcc::context *ctxt)
7033 return new pass_build_ealias (ctxt);
7037 /* IPA PTA solutions for ESCAPED. */
7038 struct pt_solution ipa_escaped_pt
7039 = { true, false, false, false, false, false, false, false, NULL };
7041 /* Associate node with varinfo DATA. Worker for
7042 cgraph_for_node_and_aliases. */
7043 static bool
7044 associate_varinfo_to_alias (struct cgraph_node *node, void *data)
7046 if ((node->alias || node->thunk.thunk_p)
7047 && node->analyzed)
7048 insert_vi_for_tree (node->decl, (varinfo_t)data);
7049 return false;
7052 /* Execute the driver for IPA PTA. */
7053 static unsigned int
7054 ipa_pta_execute (void)
7056 struct cgraph_node *node;
7057 varpool_node *var;
7058 int from;
7060 in_ipa_mode = 1;
7062 init_alias_vars ();
7064 if (dump_file && (dump_flags & TDF_DETAILS))
7066 symtab_node::dump_table (dump_file);
7067 fprintf (dump_file, "\n");
7070 /* Build the constraints. */
7071 FOR_EACH_DEFINED_FUNCTION (node)
7073 varinfo_t vi;
7074 /* Nodes without a body are not interesting. Especially do not
7075 visit clones at this point for now - we get duplicate decls
7076 there for inline clones at least. */
7077 if (!node->has_gimple_body_p () || node->clone_of)
7078 continue;
7079 node->get_body ();
7081 gcc_assert (!node->clone_of);
7083 vi = create_function_info_for (node->decl,
7084 alias_get_name (node->decl));
7085 node->call_for_symbol_thunks_and_aliases
7086 (associate_varinfo_to_alias, vi, true);
7089 /* Create constraints for global variables and their initializers. */
7090 FOR_EACH_VARIABLE (var)
7092 if (var->alias && var->analyzed)
7093 continue;
7095 get_vi_for_tree (var->decl);
7098 if (dump_file)
7100 fprintf (dump_file,
7101 "Generating constraints for global initializers\n\n");
7102 dump_constraints (dump_file, 0);
7103 fprintf (dump_file, "\n");
7105 from = constraints.length ();
7107 FOR_EACH_DEFINED_FUNCTION (node)
7109 struct function *func;
7110 basic_block bb;
7112 /* Nodes without a body are not interesting. */
7113 if (!node->has_gimple_body_p () || node->clone_of)
7114 continue;
7116 if (dump_file)
7118 fprintf (dump_file,
7119 "Generating constraints for %s", node->name ());
7120 if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
7121 fprintf (dump_file, " (%s)",
7122 IDENTIFIER_POINTER
7123 (DECL_ASSEMBLER_NAME (node->decl)));
7124 fprintf (dump_file, "\n");
7127 func = DECL_STRUCT_FUNCTION (node->decl);
7128 gcc_assert (cfun == NULL);
7130 /* For externally visible or attribute used annotated functions use
7131 local constraints for their arguments.
7132 For local functions we see all callers and thus do not need initial
7133 constraints for parameters. */
7134 if (node->used_from_other_partition
7135 || node->externally_visible
7136 || node->force_output)
7138 intra_create_variable_infos (func);
7140 /* We also need to make function return values escape. Nothing
7141 escapes by returning from main though. */
7142 if (!MAIN_NAME_P (DECL_NAME (node->decl)))
7144 varinfo_t fi, rvi;
7145 fi = lookup_vi_for_tree (node->decl);
7146 rvi = first_vi_for_offset (fi, fi_result);
7147 if (rvi && rvi->offset == fi_result)
7149 struct constraint_expr includes;
7150 struct constraint_expr var;
7151 includes.var = escaped_id;
7152 includes.offset = 0;
7153 includes.type = SCALAR;
7154 var.var = rvi->id;
7155 var.offset = 0;
7156 var.type = SCALAR;
7157 process_constraint (new_constraint (includes, var));
7162 /* Build constriants for the function body. */
7163 FOR_EACH_BB_FN (bb, func)
7165 gimple_stmt_iterator gsi;
7167 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
7168 gsi_next (&gsi))
7170 gimple phi = gsi_stmt (gsi);
7172 if (! virtual_operand_p (gimple_phi_result (phi)))
7173 find_func_aliases (func, phi);
7176 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
7178 gimple stmt = gsi_stmt (gsi);
7180 find_func_aliases (func, stmt);
7181 find_func_clobbers (func, stmt);
7185 if (dump_file)
7187 fprintf (dump_file, "\n");
7188 dump_constraints (dump_file, from);
7189 fprintf (dump_file, "\n");
7191 from = constraints.length ();
7194 /* From the constraints compute the points-to sets. */
7195 solve_constraints ();
7197 /* Compute the global points-to sets for ESCAPED.
7198 ??? Note that the computed escape set is not correct
7199 for the whole unit as we fail to consider graph edges to
7200 externally visible functions. */
7201 ipa_escaped_pt = find_what_var_points_to (get_varinfo (escaped_id));
7203 /* Make sure the ESCAPED solution (which is used as placeholder in
7204 other solutions) does not reference itself. This simplifies
7205 points-to solution queries. */
7206 ipa_escaped_pt.ipa_escaped = 0;
7208 /* Assign the points-to sets to the SSA names in the unit. */
7209 FOR_EACH_DEFINED_FUNCTION (node)
7211 tree ptr;
7212 struct function *fn;
7213 unsigned i;
7214 basic_block bb;
7216 /* Nodes without a body are not interesting. */
7217 if (!node->has_gimple_body_p () || node->clone_of)
7218 continue;
7220 fn = DECL_STRUCT_FUNCTION (node->decl);
7222 /* Compute the points-to sets for pointer SSA_NAMEs. */
7223 FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
7225 if (ptr
7226 && POINTER_TYPE_P (TREE_TYPE (ptr)))
7227 find_what_p_points_to (ptr);
7230 /* Compute the call-use and call-clobber sets for indirect calls
7231 and calls to external functions. */
7232 FOR_EACH_BB_FN (bb, fn)
7234 gimple_stmt_iterator gsi;
7236 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
7238 gimple stmt = gsi_stmt (gsi);
7239 struct pt_solution *pt;
7240 varinfo_t vi, fi;
7241 tree decl;
7243 if (!is_gimple_call (stmt))
7244 continue;
7246 /* Handle direct calls to functions with body. */
7247 decl = gimple_call_fndecl (stmt);
7248 if (decl
7249 && (fi = lookup_vi_for_tree (decl))
7250 && fi->is_fn_info)
7252 *gimple_call_clobber_set (stmt)
7253 = find_what_var_points_to
7254 (first_vi_for_offset (fi, fi_clobbers));
7255 *gimple_call_use_set (stmt)
7256 = find_what_var_points_to
7257 (first_vi_for_offset (fi, fi_uses));
7259 /* Handle direct calls to external functions. */
7260 else if (decl)
7262 pt = gimple_call_use_set (stmt);
7263 if (gimple_call_flags (stmt) & ECF_CONST)
7264 memset (pt, 0, sizeof (struct pt_solution));
7265 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
7267 *pt = find_what_var_points_to (vi);
7268 /* Escaped (and thus nonlocal) variables are always
7269 implicitly used by calls. */
7270 /* ??? ESCAPED can be empty even though NONLOCAL
7271 always escaped. */
7272 pt->nonlocal = 1;
7273 pt->ipa_escaped = 1;
7275 else
7277 /* If there is nothing special about this call then
7278 we have made everything that is used also escape. */
7279 *pt = ipa_escaped_pt;
7280 pt->nonlocal = 1;
7283 pt = gimple_call_clobber_set (stmt);
7284 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
7285 memset (pt, 0, sizeof (struct pt_solution));
7286 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
7288 *pt = find_what_var_points_to (vi);
7289 /* Escaped (and thus nonlocal) variables are always
7290 implicitly clobbered by calls. */
7291 /* ??? ESCAPED can be empty even though NONLOCAL
7292 always escaped. */
7293 pt->nonlocal = 1;
7294 pt->ipa_escaped = 1;
7296 else
7298 /* If there is nothing special about this call then
7299 we have made everything that is used also escape. */
7300 *pt = ipa_escaped_pt;
7301 pt->nonlocal = 1;
7304 /* Handle indirect calls. */
7305 else if (!decl
7306 && (fi = get_fi_for_callee (stmt)))
7308 /* We need to accumulate all clobbers/uses of all possible
7309 callees. */
7310 fi = get_varinfo (find (fi->id));
7311 /* If we cannot constrain the set of functions we'll end up
7312 calling we end up using/clobbering everything. */
7313 if (bitmap_bit_p (fi->solution, anything_id)
7314 || bitmap_bit_p (fi->solution, nonlocal_id)
7315 || bitmap_bit_p (fi->solution, escaped_id))
7317 pt_solution_reset (gimple_call_clobber_set (stmt));
7318 pt_solution_reset (gimple_call_use_set (stmt));
7320 else
7322 bitmap_iterator bi;
7323 unsigned i;
7324 struct pt_solution *uses, *clobbers;
7326 uses = gimple_call_use_set (stmt);
7327 clobbers = gimple_call_clobber_set (stmt);
7328 memset (uses, 0, sizeof (struct pt_solution));
7329 memset (clobbers, 0, sizeof (struct pt_solution));
7330 EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
7332 struct pt_solution sol;
7334 vi = get_varinfo (i);
7335 if (!vi->is_fn_info)
7337 /* ??? We could be more precise here? */
7338 uses->nonlocal = 1;
7339 uses->ipa_escaped = 1;
7340 clobbers->nonlocal = 1;
7341 clobbers->ipa_escaped = 1;
7342 continue;
7345 if (!uses->anything)
7347 sol = find_what_var_points_to
7348 (first_vi_for_offset (vi, fi_uses));
7349 pt_solution_ior_into (uses, &sol);
7351 if (!clobbers->anything)
7353 sol = find_what_var_points_to
7354 (first_vi_for_offset (vi, fi_clobbers));
7355 pt_solution_ior_into (clobbers, &sol);
7363 fn->gimple_df->ipa_pta = true;
7366 delete_points_to_sets ();
7368 in_ipa_mode = 0;
7370 return 0;
7373 namespace {
7375 const pass_data pass_data_ipa_pta =
7377 SIMPLE_IPA_PASS, /* type */
7378 "pta", /* name */
7379 OPTGROUP_NONE, /* optinfo_flags */
7380 TV_IPA_PTA, /* tv_id */
7381 0, /* properties_required */
7382 0, /* properties_provided */
7383 0, /* properties_destroyed */
7384 0, /* todo_flags_start */
7385 0, /* todo_flags_finish */
7388 class pass_ipa_pta : public simple_ipa_opt_pass
7390 public:
7391 pass_ipa_pta (gcc::context *ctxt)
7392 : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
7395 /* opt_pass methods: */
7396 virtual bool gate (function *)
7398 return (optimize
7399 && flag_ipa_pta
7400 /* Don't bother doing anything if the program has errors. */
7401 && !seen_error ());
7404 virtual unsigned int execute (function *) { return ipa_pta_execute (); }
7406 }; // class pass_ipa_pta
7408 } // anon namespace
7410 simple_ipa_opt_pass *
7411 make_pass_ipa_pta (gcc::context *ctxt)
7413 return new pass_ipa_pta (ctxt);