PR target/83368
[official-gcc.git] / gcc / tree-ssa-structalias.c
blobd3b38c3eaf2789f4269b1cd038065e8ebc7dc15f
1 /* Tree based points-to analysis
2 Copyright (C) 2005-2018 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 "backend.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "alloc-pool.h"
29 #include "tree-pass.h"
30 #include "ssa.h"
31 #include "cgraph.h"
32 #include "tree-pretty-print.h"
33 #include "diagnostic-core.h"
34 #include "fold-const.h"
35 #include "stor-layout.h"
36 #include "stmt.h"
37 #include "gimple-iterator.h"
38 #include "tree-into-ssa.h"
39 #include "tree-dfa.h"
40 #include "params.h"
41 #include "gimple-walk.h"
42 #include "varasm.h"
43 #include "stringpool.h"
44 #include "attribs.h"
46 /* The idea behind this analyzer is to generate set constraints from the
47 program, then solve the resulting constraints in order to generate the
48 points-to sets.
50 Set constraints are a way of modeling program analysis problems that
51 involve sets. They consist of an inclusion constraint language,
52 describing the variables (each variable is a set) and operations that
53 are involved on the variables, and a set of rules that derive facts
54 from these operations. To solve a system of set constraints, you derive
55 all possible facts under the rules, which gives you the correct sets
56 as a consequence.
58 See "Efficient Field-sensitive pointer analysis for C" by "David
59 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
60 http://citeseer.ist.psu.edu/pearce04efficient.html
62 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
63 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
64 http://citeseer.ist.psu.edu/heintze01ultrafast.html
66 There are three types of real constraint expressions, DEREF,
67 ADDRESSOF, and SCALAR. Each constraint expression consists
68 of a constraint type, a variable, and an offset.
70 SCALAR is a constraint expression type used to represent x, whether
71 it appears on the LHS or the RHS of a statement.
72 DEREF is a constraint expression type used to represent *x, whether
73 it appears on the LHS or the RHS of a statement.
74 ADDRESSOF is a constraint expression used to represent &x, whether
75 it appears on the LHS or the RHS of a statement.
77 Each pointer variable in the program is assigned an integer id, and
78 each field of a structure variable is assigned an integer id as well.
80 Structure variables are linked to their list of fields through a "next
81 field" in each variable that points to the next field in offset
82 order.
83 Each variable for a structure field has
85 1. "size", that tells the size in bits of that field.
86 2. "fullsize, that tells the size in bits of the entire structure.
87 3. "offset", that tells the offset in bits from the beginning of the
88 structure to this field.
90 Thus,
91 struct f
93 int a;
94 int b;
95 } foo;
96 int *bar;
98 looks like
100 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
101 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
102 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
105 In order to solve the system of set constraints, the following is
106 done:
108 1. Each constraint variable x has a solution set associated with it,
109 Sol(x).
111 2. Constraints are separated into direct, copy, and complex.
112 Direct constraints are ADDRESSOF constraints that require no extra
113 processing, such as P = &Q
114 Copy constraints are those of the form P = Q.
115 Complex constraints are all the constraints involving dereferences
116 and offsets (including offsetted copies).
118 3. All direct constraints of the form P = &Q are processed, such
119 that Q is added to Sol(P)
121 4. All complex constraints for a given constraint variable are stored in a
122 linked list attached to that variable's node.
124 5. A directed graph is built out of the copy constraints. Each
125 constraint variable is a node in the graph, and an edge from
126 Q to P is added for each copy constraint of the form P = Q
128 6. The graph is then walked, and solution sets are
129 propagated along the copy edges, such that an edge from Q to P
130 causes Sol(P) <- Sol(P) union Sol(Q).
132 7. As we visit each node, all complex constraints associated with
133 that node are processed by adding appropriate copy edges to the graph, or the
134 appropriate variables to the solution set.
136 8. The process of walking the graph is iterated until no solution
137 sets change.
139 Prior to walking the graph in steps 6 and 7, We perform static
140 cycle elimination on the constraint graph, as well
141 as off-line variable substitution.
143 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
144 on and turned into anything), but isn't. You can just see what offset
145 inside the pointed-to struct it's going to access.
147 TODO: Constant bounded arrays can be handled as if they were structs of the
148 same number of elements.
150 TODO: Modeling heap and incoming pointers becomes much better if we
151 add fields to them as we discover them, which we could do.
153 TODO: We could handle unions, but to be honest, it's probably not
154 worth the pain or slowdown. */
156 /* IPA-PTA optimizations possible.
158 When the indirect function called is ANYTHING we can add disambiguation
159 based on the function signatures (or simply the parameter count which
160 is the varinfo size). We also do not need to consider functions that
161 do not have their address taken.
163 The is_global_var bit which marks escape points is overly conservative
164 in IPA mode. Split it to is_escape_point and is_global_var - only
165 externally visible globals are escape points in IPA mode.
166 There is now is_ipa_escape_point but this is only used in a few
167 selected places.
169 The way we introduce DECL_PT_UID to avoid fixing up all points-to
170 sets in the translation unit when we copy a DECL during inlining
171 pessimizes precision. The advantage is that the DECL_PT_UID keeps
172 compile-time and memory usage overhead low - the points-to sets
173 do not grow or get unshared as they would during a fixup phase.
174 An alternative solution is to delay IPA PTA until after all
175 inlining transformations have been applied.
177 The way we propagate clobber/use information isn't optimized.
178 It should use a new complex constraint that properly filters
179 out local variables of the callee (though that would make
180 the sets invalid after inlining). OTOH we might as well
181 admit defeat to WHOPR and simply do all the clobber/use analysis
182 and propagation after PTA finished but before we threw away
183 points-to information for memory variables. WHOPR and PTA
184 do not play along well anyway - the whole constraint solving
185 would need to be done in WPA phase and it will be very interesting
186 to apply the results to local SSA names during LTRANS phase.
188 We probably should compute a per-function unit-ESCAPE solution
189 propagating it simply like the clobber / uses solutions. The
190 solution can go alongside the non-IPA espaced solution and be
191 used to query which vars escape the unit through a function.
192 This is also required to make the escaped-HEAP trick work in IPA mode.
194 We never put function decls in points-to sets so we do not
195 keep the set of called functions for indirect calls.
197 And probably more. */
199 static bool use_field_sensitive = true;
200 static int in_ipa_mode = 0;
202 /* Used for predecessor bitmaps. */
203 static bitmap_obstack predbitmap_obstack;
205 /* Used for points-to sets. */
206 static bitmap_obstack pta_obstack;
208 /* Used for oldsolution members of variables. */
209 static bitmap_obstack oldpta_obstack;
211 /* Used for per-solver-iteration bitmaps. */
212 static bitmap_obstack iteration_obstack;
214 static unsigned int create_variable_info_for (tree, const char *, bool);
215 typedef struct constraint_graph *constraint_graph_t;
216 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
218 struct constraint;
219 typedef struct constraint *constraint_t;
222 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
223 if (a) \
224 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
226 static struct constraint_stats
228 unsigned int total_vars;
229 unsigned int nonpointer_vars;
230 unsigned int unified_vars_static;
231 unsigned int unified_vars_dynamic;
232 unsigned int iterations;
233 unsigned int num_edges;
234 unsigned int num_implicit_edges;
235 unsigned int points_to_sets_created;
236 } stats;
238 struct variable_info
240 /* ID of this variable */
241 unsigned int id;
243 /* True if this is a variable created by the constraint analysis, such as
244 heap variables and constraints we had to break up. */
245 unsigned int is_artificial_var : 1;
247 /* True if this is a special variable whose solution set should not be
248 changed. */
249 unsigned int is_special_var : 1;
251 /* True for variables whose size is not known or variable. */
252 unsigned int is_unknown_size_var : 1;
254 /* True for (sub-)fields that represent a whole variable. */
255 unsigned int is_full_var : 1;
257 /* True if this is a heap variable. */
258 unsigned int is_heap_var : 1;
260 /* True if this is a register variable. */
261 unsigned int is_reg_var : 1;
263 /* True if this field may contain pointers. */
264 unsigned int may_have_pointers : 1;
266 /* True if this field has only restrict qualified pointers. */
267 unsigned int only_restrict_pointers : 1;
269 /* True if this represents a heap var created for a restrict qualified
270 pointer. */
271 unsigned int is_restrict_var : 1;
273 /* True if this represents a global variable. */
274 unsigned int is_global_var : 1;
276 /* True if this represents a module escape point for IPA analysis. */
277 unsigned int is_ipa_escape_point : 1;
279 /* True if this represents a IPA function info. */
280 unsigned int is_fn_info : 1;
282 /* ??? Store somewhere better. */
283 unsigned short ruid;
285 /* The ID of the variable for the next field in this structure
286 or zero for the last field in this structure. */
287 unsigned next;
289 /* The ID of the variable for the first field in this structure. */
290 unsigned head;
292 /* Offset of this variable, in bits, from the base variable */
293 unsigned HOST_WIDE_INT offset;
295 /* Size of the variable, in bits. */
296 unsigned HOST_WIDE_INT size;
298 /* Full size of the base variable, in bits. */
299 unsigned HOST_WIDE_INT fullsize;
301 /* Name of this variable */
302 const char *name;
304 /* Tree that this variable is associated with. */
305 tree decl;
307 /* Points-to set for this variable. */
308 bitmap solution;
310 /* Old points-to set for this variable. */
311 bitmap oldsolution;
313 typedef struct variable_info *varinfo_t;
315 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
316 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
317 unsigned HOST_WIDE_INT);
318 static varinfo_t lookup_vi_for_tree (tree);
319 static inline bool type_can_have_subvars (const_tree);
320 static void make_param_constraints (varinfo_t);
322 /* Pool of variable info structures. */
323 static object_allocator<variable_info> variable_info_pool
324 ("Variable info pool");
326 /* Map varinfo to final pt_solution. */
327 static hash_map<varinfo_t, pt_solution *> *final_solutions;
328 struct obstack final_solutions_obstack;
330 /* Table of variable info structures for constraint variables.
331 Indexed directly by variable info id. */
332 static vec<varinfo_t> varmap;
334 /* Return the varmap element N */
336 static inline varinfo_t
337 get_varinfo (unsigned int n)
339 return varmap[n];
342 /* Return the next variable in the list of sub-variables of VI
343 or NULL if VI is the last sub-variable. */
345 static inline varinfo_t
346 vi_next (varinfo_t vi)
348 return get_varinfo (vi->next);
351 /* Static IDs for the special variables. Variable ID zero is unused
352 and used as terminator for the sub-variable chain. */
353 enum { nothing_id = 1, anything_id = 2, string_id = 3,
354 escaped_id = 4, nonlocal_id = 5,
355 storedanything_id = 6, integer_id = 7 };
357 /* Return a new variable info structure consisting for a variable
358 named NAME, and using constraint graph node NODE. Append it
359 to the vector of variable info structures. */
361 static varinfo_t
362 new_var_info (tree t, const char *name, bool add_id)
364 unsigned index = varmap.length ();
365 varinfo_t ret = variable_info_pool.allocate ();
367 if (dump_file && add_id)
369 char *tempname = xasprintf ("%s(%d)", name, index);
370 name = ggc_strdup (tempname);
371 free (tempname);
374 ret->id = index;
375 ret->name = name;
376 ret->decl = t;
377 /* Vars without decl are artificial and do not have sub-variables. */
378 ret->is_artificial_var = (t == NULL_TREE);
379 ret->is_special_var = false;
380 ret->is_unknown_size_var = false;
381 ret->is_full_var = (t == NULL_TREE);
382 ret->is_heap_var = false;
383 ret->may_have_pointers = true;
384 ret->only_restrict_pointers = false;
385 ret->is_restrict_var = false;
386 ret->ruid = 0;
387 ret->is_global_var = (t == NULL_TREE);
388 ret->is_ipa_escape_point = false;
389 ret->is_fn_info = false;
390 if (t && DECL_P (t))
391 ret->is_global_var = (is_global_var (t)
392 /* We have to treat even local register variables
393 as escape points. */
394 || (VAR_P (t) && DECL_HARD_REGISTER (t)));
395 ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME);
396 ret->solution = BITMAP_ALLOC (&pta_obstack);
397 ret->oldsolution = NULL;
398 ret->next = 0;
399 ret->head = ret->id;
401 stats.total_vars++;
403 varmap.safe_push (ret);
405 return ret;
408 /* A map mapping call statements to per-stmt variables for uses
409 and clobbers specific to the call. */
410 static hash_map<gimple *, varinfo_t> *call_stmt_vars;
412 /* Lookup or create the variable for the call statement CALL. */
414 static varinfo_t
415 get_call_vi (gcall *call)
417 varinfo_t vi, vi2;
419 bool existed;
420 varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed);
421 if (existed)
422 return *slot_p;
424 vi = new_var_info (NULL_TREE, "CALLUSED", true);
425 vi->offset = 0;
426 vi->size = 1;
427 vi->fullsize = 2;
428 vi->is_full_var = true;
429 vi->is_reg_var = true;
431 vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED", true);
432 vi2->offset = 1;
433 vi2->size = 1;
434 vi2->fullsize = 2;
435 vi2->is_full_var = true;
436 vi2->is_reg_var = true;
438 vi->next = vi2->id;
440 *slot_p = vi;
441 return vi;
444 /* Lookup the variable for the call statement CALL representing
445 the uses. Returns NULL if there is nothing special about this call. */
447 static varinfo_t
448 lookup_call_use_vi (gcall *call)
450 varinfo_t *slot_p = call_stmt_vars->get (call);
451 if (slot_p)
452 return *slot_p;
454 return NULL;
457 /* Lookup the variable for the call statement CALL representing
458 the clobbers. Returns NULL if there is nothing special about this call. */
460 static varinfo_t
461 lookup_call_clobber_vi (gcall *call)
463 varinfo_t uses = lookup_call_use_vi (call);
464 if (!uses)
465 return NULL;
467 return vi_next (uses);
470 /* Lookup or create the variable for the call statement CALL representing
471 the uses. */
473 static varinfo_t
474 get_call_use_vi (gcall *call)
476 return get_call_vi (call);
479 /* Lookup or create the variable for the call statement CALL representing
480 the clobbers. */
482 static varinfo_t ATTRIBUTE_UNUSED
483 get_call_clobber_vi (gcall *call)
485 return vi_next (get_call_vi (call));
489 enum constraint_expr_type {SCALAR, DEREF, ADDRESSOF};
491 /* An expression that appears in a constraint. */
493 struct constraint_expr
495 /* Constraint type. */
496 constraint_expr_type type;
498 /* Variable we are referring to in the constraint. */
499 unsigned int var;
501 /* Offset, in bits, of this constraint from the beginning of
502 variables it ends up referring to.
504 IOW, in a deref constraint, we would deref, get the result set,
505 then add OFFSET to each member. */
506 HOST_WIDE_INT offset;
509 /* Use 0x8000... as special unknown offset. */
510 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
512 typedef struct constraint_expr ce_s;
513 static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool);
514 static void get_constraint_for (tree, vec<ce_s> *);
515 static void get_constraint_for_rhs (tree, vec<ce_s> *);
516 static void do_deref (vec<ce_s> *);
518 /* Our set constraints are made up of two constraint expressions, one
519 LHS, and one RHS.
521 As described in the introduction, our set constraints each represent an
522 operation between set valued variables.
524 struct constraint
526 struct constraint_expr lhs;
527 struct constraint_expr rhs;
530 /* List of constraints that we use to build the constraint graph from. */
532 static vec<constraint_t> constraints;
533 static object_allocator<constraint> constraint_pool ("Constraint pool");
535 /* The constraint graph is represented as an array of bitmaps
536 containing successor nodes. */
538 struct constraint_graph
540 /* Size of this graph, which may be different than the number of
541 nodes in the variable map. */
542 unsigned int size;
544 /* Explicit successors of each node. */
545 bitmap *succs;
547 /* Implicit predecessors of each node (Used for variable
548 substitution). */
549 bitmap *implicit_preds;
551 /* Explicit predecessors of each node (Used for variable substitution). */
552 bitmap *preds;
554 /* Indirect cycle representatives, or -1 if the node has no indirect
555 cycles. */
556 int *indirect_cycles;
558 /* Representative node for a node. rep[a] == a unless the node has
559 been unified. */
560 unsigned int *rep;
562 /* Equivalence class representative for a label. This is used for
563 variable substitution. */
564 int *eq_rep;
566 /* Pointer equivalence label for a node. All nodes with the same
567 pointer equivalence label can be unified together at some point
568 (either during constraint optimization or after the constraint
569 graph is built). */
570 unsigned int *pe;
572 /* Pointer equivalence representative for a label. This is used to
573 handle nodes that are pointer equivalent but not location
574 equivalent. We can unite these once the addressof constraints
575 are transformed into initial points-to sets. */
576 int *pe_rep;
578 /* Pointer equivalence label for each node, used during variable
579 substitution. */
580 unsigned int *pointer_label;
582 /* Location equivalence label for each node, used during location
583 equivalence finding. */
584 unsigned int *loc_label;
586 /* Pointed-by set for each node, used during location equivalence
587 finding. This is pointed-by rather than pointed-to, because it
588 is constructed using the predecessor graph. */
589 bitmap *pointed_by;
591 /* Points to sets for pointer equivalence. This is *not* the actual
592 points-to sets for nodes. */
593 bitmap *points_to;
595 /* Bitmap of nodes where the bit is set if the node is a direct
596 node. Used for variable substitution. */
597 sbitmap direct_nodes;
599 /* Bitmap of nodes where the bit is set if the node is address
600 taken. Used for variable substitution. */
601 bitmap address_taken;
603 /* Vector of complex constraints for each graph node. Complex
604 constraints are those involving dereferences or offsets that are
605 not 0. */
606 vec<constraint_t> *complex;
609 static constraint_graph_t graph;
611 /* During variable substitution and the offline version of indirect
612 cycle finding, we create nodes to represent dereferences and
613 address taken constraints. These represent where these start and
614 end. */
615 #define FIRST_REF_NODE (varmap).length ()
616 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
618 /* Return the representative node for NODE, if NODE has been unioned
619 with another NODE.
620 This function performs path compression along the way to finding
621 the representative. */
623 static unsigned int
624 find (unsigned int node)
626 gcc_checking_assert (node < graph->size);
627 if (graph->rep[node] != node)
628 return graph->rep[node] = find (graph->rep[node]);
629 return node;
632 /* Union the TO and FROM nodes to the TO nodes.
633 Note that at some point in the future, we may want to do
634 union-by-rank, in which case we are going to have to return the
635 node we unified to. */
637 static bool
638 unite (unsigned int to, unsigned int from)
640 gcc_checking_assert (to < graph->size && from < graph->size);
641 if (to != from && graph->rep[from] != to)
643 graph->rep[from] = to;
644 return true;
646 return false;
649 /* Create a new constraint consisting of LHS and RHS expressions. */
651 static constraint_t
652 new_constraint (const struct constraint_expr lhs,
653 const struct constraint_expr rhs)
655 constraint_t ret = constraint_pool.allocate ();
656 ret->lhs = lhs;
657 ret->rhs = rhs;
658 return ret;
661 /* Print out constraint C to FILE. */
663 static void
664 dump_constraint (FILE *file, constraint_t c)
666 if (c->lhs.type == ADDRESSOF)
667 fprintf (file, "&");
668 else if (c->lhs.type == DEREF)
669 fprintf (file, "*");
670 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
671 if (c->lhs.offset == UNKNOWN_OFFSET)
672 fprintf (file, " + UNKNOWN");
673 else if (c->lhs.offset != 0)
674 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
675 fprintf (file, " = ");
676 if (c->rhs.type == ADDRESSOF)
677 fprintf (file, "&");
678 else if (c->rhs.type == DEREF)
679 fprintf (file, "*");
680 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
681 if (c->rhs.offset == UNKNOWN_OFFSET)
682 fprintf (file, " + UNKNOWN");
683 else if (c->rhs.offset != 0)
684 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
688 void debug_constraint (constraint_t);
689 void debug_constraints (void);
690 void debug_constraint_graph (void);
691 void debug_solution_for_var (unsigned int);
692 void debug_sa_points_to_info (void);
693 void debug_varinfo (varinfo_t);
694 void debug_varmap (void);
696 /* Print out constraint C to stderr. */
698 DEBUG_FUNCTION void
699 debug_constraint (constraint_t c)
701 dump_constraint (stderr, c);
702 fprintf (stderr, "\n");
705 /* Print out all constraints to FILE */
707 static void
708 dump_constraints (FILE *file, int from)
710 int i;
711 constraint_t c;
712 for (i = from; constraints.iterate (i, &c); i++)
713 if (c)
715 dump_constraint (file, c);
716 fprintf (file, "\n");
720 /* Print out all constraints to stderr. */
722 DEBUG_FUNCTION void
723 debug_constraints (void)
725 dump_constraints (stderr, 0);
728 /* Print the constraint graph in dot format. */
730 static void
731 dump_constraint_graph (FILE *file)
733 unsigned int i;
735 /* Only print the graph if it has already been initialized: */
736 if (!graph)
737 return;
739 /* Prints the header of the dot file: */
740 fprintf (file, "strict digraph {\n");
741 fprintf (file, " node [\n shape = box\n ]\n");
742 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
743 fprintf (file, "\n // List of nodes and complex constraints in "
744 "the constraint graph:\n");
746 /* The next lines print the nodes in the graph together with the
747 complex constraints attached to them. */
748 for (i = 1; i < graph->size; i++)
750 if (i == FIRST_REF_NODE)
751 continue;
752 if (find (i) != i)
753 continue;
754 if (i < FIRST_REF_NODE)
755 fprintf (file, "\"%s\"", get_varinfo (i)->name);
756 else
757 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
758 if (graph->complex[i].exists ())
760 unsigned j;
761 constraint_t c;
762 fprintf (file, " [label=\"\\N\\n");
763 for (j = 0; graph->complex[i].iterate (j, &c); ++j)
765 dump_constraint (file, c);
766 fprintf (file, "\\l");
768 fprintf (file, "\"]");
770 fprintf (file, ";\n");
773 /* Go over the edges. */
774 fprintf (file, "\n // Edges in the constraint graph:\n");
775 for (i = 1; i < graph->size; i++)
777 unsigned j;
778 bitmap_iterator bi;
779 if (find (i) != i)
780 continue;
781 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
783 unsigned to = find (j);
784 if (i == to)
785 continue;
786 if (i < FIRST_REF_NODE)
787 fprintf (file, "\"%s\"", get_varinfo (i)->name);
788 else
789 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
790 fprintf (file, " -> ");
791 if (to < FIRST_REF_NODE)
792 fprintf (file, "\"%s\"", get_varinfo (to)->name);
793 else
794 fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
795 fprintf (file, ";\n");
799 /* Prints the tail of the dot file. */
800 fprintf (file, "}\n");
803 /* Print out the constraint graph to stderr. */
805 DEBUG_FUNCTION void
806 debug_constraint_graph (void)
808 dump_constraint_graph (stderr);
811 /* SOLVER FUNCTIONS
813 The solver is a simple worklist solver, that works on the following
814 algorithm:
816 sbitmap changed_nodes = all zeroes;
817 changed_count = 0;
818 For each node that is not already collapsed:
819 changed_count++;
820 set bit in changed nodes
822 while (changed_count > 0)
824 compute topological ordering for constraint graph
826 find and collapse cycles in the constraint graph (updating
827 changed if necessary)
829 for each node (n) in the graph in topological order:
830 changed_count--;
832 Process each complex constraint associated with the node,
833 updating changed if necessary.
835 For each outgoing edge from n, propagate the solution from n to
836 the destination of the edge, updating changed as necessary.
838 } */
840 /* Return true if two constraint expressions A and B are equal. */
842 static bool
843 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
845 return a.type == b.type && a.var == b.var && a.offset == b.offset;
848 /* Return true if constraint expression A is less than constraint expression
849 B. This is just arbitrary, but consistent, in order to give them an
850 ordering. */
852 static bool
853 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
855 if (a.type == b.type)
857 if (a.var == b.var)
858 return a.offset < b.offset;
859 else
860 return a.var < b.var;
862 else
863 return a.type < b.type;
866 /* Return true if constraint A is less than constraint B. This is just
867 arbitrary, but consistent, in order to give them an ordering. */
869 static bool
870 constraint_less (const constraint_t &a, const constraint_t &b)
872 if (constraint_expr_less (a->lhs, b->lhs))
873 return true;
874 else if (constraint_expr_less (b->lhs, a->lhs))
875 return false;
876 else
877 return constraint_expr_less (a->rhs, b->rhs);
880 /* Return true if two constraints A and B are equal. */
882 static bool
883 constraint_equal (struct constraint a, struct constraint b)
885 return constraint_expr_equal (a.lhs, b.lhs)
886 && constraint_expr_equal (a.rhs, b.rhs);
890 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
892 static constraint_t
893 constraint_vec_find (vec<constraint_t> vec,
894 struct constraint lookfor)
896 unsigned int place;
897 constraint_t found;
899 if (!vec.exists ())
900 return NULL;
902 place = vec.lower_bound (&lookfor, constraint_less);
903 if (place >= vec.length ())
904 return NULL;
905 found = vec[place];
906 if (!constraint_equal (*found, lookfor))
907 return NULL;
908 return found;
911 /* Union two constraint vectors, TO and FROM. Put the result in TO.
912 Returns true of TO set is changed. */
914 static bool
915 constraint_set_union (vec<constraint_t> *to,
916 vec<constraint_t> *from)
918 int i;
919 constraint_t c;
920 bool any_change = false;
922 FOR_EACH_VEC_ELT (*from, i, c)
924 if (constraint_vec_find (*to, *c) == NULL)
926 unsigned int place = to->lower_bound (c, constraint_less);
927 to->safe_insert (place, c);
928 any_change = true;
931 return any_change;
934 /* Expands the solution in SET to all sub-fields of variables included. */
936 static bitmap
937 solution_set_expand (bitmap set, bitmap *expanded)
939 bitmap_iterator bi;
940 unsigned j;
942 if (*expanded)
943 return *expanded;
945 *expanded = BITMAP_ALLOC (&iteration_obstack);
947 /* In a first pass expand to the head of the variables we need to
948 add all sub-fields off. This avoids quadratic behavior. */
949 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
951 varinfo_t v = get_varinfo (j);
952 if (v->is_artificial_var
953 || v->is_full_var)
954 continue;
955 bitmap_set_bit (*expanded, v->head);
958 /* In the second pass now expand all head variables with subfields. */
959 EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi)
961 varinfo_t v = get_varinfo (j);
962 if (v->head != j)
963 continue;
964 for (v = vi_next (v); v != NULL; v = vi_next (v))
965 bitmap_set_bit (*expanded, v->id);
968 /* And finally set the rest of the bits from SET. */
969 bitmap_ior_into (*expanded, set);
971 return *expanded;
974 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
975 process. */
977 static bool
978 set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
979 bitmap *expanded_delta)
981 bool changed = false;
982 bitmap_iterator bi;
983 unsigned int i;
985 /* If the solution of DELTA contains anything it is good enough to transfer
986 this to TO. */
987 if (bitmap_bit_p (delta, anything_id))
988 return bitmap_set_bit (to, anything_id);
990 /* If the offset is unknown we have to expand the solution to
991 all subfields. */
992 if (inc == UNKNOWN_OFFSET)
994 delta = solution_set_expand (delta, expanded_delta);
995 changed |= bitmap_ior_into (to, delta);
996 return changed;
999 /* For non-zero offset union the offsetted solution into the destination. */
1000 EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
1002 varinfo_t vi = get_varinfo (i);
1004 /* If this is a variable with just one field just set its bit
1005 in the result. */
1006 if (vi->is_artificial_var
1007 || vi->is_unknown_size_var
1008 || vi->is_full_var)
1009 changed |= bitmap_set_bit (to, i);
1010 else
1012 HOST_WIDE_INT fieldoffset = vi->offset + inc;
1013 unsigned HOST_WIDE_INT size = vi->size;
1015 /* If the offset makes the pointer point to before the
1016 variable use offset zero for the field lookup. */
1017 if (fieldoffset < 0)
1018 vi = get_varinfo (vi->head);
1019 else
1020 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
1024 changed |= bitmap_set_bit (to, vi->id);
1025 if (vi->is_full_var
1026 || vi->next == 0)
1027 break;
1029 /* We have to include all fields that overlap the current field
1030 shifted by inc. */
1031 vi = vi_next (vi);
1033 while (vi->offset < fieldoffset + size);
1037 return changed;
1040 /* Insert constraint C into the list of complex constraints for graph
1041 node VAR. */
1043 static void
1044 insert_into_complex (constraint_graph_t graph,
1045 unsigned int var, constraint_t c)
1047 vec<constraint_t> complex = graph->complex[var];
1048 unsigned int place = complex.lower_bound (c, constraint_less);
1050 /* Only insert constraints that do not already exist. */
1051 if (place >= complex.length ()
1052 || !constraint_equal (*c, *complex[place]))
1053 graph->complex[var].safe_insert (place, c);
1057 /* Condense two variable nodes into a single variable node, by moving
1058 all associated info from FROM to TO. Returns true if TO node's
1059 constraint set changes after the merge. */
1061 static bool
1062 merge_node_constraints (constraint_graph_t graph, unsigned int to,
1063 unsigned int from)
1065 unsigned int i;
1066 constraint_t c;
1067 bool any_change = false;
1069 gcc_checking_assert (find (from) == to);
1071 /* Move all complex constraints from src node into to node */
1072 FOR_EACH_VEC_ELT (graph->complex[from], i, c)
1074 /* In complex constraints for node FROM, we may have either
1075 a = *FROM, and *FROM = a, or an offseted constraint which are
1076 always added to the rhs node's constraints. */
1078 if (c->rhs.type == DEREF)
1079 c->rhs.var = to;
1080 else if (c->lhs.type == DEREF)
1081 c->lhs.var = to;
1082 else
1083 c->rhs.var = to;
1086 any_change = constraint_set_union (&graph->complex[to],
1087 &graph->complex[from]);
1088 graph->complex[from].release ();
1089 return any_change;
1093 /* Remove edges involving NODE from GRAPH. */
1095 static void
1096 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1098 if (graph->succs[node])
1099 BITMAP_FREE (graph->succs[node]);
1102 /* Merge GRAPH nodes FROM and TO into node TO. */
1104 static void
1105 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1106 unsigned int from)
1108 if (graph->indirect_cycles[from] != -1)
1110 /* If we have indirect cycles with the from node, and we have
1111 none on the to node, the to node has indirect cycles from the
1112 from node now that they are unified.
1113 If indirect cycles exist on both, unify the nodes that they
1114 are in a cycle with, since we know they are in a cycle with
1115 each other. */
1116 if (graph->indirect_cycles[to] == -1)
1117 graph->indirect_cycles[to] = graph->indirect_cycles[from];
1120 /* Merge all the successor edges. */
1121 if (graph->succs[from])
1123 if (!graph->succs[to])
1124 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1125 bitmap_ior_into (graph->succs[to],
1126 graph->succs[from]);
1129 clear_edges_for_node (graph, from);
1133 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1134 it doesn't exist in the graph already. */
1136 static void
1137 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1138 unsigned int from)
1140 if (to == from)
1141 return;
1143 if (!graph->implicit_preds[to])
1144 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1146 if (bitmap_set_bit (graph->implicit_preds[to], from))
1147 stats.num_implicit_edges++;
1150 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1151 it doesn't exist in the graph already.
1152 Return false if the edge already existed, true otherwise. */
1154 static void
1155 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1156 unsigned int from)
1158 if (!graph->preds[to])
1159 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1160 bitmap_set_bit (graph->preds[to], from);
1163 /* Add a graph edge to GRAPH, going from FROM to TO if
1164 it doesn't exist in the graph already.
1165 Return false if the edge already existed, true otherwise. */
1167 static bool
1168 add_graph_edge (constraint_graph_t graph, unsigned int to,
1169 unsigned int from)
1171 if (to == from)
1173 return false;
1175 else
1177 bool r = false;
1179 if (!graph->succs[from])
1180 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1181 if (bitmap_set_bit (graph->succs[from], to))
1183 r = true;
1184 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1185 stats.num_edges++;
1187 return r;
1192 /* Initialize the constraint graph structure to contain SIZE nodes. */
1194 static void
1195 init_graph (unsigned int size)
1197 unsigned int j;
1199 graph = XCNEW (struct constraint_graph);
1200 graph->size = size;
1201 graph->succs = XCNEWVEC (bitmap, graph->size);
1202 graph->indirect_cycles = XNEWVEC (int, graph->size);
1203 graph->rep = XNEWVEC (unsigned int, graph->size);
1204 /* ??? Macros do not support template types with multiple arguments,
1205 so we use a typedef to work around it. */
1206 typedef vec<constraint_t> vec_constraint_t_heap;
1207 graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
1208 graph->pe = XCNEWVEC (unsigned int, graph->size);
1209 graph->pe_rep = XNEWVEC (int, graph->size);
1211 for (j = 0; j < graph->size; j++)
1213 graph->rep[j] = j;
1214 graph->pe_rep[j] = -1;
1215 graph->indirect_cycles[j] = -1;
1219 /* Build the constraint graph, adding only predecessor edges right now. */
1221 static void
1222 build_pred_graph (void)
1224 int i;
1225 constraint_t c;
1226 unsigned int j;
1228 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1229 graph->preds = XCNEWVEC (bitmap, graph->size);
1230 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1231 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1232 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1233 graph->points_to = XCNEWVEC (bitmap, graph->size);
1234 graph->eq_rep = XNEWVEC (int, graph->size);
1235 graph->direct_nodes = sbitmap_alloc (graph->size);
1236 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1237 bitmap_clear (graph->direct_nodes);
1239 for (j = 1; j < FIRST_REF_NODE; j++)
1241 if (!get_varinfo (j)->is_special_var)
1242 bitmap_set_bit (graph->direct_nodes, j);
1245 for (j = 0; j < graph->size; j++)
1246 graph->eq_rep[j] = -1;
1248 for (j = 0; j < varmap.length (); j++)
1249 graph->indirect_cycles[j] = -1;
1251 FOR_EACH_VEC_ELT (constraints, i, c)
1253 struct constraint_expr lhs = c->lhs;
1254 struct constraint_expr rhs = c->rhs;
1255 unsigned int lhsvar = lhs.var;
1256 unsigned int rhsvar = rhs.var;
1258 if (lhs.type == DEREF)
1260 /* *x = y. */
1261 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1262 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1264 else if (rhs.type == DEREF)
1266 /* x = *y */
1267 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1268 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1269 else
1270 bitmap_clear_bit (graph->direct_nodes, lhsvar);
1272 else if (rhs.type == ADDRESSOF)
1274 varinfo_t v;
1276 /* x = &y */
1277 if (graph->points_to[lhsvar] == NULL)
1278 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1279 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1281 if (graph->pointed_by[rhsvar] == NULL)
1282 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1283 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1285 /* Implicitly, *x = y */
1286 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1288 /* All related variables are no longer direct nodes. */
1289 bitmap_clear_bit (graph->direct_nodes, rhsvar);
1290 v = get_varinfo (rhsvar);
1291 if (!v->is_full_var)
1293 v = get_varinfo (v->head);
1296 bitmap_clear_bit (graph->direct_nodes, v->id);
1297 v = vi_next (v);
1299 while (v != NULL);
1301 bitmap_set_bit (graph->address_taken, rhsvar);
1303 else if (lhsvar > anything_id
1304 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1306 /* x = y */
1307 add_pred_graph_edge (graph, lhsvar, rhsvar);
1308 /* Implicitly, *x = *y */
1309 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1310 FIRST_REF_NODE + rhsvar);
1312 else if (lhs.offset != 0 || rhs.offset != 0)
1314 if (rhs.offset != 0)
1315 bitmap_clear_bit (graph->direct_nodes, lhs.var);
1316 else if (lhs.offset != 0)
1317 bitmap_clear_bit (graph->direct_nodes, rhs.var);
1322 /* Build the constraint graph, adding successor edges. */
1324 static void
1325 build_succ_graph (void)
1327 unsigned i, t;
1328 constraint_t c;
1330 FOR_EACH_VEC_ELT (constraints, i, c)
1332 struct constraint_expr lhs;
1333 struct constraint_expr rhs;
1334 unsigned int lhsvar;
1335 unsigned int rhsvar;
1337 if (!c)
1338 continue;
1340 lhs = c->lhs;
1341 rhs = c->rhs;
1342 lhsvar = find (lhs.var);
1343 rhsvar = find (rhs.var);
1345 if (lhs.type == DEREF)
1347 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1348 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1350 else if (rhs.type == DEREF)
1352 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1353 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1355 else if (rhs.type == ADDRESSOF)
1357 /* x = &y */
1358 gcc_checking_assert (find (rhs.var) == rhs.var);
1359 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1361 else if (lhsvar > anything_id
1362 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1364 add_graph_edge (graph, lhsvar, rhsvar);
1368 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1369 receive pointers. */
1370 t = find (storedanything_id);
1371 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1373 if (!bitmap_bit_p (graph->direct_nodes, i)
1374 && get_varinfo (i)->may_have_pointers)
1375 add_graph_edge (graph, find (i), t);
1378 /* Everything stored to ANYTHING also potentially escapes. */
1379 add_graph_edge (graph, find (escaped_id), t);
1383 /* Changed variables on the last iteration. */
1384 static bitmap changed;
1386 /* Strongly Connected Component visitation info. */
1388 struct scc_info
1390 scc_info (size_t size);
1391 ~scc_info ();
1393 auto_sbitmap visited;
1394 auto_sbitmap deleted;
1395 unsigned int *dfs;
1396 unsigned int *node_mapping;
1397 int current_index;
1398 auto_vec<unsigned> scc_stack;
1402 /* Recursive routine to find strongly connected components in GRAPH.
1403 SI is the SCC info to store the information in, and N is the id of current
1404 graph node we are processing.
1406 This is Tarjan's strongly connected component finding algorithm, as
1407 modified by Nuutila to keep only non-root nodes on the stack.
1408 The algorithm can be found in "On finding the strongly connected
1409 connected components in a directed graph" by Esko Nuutila and Eljas
1410 Soisalon-Soininen, in Information Processing Letters volume 49,
1411 number 1, pages 9-14. */
1413 static void
1414 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1416 unsigned int i;
1417 bitmap_iterator bi;
1418 unsigned int my_dfs;
1420 bitmap_set_bit (si->visited, n);
1421 si->dfs[n] = si->current_index ++;
1422 my_dfs = si->dfs[n];
1424 /* Visit all the successors. */
1425 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1427 unsigned int w;
1429 if (i > LAST_REF_NODE)
1430 break;
1432 w = find (i);
1433 if (bitmap_bit_p (si->deleted, w))
1434 continue;
1436 if (!bitmap_bit_p (si->visited, w))
1437 scc_visit (graph, si, w);
1439 unsigned int t = find (w);
1440 gcc_checking_assert (find (n) == n);
1441 if (si->dfs[t] < si->dfs[n])
1442 si->dfs[n] = si->dfs[t];
1445 /* See if any components have been identified. */
1446 if (si->dfs[n] == my_dfs)
1448 if (si->scc_stack.length () > 0
1449 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1451 bitmap scc = BITMAP_ALLOC (NULL);
1452 unsigned int lowest_node;
1453 bitmap_iterator bi;
1455 bitmap_set_bit (scc, n);
1457 while (si->scc_stack.length () != 0
1458 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1460 unsigned int w = si->scc_stack.pop ();
1462 bitmap_set_bit (scc, w);
1465 lowest_node = bitmap_first_set_bit (scc);
1466 gcc_assert (lowest_node < FIRST_REF_NODE);
1468 /* Collapse the SCC nodes into a single node, and mark the
1469 indirect cycles. */
1470 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1472 if (i < FIRST_REF_NODE)
1474 if (unite (lowest_node, i))
1475 unify_nodes (graph, lowest_node, i, false);
1477 else
1479 unite (lowest_node, i);
1480 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1484 bitmap_set_bit (si->deleted, n);
1486 else
1487 si->scc_stack.safe_push (n);
1490 /* Unify node FROM into node TO, updating the changed count if
1491 necessary when UPDATE_CHANGED is true. */
1493 static void
1494 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1495 bool update_changed)
1497 gcc_checking_assert (to != from && find (to) == to);
1499 if (dump_file && (dump_flags & TDF_DETAILS))
1500 fprintf (dump_file, "Unifying %s to %s\n",
1501 get_varinfo (from)->name,
1502 get_varinfo (to)->name);
1504 if (update_changed)
1505 stats.unified_vars_dynamic++;
1506 else
1507 stats.unified_vars_static++;
1509 merge_graph_nodes (graph, to, from);
1510 if (merge_node_constraints (graph, to, from))
1512 if (update_changed)
1513 bitmap_set_bit (changed, to);
1516 /* Mark TO as changed if FROM was changed. If TO was already marked
1517 as changed, decrease the changed count. */
1519 if (update_changed
1520 && bitmap_clear_bit (changed, from))
1521 bitmap_set_bit (changed, to);
1522 varinfo_t fromvi = get_varinfo (from);
1523 if (fromvi->solution)
1525 /* If the solution changes because of the merging, we need to mark
1526 the variable as changed. */
1527 varinfo_t tovi = get_varinfo (to);
1528 if (bitmap_ior_into (tovi->solution, fromvi->solution))
1530 if (update_changed)
1531 bitmap_set_bit (changed, to);
1534 BITMAP_FREE (fromvi->solution);
1535 if (fromvi->oldsolution)
1536 BITMAP_FREE (fromvi->oldsolution);
1538 if (stats.iterations > 0
1539 && tovi->oldsolution)
1540 BITMAP_FREE (tovi->oldsolution);
1542 if (graph->succs[to])
1543 bitmap_clear_bit (graph->succs[to], to);
1546 /* Information needed to compute the topological ordering of a graph. */
1548 struct topo_info
1550 /* sbitmap of visited nodes. */
1551 sbitmap visited;
1552 /* Array that stores the topological order of the graph, *in
1553 reverse*. */
1554 vec<unsigned> topo_order;
1558 /* Initialize and return a topological info structure. */
1560 static struct topo_info *
1561 init_topo_info (void)
1563 size_t size = graph->size;
1564 struct topo_info *ti = XNEW (struct topo_info);
1565 ti->visited = sbitmap_alloc (size);
1566 bitmap_clear (ti->visited);
1567 ti->topo_order.create (1);
1568 return ti;
1572 /* Free the topological sort info pointed to by TI. */
1574 static void
1575 free_topo_info (struct topo_info *ti)
1577 sbitmap_free (ti->visited);
1578 ti->topo_order.release ();
1579 free (ti);
1582 /* Visit the graph in topological order, and store the order in the
1583 topo_info structure. */
1585 static void
1586 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1587 unsigned int n)
1589 bitmap_iterator bi;
1590 unsigned int j;
1592 bitmap_set_bit (ti->visited, n);
1594 if (graph->succs[n])
1595 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1597 if (!bitmap_bit_p (ti->visited, j))
1598 topo_visit (graph, ti, j);
1601 ti->topo_order.safe_push (n);
1604 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1605 starting solution for y. */
1607 static void
1608 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1609 bitmap delta, bitmap *expanded_delta)
1611 unsigned int lhs = c->lhs.var;
1612 bool flag = false;
1613 bitmap sol = get_varinfo (lhs)->solution;
1614 unsigned int j;
1615 bitmap_iterator bi;
1616 HOST_WIDE_INT roffset = c->rhs.offset;
1618 /* Our IL does not allow this. */
1619 gcc_checking_assert (c->lhs.offset == 0);
1621 /* If the solution of Y contains anything it is good enough to transfer
1622 this to the LHS. */
1623 if (bitmap_bit_p (delta, anything_id))
1625 flag |= bitmap_set_bit (sol, anything_id);
1626 goto done;
1629 /* If we do not know at with offset the rhs is dereferenced compute
1630 the reachability set of DELTA, conservatively assuming it is
1631 dereferenced at all valid offsets. */
1632 if (roffset == UNKNOWN_OFFSET)
1634 delta = solution_set_expand (delta, expanded_delta);
1635 /* No further offset processing is necessary. */
1636 roffset = 0;
1639 /* For each variable j in delta (Sol(y)), add
1640 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1641 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1643 varinfo_t v = get_varinfo (j);
1644 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1645 unsigned HOST_WIDE_INT size = v->size;
1646 unsigned int t;
1648 if (v->is_full_var)
1650 else if (roffset != 0)
1652 if (fieldoffset < 0)
1653 v = get_varinfo (v->head);
1654 else
1655 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1658 /* We have to include all fields that overlap the current field
1659 shifted by roffset. */
1662 t = find (v->id);
1664 /* Adding edges from the special vars is pointless.
1665 They don't have sets that can change. */
1666 if (get_varinfo (t)->is_special_var)
1667 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1668 /* Merging the solution from ESCAPED needlessly increases
1669 the set. Use ESCAPED as representative instead. */
1670 else if (v->id == escaped_id)
1671 flag |= bitmap_set_bit (sol, escaped_id);
1672 else if (v->may_have_pointers
1673 && add_graph_edge (graph, lhs, t))
1674 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1676 if (v->is_full_var
1677 || v->next == 0)
1678 break;
1680 v = vi_next (v);
1682 while (v->offset < fieldoffset + size);
1685 done:
1686 /* If the LHS solution changed, mark the var as changed. */
1687 if (flag)
1689 get_varinfo (lhs)->solution = sol;
1690 bitmap_set_bit (changed, lhs);
1694 /* Process a constraint C that represents *(x + off) = y using DELTA
1695 as the starting solution for x. */
1697 static void
1698 do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1700 unsigned int rhs = c->rhs.var;
1701 bitmap sol = get_varinfo (rhs)->solution;
1702 unsigned int j;
1703 bitmap_iterator bi;
1704 HOST_WIDE_INT loff = c->lhs.offset;
1705 bool escaped_p = false;
1707 /* Our IL does not allow this. */
1708 gcc_checking_assert (c->rhs.offset == 0);
1710 /* If the solution of y contains ANYTHING simply use the ANYTHING
1711 solution. This avoids needlessly increasing the points-to sets. */
1712 if (bitmap_bit_p (sol, anything_id))
1713 sol = get_varinfo (find (anything_id))->solution;
1715 /* If the solution for x contains ANYTHING we have to merge the
1716 solution of y into all pointer variables which we do via
1717 STOREDANYTHING. */
1718 if (bitmap_bit_p (delta, anything_id))
1720 unsigned t = find (storedanything_id);
1721 if (add_graph_edge (graph, t, rhs))
1723 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1724 bitmap_set_bit (changed, t);
1726 return;
1729 /* If we do not know at with offset the rhs is dereferenced compute
1730 the reachability set of DELTA, conservatively assuming it is
1731 dereferenced at all valid offsets. */
1732 if (loff == UNKNOWN_OFFSET)
1734 delta = solution_set_expand (delta, expanded_delta);
1735 loff = 0;
1738 /* For each member j of delta (Sol(x)), add an edge from y to j and
1739 union Sol(y) into Sol(j) */
1740 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1742 varinfo_t v = get_varinfo (j);
1743 unsigned int t;
1744 HOST_WIDE_INT fieldoffset = v->offset + loff;
1745 unsigned HOST_WIDE_INT size = v->size;
1747 if (v->is_full_var)
1749 else if (loff != 0)
1751 if (fieldoffset < 0)
1752 v = get_varinfo (v->head);
1753 else
1754 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1757 /* We have to include all fields that overlap the current field
1758 shifted by loff. */
1761 if (v->may_have_pointers)
1763 /* If v is a global variable then this is an escape point. */
1764 if (v->is_global_var
1765 && !escaped_p)
1767 t = find (escaped_id);
1768 if (add_graph_edge (graph, t, rhs)
1769 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1770 bitmap_set_bit (changed, t);
1771 /* Enough to let rhs escape once. */
1772 escaped_p = true;
1775 if (v->is_special_var)
1776 break;
1778 t = find (v->id);
1779 if (add_graph_edge (graph, t, rhs)
1780 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1781 bitmap_set_bit (changed, t);
1784 if (v->is_full_var
1785 || v->next == 0)
1786 break;
1788 v = vi_next (v);
1790 while (v->offset < fieldoffset + size);
1794 /* Handle a non-simple (simple meaning requires no iteration),
1795 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1797 static void
1798 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1799 bitmap *expanded_delta)
1801 if (c->lhs.type == DEREF)
1803 if (c->rhs.type == ADDRESSOF)
1805 gcc_unreachable ();
1807 else
1809 /* *x = y */
1810 do_ds_constraint (c, delta, expanded_delta);
1813 else if (c->rhs.type == DEREF)
1815 /* x = *y */
1816 if (!(get_varinfo (c->lhs.var)->is_special_var))
1817 do_sd_constraint (graph, c, delta, expanded_delta);
1819 else
1821 bitmap tmp;
1822 bool flag = false;
1824 gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1825 && c->rhs.offset != 0 && c->lhs.offset == 0);
1826 tmp = get_varinfo (c->lhs.var)->solution;
1828 flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1829 expanded_delta);
1831 if (flag)
1832 bitmap_set_bit (changed, c->lhs.var);
1836 /* Initialize and return a new SCC info structure. */
1838 scc_info::scc_info (size_t size) :
1839 visited (size), deleted (size), current_index (0), scc_stack (1)
1841 bitmap_clear (visited);
1842 bitmap_clear (deleted);
1843 node_mapping = XNEWVEC (unsigned int, size);
1844 dfs = XCNEWVEC (unsigned int, size);
1846 for (size_t i = 0; i < size; i++)
1847 node_mapping[i] = i;
1850 /* Free an SCC info structure pointed to by SI */
1852 scc_info::~scc_info ()
1854 free (node_mapping);
1855 free (dfs);
1859 /* Find indirect cycles in GRAPH that occur, using strongly connected
1860 components, and note them in the indirect cycles map.
1862 This technique comes from Ben Hardekopf and Calvin Lin,
1863 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1864 Lines of Code", submitted to PLDI 2007. */
1866 static void
1867 find_indirect_cycles (constraint_graph_t graph)
1869 unsigned int i;
1870 unsigned int size = graph->size;
1871 scc_info si (size);
1873 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1874 if (!bitmap_bit_p (si.visited, i) && find (i) == i)
1875 scc_visit (graph, &si, i);
1878 /* Compute a topological ordering for GRAPH, and store the result in the
1879 topo_info structure TI. */
1881 static void
1882 compute_topo_order (constraint_graph_t graph,
1883 struct topo_info *ti)
1885 unsigned int i;
1886 unsigned int size = graph->size;
1888 for (i = 0; i != size; ++i)
1889 if (!bitmap_bit_p (ti->visited, i) && find (i) == i)
1890 topo_visit (graph, ti, i);
1893 /* Structure used to for hash value numbering of pointer equivalence
1894 classes. */
1896 typedef struct equiv_class_label
1898 hashval_t hashcode;
1899 unsigned int equivalence_class;
1900 bitmap labels;
1901 } *equiv_class_label_t;
1902 typedef const struct equiv_class_label *const_equiv_class_label_t;
1904 /* Equiv_class_label hashtable helpers. */
1906 struct equiv_class_hasher : free_ptr_hash <equiv_class_label>
1908 static inline hashval_t hash (const equiv_class_label *);
1909 static inline bool equal (const equiv_class_label *,
1910 const equiv_class_label *);
1913 /* Hash function for a equiv_class_label_t */
1915 inline hashval_t
1916 equiv_class_hasher::hash (const equiv_class_label *ecl)
1918 return ecl->hashcode;
1921 /* Equality function for two equiv_class_label_t's. */
1923 inline bool
1924 equiv_class_hasher::equal (const equiv_class_label *eql1,
1925 const equiv_class_label *eql2)
1927 return (eql1->hashcode == eql2->hashcode
1928 && bitmap_equal_p (eql1->labels, eql2->labels));
1931 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1932 classes. */
1933 static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
1935 /* A hashtable for mapping a bitmap of labels->location equivalence
1936 classes. */
1937 static hash_table<equiv_class_hasher> *location_equiv_class_table;
1939 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1940 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1941 is equivalent to. */
1943 static equiv_class_label *
1944 equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1945 bitmap labels)
1947 equiv_class_label **slot;
1948 equiv_class_label ecl;
1950 ecl.labels = labels;
1951 ecl.hashcode = bitmap_hash (labels);
1952 slot = table->find_slot (&ecl, INSERT);
1953 if (!*slot)
1955 *slot = XNEW (struct equiv_class_label);
1956 (*slot)->labels = labels;
1957 (*slot)->hashcode = ecl.hashcode;
1958 (*slot)->equivalence_class = 0;
1961 return *slot;
1964 /* Perform offline variable substitution.
1966 This is a worst case quadratic time way of identifying variables
1967 that must have equivalent points-to sets, including those caused by
1968 static cycles, and single entry subgraphs, in the constraint graph.
1970 The technique is described in "Exploiting Pointer and Location
1971 Equivalence to Optimize Pointer Analysis. In the 14th International
1972 Static Analysis Symposium (SAS), August 2007." It is known as the
1973 "HU" algorithm, and is equivalent to value numbering the collapsed
1974 constraint graph including evaluating unions.
1976 The general method of finding equivalence classes is as follows:
1977 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1978 Initialize all non-REF nodes to be direct nodes.
1979 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1980 variable}
1981 For each constraint containing the dereference, we also do the same
1982 thing.
1984 We then compute SCC's in the graph and unify nodes in the same SCC,
1985 including pts sets.
1987 For each non-collapsed node x:
1988 Visit all unvisited explicit incoming edges.
1989 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1990 where y->x.
1991 Lookup the equivalence class for pts(x).
1992 If we found one, equivalence_class(x) = found class.
1993 Otherwise, equivalence_class(x) = new class, and new_class is
1994 added to the lookup table.
1996 All direct nodes with the same equivalence class can be replaced
1997 with a single representative node.
1998 All unlabeled nodes (label == 0) are not pointers and all edges
1999 involving them can be eliminated.
2000 We perform these optimizations during rewrite_constraints
2002 In addition to pointer equivalence class finding, we also perform
2003 location equivalence class finding. This is the set of variables
2004 that always appear together in points-to sets. We use this to
2005 compress the size of the points-to sets. */
2007 /* Current maximum pointer equivalence class id. */
2008 static int pointer_equiv_class;
2010 /* Current maximum location equivalence class id. */
2011 static int location_equiv_class;
2013 /* Recursive routine to find strongly connected components in GRAPH,
2014 and label it's nodes with DFS numbers. */
2016 static void
2017 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2019 unsigned int i;
2020 bitmap_iterator bi;
2021 unsigned int my_dfs;
2023 gcc_checking_assert (si->node_mapping[n] == n);
2024 bitmap_set_bit (si->visited, n);
2025 si->dfs[n] = si->current_index ++;
2026 my_dfs = si->dfs[n];
2028 /* Visit all the successors. */
2029 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2031 unsigned int w = si->node_mapping[i];
2033 if (bitmap_bit_p (si->deleted, w))
2034 continue;
2036 if (!bitmap_bit_p (si->visited, w))
2037 condense_visit (graph, si, w);
2039 unsigned int t = si->node_mapping[w];
2040 gcc_checking_assert (si->node_mapping[n] == n);
2041 if (si->dfs[t] < si->dfs[n])
2042 si->dfs[n] = si->dfs[t];
2045 /* Visit all the implicit predecessors. */
2046 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2048 unsigned int w = si->node_mapping[i];
2050 if (bitmap_bit_p (si->deleted, w))
2051 continue;
2053 if (!bitmap_bit_p (si->visited, w))
2054 condense_visit (graph, si, w);
2056 unsigned int t = si->node_mapping[w];
2057 gcc_assert (si->node_mapping[n] == n);
2058 if (si->dfs[t] < si->dfs[n])
2059 si->dfs[n] = si->dfs[t];
2062 /* See if any components have been identified. */
2063 if (si->dfs[n] == my_dfs)
2065 while (si->scc_stack.length () != 0
2066 && si->dfs[si->scc_stack.last ()] >= my_dfs)
2068 unsigned int w = si->scc_stack.pop ();
2069 si->node_mapping[w] = n;
2071 if (!bitmap_bit_p (graph->direct_nodes, w))
2072 bitmap_clear_bit (graph->direct_nodes, n);
2074 /* Unify our nodes. */
2075 if (graph->preds[w])
2077 if (!graph->preds[n])
2078 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2079 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2081 if (graph->implicit_preds[w])
2083 if (!graph->implicit_preds[n])
2084 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2085 bitmap_ior_into (graph->implicit_preds[n],
2086 graph->implicit_preds[w]);
2088 if (graph->points_to[w])
2090 if (!graph->points_to[n])
2091 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2092 bitmap_ior_into (graph->points_to[n],
2093 graph->points_to[w]);
2096 bitmap_set_bit (si->deleted, n);
2098 else
2099 si->scc_stack.safe_push (n);
2102 /* Label pointer equivalences.
2104 This performs a value numbering of the constraint graph to
2105 discover which variables will always have the same points-to sets
2106 under the current set of constraints.
2108 The way it value numbers is to store the set of points-to bits
2109 generated by the constraints and graph edges. This is just used as a
2110 hash and equality comparison. The *actual set of points-to bits* is
2111 completely irrelevant, in that we don't care about being able to
2112 extract them later.
2114 The equality values (currently bitmaps) just have to satisfy a few
2115 constraints, the main ones being:
2116 1. The combining operation must be order independent.
2117 2. The end result of a given set of operations must be unique iff the
2118 combination of input values is unique
2119 3. Hashable. */
2121 static void
2122 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2124 unsigned int i, first_pred;
2125 bitmap_iterator bi;
2127 bitmap_set_bit (si->visited, n);
2129 /* Label and union our incoming edges's points to sets. */
2130 first_pred = -1U;
2131 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2133 unsigned int w = si->node_mapping[i];
2134 if (!bitmap_bit_p (si->visited, w))
2135 label_visit (graph, si, w);
2137 /* Skip unused edges */
2138 if (w == n || graph->pointer_label[w] == 0)
2139 continue;
2141 if (graph->points_to[w])
2143 if (!graph->points_to[n])
2145 if (first_pred == -1U)
2146 first_pred = w;
2147 else
2149 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2150 bitmap_ior (graph->points_to[n],
2151 graph->points_to[first_pred],
2152 graph->points_to[w]);
2155 else
2156 bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
2160 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2161 if (!bitmap_bit_p (graph->direct_nodes, n))
2163 if (!graph->points_to[n])
2165 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2166 if (first_pred != -1U)
2167 bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
2169 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2170 graph->pointer_label[n] = pointer_equiv_class++;
2171 equiv_class_label_t ecl;
2172 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2173 graph->points_to[n]);
2174 ecl->equivalence_class = graph->pointer_label[n];
2175 return;
2178 /* If there was only a single non-empty predecessor the pointer equiv
2179 class is the same. */
2180 if (!graph->points_to[n])
2182 if (first_pred != -1U)
2184 graph->pointer_label[n] = graph->pointer_label[first_pred];
2185 graph->points_to[n] = graph->points_to[first_pred];
2187 return;
2190 if (!bitmap_empty_p (graph->points_to[n]))
2192 equiv_class_label_t ecl;
2193 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2194 graph->points_to[n]);
2195 if (ecl->equivalence_class == 0)
2196 ecl->equivalence_class = pointer_equiv_class++;
2197 else
2199 BITMAP_FREE (graph->points_to[n]);
2200 graph->points_to[n] = ecl->labels;
2202 graph->pointer_label[n] = ecl->equivalence_class;
2206 /* Print the pred graph in dot format. */
2208 static void
2209 dump_pred_graph (struct scc_info *si, FILE *file)
2211 unsigned int i;
2213 /* Only print the graph if it has already been initialized: */
2214 if (!graph)
2215 return;
2217 /* Prints the header of the dot file: */
2218 fprintf (file, "strict digraph {\n");
2219 fprintf (file, " node [\n shape = box\n ]\n");
2220 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
2221 fprintf (file, "\n // List of nodes and complex constraints in "
2222 "the constraint graph:\n");
2224 /* The next lines print the nodes in the graph together with the
2225 complex constraints attached to them. */
2226 for (i = 1; i < graph->size; i++)
2228 if (i == FIRST_REF_NODE)
2229 continue;
2230 if (si->node_mapping[i] != i)
2231 continue;
2232 if (i < FIRST_REF_NODE)
2233 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2234 else
2235 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2236 if (graph->points_to[i]
2237 && !bitmap_empty_p (graph->points_to[i]))
2239 if (i < FIRST_REF_NODE)
2240 fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
2241 else
2242 fprintf (file, "[label=\"*%s = {",
2243 get_varinfo (i - FIRST_REF_NODE)->name);
2244 unsigned j;
2245 bitmap_iterator bi;
2246 EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
2247 fprintf (file, " %d", j);
2248 fprintf (file, " }\"]");
2250 fprintf (file, ";\n");
2253 /* Go over the edges. */
2254 fprintf (file, "\n // Edges in the constraint graph:\n");
2255 for (i = 1; i < graph->size; i++)
2257 unsigned j;
2258 bitmap_iterator bi;
2259 if (si->node_mapping[i] != i)
2260 continue;
2261 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
2263 unsigned from = si->node_mapping[j];
2264 if (from < FIRST_REF_NODE)
2265 fprintf (file, "\"%s\"", get_varinfo (from)->name);
2266 else
2267 fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name);
2268 fprintf (file, " -> ");
2269 if (i < FIRST_REF_NODE)
2270 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2271 else
2272 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2273 fprintf (file, ";\n");
2277 /* Prints the tail of the dot file. */
2278 fprintf (file, "}\n");
2281 /* Perform offline variable substitution, discovering equivalence
2282 classes, and eliminating non-pointer variables. */
2284 static struct scc_info *
2285 perform_var_substitution (constraint_graph_t graph)
2287 unsigned int i;
2288 unsigned int size = graph->size;
2289 scc_info *si = new scc_info (size);
2291 bitmap_obstack_initialize (&iteration_obstack);
2292 pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
2293 location_equiv_class_table
2294 = new hash_table<equiv_class_hasher> (511);
2295 pointer_equiv_class = 1;
2296 location_equiv_class = 1;
2298 /* Condense the nodes, which means to find SCC's, count incoming
2299 predecessors, and unite nodes in SCC's. */
2300 for (i = 1; i < FIRST_REF_NODE; i++)
2301 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2302 condense_visit (graph, si, si->node_mapping[i]);
2304 if (dump_file && (dump_flags & TDF_GRAPH))
2306 fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
2307 "in dot format:\n");
2308 dump_pred_graph (si, dump_file);
2309 fprintf (dump_file, "\n\n");
2312 bitmap_clear (si->visited);
2313 /* Actually the label the nodes for pointer equivalences */
2314 for (i = 1; i < FIRST_REF_NODE; i++)
2315 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2316 label_visit (graph, si, si->node_mapping[i]);
2318 /* Calculate location equivalence labels. */
2319 for (i = 1; i < FIRST_REF_NODE; i++)
2321 bitmap pointed_by;
2322 bitmap_iterator bi;
2323 unsigned int j;
2325 if (!graph->pointed_by[i])
2326 continue;
2327 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2329 /* Translate the pointed-by mapping for pointer equivalence
2330 labels. */
2331 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2333 bitmap_set_bit (pointed_by,
2334 graph->pointer_label[si->node_mapping[j]]);
2336 /* The original pointed_by is now dead. */
2337 BITMAP_FREE (graph->pointed_by[i]);
2339 /* Look up the location equivalence label if one exists, or make
2340 one otherwise. */
2341 equiv_class_label_t ecl;
2342 ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
2343 if (ecl->equivalence_class == 0)
2344 ecl->equivalence_class = location_equiv_class++;
2345 else
2347 if (dump_file && (dump_flags & TDF_DETAILS))
2348 fprintf (dump_file, "Found location equivalence for node %s\n",
2349 get_varinfo (i)->name);
2350 BITMAP_FREE (pointed_by);
2352 graph->loc_label[i] = ecl->equivalence_class;
2356 if (dump_file && (dump_flags & TDF_DETAILS))
2357 for (i = 1; i < FIRST_REF_NODE; i++)
2359 unsigned j = si->node_mapping[i];
2360 if (j != i)
2362 fprintf (dump_file, "%s node id %d ",
2363 bitmap_bit_p (graph->direct_nodes, i)
2364 ? "Direct" : "Indirect", i);
2365 if (i < FIRST_REF_NODE)
2366 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2367 else
2368 fprintf (dump_file, "\"*%s\"",
2369 get_varinfo (i - FIRST_REF_NODE)->name);
2370 fprintf (dump_file, " mapped to SCC leader node id %d ", j);
2371 if (j < FIRST_REF_NODE)
2372 fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
2373 else
2374 fprintf (dump_file, "\"*%s\"\n",
2375 get_varinfo (j - FIRST_REF_NODE)->name);
2377 else
2379 fprintf (dump_file,
2380 "Equivalence classes for %s node id %d ",
2381 bitmap_bit_p (graph->direct_nodes, i)
2382 ? "direct" : "indirect", i);
2383 if (i < FIRST_REF_NODE)
2384 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2385 else
2386 fprintf (dump_file, "\"*%s\"",
2387 get_varinfo (i - FIRST_REF_NODE)->name);
2388 fprintf (dump_file,
2389 ": pointer %d, location %d\n",
2390 graph->pointer_label[i], graph->loc_label[i]);
2394 /* Quickly eliminate our non-pointer variables. */
2396 for (i = 1; i < FIRST_REF_NODE; i++)
2398 unsigned int node = si->node_mapping[i];
2400 if (graph->pointer_label[node] == 0)
2402 if (dump_file && (dump_flags & TDF_DETAILS))
2403 fprintf (dump_file,
2404 "%s is a non-pointer variable, eliminating edges.\n",
2405 get_varinfo (node)->name);
2406 stats.nonpointer_vars++;
2407 clear_edges_for_node (graph, node);
2411 return si;
2414 /* Free information that was only necessary for variable
2415 substitution. */
2417 static void
2418 free_var_substitution_info (struct scc_info *si)
2420 delete si;
2421 free (graph->pointer_label);
2422 free (graph->loc_label);
2423 free (graph->pointed_by);
2424 free (graph->points_to);
2425 free (graph->eq_rep);
2426 sbitmap_free (graph->direct_nodes);
2427 delete pointer_equiv_class_table;
2428 pointer_equiv_class_table = NULL;
2429 delete location_equiv_class_table;
2430 location_equiv_class_table = NULL;
2431 bitmap_obstack_release (&iteration_obstack);
2434 /* Return an existing node that is equivalent to NODE, which has
2435 equivalence class LABEL, if one exists. Return NODE otherwise. */
2437 static unsigned int
2438 find_equivalent_node (constraint_graph_t graph,
2439 unsigned int node, unsigned int label)
2441 /* If the address version of this variable is unused, we can
2442 substitute it for anything else with the same label.
2443 Otherwise, we know the pointers are equivalent, but not the
2444 locations, and we can unite them later. */
2446 if (!bitmap_bit_p (graph->address_taken, node))
2448 gcc_checking_assert (label < graph->size);
2450 if (graph->eq_rep[label] != -1)
2452 /* Unify the two variables since we know they are equivalent. */
2453 if (unite (graph->eq_rep[label], node))
2454 unify_nodes (graph, graph->eq_rep[label], node, false);
2455 return graph->eq_rep[label];
2457 else
2459 graph->eq_rep[label] = node;
2460 graph->pe_rep[label] = node;
2463 else
2465 gcc_checking_assert (label < graph->size);
2466 graph->pe[node] = label;
2467 if (graph->pe_rep[label] == -1)
2468 graph->pe_rep[label] = node;
2471 return node;
2474 /* Unite pointer equivalent but not location equivalent nodes in
2475 GRAPH. This may only be performed once variable substitution is
2476 finished. */
2478 static void
2479 unite_pointer_equivalences (constraint_graph_t graph)
2481 unsigned int i;
2483 /* Go through the pointer equivalences and unite them to their
2484 representative, if they aren't already. */
2485 for (i = 1; i < FIRST_REF_NODE; i++)
2487 unsigned int label = graph->pe[i];
2488 if (label)
2490 int label_rep = graph->pe_rep[label];
2492 if (label_rep == -1)
2493 continue;
2495 label_rep = find (label_rep);
2496 if (label_rep >= 0 && unite (label_rep, find (i)))
2497 unify_nodes (graph, label_rep, i, false);
2502 /* Move complex constraints to the GRAPH nodes they belong to. */
2504 static void
2505 move_complex_constraints (constraint_graph_t graph)
2507 int i;
2508 constraint_t c;
2510 FOR_EACH_VEC_ELT (constraints, i, c)
2512 if (c)
2514 struct constraint_expr lhs = c->lhs;
2515 struct constraint_expr rhs = c->rhs;
2517 if (lhs.type == DEREF)
2519 insert_into_complex (graph, lhs.var, c);
2521 else if (rhs.type == DEREF)
2523 if (!(get_varinfo (lhs.var)->is_special_var))
2524 insert_into_complex (graph, rhs.var, c);
2526 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2527 && (lhs.offset != 0 || rhs.offset != 0))
2529 insert_into_complex (graph, rhs.var, c);
2536 /* Optimize and rewrite complex constraints while performing
2537 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2538 result of perform_variable_substitution. */
2540 static void
2541 rewrite_constraints (constraint_graph_t graph,
2542 struct scc_info *si)
2544 int i;
2545 constraint_t c;
2547 if (flag_checking)
2549 for (unsigned int j = 0; j < graph->size; j++)
2550 gcc_assert (find (j) == j);
2553 FOR_EACH_VEC_ELT (constraints, i, c)
2555 struct constraint_expr lhs = c->lhs;
2556 struct constraint_expr rhs = c->rhs;
2557 unsigned int lhsvar = find (lhs.var);
2558 unsigned int rhsvar = find (rhs.var);
2559 unsigned int lhsnode, rhsnode;
2560 unsigned int lhslabel, rhslabel;
2562 lhsnode = si->node_mapping[lhsvar];
2563 rhsnode = si->node_mapping[rhsvar];
2564 lhslabel = graph->pointer_label[lhsnode];
2565 rhslabel = graph->pointer_label[rhsnode];
2567 /* See if it is really a non-pointer variable, and if so, ignore
2568 the constraint. */
2569 if (lhslabel == 0)
2571 if (dump_file && (dump_flags & TDF_DETAILS))
2574 fprintf (dump_file, "%s is a non-pointer variable, "
2575 "ignoring constraint:",
2576 get_varinfo (lhs.var)->name);
2577 dump_constraint (dump_file, c);
2578 fprintf (dump_file, "\n");
2580 constraints[i] = NULL;
2581 continue;
2584 if (rhslabel == 0)
2586 if (dump_file && (dump_flags & TDF_DETAILS))
2589 fprintf (dump_file, "%s is a non-pointer variable, "
2590 "ignoring constraint:",
2591 get_varinfo (rhs.var)->name);
2592 dump_constraint (dump_file, c);
2593 fprintf (dump_file, "\n");
2595 constraints[i] = NULL;
2596 continue;
2599 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2600 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2601 c->lhs.var = lhsvar;
2602 c->rhs.var = rhsvar;
2606 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2607 part of an SCC, false otherwise. */
2609 static bool
2610 eliminate_indirect_cycles (unsigned int node)
2612 if (graph->indirect_cycles[node] != -1
2613 && !bitmap_empty_p (get_varinfo (node)->solution))
2615 unsigned int i;
2616 auto_vec<unsigned> queue;
2617 int queuepos;
2618 unsigned int to = find (graph->indirect_cycles[node]);
2619 bitmap_iterator bi;
2621 /* We can't touch the solution set and call unify_nodes
2622 at the same time, because unify_nodes is going to do
2623 bitmap unions into it. */
2625 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2627 if (find (i) == i && i != to)
2629 if (unite (to, i))
2630 queue.safe_push (i);
2634 for (queuepos = 0;
2635 queue.iterate (queuepos, &i);
2636 queuepos++)
2638 unify_nodes (graph, to, i, true);
2640 return true;
2642 return false;
2645 /* Solve the constraint graph GRAPH using our worklist solver.
2646 This is based on the PW* family of solvers from the "Efficient Field
2647 Sensitive Pointer Analysis for C" paper.
2648 It works by iterating over all the graph nodes, processing the complex
2649 constraints and propagating the copy constraints, until everything stops
2650 changed. This corresponds to steps 6-8 in the solving list given above. */
2652 static void
2653 solve_graph (constraint_graph_t graph)
2655 unsigned int size = graph->size;
2656 unsigned int i;
2657 bitmap pts;
2659 changed = BITMAP_ALLOC (NULL);
2661 /* Mark all initial non-collapsed nodes as changed. */
2662 for (i = 1; i < size; i++)
2664 varinfo_t ivi = get_varinfo (i);
2665 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2666 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2667 || graph->complex[i].length () > 0))
2668 bitmap_set_bit (changed, i);
2671 /* Allocate a bitmap to be used to store the changed bits. */
2672 pts = BITMAP_ALLOC (&pta_obstack);
2674 while (!bitmap_empty_p (changed))
2676 unsigned int i;
2677 struct topo_info *ti = init_topo_info ();
2678 stats.iterations++;
2680 bitmap_obstack_initialize (&iteration_obstack);
2682 compute_topo_order (graph, ti);
2684 while (ti->topo_order.length () != 0)
2687 i = ti->topo_order.pop ();
2689 /* If this variable is not a representative, skip it. */
2690 if (find (i) != i)
2691 continue;
2693 /* In certain indirect cycle cases, we may merge this
2694 variable to another. */
2695 if (eliminate_indirect_cycles (i) && find (i) != i)
2696 continue;
2698 /* If the node has changed, we need to process the
2699 complex constraints and outgoing edges again. */
2700 if (bitmap_clear_bit (changed, i))
2702 unsigned int j;
2703 constraint_t c;
2704 bitmap solution;
2705 vec<constraint_t> complex = graph->complex[i];
2706 varinfo_t vi = get_varinfo (i);
2707 bool solution_empty;
2709 /* Compute the changed set of solution bits. If anything
2710 is in the solution just propagate that. */
2711 if (bitmap_bit_p (vi->solution, anything_id))
2713 /* If anything is also in the old solution there is
2714 nothing to do.
2715 ??? But we shouldn't ended up with "changed" set ... */
2716 if (vi->oldsolution
2717 && bitmap_bit_p (vi->oldsolution, anything_id))
2718 continue;
2719 bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2721 else if (vi->oldsolution)
2722 bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2723 else
2724 bitmap_copy (pts, vi->solution);
2726 if (bitmap_empty_p (pts))
2727 continue;
2729 if (vi->oldsolution)
2730 bitmap_ior_into (vi->oldsolution, pts);
2731 else
2733 vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2734 bitmap_copy (vi->oldsolution, pts);
2737 solution = vi->solution;
2738 solution_empty = bitmap_empty_p (solution);
2740 /* Process the complex constraints */
2741 bitmap expanded_pts = NULL;
2742 FOR_EACH_VEC_ELT (complex, j, c)
2744 /* XXX: This is going to unsort the constraints in
2745 some cases, which will occasionally add duplicate
2746 constraints during unification. This does not
2747 affect correctness. */
2748 c->lhs.var = find (c->lhs.var);
2749 c->rhs.var = find (c->rhs.var);
2751 /* The only complex constraint that can change our
2752 solution to non-empty, given an empty solution,
2753 is a constraint where the lhs side is receiving
2754 some set from elsewhere. */
2755 if (!solution_empty || c->lhs.type != DEREF)
2756 do_complex_constraint (graph, c, pts, &expanded_pts);
2758 BITMAP_FREE (expanded_pts);
2760 solution_empty = bitmap_empty_p (solution);
2762 if (!solution_empty)
2764 bitmap_iterator bi;
2765 unsigned eff_escaped_id = find (escaped_id);
2767 /* Propagate solution to all successors. */
2768 unsigned to_remove = ~0U;
2769 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2770 0, j, bi)
2772 if (to_remove != ~0U)
2774 bitmap_clear_bit (graph->succs[i], to_remove);
2775 to_remove = ~0U;
2777 unsigned int to = find (j);
2778 if (to != j)
2780 /* Update the succ graph, avoiding duplicate
2781 work. */
2782 to_remove = j;
2783 if (! bitmap_set_bit (graph->succs[i], to))
2784 continue;
2785 /* We eventually end up processing 'to' twice
2786 as it is undefined whether bitmap iteration
2787 iterates over bits set during iteration.
2788 Play safe instead of doing tricks. */
2790 /* Don't try to propagate to ourselves. */
2791 if (to == i)
2792 continue;
2794 bitmap tmp = get_varinfo (to)->solution;
2795 bool flag = false;
2797 /* If we propagate from ESCAPED use ESCAPED as
2798 placeholder. */
2799 if (i == eff_escaped_id)
2800 flag = bitmap_set_bit (tmp, escaped_id);
2801 else
2802 flag = bitmap_ior_into (tmp, pts);
2804 if (flag)
2805 bitmap_set_bit (changed, to);
2807 if (to_remove != ~0U)
2808 bitmap_clear_bit (graph->succs[i], to_remove);
2812 free_topo_info (ti);
2813 bitmap_obstack_release (&iteration_obstack);
2816 BITMAP_FREE (pts);
2817 BITMAP_FREE (changed);
2818 bitmap_obstack_release (&oldpta_obstack);
2821 /* Map from trees to variable infos. */
2822 static hash_map<tree, varinfo_t> *vi_for_tree;
2825 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2827 static void
2828 insert_vi_for_tree (tree t, varinfo_t vi)
2830 gcc_assert (vi);
2831 gcc_assert (!vi_for_tree->put (t, vi));
2834 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2835 exist in the map, return NULL, otherwise, return the varinfo we found. */
2837 static varinfo_t
2838 lookup_vi_for_tree (tree t)
2840 varinfo_t *slot = vi_for_tree->get (t);
2841 if (slot == NULL)
2842 return NULL;
2844 return *slot;
2847 /* Return a printable name for DECL */
2849 static const char *
2850 alias_get_name (tree decl)
2852 const char *res = "NULL";
2853 if (dump_file)
2855 char *temp = NULL;
2856 if (TREE_CODE (decl) == SSA_NAME)
2858 res = get_name (decl);
2859 temp = xasprintf ("%s_%u", res ? res : "", SSA_NAME_VERSION (decl));
2861 else if (HAS_DECL_ASSEMBLER_NAME_P (decl)
2862 && DECL_ASSEMBLER_NAME_SET_P (decl))
2863 res = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME_RAW (decl));
2864 else if (DECL_P (decl))
2866 res = get_name (decl);
2867 if (!res)
2868 temp = xasprintf ("D.%u", DECL_UID (decl));
2871 if (temp)
2873 res = ggc_strdup (temp);
2874 free (temp);
2878 return res;
2881 /* Find the variable id for tree T in the map.
2882 If T doesn't exist in the map, create an entry for it and return it. */
2884 static varinfo_t
2885 get_vi_for_tree (tree t)
2887 varinfo_t *slot = vi_for_tree->get (t);
2888 if (slot == NULL)
2890 unsigned int id = create_variable_info_for (t, alias_get_name (t), false);
2891 return get_varinfo (id);
2894 return *slot;
2897 /* Get a scalar constraint expression for a new temporary variable. */
2899 static struct constraint_expr
2900 new_scalar_tmp_constraint_exp (const char *name, bool add_id)
2902 struct constraint_expr tmp;
2903 varinfo_t vi;
2905 vi = new_var_info (NULL_TREE, name, add_id);
2906 vi->offset = 0;
2907 vi->size = -1;
2908 vi->fullsize = -1;
2909 vi->is_full_var = 1;
2910 vi->is_reg_var = 1;
2912 tmp.var = vi->id;
2913 tmp.type = SCALAR;
2914 tmp.offset = 0;
2916 return tmp;
2919 /* Get a constraint expression vector from an SSA_VAR_P node.
2920 If address_p is true, the result will be taken its address of. */
2922 static void
2923 get_constraint_for_ssa_var (tree t, vec<ce_s> *results, bool address_p)
2925 struct constraint_expr cexpr;
2926 varinfo_t vi;
2928 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2929 gcc_assert (TREE_CODE (t) == SSA_NAME || DECL_P (t));
2931 /* For parameters, get at the points-to set for the actual parm
2932 decl. */
2933 if (TREE_CODE (t) == SSA_NAME
2934 && SSA_NAME_IS_DEFAULT_DEF (t)
2935 && (TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2936 || TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL))
2938 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2939 return;
2942 /* For global variables resort to the alias target. */
2943 if (VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
2945 varpool_node *node = varpool_node::get (t);
2946 if (node && node->alias && node->analyzed)
2948 node = node->ultimate_alias_target ();
2949 /* Canonicalize the PT uid of all aliases to the ultimate target.
2950 ??? Hopefully the set of aliases can't change in a way that
2951 changes the ultimate alias target. */
2952 gcc_assert ((! DECL_PT_UID_SET_P (node->decl)
2953 || DECL_PT_UID (node->decl) == DECL_UID (node->decl))
2954 && (! DECL_PT_UID_SET_P (t)
2955 || DECL_PT_UID (t) == DECL_UID (node->decl)));
2956 DECL_PT_UID (t) = DECL_UID (node->decl);
2957 t = node->decl;
2960 /* If this is decl may bind to NULL note that. */
2961 if (address_p
2962 && (! node || ! node->nonzero_address ()))
2964 cexpr.var = nothing_id;
2965 cexpr.type = SCALAR;
2966 cexpr.offset = 0;
2967 results->safe_push (cexpr);
2971 vi = get_vi_for_tree (t);
2972 cexpr.var = vi->id;
2973 cexpr.type = SCALAR;
2974 cexpr.offset = 0;
2976 /* If we are not taking the address of the constraint expr, add all
2977 sub-fiels of the variable as well. */
2978 if (!address_p
2979 && !vi->is_full_var)
2981 for (; vi; vi = vi_next (vi))
2983 cexpr.var = vi->id;
2984 results->safe_push (cexpr);
2986 return;
2989 results->safe_push (cexpr);
2992 /* Process constraint T, performing various simplifications and then
2993 adding it to our list of overall constraints. */
2995 static void
2996 process_constraint (constraint_t t)
2998 struct constraint_expr rhs = t->rhs;
2999 struct constraint_expr lhs = t->lhs;
3001 gcc_assert (rhs.var < varmap.length ());
3002 gcc_assert (lhs.var < varmap.length ());
3004 /* If we didn't get any useful constraint from the lhs we get
3005 &ANYTHING as fallback from get_constraint_for. Deal with
3006 it here by turning it into *ANYTHING. */
3007 if (lhs.type == ADDRESSOF
3008 && lhs.var == anything_id)
3009 lhs.type = DEREF;
3011 /* ADDRESSOF on the lhs is invalid. */
3012 gcc_assert (lhs.type != ADDRESSOF);
3014 /* We shouldn't add constraints from things that cannot have pointers.
3015 It's not completely trivial to avoid in the callers, so do it here. */
3016 if (rhs.type != ADDRESSOF
3017 && !get_varinfo (rhs.var)->may_have_pointers)
3018 return;
3020 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3021 if (!get_varinfo (lhs.var)->may_have_pointers)
3022 return;
3024 /* This can happen in our IR with things like n->a = *p */
3025 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
3027 /* Split into tmp = *rhs, *lhs = tmp */
3028 struct constraint_expr tmplhs;
3029 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp", true);
3030 process_constraint (new_constraint (tmplhs, rhs));
3031 process_constraint (new_constraint (lhs, tmplhs));
3033 else if ((rhs.type != SCALAR || rhs.offset != 0) && lhs.type == DEREF)
3035 /* Split into tmp = &rhs, *lhs = tmp */
3036 struct constraint_expr tmplhs;
3037 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp", true);
3038 process_constraint (new_constraint (tmplhs, rhs));
3039 process_constraint (new_constraint (lhs, tmplhs));
3041 else
3043 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
3044 constraints.safe_push (t);
3049 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3050 structure. */
3052 static HOST_WIDE_INT
3053 bitpos_of_field (const tree fdecl)
3055 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl))
3056 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl)))
3057 return -1;
3059 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT
3060 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl)));
3064 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3065 resulting constraint expressions in *RESULTS. */
3067 static void
3068 get_constraint_for_ptr_offset (tree ptr, tree offset,
3069 vec<ce_s> *results)
3071 struct constraint_expr c;
3072 unsigned int j, n;
3073 HOST_WIDE_INT rhsoffset;
3075 /* If we do not do field-sensitive PTA adding offsets to pointers
3076 does not change the points-to solution. */
3077 if (!use_field_sensitive)
3079 get_constraint_for_rhs (ptr, results);
3080 return;
3083 /* If the offset is not a non-negative integer constant that fits
3084 in a HOST_WIDE_INT, we have to fall back to a conservative
3085 solution which includes all sub-fields of all pointed-to
3086 variables of ptr. */
3087 if (offset == NULL_TREE
3088 || TREE_CODE (offset) != INTEGER_CST)
3089 rhsoffset = UNKNOWN_OFFSET;
3090 else
3092 /* Sign-extend the offset. */
3093 offset_int soffset = offset_int::from (wi::to_wide (offset), SIGNED);
3094 if (!wi::fits_shwi_p (soffset))
3095 rhsoffset = UNKNOWN_OFFSET;
3096 else
3098 /* Make sure the bit-offset also fits. */
3099 HOST_WIDE_INT rhsunitoffset = soffset.to_shwi ();
3100 rhsoffset = rhsunitoffset * (unsigned HOST_WIDE_INT) BITS_PER_UNIT;
3101 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
3102 rhsoffset = UNKNOWN_OFFSET;
3106 get_constraint_for_rhs (ptr, results);
3107 if (rhsoffset == 0)
3108 return;
3110 /* As we are eventually appending to the solution do not use
3111 vec::iterate here. */
3112 n = results->length ();
3113 for (j = 0; j < n; j++)
3115 varinfo_t curr;
3116 c = (*results)[j];
3117 curr = get_varinfo (c.var);
3119 if (c.type == ADDRESSOF
3120 /* If this varinfo represents a full variable just use it. */
3121 && curr->is_full_var)
3123 else if (c.type == ADDRESSOF
3124 /* If we do not know the offset add all subfields. */
3125 && rhsoffset == UNKNOWN_OFFSET)
3127 varinfo_t temp = get_varinfo (curr->head);
3130 struct constraint_expr c2;
3131 c2.var = temp->id;
3132 c2.type = ADDRESSOF;
3133 c2.offset = 0;
3134 if (c2.var != c.var)
3135 results->safe_push (c2);
3136 temp = vi_next (temp);
3138 while (temp);
3140 else if (c.type == ADDRESSOF)
3142 varinfo_t temp;
3143 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
3145 /* If curr->offset + rhsoffset is less than zero adjust it. */
3146 if (rhsoffset < 0
3147 && curr->offset < offset)
3148 offset = 0;
3150 /* We have to include all fields that overlap the current
3151 field shifted by rhsoffset. And we include at least
3152 the last or the first field of the variable to represent
3153 reachability of off-bound addresses, in particular &object + 1,
3154 conservatively correct. */
3155 temp = first_or_preceding_vi_for_offset (curr, offset);
3156 c.var = temp->id;
3157 c.offset = 0;
3158 temp = vi_next (temp);
3159 while (temp
3160 && temp->offset < offset + curr->size)
3162 struct constraint_expr c2;
3163 c2.var = temp->id;
3164 c2.type = ADDRESSOF;
3165 c2.offset = 0;
3166 results->safe_push (c2);
3167 temp = vi_next (temp);
3170 else if (c.type == SCALAR)
3172 gcc_assert (c.offset == 0);
3173 c.offset = rhsoffset;
3175 else
3176 /* We shouldn't get any DEREFs here. */
3177 gcc_unreachable ();
3179 (*results)[j] = c;
3184 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3185 If address_p is true the result will be taken its address of.
3186 If lhs_p is true then the constraint expression is assumed to be used
3187 as the lhs. */
3189 static void
3190 get_constraint_for_component_ref (tree t, vec<ce_s> *results,
3191 bool address_p, bool lhs_p)
3193 tree orig_t = t;
3194 poly_int64 bitsize = -1;
3195 poly_int64 bitmaxsize = -1;
3196 poly_int64 bitpos;
3197 bool reverse;
3198 tree forzero;
3200 /* Some people like to do cute things like take the address of
3201 &0->a.b */
3202 forzero = t;
3203 while (handled_component_p (forzero)
3204 || INDIRECT_REF_P (forzero)
3205 || TREE_CODE (forzero) == MEM_REF)
3206 forzero = TREE_OPERAND (forzero, 0);
3208 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3210 struct constraint_expr temp;
3212 temp.offset = 0;
3213 temp.var = integer_id;
3214 temp.type = SCALAR;
3215 results->safe_push (temp);
3216 return;
3219 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize, &reverse);
3221 /* We can end up here for component references on a
3222 VIEW_CONVERT_EXPR <>(&foobar) or things like a
3223 BIT_FIELD_REF <&MEM[(void *)&b + 4B], ...>. So for
3224 symbolic constants simply give up. */
3225 if (TREE_CODE (t) == ADDR_EXPR)
3227 constraint_expr result;
3228 result.type = SCALAR;
3229 result.var = anything_id;
3230 result.offset = 0;
3231 results->safe_push (result);
3232 return;
3235 /* Pretend to take the address of the base, we'll take care of
3236 adding the required subset of sub-fields below. */
3237 get_constraint_for_1 (t, results, true, lhs_p);
3238 /* Strip off nothing_id. */
3239 if (results->length () == 2)
3241 gcc_assert ((*results)[0].var == nothing_id);
3242 results->unordered_remove (0);
3244 gcc_assert (results->length () == 1);
3245 struct constraint_expr &result = results->last ();
3247 if (result.type == SCALAR
3248 && get_varinfo (result.var)->is_full_var)
3249 /* For single-field vars do not bother about the offset. */
3250 result.offset = 0;
3251 else if (result.type == SCALAR)
3253 /* In languages like C, you can access one past the end of an
3254 array. You aren't allowed to dereference it, so we can
3255 ignore this constraint. When we handle pointer subtraction,
3256 we may have to do something cute here. */
3258 if (maybe_lt (poly_uint64 (bitpos), get_varinfo (result.var)->fullsize)
3259 && maybe_ne (bitmaxsize, 0))
3261 /* It's also not true that the constraint will actually start at the
3262 right offset, it may start in some padding. We only care about
3263 setting the constraint to the first actual field it touches, so
3264 walk to find it. */
3265 struct constraint_expr cexpr = result;
3266 varinfo_t curr;
3267 results->pop ();
3268 cexpr.offset = 0;
3269 for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr))
3271 if (ranges_maybe_overlap_p (poly_int64 (curr->offset),
3272 curr->size, bitpos, bitmaxsize))
3274 cexpr.var = curr->id;
3275 results->safe_push (cexpr);
3276 if (address_p)
3277 break;
3280 /* If we are going to take the address of this field then
3281 to be able to compute reachability correctly add at least
3282 the last field of the variable. */
3283 if (address_p && results->length () == 0)
3285 curr = get_varinfo (cexpr.var);
3286 while (curr->next != 0)
3287 curr = vi_next (curr);
3288 cexpr.var = curr->id;
3289 results->safe_push (cexpr);
3291 else if (results->length () == 0)
3292 /* Assert that we found *some* field there. The user couldn't be
3293 accessing *only* padding. */
3294 /* Still the user could access one past the end of an array
3295 embedded in a struct resulting in accessing *only* padding. */
3296 /* Or accessing only padding via type-punning to a type
3297 that has a filed just in padding space. */
3299 cexpr.type = SCALAR;
3300 cexpr.var = anything_id;
3301 cexpr.offset = 0;
3302 results->safe_push (cexpr);
3305 else if (known_eq (bitmaxsize, 0))
3307 if (dump_file && (dump_flags & TDF_DETAILS))
3308 fprintf (dump_file, "Access to zero-sized part of variable, "
3309 "ignoring\n");
3311 else
3312 if (dump_file && (dump_flags & TDF_DETAILS))
3313 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3315 else if (result.type == DEREF)
3317 /* If we do not know exactly where the access goes say so. Note
3318 that only for non-structure accesses we know that we access
3319 at most one subfiled of any variable. */
3320 HOST_WIDE_INT const_bitpos;
3321 if (!bitpos.is_constant (&const_bitpos)
3322 || const_bitpos == -1
3323 || maybe_ne (bitsize, bitmaxsize)
3324 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t))
3325 || result.offset == UNKNOWN_OFFSET)
3326 result.offset = UNKNOWN_OFFSET;
3327 else
3328 result.offset += const_bitpos;
3330 else if (result.type == ADDRESSOF)
3332 /* We can end up here for component references on constants like
3333 VIEW_CONVERT_EXPR <>({ 0, 1, 2, 3 })[i]. */
3334 result.type = SCALAR;
3335 result.var = anything_id;
3336 result.offset = 0;
3338 else
3339 gcc_unreachable ();
3343 /* Dereference the constraint expression CONS, and return the result.
3344 DEREF (ADDRESSOF) = SCALAR
3345 DEREF (SCALAR) = DEREF
3346 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3347 This is needed so that we can handle dereferencing DEREF constraints. */
3349 static void
3350 do_deref (vec<ce_s> *constraints)
3352 struct constraint_expr *c;
3353 unsigned int i = 0;
3355 FOR_EACH_VEC_ELT (*constraints, i, c)
3357 if (c->type == SCALAR)
3358 c->type = DEREF;
3359 else if (c->type == ADDRESSOF)
3360 c->type = SCALAR;
3361 else if (c->type == DEREF)
3363 struct constraint_expr tmplhs;
3364 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp", true);
3365 process_constraint (new_constraint (tmplhs, *c));
3366 c->var = tmplhs.var;
3368 else
3369 gcc_unreachable ();
3373 /* Given a tree T, return the constraint expression for taking the
3374 address of it. */
3376 static void
3377 get_constraint_for_address_of (tree t, vec<ce_s> *results)
3379 struct constraint_expr *c;
3380 unsigned int i;
3382 get_constraint_for_1 (t, results, true, true);
3384 FOR_EACH_VEC_ELT (*results, i, c)
3386 if (c->type == DEREF)
3387 c->type = SCALAR;
3388 else
3389 c->type = ADDRESSOF;
3393 /* Given a tree T, return the constraint expression for it. */
3395 static void
3396 get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p,
3397 bool lhs_p)
3399 struct constraint_expr temp;
3401 /* x = integer is all glommed to a single variable, which doesn't
3402 point to anything by itself. That is, of course, unless it is an
3403 integer constant being treated as a pointer, in which case, we
3404 will return that this is really the addressof anything. This
3405 happens below, since it will fall into the default case. The only
3406 case we know something about an integer treated like a pointer is
3407 when it is the NULL pointer, and then we just say it points to
3408 NULL.
3410 Do not do that if -fno-delete-null-pointer-checks though, because
3411 in that case *NULL does not fail, so it _should_ alias *anything.
3412 It is not worth adding a new option or renaming the existing one,
3413 since this case is relatively obscure. */
3414 if ((TREE_CODE (t) == INTEGER_CST
3415 && integer_zerop (t))
3416 /* The only valid CONSTRUCTORs in gimple with pointer typed
3417 elements are zero-initializer. But in IPA mode we also
3418 process global initializers, so verify at least. */
3419 || (TREE_CODE (t) == CONSTRUCTOR
3420 && CONSTRUCTOR_NELTS (t) == 0))
3422 if (flag_delete_null_pointer_checks)
3423 temp.var = nothing_id;
3424 else
3425 temp.var = nonlocal_id;
3426 temp.type = ADDRESSOF;
3427 temp.offset = 0;
3428 results->safe_push (temp);
3429 return;
3432 /* String constants are read-only, ideally we'd have a CONST_DECL
3433 for those. */
3434 if (TREE_CODE (t) == STRING_CST)
3436 temp.var = string_id;
3437 temp.type = SCALAR;
3438 temp.offset = 0;
3439 results->safe_push (temp);
3440 return;
3443 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3445 case tcc_expression:
3447 switch (TREE_CODE (t))
3449 case ADDR_EXPR:
3450 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3451 return;
3452 default:;
3454 break;
3456 case tcc_reference:
3458 switch (TREE_CODE (t))
3460 case MEM_REF:
3462 struct constraint_expr cs;
3463 varinfo_t vi, curr;
3464 get_constraint_for_ptr_offset (TREE_OPERAND (t, 0),
3465 TREE_OPERAND (t, 1), results);
3466 do_deref (results);
3468 /* If we are not taking the address then make sure to process
3469 all subvariables we might access. */
3470 if (address_p)
3471 return;
3473 cs = results->last ();
3474 if (cs.type == DEREF
3475 && type_can_have_subvars (TREE_TYPE (t)))
3477 /* For dereferences this means we have to defer it
3478 to solving time. */
3479 results->last ().offset = UNKNOWN_OFFSET;
3480 return;
3482 if (cs.type != SCALAR)
3483 return;
3485 vi = get_varinfo (cs.var);
3486 curr = vi_next (vi);
3487 if (!vi->is_full_var
3488 && curr)
3490 unsigned HOST_WIDE_INT size;
3491 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t))))
3492 size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t)));
3493 else
3494 size = -1;
3495 for (; curr; curr = vi_next (curr))
3497 if (curr->offset - vi->offset < size)
3499 cs.var = curr->id;
3500 results->safe_push (cs);
3502 else
3503 break;
3506 return;
3508 case ARRAY_REF:
3509 case ARRAY_RANGE_REF:
3510 case COMPONENT_REF:
3511 case IMAGPART_EXPR:
3512 case REALPART_EXPR:
3513 case BIT_FIELD_REF:
3514 get_constraint_for_component_ref (t, results, address_p, lhs_p);
3515 return;
3516 case VIEW_CONVERT_EXPR:
3517 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p,
3518 lhs_p);
3519 return;
3520 /* We are missing handling for TARGET_MEM_REF here. */
3521 default:;
3523 break;
3525 case tcc_exceptional:
3527 switch (TREE_CODE (t))
3529 case SSA_NAME:
3531 get_constraint_for_ssa_var (t, results, address_p);
3532 return;
3534 case CONSTRUCTOR:
3536 unsigned int i;
3537 tree val;
3538 auto_vec<ce_s> tmp;
3539 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val)
3541 struct constraint_expr *rhsp;
3542 unsigned j;
3543 get_constraint_for_1 (val, &tmp, address_p, lhs_p);
3544 FOR_EACH_VEC_ELT (tmp, j, rhsp)
3545 results->safe_push (*rhsp);
3546 tmp.truncate (0);
3548 /* We do not know whether the constructor was complete,
3549 so technically we have to add &NOTHING or &ANYTHING
3550 like we do for an empty constructor as well. */
3551 return;
3553 default:;
3555 break;
3557 case tcc_declaration:
3559 get_constraint_for_ssa_var (t, results, address_p);
3560 return;
3562 case tcc_constant:
3564 /* We cannot refer to automatic variables through constants. */
3565 temp.type = ADDRESSOF;
3566 temp.var = nonlocal_id;
3567 temp.offset = 0;
3568 results->safe_push (temp);
3569 return;
3571 default:;
3574 /* The default fallback is a constraint from anything. */
3575 temp.type = ADDRESSOF;
3576 temp.var = anything_id;
3577 temp.offset = 0;
3578 results->safe_push (temp);
3581 /* Given a gimple tree T, return the constraint expression vector for it. */
3583 static void
3584 get_constraint_for (tree t, vec<ce_s> *results)
3586 gcc_assert (results->length () == 0);
3588 get_constraint_for_1 (t, results, false, true);
3591 /* Given a gimple tree T, return the constraint expression vector for it
3592 to be used as the rhs of a constraint. */
3594 static void
3595 get_constraint_for_rhs (tree t, vec<ce_s> *results)
3597 gcc_assert (results->length () == 0);
3599 get_constraint_for_1 (t, results, false, false);
3603 /* Efficiently generates constraints from all entries in *RHSC to all
3604 entries in *LHSC. */
3606 static void
3607 process_all_all_constraints (vec<ce_s> lhsc,
3608 vec<ce_s> rhsc)
3610 struct constraint_expr *lhsp, *rhsp;
3611 unsigned i, j;
3613 if (lhsc.length () <= 1 || rhsc.length () <= 1)
3615 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3616 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
3617 process_constraint (new_constraint (*lhsp, *rhsp));
3619 else
3621 struct constraint_expr tmp;
3622 tmp = new_scalar_tmp_constraint_exp ("allalltmp", true);
3623 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
3624 process_constraint (new_constraint (tmp, *rhsp));
3625 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3626 process_constraint (new_constraint (*lhsp, tmp));
3630 /* Handle aggregate copies by expanding into copies of the respective
3631 fields of the structures. */
3633 static void
3634 do_structure_copy (tree lhsop, tree rhsop)
3636 struct constraint_expr *lhsp, *rhsp;
3637 auto_vec<ce_s> lhsc;
3638 auto_vec<ce_s> rhsc;
3639 unsigned j;
3641 get_constraint_for (lhsop, &lhsc);
3642 get_constraint_for_rhs (rhsop, &rhsc);
3643 lhsp = &lhsc[0];
3644 rhsp = &rhsc[0];
3645 if (lhsp->type == DEREF
3646 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3647 || rhsp->type == DEREF)
3649 if (lhsp->type == DEREF)
3651 gcc_assert (lhsc.length () == 1);
3652 lhsp->offset = UNKNOWN_OFFSET;
3654 if (rhsp->type == DEREF)
3656 gcc_assert (rhsc.length () == 1);
3657 rhsp->offset = UNKNOWN_OFFSET;
3659 process_all_all_constraints (lhsc, rhsc);
3661 else if (lhsp->type == SCALAR
3662 && (rhsp->type == SCALAR
3663 || rhsp->type == ADDRESSOF))
3665 HOST_WIDE_INT lhssize, lhsoffset;
3666 HOST_WIDE_INT rhssize, rhsoffset;
3667 bool reverse;
3668 unsigned k = 0;
3669 if (!get_ref_base_and_extent_hwi (lhsop, &lhsoffset, &lhssize, &reverse)
3670 || !get_ref_base_and_extent_hwi (rhsop, &rhsoffset, &rhssize,
3671 &reverse))
3673 process_all_all_constraints (lhsc, rhsc);
3674 return;
3676 for (j = 0; lhsc.iterate (j, &lhsp);)
3678 varinfo_t lhsv, rhsv;
3679 rhsp = &rhsc[k];
3680 lhsv = get_varinfo (lhsp->var);
3681 rhsv = get_varinfo (rhsp->var);
3682 if (lhsv->may_have_pointers
3683 && (lhsv->is_full_var
3684 || rhsv->is_full_var
3685 || ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3686 rhsv->offset + lhsoffset, rhsv->size)))
3687 process_constraint (new_constraint (*lhsp, *rhsp));
3688 if (!rhsv->is_full_var
3689 && (lhsv->is_full_var
3690 || (lhsv->offset + rhsoffset + lhsv->size
3691 > rhsv->offset + lhsoffset + rhsv->size)))
3693 ++k;
3694 if (k >= rhsc.length ())
3695 break;
3697 else
3698 ++j;
3701 else
3702 gcc_unreachable ();
3705 /* Create constraints ID = { rhsc }. */
3707 static void
3708 make_constraints_to (unsigned id, vec<ce_s> rhsc)
3710 struct constraint_expr *c;
3711 struct constraint_expr includes;
3712 unsigned int j;
3714 includes.var = id;
3715 includes.offset = 0;
3716 includes.type = SCALAR;
3718 FOR_EACH_VEC_ELT (rhsc, j, c)
3719 process_constraint (new_constraint (includes, *c));
3722 /* Create a constraint ID = OP. */
3724 static void
3725 make_constraint_to (unsigned id, tree op)
3727 auto_vec<ce_s> rhsc;
3728 get_constraint_for_rhs (op, &rhsc);
3729 make_constraints_to (id, rhsc);
3732 /* Create a constraint ID = &FROM. */
3734 static void
3735 make_constraint_from (varinfo_t vi, int from)
3737 struct constraint_expr lhs, rhs;
3739 lhs.var = vi->id;
3740 lhs.offset = 0;
3741 lhs.type = SCALAR;
3743 rhs.var = from;
3744 rhs.offset = 0;
3745 rhs.type = ADDRESSOF;
3746 process_constraint (new_constraint (lhs, rhs));
3749 /* Create a constraint ID = FROM. */
3751 static void
3752 make_copy_constraint (varinfo_t vi, int from)
3754 struct constraint_expr lhs, rhs;
3756 lhs.var = vi->id;
3757 lhs.offset = 0;
3758 lhs.type = SCALAR;
3760 rhs.var = from;
3761 rhs.offset = 0;
3762 rhs.type = SCALAR;
3763 process_constraint (new_constraint (lhs, rhs));
3766 /* Make constraints necessary to make OP escape. */
3768 static void
3769 make_escape_constraint (tree op)
3771 make_constraint_to (escaped_id, op);
3774 /* Add constraints to that the solution of VI is transitively closed. */
3776 static void
3777 make_transitive_closure_constraints (varinfo_t vi)
3779 struct constraint_expr lhs, rhs;
3781 /* VAR = *(VAR + UNKNOWN); */
3782 lhs.type = SCALAR;
3783 lhs.var = vi->id;
3784 lhs.offset = 0;
3785 rhs.type = DEREF;
3786 rhs.var = vi->id;
3787 rhs.offset = UNKNOWN_OFFSET;
3788 process_constraint (new_constraint (lhs, rhs));
3791 /* Add constraints to that the solution of VI has all subvariables added. */
3793 static void
3794 make_any_offset_constraints (varinfo_t vi)
3796 struct constraint_expr lhs, rhs;
3798 /* VAR = VAR + UNKNOWN; */
3799 lhs.type = SCALAR;
3800 lhs.var = vi->id;
3801 lhs.offset = 0;
3802 rhs.type = SCALAR;
3803 rhs.var = vi->id;
3804 rhs.offset = UNKNOWN_OFFSET;
3805 process_constraint (new_constraint (lhs, rhs));
3808 /* Temporary storage for fake var decls. */
3809 struct obstack fake_var_decl_obstack;
3811 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3813 static tree
3814 build_fake_var_decl (tree type)
3816 tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
3817 memset (decl, 0, sizeof (struct tree_var_decl));
3818 TREE_SET_CODE (decl, VAR_DECL);
3819 TREE_TYPE (decl) = type;
3820 DECL_UID (decl) = allocate_decl_uid ();
3821 SET_DECL_PT_UID (decl, -1);
3822 layout_decl (decl, 0);
3823 return decl;
3826 /* Create a new artificial heap variable with NAME.
3827 Return the created variable. */
3829 static varinfo_t
3830 make_heapvar (const char *name, bool add_id)
3832 varinfo_t vi;
3833 tree heapvar;
3835 heapvar = build_fake_var_decl (ptr_type_node);
3836 DECL_EXTERNAL (heapvar) = 1;
3838 vi = new_var_info (heapvar, name, add_id);
3839 vi->is_artificial_var = true;
3840 vi->is_heap_var = true;
3841 vi->is_unknown_size_var = true;
3842 vi->offset = 0;
3843 vi->fullsize = ~0;
3844 vi->size = ~0;
3845 vi->is_full_var = true;
3846 insert_vi_for_tree (heapvar, vi);
3848 return vi;
3851 /* Create a new artificial heap variable with NAME and make a
3852 constraint from it to LHS. Set flags according to a tag used
3853 for tracking restrict pointers. */
3855 static varinfo_t
3856 make_constraint_from_restrict (varinfo_t lhs, const char *name, bool add_id)
3858 varinfo_t vi = make_heapvar (name, add_id);
3859 vi->is_restrict_var = 1;
3860 vi->is_global_var = 1;
3861 vi->may_have_pointers = 1;
3862 make_constraint_from (lhs, vi->id);
3863 return vi;
3866 /* Create a new artificial heap variable with NAME and make a
3867 constraint from it to LHS. Set flags according to a tag used
3868 for tracking restrict pointers and make the artificial heap
3869 point to global memory. */
3871 static varinfo_t
3872 make_constraint_from_global_restrict (varinfo_t lhs, const char *name,
3873 bool add_id)
3875 varinfo_t vi = make_constraint_from_restrict (lhs, name, add_id);
3876 make_copy_constraint (vi, nonlocal_id);
3877 return vi;
3880 /* In IPA mode there are varinfos for different aspects of reach
3881 function designator. One for the points-to set of the return
3882 value, one for the variables that are clobbered by the function,
3883 one for its uses and one for each parameter (including a single
3884 glob for remaining variadic arguments). */
3886 enum { fi_clobbers = 1, fi_uses = 2,
3887 fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 };
3889 /* Get a constraint for the requested part of a function designator FI
3890 when operating in IPA mode. */
3892 static struct constraint_expr
3893 get_function_part_constraint (varinfo_t fi, unsigned part)
3895 struct constraint_expr c;
3897 gcc_assert (in_ipa_mode);
3899 if (fi->id == anything_id)
3901 /* ??? We probably should have a ANYFN special variable. */
3902 c.var = anything_id;
3903 c.offset = 0;
3904 c.type = SCALAR;
3906 else if (TREE_CODE (fi->decl) == FUNCTION_DECL)
3908 varinfo_t ai = first_vi_for_offset (fi, part);
3909 if (ai)
3910 c.var = ai->id;
3911 else
3912 c.var = anything_id;
3913 c.offset = 0;
3914 c.type = SCALAR;
3916 else
3918 c.var = fi->id;
3919 c.offset = part;
3920 c.type = DEREF;
3923 return c;
3926 /* For non-IPA mode, generate constraints necessary for a call on the
3927 RHS. */
3929 static void
3930 handle_rhs_call (gcall *stmt, vec<ce_s> *results)
3932 struct constraint_expr rhsc;
3933 unsigned i;
3934 bool returns_uses = false;
3936 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3938 tree arg = gimple_call_arg (stmt, i);
3939 int flags = gimple_call_arg_flags (stmt, i);
3941 /* If the argument is not used we can ignore it. */
3942 if (flags & EAF_UNUSED)
3943 continue;
3945 /* As we compute ESCAPED context-insensitive we do not gain
3946 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3947 set. The argument would still get clobbered through the
3948 escape solution. */
3949 if ((flags & EAF_NOCLOBBER)
3950 && (flags & EAF_NOESCAPE))
3952 varinfo_t uses = get_call_use_vi (stmt);
3953 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
3954 tem->is_reg_var = true;
3955 make_constraint_to (tem->id, arg);
3956 make_any_offset_constraints (tem);
3957 if (!(flags & EAF_DIRECT))
3958 make_transitive_closure_constraints (tem);
3959 make_copy_constraint (uses, tem->id);
3960 returns_uses = true;
3962 else if (flags & EAF_NOESCAPE)
3964 struct constraint_expr lhs, rhs;
3965 varinfo_t uses = get_call_use_vi (stmt);
3966 varinfo_t clobbers = get_call_clobber_vi (stmt);
3967 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
3968 tem->is_reg_var = true;
3969 make_constraint_to (tem->id, arg);
3970 make_any_offset_constraints (tem);
3971 if (!(flags & EAF_DIRECT))
3972 make_transitive_closure_constraints (tem);
3973 make_copy_constraint (uses, tem->id);
3974 make_copy_constraint (clobbers, tem->id);
3975 /* Add *tem = nonlocal, do not add *tem = callused as
3976 EAF_NOESCAPE parameters do not escape to other parameters
3977 and all other uses appear in NONLOCAL as well. */
3978 lhs.type = DEREF;
3979 lhs.var = tem->id;
3980 lhs.offset = 0;
3981 rhs.type = SCALAR;
3982 rhs.var = nonlocal_id;
3983 rhs.offset = 0;
3984 process_constraint (new_constraint (lhs, rhs));
3985 returns_uses = true;
3987 else
3988 make_escape_constraint (arg);
3991 /* If we added to the calls uses solution make sure we account for
3992 pointers to it to be returned. */
3993 if (returns_uses)
3995 rhsc.var = get_call_use_vi (stmt)->id;
3996 rhsc.offset = UNKNOWN_OFFSET;
3997 rhsc.type = SCALAR;
3998 results->safe_push (rhsc);
4001 /* The static chain escapes as well. */
4002 if (gimple_call_chain (stmt))
4003 make_escape_constraint (gimple_call_chain (stmt));
4005 /* And if we applied NRV the address of the return slot escapes as well. */
4006 if (gimple_call_return_slot_opt_p (stmt)
4007 && gimple_call_lhs (stmt) != NULL_TREE
4008 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4010 auto_vec<ce_s> tmpc;
4011 struct constraint_expr lhsc, *c;
4012 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4013 lhsc.var = escaped_id;
4014 lhsc.offset = 0;
4015 lhsc.type = SCALAR;
4016 FOR_EACH_VEC_ELT (tmpc, i, c)
4017 process_constraint (new_constraint (lhsc, *c));
4020 /* Regular functions return nonlocal memory. */
4021 rhsc.var = nonlocal_id;
4022 rhsc.offset = 0;
4023 rhsc.type = SCALAR;
4024 results->safe_push (rhsc);
4027 /* For non-IPA mode, generate constraints necessary for a call
4028 that returns a pointer and assigns it to LHS. This simply makes
4029 the LHS point to global and escaped variables. */
4031 static void
4032 handle_lhs_call (gcall *stmt, tree lhs, int flags, vec<ce_s> rhsc,
4033 tree fndecl)
4035 auto_vec<ce_s> lhsc;
4037 get_constraint_for (lhs, &lhsc);
4038 /* If the store is to a global decl make sure to
4039 add proper escape constraints. */
4040 lhs = get_base_address (lhs);
4041 if (lhs
4042 && DECL_P (lhs)
4043 && is_global_var (lhs))
4045 struct constraint_expr tmpc;
4046 tmpc.var = escaped_id;
4047 tmpc.offset = 0;
4048 tmpc.type = SCALAR;
4049 lhsc.safe_push (tmpc);
4052 /* If the call returns an argument unmodified override the rhs
4053 constraints. */
4054 if (flags & ERF_RETURNS_ARG
4055 && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
4057 tree arg;
4058 rhsc.create (0);
4059 arg = gimple_call_arg (stmt, flags & ERF_RETURN_ARG_MASK);
4060 get_constraint_for (arg, &rhsc);
4061 process_all_all_constraints (lhsc, rhsc);
4062 rhsc.release ();
4064 else if (flags & ERF_NOALIAS)
4066 varinfo_t vi;
4067 struct constraint_expr tmpc;
4068 rhsc.create (0);
4069 vi = make_heapvar ("HEAP", true);
4070 /* We are marking allocated storage local, we deal with it becoming
4071 global by escaping and setting of vars_contains_escaped_heap. */
4072 DECL_EXTERNAL (vi->decl) = 0;
4073 vi->is_global_var = 0;
4074 /* If this is not a real malloc call assume the memory was
4075 initialized and thus may point to global memory. All
4076 builtin functions with the malloc attribute behave in a sane way. */
4077 if (!fndecl
4078 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
4079 make_constraint_from (vi, nonlocal_id);
4080 tmpc.var = vi->id;
4081 tmpc.offset = 0;
4082 tmpc.type = ADDRESSOF;
4083 rhsc.safe_push (tmpc);
4084 process_all_all_constraints (lhsc, rhsc);
4085 rhsc.release ();
4087 else
4088 process_all_all_constraints (lhsc, rhsc);
4091 /* For non-IPA mode, generate constraints necessary for a call of a
4092 const function that returns a pointer in the statement STMT. */
4094 static void
4095 handle_const_call (gcall *stmt, vec<ce_s> *results)
4097 struct constraint_expr rhsc;
4098 unsigned int k;
4099 bool need_uses = false;
4101 /* Treat nested const functions the same as pure functions as far
4102 as the static chain is concerned. */
4103 if (gimple_call_chain (stmt))
4105 varinfo_t uses = get_call_use_vi (stmt);
4106 make_constraint_to (uses->id, gimple_call_chain (stmt));
4107 need_uses = true;
4110 /* And if we applied NRV the address of the return slot escapes as well. */
4111 if (gimple_call_return_slot_opt_p (stmt)
4112 && gimple_call_lhs (stmt) != NULL_TREE
4113 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4115 varinfo_t uses = get_call_use_vi (stmt);
4116 auto_vec<ce_s> tmpc;
4117 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4118 make_constraints_to (uses->id, tmpc);
4119 need_uses = true;
4122 if (need_uses)
4124 varinfo_t uses = get_call_use_vi (stmt);
4125 make_any_offset_constraints (uses);
4126 make_transitive_closure_constraints (uses);
4127 rhsc.var = uses->id;
4128 rhsc.offset = 0;
4129 rhsc.type = SCALAR;
4130 results->safe_push (rhsc);
4133 /* May return offsetted arguments. */
4134 varinfo_t tem = NULL;
4135 if (gimple_call_num_args (stmt) != 0)
4137 tem = new_var_info (NULL_TREE, "callarg", true);
4138 tem->is_reg_var = true;
4140 for (k = 0; k < gimple_call_num_args (stmt); ++k)
4142 tree arg = gimple_call_arg (stmt, k);
4143 auto_vec<ce_s> argc;
4144 get_constraint_for_rhs (arg, &argc);
4145 make_constraints_to (tem->id, argc);
4147 if (tem)
4149 ce_s ce;
4150 ce.type = SCALAR;
4151 ce.var = tem->id;
4152 ce.offset = UNKNOWN_OFFSET;
4153 results->safe_push (ce);
4156 /* May return addresses of globals. */
4157 rhsc.var = nonlocal_id;
4158 rhsc.offset = 0;
4159 rhsc.type = ADDRESSOF;
4160 results->safe_push (rhsc);
4163 /* For non-IPA mode, generate constraints necessary for a call to a
4164 pure function in statement STMT. */
4166 static void
4167 handle_pure_call (gcall *stmt, vec<ce_s> *results)
4169 struct constraint_expr rhsc;
4170 unsigned i;
4171 varinfo_t uses = NULL;
4173 /* Memory reached from pointer arguments is call-used. */
4174 for (i = 0; i < gimple_call_num_args (stmt); ++i)
4176 tree arg = gimple_call_arg (stmt, i);
4177 if (!uses)
4179 uses = get_call_use_vi (stmt);
4180 make_any_offset_constraints (uses);
4181 make_transitive_closure_constraints (uses);
4183 make_constraint_to (uses->id, arg);
4186 /* The static chain is used as well. */
4187 if (gimple_call_chain (stmt))
4189 if (!uses)
4191 uses = get_call_use_vi (stmt);
4192 make_any_offset_constraints (uses);
4193 make_transitive_closure_constraints (uses);
4195 make_constraint_to (uses->id, gimple_call_chain (stmt));
4198 /* And if we applied NRV the address of the return slot. */
4199 if (gimple_call_return_slot_opt_p (stmt)
4200 && gimple_call_lhs (stmt) != NULL_TREE
4201 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4203 if (!uses)
4205 uses = get_call_use_vi (stmt);
4206 make_any_offset_constraints (uses);
4207 make_transitive_closure_constraints (uses);
4209 auto_vec<ce_s> tmpc;
4210 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4211 make_constraints_to (uses->id, tmpc);
4214 /* Pure functions may return call-used and nonlocal memory. */
4215 if (uses)
4217 rhsc.var = uses->id;
4218 rhsc.offset = 0;
4219 rhsc.type = SCALAR;
4220 results->safe_push (rhsc);
4222 rhsc.var = nonlocal_id;
4223 rhsc.offset = 0;
4224 rhsc.type = SCALAR;
4225 results->safe_push (rhsc);
4229 /* Return the varinfo for the callee of CALL. */
4231 static varinfo_t
4232 get_fi_for_callee (gcall *call)
4234 tree decl, fn = gimple_call_fn (call);
4236 if (fn && TREE_CODE (fn) == OBJ_TYPE_REF)
4237 fn = OBJ_TYPE_REF_EXPR (fn);
4239 /* If we can directly resolve the function being called, do so.
4240 Otherwise, it must be some sort of indirect expression that
4241 we should still be able to handle. */
4242 decl = gimple_call_addr_fndecl (fn);
4243 if (decl)
4244 return get_vi_for_tree (decl);
4246 /* If the function is anything other than a SSA name pointer we have no
4247 clue and should be getting ANYFN (well, ANYTHING for now). */
4248 if (!fn || TREE_CODE (fn) != SSA_NAME)
4249 return get_varinfo (anything_id);
4251 if (SSA_NAME_IS_DEFAULT_DEF (fn)
4252 && (TREE_CODE (SSA_NAME_VAR (fn)) == PARM_DECL
4253 || TREE_CODE (SSA_NAME_VAR (fn)) == RESULT_DECL))
4254 fn = SSA_NAME_VAR (fn);
4256 return get_vi_for_tree (fn);
4259 /* Create constraints for assigning call argument ARG to the incoming parameter
4260 INDEX of function FI. */
4262 static void
4263 find_func_aliases_for_call_arg (varinfo_t fi, unsigned index, tree arg)
4265 struct constraint_expr lhs;
4266 lhs = get_function_part_constraint (fi, fi_parm_base + index);
4268 auto_vec<ce_s, 2> rhsc;
4269 get_constraint_for_rhs (arg, &rhsc);
4271 unsigned j;
4272 struct constraint_expr *rhsp;
4273 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4274 process_constraint (new_constraint (lhs, *rhsp));
4277 /* Return true if FNDECL may be part of another lto partition. */
4279 static bool
4280 fndecl_maybe_in_other_partition (tree fndecl)
4282 cgraph_node *fn_node = cgraph_node::get (fndecl);
4283 if (fn_node == NULL)
4284 return true;
4286 return fn_node->in_other_partition;
4289 /* Create constraints for the builtin call T. Return true if the call
4290 was handled, otherwise false. */
4292 static bool
4293 find_func_aliases_for_builtin_call (struct function *fn, gcall *t)
4295 tree fndecl = gimple_call_fndecl (t);
4296 auto_vec<ce_s, 2> lhsc;
4297 auto_vec<ce_s, 4> rhsc;
4298 varinfo_t fi;
4300 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
4301 /* ??? All builtins that are handled here need to be handled
4302 in the alias-oracle query functions explicitly! */
4303 switch (DECL_FUNCTION_CODE (fndecl))
4305 /* All the following functions return a pointer to the same object
4306 as their first argument points to. The functions do not add
4307 to the ESCAPED solution. The functions make the first argument
4308 pointed to memory point to what the second argument pointed to
4309 memory points to. */
4310 case BUILT_IN_STRCPY:
4311 case BUILT_IN_STRNCPY:
4312 case BUILT_IN_BCOPY:
4313 case BUILT_IN_MEMCPY:
4314 case BUILT_IN_MEMMOVE:
4315 case BUILT_IN_MEMPCPY:
4316 case BUILT_IN_STPCPY:
4317 case BUILT_IN_STPNCPY:
4318 case BUILT_IN_STRCAT:
4319 case BUILT_IN_STRNCAT:
4320 case BUILT_IN_STRCPY_CHK:
4321 case BUILT_IN_STRNCPY_CHK:
4322 case BUILT_IN_MEMCPY_CHK:
4323 case BUILT_IN_MEMMOVE_CHK:
4324 case BUILT_IN_MEMPCPY_CHK:
4325 case BUILT_IN_STPCPY_CHK:
4326 case BUILT_IN_STPNCPY_CHK:
4327 case BUILT_IN_STRCAT_CHK:
4328 case BUILT_IN_STRNCAT_CHK:
4329 case BUILT_IN_TM_MEMCPY:
4330 case BUILT_IN_TM_MEMMOVE:
4332 tree res = gimple_call_lhs (t);
4333 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4334 == BUILT_IN_BCOPY ? 1 : 0));
4335 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4336 == BUILT_IN_BCOPY ? 0 : 1));
4337 if (res != NULL_TREE)
4339 get_constraint_for (res, &lhsc);
4340 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
4341 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
4342 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY
4343 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHK
4344 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY_CHK
4345 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY_CHK)
4346 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
4347 else
4348 get_constraint_for (dest, &rhsc);
4349 process_all_all_constraints (lhsc, rhsc);
4350 lhsc.truncate (0);
4351 rhsc.truncate (0);
4353 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4354 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4355 do_deref (&lhsc);
4356 do_deref (&rhsc);
4357 process_all_all_constraints (lhsc, rhsc);
4358 return true;
4360 case BUILT_IN_MEMSET:
4361 case BUILT_IN_MEMSET_CHK:
4362 case BUILT_IN_TM_MEMSET:
4364 tree res = gimple_call_lhs (t);
4365 tree dest = gimple_call_arg (t, 0);
4366 unsigned i;
4367 ce_s *lhsp;
4368 struct constraint_expr ac;
4369 if (res != NULL_TREE)
4371 get_constraint_for (res, &lhsc);
4372 get_constraint_for (dest, &rhsc);
4373 process_all_all_constraints (lhsc, rhsc);
4374 lhsc.truncate (0);
4376 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4377 do_deref (&lhsc);
4378 if (flag_delete_null_pointer_checks
4379 && integer_zerop (gimple_call_arg (t, 1)))
4381 ac.type = ADDRESSOF;
4382 ac.var = nothing_id;
4384 else
4386 ac.type = SCALAR;
4387 ac.var = integer_id;
4389 ac.offset = 0;
4390 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4391 process_constraint (new_constraint (*lhsp, ac));
4392 return true;
4394 case BUILT_IN_POSIX_MEMALIGN:
4396 tree ptrptr = gimple_call_arg (t, 0);
4397 get_constraint_for (ptrptr, &lhsc);
4398 do_deref (&lhsc);
4399 varinfo_t vi = make_heapvar ("HEAP", true);
4400 /* We are marking allocated storage local, we deal with it becoming
4401 global by escaping and setting of vars_contains_escaped_heap. */
4402 DECL_EXTERNAL (vi->decl) = 0;
4403 vi->is_global_var = 0;
4404 struct constraint_expr tmpc;
4405 tmpc.var = vi->id;
4406 tmpc.offset = 0;
4407 tmpc.type = ADDRESSOF;
4408 rhsc.safe_push (tmpc);
4409 process_all_all_constraints (lhsc, rhsc);
4410 return true;
4412 case BUILT_IN_ASSUME_ALIGNED:
4414 tree res = gimple_call_lhs (t);
4415 tree dest = gimple_call_arg (t, 0);
4416 if (res != NULL_TREE)
4418 get_constraint_for (res, &lhsc);
4419 get_constraint_for (dest, &rhsc);
4420 process_all_all_constraints (lhsc, rhsc);
4422 return true;
4424 /* All the following functions do not return pointers, do not
4425 modify the points-to sets of memory reachable from their
4426 arguments and do not add to the ESCAPED solution. */
4427 case BUILT_IN_SINCOS:
4428 case BUILT_IN_SINCOSF:
4429 case BUILT_IN_SINCOSL:
4430 case BUILT_IN_FREXP:
4431 case BUILT_IN_FREXPF:
4432 case BUILT_IN_FREXPL:
4433 case BUILT_IN_GAMMA_R:
4434 case BUILT_IN_GAMMAF_R:
4435 case BUILT_IN_GAMMAL_R:
4436 case BUILT_IN_LGAMMA_R:
4437 case BUILT_IN_LGAMMAF_R:
4438 case BUILT_IN_LGAMMAL_R:
4439 case BUILT_IN_MODF:
4440 case BUILT_IN_MODFF:
4441 case BUILT_IN_MODFL:
4442 case BUILT_IN_REMQUO:
4443 case BUILT_IN_REMQUOF:
4444 case BUILT_IN_REMQUOL:
4445 case BUILT_IN_FREE:
4446 return true;
4447 case BUILT_IN_STRDUP:
4448 case BUILT_IN_STRNDUP:
4449 case BUILT_IN_REALLOC:
4450 if (gimple_call_lhs (t))
4452 handle_lhs_call (t, gimple_call_lhs (t),
4453 gimple_call_return_flags (t) | ERF_NOALIAS,
4454 vNULL, fndecl);
4455 get_constraint_for_ptr_offset (gimple_call_lhs (t),
4456 NULL_TREE, &lhsc);
4457 get_constraint_for_ptr_offset (gimple_call_arg (t, 0),
4458 NULL_TREE, &rhsc);
4459 do_deref (&lhsc);
4460 do_deref (&rhsc);
4461 process_all_all_constraints (lhsc, rhsc);
4462 lhsc.truncate (0);
4463 rhsc.truncate (0);
4464 /* For realloc the resulting pointer can be equal to the
4465 argument as well. But only doing this wouldn't be
4466 correct because with ptr == 0 realloc behaves like malloc. */
4467 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_REALLOC)
4469 get_constraint_for (gimple_call_lhs (t), &lhsc);
4470 get_constraint_for (gimple_call_arg (t, 0), &rhsc);
4471 process_all_all_constraints (lhsc, rhsc);
4473 return true;
4475 break;
4476 /* String / character search functions return a pointer into the
4477 source string or NULL. */
4478 case BUILT_IN_INDEX:
4479 case BUILT_IN_STRCHR:
4480 case BUILT_IN_STRRCHR:
4481 case BUILT_IN_MEMCHR:
4482 case BUILT_IN_STRSTR:
4483 case BUILT_IN_STRPBRK:
4484 if (gimple_call_lhs (t))
4486 tree src = gimple_call_arg (t, 0);
4487 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4488 constraint_expr nul;
4489 nul.var = nothing_id;
4490 nul.offset = 0;
4491 nul.type = ADDRESSOF;
4492 rhsc.safe_push (nul);
4493 get_constraint_for (gimple_call_lhs (t), &lhsc);
4494 process_all_all_constraints (lhsc, rhsc);
4496 return true;
4497 /* Pure functions that return something not based on any object and
4498 that use the memory pointed to by their arguments (but not
4499 transitively). */
4500 case BUILT_IN_STRCMP:
4501 case BUILT_IN_STRNCMP:
4502 case BUILT_IN_STRCASECMP:
4503 case BUILT_IN_STRNCASECMP:
4504 case BUILT_IN_MEMCMP:
4505 case BUILT_IN_BCMP:
4506 case BUILT_IN_STRSPN:
4507 case BUILT_IN_STRCSPN:
4509 varinfo_t uses = get_call_use_vi (t);
4510 make_any_offset_constraints (uses);
4511 make_constraint_to (uses->id, gimple_call_arg (t, 0));
4512 make_constraint_to (uses->id, gimple_call_arg (t, 1));
4513 /* No constraints are necessary for the return value. */
4514 return true;
4516 case BUILT_IN_STRLEN:
4518 varinfo_t uses = get_call_use_vi (t);
4519 make_any_offset_constraints (uses);
4520 make_constraint_to (uses->id, gimple_call_arg (t, 0));
4521 /* No constraints are necessary for the return value. */
4522 return true;
4524 case BUILT_IN_OBJECT_SIZE:
4525 case BUILT_IN_CONSTANT_P:
4527 /* No constraints are necessary for the return value or the
4528 arguments. */
4529 return true;
4531 /* Trampolines are special - they set up passing the static
4532 frame. */
4533 case BUILT_IN_INIT_TRAMPOLINE:
4535 tree tramp = gimple_call_arg (t, 0);
4536 tree nfunc = gimple_call_arg (t, 1);
4537 tree frame = gimple_call_arg (t, 2);
4538 unsigned i;
4539 struct constraint_expr lhs, *rhsp;
4540 if (in_ipa_mode)
4542 varinfo_t nfi = NULL;
4543 gcc_assert (TREE_CODE (nfunc) == ADDR_EXPR);
4544 nfi = lookup_vi_for_tree (TREE_OPERAND (nfunc, 0));
4545 if (nfi)
4547 lhs = get_function_part_constraint (nfi, fi_static_chain);
4548 get_constraint_for (frame, &rhsc);
4549 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4550 process_constraint (new_constraint (lhs, *rhsp));
4551 rhsc.truncate (0);
4553 /* Make the frame point to the function for
4554 the trampoline adjustment call. */
4555 get_constraint_for (tramp, &lhsc);
4556 do_deref (&lhsc);
4557 get_constraint_for (nfunc, &rhsc);
4558 process_all_all_constraints (lhsc, rhsc);
4560 return true;
4563 /* Else fallthru to generic handling which will let
4564 the frame escape. */
4565 break;
4567 case BUILT_IN_ADJUST_TRAMPOLINE:
4569 tree tramp = gimple_call_arg (t, 0);
4570 tree res = gimple_call_lhs (t);
4571 if (in_ipa_mode && res)
4573 get_constraint_for (res, &lhsc);
4574 get_constraint_for (tramp, &rhsc);
4575 do_deref (&rhsc);
4576 process_all_all_constraints (lhsc, rhsc);
4578 return true;
4580 CASE_BUILT_IN_TM_STORE (1):
4581 CASE_BUILT_IN_TM_STORE (2):
4582 CASE_BUILT_IN_TM_STORE (4):
4583 CASE_BUILT_IN_TM_STORE (8):
4584 CASE_BUILT_IN_TM_STORE (FLOAT):
4585 CASE_BUILT_IN_TM_STORE (DOUBLE):
4586 CASE_BUILT_IN_TM_STORE (LDOUBLE):
4587 CASE_BUILT_IN_TM_STORE (M64):
4588 CASE_BUILT_IN_TM_STORE (M128):
4589 CASE_BUILT_IN_TM_STORE (M256):
4591 tree addr = gimple_call_arg (t, 0);
4592 tree src = gimple_call_arg (t, 1);
4594 get_constraint_for (addr, &lhsc);
4595 do_deref (&lhsc);
4596 get_constraint_for (src, &rhsc);
4597 process_all_all_constraints (lhsc, rhsc);
4598 return true;
4600 CASE_BUILT_IN_TM_LOAD (1):
4601 CASE_BUILT_IN_TM_LOAD (2):
4602 CASE_BUILT_IN_TM_LOAD (4):
4603 CASE_BUILT_IN_TM_LOAD (8):
4604 CASE_BUILT_IN_TM_LOAD (FLOAT):
4605 CASE_BUILT_IN_TM_LOAD (DOUBLE):
4606 CASE_BUILT_IN_TM_LOAD (LDOUBLE):
4607 CASE_BUILT_IN_TM_LOAD (M64):
4608 CASE_BUILT_IN_TM_LOAD (M128):
4609 CASE_BUILT_IN_TM_LOAD (M256):
4611 tree dest = gimple_call_lhs (t);
4612 tree addr = gimple_call_arg (t, 0);
4614 get_constraint_for (dest, &lhsc);
4615 get_constraint_for (addr, &rhsc);
4616 do_deref (&rhsc);
4617 process_all_all_constraints (lhsc, rhsc);
4618 return true;
4620 /* Variadic argument handling needs to be handled in IPA
4621 mode as well. */
4622 case BUILT_IN_VA_START:
4624 tree valist = gimple_call_arg (t, 0);
4625 struct constraint_expr rhs, *lhsp;
4626 unsigned i;
4627 get_constraint_for_ptr_offset (valist, NULL_TREE, &lhsc);
4628 do_deref (&lhsc);
4629 /* The va_list gets access to pointers in variadic
4630 arguments. Which we know in the case of IPA analysis
4631 and otherwise are just all nonlocal variables. */
4632 if (in_ipa_mode)
4634 fi = lookup_vi_for_tree (fn->decl);
4635 rhs = get_function_part_constraint (fi, ~0);
4636 rhs.type = ADDRESSOF;
4638 else
4640 rhs.var = nonlocal_id;
4641 rhs.type = ADDRESSOF;
4642 rhs.offset = 0;
4644 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4645 process_constraint (new_constraint (*lhsp, rhs));
4646 /* va_list is clobbered. */
4647 make_constraint_to (get_call_clobber_vi (t)->id, valist);
4648 return true;
4650 /* va_end doesn't have any effect that matters. */
4651 case BUILT_IN_VA_END:
4652 return true;
4653 /* Alternate return. Simply give up for now. */
4654 case BUILT_IN_RETURN:
4656 fi = NULL;
4657 if (!in_ipa_mode
4658 || !(fi = get_vi_for_tree (fn->decl)))
4659 make_constraint_from (get_varinfo (escaped_id), anything_id);
4660 else if (in_ipa_mode
4661 && fi != NULL)
4663 struct constraint_expr lhs, rhs;
4664 lhs = get_function_part_constraint (fi, fi_result);
4665 rhs.var = anything_id;
4666 rhs.offset = 0;
4667 rhs.type = SCALAR;
4668 process_constraint (new_constraint (lhs, rhs));
4670 return true;
4672 case BUILT_IN_GOMP_PARALLEL:
4673 case BUILT_IN_GOACC_PARALLEL:
4675 if (in_ipa_mode)
4677 unsigned int fnpos, argpos;
4678 switch (DECL_FUNCTION_CODE (fndecl))
4680 case BUILT_IN_GOMP_PARALLEL:
4681 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
4682 fnpos = 0;
4683 argpos = 1;
4684 break;
4685 case BUILT_IN_GOACC_PARALLEL:
4686 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
4687 sizes, kinds, ...). */
4688 fnpos = 1;
4689 argpos = 3;
4690 break;
4691 default:
4692 gcc_unreachable ();
4695 tree fnarg = gimple_call_arg (t, fnpos);
4696 gcc_assert (TREE_CODE (fnarg) == ADDR_EXPR);
4697 tree fndecl = TREE_OPERAND (fnarg, 0);
4698 if (fndecl_maybe_in_other_partition (fndecl))
4699 /* Fallthru to general call handling. */
4700 break;
4702 tree arg = gimple_call_arg (t, argpos);
4704 varinfo_t fi = get_vi_for_tree (fndecl);
4705 find_func_aliases_for_call_arg (fi, 0, arg);
4706 return true;
4708 /* Else fallthru to generic call handling. */
4709 break;
4711 /* printf-style functions may have hooks to set pointers to
4712 point to somewhere into the generated string. Leave them
4713 for a later exercise... */
4714 default:
4715 /* Fallthru to general call handling. */;
4718 return false;
4721 /* Create constraints for the call T. */
4723 static void
4724 find_func_aliases_for_call (struct function *fn, gcall *t)
4726 tree fndecl = gimple_call_fndecl (t);
4727 varinfo_t fi;
4729 if (fndecl != NULL_TREE
4730 && DECL_BUILT_IN (fndecl)
4731 && find_func_aliases_for_builtin_call (fn, t))
4732 return;
4734 fi = get_fi_for_callee (t);
4735 if (!in_ipa_mode
4736 || (fndecl && !fi->is_fn_info))
4738 auto_vec<ce_s, 16> rhsc;
4739 int flags = gimple_call_flags (t);
4741 /* Const functions can return their arguments and addresses
4742 of global memory but not of escaped memory. */
4743 if (flags & (ECF_CONST|ECF_NOVOPS))
4745 if (gimple_call_lhs (t))
4746 handle_const_call (t, &rhsc);
4748 /* Pure functions can return addresses in and of memory
4749 reachable from their arguments, but they are not an escape
4750 point for reachable memory of their arguments. */
4751 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
4752 handle_pure_call (t, &rhsc);
4753 else
4754 handle_rhs_call (t, &rhsc);
4755 if (gimple_call_lhs (t))
4756 handle_lhs_call (t, gimple_call_lhs (t),
4757 gimple_call_return_flags (t), rhsc, fndecl);
4759 else
4761 auto_vec<ce_s, 2> rhsc;
4762 tree lhsop;
4763 unsigned j;
4765 /* Assign all the passed arguments to the appropriate incoming
4766 parameters of the function. */
4767 for (j = 0; j < gimple_call_num_args (t); j++)
4769 tree arg = gimple_call_arg (t, j);
4770 find_func_aliases_for_call_arg (fi, j, arg);
4773 /* If we are returning a value, assign it to the result. */
4774 lhsop = gimple_call_lhs (t);
4775 if (lhsop)
4777 auto_vec<ce_s, 2> lhsc;
4778 struct constraint_expr rhs;
4779 struct constraint_expr *lhsp;
4780 bool aggr_p = aggregate_value_p (lhsop, gimple_call_fntype (t));
4782 get_constraint_for (lhsop, &lhsc);
4783 rhs = get_function_part_constraint (fi, fi_result);
4784 if (aggr_p)
4786 auto_vec<ce_s, 2> tem;
4787 tem.quick_push (rhs);
4788 do_deref (&tem);
4789 gcc_checking_assert (tem.length () == 1);
4790 rhs = tem[0];
4792 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
4793 process_constraint (new_constraint (*lhsp, rhs));
4795 /* If we pass the result decl by reference, honor that. */
4796 if (aggr_p)
4798 struct constraint_expr lhs;
4799 struct constraint_expr *rhsp;
4801 get_constraint_for_address_of (lhsop, &rhsc);
4802 lhs = get_function_part_constraint (fi, fi_result);
4803 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4804 process_constraint (new_constraint (lhs, *rhsp));
4805 rhsc.truncate (0);
4809 /* If we use a static chain, pass it along. */
4810 if (gimple_call_chain (t))
4812 struct constraint_expr lhs;
4813 struct constraint_expr *rhsp;
4815 get_constraint_for (gimple_call_chain (t), &rhsc);
4816 lhs = get_function_part_constraint (fi, fi_static_chain);
4817 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4818 process_constraint (new_constraint (lhs, *rhsp));
4823 /* Walk statement T setting up aliasing constraints according to the
4824 references found in T. This function is the main part of the
4825 constraint builder. AI points to auxiliary alias information used
4826 when building alias sets and computing alias grouping heuristics. */
4828 static void
4829 find_func_aliases (struct function *fn, gimple *origt)
4831 gimple *t = origt;
4832 auto_vec<ce_s, 16> lhsc;
4833 auto_vec<ce_s, 16> rhsc;
4834 struct constraint_expr *c;
4835 varinfo_t fi;
4837 /* Now build constraints expressions. */
4838 if (gimple_code (t) == GIMPLE_PHI)
4840 size_t i;
4841 unsigned int j;
4843 /* For a phi node, assign all the arguments to
4844 the result. */
4845 get_constraint_for (gimple_phi_result (t), &lhsc);
4846 for (i = 0; i < gimple_phi_num_args (t); i++)
4848 tree strippedrhs = PHI_ARG_DEF (t, i);
4850 STRIP_NOPS (strippedrhs);
4851 get_constraint_for_rhs (gimple_phi_arg_def (t, i), &rhsc);
4853 FOR_EACH_VEC_ELT (lhsc, j, c)
4855 struct constraint_expr *c2;
4856 while (rhsc.length () > 0)
4858 c2 = &rhsc.last ();
4859 process_constraint (new_constraint (*c, *c2));
4860 rhsc.pop ();
4865 /* In IPA mode, we need to generate constraints to pass call
4866 arguments through their calls. There are two cases,
4867 either a GIMPLE_CALL returning a value, or just a plain
4868 GIMPLE_CALL when we are not.
4870 In non-ipa mode, we need to generate constraints for each
4871 pointer passed by address. */
4872 else if (is_gimple_call (t))
4873 find_func_aliases_for_call (fn, as_a <gcall *> (t));
4875 /* Otherwise, just a regular assignment statement. Only care about
4876 operations with pointer result, others are dealt with as escape
4877 points if they have pointer operands. */
4878 else if (is_gimple_assign (t))
4880 /* Otherwise, just a regular assignment statement. */
4881 tree lhsop = gimple_assign_lhs (t);
4882 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
4884 if (rhsop && TREE_CLOBBER_P (rhsop))
4885 /* Ignore clobbers, they don't actually store anything into
4886 the LHS. */
4888 else if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
4889 do_structure_copy (lhsop, rhsop);
4890 else
4892 enum tree_code code = gimple_assign_rhs_code (t);
4894 get_constraint_for (lhsop, &lhsc);
4896 if (code == POINTER_PLUS_EXPR)
4897 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4898 gimple_assign_rhs2 (t), &rhsc);
4899 else if (code == BIT_AND_EXPR
4900 && TREE_CODE (gimple_assign_rhs2 (t)) == INTEGER_CST)
4902 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4903 the pointer. Handle it by offsetting it by UNKNOWN. */
4904 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4905 NULL_TREE, &rhsc);
4907 else if ((CONVERT_EXPR_CODE_P (code)
4908 && !(POINTER_TYPE_P (gimple_expr_type (t))
4909 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
4910 || gimple_assign_single_p (t))
4911 get_constraint_for_rhs (rhsop, &rhsc);
4912 else if (code == COND_EXPR)
4914 /* The result is a merge of both COND_EXPR arms. */
4915 auto_vec<ce_s, 2> tmp;
4916 struct constraint_expr *rhsp;
4917 unsigned i;
4918 get_constraint_for_rhs (gimple_assign_rhs2 (t), &rhsc);
4919 get_constraint_for_rhs (gimple_assign_rhs3 (t), &tmp);
4920 FOR_EACH_VEC_ELT (tmp, i, rhsp)
4921 rhsc.safe_push (*rhsp);
4923 else if (truth_value_p (code))
4924 /* Truth value results are not pointer (parts). Or at least
4925 very unreasonable obfuscation of a part. */
4927 else
4929 /* All other operations are merges. */
4930 auto_vec<ce_s, 4> tmp;
4931 struct constraint_expr *rhsp;
4932 unsigned i, j;
4933 get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
4934 for (i = 2; i < gimple_num_ops (t); ++i)
4936 get_constraint_for_rhs (gimple_op (t, i), &tmp);
4937 FOR_EACH_VEC_ELT (tmp, j, rhsp)
4938 rhsc.safe_push (*rhsp);
4939 tmp.truncate (0);
4942 process_all_all_constraints (lhsc, rhsc);
4944 /* If there is a store to a global variable the rhs escapes. */
4945 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
4946 && DECL_P (lhsop))
4948 varinfo_t vi = get_vi_for_tree (lhsop);
4949 if ((! in_ipa_mode && vi->is_global_var)
4950 || vi->is_ipa_escape_point)
4951 make_escape_constraint (rhsop);
4954 /* Handle escapes through return. */
4955 else if (gimple_code (t) == GIMPLE_RETURN
4956 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE)
4958 greturn *return_stmt = as_a <greturn *> (t);
4959 fi = NULL;
4960 if (!in_ipa_mode
4961 || !(fi = get_vi_for_tree (fn->decl)))
4962 make_escape_constraint (gimple_return_retval (return_stmt));
4963 else if (in_ipa_mode)
4965 struct constraint_expr lhs ;
4966 struct constraint_expr *rhsp;
4967 unsigned i;
4969 lhs = get_function_part_constraint (fi, fi_result);
4970 get_constraint_for_rhs (gimple_return_retval (return_stmt), &rhsc);
4971 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4972 process_constraint (new_constraint (lhs, *rhsp));
4975 /* Handle asms conservatively by adding escape constraints to everything. */
4976 else if (gasm *asm_stmt = dyn_cast <gasm *> (t))
4978 unsigned i, noutputs;
4979 const char **oconstraints;
4980 const char *constraint;
4981 bool allows_mem, allows_reg, is_inout;
4983 noutputs = gimple_asm_noutputs (asm_stmt);
4984 oconstraints = XALLOCAVEC (const char *, noutputs);
4986 for (i = 0; i < noutputs; ++i)
4988 tree link = gimple_asm_output_op (asm_stmt, i);
4989 tree op = TREE_VALUE (link);
4991 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4992 oconstraints[i] = constraint;
4993 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4994 &allows_reg, &is_inout);
4996 /* A memory constraint makes the address of the operand escape. */
4997 if (!allows_reg && allows_mem)
4998 make_escape_constraint (build_fold_addr_expr (op));
5000 /* The asm may read global memory, so outputs may point to
5001 any global memory. */
5002 if (op)
5004 auto_vec<ce_s, 2> lhsc;
5005 struct constraint_expr rhsc, *lhsp;
5006 unsigned j;
5007 get_constraint_for (op, &lhsc);
5008 rhsc.var = nonlocal_id;
5009 rhsc.offset = 0;
5010 rhsc.type = SCALAR;
5011 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
5012 process_constraint (new_constraint (*lhsp, rhsc));
5015 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
5017 tree link = gimple_asm_input_op (asm_stmt, i);
5018 tree op = TREE_VALUE (link);
5020 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
5022 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
5023 &allows_mem, &allows_reg);
5025 /* A memory constraint makes the address of the operand escape. */
5026 if (!allows_reg && allows_mem)
5027 make_escape_constraint (build_fold_addr_expr (op));
5028 /* Strictly we'd only need the constraint to ESCAPED if
5029 the asm clobbers memory, otherwise using something
5030 along the lines of per-call clobbers/uses would be enough. */
5031 else if (op)
5032 make_escape_constraint (op);
5038 /* Create a constraint adding to the clobber set of FI the memory
5039 pointed to by PTR. */
5041 static void
5042 process_ipa_clobber (varinfo_t fi, tree ptr)
5044 vec<ce_s> ptrc = vNULL;
5045 struct constraint_expr *c, lhs;
5046 unsigned i;
5047 get_constraint_for_rhs (ptr, &ptrc);
5048 lhs = get_function_part_constraint (fi, fi_clobbers);
5049 FOR_EACH_VEC_ELT (ptrc, i, c)
5050 process_constraint (new_constraint (lhs, *c));
5051 ptrc.release ();
5054 /* Walk statement T setting up clobber and use constraints according to the
5055 references found in T. This function is a main part of the
5056 IPA constraint builder. */
5058 static void
5059 find_func_clobbers (struct function *fn, gimple *origt)
5061 gimple *t = origt;
5062 auto_vec<ce_s, 16> lhsc;
5063 auto_vec<ce_s, 16> rhsc;
5064 varinfo_t fi;
5066 /* Add constraints for clobbered/used in IPA mode.
5067 We are not interested in what automatic variables are clobbered
5068 or used as we only use the information in the caller to which
5069 they do not escape. */
5070 gcc_assert (in_ipa_mode);
5072 /* If the stmt refers to memory in any way it better had a VUSE. */
5073 if (gimple_vuse (t) == NULL_TREE)
5074 return;
5076 /* We'd better have function information for the current function. */
5077 fi = lookup_vi_for_tree (fn->decl);
5078 gcc_assert (fi != NULL);
5080 /* Account for stores in assignments and calls. */
5081 if (gimple_vdef (t) != NULL_TREE
5082 && gimple_has_lhs (t))
5084 tree lhs = gimple_get_lhs (t);
5085 tree tem = lhs;
5086 while (handled_component_p (tem))
5087 tem = TREE_OPERAND (tem, 0);
5088 if ((DECL_P (tem)
5089 && !auto_var_in_fn_p (tem, fn->decl))
5090 || INDIRECT_REF_P (tem)
5091 || (TREE_CODE (tem) == MEM_REF
5092 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
5093 && auto_var_in_fn_p
5094 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
5096 struct constraint_expr lhsc, *rhsp;
5097 unsigned i;
5098 lhsc = get_function_part_constraint (fi, fi_clobbers);
5099 get_constraint_for_address_of (lhs, &rhsc);
5100 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5101 process_constraint (new_constraint (lhsc, *rhsp));
5102 rhsc.truncate (0);
5106 /* Account for uses in assigments and returns. */
5107 if (gimple_assign_single_p (t)
5108 || (gimple_code (t) == GIMPLE_RETURN
5109 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE))
5111 tree rhs = (gimple_assign_single_p (t)
5112 ? gimple_assign_rhs1 (t)
5113 : gimple_return_retval (as_a <greturn *> (t)));
5114 tree tem = rhs;
5115 while (handled_component_p (tem))
5116 tem = TREE_OPERAND (tem, 0);
5117 if ((DECL_P (tem)
5118 && !auto_var_in_fn_p (tem, fn->decl))
5119 || INDIRECT_REF_P (tem)
5120 || (TREE_CODE (tem) == MEM_REF
5121 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
5122 && auto_var_in_fn_p
5123 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
5125 struct constraint_expr lhs, *rhsp;
5126 unsigned i;
5127 lhs = get_function_part_constraint (fi, fi_uses);
5128 get_constraint_for_address_of (rhs, &rhsc);
5129 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5130 process_constraint (new_constraint (lhs, *rhsp));
5131 rhsc.truncate (0);
5135 if (gcall *call_stmt = dyn_cast <gcall *> (t))
5137 varinfo_t cfi = NULL;
5138 tree decl = gimple_call_fndecl (t);
5139 struct constraint_expr lhs, rhs;
5140 unsigned i, j;
5142 /* For builtins we do not have separate function info. For those
5143 we do not generate escapes for we have to generate clobbers/uses. */
5144 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
5145 switch (DECL_FUNCTION_CODE (decl))
5147 /* The following functions use and clobber memory pointed to
5148 by their arguments. */
5149 case BUILT_IN_STRCPY:
5150 case BUILT_IN_STRNCPY:
5151 case BUILT_IN_BCOPY:
5152 case BUILT_IN_MEMCPY:
5153 case BUILT_IN_MEMMOVE:
5154 case BUILT_IN_MEMPCPY:
5155 case BUILT_IN_STPCPY:
5156 case BUILT_IN_STPNCPY:
5157 case BUILT_IN_STRCAT:
5158 case BUILT_IN_STRNCAT:
5159 case BUILT_IN_STRCPY_CHK:
5160 case BUILT_IN_STRNCPY_CHK:
5161 case BUILT_IN_MEMCPY_CHK:
5162 case BUILT_IN_MEMMOVE_CHK:
5163 case BUILT_IN_MEMPCPY_CHK:
5164 case BUILT_IN_STPCPY_CHK:
5165 case BUILT_IN_STPNCPY_CHK:
5166 case BUILT_IN_STRCAT_CHK:
5167 case BUILT_IN_STRNCAT_CHK:
5169 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
5170 == BUILT_IN_BCOPY ? 1 : 0));
5171 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
5172 == BUILT_IN_BCOPY ? 0 : 1));
5173 unsigned i;
5174 struct constraint_expr *rhsp, *lhsp;
5175 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
5176 lhs = get_function_part_constraint (fi, fi_clobbers);
5177 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
5178 process_constraint (new_constraint (lhs, *lhsp));
5179 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
5180 lhs = get_function_part_constraint (fi, fi_uses);
5181 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5182 process_constraint (new_constraint (lhs, *rhsp));
5183 return;
5185 /* The following function clobbers memory pointed to by
5186 its argument. */
5187 case BUILT_IN_MEMSET:
5188 case BUILT_IN_MEMSET_CHK:
5189 case BUILT_IN_POSIX_MEMALIGN:
5191 tree dest = gimple_call_arg (t, 0);
5192 unsigned i;
5193 ce_s *lhsp;
5194 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
5195 lhs = get_function_part_constraint (fi, fi_clobbers);
5196 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
5197 process_constraint (new_constraint (lhs, *lhsp));
5198 return;
5200 /* The following functions clobber their second and third
5201 arguments. */
5202 case BUILT_IN_SINCOS:
5203 case BUILT_IN_SINCOSF:
5204 case BUILT_IN_SINCOSL:
5206 process_ipa_clobber (fi, gimple_call_arg (t, 1));
5207 process_ipa_clobber (fi, gimple_call_arg (t, 2));
5208 return;
5210 /* The following functions clobber their second argument. */
5211 case BUILT_IN_FREXP:
5212 case BUILT_IN_FREXPF:
5213 case BUILT_IN_FREXPL:
5214 case BUILT_IN_LGAMMA_R:
5215 case BUILT_IN_LGAMMAF_R:
5216 case BUILT_IN_LGAMMAL_R:
5217 case BUILT_IN_GAMMA_R:
5218 case BUILT_IN_GAMMAF_R:
5219 case BUILT_IN_GAMMAL_R:
5220 case BUILT_IN_MODF:
5221 case BUILT_IN_MODFF:
5222 case BUILT_IN_MODFL:
5224 process_ipa_clobber (fi, gimple_call_arg (t, 1));
5225 return;
5227 /* The following functions clobber their third argument. */
5228 case BUILT_IN_REMQUO:
5229 case BUILT_IN_REMQUOF:
5230 case BUILT_IN_REMQUOL:
5232 process_ipa_clobber (fi, gimple_call_arg (t, 2));
5233 return;
5235 /* The following functions neither read nor clobber memory. */
5236 case BUILT_IN_ASSUME_ALIGNED:
5237 case BUILT_IN_FREE:
5238 return;
5239 /* Trampolines are of no interest to us. */
5240 case BUILT_IN_INIT_TRAMPOLINE:
5241 case BUILT_IN_ADJUST_TRAMPOLINE:
5242 return;
5243 case BUILT_IN_VA_START:
5244 case BUILT_IN_VA_END:
5245 return;
5246 case BUILT_IN_GOMP_PARALLEL:
5247 case BUILT_IN_GOACC_PARALLEL:
5249 unsigned int fnpos, argpos;
5250 unsigned int implicit_use_args[2];
5251 unsigned int num_implicit_use_args = 0;
5252 switch (DECL_FUNCTION_CODE (decl))
5254 case BUILT_IN_GOMP_PARALLEL:
5255 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
5256 fnpos = 0;
5257 argpos = 1;
5258 break;
5259 case BUILT_IN_GOACC_PARALLEL:
5260 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
5261 sizes, kinds, ...). */
5262 fnpos = 1;
5263 argpos = 3;
5264 implicit_use_args[num_implicit_use_args++] = 4;
5265 implicit_use_args[num_implicit_use_args++] = 5;
5266 break;
5267 default:
5268 gcc_unreachable ();
5271 tree fnarg = gimple_call_arg (t, fnpos);
5272 gcc_assert (TREE_CODE (fnarg) == ADDR_EXPR);
5273 tree fndecl = TREE_OPERAND (fnarg, 0);
5274 if (fndecl_maybe_in_other_partition (fndecl))
5275 /* Fallthru to general call handling. */
5276 break;
5278 varinfo_t cfi = get_vi_for_tree (fndecl);
5280 tree arg = gimple_call_arg (t, argpos);
5282 /* Parameter passed by value is used. */
5283 lhs = get_function_part_constraint (fi, fi_uses);
5284 struct constraint_expr *rhsp;
5285 get_constraint_for (arg, &rhsc);
5286 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5287 process_constraint (new_constraint (lhs, *rhsp));
5288 rhsc.truncate (0);
5290 /* Handle parameters used by the call, but not used in cfi, as
5291 implicitly used by cfi. */
5292 lhs = get_function_part_constraint (cfi, fi_uses);
5293 for (unsigned i = 0; i < num_implicit_use_args; ++i)
5295 tree arg = gimple_call_arg (t, implicit_use_args[i]);
5296 get_constraint_for (arg, &rhsc);
5297 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5298 process_constraint (new_constraint (lhs, *rhsp));
5299 rhsc.truncate (0);
5302 /* The caller clobbers what the callee does. */
5303 lhs = get_function_part_constraint (fi, fi_clobbers);
5304 rhs = get_function_part_constraint (cfi, fi_clobbers);
5305 process_constraint (new_constraint (lhs, rhs));
5307 /* The caller uses what the callee does. */
5308 lhs = get_function_part_constraint (fi, fi_uses);
5309 rhs = get_function_part_constraint (cfi, fi_uses);
5310 process_constraint (new_constraint (lhs, rhs));
5312 return;
5314 /* printf-style functions may have hooks to set pointers to
5315 point to somewhere into the generated string. Leave them
5316 for a later exercise... */
5317 default:
5318 /* Fallthru to general call handling. */;
5321 /* Parameters passed by value are used. */
5322 lhs = get_function_part_constraint (fi, fi_uses);
5323 for (i = 0; i < gimple_call_num_args (t); i++)
5325 struct constraint_expr *rhsp;
5326 tree arg = gimple_call_arg (t, i);
5328 if (TREE_CODE (arg) == SSA_NAME
5329 || is_gimple_min_invariant (arg))
5330 continue;
5332 get_constraint_for_address_of (arg, &rhsc);
5333 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5334 process_constraint (new_constraint (lhs, *rhsp));
5335 rhsc.truncate (0);
5338 /* Build constraints for propagating clobbers/uses along the
5339 callgraph edges. */
5340 cfi = get_fi_for_callee (call_stmt);
5341 if (cfi->id == anything_id)
5343 if (gimple_vdef (t))
5344 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5345 anything_id);
5346 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5347 anything_id);
5348 return;
5351 /* For callees without function info (that's external functions),
5352 ESCAPED is clobbered and used. */
5353 if (gimple_call_fndecl (t)
5354 && !cfi->is_fn_info)
5356 varinfo_t vi;
5358 if (gimple_vdef (t))
5359 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5360 escaped_id);
5361 make_copy_constraint (first_vi_for_offset (fi, fi_uses), escaped_id);
5363 /* Also honor the call statement use/clobber info. */
5364 if ((vi = lookup_call_clobber_vi (call_stmt)) != NULL)
5365 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5366 vi->id);
5367 if ((vi = lookup_call_use_vi (call_stmt)) != NULL)
5368 make_copy_constraint (first_vi_for_offset (fi, fi_uses),
5369 vi->id);
5370 return;
5373 /* Otherwise the caller clobbers and uses what the callee does.
5374 ??? This should use a new complex constraint that filters
5375 local variables of the callee. */
5376 if (gimple_vdef (t))
5378 lhs = get_function_part_constraint (fi, fi_clobbers);
5379 rhs = get_function_part_constraint (cfi, fi_clobbers);
5380 process_constraint (new_constraint (lhs, rhs));
5382 lhs = get_function_part_constraint (fi, fi_uses);
5383 rhs = get_function_part_constraint (cfi, fi_uses);
5384 process_constraint (new_constraint (lhs, rhs));
5386 else if (gimple_code (t) == GIMPLE_ASM)
5388 /* ??? Ick. We can do better. */
5389 if (gimple_vdef (t))
5390 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5391 anything_id);
5392 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5393 anything_id);
5398 /* Find the first varinfo in the same variable as START that overlaps with
5399 OFFSET. Return NULL if we can't find one. */
5401 static varinfo_t
5402 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
5404 /* If the offset is outside of the variable, bail out. */
5405 if (offset >= start->fullsize)
5406 return NULL;
5408 /* If we cannot reach offset from start, lookup the first field
5409 and start from there. */
5410 if (start->offset > offset)
5411 start = get_varinfo (start->head);
5413 while (start)
5415 /* We may not find a variable in the field list with the actual
5416 offset when we have glommed a structure to a variable.
5417 In that case, however, offset should still be within the size
5418 of the variable. */
5419 if (offset >= start->offset
5420 && (offset - start->offset) < start->size)
5421 return start;
5423 start = vi_next (start);
5426 return NULL;
5429 /* Find the first varinfo in the same variable as START that overlaps with
5430 OFFSET. If there is no such varinfo the varinfo directly preceding
5431 OFFSET is returned. */
5433 static varinfo_t
5434 first_or_preceding_vi_for_offset (varinfo_t start,
5435 unsigned HOST_WIDE_INT offset)
5437 /* If we cannot reach offset from start, lookup the first field
5438 and start from there. */
5439 if (start->offset > offset)
5440 start = get_varinfo (start->head);
5442 /* We may not find a variable in the field list with the actual
5443 offset when we have glommed a structure to a variable.
5444 In that case, however, offset should still be within the size
5445 of the variable.
5446 If we got beyond the offset we look for return the field
5447 directly preceding offset which may be the last field. */
5448 while (start->next
5449 && offset >= start->offset
5450 && !((offset - start->offset) < start->size))
5451 start = vi_next (start);
5453 return start;
5457 /* This structure is used during pushing fields onto the fieldstack
5458 to track the offset of the field, since bitpos_of_field gives it
5459 relative to its immediate containing type, and we want it relative
5460 to the ultimate containing object. */
5462 struct fieldoff
5464 /* Offset from the base of the base containing object to this field. */
5465 HOST_WIDE_INT offset;
5467 /* Size, in bits, of the field. */
5468 unsigned HOST_WIDE_INT size;
5470 unsigned has_unknown_size : 1;
5472 unsigned must_have_pointers : 1;
5474 unsigned may_have_pointers : 1;
5476 unsigned only_restrict_pointers : 1;
5478 tree restrict_pointed_type;
5480 typedef struct fieldoff fieldoff_s;
5483 /* qsort comparison function for two fieldoff's PA and PB */
5485 static int
5486 fieldoff_compare (const void *pa, const void *pb)
5488 const fieldoff_s *foa = (const fieldoff_s *)pa;
5489 const fieldoff_s *fob = (const fieldoff_s *)pb;
5490 unsigned HOST_WIDE_INT foasize, fobsize;
5492 if (foa->offset < fob->offset)
5493 return -1;
5494 else if (foa->offset > fob->offset)
5495 return 1;
5497 foasize = foa->size;
5498 fobsize = fob->size;
5499 if (foasize < fobsize)
5500 return -1;
5501 else if (foasize > fobsize)
5502 return 1;
5503 return 0;
5506 /* Sort a fieldstack according to the field offset and sizes. */
5507 static void
5508 sort_fieldstack (vec<fieldoff_s> fieldstack)
5510 fieldstack.qsort (fieldoff_compare);
5513 /* Return true if T is a type that can have subvars. */
5515 static inline bool
5516 type_can_have_subvars (const_tree t)
5518 /* Aggregates without overlapping fields can have subvars. */
5519 return TREE_CODE (t) == RECORD_TYPE;
5522 /* Return true if V is a tree that we can have subvars for.
5523 Normally, this is any aggregate type. Also complex
5524 types which are not gimple registers can have subvars. */
5526 static inline bool
5527 var_can_have_subvars (const_tree v)
5529 /* Volatile variables should never have subvars. */
5530 if (TREE_THIS_VOLATILE (v))
5531 return false;
5533 /* Non decls or memory tags can never have subvars. */
5534 if (!DECL_P (v))
5535 return false;
5537 return type_can_have_subvars (TREE_TYPE (v));
5540 /* Return true if T is a type that does contain pointers. */
5542 static bool
5543 type_must_have_pointers (tree type)
5545 if (POINTER_TYPE_P (type))
5546 return true;
5548 if (TREE_CODE (type) == ARRAY_TYPE)
5549 return type_must_have_pointers (TREE_TYPE (type));
5551 /* A function or method can have pointers as arguments, so track
5552 those separately. */
5553 if (TREE_CODE (type) == FUNCTION_TYPE
5554 || TREE_CODE (type) == METHOD_TYPE)
5555 return true;
5557 return false;
5560 static bool
5561 field_must_have_pointers (tree t)
5563 return type_must_have_pointers (TREE_TYPE (t));
5566 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5567 the fields of TYPE onto fieldstack, recording their offsets along
5568 the way.
5570 OFFSET is used to keep track of the offset in this entire
5571 structure, rather than just the immediately containing structure.
5572 Returns false if the caller is supposed to handle the field we
5573 recursed for. */
5575 static bool
5576 push_fields_onto_fieldstack (tree type, vec<fieldoff_s> *fieldstack,
5577 HOST_WIDE_INT offset)
5579 tree field;
5580 bool empty_p = true;
5582 if (TREE_CODE (type) != RECORD_TYPE)
5583 return false;
5585 /* If the vector of fields is growing too big, bail out early.
5586 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5587 sure this fails. */
5588 if (fieldstack->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
5589 return false;
5591 for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
5592 if (TREE_CODE (field) == FIELD_DECL)
5594 bool push = false;
5595 HOST_WIDE_INT foff = bitpos_of_field (field);
5596 tree field_type = TREE_TYPE (field);
5598 if (!var_can_have_subvars (field)
5599 || TREE_CODE (field_type) == QUAL_UNION_TYPE
5600 || TREE_CODE (field_type) == UNION_TYPE)
5601 push = true;
5602 else if (!push_fields_onto_fieldstack
5603 (field_type, fieldstack, offset + foff)
5604 && (DECL_SIZE (field)
5605 && !integer_zerop (DECL_SIZE (field))))
5606 /* Empty structures may have actual size, like in C++. So
5607 see if we didn't push any subfields and the size is
5608 nonzero, push the field onto the stack. */
5609 push = true;
5611 if (push)
5613 fieldoff_s *pair = NULL;
5614 bool has_unknown_size = false;
5615 bool must_have_pointers_p;
5617 if (!fieldstack->is_empty ())
5618 pair = &fieldstack->last ();
5620 /* If there isn't anything at offset zero, create sth. */
5621 if (!pair
5622 && offset + foff != 0)
5624 fieldoff_s e
5625 = {0, offset + foff, false, false, true, false, NULL_TREE};
5626 pair = fieldstack->safe_push (e);
5629 if (!DECL_SIZE (field)
5630 || !tree_fits_uhwi_p (DECL_SIZE (field)))
5631 has_unknown_size = true;
5633 /* If adjacent fields do not contain pointers merge them. */
5634 must_have_pointers_p = field_must_have_pointers (field);
5635 if (pair
5636 && !has_unknown_size
5637 && !must_have_pointers_p
5638 && !pair->must_have_pointers
5639 && !pair->has_unknown_size
5640 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
5642 pair->size += tree_to_uhwi (DECL_SIZE (field));
5644 else
5646 fieldoff_s e;
5647 e.offset = offset + foff;
5648 e.has_unknown_size = has_unknown_size;
5649 if (!has_unknown_size)
5650 e.size = tree_to_uhwi (DECL_SIZE (field));
5651 else
5652 e.size = -1;
5653 e.must_have_pointers = must_have_pointers_p;
5654 e.may_have_pointers = true;
5655 e.only_restrict_pointers
5656 = (!has_unknown_size
5657 && POINTER_TYPE_P (field_type)
5658 && TYPE_RESTRICT (field_type));
5659 if (e.only_restrict_pointers)
5660 e.restrict_pointed_type = TREE_TYPE (field_type);
5661 fieldstack->safe_push (e);
5665 empty_p = false;
5668 return !empty_p;
5671 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5672 if it is a varargs function. */
5674 static unsigned int
5675 count_num_arguments (tree decl, bool *is_varargs)
5677 unsigned int num = 0;
5678 tree t;
5680 /* Capture named arguments for K&R functions. They do not
5681 have a prototype and thus no TYPE_ARG_TYPES. */
5682 for (t = DECL_ARGUMENTS (decl); t; t = DECL_CHAIN (t))
5683 ++num;
5685 /* Check if the function has variadic arguments. */
5686 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
5687 if (TREE_VALUE (t) == void_type_node)
5688 break;
5689 if (!t)
5690 *is_varargs = true;
5692 return num;
5695 /* Creation function node for DECL, using NAME, and return the index
5696 of the variable we've created for the function. If NONLOCAL_p, create
5697 initial constraints. */
5699 static varinfo_t
5700 create_function_info_for (tree decl, const char *name, bool add_id,
5701 bool nonlocal_p)
5703 struct function *fn = DECL_STRUCT_FUNCTION (decl);
5704 varinfo_t vi, prev_vi;
5705 tree arg;
5706 unsigned int i;
5707 bool is_varargs = false;
5708 unsigned int num_args = count_num_arguments (decl, &is_varargs);
5710 /* Create the variable info. */
5712 vi = new_var_info (decl, name, add_id);
5713 vi->offset = 0;
5714 vi->size = 1;
5715 vi->fullsize = fi_parm_base + num_args;
5716 vi->is_fn_info = 1;
5717 vi->may_have_pointers = false;
5718 if (is_varargs)
5719 vi->fullsize = ~0;
5720 insert_vi_for_tree (vi->decl, vi);
5722 prev_vi = vi;
5724 /* Create a variable for things the function clobbers and one for
5725 things the function uses. */
5727 varinfo_t clobbervi, usevi;
5728 const char *newname;
5729 char *tempname;
5731 tempname = xasprintf ("%s.clobber", name);
5732 newname = ggc_strdup (tempname);
5733 free (tempname);
5735 clobbervi = new_var_info (NULL, newname, false);
5736 clobbervi->offset = fi_clobbers;
5737 clobbervi->size = 1;
5738 clobbervi->fullsize = vi->fullsize;
5739 clobbervi->is_full_var = true;
5740 clobbervi->is_global_var = false;
5741 clobbervi->is_reg_var = true;
5743 gcc_assert (prev_vi->offset < clobbervi->offset);
5744 prev_vi->next = clobbervi->id;
5745 prev_vi = clobbervi;
5747 tempname = xasprintf ("%s.use", name);
5748 newname = ggc_strdup (tempname);
5749 free (tempname);
5751 usevi = new_var_info (NULL, newname, false);
5752 usevi->offset = fi_uses;
5753 usevi->size = 1;
5754 usevi->fullsize = vi->fullsize;
5755 usevi->is_full_var = true;
5756 usevi->is_global_var = false;
5757 usevi->is_reg_var = true;
5759 gcc_assert (prev_vi->offset < usevi->offset);
5760 prev_vi->next = usevi->id;
5761 prev_vi = usevi;
5764 /* And one for the static chain. */
5765 if (fn->static_chain_decl != NULL_TREE)
5767 varinfo_t chainvi;
5768 const char *newname;
5769 char *tempname;
5771 tempname = xasprintf ("%s.chain", name);
5772 newname = ggc_strdup (tempname);
5773 free (tempname);
5775 chainvi = new_var_info (fn->static_chain_decl, newname, false);
5776 chainvi->offset = fi_static_chain;
5777 chainvi->size = 1;
5778 chainvi->fullsize = vi->fullsize;
5779 chainvi->is_full_var = true;
5780 chainvi->is_global_var = false;
5782 insert_vi_for_tree (fn->static_chain_decl, chainvi);
5784 if (nonlocal_p
5785 && chainvi->may_have_pointers)
5786 make_constraint_from (chainvi, nonlocal_id);
5788 gcc_assert (prev_vi->offset < chainvi->offset);
5789 prev_vi->next = chainvi->id;
5790 prev_vi = chainvi;
5793 /* Create a variable for the return var. */
5794 if (DECL_RESULT (decl) != NULL
5795 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
5797 varinfo_t resultvi;
5798 const char *newname;
5799 char *tempname;
5800 tree resultdecl = decl;
5802 if (DECL_RESULT (decl))
5803 resultdecl = DECL_RESULT (decl);
5805 tempname = xasprintf ("%s.result", name);
5806 newname = ggc_strdup (tempname);
5807 free (tempname);
5809 resultvi = new_var_info (resultdecl, newname, false);
5810 resultvi->offset = fi_result;
5811 resultvi->size = 1;
5812 resultvi->fullsize = vi->fullsize;
5813 resultvi->is_full_var = true;
5814 if (DECL_RESULT (decl))
5815 resultvi->may_have_pointers = true;
5817 if (DECL_RESULT (decl))
5818 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
5820 if (nonlocal_p
5821 && DECL_RESULT (decl)
5822 && DECL_BY_REFERENCE (DECL_RESULT (decl)))
5823 make_constraint_from (resultvi, nonlocal_id);
5825 gcc_assert (prev_vi->offset < resultvi->offset);
5826 prev_vi->next = resultvi->id;
5827 prev_vi = resultvi;
5830 /* We also need to make function return values escape. Nothing
5831 escapes by returning from main though. */
5832 if (nonlocal_p
5833 && !MAIN_NAME_P (DECL_NAME (decl)))
5835 varinfo_t fi, rvi;
5836 fi = lookup_vi_for_tree (decl);
5837 rvi = first_vi_for_offset (fi, fi_result);
5838 if (rvi && rvi->offset == fi_result)
5839 make_copy_constraint (get_varinfo (escaped_id), rvi->id);
5842 /* Set up variables for each argument. */
5843 arg = DECL_ARGUMENTS (decl);
5844 for (i = 0; i < num_args; i++)
5846 varinfo_t argvi;
5847 const char *newname;
5848 char *tempname;
5849 tree argdecl = decl;
5851 if (arg)
5852 argdecl = arg;
5854 tempname = xasprintf ("%s.arg%d", name, i);
5855 newname = ggc_strdup (tempname);
5856 free (tempname);
5858 argvi = new_var_info (argdecl, newname, false);
5859 argvi->offset = fi_parm_base + i;
5860 argvi->size = 1;
5861 argvi->is_full_var = true;
5862 argvi->fullsize = vi->fullsize;
5863 if (arg)
5864 argvi->may_have_pointers = true;
5866 if (arg)
5867 insert_vi_for_tree (arg, argvi);
5869 if (nonlocal_p
5870 && argvi->may_have_pointers)
5871 make_constraint_from (argvi, nonlocal_id);
5873 gcc_assert (prev_vi->offset < argvi->offset);
5874 prev_vi->next = argvi->id;
5875 prev_vi = argvi;
5876 if (arg)
5877 arg = DECL_CHAIN (arg);
5880 /* Add one representative for all further args. */
5881 if (is_varargs)
5883 varinfo_t argvi;
5884 const char *newname;
5885 char *tempname;
5886 tree decl;
5888 tempname = xasprintf ("%s.varargs", name);
5889 newname = ggc_strdup (tempname);
5890 free (tempname);
5892 /* We need sth that can be pointed to for va_start. */
5893 decl = build_fake_var_decl (ptr_type_node);
5895 argvi = new_var_info (decl, newname, false);
5896 argvi->offset = fi_parm_base + num_args;
5897 argvi->size = ~0;
5898 argvi->is_full_var = true;
5899 argvi->is_heap_var = true;
5900 argvi->fullsize = vi->fullsize;
5902 if (nonlocal_p
5903 && argvi->may_have_pointers)
5904 make_constraint_from (argvi, nonlocal_id);
5906 gcc_assert (prev_vi->offset < argvi->offset);
5907 prev_vi->next = argvi->id;
5908 prev_vi = argvi;
5911 return vi;
5915 /* Return true if FIELDSTACK contains fields that overlap.
5916 FIELDSTACK is assumed to be sorted by offset. */
5918 static bool
5919 check_for_overlaps (vec<fieldoff_s> fieldstack)
5921 fieldoff_s *fo = NULL;
5922 unsigned int i;
5923 HOST_WIDE_INT lastoffset = -1;
5925 FOR_EACH_VEC_ELT (fieldstack, i, fo)
5927 if (fo->offset == lastoffset)
5928 return true;
5929 lastoffset = fo->offset;
5931 return false;
5934 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5935 This will also create any varinfo structures necessary for fields
5936 of DECL. DECL is a function parameter if HANDLE_PARAM is set.
5937 HANDLED_STRUCT_TYPE is used to register struct types reached by following
5938 restrict pointers. This is needed to prevent infinite recursion. */
5940 static varinfo_t
5941 create_variable_info_for_1 (tree decl, const char *name, bool add_id,
5942 bool handle_param, bitmap handled_struct_type)
5944 varinfo_t vi, newvi;
5945 tree decl_type = TREE_TYPE (decl);
5946 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
5947 auto_vec<fieldoff_s> fieldstack;
5948 fieldoff_s *fo;
5949 unsigned int i;
5951 if (!declsize
5952 || !tree_fits_uhwi_p (declsize))
5954 vi = new_var_info (decl, name, add_id);
5955 vi->offset = 0;
5956 vi->size = ~0;
5957 vi->fullsize = ~0;
5958 vi->is_unknown_size_var = true;
5959 vi->is_full_var = true;
5960 vi->may_have_pointers = true;
5961 return vi;
5964 /* Collect field information. */
5965 if (use_field_sensitive
5966 && var_can_have_subvars (decl)
5967 /* ??? Force us to not use subfields for globals in IPA mode.
5968 Else we'd have to parse arbitrary initializers. */
5969 && !(in_ipa_mode
5970 && is_global_var (decl)))
5972 fieldoff_s *fo = NULL;
5973 bool notokay = false;
5974 unsigned int i;
5976 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
5978 for (i = 0; !notokay && fieldstack.iterate (i, &fo); i++)
5979 if (fo->has_unknown_size
5980 || fo->offset < 0)
5982 notokay = true;
5983 break;
5986 /* We can't sort them if we have a field with a variable sized type,
5987 which will make notokay = true. In that case, we are going to return
5988 without creating varinfos for the fields anyway, so sorting them is a
5989 waste to boot. */
5990 if (!notokay)
5992 sort_fieldstack (fieldstack);
5993 /* Due to some C++ FE issues, like PR 22488, we might end up
5994 what appear to be overlapping fields even though they,
5995 in reality, do not overlap. Until the C++ FE is fixed,
5996 we will simply disable field-sensitivity for these cases. */
5997 notokay = check_for_overlaps (fieldstack);
6000 if (notokay)
6001 fieldstack.release ();
6004 /* If we didn't end up collecting sub-variables create a full
6005 variable for the decl. */
6006 if (fieldstack.length () == 0
6007 || fieldstack.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
6009 vi = new_var_info (decl, name, add_id);
6010 vi->offset = 0;
6011 vi->may_have_pointers = true;
6012 vi->fullsize = tree_to_uhwi (declsize);
6013 vi->size = vi->fullsize;
6014 vi->is_full_var = true;
6015 if (POINTER_TYPE_P (decl_type)
6016 && TYPE_RESTRICT (decl_type))
6017 vi->only_restrict_pointers = 1;
6018 if (vi->only_restrict_pointers
6019 && !type_contains_placeholder_p (TREE_TYPE (decl_type))
6020 && handle_param
6021 && !bitmap_bit_p (handled_struct_type,
6022 TYPE_UID (TREE_TYPE (decl_type))))
6024 varinfo_t rvi;
6025 tree heapvar = build_fake_var_decl (TREE_TYPE (decl_type));
6026 DECL_EXTERNAL (heapvar) = 1;
6027 if (var_can_have_subvars (heapvar))
6028 bitmap_set_bit (handled_struct_type,
6029 TYPE_UID (TREE_TYPE (decl_type)));
6030 rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true,
6031 true, handled_struct_type);
6032 if (var_can_have_subvars (heapvar))
6033 bitmap_clear_bit (handled_struct_type,
6034 TYPE_UID (TREE_TYPE (decl_type)));
6035 rvi->is_restrict_var = 1;
6036 insert_vi_for_tree (heapvar, rvi);
6037 make_constraint_from (vi, rvi->id);
6038 make_param_constraints (rvi);
6040 fieldstack.release ();
6041 return vi;
6044 vi = new_var_info (decl, name, add_id);
6045 vi->fullsize = tree_to_uhwi (declsize);
6046 if (fieldstack.length () == 1)
6047 vi->is_full_var = true;
6048 for (i = 0, newvi = vi;
6049 fieldstack.iterate (i, &fo);
6050 ++i, newvi = vi_next (newvi))
6052 const char *newname = NULL;
6053 char *tempname;
6055 if (dump_file)
6057 if (fieldstack.length () != 1)
6059 tempname
6060 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC
6061 "+" HOST_WIDE_INT_PRINT_DEC, name,
6062 fo->offset, fo->size);
6063 newname = ggc_strdup (tempname);
6064 free (tempname);
6067 else
6068 newname = "NULL";
6070 if (newname)
6071 newvi->name = newname;
6072 newvi->offset = fo->offset;
6073 newvi->size = fo->size;
6074 newvi->fullsize = vi->fullsize;
6075 newvi->may_have_pointers = fo->may_have_pointers;
6076 newvi->only_restrict_pointers = fo->only_restrict_pointers;
6077 if (handle_param
6078 && newvi->only_restrict_pointers
6079 && !type_contains_placeholder_p (fo->restrict_pointed_type)
6080 && !bitmap_bit_p (handled_struct_type,
6081 TYPE_UID (fo->restrict_pointed_type)))
6083 varinfo_t rvi;
6084 tree heapvar = build_fake_var_decl (fo->restrict_pointed_type);
6085 DECL_EXTERNAL (heapvar) = 1;
6086 if (var_can_have_subvars (heapvar))
6087 bitmap_set_bit (handled_struct_type,
6088 TYPE_UID (fo->restrict_pointed_type));
6089 rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true,
6090 true, handled_struct_type);
6091 if (var_can_have_subvars (heapvar))
6092 bitmap_clear_bit (handled_struct_type,
6093 TYPE_UID (fo->restrict_pointed_type));
6094 rvi->is_restrict_var = 1;
6095 insert_vi_for_tree (heapvar, rvi);
6096 make_constraint_from (newvi, rvi->id);
6097 make_param_constraints (rvi);
6099 if (i + 1 < fieldstack.length ())
6101 varinfo_t tem = new_var_info (decl, name, false);
6102 newvi->next = tem->id;
6103 tem->head = vi->id;
6107 return vi;
6110 static unsigned int
6111 create_variable_info_for (tree decl, const char *name, bool add_id)
6113 varinfo_t vi = create_variable_info_for_1 (decl, name, add_id, false, NULL);
6114 unsigned int id = vi->id;
6116 insert_vi_for_tree (decl, vi);
6118 if (!VAR_P (decl))
6119 return id;
6121 /* Create initial constraints for globals. */
6122 for (; vi; vi = vi_next (vi))
6124 if (!vi->may_have_pointers
6125 || !vi->is_global_var)
6126 continue;
6128 /* Mark global restrict qualified pointers. */
6129 if ((POINTER_TYPE_P (TREE_TYPE (decl))
6130 && TYPE_RESTRICT (TREE_TYPE (decl)))
6131 || vi->only_restrict_pointers)
6133 varinfo_t rvi
6134 = make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT",
6135 true);
6136 /* ??? For now exclude reads from globals as restrict sources
6137 if those are not (indirectly) from incoming parameters. */
6138 rvi->is_restrict_var = false;
6139 continue;
6142 /* In non-IPA mode the initializer from nonlocal is all we need. */
6143 if (!in_ipa_mode
6144 || DECL_HARD_REGISTER (decl))
6145 make_copy_constraint (vi, nonlocal_id);
6147 /* In IPA mode parse the initializer and generate proper constraints
6148 for it. */
6149 else
6151 varpool_node *vnode = varpool_node::get (decl);
6153 /* For escaped variables initialize them from nonlocal. */
6154 if (!vnode->all_refs_explicit_p ())
6155 make_copy_constraint (vi, nonlocal_id);
6157 /* If this is a global variable with an initializer and we are in
6158 IPA mode generate constraints for it. */
6159 ipa_ref *ref;
6160 for (unsigned idx = 0; vnode->iterate_reference (idx, ref); ++idx)
6162 auto_vec<ce_s> rhsc;
6163 struct constraint_expr lhs, *rhsp;
6164 unsigned i;
6165 get_constraint_for_address_of (ref->referred->decl, &rhsc);
6166 lhs.var = vi->id;
6167 lhs.offset = 0;
6168 lhs.type = SCALAR;
6169 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
6170 process_constraint (new_constraint (lhs, *rhsp));
6171 /* If this is a variable that escapes from the unit
6172 the initializer escapes as well. */
6173 if (!vnode->all_refs_explicit_p ())
6175 lhs.var = escaped_id;
6176 lhs.offset = 0;
6177 lhs.type = SCALAR;
6178 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
6179 process_constraint (new_constraint (lhs, *rhsp));
6185 return id;
6188 /* Print out the points-to solution for VAR to FILE. */
6190 static void
6191 dump_solution_for_var (FILE *file, unsigned int var)
6193 varinfo_t vi = get_varinfo (var);
6194 unsigned int i;
6195 bitmap_iterator bi;
6197 /* Dump the solution for unified vars anyway, this avoids difficulties
6198 in scanning dumps in the testsuite. */
6199 fprintf (file, "%s = { ", vi->name);
6200 vi = get_varinfo (find (var));
6201 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
6202 fprintf (file, "%s ", get_varinfo (i)->name);
6203 fprintf (file, "}");
6205 /* But note when the variable was unified. */
6206 if (vi->id != var)
6207 fprintf (file, " same as %s", vi->name);
6209 fprintf (file, "\n");
6212 /* Print the points-to solution for VAR to stderr. */
6214 DEBUG_FUNCTION void
6215 debug_solution_for_var (unsigned int var)
6217 dump_solution_for_var (stderr, var);
6220 /* Register the constraints for function parameter related VI. */
6222 static void
6223 make_param_constraints (varinfo_t vi)
6225 for (; vi; vi = vi_next (vi))
6227 if (vi->only_restrict_pointers)
6229 else if (vi->may_have_pointers)
6230 make_constraint_from (vi, nonlocal_id);
6232 if (vi->is_full_var)
6233 break;
6237 /* Create varinfo structures for all of the variables in the
6238 function for intraprocedural mode. */
6240 static void
6241 intra_create_variable_infos (struct function *fn)
6243 tree t;
6244 bitmap handled_struct_type = NULL;
6246 /* For each incoming pointer argument arg, create the constraint ARG
6247 = NONLOCAL or a dummy variable if it is a restrict qualified
6248 passed-by-reference argument. */
6249 for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t))
6251 if (handled_struct_type == NULL)
6252 handled_struct_type = BITMAP_ALLOC (NULL);
6254 varinfo_t p
6255 = create_variable_info_for_1 (t, alias_get_name (t), false, true,
6256 handled_struct_type);
6257 insert_vi_for_tree (t, p);
6259 make_param_constraints (p);
6262 if (handled_struct_type != NULL)
6263 BITMAP_FREE (handled_struct_type);
6265 /* Add a constraint for a result decl that is passed by reference. */
6266 if (DECL_RESULT (fn->decl)
6267 && DECL_BY_REFERENCE (DECL_RESULT (fn->decl)))
6269 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (fn->decl));
6271 for (p = result_vi; p; p = vi_next (p))
6272 make_constraint_from (p, nonlocal_id);
6275 /* Add a constraint for the incoming static chain parameter. */
6276 if (fn->static_chain_decl != NULL_TREE)
6278 varinfo_t p, chain_vi = get_vi_for_tree (fn->static_chain_decl);
6280 for (p = chain_vi; p; p = vi_next (p))
6281 make_constraint_from (p, nonlocal_id);
6285 /* Structure used to put solution bitmaps in a hashtable so they can
6286 be shared among variables with the same points-to set. */
6288 typedef struct shared_bitmap_info
6290 bitmap pt_vars;
6291 hashval_t hashcode;
6292 } *shared_bitmap_info_t;
6293 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
6295 /* Shared_bitmap hashtable helpers. */
6297 struct shared_bitmap_hasher : free_ptr_hash <shared_bitmap_info>
6299 static inline hashval_t hash (const shared_bitmap_info *);
6300 static inline bool equal (const shared_bitmap_info *,
6301 const shared_bitmap_info *);
6304 /* Hash function for a shared_bitmap_info_t */
6306 inline hashval_t
6307 shared_bitmap_hasher::hash (const shared_bitmap_info *bi)
6309 return bi->hashcode;
6312 /* Equality function for two shared_bitmap_info_t's. */
6314 inline bool
6315 shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1,
6316 const shared_bitmap_info *sbi2)
6318 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
6321 /* Shared_bitmap hashtable. */
6323 static hash_table<shared_bitmap_hasher> *shared_bitmap_table;
6325 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
6326 existing instance if there is one, NULL otherwise. */
6328 static bitmap
6329 shared_bitmap_lookup (bitmap pt_vars)
6331 shared_bitmap_info **slot;
6332 struct shared_bitmap_info sbi;
6334 sbi.pt_vars = pt_vars;
6335 sbi.hashcode = bitmap_hash (pt_vars);
6337 slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
6338 if (!slot)
6339 return NULL;
6340 else
6341 return (*slot)->pt_vars;
6345 /* Add a bitmap to the shared bitmap hashtable. */
6347 static void
6348 shared_bitmap_add (bitmap pt_vars)
6350 shared_bitmap_info **slot;
6351 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
6353 sbi->pt_vars = pt_vars;
6354 sbi->hashcode = bitmap_hash (pt_vars);
6356 slot = shared_bitmap_table->find_slot (sbi, INSERT);
6357 gcc_assert (!*slot);
6358 *slot = sbi;
6362 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
6364 static void
6365 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt,
6366 tree fndecl)
6368 unsigned int i;
6369 bitmap_iterator bi;
6370 varinfo_t escaped_vi = get_varinfo (find (escaped_id));
6371 bool everything_escaped
6372 = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
6374 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
6376 varinfo_t vi = get_varinfo (i);
6378 /* The only artificial variables that are allowed in a may-alias
6379 set are heap variables. */
6380 if (vi->is_artificial_var && !vi->is_heap_var)
6381 continue;
6383 if (everything_escaped
6384 || (escaped_vi->solution
6385 && bitmap_bit_p (escaped_vi->solution, i)))
6387 pt->vars_contains_escaped = true;
6388 pt->vars_contains_escaped_heap = vi->is_heap_var;
6391 if (vi->is_restrict_var)
6392 pt->vars_contains_restrict = true;
6394 if (VAR_P (vi->decl)
6395 || TREE_CODE (vi->decl) == PARM_DECL
6396 || TREE_CODE (vi->decl) == RESULT_DECL)
6398 /* If we are in IPA mode we will not recompute points-to
6399 sets after inlining so make sure they stay valid. */
6400 if (in_ipa_mode
6401 && !DECL_PT_UID_SET_P (vi->decl))
6402 SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
6404 /* Add the decl to the points-to set. Note that the points-to
6405 set contains global variables. */
6406 bitmap_set_bit (into, DECL_PT_UID (vi->decl));
6407 if (vi->is_global_var
6408 /* In IPA mode the escaped_heap trick doesn't work as
6409 ESCAPED is escaped from the unit but
6410 pt_solution_includes_global needs to answer true for
6411 all variables not automatic within a function.
6412 For the same reason is_global_var is not the
6413 correct flag to track - local variables from other
6414 functions also need to be considered global.
6415 Conveniently all HEAP vars are not put in function
6416 scope. */
6417 || (in_ipa_mode
6418 && fndecl
6419 && ! auto_var_in_fn_p (vi->decl, fndecl)))
6420 pt->vars_contains_nonlocal = true;
6422 /* If we have a variable that is interposable record that fact
6423 for pointer comparison simplification. */
6424 if (VAR_P (vi->decl)
6425 && (TREE_STATIC (vi->decl) || DECL_EXTERNAL (vi->decl))
6426 && ! decl_binds_to_current_def_p (vi->decl))
6427 pt->vars_contains_interposable = true;
6430 else if (TREE_CODE (vi->decl) == FUNCTION_DECL
6431 || TREE_CODE (vi->decl) == LABEL_DECL)
6433 /* Nothing should read/write from/to code so we can
6434 save bits by not including them in the points-to bitmaps.
6435 Still mark the points-to set as containing global memory
6436 to make code-patching possible - see PR70128. */
6437 pt->vars_contains_nonlocal = true;
6443 /* Compute the points-to solution *PT for the variable VI. */
6445 static struct pt_solution
6446 find_what_var_points_to (tree fndecl, varinfo_t orig_vi)
6448 unsigned int i;
6449 bitmap_iterator bi;
6450 bitmap finished_solution;
6451 bitmap result;
6452 varinfo_t vi;
6453 struct pt_solution *pt;
6455 /* This variable may have been collapsed, let's get the real
6456 variable. */
6457 vi = get_varinfo (find (orig_vi->id));
6459 /* See if we have already computed the solution and return it. */
6460 pt_solution **slot = &final_solutions->get_or_insert (vi);
6461 if (*slot != NULL)
6462 return **slot;
6464 *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
6465 memset (pt, 0, sizeof (struct pt_solution));
6467 /* Translate artificial variables into SSA_NAME_PTR_INFO
6468 attributes. */
6469 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
6471 varinfo_t vi = get_varinfo (i);
6473 if (vi->is_artificial_var)
6475 if (vi->id == nothing_id)
6476 pt->null = 1;
6477 else if (vi->id == escaped_id)
6479 if (in_ipa_mode)
6480 pt->ipa_escaped = 1;
6481 else
6482 pt->escaped = 1;
6483 /* Expand some special vars of ESCAPED in-place here. */
6484 varinfo_t evi = get_varinfo (find (escaped_id));
6485 if (bitmap_bit_p (evi->solution, nonlocal_id))
6486 pt->nonlocal = 1;
6488 else if (vi->id == nonlocal_id)
6489 pt->nonlocal = 1;
6490 else if (vi->is_heap_var)
6491 /* We represent heapvars in the points-to set properly. */
6493 else if (vi->id == string_id)
6494 /* Nobody cares - STRING_CSTs are read-only entities. */
6496 else if (vi->id == anything_id
6497 || vi->id == integer_id)
6498 pt->anything = 1;
6502 /* Instead of doing extra work, simply do not create
6503 elaborate points-to information for pt_anything pointers. */
6504 if (pt->anything)
6505 return *pt;
6507 /* Share the final set of variables when possible. */
6508 finished_solution = BITMAP_GGC_ALLOC ();
6509 stats.points_to_sets_created++;
6511 set_uids_in_ptset (finished_solution, vi->solution, pt, fndecl);
6512 result = shared_bitmap_lookup (finished_solution);
6513 if (!result)
6515 shared_bitmap_add (finished_solution);
6516 pt->vars = finished_solution;
6518 else
6520 pt->vars = result;
6521 bitmap_clear (finished_solution);
6524 return *pt;
6527 /* Given a pointer variable P, fill in its points-to set. */
6529 static void
6530 find_what_p_points_to (tree fndecl, tree p)
6532 struct ptr_info_def *pi;
6533 tree lookup_p = p;
6534 varinfo_t vi;
6535 bool nonnull = get_ptr_nonnull (p);
6537 /* For parameters, get at the points-to set for the actual parm
6538 decl. */
6539 if (TREE_CODE (p) == SSA_NAME
6540 && SSA_NAME_IS_DEFAULT_DEF (p)
6541 && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
6542 || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
6543 lookup_p = SSA_NAME_VAR (p);
6545 vi = lookup_vi_for_tree (lookup_p);
6546 if (!vi)
6547 return;
6549 pi = get_ptr_info (p);
6550 pi->pt = find_what_var_points_to (fndecl, vi);
6551 /* Conservatively set to NULL from PTA (to true). */
6552 pi->pt.null = 1;
6553 /* Preserve pointer nonnull computed by VRP. See get_ptr_nonnull
6554 in gcc/tree-ssaname.c for more information. */
6555 if (nonnull)
6556 set_ptr_nonnull (p);
6560 /* Query statistics for points-to solutions. */
6562 static struct {
6563 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
6564 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
6565 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
6566 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
6567 } pta_stats;
6569 void
6570 dump_pta_stats (FILE *s)
6572 fprintf (s, "\nPTA query stats:\n");
6573 fprintf (s, " pt_solution_includes: "
6574 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6575 HOST_WIDE_INT_PRINT_DEC" queries\n",
6576 pta_stats.pt_solution_includes_no_alias,
6577 pta_stats.pt_solution_includes_no_alias
6578 + pta_stats.pt_solution_includes_may_alias);
6579 fprintf (s, " pt_solutions_intersect: "
6580 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6581 HOST_WIDE_INT_PRINT_DEC" queries\n",
6582 pta_stats.pt_solutions_intersect_no_alias,
6583 pta_stats.pt_solutions_intersect_no_alias
6584 + pta_stats.pt_solutions_intersect_may_alias);
6588 /* Reset the points-to solution *PT to a conservative default
6589 (point to anything). */
6591 void
6592 pt_solution_reset (struct pt_solution *pt)
6594 memset (pt, 0, sizeof (struct pt_solution));
6595 pt->anything = true;
6596 pt->null = true;
6599 /* Set the points-to solution *PT to point only to the variables
6600 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6601 global variables and VARS_CONTAINS_RESTRICT specifies whether
6602 it contains restrict tag variables. */
6604 void
6605 pt_solution_set (struct pt_solution *pt, bitmap vars,
6606 bool vars_contains_nonlocal)
6608 memset (pt, 0, sizeof (struct pt_solution));
6609 pt->vars = vars;
6610 pt->vars_contains_nonlocal = vars_contains_nonlocal;
6611 pt->vars_contains_escaped
6612 = (cfun->gimple_df->escaped.anything
6613 || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
6616 /* Set the points-to solution *PT to point only to the variable VAR. */
6618 void
6619 pt_solution_set_var (struct pt_solution *pt, tree var)
6621 memset (pt, 0, sizeof (struct pt_solution));
6622 pt->vars = BITMAP_GGC_ALLOC ();
6623 bitmap_set_bit (pt->vars, DECL_PT_UID (var));
6624 pt->vars_contains_nonlocal = is_global_var (var);
6625 pt->vars_contains_escaped
6626 = (cfun->gimple_df->escaped.anything
6627 || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
6630 /* Computes the union of the points-to solutions *DEST and *SRC and
6631 stores the result in *DEST. This changes the points-to bitmap
6632 of *DEST and thus may not be used if that might be shared.
6633 The points-to bitmap of *SRC and *DEST will not be shared after
6634 this function if they were not before. */
6636 static void
6637 pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
6639 dest->anything |= src->anything;
6640 if (dest->anything)
6642 pt_solution_reset (dest);
6643 return;
6646 dest->nonlocal |= src->nonlocal;
6647 dest->escaped |= src->escaped;
6648 dest->ipa_escaped |= src->ipa_escaped;
6649 dest->null |= src->null;
6650 dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
6651 dest->vars_contains_escaped |= src->vars_contains_escaped;
6652 dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
6653 if (!src->vars)
6654 return;
6656 if (!dest->vars)
6657 dest->vars = BITMAP_GGC_ALLOC ();
6658 bitmap_ior_into (dest->vars, src->vars);
6661 /* Return true if the points-to solution *PT is empty. */
6663 bool
6664 pt_solution_empty_p (struct pt_solution *pt)
6666 if (pt->anything
6667 || pt->nonlocal)
6668 return false;
6670 if (pt->vars
6671 && !bitmap_empty_p (pt->vars))
6672 return false;
6674 /* If the solution includes ESCAPED, check if that is empty. */
6675 if (pt->escaped
6676 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
6677 return false;
6679 /* If the solution includes ESCAPED, check if that is empty. */
6680 if (pt->ipa_escaped
6681 && !pt_solution_empty_p (&ipa_escaped_pt))
6682 return false;
6684 return true;
6687 /* Return true if the points-to solution *PT only point to a single var, and
6688 return the var uid in *UID. */
6690 bool
6691 pt_solution_singleton_or_null_p (struct pt_solution *pt, unsigned *uid)
6693 if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
6694 || pt->vars == NULL
6695 || !bitmap_single_bit_set_p (pt->vars))
6696 return false;
6698 *uid = bitmap_first_set_bit (pt->vars);
6699 return true;
6702 /* Return true if the points-to solution *PT includes global memory. */
6704 bool
6705 pt_solution_includes_global (struct pt_solution *pt)
6707 if (pt->anything
6708 || pt->nonlocal
6709 || pt->vars_contains_nonlocal
6710 /* The following is a hack to make the malloc escape hack work.
6711 In reality we'd need different sets for escaped-through-return
6712 and escaped-to-callees and passes would need to be updated. */
6713 || pt->vars_contains_escaped_heap)
6714 return true;
6716 /* 'escaped' is also a placeholder so we have to look into it. */
6717 if (pt->escaped)
6718 return pt_solution_includes_global (&cfun->gimple_df->escaped);
6720 if (pt->ipa_escaped)
6721 return pt_solution_includes_global (&ipa_escaped_pt);
6723 return false;
6726 /* Return true if the points-to solution *PT includes the variable
6727 declaration DECL. */
6729 static bool
6730 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
6732 if (pt->anything)
6733 return true;
6735 if (pt->nonlocal
6736 && is_global_var (decl))
6737 return true;
6739 if (pt->vars
6740 && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
6741 return true;
6743 /* If the solution includes ESCAPED, check it. */
6744 if (pt->escaped
6745 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
6746 return true;
6748 /* If the solution includes ESCAPED, check it. */
6749 if (pt->ipa_escaped
6750 && pt_solution_includes_1 (&ipa_escaped_pt, decl))
6751 return true;
6753 return false;
6756 bool
6757 pt_solution_includes (struct pt_solution *pt, const_tree decl)
6759 bool res = pt_solution_includes_1 (pt, decl);
6760 if (res)
6761 ++pta_stats.pt_solution_includes_may_alias;
6762 else
6763 ++pta_stats.pt_solution_includes_no_alias;
6764 return res;
6767 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6768 intersection. */
6770 static bool
6771 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
6773 if (pt1->anything || pt2->anything)
6774 return true;
6776 /* If either points to unknown global memory and the other points to
6777 any global memory they alias. */
6778 if ((pt1->nonlocal
6779 && (pt2->nonlocal
6780 || pt2->vars_contains_nonlocal))
6781 || (pt2->nonlocal
6782 && pt1->vars_contains_nonlocal))
6783 return true;
6785 /* If either points to all escaped memory and the other points to
6786 any escaped memory they alias. */
6787 if ((pt1->escaped
6788 && (pt2->escaped
6789 || pt2->vars_contains_escaped))
6790 || (pt2->escaped
6791 && pt1->vars_contains_escaped))
6792 return true;
6794 /* Check the escaped solution if required.
6795 ??? Do we need to check the local against the IPA escaped sets? */
6796 if ((pt1->ipa_escaped || pt2->ipa_escaped)
6797 && !pt_solution_empty_p (&ipa_escaped_pt))
6799 /* If both point to escaped memory and that solution
6800 is not empty they alias. */
6801 if (pt1->ipa_escaped && pt2->ipa_escaped)
6802 return true;
6804 /* If either points to escaped memory see if the escaped solution
6805 intersects with the other. */
6806 if ((pt1->ipa_escaped
6807 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
6808 || (pt2->ipa_escaped
6809 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
6810 return true;
6813 /* Now both pointers alias if their points-to solution intersects. */
6814 return (pt1->vars
6815 && pt2->vars
6816 && bitmap_intersect_p (pt1->vars, pt2->vars));
6819 bool
6820 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
6822 bool res = pt_solutions_intersect_1 (pt1, pt2);
6823 if (res)
6824 ++pta_stats.pt_solutions_intersect_may_alias;
6825 else
6826 ++pta_stats.pt_solutions_intersect_no_alias;
6827 return res;
6831 /* Dump points-to information to OUTFILE. */
6833 static void
6834 dump_sa_points_to_info (FILE *outfile)
6836 unsigned int i;
6838 fprintf (outfile, "\nPoints-to sets\n\n");
6840 if (dump_flags & TDF_STATS)
6842 fprintf (outfile, "Stats:\n");
6843 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
6844 fprintf (outfile, "Non-pointer vars: %d\n",
6845 stats.nonpointer_vars);
6846 fprintf (outfile, "Statically unified vars: %d\n",
6847 stats.unified_vars_static);
6848 fprintf (outfile, "Dynamically unified vars: %d\n",
6849 stats.unified_vars_dynamic);
6850 fprintf (outfile, "Iterations: %d\n", stats.iterations);
6851 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
6852 fprintf (outfile, "Number of implicit edges: %d\n",
6853 stats.num_implicit_edges);
6856 for (i = 1; i < varmap.length (); i++)
6858 varinfo_t vi = get_varinfo (i);
6859 if (!vi->may_have_pointers)
6860 continue;
6861 dump_solution_for_var (outfile, i);
6866 /* Debug points-to information to stderr. */
6868 DEBUG_FUNCTION void
6869 debug_sa_points_to_info (void)
6871 dump_sa_points_to_info (stderr);
6875 /* Initialize the always-existing constraint variables for NULL
6876 ANYTHING, READONLY, and INTEGER */
6878 static void
6879 init_base_vars (void)
6881 struct constraint_expr lhs, rhs;
6882 varinfo_t var_anything;
6883 varinfo_t var_nothing;
6884 varinfo_t var_string;
6885 varinfo_t var_escaped;
6886 varinfo_t var_nonlocal;
6887 varinfo_t var_storedanything;
6888 varinfo_t var_integer;
6890 /* Variable ID zero is reserved and should be NULL. */
6891 varmap.safe_push (NULL);
6893 /* Create the NULL variable, used to represent that a variable points
6894 to NULL. */
6895 var_nothing = new_var_info (NULL_TREE, "NULL", false);
6896 gcc_assert (var_nothing->id == nothing_id);
6897 var_nothing->is_artificial_var = 1;
6898 var_nothing->offset = 0;
6899 var_nothing->size = ~0;
6900 var_nothing->fullsize = ~0;
6901 var_nothing->is_special_var = 1;
6902 var_nothing->may_have_pointers = 0;
6903 var_nothing->is_global_var = 0;
6905 /* Create the ANYTHING variable, used to represent that a variable
6906 points to some unknown piece of memory. */
6907 var_anything = new_var_info (NULL_TREE, "ANYTHING", false);
6908 gcc_assert (var_anything->id == anything_id);
6909 var_anything->is_artificial_var = 1;
6910 var_anything->size = ~0;
6911 var_anything->offset = 0;
6912 var_anything->fullsize = ~0;
6913 var_anything->is_special_var = 1;
6915 /* Anything points to anything. This makes deref constraints just
6916 work in the presence of linked list and other p = *p type loops,
6917 by saying that *ANYTHING = ANYTHING. */
6918 lhs.type = SCALAR;
6919 lhs.var = anything_id;
6920 lhs.offset = 0;
6921 rhs.type = ADDRESSOF;
6922 rhs.var = anything_id;
6923 rhs.offset = 0;
6925 /* This specifically does not use process_constraint because
6926 process_constraint ignores all anything = anything constraints, since all
6927 but this one are redundant. */
6928 constraints.safe_push (new_constraint (lhs, rhs));
6930 /* Create the STRING variable, used to represent that a variable
6931 points to a string literal. String literals don't contain
6932 pointers so STRING doesn't point to anything. */
6933 var_string = new_var_info (NULL_TREE, "STRING", false);
6934 gcc_assert (var_string->id == string_id);
6935 var_string->is_artificial_var = 1;
6936 var_string->offset = 0;
6937 var_string->size = ~0;
6938 var_string->fullsize = ~0;
6939 var_string->is_special_var = 1;
6940 var_string->may_have_pointers = 0;
6942 /* Create the ESCAPED variable, used to represent the set of escaped
6943 memory. */
6944 var_escaped = new_var_info (NULL_TREE, "ESCAPED", false);
6945 gcc_assert (var_escaped->id == escaped_id);
6946 var_escaped->is_artificial_var = 1;
6947 var_escaped->offset = 0;
6948 var_escaped->size = ~0;
6949 var_escaped->fullsize = ~0;
6950 var_escaped->is_special_var = 0;
6952 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6953 memory. */
6954 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL", false);
6955 gcc_assert (var_nonlocal->id == nonlocal_id);
6956 var_nonlocal->is_artificial_var = 1;
6957 var_nonlocal->offset = 0;
6958 var_nonlocal->size = ~0;
6959 var_nonlocal->fullsize = ~0;
6960 var_nonlocal->is_special_var = 1;
6962 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6963 lhs.type = SCALAR;
6964 lhs.var = escaped_id;
6965 lhs.offset = 0;
6966 rhs.type = DEREF;
6967 rhs.var = escaped_id;
6968 rhs.offset = 0;
6969 process_constraint (new_constraint (lhs, rhs));
6971 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6972 whole variable escapes. */
6973 lhs.type = SCALAR;
6974 lhs.var = escaped_id;
6975 lhs.offset = 0;
6976 rhs.type = SCALAR;
6977 rhs.var = escaped_id;
6978 rhs.offset = UNKNOWN_OFFSET;
6979 process_constraint (new_constraint (lhs, rhs));
6981 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6982 everything pointed to by escaped points to what global memory can
6983 point to. */
6984 lhs.type = DEREF;
6985 lhs.var = escaped_id;
6986 lhs.offset = 0;
6987 rhs.type = SCALAR;
6988 rhs.var = nonlocal_id;
6989 rhs.offset = 0;
6990 process_constraint (new_constraint (lhs, rhs));
6992 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6993 global memory may point to global memory and escaped memory. */
6994 lhs.type = SCALAR;
6995 lhs.var = nonlocal_id;
6996 lhs.offset = 0;
6997 rhs.type = ADDRESSOF;
6998 rhs.var = nonlocal_id;
6999 rhs.offset = 0;
7000 process_constraint (new_constraint (lhs, rhs));
7001 rhs.type = ADDRESSOF;
7002 rhs.var = escaped_id;
7003 rhs.offset = 0;
7004 process_constraint (new_constraint (lhs, rhs));
7006 /* Create the STOREDANYTHING variable, used to represent the set of
7007 variables stored to *ANYTHING. */
7008 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING", false);
7009 gcc_assert (var_storedanything->id == storedanything_id);
7010 var_storedanything->is_artificial_var = 1;
7011 var_storedanything->offset = 0;
7012 var_storedanything->size = ~0;
7013 var_storedanything->fullsize = ~0;
7014 var_storedanything->is_special_var = 0;
7016 /* Create the INTEGER variable, used to represent that a variable points
7017 to what an INTEGER "points to". */
7018 var_integer = new_var_info (NULL_TREE, "INTEGER", false);
7019 gcc_assert (var_integer->id == integer_id);
7020 var_integer->is_artificial_var = 1;
7021 var_integer->size = ~0;
7022 var_integer->fullsize = ~0;
7023 var_integer->offset = 0;
7024 var_integer->is_special_var = 1;
7026 /* INTEGER = ANYTHING, because we don't know where a dereference of
7027 a random integer will point to. */
7028 lhs.type = SCALAR;
7029 lhs.var = integer_id;
7030 lhs.offset = 0;
7031 rhs.type = ADDRESSOF;
7032 rhs.var = anything_id;
7033 rhs.offset = 0;
7034 process_constraint (new_constraint (lhs, rhs));
7037 /* Initialize things necessary to perform PTA */
7039 static void
7040 init_alias_vars (void)
7042 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
7044 bitmap_obstack_initialize (&pta_obstack);
7045 bitmap_obstack_initialize (&oldpta_obstack);
7046 bitmap_obstack_initialize (&predbitmap_obstack);
7048 constraints.create (8);
7049 varmap.create (8);
7050 vi_for_tree = new hash_map<tree, varinfo_t>;
7051 call_stmt_vars = new hash_map<gimple *, varinfo_t>;
7053 memset (&stats, 0, sizeof (stats));
7054 shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
7055 init_base_vars ();
7057 gcc_obstack_init (&fake_var_decl_obstack);
7059 final_solutions = new hash_map<varinfo_t, pt_solution *>;
7060 gcc_obstack_init (&final_solutions_obstack);
7063 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
7064 predecessor edges. */
7066 static void
7067 remove_preds_and_fake_succs (constraint_graph_t graph)
7069 unsigned int i;
7071 /* Clear the implicit ref and address nodes from the successor
7072 lists. */
7073 for (i = 1; i < FIRST_REF_NODE; i++)
7075 if (graph->succs[i])
7076 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
7077 FIRST_REF_NODE * 2);
7080 /* Free the successor list for the non-ref nodes. */
7081 for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
7083 if (graph->succs[i])
7084 BITMAP_FREE (graph->succs[i]);
7087 /* Now reallocate the size of the successor list as, and blow away
7088 the predecessor bitmaps. */
7089 graph->size = varmap.length ();
7090 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
7092 free (graph->implicit_preds);
7093 graph->implicit_preds = NULL;
7094 free (graph->preds);
7095 graph->preds = NULL;
7096 bitmap_obstack_release (&predbitmap_obstack);
7099 /* Solve the constraint set. */
7101 static void
7102 solve_constraints (void)
7104 struct scc_info *si;
7106 /* Sort varinfos so that ones that cannot be pointed to are last.
7107 This makes bitmaps more efficient. */
7108 unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
7109 for (unsigned i = 0; i < integer_id + 1; ++i)
7110 map[i] = i;
7111 /* Start with non-register vars (as possibly address-taken), followed
7112 by register vars as conservative set of vars never appearing in
7113 the points-to solution bitmaps. */
7114 unsigned j = integer_id + 1;
7115 for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
7116 if (! varmap[i]->is_reg_var)
7117 map[i] = j++;
7118 for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
7119 if (varmap[i]->is_reg_var)
7120 map[i] = j++;
7121 /* Shuffle varmap according to map. */
7122 for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
7124 while (map[varmap[i]->id] != i)
7125 std::swap (varmap[i], varmap[map[varmap[i]->id]]);
7126 gcc_assert (bitmap_empty_p (varmap[i]->solution));
7127 varmap[i]->id = i;
7128 varmap[i]->next = map[varmap[i]->next];
7129 varmap[i]->head = map[varmap[i]->head];
7131 /* Finally rewrite constraints. */
7132 for (unsigned i = 0; i < constraints.length (); ++i)
7134 constraints[i]->lhs.var = map[constraints[i]->lhs.var];
7135 constraints[i]->rhs.var = map[constraints[i]->rhs.var];
7137 free (map);
7139 if (dump_file)
7140 fprintf (dump_file,
7141 "\nCollapsing static cycles and doing variable "
7142 "substitution\n");
7144 init_graph (varmap.length () * 2);
7146 if (dump_file)
7147 fprintf (dump_file, "Building predecessor graph\n");
7148 build_pred_graph ();
7150 if (dump_file)
7151 fprintf (dump_file, "Detecting pointer and location "
7152 "equivalences\n");
7153 si = perform_var_substitution (graph);
7155 if (dump_file)
7156 fprintf (dump_file, "Rewriting constraints and unifying "
7157 "variables\n");
7158 rewrite_constraints (graph, si);
7160 build_succ_graph ();
7162 free_var_substitution_info (si);
7164 /* Attach complex constraints to graph nodes. */
7165 move_complex_constraints (graph);
7167 if (dump_file)
7168 fprintf (dump_file, "Uniting pointer but not location equivalent "
7169 "variables\n");
7170 unite_pointer_equivalences (graph);
7172 if (dump_file)
7173 fprintf (dump_file, "Finding indirect cycles\n");
7174 find_indirect_cycles (graph);
7176 /* Implicit nodes and predecessors are no longer necessary at this
7177 point. */
7178 remove_preds_and_fake_succs (graph);
7180 if (dump_file && (dump_flags & TDF_GRAPH))
7182 fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
7183 "in dot format:\n");
7184 dump_constraint_graph (dump_file);
7185 fprintf (dump_file, "\n\n");
7188 if (dump_file)
7189 fprintf (dump_file, "Solving graph\n");
7191 solve_graph (graph);
7193 if (dump_file && (dump_flags & TDF_GRAPH))
7195 fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
7196 "in dot format:\n");
7197 dump_constraint_graph (dump_file);
7198 fprintf (dump_file, "\n\n");
7201 if (dump_file)
7202 dump_sa_points_to_info (dump_file);
7205 /* Create points-to sets for the current function. See the comments
7206 at the start of the file for an algorithmic overview. */
7208 static void
7209 compute_points_to_sets (void)
7211 basic_block bb;
7212 varinfo_t vi;
7214 timevar_push (TV_TREE_PTA);
7216 init_alias_vars ();
7218 intra_create_variable_infos (cfun);
7220 /* Now walk all statements and build the constraint set. */
7221 FOR_EACH_BB_FN (bb, cfun)
7223 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
7224 gsi_next (&gsi))
7226 gphi *phi = gsi.phi ();
7228 if (! virtual_operand_p (gimple_phi_result (phi)))
7229 find_func_aliases (cfun, phi);
7232 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
7233 gsi_next (&gsi))
7235 gimple *stmt = gsi_stmt (gsi);
7237 find_func_aliases (cfun, stmt);
7241 if (dump_file)
7243 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
7244 dump_constraints (dump_file, 0);
7247 /* From the constraints compute the points-to sets. */
7248 solve_constraints ();
7250 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
7251 cfun->gimple_df->escaped = find_what_var_points_to (cfun->decl,
7252 get_varinfo (escaped_id));
7254 /* Make sure the ESCAPED solution (which is used as placeholder in
7255 other solutions) does not reference itself. This simplifies
7256 points-to solution queries. */
7257 cfun->gimple_df->escaped.escaped = 0;
7259 /* Compute the points-to sets for pointer SSA_NAMEs. */
7260 unsigned i;
7261 tree ptr;
7263 FOR_EACH_SSA_NAME (i, ptr, cfun)
7265 if (POINTER_TYPE_P (TREE_TYPE (ptr)))
7266 find_what_p_points_to (cfun->decl, ptr);
7269 /* Compute the call-used/clobbered sets. */
7270 FOR_EACH_BB_FN (bb, cfun)
7272 gimple_stmt_iterator gsi;
7274 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
7276 gcall *stmt;
7277 struct pt_solution *pt;
7279 stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
7280 if (!stmt)
7281 continue;
7283 pt = gimple_call_use_set (stmt);
7284 if (gimple_call_flags (stmt) & ECF_CONST)
7285 memset (pt, 0, sizeof (struct pt_solution));
7286 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
7288 *pt = find_what_var_points_to (cfun->decl, vi);
7289 /* Escaped (and thus nonlocal) variables are always
7290 implicitly used by calls. */
7291 /* ??? ESCAPED can be empty even though NONLOCAL
7292 always escaped. */
7293 pt->nonlocal = 1;
7294 pt->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 = cfun->gimple_df->escaped;
7301 pt->nonlocal = 1;
7304 pt = gimple_call_clobber_set (stmt);
7305 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
7306 memset (pt, 0, sizeof (struct pt_solution));
7307 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
7309 *pt = find_what_var_points_to (cfun->decl, vi);
7310 /* Escaped (and thus nonlocal) variables are always
7311 implicitly clobbered by calls. */
7312 /* ??? ESCAPED can be empty even though NONLOCAL
7313 always escaped. */
7314 pt->nonlocal = 1;
7315 pt->escaped = 1;
7317 else
7319 /* If there is nothing special about this call then
7320 we have made everything that is used also escape. */
7321 *pt = cfun->gimple_df->escaped;
7322 pt->nonlocal = 1;
7327 timevar_pop (TV_TREE_PTA);
7331 /* Delete created points-to sets. */
7333 static void
7334 delete_points_to_sets (void)
7336 unsigned int i;
7338 delete shared_bitmap_table;
7339 shared_bitmap_table = NULL;
7340 if (dump_file && (dump_flags & TDF_STATS))
7341 fprintf (dump_file, "Points to sets created:%d\n",
7342 stats.points_to_sets_created);
7344 delete vi_for_tree;
7345 delete call_stmt_vars;
7346 bitmap_obstack_release (&pta_obstack);
7347 constraints.release ();
7349 for (i = 0; i < graph->size; i++)
7350 graph->complex[i].release ();
7351 free (graph->complex);
7353 free (graph->rep);
7354 free (graph->succs);
7355 free (graph->pe);
7356 free (graph->pe_rep);
7357 free (graph->indirect_cycles);
7358 free (graph);
7360 varmap.release ();
7361 variable_info_pool.release ();
7362 constraint_pool.release ();
7364 obstack_free (&fake_var_decl_obstack, NULL);
7366 delete final_solutions;
7367 obstack_free (&final_solutions_obstack, NULL);
7370 struct vls_data
7372 unsigned short clique;
7373 bitmap rvars;
7376 /* Mark "other" loads and stores as belonging to CLIQUE and with
7377 base zero. */
7379 static bool
7380 visit_loadstore (gimple *, tree base, tree ref, void *data)
7382 unsigned short clique = ((vls_data *) data)->clique;
7383 bitmap rvars = ((vls_data *) data)->rvars;
7384 if (TREE_CODE (base) == MEM_REF
7385 || TREE_CODE (base) == TARGET_MEM_REF)
7387 tree ptr = TREE_OPERAND (base, 0);
7388 if (TREE_CODE (ptr) == SSA_NAME)
7390 /* For parameters, get at the points-to set for the actual parm
7391 decl. */
7392 if (SSA_NAME_IS_DEFAULT_DEF (ptr)
7393 && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
7394 || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
7395 ptr = SSA_NAME_VAR (ptr);
7397 /* We need to make sure 'ptr' doesn't include any of
7398 the restrict tags we added bases for in its points-to set. */
7399 varinfo_t vi = lookup_vi_for_tree (ptr);
7400 if (! vi)
7401 return false;
7403 vi = get_varinfo (find (vi->id));
7404 if (bitmap_intersect_p (rvars, vi->solution))
7405 return false;
7408 /* Do not overwrite existing cliques (that includes clique, base
7409 pairs we just set). */
7410 if (MR_DEPENDENCE_CLIQUE (base) == 0)
7412 MR_DEPENDENCE_CLIQUE (base) = clique;
7413 MR_DEPENDENCE_BASE (base) = 0;
7417 /* For plain decl accesses see whether they are accesses to globals
7418 and rewrite them to MEM_REFs with { clique, 0 }. */
7419 if (VAR_P (base)
7420 && is_global_var (base)
7421 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
7422 ops callback. */
7423 && base != ref)
7425 tree *basep = &ref;
7426 while (handled_component_p (*basep))
7427 basep = &TREE_OPERAND (*basep, 0);
7428 gcc_assert (VAR_P (*basep));
7429 tree ptr = build_fold_addr_expr (*basep);
7430 tree zero = build_int_cst (TREE_TYPE (ptr), 0);
7431 *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero);
7432 MR_DEPENDENCE_CLIQUE (*basep) = clique;
7433 MR_DEPENDENCE_BASE (*basep) = 0;
7436 return false;
7439 /* If REF is a MEM_REF then assign a clique, base pair to it, updating
7440 CLIQUE, *RESTRICT_VAR and LAST_RUID. Return whether dependence info
7441 was assigned to REF. */
7443 static bool
7444 maybe_set_dependence_info (tree ref, tree ptr,
7445 unsigned short &clique, varinfo_t restrict_var,
7446 unsigned short &last_ruid)
7448 while (handled_component_p (ref))
7449 ref = TREE_OPERAND (ref, 0);
7450 if ((TREE_CODE (ref) == MEM_REF
7451 || TREE_CODE (ref) == TARGET_MEM_REF)
7452 && TREE_OPERAND (ref, 0) == ptr)
7454 /* Do not overwrite existing cliques. This avoids overwriting dependence
7455 info inlined from a function with restrict parameters inlined
7456 into a function with restrict parameters. This usually means we
7457 prefer to be precise in innermost loops. */
7458 if (MR_DEPENDENCE_CLIQUE (ref) == 0)
7460 if (clique == 0)
7461 clique = ++cfun->last_clique;
7462 if (restrict_var->ruid == 0)
7463 restrict_var->ruid = ++last_ruid;
7464 MR_DEPENDENCE_CLIQUE (ref) = clique;
7465 MR_DEPENDENCE_BASE (ref) = restrict_var->ruid;
7466 return true;
7469 return false;
7472 /* Compute the set of independend memory references based on restrict
7473 tags and their conservative propagation to the points-to sets. */
7475 static void
7476 compute_dependence_clique (void)
7478 unsigned short clique = 0;
7479 unsigned short last_ruid = 0;
7480 bitmap rvars = BITMAP_ALLOC (NULL);
7481 for (unsigned i = 0; i < num_ssa_names; ++i)
7483 tree ptr = ssa_name (i);
7484 if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr)))
7485 continue;
7487 /* Avoid all this when ptr is not dereferenced? */
7488 tree p = ptr;
7489 if (SSA_NAME_IS_DEFAULT_DEF (ptr)
7490 && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
7491 || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
7492 p = SSA_NAME_VAR (ptr);
7493 varinfo_t vi = lookup_vi_for_tree (p);
7494 if (!vi)
7495 continue;
7496 vi = get_varinfo (find (vi->id));
7497 bitmap_iterator bi;
7498 unsigned j;
7499 varinfo_t restrict_var = NULL;
7500 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
7502 varinfo_t oi = get_varinfo (j);
7503 if (oi->is_restrict_var)
7505 if (restrict_var)
7507 if (dump_file && (dump_flags & TDF_DETAILS))
7509 fprintf (dump_file, "found restrict pointed-to "
7510 "for ");
7511 print_generic_expr (dump_file, ptr);
7512 fprintf (dump_file, " but not exclusively\n");
7514 restrict_var = NULL;
7515 break;
7517 restrict_var = oi;
7519 /* NULL is the only other valid points-to entry. */
7520 else if (oi->id != nothing_id)
7522 restrict_var = NULL;
7523 break;
7526 /* Ok, found that ptr must(!) point to a single(!) restrict
7527 variable. */
7528 /* ??? PTA isn't really a proper propagation engine to compute
7529 this property.
7530 ??? We could handle merging of two restricts by unifying them. */
7531 if (restrict_var)
7533 /* Now look at possible dereferences of ptr. */
7534 imm_use_iterator ui;
7535 gimple *use_stmt;
7536 bool used = false;
7537 FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
7539 /* ??? Calls and asms. */
7540 if (!gimple_assign_single_p (use_stmt))
7541 continue;
7542 used |= maybe_set_dependence_info (gimple_assign_lhs (use_stmt),
7543 ptr, clique, restrict_var,
7544 last_ruid);
7545 used |= maybe_set_dependence_info (gimple_assign_rhs1 (use_stmt),
7546 ptr, clique, restrict_var,
7547 last_ruid);
7549 if (used)
7550 bitmap_set_bit (rvars, restrict_var->id);
7554 if (clique != 0)
7556 /* Assign the BASE id zero to all accesses not based on a restrict
7557 pointer. That way they get disambiguated against restrict
7558 accesses but not against each other. */
7559 /* ??? For restricts derived from globals (thus not incoming
7560 parameters) we can't restrict scoping properly thus the following
7561 is too aggressive there. For now we have excluded those globals from
7562 getting into the MR_DEPENDENCE machinery. */
7563 vls_data data = { clique, rvars };
7564 basic_block bb;
7565 FOR_EACH_BB_FN (bb, cfun)
7566 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
7567 !gsi_end_p (gsi); gsi_next (&gsi))
7569 gimple *stmt = gsi_stmt (gsi);
7570 walk_stmt_load_store_ops (stmt, &data,
7571 visit_loadstore, visit_loadstore);
7575 BITMAP_FREE (rvars);
7578 /* Compute points-to information for every SSA_NAME pointer in the
7579 current function and compute the transitive closure of escaped
7580 variables to re-initialize the call-clobber states of local variables. */
7582 unsigned int
7583 compute_may_aliases (void)
7585 if (cfun->gimple_df->ipa_pta)
7587 if (dump_file)
7589 fprintf (dump_file, "\nNot re-computing points-to information "
7590 "because IPA points-to information is available.\n\n");
7592 /* But still dump what we have remaining it. */
7593 dump_alias_info (dump_file);
7596 return 0;
7599 /* For each pointer P_i, determine the sets of variables that P_i may
7600 point-to. Compute the reachability set of escaped and call-used
7601 variables. */
7602 compute_points_to_sets ();
7604 /* Debugging dumps. */
7605 if (dump_file)
7606 dump_alias_info (dump_file);
7608 /* Compute restrict-based memory disambiguations. */
7609 compute_dependence_clique ();
7611 /* Deallocate memory used by aliasing data structures and the internal
7612 points-to solution. */
7613 delete_points_to_sets ();
7615 gcc_assert (!need_ssa_update_p (cfun));
7617 return 0;
7620 /* A dummy pass to cause points-to information to be computed via
7621 TODO_rebuild_alias. */
7623 namespace {
7625 const pass_data pass_data_build_alias =
7627 GIMPLE_PASS, /* type */
7628 "alias", /* name */
7629 OPTGROUP_NONE, /* optinfo_flags */
7630 TV_NONE, /* tv_id */
7631 ( PROP_cfg | PROP_ssa ), /* properties_required */
7632 0, /* properties_provided */
7633 0, /* properties_destroyed */
7634 0, /* todo_flags_start */
7635 TODO_rebuild_alias, /* todo_flags_finish */
7638 class pass_build_alias : public gimple_opt_pass
7640 public:
7641 pass_build_alias (gcc::context *ctxt)
7642 : gimple_opt_pass (pass_data_build_alias, ctxt)
7645 /* opt_pass methods: */
7646 virtual bool gate (function *) { return flag_tree_pta; }
7648 }; // class pass_build_alias
7650 } // anon namespace
7652 gimple_opt_pass *
7653 make_pass_build_alias (gcc::context *ctxt)
7655 return new pass_build_alias (ctxt);
7658 /* A dummy pass to cause points-to information to be computed via
7659 TODO_rebuild_alias. */
7661 namespace {
7663 const pass_data pass_data_build_ealias =
7665 GIMPLE_PASS, /* type */
7666 "ealias", /* name */
7667 OPTGROUP_NONE, /* optinfo_flags */
7668 TV_NONE, /* tv_id */
7669 ( PROP_cfg | PROP_ssa ), /* properties_required */
7670 0, /* properties_provided */
7671 0, /* properties_destroyed */
7672 0, /* todo_flags_start */
7673 TODO_rebuild_alias, /* todo_flags_finish */
7676 class pass_build_ealias : public gimple_opt_pass
7678 public:
7679 pass_build_ealias (gcc::context *ctxt)
7680 : gimple_opt_pass (pass_data_build_ealias, ctxt)
7683 /* opt_pass methods: */
7684 virtual bool gate (function *) { return flag_tree_pta; }
7686 }; // class pass_build_ealias
7688 } // anon namespace
7690 gimple_opt_pass *
7691 make_pass_build_ealias (gcc::context *ctxt)
7693 return new pass_build_ealias (ctxt);
7697 /* IPA PTA solutions for ESCAPED. */
7698 struct pt_solution ipa_escaped_pt
7699 = { true, false, false, false, false,
7700 false, false, false, false, false, NULL };
7702 /* Associate node with varinfo DATA. Worker for
7703 cgraph_for_symbol_thunks_and_aliases. */
7704 static bool
7705 associate_varinfo_to_alias (struct cgraph_node *node, void *data)
7707 if ((node->alias
7708 || (node->thunk.thunk_p
7709 && ! node->global.inlined_to))
7710 && node->analyzed)
7711 insert_vi_for_tree (node->decl, (varinfo_t)data);
7712 return false;
7715 /* Dump varinfo VI to FILE. */
7717 static void
7718 dump_varinfo (FILE *file, varinfo_t vi)
7720 if (vi == NULL)
7721 return;
7723 fprintf (file, "%u: %s\n", vi->id, vi->name);
7725 const char *sep = " ";
7726 if (vi->is_artificial_var)
7727 fprintf (file, "%sartificial", sep);
7728 if (vi->is_special_var)
7729 fprintf (file, "%sspecial", sep);
7730 if (vi->is_unknown_size_var)
7731 fprintf (file, "%sunknown-size", sep);
7732 if (vi->is_full_var)
7733 fprintf (file, "%sfull", sep);
7734 if (vi->is_heap_var)
7735 fprintf (file, "%sheap", sep);
7736 if (vi->may_have_pointers)
7737 fprintf (file, "%smay-have-pointers", sep);
7738 if (vi->only_restrict_pointers)
7739 fprintf (file, "%sonly-restrict-pointers", sep);
7740 if (vi->is_restrict_var)
7741 fprintf (file, "%sis-restrict-var", sep);
7742 if (vi->is_global_var)
7743 fprintf (file, "%sglobal", sep);
7744 if (vi->is_ipa_escape_point)
7745 fprintf (file, "%sipa-escape-point", sep);
7746 if (vi->is_fn_info)
7747 fprintf (file, "%sfn-info", sep);
7748 if (vi->ruid)
7749 fprintf (file, "%srestrict-uid:%u", sep, vi->ruid);
7750 if (vi->next)
7751 fprintf (file, "%snext:%u", sep, vi->next);
7752 if (vi->head != vi->id)
7753 fprintf (file, "%shead:%u", sep, vi->head);
7754 if (vi->offset)
7755 fprintf (file, "%soffset:" HOST_WIDE_INT_PRINT_DEC, sep, vi->offset);
7756 if (vi->size != ~(unsigned HOST_WIDE_INT)0)
7757 fprintf (file, "%ssize:" HOST_WIDE_INT_PRINT_DEC, sep, vi->size);
7758 if (vi->fullsize != ~(unsigned HOST_WIDE_INT)0
7759 && vi->fullsize != vi->size)
7760 fprintf (file, "%sfullsize:" HOST_WIDE_INT_PRINT_DEC, sep,
7761 vi->fullsize);
7762 fprintf (file, "\n");
7764 if (vi->solution && !bitmap_empty_p (vi->solution))
7766 bitmap_iterator bi;
7767 unsigned i;
7768 fprintf (file, " solution: {");
7769 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
7770 fprintf (file, " %u", i);
7771 fprintf (file, " }\n");
7774 if (vi->oldsolution && !bitmap_empty_p (vi->oldsolution)
7775 && !bitmap_equal_p (vi->solution, vi->oldsolution))
7777 bitmap_iterator bi;
7778 unsigned i;
7779 fprintf (file, " oldsolution: {");
7780 EXECUTE_IF_SET_IN_BITMAP (vi->oldsolution, 0, i, bi)
7781 fprintf (file, " %u", i);
7782 fprintf (file, " }\n");
7786 /* Dump varinfo VI to stderr. */
7788 DEBUG_FUNCTION void
7789 debug_varinfo (varinfo_t vi)
7791 dump_varinfo (stderr, vi);
7794 /* Dump varmap to FILE. */
7796 static void
7797 dump_varmap (FILE *file)
7799 if (varmap.length () == 0)
7800 return;
7802 fprintf (file, "variables:\n");
7804 for (unsigned int i = 0; i < varmap.length (); ++i)
7806 varinfo_t vi = get_varinfo (i);
7807 dump_varinfo (file, vi);
7810 fprintf (file, "\n");
7813 /* Dump varmap to stderr. */
7815 DEBUG_FUNCTION void
7816 debug_varmap (void)
7818 dump_varmap (stderr);
7821 /* Compute whether node is refered to non-locally. Worker for
7822 cgraph_for_symbol_thunks_and_aliases. */
7823 static bool
7824 refered_from_nonlocal_fn (struct cgraph_node *node, void *data)
7826 bool *nonlocal_p = (bool *)data;
7827 *nonlocal_p |= (node->used_from_other_partition
7828 || node->externally_visible
7829 || node->force_output
7830 || lookup_attribute ("noipa", DECL_ATTRIBUTES (node->decl)));
7831 return false;
7834 /* Same for varpool nodes. */
7835 static bool
7836 refered_from_nonlocal_var (struct varpool_node *node, void *data)
7838 bool *nonlocal_p = (bool *)data;
7839 *nonlocal_p |= (node->used_from_other_partition
7840 || node->externally_visible
7841 || node->force_output);
7842 return false;
7845 /* Execute the driver for IPA PTA. */
7846 static unsigned int
7847 ipa_pta_execute (void)
7849 struct cgraph_node *node;
7850 varpool_node *var;
7851 unsigned int from = 0;
7853 in_ipa_mode = 1;
7855 init_alias_vars ();
7857 if (dump_file && (dump_flags & TDF_DETAILS))
7859 symtab->dump (dump_file);
7860 fprintf (dump_file, "\n");
7863 if (dump_file)
7865 fprintf (dump_file, "Generating generic constraints\n\n");
7866 dump_constraints (dump_file, from);
7867 fprintf (dump_file, "\n");
7868 from = constraints.length ();
7871 /* Build the constraints. */
7872 FOR_EACH_DEFINED_FUNCTION (node)
7874 varinfo_t vi;
7875 /* Nodes without a body are not interesting. Especially do not
7876 visit clones at this point for now - we get duplicate decls
7877 there for inline clones at least. */
7878 if (!node->has_gimple_body_p () || node->global.inlined_to)
7879 continue;
7880 node->get_body ();
7882 gcc_assert (!node->clone_of);
7884 /* For externally visible or attribute used annotated functions use
7885 local constraints for their arguments.
7886 For local functions we see all callers and thus do not need initial
7887 constraints for parameters. */
7888 bool nonlocal_p = (node->used_from_other_partition
7889 || node->externally_visible
7890 || node->force_output
7891 || lookup_attribute ("noipa",
7892 DECL_ATTRIBUTES (node->decl)));
7893 node->call_for_symbol_thunks_and_aliases (refered_from_nonlocal_fn,
7894 &nonlocal_p, true);
7896 vi = create_function_info_for (node->decl,
7897 alias_get_name (node->decl), false,
7898 nonlocal_p);
7899 if (dump_file
7900 && from != constraints.length ())
7902 fprintf (dump_file,
7903 "Generating intial constraints for %s", node->name ());
7904 if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
7905 fprintf (dump_file, " (%s)",
7906 IDENTIFIER_POINTER
7907 (DECL_ASSEMBLER_NAME (node->decl)));
7908 fprintf (dump_file, "\n\n");
7909 dump_constraints (dump_file, from);
7910 fprintf (dump_file, "\n");
7912 from = constraints.length ();
7915 node->call_for_symbol_thunks_and_aliases
7916 (associate_varinfo_to_alias, vi, true);
7919 /* Create constraints for global variables and their initializers. */
7920 FOR_EACH_VARIABLE (var)
7922 if (var->alias && var->analyzed)
7923 continue;
7925 varinfo_t vi = get_vi_for_tree (var->decl);
7927 /* For the purpose of IPA PTA unit-local globals are not
7928 escape points. */
7929 bool nonlocal_p = (var->used_from_other_partition
7930 || var->externally_visible
7931 || var->force_output);
7932 var->call_for_symbol_and_aliases (refered_from_nonlocal_var,
7933 &nonlocal_p, true);
7934 if (nonlocal_p)
7935 vi->is_ipa_escape_point = true;
7938 if (dump_file
7939 && from != constraints.length ())
7941 fprintf (dump_file,
7942 "Generating constraints for global initializers\n\n");
7943 dump_constraints (dump_file, from);
7944 fprintf (dump_file, "\n");
7945 from = constraints.length ();
7948 FOR_EACH_DEFINED_FUNCTION (node)
7950 struct function *func;
7951 basic_block bb;
7953 /* Nodes without a body are not interesting. */
7954 if (!node->has_gimple_body_p () || node->clone_of)
7955 continue;
7957 if (dump_file)
7959 fprintf (dump_file,
7960 "Generating constraints for %s", node->name ());
7961 if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
7962 fprintf (dump_file, " (%s)",
7963 IDENTIFIER_POINTER
7964 (DECL_ASSEMBLER_NAME (node->decl)));
7965 fprintf (dump_file, "\n");
7968 func = DECL_STRUCT_FUNCTION (node->decl);
7969 gcc_assert (cfun == NULL);
7971 /* Build constriants for the function body. */
7972 FOR_EACH_BB_FN (bb, func)
7974 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
7975 gsi_next (&gsi))
7977 gphi *phi = gsi.phi ();
7979 if (! virtual_operand_p (gimple_phi_result (phi)))
7980 find_func_aliases (func, phi);
7983 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
7984 gsi_next (&gsi))
7986 gimple *stmt = gsi_stmt (gsi);
7988 find_func_aliases (func, stmt);
7989 find_func_clobbers (func, stmt);
7993 if (dump_file)
7995 fprintf (dump_file, "\n");
7996 dump_constraints (dump_file, from);
7997 fprintf (dump_file, "\n");
7998 from = constraints.length ();
8002 /* From the constraints compute the points-to sets. */
8003 solve_constraints ();
8005 /* Compute the global points-to sets for ESCAPED.
8006 ??? Note that the computed escape set is not correct
8007 for the whole unit as we fail to consider graph edges to
8008 externally visible functions. */
8009 ipa_escaped_pt = find_what_var_points_to (NULL, get_varinfo (escaped_id));
8011 /* Make sure the ESCAPED solution (which is used as placeholder in
8012 other solutions) does not reference itself. This simplifies
8013 points-to solution queries. */
8014 ipa_escaped_pt.ipa_escaped = 0;
8016 /* Assign the points-to sets to the SSA names in the unit. */
8017 FOR_EACH_DEFINED_FUNCTION (node)
8019 tree ptr;
8020 struct function *fn;
8021 unsigned i;
8022 basic_block bb;
8024 /* Nodes without a body are not interesting. */
8025 if (!node->has_gimple_body_p () || node->clone_of)
8026 continue;
8028 fn = DECL_STRUCT_FUNCTION (node->decl);
8030 /* Compute the points-to sets for pointer SSA_NAMEs. */
8031 FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
8033 if (ptr
8034 && POINTER_TYPE_P (TREE_TYPE (ptr)))
8035 find_what_p_points_to (node->decl, ptr);
8038 /* Compute the call-use and call-clobber sets for indirect calls
8039 and calls to external functions. */
8040 FOR_EACH_BB_FN (bb, fn)
8042 gimple_stmt_iterator gsi;
8044 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
8046 gcall *stmt;
8047 struct pt_solution *pt;
8048 varinfo_t vi, fi;
8049 tree decl;
8051 stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
8052 if (!stmt)
8053 continue;
8055 /* Handle direct calls to functions with body. */
8056 decl = gimple_call_fndecl (stmt);
8059 tree called_decl = NULL_TREE;
8060 if (gimple_call_builtin_p (stmt, BUILT_IN_GOMP_PARALLEL))
8061 called_decl = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
8062 else if (gimple_call_builtin_p (stmt, BUILT_IN_GOACC_PARALLEL))
8063 called_decl = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
8065 if (called_decl != NULL_TREE
8066 && !fndecl_maybe_in_other_partition (called_decl))
8067 decl = called_decl;
8070 if (decl
8071 && (fi = lookup_vi_for_tree (decl))
8072 && fi->is_fn_info)
8074 *gimple_call_clobber_set (stmt)
8075 = find_what_var_points_to
8076 (node->decl, first_vi_for_offset (fi, fi_clobbers));
8077 *gimple_call_use_set (stmt)
8078 = find_what_var_points_to
8079 (node->decl, first_vi_for_offset (fi, fi_uses));
8081 /* Handle direct calls to external functions. */
8082 else if (decl)
8084 pt = gimple_call_use_set (stmt);
8085 if (gimple_call_flags (stmt) & ECF_CONST)
8086 memset (pt, 0, sizeof (struct pt_solution));
8087 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
8089 *pt = find_what_var_points_to (node->decl, vi);
8090 /* Escaped (and thus nonlocal) variables are always
8091 implicitly used by calls. */
8092 /* ??? ESCAPED can be empty even though NONLOCAL
8093 always escaped. */
8094 pt->nonlocal = 1;
8095 pt->ipa_escaped = 1;
8097 else
8099 /* If there is nothing special about this call then
8100 we have made everything that is used also escape. */
8101 *pt = ipa_escaped_pt;
8102 pt->nonlocal = 1;
8105 pt = gimple_call_clobber_set (stmt);
8106 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
8107 memset (pt, 0, sizeof (struct pt_solution));
8108 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
8110 *pt = find_what_var_points_to (node->decl, vi);
8111 /* Escaped (and thus nonlocal) variables are always
8112 implicitly clobbered by calls. */
8113 /* ??? ESCAPED can be empty even though NONLOCAL
8114 always escaped. */
8115 pt->nonlocal = 1;
8116 pt->ipa_escaped = 1;
8118 else
8120 /* If there is nothing special about this call then
8121 we have made everything that is used also escape. */
8122 *pt = ipa_escaped_pt;
8123 pt->nonlocal = 1;
8126 /* Handle indirect calls. */
8127 else if (!decl
8128 && (fi = get_fi_for_callee (stmt)))
8130 /* We need to accumulate all clobbers/uses of all possible
8131 callees. */
8132 fi = get_varinfo (find (fi->id));
8133 /* If we cannot constrain the set of functions we'll end up
8134 calling we end up using/clobbering everything. */
8135 if (bitmap_bit_p (fi->solution, anything_id)
8136 || bitmap_bit_p (fi->solution, nonlocal_id)
8137 || bitmap_bit_p (fi->solution, escaped_id))
8139 pt_solution_reset (gimple_call_clobber_set (stmt));
8140 pt_solution_reset (gimple_call_use_set (stmt));
8142 else
8144 bitmap_iterator bi;
8145 unsigned i;
8146 struct pt_solution *uses, *clobbers;
8148 uses = gimple_call_use_set (stmt);
8149 clobbers = gimple_call_clobber_set (stmt);
8150 memset (uses, 0, sizeof (struct pt_solution));
8151 memset (clobbers, 0, sizeof (struct pt_solution));
8152 EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
8154 struct pt_solution sol;
8156 vi = get_varinfo (i);
8157 if (!vi->is_fn_info)
8159 /* ??? We could be more precise here? */
8160 uses->nonlocal = 1;
8161 uses->ipa_escaped = 1;
8162 clobbers->nonlocal = 1;
8163 clobbers->ipa_escaped = 1;
8164 continue;
8167 if (!uses->anything)
8169 sol = find_what_var_points_to
8170 (node->decl,
8171 first_vi_for_offset (vi, fi_uses));
8172 pt_solution_ior_into (uses, &sol);
8174 if (!clobbers->anything)
8176 sol = find_what_var_points_to
8177 (node->decl,
8178 first_vi_for_offset (vi, fi_clobbers));
8179 pt_solution_ior_into (clobbers, &sol);
8187 fn->gimple_df->ipa_pta = true;
8189 /* We have to re-set the final-solution cache after each function
8190 because what is a "global" is dependent on function context. */
8191 final_solutions->empty ();
8192 obstack_free (&final_solutions_obstack, NULL);
8193 gcc_obstack_init (&final_solutions_obstack);
8196 delete_points_to_sets ();
8198 in_ipa_mode = 0;
8200 return 0;
8203 namespace {
8205 const pass_data pass_data_ipa_pta =
8207 SIMPLE_IPA_PASS, /* type */
8208 "pta", /* name */
8209 OPTGROUP_NONE, /* optinfo_flags */
8210 TV_IPA_PTA, /* tv_id */
8211 0, /* properties_required */
8212 0, /* properties_provided */
8213 0, /* properties_destroyed */
8214 0, /* todo_flags_start */
8215 0, /* todo_flags_finish */
8218 class pass_ipa_pta : public simple_ipa_opt_pass
8220 public:
8221 pass_ipa_pta (gcc::context *ctxt)
8222 : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
8225 /* opt_pass methods: */
8226 virtual bool gate (function *)
8228 return (optimize
8229 && flag_ipa_pta
8230 /* Don't bother doing anything if the program has errors. */
8231 && !seen_error ());
8234 opt_pass * clone () { return new pass_ipa_pta (m_ctxt); }
8236 virtual unsigned int execute (function *) { return ipa_pta_execute (); }
8238 }; // class pass_ipa_pta
8240 } // anon namespace
8242 simple_ipa_opt_pass *
8243 make_pass_ipa_pta (gcc::context *ctxt)
8245 return new pass_ipa_pta (ctxt);