remove need for store_values_directly
[official-gcc.git] / gcc / tree-ssa-structalias.c
blobd6a9f678259d569ef1d0780795dbb3181f29a2aa
1 /* Tree based points-to analysis
2 Copyright (C) 2005-2015 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "obstack.h"
26 #include "bitmap.h"
27 #include "sbitmap.h"
28 #include "flags.h"
29 #include "predict.h"
30 #include "vec.h"
31 #include "hashtab.h"
32 #include "hash-set.h"
33 #include "machmode.h"
34 #include "hard-reg-set.h"
35 #include "input.h"
36 #include "function.h"
37 #include "dominance.h"
38 #include "cfg.h"
39 #include "basic-block.h"
40 #include "double-int.h"
41 #include "alias.h"
42 #include "symtab.h"
43 #include "wide-int.h"
44 #include "inchash.h"
45 #include "tree.h"
46 #include "fold-const.h"
47 #include "stor-layout.h"
48 #include "stmt.h"
49 #include "hash-table.h"
50 #include "tree-ssa-alias.h"
51 #include "internal-fn.h"
52 #include "gimple-expr.h"
53 #include "is-a.h"
54 #include "gimple.h"
55 #include "gimple-iterator.h"
56 #include "gimple-ssa.h"
57 #include "hash-map.h"
58 #include "plugin-api.h"
59 #include "ipa-ref.h"
60 #include "cgraph.h"
61 #include "stringpool.h"
62 #include "tree-ssanames.h"
63 #include "tree-into-ssa.h"
64 #include "rtl.h"
65 #include "statistics.h"
66 #include "real.h"
67 #include "fixed-value.h"
68 #include "insn-config.h"
69 #include "expmed.h"
70 #include "dojump.h"
71 #include "explow.h"
72 #include "calls.h"
73 #include "emit-rtl.h"
74 #include "varasm.h"
75 #include "expr.h"
76 #include "tree-dfa.h"
77 #include "tree-inline.h"
78 #include "diagnostic-core.h"
79 #include "tree-pass.h"
80 #include "alloc-pool.h"
81 #include "splay-tree.h"
82 #include "params.h"
83 #include "tree-phinodes.h"
84 #include "ssa-iterators.h"
85 #include "tree-pretty-print.h"
86 #include "gimple-walk.h"
88 /* The idea behind this analyzer is to generate set constraints from the
89 program, then solve the resulting constraints in order to generate the
90 points-to sets.
92 Set constraints are a way of modeling program analysis problems that
93 involve sets. They consist of an inclusion constraint language,
94 describing the variables (each variable is a set) and operations that
95 are involved on the variables, and a set of rules that derive facts
96 from these operations. To solve a system of set constraints, you derive
97 all possible facts under the rules, which gives you the correct sets
98 as a consequence.
100 See "Efficient Field-sensitive pointer analysis for C" by "David
101 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
102 http://citeseer.ist.psu.edu/pearce04efficient.html
104 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
105 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
106 http://citeseer.ist.psu.edu/heintze01ultrafast.html
108 There are three types of real constraint expressions, DEREF,
109 ADDRESSOF, and SCALAR. Each constraint expression consists
110 of a constraint type, a variable, and an offset.
112 SCALAR is a constraint expression type used to represent x, whether
113 it appears on the LHS or the RHS of a statement.
114 DEREF is a constraint expression type used to represent *x, whether
115 it appears on the LHS or the RHS of a statement.
116 ADDRESSOF is a constraint expression used to represent &x, whether
117 it appears on the LHS or the RHS of a statement.
119 Each pointer variable in the program is assigned an integer id, and
120 each field of a structure variable is assigned an integer id as well.
122 Structure variables are linked to their list of fields through a "next
123 field" in each variable that points to the next field in offset
124 order.
125 Each variable for a structure field has
127 1. "size", that tells the size in bits of that field.
128 2. "fullsize, that tells the size in bits of the entire structure.
129 3. "offset", that tells the offset in bits from the beginning of the
130 structure to this field.
132 Thus,
133 struct f
135 int a;
136 int b;
137 } foo;
138 int *bar;
140 looks like
142 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
143 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
144 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
147 In order to solve the system of set constraints, the following is
148 done:
150 1. Each constraint variable x has a solution set associated with it,
151 Sol(x).
153 2. Constraints are separated into direct, copy, and complex.
154 Direct constraints are ADDRESSOF constraints that require no extra
155 processing, such as P = &Q
156 Copy constraints are those of the form P = Q.
157 Complex constraints are all the constraints involving dereferences
158 and offsets (including offsetted copies).
160 3. All direct constraints of the form P = &Q are processed, such
161 that Q is added to Sol(P)
163 4. All complex constraints for a given constraint variable are stored in a
164 linked list attached to that variable's node.
166 5. A directed graph is built out of the copy constraints. Each
167 constraint variable is a node in the graph, and an edge from
168 Q to P is added for each copy constraint of the form P = Q
170 6. The graph is then walked, and solution sets are
171 propagated along the copy edges, such that an edge from Q to P
172 causes Sol(P) <- Sol(P) union Sol(Q).
174 7. As we visit each node, all complex constraints associated with
175 that node are processed by adding appropriate copy edges to the graph, or the
176 appropriate variables to the solution set.
178 8. The process of walking the graph is iterated until no solution
179 sets change.
181 Prior to walking the graph in steps 6 and 7, We perform static
182 cycle elimination on the constraint graph, as well
183 as off-line variable substitution.
185 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
186 on and turned into anything), but isn't. You can just see what offset
187 inside the pointed-to struct it's going to access.
189 TODO: Constant bounded arrays can be handled as if they were structs of the
190 same number of elements.
192 TODO: Modeling heap and incoming pointers becomes much better if we
193 add fields to them as we discover them, which we could do.
195 TODO: We could handle unions, but to be honest, it's probably not
196 worth the pain or slowdown. */
198 /* IPA-PTA optimizations possible.
200 When the indirect function called is ANYTHING we can add disambiguation
201 based on the function signatures (or simply the parameter count which
202 is the varinfo size). We also do not need to consider functions that
203 do not have their address taken.
205 The is_global_var bit which marks escape points is overly conservative
206 in IPA mode. Split it to is_escape_point and is_global_var - only
207 externally visible globals are escape points in IPA mode. This is
208 also needed to fix the pt_solution_includes_global predicate
209 (and thus ptr_deref_may_alias_global_p).
211 The way we introduce DECL_PT_UID to avoid fixing up all points-to
212 sets in the translation unit when we copy a DECL during inlining
213 pessimizes precision. The advantage is that the DECL_PT_UID keeps
214 compile-time and memory usage overhead low - the points-to sets
215 do not grow or get unshared as they would during a fixup phase.
216 An alternative solution is to delay IPA PTA until after all
217 inlining transformations have been applied.
219 The way we propagate clobber/use information isn't optimized.
220 It should use a new complex constraint that properly filters
221 out local variables of the callee (though that would make
222 the sets invalid after inlining). OTOH we might as well
223 admit defeat to WHOPR and simply do all the clobber/use analysis
224 and propagation after PTA finished but before we threw away
225 points-to information for memory variables. WHOPR and PTA
226 do not play along well anyway - the whole constraint solving
227 would need to be done in WPA phase and it will be very interesting
228 to apply the results to local SSA names during LTRANS phase.
230 We probably should compute a per-function unit-ESCAPE solution
231 propagating it simply like the clobber / uses solutions. The
232 solution can go alongside the non-IPA espaced solution and be
233 used to query which vars escape the unit through a function.
235 We never put function decls in points-to sets so we do not
236 keep the set of called functions for indirect calls.
238 And probably more. */
240 static bool use_field_sensitive = true;
241 static int in_ipa_mode = 0;
243 /* Used for predecessor bitmaps. */
244 static bitmap_obstack predbitmap_obstack;
246 /* Used for points-to sets. */
247 static bitmap_obstack pta_obstack;
249 /* Used for oldsolution members of variables. */
250 static bitmap_obstack oldpta_obstack;
252 /* Used for per-solver-iteration bitmaps. */
253 static bitmap_obstack iteration_obstack;
255 static unsigned int create_variable_info_for (tree, const char *);
256 typedef struct constraint_graph *constraint_graph_t;
257 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
259 struct constraint;
260 typedef struct constraint *constraint_t;
263 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
264 if (a) \
265 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
267 static struct constraint_stats
269 unsigned int total_vars;
270 unsigned int nonpointer_vars;
271 unsigned int unified_vars_static;
272 unsigned int unified_vars_dynamic;
273 unsigned int iterations;
274 unsigned int num_edges;
275 unsigned int num_implicit_edges;
276 unsigned int points_to_sets_created;
277 } stats;
279 struct variable_info
281 /* ID of this variable */
282 unsigned int id;
284 /* True if this is a variable created by the constraint analysis, such as
285 heap variables and constraints we had to break up. */
286 unsigned int is_artificial_var : 1;
288 /* True if this is a special variable whose solution set should not be
289 changed. */
290 unsigned int is_special_var : 1;
292 /* True for variables whose size is not known or variable. */
293 unsigned int is_unknown_size_var : 1;
295 /* True for (sub-)fields that represent a whole variable. */
296 unsigned int is_full_var : 1;
298 /* True if this is a heap variable. */
299 unsigned int is_heap_var : 1;
301 /* True if this field may contain pointers. */
302 unsigned int may_have_pointers : 1;
304 /* True if this field has only restrict qualified pointers. */
305 unsigned int only_restrict_pointers : 1;
307 /* True if this represents a heap var created for a restrict qualified
308 pointer. */
309 unsigned int is_restrict_var : 1;
311 /* True if this represents a global variable. */
312 unsigned int is_global_var : 1;
314 /* True if this represents a IPA function info. */
315 unsigned int is_fn_info : 1;
317 /* ??? Store somewhere better. */
318 unsigned short ruid;
320 /* The ID of the variable for the next field in this structure
321 or zero for the last field in this structure. */
322 unsigned next;
324 /* The ID of the variable for the first field in this structure. */
325 unsigned head;
327 /* Offset of this variable, in bits, from the base variable */
328 unsigned HOST_WIDE_INT offset;
330 /* Size of the variable, in bits. */
331 unsigned HOST_WIDE_INT size;
333 /* Full size of the base variable, in bits. */
334 unsigned HOST_WIDE_INT fullsize;
336 /* Name of this variable */
337 const char *name;
339 /* Tree that this variable is associated with. */
340 tree decl;
342 /* Points-to set for this variable. */
343 bitmap solution;
345 /* Old points-to set for this variable. */
346 bitmap oldsolution;
348 typedef struct variable_info *varinfo_t;
350 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
351 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
352 unsigned HOST_WIDE_INT);
353 static varinfo_t lookup_vi_for_tree (tree);
354 static inline bool type_can_have_subvars (const_tree);
356 /* Pool of variable info structures. */
357 static alloc_pool variable_info_pool;
359 /* Map varinfo to final pt_solution. */
360 static hash_map<varinfo_t, pt_solution *> *final_solutions;
361 struct obstack final_solutions_obstack;
363 /* Table of variable info structures for constraint variables.
364 Indexed directly by variable info id. */
365 static vec<varinfo_t> varmap;
367 /* Return the varmap element N */
369 static inline varinfo_t
370 get_varinfo (unsigned int n)
372 return varmap[n];
375 /* Return the next variable in the list of sub-variables of VI
376 or NULL if VI is the last sub-variable. */
378 static inline varinfo_t
379 vi_next (varinfo_t vi)
381 return get_varinfo (vi->next);
384 /* Static IDs for the special variables. Variable ID zero is unused
385 and used as terminator for the sub-variable chain. */
386 enum { nothing_id = 1, anything_id = 2, string_id = 3,
387 escaped_id = 4, nonlocal_id = 5,
388 storedanything_id = 6, integer_id = 7 };
390 /* Return a new variable info structure consisting for a variable
391 named NAME, and using constraint graph node NODE. Append it
392 to the vector of variable info structures. */
394 static varinfo_t
395 new_var_info (tree t, const char *name)
397 unsigned index = varmap.length ();
398 varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
400 ret->id = index;
401 ret->name = name;
402 ret->decl = t;
403 /* Vars without decl are artificial and do not have sub-variables. */
404 ret->is_artificial_var = (t == NULL_TREE);
405 ret->is_special_var = false;
406 ret->is_unknown_size_var = false;
407 ret->is_full_var = (t == NULL_TREE);
408 ret->is_heap_var = false;
409 ret->may_have_pointers = true;
410 ret->only_restrict_pointers = false;
411 ret->is_restrict_var = false;
412 ret->ruid = 0;
413 ret->is_global_var = (t == NULL_TREE);
414 ret->is_fn_info = false;
415 if (t && DECL_P (t))
416 ret->is_global_var = (is_global_var (t)
417 /* We have to treat even local register variables
418 as escape points. */
419 || (TREE_CODE (t) == VAR_DECL
420 && DECL_HARD_REGISTER (t)));
421 ret->solution = BITMAP_ALLOC (&pta_obstack);
422 ret->oldsolution = NULL;
423 ret->next = 0;
424 ret->head = ret->id;
426 stats.total_vars++;
428 varmap.safe_push (ret);
430 return ret;
434 /* A map mapping call statements to per-stmt variables for uses
435 and clobbers specific to the call. */
436 static hash_map<gimple, varinfo_t> *call_stmt_vars;
438 /* Lookup or create the variable for the call statement CALL. */
440 static varinfo_t
441 get_call_vi (gcall *call)
443 varinfo_t vi, vi2;
445 bool existed;
446 varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed);
447 if (existed)
448 return *slot_p;
450 vi = new_var_info (NULL_TREE, "CALLUSED");
451 vi->offset = 0;
452 vi->size = 1;
453 vi->fullsize = 2;
454 vi->is_full_var = true;
456 vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
457 vi2->offset = 1;
458 vi2->size = 1;
459 vi2->fullsize = 2;
460 vi2->is_full_var = true;
462 vi->next = vi2->id;
464 *slot_p = vi;
465 return vi;
468 /* Lookup the variable for the call statement CALL representing
469 the uses. Returns NULL if there is nothing special about this call. */
471 static varinfo_t
472 lookup_call_use_vi (gcall *call)
474 varinfo_t *slot_p = call_stmt_vars->get (call);
475 if (slot_p)
476 return *slot_p;
478 return NULL;
481 /* Lookup the variable for the call statement CALL representing
482 the clobbers. Returns NULL if there is nothing special about this call. */
484 static varinfo_t
485 lookup_call_clobber_vi (gcall *call)
487 varinfo_t uses = lookup_call_use_vi (call);
488 if (!uses)
489 return NULL;
491 return vi_next (uses);
494 /* Lookup or create the variable for the call statement CALL representing
495 the uses. */
497 static varinfo_t
498 get_call_use_vi (gcall *call)
500 return get_call_vi (call);
503 /* Lookup or create the variable for the call statement CALL representing
504 the clobbers. */
506 static varinfo_t ATTRIBUTE_UNUSED
507 get_call_clobber_vi (gcall *call)
509 return vi_next (get_call_vi (call));
513 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
515 /* An expression that appears in a constraint. */
517 struct constraint_expr
519 /* Constraint type. */
520 constraint_expr_type type;
522 /* Variable we are referring to in the constraint. */
523 unsigned int var;
525 /* Offset, in bits, of this constraint from the beginning of
526 variables it ends up referring to.
528 IOW, in a deref constraint, we would deref, get the result set,
529 then add OFFSET to each member. */
530 HOST_WIDE_INT offset;
533 /* Use 0x8000... as special unknown offset. */
534 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
536 typedef struct constraint_expr ce_s;
537 static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool);
538 static void get_constraint_for (tree, vec<ce_s> *);
539 static void get_constraint_for_rhs (tree, vec<ce_s> *);
540 static void do_deref (vec<ce_s> *);
542 /* Our set constraints are made up of two constraint expressions, one
543 LHS, and one RHS.
545 As described in the introduction, our set constraints each represent an
546 operation between set valued variables.
548 struct constraint
550 struct constraint_expr lhs;
551 struct constraint_expr rhs;
554 /* List of constraints that we use to build the constraint graph from. */
556 static vec<constraint_t> constraints;
557 static alloc_pool constraint_pool;
559 /* The constraint graph is represented as an array of bitmaps
560 containing successor nodes. */
562 struct constraint_graph
564 /* Size of this graph, which may be different than the number of
565 nodes in the variable map. */
566 unsigned int size;
568 /* Explicit successors of each node. */
569 bitmap *succs;
571 /* Implicit predecessors of each node (Used for variable
572 substitution). */
573 bitmap *implicit_preds;
575 /* Explicit predecessors of each node (Used for variable substitution). */
576 bitmap *preds;
578 /* Indirect cycle representatives, or -1 if the node has no indirect
579 cycles. */
580 int *indirect_cycles;
582 /* Representative node for a node. rep[a] == a unless the node has
583 been unified. */
584 unsigned int *rep;
586 /* Equivalence class representative for a label. This is used for
587 variable substitution. */
588 int *eq_rep;
590 /* Pointer equivalence label for a node. All nodes with the same
591 pointer equivalence label can be unified together at some point
592 (either during constraint optimization or after the constraint
593 graph is built). */
594 unsigned int *pe;
596 /* Pointer equivalence representative for a label. This is used to
597 handle nodes that are pointer equivalent but not location
598 equivalent. We can unite these once the addressof constraints
599 are transformed into initial points-to sets. */
600 int *pe_rep;
602 /* Pointer equivalence label for each node, used during variable
603 substitution. */
604 unsigned int *pointer_label;
606 /* Location equivalence label for each node, used during location
607 equivalence finding. */
608 unsigned int *loc_label;
610 /* Pointed-by set for each node, used during location equivalence
611 finding. This is pointed-by rather than pointed-to, because it
612 is constructed using the predecessor graph. */
613 bitmap *pointed_by;
615 /* Points to sets for pointer equivalence. This is *not* the actual
616 points-to sets for nodes. */
617 bitmap *points_to;
619 /* Bitmap of nodes where the bit is set if the node is a direct
620 node. Used for variable substitution. */
621 sbitmap direct_nodes;
623 /* Bitmap of nodes where the bit is set if the node is address
624 taken. Used for variable substitution. */
625 bitmap address_taken;
627 /* Vector of complex constraints for each graph node. Complex
628 constraints are those involving dereferences or offsets that are
629 not 0. */
630 vec<constraint_t> *complex;
633 static constraint_graph_t graph;
635 /* During variable substitution and the offline version of indirect
636 cycle finding, we create nodes to represent dereferences and
637 address taken constraints. These represent where these start and
638 end. */
639 #define FIRST_REF_NODE (varmap).length ()
640 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
642 /* Return the representative node for NODE, if NODE has been unioned
643 with another NODE.
644 This function performs path compression along the way to finding
645 the representative. */
647 static unsigned int
648 find (unsigned int node)
650 gcc_checking_assert (node < graph->size);
651 if (graph->rep[node] != node)
652 return graph->rep[node] = find (graph->rep[node]);
653 return node;
656 /* Union the TO and FROM nodes to the TO nodes.
657 Note that at some point in the future, we may want to do
658 union-by-rank, in which case we are going to have to return the
659 node we unified to. */
661 static bool
662 unite (unsigned int to, unsigned int from)
664 gcc_checking_assert (to < graph->size && from < graph->size);
665 if (to != from && graph->rep[from] != to)
667 graph->rep[from] = to;
668 return true;
670 return false;
673 /* Create a new constraint consisting of LHS and RHS expressions. */
675 static constraint_t
676 new_constraint (const struct constraint_expr lhs,
677 const struct constraint_expr rhs)
679 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
680 ret->lhs = lhs;
681 ret->rhs = rhs;
682 return ret;
685 /* Print out constraint C to FILE. */
687 static void
688 dump_constraint (FILE *file, constraint_t c)
690 if (c->lhs.type == ADDRESSOF)
691 fprintf (file, "&");
692 else if (c->lhs.type == DEREF)
693 fprintf (file, "*");
694 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
695 if (c->lhs.offset == UNKNOWN_OFFSET)
696 fprintf (file, " + UNKNOWN");
697 else if (c->lhs.offset != 0)
698 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
699 fprintf (file, " = ");
700 if (c->rhs.type == ADDRESSOF)
701 fprintf (file, "&");
702 else if (c->rhs.type == DEREF)
703 fprintf (file, "*");
704 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
705 if (c->rhs.offset == UNKNOWN_OFFSET)
706 fprintf (file, " + UNKNOWN");
707 else if (c->rhs.offset != 0)
708 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
712 void debug_constraint (constraint_t);
713 void debug_constraints (void);
714 void debug_constraint_graph (void);
715 void debug_solution_for_var (unsigned int);
716 void debug_sa_points_to_info (void);
718 /* Print out constraint C to stderr. */
720 DEBUG_FUNCTION void
721 debug_constraint (constraint_t c)
723 dump_constraint (stderr, c);
724 fprintf (stderr, "\n");
727 /* Print out all constraints to FILE */
729 static void
730 dump_constraints (FILE *file, int from)
732 int i;
733 constraint_t c;
734 for (i = from; constraints.iterate (i, &c); i++)
735 if (c)
737 dump_constraint (file, c);
738 fprintf (file, "\n");
742 /* Print out all constraints to stderr. */
744 DEBUG_FUNCTION void
745 debug_constraints (void)
747 dump_constraints (stderr, 0);
750 /* Print the constraint graph in dot format. */
752 static void
753 dump_constraint_graph (FILE *file)
755 unsigned int i;
757 /* Only print the graph if it has already been initialized: */
758 if (!graph)
759 return;
761 /* Prints the header of the dot file: */
762 fprintf (file, "strict digraph {\n");
763 fprintf (file, " node [\n shape = box\n ]\n");
764 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
765 fprintf (file, "\n // List of nodes and complex constraints in "
766 "the constraint graph:\n");
768 /* The next lines print the nodes in the graph together with the
769 complex constraints attached to them. */
770 for (i = 1; i < graph->size; i++)
772 if (i == FIRST_REF_NODE)
773 continue;
774 if (find (i) != i)
775 continue;
776 if (i < FIRST_REF_NODE)
777 fprintf (file, "\"%s\"", get_varinfo (i)->name);
778 else
779 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
780 if (graph->complex[i].exists ())
782 unsigned j;
783 constraint_t c;
784 fprintf (file, " [label=\"\\N\\n");
785 for (j = 0; graph->complex[i].iterate (j, &c); ++j)
787 dump_constraint (file, c);
788 fprintf (file, "\\l");
790 fprintf (file, "\"]");
792 fprintf (file, ";\n");
795 /* Go over the edges. */
796 fprintf (file, "\n // Edges in the constraint graph:\n");
797 for (i = 1; i < graph->size; i++)
799 unsigned j;
800 bitmap_iterator bi;
801 if (find (i) != i)
802 continue;
803 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
805 unsigned to = find (j);
806 if (i == to)
807 continue;
808 if (i < FIRST_REF_NODE)
809 fprintf (file, "\"%s\"", get_varinfo (i)->name);
810 else
811 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
812 fprintf (file, " -> ");
813 if (to < FIRST_REF_NODE)
814 fprintf (file, "\"%s\"", get_varinfo (to)->name);
815 else
816 fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
817 fprintf (file, ";\n");
821 /* Prints the tail of the dot file. */
822 fprintf (file, "}\n");
825 /* Print out the constraint graph to stderr. */
827 DEBUG_FUNCTION void
828 debug_constraint_graph (void)
830 dump_constraint_graph (stderr);
833 /* SOLVER FUNCTIONS
835 The solver is a simple worklist solver, that works on the following
836 algorithm:
838 sbitmap changed_nodes = all zeroes;
839 changed_count = 0;
840 For each node that is not already collapsed:
841 changed_count++;
842 set bit in changed nodes
844 while (changed_count > 0)
846 compute topological ordering for constraint graph
848 find and collapse cycles in the constraint graph (updating
849 changed if necessary)
851 for each node (n) in the graph in topological order:
852 changed_count--;
854 Process each complex constraint associated with the node,
855 updating changed if necessary.
857 For each outgoing edge from n, propagate the solution from n to
858 the destination of the edge, updating changed as necessary.
860 } */
862 /* Return true if two constraint expressions A and B are equal. */
864 static bool
865 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
867 return a.type == b.type && a.var == b.var && a.offset == b.offset;
870 /* Return true if constraint expression A is less than constraint expression
871 B. This is just arbitrary, but consistent, in order to give them an
872 ordering. */
874 static bool
875 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
877 if (a.type == b.type)
879 if (a.var == b.var)
880 return a.offset < b.offset;
881 else
882 return a.var < b.var;
884 else
885 return a.type < b.type;
888 /* Return true if constraint A is less than constraint B. This is just
889 arbitrary, but consistent, in order to give them an ordering. */
891 static bool
892 constraint_less (const constraint_t &a, const constraint_t &b)
894 if (constraint_expr_less (a->lhs, b->lhs))
895 return true;
896 else if (constraint_expr_less (b->lhs, a->lhs))
897 return false;
898 else
899 return constraint_expr_less (a->rhs, b->rhs);
902 /* Return true if two constraints A and B are equal. */
904 static bool
905 constraint_equal (struct constraint a, struct constraint b)
907 return constraint_expr_equal (a.lhs, b.lhs)
908 && constraint_expr_equal (a.rhs, b.rhs);
912 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
914 static constraint_t
915 constraint_vec_find (vec<constraint_t> vec,
916 struct constraint lookfor)
918 unsigned int place;
919 constraint_t found;
921 if (!vec.exists ())
922 return NULL;
924 place = vec.lower_bound (&lookfor, constraint_less);
925 if (place >= vec.length ())
926 return NULL;
927 found = vec[place];
928 if (!constraint_equal (*found, lookfor))
929 return NULL;
930 return found;
933 /* Union two constraint vectors, TO and FROM. Put the result in TO.
934 Returns true of TO set is changed. */
936 static bool
937 constraint_set_union (vec<constraint_t> *to,
938 vec<constraint_t> *from)
940 int i;
941 constraint_t c;
942 bool any_change = false;
944 FOR_EACH_VEC_ELT (*from, i, c)
946 if (constraint_vec_find (*to, *c) == NULL)
948 unsigned int place = to->lower_bound (c, constraint_less);
949 to->safe_insert (place, c);
950 any_change = true;
953 return any_change;
956 /* Expands the solution in SET to all sub-fields of variables included. */
958 static bitmap
959 solution_set_expand (bitmap set, bitmap *expanded)
961 bitmap_iterator bi;
962 unsigned j;
964 if (*expanded)
965 return *expanded;
967 *expanded = BITMAP_ALLOC (&iteration_obstack);
969 /* In a first pass expand to the head of the variables we need to
970 add all sub-fields off. This avoids quadratic behavior. */
971 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
973 varinfo_t v = get_varinfo (j);
974 if (v->is_artificial_var
975 || v->is_full_var)
976 continue;
977 bitmap_set_bit (*expanded, v->head);
980 /* In the second pass now expand all head variables with subfields. */
981 EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi)
983 varinfo_t v = get_varinfo (j);
984 if (v->head != j)
985 continue;
986 for (v = vi_next (v); v != NULL; v = vi_next (v))
987 bitmap_set_bit (*expanded, v->id);
990 /* And finally set the rest of the bits from SET. */
991 bitmap_ior_into (*expanded, set);
993 return *expanded;
996 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
997 process. */
999 static bool
1000 set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
1001 bitmap *expanded_delta)
1003 bool changed = false;
1004 bitmap_iterator bi;
1005 unsigned int i;
1007 /* If the solution of DELTA contains anything it is good enough to transfer
1008 this to TO. */
1009 if (bitmap_bit_p (delta, anything_id))
1010 return bitmap_set_bit (to, anything_id);
1012 /* If the offset is unknown we have to expand the solution to
1013 all subfields. */
1014 if (inc == UNKNOWN_OFFSET)
1016 delta = solution_set_expand (delta, expanded_delta);
1017 changed |= bitmap_ior_into (to, delta);
1018 return changed;
1021 /* For non-zero offset union the offsetted solution into the destination. */
1022 EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
1024 varinfo_t vi = get_varinfo (i);
1026 /* If this is a variable with just one field just set its bit
1027 in the result. */
1028 if (vi->is_artificial_var
1029 || vi->is_unknown_size_var
1030 || vi->is_full_var)
1031 changed |= bitmap_set_bit (to, i);
1032 else
1034 HOST_WIDE_INT fieldoffset = vi->offset + inc;
1035 unsigned HOST_WIDE_INT size = vi->size;
1037 /* If the offset makes the pointer point to before the
1038 variable use offset zero for the field lookup. */
1039 if (fieldoffset < 0)
1040 vi = get_varinfo (vi->head);
1041 else
1042 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
1046 changed |= bitmap_set_bit (to, vi->id);
1047 if (vi->is_full_var
1048 || vi->next == 0)
1049 break;
1051 /* We have to include all fields that overlap the current field
1052 shifted by inc. */
1053 vi = vi_next (vi);
1055 while (vi->offset < fieldoffset + size);
1059 return changed;
1062 /* Insert constraint C into the list of complex constraints for graph
1063 node VAR. */
1065 static void
1066 insert_into_complex (constraint_graph_t graph,
1067 unsigned int var, constraint_t c)
1069 vec<constraint_t> complex = graph->complex[var];
1070 unsigned int place = complex.lower_bound (c, constraint_less);
1072 /* Only insert constraints that do not already exist. */
1073 if (place >= complex.length ()
1074 || !constraint_equal (*c, *complex[place]))
1075 graph->complex[var].safe_insert (place, c);
1079 /* Condense two variable nodes into a single variable node, by moving
1080 all associated info from FROM to TO. Returns true if TO node's
1081 constraint set changes after the merge. */
1083 static bool
1084 merge_node_constraints (constraint_graph_t graph, unsigned int to,
1085 unsigned int from)
1087 unsigned int i;
1088 constraint_t c;
1089 bool any_change = false;
1091 gcc_checking_assert (find (from) == to);
1093 /* Move all complex constraints from src node into to node */
1094 FOR_EACH_VEC_ELT (graph->complex[from], i, c)
1096 /* In complex constraints for node FROM, we may have either
1097 a = *FROM, and *FROM = a, or an offseted constraint which are
1098 always added to the rhs node's constraints. */
1100 if (c->rhs.type == DEREF)
1101 c->rhs.var = to;
1102 else if (c->lhs.type == DEREF)
1103 c->lhs.var = to;
1104 else
1105 c->rhs.var = to;
1108 any_change = constraint_set_union (&graph->complex[to],
1109 &graph->complex[from]);
1110 graph->complex[from].release ();
1111 return any_change;
1115 /* Remove edges involving NODE from GRAPH. */
1117 static void
1118 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1120 if (graph->succs[node])
1121 BITMAP_FREE (graph->succs[node]);
1124 /* Merge GRAPH nodes FROM and TO into node TO. */
1126 static void
1127 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1128 unsigned int from)
1130 if (graph->indirect_cycles[from] != -1)
1132 /* If we have indirect cycles with the from node, and we have
1133 none on the to node, the to node has indirect cycles from the
1134 from node now that they are unified.
1135 If indirect cycles exist on both, unify the nodes that they
1136 are in a cycle with, since we know they are in a cycle with
1137 each other. */
1138 if (graph->indirect_cycles[to] == -1)
1139 graph->indirect_cycles[to] = graph->indirect_cycles[from];
1142 /* Merge all the successor edges. */
1143 if (graph->succs[from])
1145 if (!graph->succs[to])
1146 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1147 bitmap_ior_into (graph->succs[to],
1148 graph->succs[from]);
1151 clear_edges_for_node (graph, from);
1155 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1156 it doesn't exist in the graph already. */
1158 static void
1159 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1160 unsigned int from)
1162 if (to == from)
1163 return;
1165 if (!graph->implicit_preds[to])
1166 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1168 if (bitmap_set_bit (graph->implicit_preds[to], from))
1169 stats.num_implicit_edges++;
1172 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1173 it doesn't exist in the graph already.
1174 Return false if the edge already existed, true otherwise. */
1176 static void
1177 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1178 unsigned int from)
1180 if (!graph->preds[to])
1181 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1182 bitmap_set_bit (graph->preds[to], from);
1185 /* Add a graph edge to GRAPH, going from FROM to TO if
1186 it doesn't exist in the graph already.
1187 Return false if the edge already existed, true otherwise. */
1189 static bool
1190 add_graph_edge (constraint_graph_t graph, unsigned int to,
1191 unsigned int from)
1193 if (to == from)
1195 return false;
1197 else
1199 bool r = false;
1201 if (!graph->succs[from])
1202 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1203 if (bitmap_set_bit (graph->succs[from], to))
1205 r = true;
1206 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1207 stats.num_edges++;
1209 return r;
1214 /* Initialize the constraint graph structure to contain SIZE nodes. */
1216 static void
1217 init_graph (unsigned int size)
1219 unsigned int j;
1221 graph = XCNEW (struct constraint_graph);
1222 graph->size = size;
1223 graph->succs = XCNEWVEC (bitmap, graph->size);
1224 graph->indirect_cycles = XNEWVEC (int, graph->size);
1225 graph->rep = XNEWVEC (unsigned int, graph->size);
1226 /* ??? Macros do not support template types with multiple arguments,
1227 so we use a typedef to work around it. */
1228 typedef vec<constraint_t> vec_constraint_t_heap;
1229 graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
1230 graph->pe = XCNEWVEC (unsigned int, graph->size);
1231 graph->pe_rep = XNEWVEC (int, graph->size);
1233 for (j = 0; j < graph->size; j++)
1235 graph->rep[j] = j;
1236 graph->pe_rep[j] = -1;
1237 graph->indirect_cycles[j] = -1;
1241 /* Build the constraint graph, adding only predecessor edges right now. */
1243 static void
1244 build_pred_graph (void)
1246 int i;
1247 constraint_t c;
1248 unsigned int j;
1250 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1251 graph->preds = XCNEWVEC (bitmap, graph->size);
1252 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1253 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1254 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1255 graph->points_to = XCNEWVEC (bitmap, graph->size);
1256 graph->eq_rep = XNEWVEC (int, graph->size);
1257 graph->direct_nodes = sbitmap_alloc (graph->size);
1258 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1259 bitmap_clear (graph->direct_nodes);
1261 for (j = 1; j < FIRST_REF_NODE; j++)
1263 if (!get_varinfo (j)->is_special_var)
1264 bitmap_set_bit (graph->direct_nodes, j);
1267 for (j = 0; j < graph->size; j++)
1268 graph->eq_rep[j] = -1;
1270 for (j = 0; j < varmap.length (); j++)
1271 graph->indirect_cycles[j] = -1;
1273 FOR_EACH_VEC_ELT (constraints, i, c)
1275 struct constraint_expr lhs = c->lhs;
1276 struct constraint_expr rhs = c->rhs;
1277 unsigned int lhsvar = lhs.var;
1278 unsigned int rhsvar = rhs.var;
1280 if (lhs.type == DEREF)
1282 /* *x = y. */
1283 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1284 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1286 else if (rhs.type == DEREF)
1288 /* x = *y */
1289 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1290 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1291 else
1292 bitmap_clear_bit (graph->direct_nodes, lhsvar);
1294 else if (rhs.type == ADDRESSOF)
1296 varinfo_t v;
1298 /* x = &y */
1299 if (graph->points_to[lhsvar] == NULL)
1300 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1301 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1303 if (graph->pointed_by[rhsvar] == NULL)
1304 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1305 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1307 /* Implicitly, *x = y */
1308 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1310 /* All related variables are no longer direct nodes. */
1311 bitmap_clear_bit (graph->direct_nodes, rhsvar);
1312 v = get_varinfo (rhsvar);
1313 if (!v->is_full_var)
1315 v = get_varinfo (v->head);
1318 bitmap_clear_bit (graph->direct_nodes, v->id);
1319 v = vi_next (v);
1321 while (v != NULL);
1323 bitmap_set_bit (graph->address_taken, rhsvar);
1325 else if (lhsvar > anything_id
1326 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1328 /* x = y */
1329 add_pred_graph_edge (graph, lhsvar, rhsvar);
1330 /* Implicitly, *x = *y */
1331 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1332 FIRST_REF_NODE + rhsvar);
1334 else if (lhs.offset != 0 || rhs.offset != 0)
1336 if (rhs.offset != 0)
1337 bitmap_clear_bit (graph->direct_nodes, lhs.var);
1338 else if (lhs.offset != 0)
1339 bitmap_clear_bit (graph->direct_nodes, rhs.var);
1344 /* Build the constraint graph, adding successor edges. */
1346 static void
1347 build_succ_graph (void)
1349 unsigned i, t;
1350 constraint_t c;
1352 FOR_EACH_VEC_ELT (constraints, i, c)
1354 struct constraint_expr lhs;
1355 struct constraint_expr rhs;
1356 unsigned int lhsvar;
1357 unsigned int rhsvar;
1359 if (!c)
1360 continue;
1362 lhs = c->lhs;
1363 rhs = c->rhs;
1364 lhsvar = find (lhs.var);
1365 rhsvar = find (rhs.var);
1367 if (lhs.type == DEREF)
1369 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1370 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1372 else if (rhs.type == DEREF)
1374 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1375 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1377 else if (rhs.type == ADDRESSOF)
1379 /* x = &y */
1380 gcc_checking_assert (find (rhs.var) == rhs.var);
1381 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1383 else if (lhsvar > anything_id
1384 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1386 add_graph_edge (graph, lhsvar, rhsvar);
1390 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1391 receive pointers. */
1392 t = find (storedanything_id);
1393 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1395 if (!bitmap_bit_p (graph->direct_nodes, i)
1396 && get_varinfo (i)->may_have_pointers)
1397 add_graph_edge (graph, find (i), t);
1400 /* Everything stored to ANYTHING also potentially escapes. */
1401 add_graph_edge (graph, find (escaped_id), t);
1405 /* Changed variables on the last iteration. */
1406 static bitmap changed;
1408 /* Strongly Connected Component visitation info. */
1410 struct scc_info
1412 sbitmap visited;
1413 sbitmap deleted;
1414 unsigned int *dfs;
1415 unsigned int *node_mapping;
1416 int current_index;
1417 vec<unsigned> scc_stack;
1421 /* Recursive routine to find strongly connected components in GRAPH.
1422 SI is the SCC info to store the information in, and N is the id of current
1423 graph node we are processing.
1425 This is Tarjan's strongly connected component finding algorithm, as
1426 modified by Nuutila to keep only non-root nodes on the stack.
1427 The algorithm can be found in "On finding the strongly connected
1428 connected components in a directed graph" by Esko Nuutila and Eljas
1429 Soisalon-Soininen, in Information Processing Letters volume 49,
1430 number 1, pages 9-14. */
1432 static void
1433 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1435 unsigned int i;
1436 bitmap_iterator bi;
1437 unsigned int my_dfs;
1439 bitmap_set_bit (si->visited, n);
1440 si->dfs[n] = si->current_index ++;
1441 my_dfs = si->dfs[n];
1443 /* Visit all the successors. */
1444 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1446 unsigned int w;
1448 if (i > LAST_REF_NODE)
1449 break;
1451 w = find (i);
1452 if (bitmap_bit_p (si->deleted, w))
1453 continue;
1455 if (!bitmap_bit_p (si->visited, w))
1456 scc_visit (graph, si, w);
1458 unsigned int t = find (w);
1459 gcc_checking_assert (find (n) == n);
1460 if (si->dfs[t] < si->dfs[n])
1461 si->dfs[n] = si->dfs[t];
1464 /* See if any components have been identified. */
1465 if (si->dfs[n] == my_dfs)
1467 if (si->scc_stack.length () > 0
1468 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1470 bitmap scc = BITMAP_ALLOC (NULL);
1471 unsigned int lowest_node;
1472 bitmap_iterator bi;
1474 bitmap_set_bit (scc, n);
1476 while (si->scc_stack.length () != 0
1477 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1479 unsigned int w = si->scc_stack.pop ();
1481 bitmap_set_bit (scc, w);
1484 lowest_node = bitmap_first_set_bit (scc);
1485 gcc_assert (lowest_node < FIRST_REF_NODE);
1487 /* Collapse the SCC nodes into a single node, and mark the
1488 indirect cycles. */
1489 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1491 if (i < FIRST_REF_NODE)
1493 if (unite (lowest_node, i))
1494 unify_nodes (graph, lowest_node, i, false);
1496 else
1498 unite (lowest_node, i);
1499 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1503 bitmap_set_bit (si->deleted, n);
1505 else
1506 si->scc_stack.safe_push (n);
1509 /* Unify node FROM into node TO, updating the changed count if
1510 necessary when UPDATE_CHANGED is true. */
1512 static void
1513 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1514 bool update_changed)
1516 gcc_checking_assert (to != from && find (to) == to);
1518 if (dump_file && (dump_flags & TDF_DETAILS))
1519 fprintf (dump_file, "Unifying %s to %s\n",
1520 get_varinfo (from)->name,
1521 get_varinfo (to)->name);
1523 if (update_changed)
1524 stats.unified_vars_dynamic++;
1525 else
1526 stats.unified_vars_static++;
1528 merge_graph_nodes (graph, to, from);
1529 if (merge_node_constraints (graph, to, from))
1531 if (update_changed)
1532 bitmap_set_bit (changed, to);
1535 /* Mark TO as changed if FROM was changed. If TO was already marked
1536 as changed, decrease the changed count. */
1538 if (update_changed
1539 && bitmap_clear_bit (changed, from))
1540 bitmap_set_bit (changed, to);
1541 varinfo_t fromvi = get_varinfo (from);
1542 if (fromvi->solution)
1544 /* If the solution changes because of the merging, we need to mark
1545 the variable as changed. */
1546 varinfo_t tovi = get_varinfo (to);
1547 if (bitmap_ior_into (tovi->solution, fromvi->solution))
1549 if (update_changed)
1550 bitmap_set_bit (changed, to);
1553 BITMAP_FREE (fromvi->solution);
1554 if (fromvi->oldsolution)
1555 BITMAP_FREE (fromvi->oldsolution);
1557 if (stats.iterations > 0
1558 && tovi->oldsolution)
1559 BITMAP_FREE (tovi->oldsolution);
1561 if (graph->succs[to])
1562 bitmap_clear_bit (graph->succs[to], to);
1565 /* Information needed to compute the topological ordering of a graph. */
1567 struct topo_info
1569 /* sbitmap of visited nodes. */
1570 sbitmap visited;
1571 /* Array that stores the topological order of the graph, *in
1572 reverse*. */
1573 vec<unsigned> topo_order;
1577 /* Initialize and return a topological info structure. */
1579 static struct topo_info *
1580 init_topo_info (void)
1582 size_t size = graph->size;
1583 struct topo_info *ti = XNEW (struct topo_info);
1584 ti->visited = sbitmap_alloc (size);
1585 bitmap_clear (ti->visited);
1586 ti->topo_order.create (1);
1587 return ti;
1591 /* Free the topological sort info pointed to by TI. */
1593 static void
1594 free_topo_info (struct topo_info *ti)
1596 sbitmap_free (ti->visited);
1597 ti->topo_order.release ();
1598 free (ti);
1601 /* Visit the graph in topological order, and store the order in the
1602 topo_info structure. */
1604 static void
1605 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1606 unsigned int n)
1608 bitmap_iterator bi;
1609 unsigned int j;
1611 bitmap_set_bit (ti->visited, n);
1613 if (graph->succs[n])
1614 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1616 if (!bitmap_bit_p (ti->visited, j))
1617 topo_visit (graph, ti, j);
1620 ti->topo_order.safe_push (n);
1623 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1624 starting solution for y. */
1626 static void
1627 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1628 bitmap delta, bitmap *expanded_delta)
1630 unsigned int lhs = c->lhs.var;
1631 bool flag = false;
1632 bitmap sol = get_varinfo (lhs)->solution;
1633 unsigned int j;
1634 bitmap_iterator bi;
1635 HOST_WIDE_INT roffset = c->rhs.offset;
1637 /* Our IL does not allow this. */
1638 gcc_checking_assert (c->lhs.offset == 0);
1640 /* If the solution of Y contains anything it is good enough to transfer
1641 this to the LHS. */
1642 if (bitmap_bit_p (delta, anything_id))
1644 flag |= bitmap_set_bit (sol, anything_id);
1645 goto done;
1648 /* If we do not know at with offset the rhs is dereferenced compute
1649 the reachability set of DELTA, conservatively assuming it is
1650 dereferenced at all valid offsets. */
1651 if (roffset == UNKNOWN_OFFSET)
1653 delta = solution_set_expand (delta, expanded_delta);
1654 /* No further offset processing is necessary. */
1655 roffset = 0;
1658 /* For each variable j in delta (Sol(y)), add
1659 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1660 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1662 varinfo_t v = get_varinfo (j);
1663 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1664 unsigned HOST_WIDE_INT size = v->size;
1665 unsigned int t;
1667 if (v->is_full_var)
1669 else if (roffset != 0)
1671 if (fieldoffset < 0)
1672 v = get_varinfo (v->head);
1673 else
1674 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1677 /* We have to include all fields that overlap the current field
1678 shifted by roffset. */
1681 t = find (v->id);
1683 /* Adding edges from the special vars is pointless.
1684 They don't have sets that can change. */
1685 if (get_varinfo (t)->is_special_var)
1686 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1687 /* Merging the solution from ESCAPED needlessly increases
1688 the set. Use ESCAPED as representative instead. */
1689 else if (v->id == escaped_id)
1690 flag |= bitmap_set_bit (sol, escaped_id);
1691 else if (v->may_have_pointers
1692 && add_graph_edge (graph, lhs, t))
1693 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1695 if (v->is_full_var
1696 || v->next == 0)
1697 break;
1699 v = vi_next (v);
1701 while (v->offset < fieldoffset + size);
1704 done:
1705 /* If the LHS solution changed, mark the var as changed. */
1706 if (flag)
1708 get_varinfo (lhs)->solution = sol;
1709 bitmap_set_bit (changed, lhs);
1713 /* Process a constraint C that represents *(x + off) = y using DELTA
1714 as the starting solution for x. */
1716 static void
1717 do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1719 unsigned int rhs = c->rhs.var;
1720 bitmap sol = get_varinfo (rhs)->solution;
1721 unsigned int j;
1722 bitmap_iterator bi;
1723 HOST_WIDE_INT loff = c->lhs.offset;
1724 bool escaped_p = false;
1726 /* Our IL does not allow this. */
1727 gcc_checking_assert (c->rhs.offset == 0);
1729 /* If the solution of y contains ANYTHING simply use the ANYTHING
1730 solution. This avoids needlessly increasing the points-to sets. */
1731 if (bitmap_bit_p (sol, anything_id))
1732 sol = get_varinfo (find (anything_id))->solution;
1734 /* If the solution for x contains ANYTHING we have to merge the
1735 solution of y into all pointer variables which we do via
1736 STOREDANYTHING. */
1737 if (bitmap_bit_p (delta, anything_id))
1739 unsigned t = find (storedanything_id);
1740 if (add_graph_edge (graph, t, rhs))
1742 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1743 bitmap_set_bit (changed, t);
1745 return;
1748 /* If we do not know at with offset the rhs is dereferenced compute
1749 the reachability set of DELTA, conservatively assuming it is
1750 dereferenced at all valid offsets. */
1751 if (loff == UNKNOWN_OFFSET)
1753 delta = solution_set_expand (delta, expanded_delta);
1754 loff = 0;
1757 /* For each member j of delta (Sol(x)), add an edge from y to j and
1758 union Sol(y) into Sol(j) */
1759 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1761 varinfo_t v = get_varinfo (j);
1762 unsigned int t;
1763 HOST_WIDE_INT fieldoffset = v->offset + loff;
1764 unsigned HOST_WIDE_INT size = v->size;
1766 if (v->is_full_var)
1768 else if (loff != 0)
1770 if (fieldoffset < 0)
1771 v = get_varinfo (v->head);
1772 else
1773 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1776 /* We have to include all fields that overlap the current field
1777 shifted by loff. */
1780 if (v->may_have_pointers)
1782 /* If v is a global variable then this is an escape point. */
1783 if (v->is_global_var
1784 && !escaped_p)
1786 t = find (escaped_id);
1787 if (add_graph_edge (graph, t, rhs)
1788 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1789 bitmap_set_bit (changed, t);
1790 /* Enough to let rhs escape once. */
1791 escaped_p = true;
1794 if (v->is_special_var)
1795 break;
1797 t = find (v->id);
1798 if (add_graph_edge (graph, t, rhs)
1799 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1800 bitmap_set_bit (changed, t);
1803 if (v->is_full_var
1804 || v->next == 0)
1805 break;
1807 v = vi_next (v);
1809 while (v->offset < fieldoffset + size);
1813 /* Handle a non-simple (simple meaning requires no iteration),
1814 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1816 static void
1817 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1818 bitmap *expanded_delta)
1820 if (c->lhs.type == DEREF)
1822 if (c->rhs.type == ADDRESSOF)
1824 gcc_unreachable ();
1826 else
1828 /* *x = y */
1829 do_ds_constraint (c, delta, expanded_delta);
1832 else if (c->rhs.type == DEREF)
1834 /* x = *y */
1835 if (!(get_varinfo (c->lhs.var)->is_special_var))
1836 do_sd_constraint (graph, c, delta, expanded_delta);
1838 else
1840 bitmap tmp;
1841 bool flag = false;
1843 gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1844 && c->rhs.offset != 0 && c->lhs.offset == 0);
1845 tmp = get_varinfo (c->lhs.var)->solution;
1847 flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1848 expanded_delta);
1850 if (flag)
1851 bitmap_set_bit (changed, c->lhs.var);
1855 /* Initialize and return a new SCC info structure. */
1857 static struct scc_info *
1858 init_scc_info (size_t size)
1860 struct scc_info *si = XNEW (struct scc_info);
1861 size_t i;
1863 si->current_index = 0;
1864 si->visited = sbitmap_alloc (size);
1865 bitmap_clear (si->visited);
1866 si->deleted = sbitmap_alloc (size);
1867 bitmap_clear (si->deleted);
1868 si->node_mapping = XNEWVEC (unsigned int, size);
1869 si->dfs = XCNEWVEC (unsigned int, size);
1871 for (i = 0; i < size; i++)
1872 si->node_mapping[i] = i;
1874 si->scc_stack.create (1);
1875 return si;
1878 /* Free an SCC info structure pointed to by SI */
1880 static void
1881 free_scc_info (struct scc_info *si)
1883 sbitmap_free (si->visited);
1884 sbitmap_free (si->deleted);
1885 free (si->node_mapping);
1886 free (si->dfs);
1887 si->scc_stack.release ();
1888 free (si);
1892 /* Find indirect cycles in GRAPH that occur, using strongly connected
1893 components, and note them in the indirect cycles map.
1895 This technique comes from Ben Hardekopf and Calvin Lin,
1896 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1897 Lines of Code", submitted to PLDI 2007. */
1899 static void
1900 find_indirect_cycles (constraint_graph_t graph)
1902 unsigned int i;
1903 unsigned int size = graph->size;
1904 struct scc_info *si = init_scc_info (size);
1906 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1907 if (!bitmap_bit_p (si->visited, i) && find (i) == i)
1908 scc_visit (graph, si, i);
1910 free_scc_info (si);
1913 /* Compute a topological ordering for GRAPH, and store the result in the
1914 topo_info structure TI. */
1916 static void
1917 compute_topo_order (constraint_graph_t graph,
1918 struct topo_info *ti)
1920 unsigned int i;
1921 unsigned int size = graph->size;
1923 for (i = 0; i != size; ++i)
1924 if (!bitmap_bit_p (ti->visited, i) && find (i) == i)
1925 topo_visit (graph, ti, i);
1928 /* Structure used to for hash value numbering of pointer equivalence
1929 classes. */
1931 typedef struct equiv_class_label
1933 hashval_t hashcode;
1934 unsigned int equivalence_class;
1935 bitmap labels;
1936 } *equiv_class_label_t;
1937 typedef const struct equiv_class_label *const_equiv_class_label_t;
1939 /* Equiv_class_label hashtable helpers. */
1941 struct equiv_class_hasher : typed_free_remove <equiv_class_label>
1943 typedef equiv_class_label *value_type;
1944 typedef equiv_class_label *compare_type;
1945 static inline hashval_t hash (const equiv_class_label *);
1946 static inline bool equal (const equiv_class_label *,
1947 const equiv_class_label *);
1950 /* Hash function for a equiv_class_label_t */
1952 inline hashval_t
1953 equiv_class_hasher::hash (const equiv_class_label *ecl)
1955 return ecl->hashcode;
1958 /* Equality function for two equiv_class_label_t's. */
1960 inline bool
1961 equiv_class_hasher::equal (const equiv_class_label *eql1,
1962 const equiv_class_label *eql2)
1964 return (eql1->hashcode == eql2->hashcode
1965 && bitmap_equal_p (eql1->labels, eql2->labels));
1968 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1969 classes. */
1970 static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
1972 /* A hashtable for mapping a bitmap of labels->location equivalence
1973 classes. */
1974 static hash_table<equiv_class_hasher> *location_equiv_class_table;
1976 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1977 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1978 is equivalent to. */
1980 static equiv_class_label *
1981 equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1982 bitmap labels)
1984 equiv_class_label **slot;
1985 equiv_class_label ecl;
1987 ecl.labels = labels;
1988 ecl.hashcode = bitmap_hash (labels);
1989 slot = table->find_slot (&ecl, INSERT);
1990 if (!*slot)
1992 *slot = XNEW (struct equiv_class_label);
1993 (*slot)->labels = labels;
1994 (*slot)->hashcode = ecl.hashcode;
1995 (*slot)->equivalence_class = 0;
1998 return *slot;
2001 /* Perform offline variable substitution.
2003 This is a worst case quadratic time way of identifying variables
2004 that must have equivalent points-to sets, including those caused by
2005 static cycles, and single entry subgraphs, in the constraint graph.
2007 The technique is described in "Exploiting Pointer and Location
2008 Equivalence to Optimize Pointer Analysis. In the 14th International
2009 Static Analysis Symposium (SAS), August 2007." It is known as the
2010 "HU" algorithm, and is equivalent to value numbering the collapsed
2011 constraint graph including evaluating unions.
2013 The general method of finding equivalence classes is as follows:
2014 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
2015 Initialize all non-REF nodes to be direct nodes.
2016 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
2017 variable}
2018 For each constraint containing the dereference, we also do the same
2019 thing.
2021 We then compute SCC's in the graph and unify nodes in the same SCC,
2022 including pts sets.
2024 For each non-collapsed node x:
2025 Visit all unvisited explicit incoming edges.
2026 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
2027 where y->x.
2028 Lookup the equivalence class for pts(x).
2029 If we found one, equivalence_class(x) = found class.
2030 Otherwise, equivalence_class(x) = new class, and new_class is
2031 added to the lookup table.
2033 All direct nodes with the same equivalence class can be replaced
2034 with a single representative node.
2035 All unlabeled nodes (label == 0) are not pointers and all edges
2036 involving them can be eliminated.
2037 We perform these optimizations during rewrite_constraints
2039 In addition to pointer equivalence class finding, we also perform
2040 location equivalence class finding. This is the set of variables
2041 that always appear together in points-to sets. We use this to
2042 compress the size of the points-to sets. */
2044 /* Current maximum pointer equivalence class id. */
2045 static int pointer_equiv_class;
2047 /* Current maximum location equivalence class id. */
2048 static int location_equiv_class;
2050 /* Recursive routine to find strongly connected components in GRAPH,
2051 and label it's nodes with DFS numbers. */
2053 static void
2054 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2056 unsigned int i;
2057 bitmap_iterator bi;
2058 unsigned int my_dfs;
2060 gcc_checking_assert (si->node_mapping[n] == n);
2061 bitmap_set_bit (si->visited, n);
2062 si->dfs[n] = si->current_index ++;
2063 my_dfs = si->dfs[n];
2065 /* Visit all the successors. */
2066 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2068 unsigned int w = si->node_mapping[i];
2070 if (bitmap_bit_p (si->deleted, w))
2071 continue;
2073 if (!bitmap_bit_p (si->visited, w))
2074 condense_visit (graph, si, w);
2076 unsigned int t = si->node_mapping[w];
2077 gcc_checking_assert (si->node_mapping[n] == n);
2078 if (si->dfs[t] < si->dfs[n])
2079 si->dfs[n] = si->dfs[t];
2082 /* Visit all the implicit predecessors. */
2083 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2085 unsigned int w = si->node_mapping[i];
2087 if (bitmap_bit_p (si->deleted, w))
2088 continue;
2090 if (!bitmap_bit_p (si->visited, w))
2091 condense_visit (graph, si, w);
2093 unsigned int t = si->node_mapping[w];
2094 gcc_assert (si->node_mapping[n] == n);
2095 if (si->dfs[t] < si->dfs[n])
2096 si->dfs[n] = si->dfs[t];
2099 /* See if any components have been identified. */
2100 if (si->dfs[n] == my_dfs)
2102 while (si->scc_stack.length () != 0
2103 && si->dfs[si->scc_stack.last ()] >= my_dfs)
2105 unsigned int w = si->scc_stack.pop ();
2106 si->node_mapping[w] = n;
2108 if (!bitmap_bit_p (graph->direct_nodes, w))
2109 bitmap_clear_bit (graph->direct_nodes, n);
2111 /* Unify our nodes. */
2112 if (graph->preds[w])
2114 if (!graph->preds[n])
2115 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2116 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2118 if (graph->implicit_preds[w])
2120 if (!graph->implicit_preds[n])
2121 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2122 bitmap_ior_into (graph->implicit_preds[n],
2123 graph->implicit_preds[w]);
2125 if (graph->points_to[w])
2127 if (!graph->points_to[n])
2128 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2129 bitmap_ior_into (graph->points_to[n],
2130 graph->points_to[w]);
2133 bitmap_set_bit (si->deleted, n);
2135 else
2136 si->scc_stack.safe_push (n);
2139 /* Label pointer equivalences.
2141 This performs a value numbering of the constraint graph to
2142 discover which variables will always have the same points-to sets
2143 under the current set of constraints.
2145 The way it value numbers is to store the set of points-to bits
2146 generated by the constraints and graph edges. This is just used as a
2147 hash and equality comparison. The *actual set of points-to bits* is
2148 completely irrelevant, in that we don't care about being able to
2149 extract them later.
2151 The equality values (currently bitmaps) just have to satisfy a few
2152 constraints, the main ones being:
2153 1. The combining operation must be order independent.
2154 2. The end result of a given set of operations must be unique iff the
2155 combination of input values is unique
2156 3. Hashable. */
2158 static void
2159 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2161 unsigned int i, first_pred;
2162 bitmap_iterator bi;
2164 bitmap_set_bit (si->visited, n);
2166 /* Label and union our incoming edges's points to sets. */
2167 first_pred = -1U;
2168 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2170 unsigned int w = si->node_mapping[i];
2171 if (!bitmap_bit_p (si->visited, w))
2172 label_visit (graph, si, w);
2174 /* Skip unused edges */
2175 if (w == n || graph->pointer_label[w] == 0)
2176 continue;
2178 if (graph->points_to[w])
2180 if (!graph->points_to[n])
2182 if (first_pred == -1U)
2183 first_pred = w;
2184 else
2186 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2187 bitmap_ior (graph->points_to[n],
2188 graph->points_to[first_pred],
2189 graph->points_to[w]);
2192 else
2193 bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
2197 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2198 if (!bitmap_bit_p (graph->direct_nodes, n))
2200 if (!graph->points_to[n])
2202 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2203 if (first_pred != -1U)
2204 bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
2206 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2207 graph->pointer_label[n] = pointer_equiv_class++;
2208 equiv_class_label_t ecl;
2209 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2210 graph->points_to[n]);
2211 ecl->equivalence_class = graph->pointer_label[n];
2212 return;
2215 /* If there was only a single non-empty predecessor the pointer equiv
2216 class is the same. */
2217 if (!graph->points_to[n])
2219 if (first_pred != -1U)
2221 graph->pointer_label[n] = graph->pointer_label[first_pred];
2222 graph->points_to[n] = graph->points_to[first_pred];
2224 return;
2227 if (!bitmap_empty_p (graph->points_to[n]))
2229 equiv_class_label_t ecl;
2230 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2231 graph->points_to[n]);
2232 if (ecl->equivalence_class == 0)
2233 ecl->equivalence_class = pointer_equiv_class++;
2234 else
2236 BITMAP_FREE (graph->points_to[n]);
2237 graph->points_to[n] = ecl->labels;
2239 graph->pointer_label[n] = ecl->equivalence_class;
2243 /* Print the pred graph in dot format. */
2245 static void
2246 dump_pred_graph (struct scc_info *si, FILE *file)
2248 unsigned int i;
2250 /* Only print the graph if it has already been initialized: */
2251 if (!graph)
2252 return;
2254 /* Prints the header of the dot file: */
2255 fprintf (file, "strict digraph {\n");
2256 fprintf (file, " node [\n shape = box\n ]\n");
2257 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
2258 fprintf (file, "\n // List of nodes and complex constraints in "
2259 "the constraint graph:\n");
2261 /* The next lines print the nodes in the graph together with the
2262 complex constraints attached to them. */
2263 for (i = 1; i < graph->size; i++)
2265 if (i == FIRST_REF_NODE)
2266 continue;
2267 if (si->node_mapping[i] != i)
2268 continue;
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 if (graph->points_to[i]
2274 && !bitmap_empty_p (graph->points_to[i]))
2276 fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
2277 unsigned j;
2278 bitmap_iterator bi;
2279 EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
2280 fprintf (file, " %d", j);
2281 fprintf (file, " }\"]");
2283 fprintf (file, ";\n");
2286 /* Go over the edges. */
2287 fprintf (file, "\n // Edges in the constraint graph:\n");
2288 for (i = 1; i < graph->size; i++)
2290 unsigned j;
2291 bitmap_iterator bi;
2292 if (si->node_mapping[i] != i)
2293 continue;
2294 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
2296 unsigned from = si->node_mapping[j];
2297 if (from < FIRST_REF_NODE)
2298 fprintf (file, "\"%s\"", get_varinfo (from)->name);
2299 else
2300 fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name);
2301 fprintf (file, " -> ");
2302 if (i < FIRST_REF_NODE)
2303 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2304 else
2305 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2306 fprintf (file, ";\n");
2310 /* Prints the tail of the dot file. */
2311 fprintf (file, "}\n");
2314 /* Perform offline variable substitution, discovering equivalence
2315 classes, and eliminating non-pointer variables. */
2317 static struct scc_info *
2318 perform_var_substitution (constraint_graph_t graph)
2320 unsigned int i;
2321 unsigned int size = graph->size;
2322 struct scc_info *si = init_scc_info (size);
2324 bitmap_obstack_initialize (&iteration_obstack);
2325 pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
2326 location_equiv_class_table
2327 = new hash_table<equiv_class_hasher> (511);
2328 pointer_equiv_class = 1;
2329 location_equiv_class = 1;
2331 /* Condense the nodes, which means to find SCC's, count incoming
2332 predecessors, and unite nodes in SCC's. */
2333 for (i = 1; i < FIRST_REF_NODE; i++)
2334 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2335 condense_visit (graph, si, si->node_mapping[i]);
2337 if (dump_file && (dump_flags & TDF_GRAPH))
2339 fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
2340 "in dot format:\n");
2341 dump_pred_graph (si, dump_file);
2342 fprintf (dump_file, "\n\n");
2345 bitmap_clear (si->visited);
2346 /* Actually the label the nodes for pointer equivalences */
2347 for (i = 1; i < FIRST_REF_NODE; i++)
2348 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2349 label_visit (graph, si, si->node_mapping[i]);
2351 /* Calculate location equivalence labels. */
2352 for (i = 1; i < FIRST_REF_NODE; i++)
2354 bitmap pointed_by;
2355 bitmap_iterator bi;
2356 unsigned int j;
2358 if (!graph->pointed_by[i])
2359 continue;
2360 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2362 /* Translate the pointed-by mapping for pointer equivalence
2363 labels. */
2364 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2366 bitmap_set_bit (pointed_by,
2367 graph->pointer_label[si->node_mapping[j]]);
2369 /* The original pointed_by is now dead. */
2370 BITMAP_FREE (graph->pointed_by[i]);
2372 /* Look up the location equivalence label if one exists, or make
2373 one otherwise. */
2374 equiv_class_label_t ecl;
2375 ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
2376 if (ecl->equivalence_class == 0)
2377 ecl->equivalence_class = location_equiv_class++;
2378 else
2380 if (dump_file && (dump_flags & TDF_DETAILS))
2381 fprintf (dump_file, "Found location equivalence for node %s\n",
2382 get_varinfo (i)->name);
2383 BITMAP_FREE (pointed_by);
2385 graph->loc_label[i] = ecl->equivalence_class;
2389 if (dump_file && (dump_flags & TDF_DETAILS))
2390 for (i = 1; i < FIRST_REF_NODE; i++)
2392 unsigned j = si->node_mapping[i];
2393 if (j != i)
2395 fprintf (dump_file, "%s node id %d ",
2396 bitmap_bit_p (graph->direct_nodes, i)
2397 ? "Direct" : "Indirect", i);
2398 if (i < FIRST_REF_NODE)
2399 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2400 else
2401 fprintf (dump_file, "\"*%s\"",
2402 get_varinfo (i - FIRST_REF_NODE)->name);
2403 fprintf (dump_file, " mapped to SCC leader node id %d ", j);
2404 if (j < FIRST_REF_NODE)
2405 fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
2406 else
2407 fprintf (dump_file, "\"*%s\"\n",
2408 get_varinfo (j - FIRST_REF_NODE)->name);
2410 else
2412 fprintf (dump_file,
2413 "Equivalence classes for %s node id %d ",
2414 bitmap_bit_p (graph->direct_nodes, i)
2415 ? "direct" : "indirect", i);
2416 if (i < FIRST_REF_NODE)
2417 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2418 else
2419 fprintf (dump_file, "\"*%s\"",
2420 get_varinfo (i - FIRST_REF_NODE)->name);
2421 fprintf (dump_file,
2422 ": pointer %d, location %d\n",
2423 graph->pointer_label[i], graph->loc_label[i]);
2427 /* Quickly eliminate our non-pointer variables. */
2429 for (i = 1; i < FIRST_REF_NODE; i++)
2431 unsigned int node = si->node_mapping[i];
2433 if (graph->pointer_label[node] == 0)
2435 if (dump_file && (dump_flags & TDF_DETAILS))
2436 fprintf (dump_file,
2437 "%s is a non-pointer variable, eliminating edges.\n",
2438 get_varinfo (node)->name);
2439 stats.nonpointer_vars++;
2440 clear_edges_for_node (graph, node);
2444 return si;
2447 /* Free information that was only necessary for variable
2448 substitution. */
2450 static void
2451 free_var_substitution_info (struct scc_info *si)
2453 free_scc_info (si);
2454 free (graph->pointer_label);
2455 free (graph->loc_label);
2456 free (graph->pointed_by);
2457 free (graph->points_to);
2458 free (graph->eq_rep);
2459 sbitmap_free (graph->direct_nodes);
2460 delete pointer_equiv_class_table;
2461 pointer_equiv_class_table = NULL;
2462 delete location_equiv_class_table;
2463 location_equiv_class_table = NULL;
2464 bitmap_obstack_release (&iteration_obstack);
2467 /* Return an existing node that is equivalent to NODE, which has
2468 equivalence class LABEL, if one exists. Return NODE otherwise. */
2470 static unsigned int
2471 find_equivalent_node (constraint_graph_t graph,
2472 unsigned int node, unsigned int label)
2474 /* If the address version of this variable is unused, we can
2475 substitute it for anything else with the same label.
2476 Otherwise, we know the pointers are equivalent, but not the
2477 locations, and we can unite them later. */
2479 if (!bitmap_bit_p (graph->address_taken, node))
2481 gcc_checking_assert (label < graph->size);
2483 if (graph->eq_rep[label] != -1)
2485 /* Unify the two variables since we know they are equivalent. */
2486 if (unite (graph->eq_rep[label], node))
2487 unify_nodes (graph, graph->eq_rep[label], node, false);
2488 return graph->eq_rep[label];
2490 else
2492 graph->eq_rep[label] = node;
2493 graph->pe_rep[label] = node;
2496 else
2498 gcc_checking_assert (label < graph->size);
2499 graph->pe[node] = label;
2500 if (graph->pe_rep[label] == -1)
2501 graph->pe_rep[label] = node;
2504 return node;
2507 /* Unite pointer equivalent but not location equivalent nodes in
2508 GRAPH. This may only be performed once variable substitution is
2509 finished. */
2511 static void
2512 unite_pointer_equivalences (constraint_graph_t graph)
2514 unsigned int i;
2516 /* Go through the pointer equivalences and unite them to their
2517 representative, if they aren't already. */
2518 for (i = 1; i < FIRST_REF_NODE; i++)
2520 unsigned int label = graph->pe[i];
2521 if (label)
2523 int label_rep = graph->pe_rep[label];
2525 if (label_rep == -1)
2526 continue;
2528 label_rep = find (label_rep);
2529 if (label_rep >= 0 && unite (label_rep, find (i)))
2530 unify_nodes (graph, label_rep, i, false);
2535 /* Move complex constraints to the GRAPH nodes they belong to. */
2537 static void
2538 move_complex_constraints (constraint_graph_t graph)
2540 int i;
2541 constraint_t c;
2543 FOR_EACH_VEC_ELT (constraints, i, c)
2545 if (c)
2547 struct constraint_expr lhs = c->lhs;
2548 struct constraint_expr rhs = c->rhs;
2550 if (lhs.type == DEREF)
2552 insert_into_complex (graph, lhs.var, c);
2554 else if (rhs.type == DEREF)
2556 if (!(get_varinfo (lhs.var)->is_special_var))
2557 insert_into_complex (graph, rhs.var, c);
2559 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2560 && (lhs.offset != 0 || rhs.offset != 0))
2562 insert_into_complex (graph, rhs.var, c);
2569 /* Optimize and rewrite complex constraints while performing
2570 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2571 result of perform_variable_substitution. */
2573 static void
2574 rewrite_constraints (constraint_graph_t graph,
2575 struct scc_info *si)
2577 int i;
2578 constraint_t c;
2580 #ifdef ENABLE_CHECKING
2581 for (unsigned int j = 0; j < graph->size; j++)
2582 gcc_assert (find (j) == j);
2583 #endif
2585 FOR_EACH_VEC_ELT (constraints, i, c)
2587 struct constraint_expr lhs = c->lhs;
2588 struct constraint_expr rhs = c->rhs;
2589 unsigned int lhsvar = find (lhs.var);
2590 unsigned int rhsvar = find (rhs.var);
2591 unsigned int lhsnode, rhsnode;
2592 unsigned int lhslabel, rhslabel;
2594 lhsnode = si->node_mapping[lhsvar];
2595 rhsnode = si->node_mapping[rhsvar];
2596 lhslabel = graph->pointer_label[lhsnode];
2597 rhslabel = graph->pointer_label[rhsnode];
2599 /* See if it is really a non-pointer variable, and if so, ignore
2600 the constraint. */
2601 if (lhslabel == 0)
2603 if (dump_file && (dump_flags & TDF_DETAILS))
2606 fprintf (dump_file, "%s is a non-pointer variable,"
2607 "ignoring constraint:",
2608 get_varinfo (lhs.var)->name);
2609 dump_constraint (dump_file, c);
2610 fprintf (dump_file, "\n");
2612 constraints[i] = NULL;
2613 continue;
2616 if (rhslabel == 0)
2618 if (dump_file && (dump_flags & TDF_DETAILS))
2621 fprintf (dump_file, "%s is a non-pointer variable,"
2622 "ignoring constraint:",
2623 get_varinfo (rhs.var)->name);
2624 dump_constraint (dump_file, c);
2625 fprintf (dump_file, "\n");
2627 constraints[i] = NULL;
2628 continue;
2631 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2632 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2633 c->lhs.var = lhsvar;
2634 c->rhs.var = rhsvar;
2638 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2639 part of an SCC, false otherwise. */
2641 static bool
2642 eliminate_indirect_cycles (unsigned int node)
2644 if (graph->indirect_cycles[node] != -1
2645 && !bitmap_empty_p (get_varinfo (node)->solution))
2647 unsigned int i;
2648 auto_vec<unsigned> queue;
2649 int queuepos;
2650 unsigned int to = find (graph->indirect_cycles[node]);
2651 bitmap_iterator bi;
2653 /* We can't touch the solution set and call unify_nodes
2654 at the same time, because unify_nodes is going to do
2655 bitmap unions into it. */
2657 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2659 if (find (i) == i && i != to)
2661 if (unite (to, i))
2662 queue.safe_push (i);
2666 for (queuepos = 0;
2667 queue.iterate (queuepos, &i);
2668 queuepos++)
2670 unify_nodes (graph, to, i, true);
2672 return true;
2674 return false;
2677 /* Solve the constraint graph GRAPH using our worklist solver.
2678 This is based on the PW* family of solvers from the "Efficient Field
2679 Sensitive Pointer Analysis for C" paper.
2680 It works by iterating over all the graph nodes, processing the complex
2681 constraints and propagating the copy constraints, until everything stops
2682 changed. This corresponds to steps 6-8 in the solving list given above. */
2684 static void
2685 solve_graph (constraint_graph_t graph)
2687 unsigned int size = graph->size;
2688 unsigned int i;
2689 bitmap pts;
2691 changed = BITMAP_ALLOC (NULL);
2693 /* Mark all initial non-collapsed nodes as changed. */
2694 for (i = 1; i < size; i++)
2696 varinfo_t ivi = get_varinfo (i);
2697 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2698 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2699 || graph->complex[i].length () > 0))
2700 bitmap_set_bit (changed, i);
2703 /* Allocate a bitmap to be used to store the changed bits. */
2704 pts = BITMAP_ALLOC (&pta_obstack);
2706 while (!bitmap_empty_p (changed))
2708 unsigned int i;
2709 struct topo_info *ti = init_topo_info ();
2710 stats.iterations++;
2712 bitmap_obstack_initialize (&iteration_obstack);
2714 compute_topo_order (graph, ti);
2716 while (ti->topo_order.length () != 0)
2719 i = ti->topo_order.pop ();
2721 /* If this variable is not a representative, skip it. */
2722 if (find (i) != i)
2723 continue;
2725 /* In certain indirect cycle cases, we may merge this
2726 variable to another. */
2727 if (eliminate_indirect_cycles (i) && find (i) != i)
2728 continue;
2730 /* If the node has changed, we need to process the
2731 complex constraints and outgoing edges again. */
2732 if (bitmap_clear_bit (changed, i))
2734 unsigned int j;
2735 constraint_t c;
2736 bitmap solution;
2737 vec<constraint_t> complex = graph->complex[i];
2738 varinfo_t vi = get_varinfo (i);
2739 bool solution_empty;
2741 /* Compute the changed set of solution bits. If anything
2742 is in the solution just propagate that. */
2743 if (bitmap_bit_p (vi->solution, anything_id))
2745 /* If anything is also in the old solution there is
2746 nothing to do.
2747 ??? But we shouldn't ended up with "changed" set ... */
2748 if (vi->oldsolution
2749 && bitmap_bit_p (vi->oldsolution, anything_id))
2750 continue;
2751 bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2753 else if (vi->oldsolution)
2754 bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2755 else
2756 bitmap_copy (pts, vi->solution);
2758 if (bitmap_empty_p (pts))
2759 continue;
2761 if (vi->oldsolution)
2762 bitmap_ior_into (vi->oldsolution, pts);
2763 else
2765 vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2766 bitmap_copy (vi->oldsolution, pts);
2769 solution = vi->solution;
2770 solution_empty = bitmap_empty_p (solution);
2772 /* Process the complex constraints */
2773 bitmap expanded_pts = NULL;
2774 FOR_EACH_VEC_ELT (complex, j, c)
2776 /* XXX: This is going to unsort the constraints in
2777 some cases, which will occasionally add duplicate
2778 constraints during unification. This does not
2779 affect correctness. */
2780 c->lhs.var = find (c->lhs.var);
2781 c->rhs.var = find (c->rhs.var);
2783 /* The only complex constraint that can change our
2784 solution to non-empty, given an empty solution,
2785 is a constraint where the lhs side is receiving
2786 some set from elsewhere. */
2787 if (!solution_empty || c->lhs.type != DEREF)
2788 do_complex_constraint (graph, c, pts, &expanded_pts);
2790 BITMAP_FREE (expanded_pts);
2792 solution_empty = bitmap_empty_p (solution);
2794 if (!solution_empty)
2796 bitmap_iterator bi;
2797 unsigned eff_escaped_id = find (escaped_id);
2799 /* Propagate solution to all successors. */
2800 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2801 0, j, bi)
2803 bitmap tmp;
2804 bool flag;
2806 unsigned int to = find (j);
2807 tmp = get_varinfo (to)->solution;
2808 flag = false;
2810 /* Don't try to propagate to ourselves. */
2811 if (to == i)
2812 continue;
2814 /* If we propagate from ESCAPED use ESCAPED as
2815 placeholder. */
2816 if (i == eff_escaped_id)
2817 flag = bitmap_set_bit (tmp, escaped_id);
2818 else
2819 flag = bitmap_ior_into (tmp, pts);
2821 if (flag)
2822 bitmap_set_bit (changed, to);
2827 free_topo_info (ti);
2828 bitmap_obstack_release (&iteration_obstack);
2831 BITMAP_FREE (pts);
2832 BITMAP_FREE (changed);
2833 bitmap_obstack_release (&oldpta_obstack);
2836 /* Map from trees to variable infos. */
2837 static hash_map<tree, varinfo_t> *vi_for_tree;
2840 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2842 static void
2843 insert_vi_for_tree (tree t, varinfo_t vi)
2845 gcc_assert (vi);
2846 gcc_assert (!vi_for_tree->put (t, vi));
2849 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2850 exist in the map, return NULL, otherwise, return the varinfo we found. */
2852 static varinfo_t
2853 lookup_vi_for_tree (tree t)
2855 varinfo_t *slot = vi_for_tree->get (t);
2856 if (slot == NULL)
2857 return NULL;
2859 return *slot;
2862 /* Return a printable name for DECL */
2864 static const char *
2865 alias_get_name (tree decl)
2867 const char *res = NULL;
2868 char *temp;
2869 int num_printed = 0;
2871 if (!dump_file)
2872 return "NULL";
2874 if (TREE_CODE (decl) == SSA_NAME)
2876 res = get_name (decl);
2877 if (res)
2878 num_printed = asprintf (&temp, "%s_%u", res, SSA_NAME_VERSION (decl));
2879 else
2880 num_printed = asprintf (&temp, "_%u", SSA_NAME_VERSION (decl));
2881 if (num_printed > 0)
2883 res = ggc_strdup (temp);
2884 free (temp);
2887 else if (DECL_P (decl))
2889 if (DECL_ASSEMBLER_NAME_SET_P (decl))
2890 res = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
2891 else
2893 res = get_name (decl);
2894 if (!res)
2896 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2897 if (num_printed > 0)
2899 res = ggc_strdup (temp);
2900 free (temp);
2905 if (res != NULL)
2906 return res;
2908 return "NULL";
2911 /* Find the variable id for tree T in the map.
2912 If T doesn't exist in the map, create an entry for it and return it. */
2914 static varinfo_t
2915 get_vi_for_tree (tree t)
2917 varinfo_t *slot = vi_for_tree->get (t);
2918 if (slot == NULL)
2919 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2921 return *slot;
2924 /* Get a scalar constraint expression for a new temporary variable. */
2926 static struct constraint_expr
2927 new_scalar_tmp_constraint_exp (const char *name)
2929 struct constraint_expr tmp;
2930 varinfo_t vi;
2932 vi = new_var_info (NULL_TREE, name);
2933 vi->offset = 0;
2934 vi->size = -1;
2935 vi->fullsize = -1;
2936 vi->is_full_var = 1;
2938 tmp.var = vi->id;
2939 tmp.type = SCALAR;
2940 tmp.offset = 0;
2942 return tmp;
2945 /* Get a constraint expression vector from an SSA_VAR_P node.
2946 If address_p is true, the result will be taken its address of. */
2948 static void
2949 get_constraint_for_ssa_var (tree t, vec<ce_s> *results, bool address_p)
2951 struct constraint_expr cexpr;
2952 varinfo_t vi;
2954 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2955 gcc_assert (TREE_CODE (t) == SSA_NAME || DECL_P (t));
2957 /* For parameters, get at the points-to set for the actual parm
2958 decl. */
2959 if (TREE_CODE (t) == SSA_NAME
2960 && SSA_NAME_IS_DEFAULT_DEF (t)
2961 && (TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2962 || TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL))
2964 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2965 return;
2968 /* For global variables resort to the alias target. */
2969 if (TREE_CODE (t) == VAR_DECL
2970 && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
2972 varpool_node *node = varpool_node::get (t);
2973 if (node && node->alias && node->analyzed)
2975 node = node->ultimate_alias_target ();
2976 t = node->decl;
2980 vi = get_vi_for_tree (t);
2981 cexpr.var = vi->id;
2982 cexpr.type = SCALAR;
2983 cexpr.offset = 0;
2985 /* If we are not taking the address of the constraint expr, add all
2986 sub-fiels of the variable as well. */
2987 if (!address_p
2988 && !vi->is_full_var)
2990 for (; vi; vi = vi_next (vi))
2992 cexpr.var = vi->id;
2993 results->safe_push (cexpr);
2995 return;
2998 results->safe_push (cexpr);
3001 /* Process constraint T, performing various simplifications and then
3002 adding it to our list of overall constraints. */
3004 static void
3005 process_constraint (constraint_t t)
3007 struct constraint_expr rhs = t->rhs;
3008 struct constraint_expr lhs = t->lhs;
3010 gcc_assert (rhs.var < varmap.length ());
3011 gcc_assert (lhs.var < varmap.length ());
3013 /* If we didn't get any useful constraint from the lhs we get
3014 &ANYTHING as fallback from get_constraint_for. Deal with
3015 it here by turning it into *ANYTHING. */
3016 if (lhs.type == ADDRESSOF
3017 && lhs.var == anything_id)
3018 lhs.type = DEREF;
3020 /* ADDRESSOF on the lhs is invalid. */
3021 gcc_assert (lhs.type != ADDRESSOF);
3023 /* We shouldn't add constraints from things that cannot have pointers.
3024 It's not completely trivial to avoid in the callers, so do it here. */
3025 if (rhs.type != ADDRESSOF
3026 && !get_varinfo (rhs.var)->may_have_pointers)
3027 return;
3029 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3030 if (!get_varinfo (lhs.var)->may_have_pointers)
3031 return;
3033 /* This can happen in our IR with things like n->a = *p */
3034 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
3036 /* Split into tmp = *rhs, *lhs = tmp */
3037 struct constraint_expr tmplhs;
3038 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
3039 process_constraint (new_constraint (tmplhs, rhs));
3040 process_constraint (new_constraint (lhs, tmplhs));
3042 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
3044 /* Split into tmp = &rhs, *lhs = tmp */
3045 struct constraint_expr tmplhs;
3046 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
3047 process_constraint (new_constraint (tmplhs, rhs));
3048 process_constraint (new_constraint (lhs, tmplhs));
3050 else
3052 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
3053 constraints.safe_push (t);
3058 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3059 structure. */
3061 static HOST_WIDE_INT
3062 bitpos_of_field (const tree fdecl)
3064 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl))
3065 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl)))
3066 return -1;
3068 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT
3069 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl)));
3073 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3074 resulting constraint expressions in *RESULTS. */
3076 static void
3077 get_constraint_for_ptr_offset (tree ptr, tree offset,
3078 vec<ce_s> *results)
3080 struct constraint_expr c;
3081 unsigned int j, n;
3082 HOST_WIDE_INT rhsoffset;
3084 /* If we do not do field-sensitive PTA adding offsets to pointers
3085 does not change the points-to solution. */
3086 if (!use_field_sensitive)
3088 get_constraint_for_rhs (ptr, results);
3089 return;
3092 /* If the offset is not a non-negative integer constant that fits
3093 in a HOST_WIDE_INT, we have to fall back to a conservative
3094 solution which includes all sub-fields of all pointed-to
3095 variables of ptr. */
3096 if (offset == NULL_TREE
3097 || TREE_CODE (offset) != INTEGER_CST)
3098 rhsoffset = UNKNOWN_OFFSET;
3099 else
3101 /* Sign-extend the offset. */
3102 offset_int soffset = offset_int::from (offset, SIGNED);
3103 if (!wi::fits_shwi_p (soffset))
3104 rhsoffset = UNKNOWN_OFFSET;
3105 else
3107 /* Make sure the bit-offset also fits. */
3108 HOST_WIDE_INT rhsunitoffset = soffset.to_shwi ();
3109 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
3110 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
3111 rhsoffset = UNKNOWN_OFFSET;
3115 get_constraint_for_rhs (ptr, results);
3116 if (rhsoffset == 0)
3117 return;
3119 /* As we are eventually appending to the solution do not use
3120 vec::iterate here. */
3121 n = results->length ();
3122 for (j = 0; j < n; j++)
3124 varinfo_t curr;
3125 c = (*results)[j];
3126 curr = get_varinfo (c.var);
3128 if (c.type == ADDRESSOF
3129 /* If this varinfo represents a full variable just use it. */
3130 && curr->is_full_var)
3132 else if (c.type == ADDRESSOF
3133 /* If we do not know the offset add all subfields. */
3134 && rhsoffset == UNKNOWN_OFFSET)
3136 varinfo_t temp = get_varinfo (curr->head);
3139 struct constraint_expr c2;
3140 c2.var = temp->id;
3141 c2.type = ADDRESSOF;
3142 c2.offset = 0;
3143 if (c2.var != c.var)
3144 results->safe_push (c2);
3145 temp = vi_next (temp);
3147 while (temp);
3149 else if (c.type == ADDRESSOF)
3151 varinfo_t temp;
3152 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
3154 /* If curr->offset + rhsoffset is less than zero adjust it. */
3155 if (rhsoffset < 0
3156 && curr->offset < offset)
3157 offset = 0;
3159 /* We have to include all fields that overlap the current
3160 field shifted by rhsoffset. And we include at least
3161 the last or the first field of the variable to represent
3162 reachability of off-bound addresses, in particular &object + 1,
3163 conservatively correct. */
3164 temp = first_or_preceding_vi_for_offset (curr, offset);
3165 c.var = temp->id;
3166 c.offset = 0;
3167 temp = vi_next (temp);
3168 while (temp
3169 && temp->offset < offset + curr->size)
3171 struct constraint_expr c2;
3172 c2.var = temp->id;
3173 c2.type = ADDRESSOF;
3174 c2.offset = 0;
3175 results->safe_push (c2);
3176 temp = vi_next (temp);
3179 else if (c.type == SCALAR)
3181 gcc_assert (c.offset == 0);
3182 c.offset = rhsoffset;
3184 else
3185 /* We shouldn't get any DEREFs here. */
3186 gcc_unreachable ();
3188 (*results)[j] = c;
3193 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3194 If address_p is true the result will be taken its address of.
3195 If lhs_p is true then the constraint expression is assumed to be used
3196 as the lhs. */
3198 static void
3199 get_constraint_for_component_ref (tree t, vec<ce_s> *results,
3200 bool address_p, bool lhs_p)
3202 tree orig_t = t;
3203 HOST_WIDE_INT bitsize = -1;
3204 HOST_WIDE_INT bitmaxsize = -1;
3205 HOST_WIDE_INT bitpos;
3206 tree forzero;
3208 /* Some people like to do cute things like take the address of
3209 &0->a.b */
3210 forzero = t;
3211 while (handled_component_p (forzero)
3212 || INDIRECT_REF_P (forzero)
3213 || TREE_CODE (forzero) == MEM_REF)
3214 forzero = TREE_OPERAND (forzero, 0);
3216 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3218 struct constraint_expr temp;
3220 temp.offset = 0;
3221 temp.var = integer_id;
3222 temp.type = SCALAR;
3223 results->safe_push (temp);
3224 return;
3227 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
3229 /* Pretend to take the address of the base, we'll take care of
3230 adding the required subset of sub-fields below. */
3231 get_constraint_for_1 (t, results, true, lhs_p);
3232 gcc_assert (results->length () == 1);
3233 struct constraint_expr &result = results->last ();
3235 if (result.type == SCALAR
3236 && get_varinfo (result.var)->is_full_var)
3237 /* For single-field vars do not bother about the offset. */
3238 result.offset = 0;
3239 else if (result.type == SCALAR)
3241 /* In languages like C, you can access one past the end of an
3242 array. You aren't allowed to dereference it, so we can
3243 ignore this constraint. When we handle pointer subtraction,
3244 we may have to do something cute here. */
3246 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result.var)->fullsize
3247 && bitmaxsize != 0)
3249 /* It's also not true that the constraint will actually start at the
3250 right offset, it may start in some padding. We only care about
3251 setting the constraint to the first actual field it touches, so
3252 walk to find it. */
3253 struct constraint_expr cexpr = result;
3254 varinfo_t curr;
3255 results->pop ();
3256 cexpr.offset = 0;
3257 for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr))
3259 if (ranges_overlap_p (curr->offset, curr->size,
3260 bitpos, bitmaxsize))
3262 cexpr.var = curr->id;
3263 results->safe_push (cexpr);
3264 if (address_p)
3265 break;
3268 /* If we are going to take the address of this field then
3269 to be able to compute reachability correctly add at least
3270 the last field of the variable. */
3271 if (address_p && results->length () == 0)
3273 curr = get_varinfo (cexpr.var);
3274 while (curr->next != 0)
3275 curr = vi_next (curr);
3276 cexpr.var = curr->id;
3277 results->safe_push (cexpr);
3279 else if (results->length () == 0)
3280 /* Assert that we found *some* field there. The user couldn't be
3281 accessing *only* padding. */
3282 /* Still the user could access one past the end of an array
3283 embedded in a struct resulting in accessing *only* padding. */
3284 /* Or accessing only padding via type-punning to a type
3285 that has a filed just in padding space. */
3287 cexpr.type = SCALAR;
3288 cexpr.var = anything_id;
3289 cexpr.offset = 0;
3290 results->safe_push (cexpr);
3293 else if (bitmaxsize == 0)
3295 if (dump_file && (dump_flags & TDF_DETAILS))
3296 fprintf (dump_file, "Access to zero-sized part of variable,"
3297 "ignoring\n");
3299 else
3300 if (dump_file && (dump_flags & TDF_DETAILS))
3301 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3303 else if (result.type == DEREF)
3305 /* If we do not know exactly where the access goes say so. Note
3306 that only for non-structure accesses we know that we access
3307 at most one subfiled of any variable. */
3308 if (bitpos == -1
3309 || bitsize != bitmaxsize
3310 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t))
3311 || result.offset == UNKNOWN_OFFSET)
3312 result.offset = UNKNOWN_OFFSET;
3313 else
3314 result.offset += bitpos;
3316 else if (result.type == ADDRESSOF)
3318 /* We can end up here for component references on a
3319 VIEW_CONVERT_EXPR <>(&foobar). */
3320 result.type = SCALAR;
3321 result.var = anything_id;
3322 result.offset = 0;
3324 else
3325 gcc_unreachable ();
3329 /* Dereference the constraint expression CONS, and return the result.
3330 DEREF (ADDRESSOF) = SCALAR
3331 DEREF (SCALAR) = DEREF
3332 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3333 This is needed so that we can handle dereferencing DEREF constraints. */
3335 static void
3336 do_deref (vec<ce_s> *constraints)
3338 struct constraint_expr *c;
3339 unsigned int i = 0;
3341 FOR_EACH_VEC_ELT (*constraints, i, c)
3343 if (c->type == SCALAR)
3344 c->type = DEREF;
3345 else if (c->type == ADDRESSOF)
3346 c->type = SCALAR;
3347 else if (c->type == DEREF)
3349 struct constraint_expr tmplhs;
3350 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3351 process_constraint (new_constraint (tmplhs, *c));
3352 c->var = tmplhs.var;
3354 else
3355 gcc_unreachable ();
3359 /* Given a tree T, return the constraint expression for taking the
3360 address of it. */
3362 static void
3363 get_constraint_for_address_of (tree t, vec<ce_s> *results)
3365 struct constraint_expr *c;
3366 unsigned int i;
3368 get_constraint_for_1 (t, results, true, true);
3370 FOR_EACH_VEC_ELT (*results, i, c)
3372 if (c->type == DEREF)
3373 c->type = SCALAR;
3374 else
3375 c->type = ADDRESSOF;
3379 /* Given a tree T, return the constraint expression for it. */
3381 static void
3382 get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p,
3383 bool lhs_p)
3385 struct constraint_expr temp;
3387 /* x = integer is all glommed to a single variable, which doesn't
3388 point to anything by itself. That is, of course, unless it is an
3389 integer constant being treated as a pointer, in which case, we
3390 will return that this is really the addressof anything. This
3391 happens below, since it will fall into the default case. The only
3392 case we know something about an integer treated like a pointer is
3393 when it is the NULL pointer, and then we just say it points to
3394 NULL.
3396 Do not do that if -fno-delete-null-pointer-checks though, because
3397 in that case *NULL does not fail, so it _should_ alias *anything.
3398 It is not worth adding a new option or renaming the existing one,
3399 since this case is relatively obscure. */
3400 if ((TREE_CODE (t) == INTEGER_CST
3401 && integer_zerop (t))
3402 /* The only valid CONSTRUCTORs in gimple with pointer typed
3403 elements are zero-initializer. But in IPA mode we also
3404 process global initializers, so verify at least. */
3405 || (TREE_CODE (t) == CONSTRUCTOR
3406 && CONSTRUCTOR_NELTS (t) == 0))
3408 if (flag_delete_null_pointer_checks)
3409 temp.var = nothing_id;
3410 else
3411 temp.var = nonlocal_id;
3412 temp.type = ADDRESSOF;
3413 temp.offset = 0;
3414 results->safe_push (temp);
3415 return;
3418 /* String constants are read-only, ideally we'd have a CONST_DECL
3419 for those. */
3420 if (TREE_CODE (t) == STRING_CST)
3422 temp.var = string_id;
3423 temp.type = SCALAR;
3424 temp.offset = 0;
3425 results->safe_push (temp);
3426 return;
3429 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3431 case tcc_expression:
3433 switch (TREE_CODE (t))
3435 case ADDR_EXPR:
3436 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3437 return;
3438 default:;
3440 break;
3442 case tcc_reference:
3444 switch (TREE_CODE (t))
3446 case MEM_REF:
3448 struct constraint_expr cs;
3449 varinfo_t vi, curr;
3450 get_constraint_for_ptr_offset (TREE_OPERAND (t, 0),
3451 TREE_OPERAND (t, 1), results);
3452 do_deref (results);
3454 /* If we are not taking the address then make sure to process
3455 all subvariables we might access. */
3456 if (address_p)
3457 return;
3459 cs = results->last ();
3460 if (cs.type == DEREF
3461 && type_can_have_subvars (TREE_TYPE (t)))
3463 /* For dereferences this means we have to defer it
3464 to solving time. */
3465 results->last ().offset = UNKNOWN_OFFSET;
3466 return;
3468 if (cs.type != SCALAR)
3469 return;
3471 vi = get_varinfo (cs.var);
3472 curr = vi_next (vi);
3473 if (!vi->is_full_var
3474 && curr)
3476 unsigned HOST_WIDE_INT size;
3477 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t))))
3478 size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t)));
3479 else
3480 size = -1;
3481 for (; curr; curr = vi_next (curr))
3483 if (curr->offset - vi->offset < size)
3485 cs.var = curr->id;
3486 results->safe_push (cs);
3488 else
3489 break;
3492 return;
3494 case ARRAY_REF:
3495 case ARRAY_RANGE_REF:
3496 case COMPONENT_REF:
3497 case IMAGPART_EXPR:
3498 case REALPART_EXPR:
3499 case BIT_FIELD_REF:
3500 get_constraint_for_component_ref (t, results, address_p, lhs_p);
3501 return;
3502 case VIEW_CONVERT_EXPR:
3503 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p,
3504 lhs_p);
3505 return;
3506 /* We are missing handling for TARGET_MEM_REF here. */
3507 default:;
3509 break;
3511 case tcc_exceptional:
3513 switch (TREE_CODE (t))
3515 case SSA_NAME:
3517 get_constraint_for_ssa_var (t, results, address_p);
3518 return;
3520 case CONSTRUCTOR:
3522 unsigned int i;
3523 tree val;
3524 auto_vec<ce_s> tmp;
3525 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val)
3527 struct constraint_expr *rhsp;
3528 unsigned j;
3529 get_constraint_for_1 (val, &tmp, address_p, lhs_p);
3530 FOR_EACH_VEC_ELT (tmp, j, rhsp)
3531 results->safe_push (*rhsp);
3532 tmp.truncate (0);
3534 /* We do not know whether the constructor was complete,
3535 so technically we have to add &NOTHING or &ANYTHING
3536 like we do for an empty constructor as well. */
3537 return;
3539 default:;
3541 break;
3543 case tcc_declaration:
3545 get_constraint_for_ssa_var (t, results, address_p);
3546 return;
3548 case tcc_constant:
3550 /* We cannot refer to automatic variables through constants. */
3551 temp.type = ADDRESSOF;
3552 temp.var = nonlocal_id;
3553 temp.offset = 0;
3554 results->safe_push (temp);
3555 return;
3557 default:;
3560 /* The default fallback is a constraint from anything. */
3561 temp.type = ADDRESSOF;
3562 temp.var = anything_id;
3563 temp.offset = 0;
3564 results->safe_push (temp);
3567 /* Given a gimple tree T, return the constraint expression vector for it. */
3569 static void
3570 get_constraint_for (tree t, vec<ce_s> *results)
3572 gcc_assert (results->length () == 0);
3574 get_constraint_for_1 (t, results, false, true);
3577 /* Given a gimple tree T, return the constraint expression vector for it
3578 to be used as the rhs of a constraint. */
3580 static void
3581 get_constraint_for_rhs (tree t, vec<ce_s> *results)
3583 gcc_assert (results->length () == 0);
3585 get_constraint_for_1 (t, results, false, false);
3589 /* Efficiently generates constraints from all entries in *RHSC to all
3590 entries in *LHSC. */
3592 static void
3593 process_all_all_constraints (vec<ce_s> lhsc,
3594 vec<ce_s> rhsc)
3596 struct constraint_expr *lhsp, *rhsp;
3597 unsigned i, j;
3599 if (lhsc.length () <= 1 || rhsc.length () <= 1)
3601 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3602 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
3603 process_constraint (new_constraint (*lhsp, *rhsp));
3605 else
3607 struct constraint_expr tmp;
3608 tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3609 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
3610 process_constraint (new_constraint (tmp, *rhsp));
3611 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3612 process_constraint (new_constraint (*lhsp, tmp));
3616 /* Handle aggregate copies by expanding into copies of the respective
3617 fields of the structures. */
3619 static void
3620 do_structure_copy (tree lhsop, tree rhsop)
3622 struct constraint_expr *lhsp, *rhsp;
3623 auto_vec<ce_s> lhsc;
3624 auto_vec<ce_s> rhsc;
3625 unsigned j;
3627 get_constraint_for (lhsop, &lhsc);
3628 get_constraint_for_rhs (rhsop, &rhsc);
3629 lhsp = &lhsc[0];
3630 rhsp = &rhsc[0];
3631 if (lhsp->type == DEREF
3632 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3633 || rhsp->type == DEREF)
3635 if (lhsp->type == DEREF)
3637 gcc_assert (lhsc.length () == 1);
3638 lhsp->offset = UNKNOWN_OFFSET;
3640 if (rhsp->type == DEREF)
3642 gcc_assert (rhsc.length () == 1);
3643 rhsp->offset = UNKNOWN_OFFSET;
3645 process_all_all_constraints (lhsc, rhsc);
3647 else if (lhsp->type == SCALAR
3648 && (rhsp->type == SCALAR
3649 || rhsp->type == ADDRESSOF))
3651 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3652 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3653 unsigned k = 0;
3654 get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize);
3655 get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize);
3656 for (j = 0; lhsc.iterate (j, &lhsp);)
3658 varinfo_t lhsv, rhsv;
3659 rhsp = &rhsc[k];
3660 lhsv = get_varinfo (lhsp->var);
3661 rhsv = get_varinfo (rhsp->var);
3662 if (lhsv->may_have_pointers
3663 && (lhsv->is_full_var
3664 || rhsv->is_full_var
3665 || ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3666 rhsv->offset + lhsoffset, rhsv->size)))
3667 process_constraint (new_constraint (*lhsp, *rhsp));
3668 if (!rhsv->is_full_var
3669 && (lhsv->is_full_var
3670 || (lhsv->offset + rhsoffset + lhsv->size
3671 > rhsv->offset + lhsoffset + rhsv->size)))
3673 ++k;
3674 if (k >= rhsc.length ())
3675 break;
3677 else
3678 ++j;
3681 else
3682 gcc_unreachable ();
3685 /* Create constraints ID = { rhsc }. */
3687 static void
3688 make_constraints_to (unsigned id, vec<ce_s> rhsc)
3690 struct constraint_expr *c;
3691 struct constraint_expr includes;
3692 unsigned int j;
3694 includes.var = id;
3695 includes.offset = 0;
3696 includes.type = SCALAR;
3698 FOR_EACH_VEC_ELT (rhsc, j, c)
3699 process_constraint (new_constraint (includes, *c));
3702 /* Create a constraint ID = OP. */
3704 static void
3705 make_constraint_to (unsigned id, tree op)
3707 auto_vec<ce_s> rhsc;
3708 get_constraint_for_rhs (op, &rhsc);
3709 make_constraints_to (id, rhsc);
3712 /* Create a constraint ID = &FROM. */
3714 static void
3715 make_constraint_from (varinfo_t vi, int from)
3717 struct constraint_expr lhs, rhs;
3719 lhs.var = vi->id;
3720 lhs.offset = 0;
3721 lhs.type = SCALAR;
3723 rhs.var = from;
3724 rhs.offset = 0;
3725 rhs.type = ADDRESSOF;
3726 process_constraint (new_constraint (lhs, rhs));
3729 /* Create a constraint ID = FROM. */
3731 static void
3732 make_copy_constraint (varinfo_t vi, int from)
3734 struct constraint_expr lhs, rhs;
3736 lhs.var = vi->id;
3737 lhs.offset = 0;
3738 lhs.type = SCALAR;
3740 rhs.var = from;
3741 rhs.offset = 0;
3742 rhs.type = SCALAR;
3743 process_constraint (new_constraint (lhs, rhs));
3746 /* Make constraints necessary to make OP escape. */
3748 static void
3749 make_escape_constraint (tree op)
3751 make_constraint_to (escaped_id, op);
3754 /* Add constraints to that the solution of VI is transitively closed. */
3756 static void
3757 make_transitive_closure_constraints (varinfo_t vi)
3759 struct constraint_expr lhs, rhs;
3761 /* VAR = *VAR; */
3762 lhs.type = SCALAR;
3763 lhs.var = vi->id;
3764 lhs.offset = 0;
3765 rhs.type = DEREF;
3766 rhs.var = vi->id;
3767 rhs.offset = UNKNOWN_OFFSET;
3768 process_constraint (new_constraint (lhs, rhs));
3771 /* Temporary storage for fake var decls. */
3772 struct obstack fake_var_decl_obstack;
3774 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3776 static tree
3777 build_fake_var_decl (tree type)
3779 tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
3780 memset (decl, 0, sizeof (struct tree_var_decl));
3781 TREE_SET_CODE (decl, VAR_DECL);
3782 TREE_TYPE (decl) = type;
3783 DECL_UID (decl) = allocate_decl_uid ();
3784 SET_DECL_PT_UID (decl, -1);
3785 layout_decl (decl, 0);
3786 return decl;
3789 /* Create a new artificial heap variable with NAME.
3790 Return the created variable. */
3792 static varinfo_t
3793 make_heapvar (const char *name)
3795 varinfo_t vi;
3796 tree heapvar;
3798 heapvar = build_fake_var_decl (ptr_type_node);
3799 DECL_EXTERNAL (heapvar) = 1;
3801 vi = new_var_info (heapvar, name);
3802 vi->is_artificial_var = true;
3803 vi->is_heap_var = true;
3804 vi->is_unknown_size_var = true;
3805 vi->offset = 0;
3806 vi->fullsize = ~0;
3807 vi->size = ~0;
3808 vi->is_full_var = true;
3809 insert_vi_for_tree (heapvar, vi);
3811 return vi;
3814 /* Create a new artificial heap variable with NAME and make a
3815 constraint from it to LHS. Set flags according to a tag used
3816 for tracking restrict pointers. */
3818 static varinfo_t
3819 make_constraint_from_restrict (varinfo_t lhs, const char *name)
3821 varinfo_t vi = make_heapvar (name);
3822 vi->is_restrict_var = 1;
3823 vi->is_global_var = 1;
3824 vi->may_have_pointers = 1;
3825 make_constraint_from (lhs, vi->id);
3826 return vi;
3829 /* Create a new artificial heap variable with NAME and make a
3830 constraint from it to LHS. Set flags according to a tag used
3831 for tracking restrict pointers and make the artificial heap
3832 point to global memory. */
3834 static varinfo_t
3835 make_constraint_from_global_restrict (varinfo_t lhs, const char *name)
3837 varinfo_t vi = make_constraint_from_restrict (lhs, name);
3838 make_copy_constraint (vi, nonlocal_id);
3839 return vi;
3842 /* In IPA mode there are varinfos for different aspects of reach
3843 function designator. One for the points-to set of the return
3844 value, one for the variables that are clobbered by the function,
3845 one for its uses and one for each parameter (including a single
3846 glob for remaining variadic arguments). */
3848 enum { fi_clobbers = 1, fi_uses = 2,
3849 fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 };
3851 /* Get a constraint for the requested part of a function designator FI
3852 when operating in IPA mode. */
3854 static struct constraint_expr
3855 get_function_part_constraint (varinfo_t fi, unsigned part)
3857 struct constraint_expr c;
3859 gcc_assert (in_ipa_mode);
3861 if (fi->id == anything_id)
3863 /* ??? We probably should have a ANYFN special variable. */
3864 c.var = anything_id;
3865 c.offset = 0;
3866 c.type = SCALAR;
3868 else if (TREE_CODE (fi->decl) == FUNCTION_DECL)
3870 varinfo_t ai = first_vi_for_offset (fi, part);
3871 if (ai)
3872 c.var = ai->id;
3873 else
3874 c.var = anything_id;
3875 c.offset = 0;
3876 c.type = SCALAR;
3878 else
3880 c.var = fi->id;
3881 c.offset = part;
3882 c.type = DEREF;
3885 return c;
3888 /* For non-IPA mode, generate constraints necessary for a call on the
3889 RHS. */
3891 static void
3892 handle_rhs_call (gcall *stmt, vec<ce_s> *results)
3894 struct constraint_expr rhsc;
3895 unsigned i;
3896 bool returns_uses = false;
3898 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3900 tree arg = gimple_call_arg (stmt, i);
3901 int flags = gimple_call_arg_flags (stmt, i);
3903 /* If the argument is not used we can ignore it. */
3904 if (flags & EAF_UNUSED)
3905 continue;
3907 /* As we compute ESCAPED context-insensitive we do not gain
3908 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3909 set. The argument would still get clobbered through the
3910 escape solution. */
3911 if ((flags & EAF_NOCLOBBER)
3912 && (flags & EAF_NOESCAPE))
3914 varinfo_t uses = get_call_use_vi (stmt);
3915 if (!(flags & EAF_DIRECT))
3917 varinfo_t tem = new_var_info (NULL_TREE, "callarg");
3918 make_constraint_to (tem->id, arg);
3919 make_transitive_closure_constraints (tem);
3920 make_copy_constraint (uses, tem->id);
3922 else
3923 make_constraint_to (uses->id, arg);
3924 returns_uses = true;
3926 else if (flags & EAF_NOESCAPE)
3928 struct constraint_expr lhs, rhs;
3929 varinfo_t uses = get_call_use_vi (stmt);
3930 varinfo_t clobbers = get_call_clobber_vi (stmt);
3931 varinfo_t tem = new_var_info (NULL_TREE, "callarg");
3932 make_constraint_to (tem->id, arg);
3933 if (!(flags & EAF_DIRECT))
3934 make_transitive_closure_constraints (tem);
3935 make_copy_constraint (uses, tem->id);
3936 make_copy_constraint (clobbers, tem->id);
3937 /* Add *tem = nonlocal, do not add *tem = callused as
3938 EAF_NOESCAPE parameters do not escape to other parameters
3939 and all other uses appear in NONLOCAL as well. */
3940 lhs.type = DEREF;
3941 lhs.var = tem->id;
3942 lhs.offset = 0;
3943 rhs.type = SCALAR;
3944 rhs.var = nonlocal_id;
3945 rhs.offset = 0;
3946 process_constraint (new_constraint (lhs, rhs));
3947 returns_uses = true;
3949 else
3950 make_escape_constraint (arg);
3953 /* If we added to the calls uses solution make sure we account for
3954 pointers to it to be returned. */
3955 if (returns_uses)
3957 rhsc.var = get_call_use_vi (stmt)->id;
3958 rhsc.offset = 0;
3959 rhsc.type = SCALAR;
3960 results->safe_push (rhsc);
3963 /* The static chain escapes as well. */
3964 if (gimple_call_chain (stmt))
3965 make_escape_constraint (gimple_call_chain (stmt));
3967 /* And if we applied NRV the address of the return slot escapes as well. */
3968 if (gimple_call_return_slot_opt_p (stmt)
3969 && gimple_call_lhs (stmt) != NULL_TREE
3970 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
3972 auto_vec<ce_s> tmpc;
3973 struct constraint_expr lhsc, *c;
3974 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
3975 lhsc.var = escaped_id;
3976 lhsc.offset = 0;
3977 lhsc.type = SCALAR;
3978 FOR_EACH_VEC_ELT (tmpc, i, c)
3979 process_constraint (new_constraint (lhsc, *c));
3982 /* Regular functions return nonlocal memory. */
3983 rhsc.var = nonlocal_id;
3984 rhsc.offset = 0;
3985 rhsc.type = SCALAR;
3986 results->safe_push (rhsc);
3989 /* For non-IPA mode, generate constraints necessary for a call
3990 that returns a pointer and assigns it to LHS. This simply makes
3991 the LHS point to global and escaped variables. */
3993 static void
3994 handle_lhs_call (gcall *stmt, tree lhs, int flags, vec<ce_s> rhsc,
3995 tree fndecl)
3997 auto_vec<ce_s> lhsc;
3999 get_constraint_for (lhs, &lhsc);
4000 /* If the store is to a global decl make sure to
4001 add proper escape constraints. */
4002 lhs = get_base_address (lhs);
4003 if (lhs
4004 && DECL_P (lhs)
4005 && is_global_var (lhs))
4007 struct constraint_expr tmpc;
4008 tmpc.var = escaped_id;
4009 tmpc.offset = 0;
4010 tmpc.type = SCALAR;
4011 lhsc.safe_push (tmpc);
4014 /* If the call returns an argument unmodified override the rhs
4015 constraints. */
4016 if (flags & ERF_RETURNS_ARG
4017 && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
4019 tree arg;
4020 rhsc.create (0);
4021 arg = gimple_call_arg (stmt, flags & ERF_RETURN_ARG_MASK);
4022 get_constraint_for (arg, &rhsc);
4023 process_all_all_constraints (lhsc, rhsc);
4024 rhsc.release ();
4026 else if (flags & ERF_NOALIAS)
4028 varinfo_t vi;
4029 struct constraint_expr tmpc;
4030 rhsc.create (0);
4031 vi = make_heapvar ("HEAP");
4032 /* We are marking allocated storage local, we deal with it becoming
4033 global by escaping and setting of vars_contains_escaped_heap. */
4034 DECL_EXTERNAL (vi->decl) = 0;
4035 vi->is_global_var = 0;
4036 /* If this is not a real malloc call assume the memory was
4037 initialized and thus may point to global memory. All
4038 builtin functions with the malloc attribute behave in a sane way. */
4039 if (!fndecl
4040 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
4041 make_constraint_from (vi, nonlocal_id);
4042 tmpc.var = vi->id;
4043 tmpc.offset = 0;
4044 tmpc.type = ADDRESSOF;
4045 rhsc.safe_push (tmpc);
4046 process_all_all_constraints (lhsc, rhsc);
4047 rhsc.release ();
4049 else
4050 process_all_all_constraints (lhsc, rhsc);
4053 /* For non-IPA mode, generate constraints necessary for a call of a
4054 const function that returns a pointer in the statement STMT. */
4056 static void
4057 handle_const_call (gcall *stmt, vec<ce_s> *results)
4059 struct constraint_expr rhsc;
4060 unsigned int k;
4062 /* Treat nested const functions the same as pure functions as far
4063 as the static chain is concerned. */
4064 if (gimple_call_chain (stmt))
4066 varinfo_t uses = get_call_use_vi (stmt);
4067 make_transitive_closure_constraints (uses);
4068 make_constraint_to (uses->id, gimple_call_chain (stmt));
4069 rhsc.var = uses->id;
4070 rhsc.offset = 0;
4071 rhsc.type = SCALAR;
4072 results->safe_push (rhsc);
4075 /* May return arguments. */
4076 for (k = 0; k < gimple_call_num_args (stmt); ++k)
4078 tree arg = gimple_call_arg (stmt, k);
4079 auto_vec<ce_s> argc;
4080 unsigned i;
4081 struct constraint_expr *argp;
4082 get_constraint_for_rhs (arg, &argc);
4083 FOR_EACH_VEC_ELT (argc, i, argp)
4084 results->safe_push (*argp);
4087 /* May return addresses of globals. */
4088 rhsc.var = nonlocal_id;
4089 rhsc.offset = 0;
4090 rhsc.type = ADDRESSOF;
4091 results->safe_push (rhsc);
4094 /* For non-IPA mode, generate constraints necessary for a call to a
4095 pure function in statement STMT. */
4097 static void
4098 handle_pure_call (gcall *stmt, vec<ce_s> *results)
4100 struct constraint_expr rhsc;
4101 unsigned i;
4102 varinfo_t uses = NULL;
4104 /* Memory reached from pointer arguments is call-used. */
4105 for (i = 0; i < gimple_call_num_args (stmt); ++i)
4107 tree arg = gimple_call_arg (stmt, i);
4108 if (!uses)
4110 uses = get_call_use_vi (stmt);
4111 make_transitive_closure_constraints (uses);
4113 make_constraint_to (uses->id, arg);
4116 /* The static chain is used as well. */
4117 if (gimple_call_chain (stmt))
4119 if (!uses)
4121 uses = get_call_use_vi (stmt);
4122 make_transitive_closure_constraints (uses);
4124 make_constraint_to (uses->id, gimple_call_chain (stmt));
4127 /* Pure functions may return call-used and nonlocal memory. */
4128 if (uses)
4130 rhsc.var = uses->id;
4131 rhsc.offset = 0;
4132 rhsc.type = SCALAR;
4133 results->safe_push (rhsc);
4135 rhsc.var = nonlocal_id;
4136 rhsc.offset = 0;
4137 rhsc.type = SCALAR;
4138 results->safe_push (rhsc);
4142 /* Return the varinfo for the callee of CALL. */
4144 static varinfo_t
4145 get_fi_for_callee (gcall *call)
4147 tree decl, fn = gimple_call_fn (call);
4149 if (fn && TREE_CODE (fn) == OBJ_TYPE_REF)
4150 fn = OBJ_TYPE_REF_EXPR (fn);
4152 /* If we can directly resolve the function being called, do so.
4153 Otherwise, it must be some sort of indirect expression that
4154 we should still be able to handle. */
4155 decl = gimple_call_addr_fndecl (fn);
4156 if (decl)
4157 return get_vi_for_tree (decl);
4159 /* If the function is anything other than a SSA name pointer we have no
4160 clue and should be getting ANYFN (well, ANYTHING for now). */
4161 if (!fn || TREE_CODE (fn) != SSA_NAME)
4162 return get_varinfo (anything_id);
4164 if (SSA_NAME_IS_DEFAULT_DEF (fn)
4165 && (TREE_CODE (SSA_NAME_VAR (fn)) == PARM_DECL
4166 || TREE_CODE (SSA_NAME_VAR (fn)) == RESULT_DECL))
4167 fn = SSA_NAME_VAR (fn);
4169 return get_vi_for_tree (fn);
4172 /* Create constraints for the builtin call T. Return true if the call
4173 was handled, otherwise false. */
4175 static bool
4176 find_func_aliases_for_builtin_call (struct function *fn, gcall *t)
4178 tree fndecl = gimple_call_fndecl (t);
4179 auto_vec<ce_s, 2> lhsc;
4180 auto_vec<ce_s, 4> rhsc;
4181 varinfo_t fi;
4183 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
4184 /* ??? All builtins that are handled here need to be handled
4185 in the alias-oracle query functions explicitly! */
4186 switch (DECL_FUNCTION_CODE (fndecl))
4188 /* All the following functions return a pointer to the same object
4189 as their first argument points to. The functions do not add
4190 to the ESCAPED solution. The functions make the first argument
4191 pointed to memory point to what the second argument pointed to
4192 memory points to. */
4193 case BUILT_IN_STRCPY:
4194 case BUILT_IN_STRNCPY:
4195 case BUILT_IN_BCOPY:
4196 case BUILT_IN_MEMCPY:
4197 case BUILT_IN_MEMMOVE:
4198 case BUILT_IN_MEMPCPY:
4199 case BUILT_IN_STPCPY:
4200 case BUILT_IN_STPNCPY:
4201 case BUILT_IN_STRCAT:
4202 case BUILT_IN_STRNCAT:
4203 case BUILT_IN_STRCPY_CHK:
4204 case BUILT_IN_STRNCPY_CHK:
4205 case BUILT_IN_MEMCPY_CHK:
4206 case BUILT_IN_MEMMOVE_CHK:
4207 case BUILT_IN_MEMPCPY_CHK:
4208 case BUILT_IN_STPCPY_CHK:
4209 case BUILT_IN_STPNCPY_CHK:
4210 case BUILT_IN_STRCAT_CHK:
4211 case BUILT_IN_STRNCAT_CHK:
4212 case BUILT_IN_TM_MEMCPY:
4213 case BUILT_IN_TM_MEMMOVE:
4215 tree res = gimple_call_lhs (t);
4216 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4217 == BUILT_IN_BCOPY ? 1 : 0));
4218 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4219 == BUILT_IN_BCOPY ? 0 : 1));
4220 if (res != NULL_TREE)
4222 get_constraint_for (res, &lhsc);
4223 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
4224 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
4225 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY
4226 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHK
4227 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY_CHK
4228 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY_CHK)
4229 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
4230 else
4231 get_constraint_for (dest, &rhsc);
4232 process_all_all_constraints (lhsc, rhsc);
4233 lhsc.truncate (0);
4234 rhsc.truncate (0);
4236 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4237 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4238 do_deref (&lhsc);
4239 do_deref (&rhsc);
4240 process_all_all_constraints (lhsc, rhsc);
4241 return true;
4243 case BUILT_IN_MEMSET:
4244 case BUILT_IN_MEMSET_CHK:
4245 case BUILT_IN_TM_MEMSET:
4247 tree res = gimple_call_lhs (t);
4248 tree dest = gimple_call_arg (t, 0);
4249 unsigned i;
4250 ce_s *lhsp;
4251 struct constraint_expr ac;
4252 if (res != NULL_TREE)
4254 get_constraint_for (res, &lhsc);
4255 get_constraint_for (dest, &rhsc);
4256 process_all_all_constraints (lhsc, rhsc);
4257 lhsc.truncate (0);
4259 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4260 do_deref (&lhsc);
4261 if (flag_delete_null_pointer_checks
4262 && integer_zerop (gimple_call_arg (t, 1)))
4264 ac.type = ADDRESSOF;
4265 ac.var = nothing_id;
4267 else
4269 ac.type = SCALAR;
4270 ac.var = integer_id;
4272 ac.offset = 0;
4273 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4274 process_constraint (new_constraint (*lhsp, ac));
4275 return true;
4277 case BUILT_IN_POSIX_MEMALIGN:
4279 tree ptrptr = gimple_call_arg (t, 0);
4280 get_constraint_for (ptrptr, &lhsc);
4281 do_deref (&lhsc);
4282 varinfo_t vi = make_heapvar ("HEAP");
4283 /* We are marking allocated storage local, we deal with it becoming
4284 global by escaping and setting of vars_contains_escaped_heap. */
4285 DECL_EXTERNAL (vi->decl) = 0;
4286 vi->is_global_var = 0;
4287 struct constraint_expr tmpc;
4288 tmpc.var = vi->id;
4289 tmpc.offset = 0;
4290 tmpc.type = ADDRESSOF;
4291 rhsc.safe_push (tmpc);
4292 process_all_all_constraints (lhsc, rhsc);
4293 return true;
4295 case BUILT_IN_ASSUME_ALIGNED:
4297 tree res = gimple_call_lhs (t);
4298 tree dest = gimple_call_arg (t, 0);
4299 if (res != NULL_TREE)
4301 get_constraint_for (res, &lhsc);
4302 get_constraint_for (dest, &rhsc);
4303 process_all_all_constraints (lhsc, rhsc);
4305 return true;
4307 /* All the following functions do not return pointers, do not
4308 modify the points-to sets of memory reachable from their
4309 arguments and do not add to the ESCAPED solution. */
4310 case BUILT_IN_SINCOS:
4311 case BUILT_IN_SINCOSF:
4312 case BUILT_IN_SINCOSL:
4313 case BUILT_IN_FREXP:
4314 case BUILT_IN_FREXPF:
4315 case BUILT_IN_FREXPL:
4316 case BUILT_IN_GAMMA_R:
4317 case BUILT_IN_GAMMAF_R:
4318 case BUILT_IN_GAMMAL_R:
4319 case BUILT_IN_LGAMMA_R:
4320 case BUILT_IN_LGAMMAF_R:
4321 case BUILT_IN_LGAMMAL_R:
4322 case BUILT_IN_MODF:
4323 case BUILT_IN_MODFF:
4324 case BUILT_IN_MODFL:
4325 case BUILT_IN_REMQUO:
4326 case BUILT_IN_REMQUOF:
4327 case BUILT_IN_REMQUOL:
4328 case BUILT_IN_FREE:
4329 return true;
4330 case BUILT_IN_STRDUP:
4331 case BUILT_IN_STRNDUP:
4332 case BUILT_IN_REALLOC:
4333 if (gimple_call_lhs (t))
4335 handle_lhs_call (t, gimple_call_lhs (t),
4336 gimple_call_return_flags (t) | ERF_NOALIAS,
4337 vNULL, fndecl);
4338 get_constraint_for_ptr_offset (gimple_call_lhs (t),
4339 NULL_TREE, &lhsc);
4340 get_constraint_for_ptr_offset (gimple_call_arg (t, 0),
4341 NULL_TREE, &rhsc);
4342 do_deref (&lhsc);
4343 do_deref (&rhsc);
4344 process_all_all_constraints (lhsc, rhsc);
4345 lhsc.truncate (0);
4346 rhsc.truncate (0);
4347 /* For realloc the resulting pointer can be equal to the
4348 argument as well. But only doing this wouldn't be
4349 correct because with ptr == 0 realloc behaves like malloc. */
4350 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_REALLOC)
4352 get_constraint_for (gimple_call_lhs (t), &lhsc);
4353 get_constraint_for (gimple_call_arg (t, 0), &rhsc);
4354 process_all_all_constraints (lhsc, rhsc);
4356 return true;
4358 break;
4359 /* String / character search functions return a pointer into the
4360 source string or NULL. */
4361 case BUILT_IN_INDEX:
4362 case BUILT_IN_STRCHR:
4363 case BUILT_IN_STRRCHR:
4364 case BUILT_IN_MEMCHR:
4365 case BUILT_IN_STRSTR:
4366 case BUILT_IN_STRPBRK:
4367 if (gimple_call_lhs (t))
4369 tree src = gimple_call_arg (t, 0);
4370 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4371 constraint_expr nul;
4372 nul.var = nothing_id;
4373 nul.offset = 0;
4374 nul.type = ADDRESSOF;
4375 rhsc.safe_push (nul);
4376 get_constraint_for (gimple_call_lhs (t), &lhsc);
4377 process_all_all_constraints (lhsc, rhsc);
4379 return true;
4380 /* Trampolines are special - they set up passing the static
4381 frame. */
4382 case BUILT_IN_INIT_TRAMPOLINE:
4384 tree tramp = gimple_call_arg (t, 0);
4385 tree nfunc = gimple_call_arg (t, 1);
4386 tree frame = gimple_call_arg (t, 2);
4387 unsigned i;
4388 struct constraint_expr lhs, *rhsp;
4389 if (in_ipa_mode)
4391 varinfo_t nfi = NULL;
4392 gcc_assert (TREE_CODE (nfunc) == ADDR_EXPR);
4393 nfi = lookup_vi_for_tree (TREE_OPERAND (nfunc, 0));
4394 if (nfi)
4396 lhs = get_function_part_constraint (nfi, fi_static_chain);
4397 get_constraint_for (frame, &rhsc);
4398 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4399 process_constraint (new_constraint (lhs, *rhsp));
4400 rhsc.truncate (0);
4402 /* Make the frame point to the function for
4403 the trampoline adjustment call. */
4404 get_constraint_for (tramp, &lhsc);
4405 do_deref (&lhsc);
4406 get_constraint_for (nfunc, &rhsc);
4407 process_all_all_constraints (lhsc, rhsc);
4409 return true;
4412 /* Else fallthru to generic handling which will let
4413 the frame escape. */
4414 break;
4416 case BUILT_IN_ADJUST_TRAMPOLINE:
4418 tree tramp = gimple_call_arg (t, 0);
4419 tree res = gimple_call_lhs (t);
4420 if (in_ipa_mode && res)
4422 get_constraint_for (res, &lhsc);
4423 get_constraint_for (tramp, &rhsc);
4424 do_deref (&rhsc);
4425 process_all_all_constraints (lhsc, rhsc);
4427 return true;
4429 CASE_BUILT_IN_TM_STORE (1):
4430 CASE_BUILT_IN_TM_STORE (2):
4431 CASE_BUILT_IN_TM_STORE (4):
4432 CASE_BUILT_IN_TM_STORE (8):
4433 CASE_BUILT_IN_TM_STORE (FLOAT):
4434 CASE_BUILT_IN_TM_STORE (DOUBLE):
4435 CASE_BUILT_IN_TM_STORE (LDOUBLE):
4436 CASE_BUILT_IN_TM_STORE (M64):
4437 CASE_BUILT_IN_TM_STORE (M128):
4438 CASE_BUILT_IN_TM_STORE (M256):
4440 tree addr = gimple_call_arg (t, 0);
4441 tree src = gimple_call_arg (t, 1);
4443 get_constraint_for (addr, &lhsc);
4444 do_deref (&lhsc);
4445 get_constraint_for (src, &rhsc);
4446 process_all_all_constraints (lhsc, rhsc);
4447 return true;
4449 CASE_BUILT_IN_TM_LOAD (1):
4450 CASE_BUILT_IN_TM_LOAD (2):
4451 CASE_BUILT_IN_TM_LOAD (4):
4452 CASE_BUILT_IN_TM_LOAD (8):
4453 CASE_BUILT_IN_TM_LOAD (FLOAT):
4454 CASE_BUILT_IN_TM_LOAD (DOUBLE):
4455 CASE_BUILT_IN_TM_LOAD (LDOUBLE):
4456 CASE_BUILT_IN_TM_LOAD (M64):
4457 CASE_BUILT_IN_TM_LOAD (M128):
4458 CASE_BUILT_IN_TM_LOAD (M256):
4460 tree dest = gimple_call_lhs (t);
4461 tree addr = gimple_call_arg (t, 0);
4463 get_constraint_for (dest, &lhsc);
4464 get_constraint_for (addr, &rhsc);
4465 do_deref (&rhsc);
4466 process_all_all_constraints (lhsc, rhsc);
4467 return true;
4469 /* Variadic argument handling needs to be handled in IPA
4470 mode as well. */
4471 case BUILT_IN_VA_START:
4473 tree valist = gimple_call_arg (t, 0);
4474 struct constraint_expr rhs, *lhsp;
4475 unsigned i;
4476 get_constraint_for (valist, &lhsc);
4477 do_deref (&lhsc);
4478 /* The va_list gets access to pointers in variadic
4479 arguments. Which we know in the case of IPA analysis
4480 and otherwise are just all nonlocal variables. */
4481 if (in_ipa_mode)
4483 fi = lookup_vi_for_tree (fn->decl);
4484 rhs = get_function_part_constraint (fi, ~0);
4485 rhs.type = ADDRESSOF;
4487 else
4489 rhs.var = nonlocal_id;
4490 rhs.type = ADDRESSOF;
4491 rhs.offset = 0;
4493 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4494 process_constraint (new_constraint (*lhsp, rhs));
4495 /* va_list is clobbered. */
4496 make_constraint_to (get_call_clobber_vi (t)->id, valist);
4497 return true;
4499 /* va_end doesn't have any effect that matters. */
4500 case BUILT_IN_VA_END:
4501 return true;
4502 /* Alternate return. Simply give up for now. */
4503 case BUILT_IN_RETURN:
4505 fi = NULL;
4506 if (!in_ipa_mode
4507 || !(fi = get_vi_for_tree (fn->decl)))
4508 make_constraint_from (get_varinfo (escaped_id), anything_id);
4509 else if (in_ipa_mode
4510 && fi != NULL)
4512 struct constraint_expr lhs, rhs;
4513 lhs = get_function_part_constraint (fi, fi_result);
4514 rhs.var = anything_id;
4515 rhs.offset = 0;
4516 rhs.type = SCALAR;
4517 process_constraint (new_constraint (lhs, rhs));
4519 return true;
4521 /* printf-style functions may have hooks to set pointers to
4522 point to somewhere into the generated string. Leave them
4523 for a later exercise... */
4524 default:
4525 /* Fallthru to general call handling. */;
4528 return false;
4531 /* Create constraints for the call T. */
4533 static void
4534 find_func_aliases_for_call (struct function *fn, gcall *t)
4536 tree fndecl = gimple_call_fndecl (t);
4537 varinfo_t fi;
4539 if (fndecl != NULL_TREE
4540 && DECL_BUILT_IN (fndecl)
4541 && find_func_aliases_for_builtin_call (fn, t))
4542 return;
4544 fi = get_fi_for_callee (t);
4545 if (!in_ipa_mode
4546 || (fndecl && !fi->is_fn_info))
4548 auto_vec<ce_s, 16> rhsc;
4549 int flags = gimple_call_flags (t);
4551 /* Const functions can return their arguments and addresses
4552 of global memory but not of escaped memory. */
4553 if (flags & (ECF_CONST|ECF_NOVOPS))
4555 if (gimple_call_lhs (t))
4556 handle_const_call (t, &rhsc);
4558 /* Pure functions can return addresses in and of memory
4559 reachable from their arguments, but they are not an escape
4560 point for reachable memory of their arguments. */
4561 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
4562 handle_pure_call (t, &rhsc);
4563 else
4564 handle_rhs_call (t, &rhsc);
4565 if (gimple_call_lhs (t))
4566 handle_lhs_call (t, gimple_call_lhs (t),
4567 gimple_call_return_flags (t), rhsc, fndecl);
4569 else
4571 auto_vec<ce_s, 2> rhsc;
4572 tree lhsop;
4573 unsigned j;
4575 /* Assign all the passed arguments to the appropriate incoming
4576 parameters of the function. */
4577 for (j = 0; j < gimple_call_num_args (t); j++)
4579 struct constraint_expr lhs ;
4580 struct constraint_expr *rhsp;
4581 tree arg = gimple_call_arg (t, j);
4583 get_constraint_for_rhs (arg, &rhsc);
4584 lhs = get_function_part_constraint (fi, fi_parm_base + j);
4585 while (rhsc.length () != 0)
4587 rhsp = &rhsc.last ();
4588 process_constraint (new_constraint (lhs, *rhsp));
4589 rhsc.pop ();
4593 /* If we are returning a value, assign it to the result. */
4594 lhsop = gimple_call_lhs (t);
4595 if (lhsop)
4597 auto_vec<ce_s, 2> lhsc;
4598 struct constraint_expr rhs;
4599 struct constraint_expr *lhsp;
4601 get_constraint_for (lhsop, &lhsc);
4602 rhs = get_function_part_constraint (fi, fi_result);
4603 if (fndecl
4604 && DECL_RESULT (fndecl)
4605 && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
4607 auto_vec<ce_s, 2> tem;
4608 tem.quick_push (rhs);
4609 do_deref (&tem);
4610 gcc_checking_assert (tem.length () == 1);
4611 rhs = tem[0];
4613 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
4614 process_constraint (new_constraint (*lhsp, rhs));
4617 /* If we pass the result decl by reference, honor that. */
4618 if (lhsop
4619 && fndecl
4620 && DECL_RESULT (fndecl)
4621 && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
4623 struct constraint_expr lhs;
4624 struct constraint_expr *rhsp;
4626 get_constraint_for_address_of (lhsop, &rhsc);
4627 lhs = get_function_part_constraint (fi, fi_result);
4628 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4629 process_constraint (new_constraint (lhs, *rhsp));
4630 rhsc.truncate (0);
4633 /* If we use a static chain, pass it along. */
4634 if (gimple_call_chain (t))
4636 struct constraint_expr lhs;
4637 struct constraint_expr *rhsp;
4639 get_constraint_for (gimple_call_chain (t), &rhsc);
4640 lhs = get_function_part_constraint (fi, fi_static_chain);
4641 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4642 process_constraint (new_constraint (lhs, *rhsp));
4647 /* Walk statement T setting up aliasing constraints according to the
4648 references found in T. This function is the main part of the
4649 constraint builder. AI points to auxiliary alias information used
4650 when building alias sets and computing alias grouping heuristics. */
4652 static void
4653 find_func_aliases (struct function *fn, gimple origt)
4655 gimple t = origt;
4656 auto_vec<ce_s, 16> lhsc;
4657 auto_vec<ce_s, 16> rhsc;
4658 struct constraint_expr *c;
4659 varinfo_t fi;
4661 /* Now build constraints expressions. */
4662 if (gimple_code (t) == GIMPLE_PHI)
4664 size_t i;
4665 unsigned int j;
4667 /* For a phi node, assign all the arguments to
4668 the result. */
4669 get_constraint_for (gimple_phi_result (t), &lhsc);
4670 for (i = 0; i < gimple_phi_num_args (t); i++)
4672 tree strippedrhs = PHI_ARG_DEF (t, i);
4674 STRIP_NOPS (strippedrhs);
4675 get_constraint_for_rhs (gimple_phi_arg_def (t, i), &rhsc);
4677 FOR_EACH_VEC_ELT (lhsc, j, c)
4679 struct constraint_expr *c2;
4680 while (rhsc.length () > 0)
4682 c2 = &rhsc.last ();
4683 process_constraint (new_constraint (*c, *c2));
4684 rhsc.pop ();
4689 /* In IPA mode, we need to generate constraints to pass call
4690 arguments through their calls. There are two cases,
4691 either a GIMPLE_CALL returning a value, or just a plain
4692 GIMPLE_CALL when we are not.
4694 In non-ipa mode, we need to generate constraints for each
4695 pointer passed by address. */
4696 else if (is_gimple_call (t))
4697 find_func_aliases_for_call (fn, as_a <gcall *> (t));
4699 /* Otherwise, just a regular assignment statement. Only care about
4700 operations with pointer result, others are dealt with as escape
4701 points if they have pointer operands. */
4702 else if (is_gimple_assign (t))
4704 /* Otherwise, just a regular assignment statement. */
4705 tree lhsop = gimple_assign_lhs (t);
4706 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
4708 if (rhsop && TREE_CLOBBER_P (rhsop))
4709 /* Ignore clobbers, they don't actually store anything into
4710 the LHS. */
4712 else if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
4713 do_structure_copy (lhsop, rhsop);
4714 else
4716 enum tree_code code = gimple_assign_rhs_code (t);
4718 get_constraint_for (lhsop, &lhsc);
4720 if (code == POINTER_PLUS_EXPR)
4721 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4722 gimple_assign_rhs2 (t), &rhsc);
4723 else if (code == BIT_AND_EXPR
4724 && TREE_CODE (gimple_assign_rhs2 (t)) == INTEGER_CST)
4726 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4727 the pointer. Handle it by offsetting it by UNKNOWN. */
4728 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4729 NULL_TREE, &rhsc);
4731 else if ((CONVERT_EXPR_CODE_P (code)
4732 && !(POINTER_TYPE_P (gimple_expr_type (t))
4733 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
4734 || gimple_assign_single_p (t))
4735 get_constraint_for_rhs (rhsop, &rhsc);
4736 else if (code == COND_EXPR)
4738 /* The result is a merge of both COND_EXPR arms. */
4739 auto_vec<ce_s, 2> tmp;
4740 struct constraint_expr *rhsp;
4741 unsigned i;
4742 get_constraint_for_rhs (gimple_assign_rhs2 (t), &rhsc);
4743 get_constraint_for_rhs (gimple_assign_rhs3 (t), &tmp);
4744 FOR_EACH_VEC_ELT (tmp, i, rhsp)
4745 rhsc.safe_push (*rhsp);
4747 else if (truth_value_p (code))
4748 /* Truth value results are not pointer (parts). Or at least
4749 very very unreasonable obfuscation of a part. */
4751 else
4753 /* All other operations are merges. */
4754 auto_vec<ce_s, 4> tmp;
4755 struct constraint_expr *rhsp;
4756 unsigned i, j;
4757 get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
4758 for (i = 2; i < gimple_num_ops (t); ++i)
4760 get_constraint_for_rhs (gimple_op (t, i), &tmp);
4761 FOR_EACH_VEC_ELT (tmp, j, rhsp)
4762 rhsc.safe_push (*rhsp);
4763 tmp.truncate (0);
4766 process_all_all_constraints (lhsc, rhsc);
4768 /* If there is a store to a global variable the rhs escapes. */
4769 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
4770 && DECL_P (lhsop)
4771 && is_global_var (lhsop)
4772 && (!in_ipa_mode
4773 || DECL_EXTERNAL (lhsop) || TREE_PUBLIC (lhsop)))
4774 make_escape_constraint (rhsop);
4776 /* Handle escapes through return. */
4777 else if (gimple_code (t) == GIMPLE_RETURN
4778 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE)
4780 greturn *return_stmt = as_a <greturn *> (t);
4781 fi = NULL;
4782 if (!in_ipa_mode
4783 || !(fi = get_vi_for_tree (fn->decl)))
4784 make_escape_constraint (gimple_return_retval (return_stmt));
4785 else if (in_ipa_mode
4786 && fi != NULL)
4788 struct constraint_expr lhs ;
4789 struct constraint_expr *rhsp;
4790 unsigned i;
4792 lhs = get_function_part_constraint (fi, fi_result);
4793 get_constraint_for_rhs (gimple_return_retval (return_stmt), &rhsc);
4794 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4795 process_constraint (new_constraint (lhs, *rhsp));
4798 /* Handle asms conservatively by adding escape constraints to everything. */
4799 else if (gasm *asm_stmt = dyn_cast <gasm *> (t))
4801 unsigned i, noutputs;
4802 const char **oconstraints;
4803 const char *constraint;
4804 bool allows_mem, allows_reg, is_inout;
4806 noutputs = gimple_asm_noutputs (asm_stmt);
4807 oconstraints = XALLOCAVEC (const char *, noutputs);
4809 for (i = 0; i < noutputs; ++i)
4811 tree link = gimple_asm_output_op (asm_stmt, i);
4812 tree op = TREE_VALUE (link);
4814 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4815 oconstraints[i] = constraint;
4816 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4817 &allows_reg, &is_inout);
4819 /* A memory constraint makes the address of the operand escape. */
4820 if (!allows_reg && allows_mem)
4821 make_escape_constraint (build_fold_addr_expr (op));
4823 /* The asm may read global memory, so outputs may point to
4824 any global memory. */
4825 if (op)
4827 auto_vec<ce_s, 2> lhsc;
4828 struct constraint_expr rhsc, *lhsp;
4829 unsigned j;
4830 get_constraint_for (op, &lhsc);
4831 rhsc.var = nonlocal_id;
4832 rhsc.offset = 0;
4833 rhsc.type = SCALAR;
4834 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
4835 process_constraint (new_constraint (*lhsp, rhsc));
4838 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
4840 tree link = gimple_asm_input_op (asm_stmt, i);
4841 tree op = TREE_VALUE (link);
4843 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4845 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
4846 &allows_mem, &allows_reg);
4848 /* A memory constraint makes the address of the operand escape. */
4849 if (!allows_reg && allows_mem)
4850 make_escape_constraint (build_fold_addr_expr (op));
4851 /* Strictly we'd only need the constraint to ESCAPED if
4852 the asm clobbers memory, otherwise using something
4853 along the lines of per-call clobbers/uses would be enough. */
4854 else if (op)
4855 make_escape_constraint (op);
4861 /* Create a constraint adding to the clobber set of FI the memory
4862 pointed to by PTR. */
4864 static void
4865 process_ipa_clobber (varinfo_t fi, tree ptr)
4867 vec<ce_s> ptrc = vNULL;
4868 struct constraint_expr *c, lhs;
4869 unsigned i;
4870 get_constraint_for_rhs (ptr, &ptrc);
4871 lhs = get_function_part_constraint (fi, fi_clobbers);
4872 FOR_EACH_VEC_ELT (ptrc, i, c)
4873 process_constraint (new_constraint (lhs, *c));
4874 ptrc.release ();
4877 /* Walk statement T setting up clobber and use constraints according to the
4878 references found in T. This function is a main part of the
4879 IPA constraint builder. */
4881 static void
4882 find_func_clobbers (struct function *fn, gimple origt)
4884 gimple t = origt;
4885 auto_vec<ce_s, 16> lhsc;
4886 auto_vec<ce_s, 16> rhsc;
4887 varinfo_t fi;
4889 /* Add constraints for clobbered/used in IPA mode.
4890 We are not interested in what automatic variables are clobbered
4891 or used as we only use the information in the caller to which
4892 they do not escape. */
4893 gcc_assert (in_ipa_mode);
4895 /* If the stmt refers to memory in any way it better had a VUSE. */
4896 if (gimple_vuse (t) == NULL_TREE)
4897 return;
4899 /* We'd better have function information for the current function. */
4900 fi = lookup_vi_for_tree (fn->decl);
4901 gcc_assert (fi != NULL);
4903 /* Account for stores in assignments and calls. */
4904 if (gimple_vdef (t) != NULL_TREE
4905 && gimple_has_lhs (t))
4907 tree lhs = gimple_get_lhs (t);
4908 tree tem = lhs;
4909 while (handled_component_p (tem))
4910 tem = TREE_OPERAND (tem, 0);
4911 if ((DECL_P (tem)
4912 && !auto_var_in_fn_p (tem, fn->decl))
4913 || INDIRECT_REF_P (tem)
4914 || (TREE_CODE (tem) == MEM_REF
4915 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
4916 && auto_var_in_fn_p
4917 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
4919 struct constraint_expr lhsc, *rhsp;
4920 unsigned i;
4921 lhsc = get_function_part_constraint (fi, fi_clobbers);
4922 get_constraint_for_address_of (lhs, &rhsc);
4923 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4924 process_constraint (new_constraint (lhsc, *rhsp));
4925 rhsc.truncate (0);
4929 /* Account for uses in assigments and returns. */
4930 if (gimple_assign_single_p (t)
4931 || (gimple_code (t) == GIMPLE_RETURN
4932 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE))
4934 tree rhs = (gimple_assign_single_p (t)
4935 ? gimple_assign_rhs1 (t)
4936 : gimple_return_retval (as_a <greturn *> (t)));
4937 tree tem = rhs;
4938 while (handled_component_p (tem))
4939 tem = TREE_OPERAND (tem, 0);
4940 if ((DECL_P (tem)
4941 && !auto_var_in_fn_p (tem, fn->decl))
4942 || INDIRECT_REF_P (tem)
4943 || (TREE_CODE (tem) == MEM_REF
4944 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
4945 && auto_var_in_fn_p
4946 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
4948 struct constraint_expr lhs, *rhsp;
4949 unsigned i;
4950 lhs = get_function_part_constraint (fi, fi_uses);
4951 get_constraint_for_address_of (rhs, &rhsc);
4952 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4953 process_constraint (new_constraint (lhs, *rhsp));
4954 rhsc.truncate (0);
4958 if (gcall *call_stmt = dyn_cast <gcall *> (t))
4960 varinfo_t cfi = NULL;
4961 tree decl = gimple_call_fndecl (t);
4962 struct constraint_expr lhs, rhs;
4963 unsigned i, j;
4965 /* For builtins we do not have separate function info. For those
4966 we do not generate escapes for we have to generate clobbers/uses. */
4967 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
4968 switch (DECL_FUNCTION_CODE (decl))
4970 /* The following functions use and clobber memory pointed to
4971 by their arguments. */
4972 case BUILT_IN_STRCPY:
4973 case BUILT_IN_STRNCPY:
4974 case BUILT_IN_BCOPY:
4975 case BUILT_IN_MEMCPY:
4976 case BUILT_IN_MEMMOVE:
4977 case BUILT_IN_MEMPCPY:
4978 case BUILT_IN_STPCPY:
4979 case BUILT_IN_STPNCPY:
4980 case BUILT_IN_STRCAT:
4981 case BUILT_IN_STRNCAT:
4982 case BUILT_IN_STRCPY_CHK:
4983 case BUILT_IN_STRNCPY_CHK:
4984 case BUILT_IN_MEMCPY_CHK:
4985 case BUILT_IN_MEMMOVE_CHK:
4986 case BUILT_IN_MEMPCPY_CHK:
4987 case BUILT_IN_STPCPY_CHK:
4988 case BUILT_IN_STPNCPY_CHK:
4989 case BUILT_IN_STRCAT_CHK:
4990 case BUILT_IN_STRNCAT_CHK:
4992 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
4993 == BUILT_IN_BCOPY ? 1 : 0));
4994 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
4995 == BUILT_IN_BCOPY ? 0 : 1));
4996 unsigned i;
4997 struct constraint_expr *rhsp, *lhsp;
4998 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4999 lhs = get_function_part_constraint (fi, fi_clobbers);
5000 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
5001 process_constraint (new_constraint (lhs, *lhsp));
5002 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
5003 lhs = get_function_part_constraint (fi, fi_uses);
5004 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5005 process_constraint (new_constraint (lhs, *rhsp));
5006 return;
5008 /* The following function clobbers memory pointed to by
5009 its argument. */
5010 case BUILT_IN_MEMSET:
5011 case BUILT_IN_MEMSET_CHK:
5012 case BUILT_IN_POSIX_MEMALIGN:
5014 tree dest = gimple_call_arg (t, 0);
5015 unsigned i;
5016 ce_s *lhsp;
5017 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
5018 lhs = get_function_part_constraint (fi, fi_clobbers);
5019 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
5020 process_constraint (new_constraint (lhs, *lhsp));
5021 return;
5023 /* The following functions clobber their second and third
5024 arguments. */
5025 case BUILT_IN_SINCOS:
5026 case BUILT_IN_SINCOSF:
5027 case BUILT_IN_SINCOSL:
5029 process_ipa_clobber (fi, gimple_call_arg (t, 1));
5030 process_ipa_clobber (fi, gimple_call_arg (t, 2));
5031 return;
5033 /* The following functions clobber their second argument. */
5034 case BUILT_IN_FREXP:
5035 case BUILT_IN_FREXPF:
5036 case BUILT_IN_FREXPL:
5037 case BUILT_IN_LGAMMA_R:
5038 case BUILT_IN_LGAMMAF_R:
5039 case BUILT_IN_LGAMMAL_R:
5040 case BUILT_IN_GAMMA_R:
5041 case BUILT_IN_GAMMAF_R:
5042 case BUILT_IN_GAMMAL_R:
5043 case BUILT_IN_MODF:
5044 case BUILT_IN_MODFF:
5045 case BUILT_IN_MODFL:
5047 process_ipa_clobber (fi, gimple_call_arg (t, 1));
5048 return;
5050 /* The following functions clobber their third argument. */
5051 case BUILT_IN_REMQUO:
5052 case BUILT_IN_REMQUOF:
5053 case BUILT_IN_REMQUOL:
5055 process_ipa_clobber (fi, gimple_call_arg (t, 2));
5056 return;
5058 /* The following functions neither read nor clobber memory. */
5059 case BUILT_IN_ASSUME_ALIGNED:
5060 case BUILT_IN_FREE:
5061 return;
5062 /* Trampolines are of no interest to us. */
5063 case BUILT_IN_INIT_TRAMPOLINE:
5064 case BUILT_IN_ADJUST_TRAMPOLINE:
5065 return;
5066 case BUILT_IN_VA_START:
5067 case BUILT_IN_VA_END:
5068 return;
5069 /* printf-style functions may have hooks to set pointers to
5070 point to somewhere into the generated string. Leave them
5071 for a later exercise... */
5072 default:
5073 /* Fallthru to general call handling. */;
5076 /* Parameters passed by value are used. */
5077 lhs = get_function_part_constraint (fi, fi_uses);
5078 for (i = 0; i < gimple_call_num_args (t); i++)
5080 struct constraint_expr *rhsp;
5081 tree arg = gimple_call_arg (t, i);
5083 if (TREE_CODE (arg) == SSA_NAME
5084 || is_gimple_min_invariant (arg))
5085 continue;
5087 get_constraint_for_address_of (arg, &rhsc);
5088 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5089 process_constraint (new_constraint (lhs, *rhsp));
5090 rhsc.truncate (0);
5093 /* Build constraints for propagating clobbers/uses along the
5094 callgraph edges. */
5095 cfi = get_fi_for_callee (call_stmt);
5096 if (cfi->id == anything_id)
5098 if (gimple_vdef (t))
5099 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5100 anything_id);
5101 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5102 anything_id);
5103 return;
5106 /* For callees without function info (that's external functions),
5107 ESCAPED is clobbered and used. */
5108 if (gimple_call_fndecl (t)
5109 && !cfi->is_fn_info)
5111 varinfo_t vi;
5113 if (gimple_vdef (t))
5114 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5115 escaped_id);
5116 make_copy_constraint (first_vi_for_offset (fi, fi_uses), escaped_id);
5118 /* Also honor the call statement use/clobber info. */
5119 if ((vi = lookup_call_clobber_vi (call_stmt)) != NULL)
5120 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5121 vi->id);
5122 if ((vi = lookup_call_use_vi (call_stmt)) != NULL)
5123 make_copy_constraint (first_vi_for_offset (fi, fi_uses),
5124 vi->id);
5125 return;
5128 /* Otherwise the caller clobbers and uses what the callee does.
5129 ??? This should use a new complex constraint that filters
5130 local variables of the callee. */
5131 if (gimple_vdef (t))
5133 lhs = get_function_part_constraint (fi, fi_clobbers);
5134 rhs = get_function_part_constraint (cfi, fi_clobbers);
5135 process_constraint (new_constraint (lhs, rhs));
5137 lhs = get_function_part_constraint (fi, fi_uses);
5138 rhs = get_function_part_constraint (cfi, fi_uses);
5139 process_constraint (new_constraint (lhs, rhs));
5141 else if (gimple_code (t) == GIMPLE_ASM)
5143 /* ??? Ick. We can do better. */
5144 if (gimple_vdef (t))
5145 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5146 anything_id);
5147 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5148 anything_id);
5153 /* Find the first varinfo in the same variable as START that overlaps with
5154 OFFSET. Return NULL if we can't find one. */
5156 static varinfo_t
5157 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
5159 /* If the offset is outside of the variable, bail out. */
5160 if (offset >= start->fullsize)
5161 return NULL;
5163 /* If we cannot reach offset from start, lookup the first field
5164 and start from there. */
5165 if (start->offset > offset)
5166 start = get_varinfo (start->head);
5168 while (start)
5170 /* We may not find a variable in the field list with the actual
5171 offset when when we have glommed a structure to a variable.
5172 In that case, however, offset should still be within the size
5173 of the variable. */
5174 if (offset >= start->offset
5175 && (offset - start->offset) < start->size)
5176 return start;
5178 start = vi_next (start);
5181 return NULL;
5184 /* Find the first varinfo in the same variable as START that overlaps with
5185 OFFSET. If there is no such varinfo the varinfo directly preceding
5186 OFFSET is returned. */
5188 static varinfo_t
5189 first_or_preceding_vi_for_offset (varinfo_t start,
5190 unsigned HOST_WIDE_INT offset)
5192 /* If we cannot reach offset from start, lookup the first field
5193 and start from there. */
5194 if (start->offset > offset)
5195 start = get_varinfo (start->head);
5197 /* We may not find a variable in the field list with the actual
5198 offset when when we have glommed a structure to a variable.
5199 In that case, however, offset should still be within the size
5200 of the variable.
5201 If we got beyond the offset we look for return the field
5202 directly preceding offset which may be the last field. */
5203 while (start->next
5204 && offset >= start->offset
5205 && !((offset - start->offset) < start->size))
5206 start = vi_next (start);
5208 return start;
5212 /* This structure is used during pushing fields onto the fieldstack
5213 to track the offset of the field, since bitpos_of_field gives it
5214 relative to its immediate containing type, and we want it relative
5215 to the ultimate containing object. */
5217 struct fieldoff
5219 /* Offset from the base of the base containing object to this field. */
5220 HOST_WIDE_INT offset;
5222 /* Size, in bits, of the field. */
5223 unsigned HOST_WIDE_INT size;
5225 unsigned has_unknown_size : 1;
5227 unsigned must_have_pointers : 1;
5229 unsigned may_have_pointers : 1;
5231 unsigned only_restrict_pointers : 1;
5233 typedef struct fieldoff fieldoff_s;
5236 /* qsort comparison function for two fieldoff's PA and PB */
5238 static int
5239 fieldoff_compare (const void *pa, const void *pb)
5241 const fieldoff_s *foa = (const fieldoff_s *)pa;
5242 const fieldoff_s *fob = (const fieldoff_s *)pb;
5243 unsigned HOST_WIDE_INT foasize, fobsize;
5245 if (foa->offset < fob->offset)
5246 return -1;
5247 else if (foa->offset > fob->offset)
5248 return 1;
5250 foasize = foa->size;
5251 fobsize = fob->size;
5252 if (foasize < fobsize)
5253 return -1;
5254 else if (foasize > fobsize)
5255 return 1;
5256 return 0;
5259 /* Sort a fieldstack according to the field offset and sizes. */
5260 static void
5261 sort_fieldstack (vec<fieldoff_s> fieldstack)
5263 fieldstack.qsort (fieldoff_compare);
5266 /* Return true if T is a type that can have subvars. */
5268 static inline bool
5269 type_can_have_subvars (const_tree t)
5271 /* Aggregates without overlapping fields can have subvars. */
5272 return TREE_CODE (t) == RECORD_TYPE;
5275 /* Return true if V is a tree that we can have subvars for.
5276 Normally, this is any aggregate type. Also complex
5277 types which are not gimple registers can have subvars. */
5279 static inline bool
5280 var_can_have_subvars (const_tree v)
5282 /* Volatile variables should never have subvars. */
5283 if (TREE_THIS_VOLATILE (v))
5284 return false;
5286 /* Non decls or memory tags can never have subvars. */
5287 if (!DECL_P (v))
5288 return false;
5290 return type_can_have_subvars (TREE_TYPE (v));
5293 /* Return true if T is a type that does contain pointers. */
5295 static bool
5296 type_must_have_pointers (tree type)
5298 if (POINTER_TYPE_P (type))
5299 return true;
5301 if (TREE_CODE (type) == ARRAY_TYPE)
5302 return type_must_have_pointers (TREE_TYPE (type));
5304 /* A function or method can have pointers as arguments, so track
5305 those separately. */
5306 if (TREE_CODE (type) == FUNCTION_TYPE
5307 || TREE_CODE (type) == METHOD_TYPE)
5308 return true;
5310 return false;
5313 static bool
5314 field_must_have_pointers (tree t)
5316 return type_must_have_pointers (TREE_TYPE (t));
5319 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5320 the fields of TYPE onto fieldstack, recording their offsets along
5321 the way.
5323 OFFSET is used to keep track of the offset in this entire
5324 structure, rather than just the immediately containing structure.
5325 Returns false if the caller is supposed to handle the field we
5326 recursed for. */
5328 static bool
5329 push_fields_onto_fieldstack (tree type, vec<fieldoff_s> *fieldstack,
5330 HOST_WIDE_INT offset)
5332 tree field;
5333 bool empty_p = true;
5335 if (TREE_CODE (type) != RECORD_TYPE)
5336 return false;
5338 /* If the vector of fields is growing too big, bail out early.
5339 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5340 sure this fails. */
5341 if (fieldstack->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
5342 return false;
5344 for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
5345 if (TREE_CODE (field) == FIELD_DECL)
5347 bool push = false;
5348 HOST_WIDE_INT foff = bitpos_of_field (field);
5350 if (!var_can_have_subvars (field)
5351 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
5352 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
5353 push = true;
5354 else if (!push_fields_onto_fieldstack
5355 (TREE_TYPE (field), fieldstack, offset + foff)
5356 && (DECL_SIZE (field)
5357 && !integer_zerop (DECL_SIZE (field))))
5358 /* Empty structures may have actual size, like in C++. So
5359 see if we didn't push any subfields and the size is
5360 nonzero, push the field onto the stack. */
5361 push = true;
5363 if (push)
5365 fieldoff_s *pair = NULL;
5366 bool has_unknown_size = false;
5367 bool must_have_pointers_p;
5369 if (!fieldstack->is_empty ())
5370 pair = &fieldstack->last ();
5372 /* If there isn't anything at offset zero, create sth. */
5373 if (!pair
5374 && offset + foff != 0)
5376 fieldoff_s e = {0, offset + foff, false, false, false, false};
5377 pair = fieldstack->safe_push (e);
5380 if (!DECL_SIZE (field)
5381 || !tree_fits_uhwi_p (DECL_SIZE (field)))
5382 has_unknown_size = true;
5384 /* If adjacent fields do not contain pointers merge them. */
5385 must_have_pointers_p = field_must_have_pointers (field);
5386 if (pair
5387 && !has_unknown_size
5388 && !must_have_pointers_p
5389 && !pair->must_have_pointers
5390 && !pair->has_unknown_size
5391 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
5393 pair->size += tree_to_uhwi (DECL_SIZE (field));
5395 else
5397 fieldoff_s e;
5398 e.offset = offset + foff;
5399 e.has_unknown_size = has_unknown_size;
5400 if (!has_unknown_size)
5401 e.size = tree_to_uhwi (DECL_SIZE (field));
5402 else
5403 e.size = -1;
5404 e.must_have_pointers = must_have_pointers_p;
5405 e.may_have_pointers = true;
5406 e.only_restrict_pointers
5407 = (!has_unknown_size
5408 && POINTER_TYPE_P (TREE_TYPE (field))
5409 && TYPE_RESTRICT (TREE_TYPE (field)));
5410 fieldstack->safe_push (e);
5414 empty_p = false;
5417 return !empty_p;
5420 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5421 if it is a varargs function. */
5423 static unsigned int
5424 count_num_arguments (tree decl, bool *is_varargs)
5426 unsigned int num = 0;
5427 tree t;
5429 /* Capture named arguments for K&R functions. They do not
5430 have a prototype and thus no TYPE_ARG_TYPES. */
5431 for (t = DECL_ARGUMENTS (decl); t; t = DECL_CHAIN (t))
5432 ++num;
5434 /* Check if the function has variadic arguments. */
5435 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
5436 if (TREE_VALUE (t) == void_type_node)
5437 break;
5438 if (!t)
5439 *is_varargs = true;
5441 return num;
5444 /* Creation function node for DECL, using NAME, and return the index
5445 of the variable we've created for the function. */
5447 static varinfo_t
5448 create_function_info_for (tree decl, const char *name)
5450 struct function *fn = DECL_STRUCT_FUNCTION (decl);
5451 varinfo_t vi, prev_vi;
5452 tree arg;
5453 unsigned int i;
5454 bool is_varargs = false;
5455 unsigned int num_args = count_num_arguments (decl, &is_varargs);
5457 /* Create the variable info. */
5459 vi = new_var_info (decl, name);
5460 vi->offset = 0;
5461 vi->size = 1;
5462 vi->fullsize = fi_parm_base + num_args;
5463 vi->is_fn_info = 1;
5464 vi->may_have_pointers = false;
5465 if (is_varargs)
5466 vi->fullsize = ~0;
5467 insert_vi_for_tree (vi->decl, vi);
5469 prev_vi = vi;
5471 /* Create a variable for things the function clobbers and one for
5472 things the function uses. */
5474 varinfo_t clobbervi, usevi;
5475 const char *newname;
5476 char *tempname;
5478 tempname = xasprintf ("%s.clobber", name);
5479 newname = ggc_strdup (tempname);
5480 free (tempname);
5482 clobbervi = new_var_info (NULL, newname);
5483 clobbervi->offset = fi_clobbers;
5484 clobbervi->size = 1;
5485 clobbervi->fullsize = vi->fullsize;
5486 clobbervi->is_full_var = true;
5487 clobbervi->is_global_var = false;
5488 gcc_assert (prev_vi->offset < clobbervi->offset);
5489 prev_vi->next = clobbervi->id;
5490 prev_vi = clobbervi;
5492 tempname = xasprintf ("%s.use", name);
5493 newname = ggc_strdup (tempname);
5494 free (tempname);
5496 usevi = new_var_info (NULL, newname);
5497 usevi->offset = fi_uses;
5498 usevi->size = 1;
5499 usevi->fullsize = vi->fullsize;
5500 usevi->is_full_var = true;
5501 usevi->is_global_var = false;
5502 gcc_assert (prev_vi->offset < usevi->offset);
5503 prev_vi->next = usevi->id;
5504 prev_vi = usevi;
5507 /* And one for the static chain. */
5508 if (fn->static_chain_decl != NULL_TREE)
5510 varinfo_t chainvi;
5511 const char *newname;
5512 char *tempname;
5514 tempname = xasprintf ("%s.chain", name);
5515 newname = ggc_strdup (tempname);
5516 free (tempname);
5518 chainvi = new_var_info (fn->static_chain_decl, newname);
5519 chainvi->offset = fi_static_chain;
5520 chainvi->size = 1;
5521 chainvi->fullsize = vi->fullsize;
5522 chainvi->is_full_var = true;
5523 chainvi->is_global_var = false;
5524 gcc_assert (prev_vi->offset < chainvi->offset);
5525 prev_vi->next = chainvi->id;
5526 prev_vi = chainvi;
5527 insert_vi_for_tree (fn->static_chain_decl, chainvi);
5530 /* Create a variable for the return var. */
5531 if (DECL_RESULT (decl) != NULL
5532 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
5534 varinfo_t resultvi;
5535 const char *newname;
5536 char *tempname;
5537 tree resultdecl = decl;
5539 if (DECL_RESULT (decl))
5540 resultdecl = DECL_RESULT (decl);
5542 tempname = xasprintf ("%s.result", name);
5543 newname = ggc_strdup (tempname);
5544 free (tempname);
5546 resultvi = new_var_info (resultdecl, newname);
5547 resultvi->offset = fi_result;
5548 resultvi->size = 1;
5549 resultvi->fullsize = vi->fullsize;
5550 resultvi->is_full_var = true;
5551 if (DECL_RESULT (decl))
5552 resultvi->may_have_pointers = true;
5553 gcc_assert (prev_vi->offset < resultvi->offset);
5554 prev_vi->next = resultvi->id;
5555 prev_vi = resultvi;
5556 if (DECL_RESULT (decl))
5557 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
5560 /* Set up variables for each argument. */
5561 arg = DECL_ARGUMENTS (decl);
5562 for (i = 0; i < num_args; i++)
5564 varinfo_t argvi;
5565 const char *newname;
5566 char *tempname;
5567 tree argdecl = decl;
5569 if (arg)
5570 argdecl = arg;
5572 tempname = xasprintf ("%s.arg%d", name, i);
5573 newname = ggc_strdup (tempname);
5574 free (tempname);
5576 argvi = new_var_info (argdecl, newname);
5577 argvi->offset = fi_parm_base + i;
5578 argvi->size = 1;
5579 argvi->is_full_var = true;
5580 argvi->fullsize = vi->fullsize;
5581 if (arg)
5582 argvi->may_have_pointers = true;
5583 gcc_assert (prev_vi->offset < argvi->offset);
5584 prev_vi->next = argvi->id;
5585 prev_vi = argvi;
5586 if (arg)
5588 insert_vi_for_tree (arg, argvi);
5589 arg = DECL_CHAIN (arg);
5593 /* Add one representative for all further args. */
5594 if (is_varargs)
5596 varinfo_t argvi;
5597 const char *newname;
5598 char *tempname;
5599 tree decl;
5601 tempname = xasprintf ("%s.varargs", name);
5602 newname = ggc_strdup (tempname);
5603 free (tempname);
5605 /* We need sth that can be pointed to for va_start. */
5606 decl = build_fake_var_decl (ptr_type_node);
5608 argvi = new_var_info (decl, newname);
5609 argvi->offset = fi_parm_base + num_args;
5610 argvi->size = ~0;
5611 argvi->is_full_var = true;
5612 argvi->is_heap_var = true;
5613 argvi->fullsize = vi->fullsize;
5614 gcc_assert (prev_vi->offset < argvi->offset);
5615 prev_vi->next = argvi->id;
5616 prev_vi = argvi;
5619 return vi;
5623 /* Return true if FIELDSTACK contains fields that overlap.
5624 FIELDSTACK is assumed to be sorted by offset. */
5626 static bool
5627 check_for_overlaps (vec<fieldoff_s> fieldstack)
5629 fieldoff_s *fo = NULL;
5630 unsigned int i;
5631 HOST_WIDE_INT lastoffset = -1;
5633 FOR_EACH_VEC_ELT (fieldstack, i, fo)
5635 if (fo->offset == lastoffset)
5636 return true;
5637 lastoffset = fo->offset;
5639 return false;
5642 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5643 This will also create any varinfo structures necessary for fields
5644 of DECL. */
5646 static varinfo_t
5647 create_variable_info_for_1 (tree decl, const char *name)
5649 varinfo_t vi, newvi;
5650 tree decl_type = TREE_TYPE (decl);
5651 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
5652 auto_vec<fieldoff_s> fieldstack;
5653 fieldoff_s *fo;
5654 unsigned int i;
5655 varpool_node *vnode;
5657 if (!declsize
5658 || !tree_fits_uhwi_p (declsize))
5660 vi = new_var_info (decl, name);
5661 vi->offset = 0;
5662 vi->size = ~0;
5663 vi->fullsize = ~0;
5664 vi->is_unknown_size_var = true;
5665 vi->is_full_var = true;
5666 vi->may_have_pointers = true;
5667 return vi;
5670 /* Collect field information. */
5671 if (use_field_sensitive
5672 && var_can_have_subvars (decl)
5673 /* ??? Force us to not use subfields for global initializers
5674 in IPA mode. Else we'd have to parse arbitrary initializers. */
5675 && !(in_ipa_mode
5676 && is_global_var (decl)
5677 && (vnode = varpool_node::get (decl))
5678 && vnode->get_constructor ()))
5680 fieldoff_s *fo = NULL;
5681 bool notokay = false;
5682 unsigned int i;
5684 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
5686 for (i = 0; !notokay && fieldstack.iterate (i, &fo); i++)
5687 if (fo->has_unknown_size
5688 || fo->offset < 0)
5690 notokay = true;
5691 break;
5694 /* We can't sort them if we have a field with a variable sized type,
5695 which will make notokay = true. In that case, we are going to return
5696 without creating varinfos for the fields anyway, so sorting them is a
5697 waste to boot. */
5698 if (!notokay)
5700 sort_fieldstack (fieldstack);
5701 /* Due to some C++ FE issues, like PR 22488, we might end up
5702 what appear to be overlapping fields even though they,
5703 in reality, do not overlap. Until the C++ FE is fixed,
5704 we will simply disable field-sensitivity for these cases. */
5705 notokay = check_for_overlaps (fieldstack);
5708 if (notokay)
5709 fieldstack.release ();
5712 /* If we didn't end up collecting sub-variables create a full
5713 variable for the decl. */
5714 if (fieldstack.length () <= 1
5715 || fieldstack.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
5717 vi = new_var_info (decl, name);
5718 vi->offset = 0;
5719 vi->may_have_pointers = true;
5720 vi->fullsize = tree_to_uhwi (declsize);
5721 vi->size = vi->fullsize;
5722 vi->is_full_var = true;
5723 fieldstack.release ();
5724 return vi;
5727 vi = new_var_info (decl, name);
5728 vi->fullsize = tree_to_uhwi (declsize);
5729 for (i = 0, newvi = vi;
5730 fieldstack.iterate (i, &fo);
5731 ++i, newvi = vi_next (newvi))
5733 const char *newname = "NULL";
5734 char *tempname;
5736 if (dump_file)
5738 tempname
5739 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC
5740 "+" HOST_WIDE_INT_PRINT_DEC, name,
5741 fo->offset, fo->size);
5742 newname = ggc_strdup (tempname);
5743 free (tempname);
5745 newvi->name = newname;
5746 newvi->offset = fo->offset;
5747 newvi->size = fo->size;
5748 newvi->fullsize = vi->fullsize;
5749 newvi->may_have_pointers = fo->may_have_pointers;
5750 newvi->only_restrict_pointers = fo->only_restrict_pointers;
5751 if (i + 1 < fieldstack.length ())
5753 varinfo_t tem = new_var_info (decl, name);
5754 newvi->next = tem->id;
5755 tem->head = vi->id;
5759 return vi;
5762 static unsigned int
5763 create_variable_info_for (tree decl, const char *name)
5765 varinfo_t vi = create_variable_info_for_1 (decl, name);
5766 unsigned int id = vi->id;
5768 insert_vi_for_tree (decl, vi);
5770 if (TREE_CODE (decl) != VAR_DECL)
5771 return id;
5773 /* Create initial constraints for globals. */
5774 for (; vi; vi = vi_next (vi))
5776 if (!vi->may_have_pointers
5777 || !vi->is_global_var)
5778 continue;
5780 /* Mark global restrict qualified pointers. */
5781 if ((POINTER_TYPE_P (TREE_TYPE (decl))
5782 && TYPE_RESTRICT (TREE_TYPE (decl)))
5783 || vi->only_restrict_pointers)
5785 varinfo_t rvi
5786 = make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
5787 /* ??? For now exclude reads from globals as restrict sources
5788 if those are not (indirectly) from incoming parameters. */
5789 rvi->is_restrict_var = false;
5790 continue;
5793 /* In non-IPA mode the initializer from nonlocal is all we need. */
5794 if (!in_ipa_mode
5795 || DECL_HARD_REGISTER (decl))
5796 make_copy_constraint (vi, nonlocal_id);
5798 /* In IPA mode parse the initializer and generate proper constraints
5799 for it. */
5800 else
5802 varpool_node *vnode = varpool_node::get (decl);
5804 /* For escaped variables initialize them from nonlocal. */
5805 if (!vnode->all_refs_explicit_p ())
5806 make_copy_constraint (vi, nonlocal_id);
5808 /* If this is a global variable with an initializer and we are in
5809 IPA mode generate constraints for it. */
5810 if (vnode->get_constructor ()
5811 && vnode->definition)
5813 auto_vec<ce_s> rhsc;
5814 struct constraint_expr lhs, *rhsp;
5815 unsigned i;
5816 get_constraint_for_rhs (vnode->get_constructor (), &rhsc);
5817 lhs.var = vi->id;
5818 lhs.offset = 0;
5819 lhs.type = SCALAR;
5820 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5821 process_constraint (new_constraint (lhs, *rhsp));
5822 /* If this is a variable that escapes from the unit
5823 the initializer escapes as well. */
5824 if (!vnode->all_refs_explicit_p ())
5826 lhs.var = escaped_id;
5827 lhs.offset = 0;
5828 lhs.type = SCALAR;
5829 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5830 process_constraint (new_constraint (lhs, *rhsp));
5836 return id;
5839 /* Print out the points-to solution for VAR to FILE. */
5841 static void
5842 dump_solution_for_var (FILE *file, unsigned int var)
5844 varinfo_t vi = get_varinfo (var);
5845 unsigned int i;
5846 bitmap_iterator bi;
5848 /* Dump the solution for unified vars anyway, this avoids difficulties
5849 in scanning dumps in the testsuite. */
5850 fprintf (file, "%s = { ", vi->name);
5851 vi = get_varinfo (find (var));
5852 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5853 fprintf (file, "%s ", get_varinfo (i)->name);
5854 fprintf (file, "}");
5856 /* But note when the variable was unified. */
5857 if (vi->id != var)
5858 fprintf (file, " same as %s", vi->name);
5860 fprintf (file, "\n");
5863 /* Print the points-to solution for VAR to stderr. */
5865 DEBUG_FUNCTION void
5866 debug_solution_for_var (unsigned int var)
5868 dump_solution_for_var (stderr, var);
5871 /* Create varinfo structures for all of the variables in the
5872 function for intraprocedural mode. */
5874 static void
5875 intra_create_variable_infos (struct function *fn)
5877 tree t;
5879 /* For each incoming pointer argument arg, create the constraint ARG
5880 = NONLOCAL or a dummy variable if it is a restrict qualified
5881 passed-by-reference argument. */
5882 for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t))
5884 varinfo_t p = get_vi_for_tree (t);
5886 /* For restrict qualified pointers to objects passed by
5887 reference build a real representative for the pointed-to object.
5888 Treat restrict qualified references the same. */
5889 if (TYPE_RESTRICT (TREE_TYPE (t))
5890 && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
5891 || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
5892 && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
5894 struct constraint_expr lhsc, rhsc;
5895 varinfo_t vi;
5896 tree heapvar = build_fake_var_decl (TREE_TYPE (TREE_TYPE (t)));
5897 DECL_EXTERNAL (heapvar) = 1;
5898 vi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS");
5899 vi->is_restrict_var = 1;
5900 insert_vi_for_tree (heapvar, vi);
5901 lhsc.var = p->id;
5902 lhsc.type = SCALAR;
5903 lhsc.offset = 0;
5904 rhsc.var = vi->id;
5905 rhsc.type = ADDRESSOF;
5906 rhsc.offset = 0;
5907 process_constraint (new_constraint (lhsc, rhsc));
5908 for (; vi; vi = vi_next (vi))
5909 if (vi->may_have_pointers)
5911 if (vi->only_restrict_pointers)
5912 make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
5913 else
5914 make_copy_constraint (vi, nonlocal_id);
5916 continue;
5919 if (POINTER_TYPE_P (TREE_TYPE (t))
5920 && TYPE_RESTRICT (TREE_TYPE (t)))
5921 make_constraint_from_global_restrict (p, "PARM_RESTRICT");
5922 else
5924 for (; p; p = vi_next (p))
5926 if (p->only_restrict_pointers)
5927 make_constraint_from_global_restrict (p, "PARM_RESTRICT");
5928 else if (p->may_have_pointers)
5929 make_constraint_from (p, nonlocal_id);
5934 /* Add a constraint for a result decl that is passed by reference. */
5935 if (DECL_RESULT (fn->decl)
5936 && DECL_BY_REFERENCE (DECL_RESULT (fn->decl)))
5938 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (fn->decl));
5940 for (p = result_vi; p; p = vi_next (p))
5941 make_constraint_from (p, nonlocal_id);
5944 /* Add a constraint for the incoming static chain parameter. */
5945 if (fn->static_chain_decl != NULL_TREE)
5947 varinfo_t p, chain_vi = get_vi_for_tree (fn->static_chain_decl);
5949 for (p = chain_vi; p; p = vi_next (p))
5950 make_constraint_from (p, nonlocal_id);
5954 /* Structure used to put solution bitmaps in a hashtable so they can
5955 be shared among variables with the same points-to set. */
5957 typedef struct shared_bitmap_info
5959 bitmap pt_vars;
5960 hashval_t hashcode;
5961 } *shared_bitmap_info_t;
5962 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
5964 /* Shared_bitmap hashtable helpers. */
5966 struct shared_bitmap_hasher : typed_free_remove <shared_bitmap_info>
5968 typedef shared_bitmap_info *value_type;
5969 typedef shared_bitmap_info *compare_type;
5970 static inline hashval_t hash (const shared_bitmap_info *);
5971 static inline bool equal (const shared_bitmap_info *,
5972 const shared_bitmap_info *);
5975 /* Hash function for a shared_bitmap_info_t */
5977 inline hashval_t
5978 shared_bitmap_hasher::hash (const shared_bitmap_info *bi)
5980 return bi->hashcode;
5983 /* Equality function for two shared_bitmap_info_t's. */
5985 inline bool
5986 shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1,
5987 const shared_bitmap_info *sbi2)
5989 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
5992 /* Shared_bitmap hashtable. */
5994 static hash_table<shared_bitmap_hasher> *shared_bitmap_table;
5996 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
5997 existing instance if there is one, NULL otherwise. */
5999 static bitmap
6000 shared_bitmap_lookup (bitmap pt_vars)
6002 shared_bitmap_info **slot;
6003 struct shared_bitmap_info sbi;
6005 sbi.pt_vars = pt_vars;
6006 sbi.hashcode = bitmap_hash (pt_vars);
6008 slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
6009 if (!slot)
6010 return NULL;
6011 else
6012 return (*slot)->pt_vars;
6016 /* Add a bitmap to the shared bitmap hashtable. */
6018 static void
6019 shared_bitmap_add (bitmap pt_vars)
6021 shared_bitmap_info **slot;
6022 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
6024 sbi->pt_vars = pt_vars;
6025 sbi->hashcode = bitmap_hash (pt_vars);
6027 slot = shared_bitmap_table->find_slot (sbi, INSERT);
6028 gcc_assert (!*slot);
6029 *slot = sbi;
6033 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
6035 static void
6036 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt)
6038 unsigned int i;
6039 bitmap_iterator bi;
6040 varinfo_t escaped_vi = get_varinfo (find (escaped_id));
6041 bool everything_escaped
6042 = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
6044 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
6046 varinfo_t vi = get_varinfo (i);
6048 /* The only artificial variables that are allowed in a may-alias
6049 set are heap variables. */
6050 if (vi->is_artificial_var && !vi->is_heap_var)
6051 continue;
6053 if (everything_escaped
6054 || (escaped_vi->solution
6055 && bitmap_bit_p (escaped_vi->solution, i)))
6057 pt->vars_contains_escaped = true;
6058 pt->vars_contains_escaped_heap = vi->is_heap_var;
6061 if (TREE_CODE (vi->decl) == VAR_DECL
6062 || TREE_CODE (vi->decl) == PARM_DECL
6063 || TREE_CODE (vi->decl) == RESULT_DECL)
6065 /* If we are in IPA mode we will not recompute points-to
6066 sets after inlining so make sure they stay valid. */
6067 if (in_ipa_mode
6068 && !DECL_PT_UID_SET_P (vi->decl))
6069 SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
6071 /* Add the decl to the points-to set. Note that the points-to
6072 set contains global variables. */
6073 bitmap_set_bit (into, DECL_PT_UID (vi->decl));
6074 if (vi->is_global_var)
6075 pt->vars_contains_nonlocal = true;
6081 /* Compute the points-to solution *PT for the variable VI. */
6083 static struct pt_solution
6084 find_what_var_points_to (varinfo_t orig_vi)
6086 unsigned int i;
6087 bitmap_iterator bi;
6088 bitmap finished_solution;
6089 bitmap result;
6090 varinfo_t vi;
6091 struct pt_solution *pt;
6093 /* This variable may have been collapsed, let's get the real
6094 variable. */
6095 vi = get_varinfo (find (orig_vi->id));
6097 /* See if we have already computed the solution and return it. */
6098 pt_solution **slot = &final_solutions->get_or_insert (vi);
6099 if (*slot != NULL)
6100 return **slot;
6102 *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
6103 memset (pt, 0, sizeof (struct pt_solution));
6105 /* Translate artificial variables into SSA_NAME_PTR_INFO
6106 attributes. */
6107 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
6109 varinfo_t vi = get_varinfo (i);
6111 if (vi->is_artificial_var)
6113 if (vi->id == nothing_id)
6114 pt->null = 1;
6115 else if (vi->id == escaped_id)
6117 if (in_ipa_mode)
6118 pt->ipa_escaped = 1;
6119 else
6120 pt->escaped = 1;
6121 /* Expand some special vars of ESCAPED in-place here. */
6122 varinfo_t evi = get_varinfo (find (escaped_id));
6123 if (bitmap_bit_p (evi->solution, nonlocal_id))
6124 pt->nonlocal = 1;
6126 else if (vi->id == nonlocal_id)
6127 pt->nonlocal = 1;
6128 else if (vi->is_heap_var)
6129 /* We represent heapvars in the points-to set properly. */
6131 else if (vi->id == string_id)
6132 /* Nobody cares - STRING_CSTs are read-only entities. */
6134 else if (vi->id == anything_id
6135 || vi->id == integer_id)
6136 pt->anything = 1;
6140 /* Instead of doing extra work, simply do not create
6141 elaborate points-to information for pt_anything pointers. */
6142 if (pt->anything)
6143 return *pt;
6145 /* Share the final set of variables when possible. */
6146 finished_solution = BITMAP_GGC_ALLOC ();
6147 stats.points_to_sets_created++;
6149 set_uids_in_ptset (finished_solution, vi->solution, pt);
6150 result = shared_bitmap_lookup (finished_solution);
6151 if (!result)
6153 shared_bitmap_add (finished_solution);
6154 pt->vars = finished_solution;
6156 else
6158 pt->vars = result;
6159 bitmap_clear (finished_solution);
6162 return *pt;
6165 /* Given a pointer variable P, fill in its points-to set. */
6167 static void
6168 find_what_p_points_to (tree p)
6170 struct ptr_info_def *pi;
6171 tree lookup_p = p;
6172 varinfo_t vi;
6174 /* For parameters, get at the points-to set for the actual parm
6175 decl. */
6176 if (TREE_CODE (p) == SSA_NAME
6177 && SSA_NAME_IS_DEFAULT_DEF (p)
6178 && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
6179 || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
6180 lookup_p = SSA_NAME_VAR (p);
6182 vi = lookup_vi_for_tree (lookup_p);
6183 if (!vi)
6184 return;
6186 pi = get_ptr_info (p);
6187 pi->pt = find_what_var_points_to (vi);
6191 /* Query statistics for points-to solutions. */
6193 static struct {
6194 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
6195 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
6196 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
6197 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
6198 } pta_stats;
6200 void
6201 dump_pta_stats (FILE *s)
6203 fprintf (s, "\nPTA query stats:\n");
6204 fprintf (s, " pt_solution_includes: "
6205 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6206 HOST_WIDE_INT_PRINT_DEC" queries\n",
6207 pta_stats.pt_solution_includes_no_alias,
6208 pta_stats.pt_solution_includes_no_alias
6209 + pta_stats.pt_solution_includes_may_alias);
6210 fprintf (s, " pt_solutions_intersect: "
6211 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6212 HOST_WIDE_INT_PRINT_DEC" queries\n",
6213 pta_stats.pt_solutions_intersect_no_alias,
6214 pta_stats.pt_solutions_intersect_no_alias
6215 + pta_stats.pt_solutions_intersect_may_alias);
6219 /* Reset the points-to solution *PT to a conservative default
6220 (point to anything). */
6222 void
6223 pt_solution_reset (struct pt_solution *pt)
6225 memset (pt, 0, sizeof (struct pt_solution));
6226 pt->anything = true;
6229 /* Set the points-to solution *PT to point only to the variables
6230 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6231 global variables and VARS_CONTAINS_RESTRICT specifies whether
6232 it contains restrict tag variables. */
6234 void
6235 pt_solution_set (struct pt_solution *pt, bitmap vars,
6236 bool vars_contains_nonlocal)
6238 memset (pt, 0, sizeof (struct pt_solution));
6239 pt->vars = vars;
6240 pt->vars_contains_nonlocal = vars_contains_nonlocal;
6241 pt->vars_contains_escaped
6242 = (cfun->gimple_df->escaped.anything
6243 || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
6246 /* Set the points-to solution *PT to point only to the variable VAR. */
6248 void
6249 pt_solution_set_var (struct pt_solution *pt, tree var)
6251 memset (pt, 0, sizeof (struct pt_solution));
6252 pt->vars = BITMAP_GGC_ALLOC ();
6253 bitmap_set_bit (pt->vars, DECL_PT_UID (var));
6254 pt->vars_contains_nonlocal = is_global_var (var);
6255 pt->vars_contains_escaped
6256 = (cfun->gimple_df->escaped.anything
6257 || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
6260 /* Computes the union of the points-to solutions *DEST and *SRC and
6261 stores the result in *DEST. This changes the points-to bitmap
6262 of *DEST and thus may not be used if that might be shared.
6263 The points-to bitmap of *SRC and *DEST will not be shared after
6264 this function if they were not before. */
6266 static void
6267 pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
6269 dest->anything |= src->anything;
6270 if (dest->anything)
6272 pt_solution_reset (dest);
6273 return;
6276 dest->nonlocal |= src->nonlocal;
6277 dest->escaped |= src->escaped;
6278 dest->ipa_escaped |= src->ipa_escaped;
6279 dest->null |= src->null;
6280 dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
6281 dest->vars_contains_escaped |= src->vars_contains_escaped;
6282 dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
6283 if (!src->vars)
6284 return;
6286 if (!dest->vars)
6287 dest->vars = BITMAP_GGC_ALLOC ();
6288 bitmap_ior_into (dest->vars, src->vars);
6291 /* Return true if the points-to solution *PT is empty. */
6293 bool
6294 pt_solution_empty_p (struct pt_solution *pt)
6296 if (pt->anything
6297 || pt->nonlocal)
6298 return false;
6300 if (pt->vars
6301 && !bitmap_empty_p (pt->vars))
6302 return false;
6304 /* If the solution includes ESCAPED, check if that is empty. */
6305 if (pt->escaped
6306 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
6307 return false;
6309 /* If the solution includes ESCAPED, check if that is empty. */
6310 if (pt->ipa_escaped
6311 && !pt_solution_empty_p (&ipa_escaped_pt))
6312 return false;
6314 return true;
6317 /* Return true if the points-to solution *PT only point to a single var, and
6318 return the var uid in *UID. */
6320 bool
6321 pt_solution_singleton_p (struct pt_solution *pt, unsigned *uid)
6323 if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
6324 || pt->null || pt->vars == NULL
6325 || !bitmap_single_bit_set_p (pt->vars))
6326 return false;
6328 *uid = bitmap_first_set_bit (pt->vars);
6329 return true;
6332 /* Return true if the points-to solution *PT includes global memory. */
6334 bool
6335 pt_solution_includes_global (struct pt_solution *pt)
6337 if (pt->anything
6338 || pt->nonlocal
6339 || pt->vars_contains_nonlocal
6340 /* The following is a hack to make the malloc escape hack work.
6341 In reality we'd need different sets for escaped-through-return
6342 and escaped-to-callees and passes would need to be updated. */
6343 || pt->vars_contains_escaped_heap)
6344 return true;
6346 /* 'escaped' is also a placeholder so we have to look into it. */
6347 if (pt->escaped)
6348 return pt_solution_includes_global (&cfun->gimple_df->escaped);
6350 if (pt->ipa_escaped)
6351 return pt_solution_includes_global (&ipa_escaped_pt);
6353 /* ??? This predicate is not correct for the IPA-PTA solution
6354 as we do not properly distinguish between unit escape points
6355 and global variables. */
6356 if (cfun->gimple_df->ipa_pta)
6357 return true;
6359 return false;
6362 /* Return true if the points-to solution *PT includes the variable
6363 declaration DECL. */
6365 static bool
6366 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
6368 if (pt->anything)
6369 return true;
6371 if (pt->nonlocal
6372 && is_global_var (decl))
6373 return true;
6375 if (pt->vars
6376 && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
6377 return true;
6379 /* If the solution includes ESCAPED, check it. */
6380 if (pt->escaped
6381 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
6382 return true;
6384 /* If the solution includes ESCAPED, check it. */
6385 if (pt->ipa_escaped
6386 && pt_solution_includes_1 (&ipa_escaped_pt, decl))
6387 return true;
6389 return false;
6392 bool
6393 pt_solution_includes (struct pt_solution *pt, const_tree decl)
6395 bool res = pt_solution_includes_1 (pt, decl);
6396 if (res)
6397 ++pta_stats.pt_solution_includes_may_alias;
6398 else
6399 ++pta_stats.pt_solution_includes_no_alias;
6400 return res;
6403 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6404 intersection. */
6406 static bool
6407 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
6409 if (pt1->anything || pt2->anything)
6410 return true;
6412 /* If either points to unknown global memory and the other points to
6413 any global memory they alias. */
6414 if ((pt1->nonlocal
6415 && (pt2->nonlocal
6416 || pt2->vars_contains_nonlocal))
6417 || (pt2->nonlocal
6418 && pt1->vars_contains_nonlocal))
6419 return true;
6421 /* If either points to all escaped memory and the other points to
6422 any escaped memory they alias. */
6423 if ((pt1->escaped
6424 && (pt2->escaped
6425 || pt2->vars_contains_escaped))
6426 || (pt2->escaped
6427 && pt1->vars_contains_escaped))
6428 return true;
6430 /* Check the escaped solution if required.
6431 ??? Do we need to check the local against the IPA escaped sets? */
6432 if ((pt1->ipa_escaped || pt2->ipa_escaped)
6433 && !pt_solution_empty_p (&ipa_escaped_pt))
6435 /* If both point to escaped memory and that solution
6436 is not empty they alias. */
6437 if (pt1->ipa_escaped && pt2->ipa_escaped)
6438 return true;
6440 /* If either points to escaped memory see if the escaped solution
6441 intersects with the other. */
6442 if ((pt1->ipa_escaped
6443 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
6444 || (pt2->ipa_escaped
6445 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
6446 return true;
6449 /* Now both pointers alias if their points-to solution intersects. */
6450 return (pt1->vars
6451 && pt2->vars
6452 && bitmap_intersect_p (pt1->vars, pt2->vars));
6455 bool
6456 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
6458 bool res = pt_solutions_intersect_1 (pt1, pt2);
6459 if (res)
6460 ++pta_stats.pt_solutions_intersect_may_alias;
6461 else
6462 ++pta_stats.pt_solutions_intersect_no_alias;
6463 return res;
6467 /* Dump points-to information to OUTFILE. */
6469 static void
6470 dump_sa_points_to_info (FILE *outfile)
6472 unsigned int i;
6474 fprintf (outfile, "\nPoints-to sets\n\n");
6476 if (dump_flags & TDF_STATS)
6478 fprintf (outfile, "Stats:\n");
6479 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
6480 fprintf (outfile, "Non-pointer vars: %d\n",
6481 stats.nonpointer_vars);
6482 fprintf (outfile, "Statically unified vars: %d\n",
6483 stats.unified_vars_static);
6484 fprintf (outfile, "Dynamically unified vars: %d\n",
6485 stats.unified_vars_dynamic);
6486 fprintf (outfile, "Iterations: %d\n", stats.iterations);
6487 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
6488 fprintf (outfile, "Number of implicit edges: %d\n",
6489 stats.num_implicit_edges);
6492 for (i = 1; i < varmap.length (); i++)
6494 varinfo_t vi = get_varinfo (i);
6495 if (!vi->may_have_pointers)
6496 continue;
6497 dump_solution_for_var (outfile, i);
6502 /* Debug points-to information to stderr. */
6504 DEBUG_FUNCTION void
6505 debug_sa_points_to_info (void)
6507 dump_sa_points_to_info (stderr);
6511 /* Initialize the always-existing constraint variables for NULL
6512 ANYTHING, READONLY, and INTEGER */
6514 static void
6515 init_base_vars (void)
6517 struct constraint_expr lhs, rhs;
6518 varinfo_t var_anything;
6519 varinfo_t var_nothing;
6520 varinfo_t var_string;
6521 varinfo_t var_escaped;
6522 varinfo_t var_nonlocal;
6523 varinfo_t var_storedanything;
6524 varinfo_t var_integer;
6526 /* Variable ID zero is reserved and should be NULL. */
6527 varmap.safe_push (NULL);
6529 /* Create the NULL variable, used to represent that a variable points
6530 to NULL. */
6531 var_nothing = new_var_info (NULL_TREE, "NULL");
6532 gcc_assert (var_nothing->id == nothing_id);
6533 var_nothing->is_artificial_var = 1;
6534 var_nothing->offset = 0;
6535 var_nothing->size = ~0;
6536 var_nothing->fullsize = ~0;
6537 var_nothing->is_special_var = 1;
6538 var_nothing->may_have_pointers = 0;
6539 var_nothing->is_global_var = 0;
6541 /* Create the ANYTHING variable, used to represent that a variable
6542 points to some unknown piece of memory. */
6543 var_anything = new_var_info (NULL_TREE, "ANYTHING");
6544 gcc_assert (var_anything->id == anything_id);
6545 var_anything->is_artificial_var = 1;
6546 var_anything->size = ~0;
6547 var_anything->offset = 0;
6548 var_anything->fullsize = ~0;
6549 var_anything->is_special_var = 1;
6551 /* Anything points to anything. This makes deref constraints just
6552 work in the presence of linked list and other p = *p type loops,
6553 by saying that *ANYTHING = ANYTHING. */
6554 lhs.type = SCALAR;
6555 lhs.var = anything_id;
6556 lhs.offset = 0;
6557 rhs.type = ADDRESSOF;
6558 rhs.var = anything_id;
6559 rhs.offset = 0;
6561 /* This specifically does not use process_constraint because
6562 process_constraint ignores all anything = anything constraints, since all
6563 but this one are redundant. */
6564 constraints.safe_push (new_constraint (lhs, rhs));
6566 /* Create the STRING variable, used to represent that a variable
6567 points to a string literal. String literals don't contain
6568 pointers so STRING doesn't point to anything. */
6569 var_string = new_var_info (NULL_TREE, "STRING");
6570 gcc_assert (var_string->id == string_id);
6571 var_string->is_artificial_var = 1;
6572 var_string->offset = 0;
6573 var_string->size = ~0;
6574 var_string->fullsize = ~0;
6575 var_string->is_special_var = 1;
6576 var_string->may_have_pointers = 0;
6578 /* Create the ESCAPED variable, used to represent the set of escaped
6579 memory. */
6580 var_escaped = new_var_info (NULL_TREE, "ESCAPED");
6581 gcc_assert (var_escaped->id == escaped_id);
6582 var_escaped->is_artificial_var = 1;
6583 var_escaped->offset = 0;
6584 var_escaped->size = ~0;
6585 var_escaped->fullsize = ~0;
6586 var_escaped->is_special_var = 0;
6588 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6589 memory. */
6590 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL");
6591 gcc_assert (var_nonlocal->id == nonlocal_id);
6592 var_nonlocal->is_artificial_var = 1;
6593 var_nonlocal->offset = 0;
6594 var_nonlocal->size = ~0;
6595 var_nonlocal->fullsize = ~0;
6596 var_nonlocal->is_special_var = 1;
6598 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6599 lhs.type = SCALAR;
6600 lhs.var = escaped_id;
6601 lhs.offset = 0;
6602 rhs.type = DEREF;
6603 rhs.var = escaped_id;
6604 rhs.offset = 0;
6605 process_constraint (new_constraint (lhs, rhs));
6607 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6608 whole variable escapes. */
6609 lhs.type = SCALAR;
6610 lhs.var = escaped_id;
6611 lhs.offset = 0;
6612 rhs.type = SCALAR;
6613 rhs.var = escaped_id;
6614 rhs.offset = UNKNOWN_OFFSET;
6615 process_constraint (new_constraint (lhs, rhs));
6617 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6618 everything pointed to by escaped points to what global memory can
6619 point to. */
6620 lhs.type = DEREF;
6621 lhs.var = escaped_id;
6622 lhs.offset = 0;
6623 rhs.type = SCALAR;
6624 rhs.var = nonlocal_id;
6625 rhs.offset = 0;
6626 process_constraint (new_constraint (lhs, rhs));
6628 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6629 global memory may point to global memory and escaped memory. */
6630 lhs.type = SCALAR;
6631 lhs.var = nonlocal_id;
6632 lhs.offset = 0;
6633 rhs.type = ADDRESSOF;
6634 rhs.var = nonlocal_id;
6635 rhs.offset = 0;
6636 process_constraint (new_constraint (lhs, rhs));
6637 rhs.type = ADDRESSOF;
6638 rhs.var = escaped_id;
6639 rhs.offset = 0;
6640 process_constraint (new_constraint (lhs, rhs));
6642 /* Create the STOREDANYTHING variable, used to represent the set of
6643 variables stored to *ANYTHING. */
6644 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING");
6645 gcc_assert (var_storedanything->id == storedanything_id);
6646 var_storedanything->is_artificial_var = 1;
6647 var_storedanything->offset = 0;
6648 var_storedanything->size = ~0;
6649 var_storedanything->fullsize = ~0;
6650 var_storedanything->is_special_var = 0;
6652 /* Create the INTEGER variable, used to represent that a variable points
6653 to what an INTEGER "points to". */
6654 var_integer = new_var_info (NULL_TREE, "INTEGER");
6655 gcc_assert (var_integer->id == integer_id);
6656 var_integer->is_artificial_var = 1;
6657 var_integer->size = ~0;
6658 var_integer->fullsize = ~0;
6659 var_integer->offset = 0;
6660 var_integer->is_special_var = 1;
6662 /* INTEGER = ANYTHING, because we don't know where a dereference of
6663 a random integer will point to. */
6664 lhs.type = SCALAR;
6665 lhs.var = integer_id;
6666 lhs.offset = 0;
6667 rhs.type = ADDRESSOF;
6668 rhs.var = anything_id;
6669 rhs.offset = 0;
6670 process_constraint (new_constraint (lhs, rhs));
6673 /* Initialize things necessary to perform PTA */
6675 static void
6676 init_alias_vars (void)
6678 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
6680 bitmap_obstack_initialize (&pta_obstack);
6681 bitmap_obstack_initialize (&oldpta_obstack);
6682 bitmap_obstack_initialize (&predbitmap_obstack);
6684 constraint_pool = create_alloc_pool ("Constraint pool",
6685 sizeof (struct constraint), 30);
6686 variable_info_pool = create_alloc_pool ("Variable info pool",
6687 sizeof (struct variable_info), 30);
6688 constraints.create (8);
6689 varmap.create (8);
6690 vi_for_tree = new hash_map<tree, varinfo_t>;
6691 call_stmt_vars = new hash_map<gimple, varinfo_t>;
6693 memset (&stats, 0, sizeof (stats));
6694 shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
6695 init_base_vars ();
6697 gcc_obstack_init (&fake_var_decl_obstack);
6699 final_solutions = new hash_map<varinfo_t, pt_solution *>;
6700 gcc_obstack_init (&final_solutions_obstack);
6703 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6704 predecessor edges. */
6706 static void
6707 remove_preds_and_fake_succs (constraint_graph_t graph)
6709 unsigned int i;
6711 /* Clear the implicit ref and address nodes from the successor
6712 lists. */
6713 for (i = 1; i < FIRST_REF_NODE; i++)
6715 if (graph->succs[i])
6716 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
6717 FIRST_REF_NODE * 2);
6720 /* Free the successor list for the non-ref nodes. */
6721 for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
6723 if (graph->succs[i])
6724 BITMAP_FREE (graph->succs[i]);
6727 /* Now reallocate the size of the successor list as, and blow away
6728 the predecessor bitmaps. */
6729 graph->size = varmap.length ();
6730 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
6732 free (graph->implicit_preds);
6733 graph->implicit_preds = NULL;
6734 free (graph->preds);
6735 graph->preds = NULL;
6736 bitmap_obstack_release (&predbitmap_obstack);
6739 /* Solve the constraint set. */
6741 static void
6742 solve_constraints (void)
6744 struct scc_info *si;
6746 if (dump_file)
6747 fprintf (dump_file,
6748 "\nCollapsing static cycles and doing variable "
6749 "substitution\n");
6751 init_graph (varmap.length () * 2);
6753 if (dump_file)
6754 fprintf (dump_file, "Building predecessor graph\n");
6755 build_pred_graph ();
6757 if (dump_file)
6758 fprintf (dump_file, "Detecting pointer and location "
6759 "equivalences\n");
6760 si = perform_var_substitution (graph);
6762 if (dump_file)
6763 fprintf (dump_file, "Rewriting constraints and unifying "
6764 "variables\n");
6765 rewrite_constraints (graph, si);
6767 build_succ_graph ();
6769 free_var_substitution_info (si);
6771 /* Attach complex constraints to graph nodes. */
6772 move_complex_constraints (graph);
6774 if (dump_file)
6775 fprintf (dump_file, "Uniting pointer but not location equivalent "
6776 "variables\n");
6777 unite_pointer_equivalences (graph);
6779 if (dump_file)
6780 fprintf (dump_file, "Finding indirect cycles\n");
6781 find_indirect_cycles (graph);
6783 /* Implicit nodes and predecessors are no longer necessary at this
6784 point. */
6785 remove_preds_and_fake_succs (graph);
6787 if (dump_file && (dump_flags & TDF_GRAPH))
6789 fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
6790 "in dot format:\n");
6791 dump_constraint_graph (dump_file);
6792 fprintf (dump_file, "\n\n");
6795 if (dump_file)
6796 fprintf (dump_file, "Solving graph\n");
6798 solve_graph (graph);
6800 if (dump_file && (dump_flags & TDF_GRAPH))
6802 fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
6803 "in dot format:\n");
6804 dump_constraint_graph (dump_file);
6805 fprintf (dump_file, "\n\n");
6808 if (dump_file)
6809 dump_sa_points_to_info (dump_file);
6812 /* Create points-to sets for the current function. See the comments
6813 at the start of the file for an algorithmic overview. */
6815 static void
6816 compute_points_to_sets (void)
6818 basic_block bb;
6819 unsigned i;
6820 varinfo_t vi;
6822 timevar_push (TV_TREE_PTA);
6824 init_alias_vars ();
6826 intra_create_variable_infos (cfun);
6828 /* Now walk all statements and build the constraint set. */
6829 FOR_EACH_BB_FN (bb, cfun)
6831 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
6832 gsi_next (&gsi))
6834 gphi *phi = gsi.phi ();
6836 if (! virtual_operand_p (gimple_phi_result (phi)))
6837 find_func_aliases (cfun, phi);
6840 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
6841 gsi_next (&gsi))
6843 gimple stmt = gsi_stmt (gsi);
6845 find_func_aliases (cfun, stmt);
6849 if (dump_file)
6851 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
6852 dump_constraints (dump_file, 0);
6855 /* From the constraints compute the points-to sets. */
6856 solve_constraints ();
6858 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
6859 cfun->gimple_df->escaped = find_what_var_points_to (get_varinfo (escaped_id));
6861 /* Make sure the ESCAPED solution (which is used as placeholder in
6862 other solutions) does not reference itself. This simplifies
6863 points-to solution queries. */
6864 cfun->gimple_df->escaped.escaped = 0;
6866 /* Compute the points-to sets for pointer SSA_NAMEs. */
6867 for (i = 0; i < num_ssa_names; ++i)
6869 tree ptr = ssa_name (i);
6870 if (ptr
6871 && POINTER_TYPE_P (TREE_TYPE (ptr)))
6872 find_what_p_points_to (ptr);
6875 /* Compute the call-used/clobbered sets. */
6876 FOR_EACH_BB_FN (bb, cfun)
6878 gimple_stmt_iterator gsi;
6880 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6882 gcall *stmt;
6883 struct pt_solution *pt;
6885 stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
6886 if (!stmt)
6887 continue;
6889 pt = gimple_call_use_set (stmt);
6890 if (gimple_call_flags (stmt) & ECF_CONST)
6891 memset (pt, 0, sizeof (struct pt_solution));
6892 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
6894 *pt = find_what_var_points_to (vi);
6895 /* Escaped (and thus nonlocal) variables are always
6896 implicitly used by calls. */
6897 /* ??? ESCAPED can be empty even though NONLOCAL
6898 always escaped. */
6899 pt->nonlocal = 1;
6900 pt->escaped = 1;
6902 else
6904 /* If there is nothing special about this call then
6905 we have made everything that is used also escape. */
6906 *pt = cfun->gimple_df->escaped;
6907 pt->nonlocal = 1;
6910 pt = gimple_call_clobber_set (stmt);
6911 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
6912 memset (pt, 0, sizeof (struct pt_solution));
6913 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
6915 *pt = find_what_var_points_to (vi);
6916 /* Escaped (and thus nonlocal) variables are always
6917 implicitly clobbered by calls. */
6918 /* ??? ESCAPED can be empty even though NONLOCAL
6919 always escaped. */
6920 pt->nonlocal = 1;
6921 pt->escaped = 1;
6923 else
6925 /* If there is nothing special about this call then
6926 we have made everything that is used also escape. */
6927 *pt = cfun->gimple_df->escaped;
6928 pt->nonlocal = 1;
6933 timevar_pop (TV_TREE_PTA);
6937 /* Delete created points-to sets. */
6939 static void
6940 delete_points_to_sets (void)
6942 unsigned int i;
6944 delete shared_bitmap_table;
6945 shared_bitmap_table = NULL;
6946 if (dump_file && (dump_flags & TDF_STATS))
6947 fprintf (dump_file, "Points to sets created:%d\n",
6948 stats.points_to_sets_created);
6950 delete vi_for_tree;
6951 delete call_stmt_vars;
6952 bitmap_obstack_release (&pta_obstack);
6953 constraints.release ();
6955 for (i = 0; i < graph->size; i++)
6956 graph->complex[i].release ();
6957 free (graph->complex);
6959 free (graph->rep);
6960 free (graph->succs);
6961 free (graph->pe);
6962 free (graph->pe_rep);
6963 free (graph->indirect_cycles);
6964 free (graph);
6966 varmap.release ();
6967 free_alloc_pool (variable_info_pool);
6968 free_alloc_pool (constraint_pool);
6970 obstack_free (&fake_var_decl_obstack, NULL);
6972 delete final_solutions;
6973 obstack_free (&final_solutions_obstack, NULL);
6976 /* Mark "other" loads and stores as belonging to CLIQUE and with
6977 base zero. */
6979 static bool
6980 visit_loadstore (gimple, tree base, tree ref, void *clique_)
6982 unsigned short clique = (uintptr_t)clique_;
6983 if (TREE_CODE (base) == MEM_REF
6984 || TREE_CODE (base) == TARGET_MEM_REF)
6986 tree ptr = TREE_OPERAND (base, 0);
6987 if (TREE_CODE (ptr) == SSA_NAME)
6989 /* ??? We need to make sure 'ptr' doesn't include any of
6990 the restrict tags in its points-to set. */
6991 return false;
6994 /* For now let decls through. */
6996 /* Do not overwrite existing cliques (that includes clique, base
6997 pairs we just set). */
6998 if (MR_DEPENDENCE_CLIQUE (base) == 0)
7000 MR_DEPENDENCE_CLIQUE (base) = clique;
7001 MR_DEPENDENCE_BASE (base) = 0;
7005 /* For plain decl accesses see whether they are accesses to globals
7006 and rewrite them to MEM_REFs with { clique, 0 }. */
7007 if (TREE_CODE (base) == VAR_DECL
7008 && is_global_var (base)
7009 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
7010 ops callback. */
7011 && base != ref)
7013 tree *basep = &ref;
7014 while (handled_component_p (*basep))
7015 basep = &TREE_OPERAND (*basep, 0);
7016 gcc_assert (TREE_CODE (*basep) == VAR_DECL);
7017 tree ptr = build_fold_addr_expr (*basep);
7018 tree zero = build_int_cst (TREE_TYPE (ptr), 0);
7019 *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero);
7020 MR_DEPENDENCE_CLIQUE (*basep) = clique;
7021 MR_DEPENDENCE_BASE (*basep) = 0;
7024 return false;
7027 /* If REF is a MEM_REF then assign a clique, base pair to it, updating
7028 CLIQUE, *RESTRICT_VAR and LAST_RUID. Return whether dependence info
7029 was assigned to REF. */
7031 static bool
7032 maybe_set_dependence_info (tree ref, tree ptr,
7033 unsigned short &clique, varinfo_t restrict_var,
7034 unsigned short &last_ruid)
7036 while (handled_component_p (ref))
7037 ref = TREE_OPERAND (ref, 0);
7038 if ((TREE_CODE (ref) == MEM_REF
7039 || TREE_CODE (ref) == TARGET_MEM_REF)
7040 && TREE_OPERAND (ref, 0) == ptr)
7042 /* Do not overwrite existing cliques. This avoids overwriting dependence
7043 info inlined from a function with restrict parameters inlined
7044 into a function with restrict parameters. This usually means we
7045 prefer to be precise in innermost loops. */
7046 if (MR_DEPENDENCE_CLIQUE (ref) == 0)
7048 if (clique == 0)
7049 clique = ++cfun->last_clique;
7050 if (restrict_var->ruid == 0)
7051 restrict_var->ruid = ++last_ruid;
7052 MR_DEPENDENCE_CLIQUE (ref) = clique;
7053 MR_DEPENDENCE_BASE (ref) = restrict_var->ruid;
7054 return true;
7057 return false;
7060 /* Compute the set of independend memory references based on restrict
7061 tags and their conservative propagation to the points-to sets. */
7063 static void
7064 compute_dependence_clique (void)
7066 unsigned short clique = 0;
7067 unsigned short last_ruid = 0;
7068 for (unsigned i = 0; i < num_ssa_names; ++i)
7070 tree ptr = ssa_name (i);
7071 if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr)))
7072 continue;
7074 /* Avoid all this when ptr is not dereferenced? */
7075 tree p = ptr;
7076 if (SSA_NAME_IS_DEFAULT_DEF (ptr)
7077 && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
7078 || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
7079 p = SSA_NAME_VAR (ptr);
7080 varinfo_t vi = lookup_vi_for_tree (p);
7081 if (!vi)
7082 continue;
7083 vi = get_varinfo (find (vi->id));
7084 bitmap_iterator bi;
7085 unsigned j;
7086 varinfo_t restrict_var = NULL;
7087 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
7089 varinfo_t oi = get_varinfo (j);
7090 if (oi->is_restrict_var)
7092 if (restrict_var)
7094 if (dump_file && (dump_flags & TDF_DETAILS))
7096 fprintf (dump_file, "found restrict pointed-to "
7097 "for ");
7098 print_generic_expr (dump_file, ptr, 0);
7099 fprintf (dump_file, " but not exclusively\n");
7101 restrict_var = NULL;
7102 break;
7104 restrict_var = oi;
7106 /* NULL is the only other valid points-to entry. */
7107 else if (oi->id != nothing_id)
7109 restrict_var = NULL;
7110 break;
7113 /* Ok, found that ptr must(!) point to a single(!) restrict
7114 variable. */
7115 /* ??? PTA isn't really a proper propagation engine to compute
7116 this property.
7117 ??? We could handle merging of two restricts by unifying them. */
7118 if (restrict_var)
7120 /* Now look at possible dereferences of ptr. */
7121 imm_use_iterator ui;
7122 gimple use_stmt;
7123 FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
7125 /* ??? Calls and asms. */
7126 if (!gimple_assign_single_p (use_stmt))
7127 continue;
7128 maybe_set_dependence_info (gimple_assign_lhs (use_stmt), ptr,
7129 clique, restrict_var, last_ruid);
7130 maybe_set_dependence_info (gimple_assign_rhs1 (use_stmt), ptr,
7131 clique, restrict_var, last_ruid);
7136 if (clique == 0)
7137 return;
7139 /* Assign the BASE id zero to all accesses not based on a restrict
7140 pointer. That way they get disabiguated against restrict
7141 accesses but not against each other. */
7142 /* ??? For restricts derived from globals (thus not incoming
7143 parameters) we can't restrict scoping properly thus the following
7144 is too aggressive there. For now we have excluded those globals from
7145 getting into the MR_DEPENDENCE machinery. */
7146 basic_block bb;
7147 FOR_EACH_BB_FN (bb, cfun)
7148 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
7149 !gsi_end_p (gsi); gsi_next (&gsi))
7151 gimple stmt = gsi_stmt (gsi);
7152 walk_stmt_load_store_ops (stmt, (void *)(uintptr_t)clique,
7153 visit_loadstore, visit_loadstore);
7157 /* Compute points-to information for every SSA_NAME pointer in the
7158 current function and compute the transitive closure of escaped
7159 variables to re-initialize the call-clobber states of local variables. */
7161 unsigned int
7162 compute_may_aliases (void)
7164 if (cfun->gimple_df->ipa_pta)
7166 if (dump_file)
7168 fprintf (dump_file, "\nNot re-computing points-to information "
7169 "because IPA points-to information is available.\n\n");
7171 /* But still dump what we have remaining it. */
7172 dump_alias_info (dump_file);
7175 return 0;
7178 /* For each pointer P_i, determine the sets of variables that P_i may
7179 point-to. Compute the reachability set of escaped and call-used
7180 variables. */
7181 compute_points_to_sets ();
7183 /* Debugging dumps. */
7184 if (dump_file)
7185 dump_alias_info (dump_file);
7187 /* Compute restrict-based memory disambiguations. */
7188 compute_dependence_clique ();
7190 /* Deallocate memory used by aliasing data structures and the internal
7191 points-to solution. */
7192 delete_points_to_sets ();
7194 gcc_assert (!need_ssa_update_p (cfun));
7196 return 0;
7199 /* A dummy pass to cause points-to information to be computed via
7200 TODO_rebuild_alias. */
7202 namespace {
7204 const pass_data pass_data_build_alias =
7206 GIMPLE_PASS, /* type */
7207 "alias", /* name */
7208 OPTGROUP_NONE, /* optinfo_flags */
7209 TV_NONE, /* tv_id */
7210 ( PROP_cfg | PROP_ssa ), /* properties_required */
7211 0, /* properties_provided */
7212 0, /* properties_destroyed */
7213 0, /* todo_flags_start */
7214 TODO_rebuild_alias, /* todo_flags_finish */
7217 class pass_build_alias : public gimple_opt_pass
7219 public:
7220 pass_build_alias (gcc::context *ctxt)
7221 : gimple_opt_pass (pass_data_build_alias, ctxt)
7224 /* opt_pass methods: */
7225 virtual bool gate (function *) { return flag_tree_pta; }
7227 }; // class pass_build_alias
7229 } // anon namespace
7231 gimple_opt_pass *
7232 make_pass_build_alias (gcc::context *ctxt)
7234 return new pass_build_alias (ctxt);
7237 /* A dummy pass to cause points-to information to be computed via
7238 TODO_rebuild_alias. */
7240 namespace {
7242 const pass_data pass_data_build_ealias =
7244 GIMPLE_PASS, /* type */
7245 "ealias", /* name */
7246 OPTGROUP_NONE, /* optinfo_flags */
7247 TV_NONE, /* tv_id */
7248 ( PROP_cfg | PROP_ssa ), /* properties_required */
7249 0, /* properties_provided */
7250 0, /* properties_destroyed */
7251 0, /* todo_flags_start */
7252 TODO_rebuild_alias, /* todo_flags_finish */
7255 class pass_build_ealias : public gimple_opt_pass
7257 public:
7258 pass_build_ealias (gcc::context *ctxt)
7259 : gimple_opt_pass (pass_data_build_ealias, ctxt)
7262 /* opt_pass methods: */
7263 virtual bool gate (function *) { return flag_tree_pta; }
7265 }; // class pass_build_ealias
7267 } // anon namespace
7269 gimple_opt_pass *
7270 make_pass_build_ealias (gcc::context *ctxt)
7272 return new pass_build_ealias (ctxt);
7276 /* IPA PTA solutions for ESCAPED. */
7277 struct pt_solution ipa_escaped_pt
7278 = { true, false, false, false, false, false, false, false, NULL };
7280 /* Associate node with varinfo DATA. Worker for
7281 cgraph_for_node_and_aliases. */
7282 static bool
7283 associate_varinfo_to_alias (struct cgraph_node *node, void *data)
7285 if ((node->alias || node->thunk.thunk_p)
7286 && node->analyzed)
7287 insert_vi_for_tree (node->decl, (varinfo_t)data);
7288 return false;
7291 /* Execute the driver for IPA PTA. */
7292 static unsigned int
7293 ipa_pta_execute (void)
7295 struct cgraph_node *node;
7296 varpool_node *var;
7297 int from;
7299 in_ipa_mode = 1;
7301 init_alias_vars ();
7303 if (dump_file && (dump_flags & TDF_DETAILS))
7305 symtab_node::dump_table (dump_file);
7306 fprintf (dump_file, "\n");
7309 /* Build the constraints. */
7310 FOR_EACH_DEFINED_FUNCTION (node)
7312 varinfo_t vi;
7313 /* Nodes without a body are not interesting. Especially do not
7314 visit clones at this point for now - we get duplicate decls
7315 there for inline clones at least. */
7316 if (!node->has_gimple_body_p () || node->global.inlined_to)
7317 continue;
7318 node->get_body ();
7320 gcc_assert (!node->clone_of);
7322 vi = create_function_info_for (node->decl,
7323 alias_get_name (node->decl));
7324 node->call_for_symbol_thunks_and_aliases
7325 (associate_varinfo_to_alias, vi, true);
7328 /* Create constraints for global variables and their initializers. */
7329 FOR_EACH_VARIABLE (var)
7331 if (var->alias && var->analyzed)
7332 continue;
7334 get_vi_for_tree (var->decl);
7337 if (dump_file)
7339 fprintf (dump_file,
7340 "Generating constraints for global initializers\n\n");
7341 dump_constraints (dump_file, 0);
7342 fprintf (dump_file, "\n");
7344 from = constraints.length ();
7346 FOR_EACH_DEFINED_FUNCTION (node)
7348 struct function *func;
7349 basic_block bb;
7351 /* Nodes without a body are not interesting. */
7352 if (!node->has_gimple_body_p () || node->clone_of)
7353 continue;
7355 if (dump_file)
7357 fprintf (dump_file,
7358 "Generating constraints for %s", node->name ());
7359 if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
7360 fprintf (dump_file, " (%s)",
7361 IDENTIFIER_POINTER
7362 (DECL_ASSEMBLER_NAME (node->decl)));
7363 fprintf (dump_file, "\n");
7366 func = DECL_STRUCT_FUNCTION (node->decl);
7367 gcc_assert (cfun == NULL);
7369 /* For externally visible or attribute used annotated functions use
7370 local constraints for their arguments.
7371 For local functions we see all callers and thus do not need initial
7372 constraints for parameters. */
7373 if (node->used_from_other_partition
7374 || node->externally_visible
7375 || node->force_output)
7377 intra_create_variable_infos (func);
7379 /* We also need to make function return values escape. Nothing
7380 escapes by returning from main though. */
7381 if (!MAIN_NAME_P (DECL_NAME (node->decl)))
7383 varinfo_t fi, rvi;
7384 fi = lookup_vi_for_tree (node->decl);
7385 rvi = first_vi_for_offset (fi, fi_result);
7386 if (rvi && rvi->offset == fi_result)
7388 struct constraint_expr includes;
7389 struct constraint_expr var;
7390 includes.var = escaped_id;
7391 includes.offset = 0;
7392 includes.type = SCALAR;
7393 var.var = rvi->id;
7394 var.offset = 0;
7395 var.type = SCALAR;
7396 process_constraint (new_constraint (includes, var));
7401 /* Build constriants for the function body. */
7402 FOR_EACH_BB_FN (bb, func)
7404 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
7405 gsi_next (&gsi))
7407 gphi *phi = gsi.phi ();
7409 if (! virtual_operand_p (gimple_phi_result (phi)))
7410 find_func_aliases (func, phi);
7413 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
7414 gsi_next (&gsi))
7416 gimple stmt = gsi_stmt (gsi);
7418 find_func_aliases (func, stmt);
7419 find_func_clobbers (func, stmt);
7423 if (dump_file)
7425 fprintf (dump_file, "\n");
7426 dump_constraints (dump_file, from);
7427 fprintf (dump_file, "\n");
7429 from = constraints.length ();
7432 /* From the constraints compute the points-to sets. */
7433 solve_constraints ();
7435 /* Compute the global points-to sets for ESCAPED.
7436 ??? Note that the computed escape set is not correct
7437 for the whole unit as we fail to consider graph edges to
7438 externally visible functions. */
7439 ipa_escaped_pt = find_what_var_points_to (get_varinfo (escaped_id));
7441 /* Make sure the ESCAPED solution (which is used as placeholder in
7442 other solutions) does not reference itself. This simplifies
7443 points-to solution queries. */
7444 ipa_escaped_pt.ipa_escaped = 0;
7446 /* Assign the points-to sets to the SSA names in the unit. */
7447 FOR_EACH_DEFINED_FUNCTION (node)
7449 tree ptr;
7450 struct function *fn;
7451 unsigned i;
7452 basic_block bb;
7454 /* Nodes without a body are not interesting. */
7455 if (!node->has_gimple_body_p () || node->clone_of)
7456 continue;
7458 fn = DECL_STRUCT_FUNCTION (node->decl);
7460 /* Compute the points-to sets for pointer SSA_NAMEs. */
7461 FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
7463 if (ptr
7464 && POINTER_TYPE_P (TREE_TYPE (ptr)))
7465 find_what_p_points_to (ptr);
7468 /* Compute the call-use and call-clobber sets for indirect calls
7469 and calls to external functions. */
7470 FOR_EACH_BB_FN (bb, fn)
7472 gimple_stmt_iterator gsi;
7474 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
7476 gcall *stmt;
7477 struct pt_solution *pt;
7478 varinfo_t vi, fi;
7479 tree decl;
7481 stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
7482 if (!stmt)
7483 continue;
7485 /* Handle direct calls to functions with body. */
7486 decl = gimple_call_fndecl (stmt);
7487 if (decl
7488 && (fi = lookup_vi_for_tree (decl))
7489 && fi->is_fn_info)
7491 *gimple_call_clobber_set (stmt)
7492 = find_what_var_points_to
7493 (first_vi_for_offset (fi, fi_clobbers));
7494 *gimple_call_use_set (stmt)
7495 = find_what_var_points_to
7496 (first_vi_for_offset (fi, fi_uses));
7498 /* Handle direct calls to external functions. */
7499 else if (decl)
7501 pt = gimple_call_use_set (stmt);
7502 if (gimple_call_flags (stmt) & ECF_CONST)
7503 memset (pt, 0, sizeof (struct pt_solution));
7504 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
7506 *pt = find_what_var_points_to (vi);
7507 /* Escaped (and thus nonlocal) variables are always
7508 implicitly used by calls. */
7509 /* ??? ESCAPED can be empty even though NONLOCAL
7510 always escaped. */
7511 pt->nonlocal = 1;
7512 pt->ipa_escaped = 1;
7514 else
7516 /* If there is nothing special about this call then
7517 we have made everything that is used also escape. */
7518 *pt = ipa_escaped_pt;
7519 pt->nonlocal = 1;
7522 pt = gimple_call_clobber_set (stmt);
7523 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
7524 memset (pt, 0, sizeof (struct pt_solution));
7525 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
7527 *pt = find_what_var_points_to (vi);
7528 /* Escaped (and thus nonlocal) variables are always
7529 implicitly clobbered by calls. */
7530 /* ??? ESCAPED can be empty even though NONLOCAL
7531 always escaped. */
7532 pt->nonlocal = 1;
7533 pt->ipa_escaped = 1;
7535 else
7537 /* If there is nothing special about this call then
7538 we have made everything that is used also escape. */
7539 *pt = ipa_escaped_pt;
7540 pt->nonlocal = 1;
7543 /* Handle indirect calls. */
7544 else if (!decl
7545 && (fi = get_fi_for_callee (stmt)))
7547 /* We need to accumulate all clobbers/uses of all possible
7548 callees. */
7549 fi = get_varinfo (find (fi->id));
7550 /* If we cannot constrain the set of functions we'll end up
7551 calling we end up using/clobbering everything. */
7552 if (bitmap_bit_p (fi->solution, anything_id)
7553 || bitmap_bit_p (fi->solution, nonlocal_id)
7554 || bitmap_bit_p (fi->solution, escaped_id))
7556 pt_solution_reset (gimple_call_clobber_set (stmt));
7557 pt_solution_reset (gimple_call_use_set (stmt));
7559 else
7561 bitmap_iterator bi;
7562 unsigned i;
7563 struct pt_solution *uses, *clobbers;
7565 uses = gimple_call_use_set (stmt);
7566 clobbers = gimple_call_clobber_set (stmt);
7567 memset (uses, 0, sizeof (struct pt_solution));
7568 memset (clobbers, 0, sizeof (struct pt_solution));
7569 EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
7571 struct pt_solution sol;
7573 vi = get_varinfo (i);
7574 if (!vi->is_fn_info)
7576 /* ??? We could be more precise here? */
7577 uses->nonlocal = 1;
7578 uses->ipa_escaped = 1;
7579 clobbers->nonlocal = 1;
7580 clobbers->ipa_escaped = 1;
7581 continue;
7584 if (!uses->anything)
7586 sol = find_what_var_points_to
7587 (first_vi_for_offset (vi, fi_uses));
7588 pt_solution_ior_into (uses, &sol);
7590 if (!clobbers->anything)
7592 sol = find_what_var_points_to
7593 (first_vi_for_offset (vi, fi_clobbers));
7594 pt_solution_ior_into (clobbers, &sol);
7602 fn->gimple_df->ipa_pta = true;
7605 delete_points_to_sets ();
7607 in_ipa_mode = 0;
7609 return 0;
7612 namespace {
7614 const pass_data pass_data_ipa_pta =
7616 SIMPLE_IPA_PASS, /* type */
7617 "pta", /* name */
7618 OPTGROUP_NONE, /* optinfo_flags */
7619 TV_IPA_PTA, /* tv_id */
7620 0, /* properties_required */
7621 0, /* properties_provided */
7622 0, /* properties_destroyed */
7623 0, /* todo_flags_start */
7624 0, /* todo_flags_finish */
7627 class pass_ipa_pta : public simple_ipa_opt_pass
7629 public:
7630 pass_ipa_pta (gcc::context *ctxt)
7631 : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
7634 /* opt_pass methods: */
7635 virtual bool gate (function *)
7637 return (optimize
7638 && flag_ipa_pta
7639 /* Don't bother doing anything if the program has errors. */
7640 && !seen_error ());
7643 virtual unsigned int execute (function *) { return ipa_pta_execute (); }
7645 }; // class pass_ipa_pta
7647 } // anon namespace
7649 simple_ipa_opt_pass *
7650 make_pass_ipa_pta (gcc::context *ctxt)
7652 return new pass_ipa_pta (ctxt);