gccrs: Add get_locus function for abstract class MetaItemInner.
[official-gcc.git] / gcc / tree-ssa-alias.cc
blob81bc51ed4ad8e4c2018a98b00c75efafb90c2fa8
1 /* Alias analysis for trees.
2 Copyright (C) 2004-2023 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "target.h"
26 #include "rtl.h"
27 #include "tree.h"
28 #include "gimple.h"
29 #include "timevar.h" /* for TV_ALIAS_STMT_WALK */
30 #include "ssa.h"
31 #include "cgraph.h"
32 #include "tree-pretty-print.h"
33 #include "alias.h"
34 #include "fold-const.h"
35 #include "langhooks.h"
36 #include "dumpfile.h"
37 #include "tree-eh.h"
38 #include "tree-dfa.h"
39 #include "ipa-reference.h"
40 #include "varasm.h"
41 #include "ipa-modref-tree.h"
42 #include "ipa-modref.h"
43 #include "attr-fnspec.h"
44 #include "errors.h"
45 #include "dbgcnt.h"
46 #include "gimple-pretty-print.h"
47 #include "print-tree.h"
48 #include "tree-ssa-alias-compare.h"
49 #include "builtins.h"
50 #include "internal-fn.h"
52 /* Broad overview of how alias analysis on gimple works:
54 Statements clobbering or using memory are linked through the
55 virtual operand factored use-def chain. The virtual operand
56 is unique per function, its symbol is accessible via gimple_vop (cfun).
57 Virtual operands are used for efficiently walking memory statements
58 in the gimple IL and are useful for things like value-numbering as
59 a generation count for memory references.
61 SSA_NAME pointers may have associated points-to information
62 accessible via the SSA_NAME_PTR_INFO macro. Flow-insensitive
63 points-to information is (re-)computed by the TODO_rebuild_alias
64 pass manager todo. Points-to information is also used for more
65 precise tracking of call-clobbered and call-used variables and
66 related disambiguations.
68 This file contains functions for disambiguating memory references,
69 the so called alias-oracle and tools for walking of the gimple IL.
71 The main alias-oracle entry-points are
73 bool stmt_may_clobber_ref_p (gimple *, tree)
75 This function queries if a statement may invalidate (parts of)
76 the memory designated by the reference tree argument.
78 bool ref_maybe_used_by_stmt_p (gimple *, tree)
80 This function queries if a statement may need (parts of) the
81 memory designated by the reference tree argument.
83 There are variants of these functions that only handle the call
84 part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
85 Note that these do not disambiguate against a possible call lhs.
87 bool refs_may_alias_p (tree, tree)
89 This function tries to disambiguate two reference trees.
91 bool ptr_deref_may_alias_global_p (tree, bool)
93 This function queries if dereferencing a pointer variable may
94 alias global memory. If bool argument is true, global memory
95 is considered to also include function local memory that escaped.
97 More low-level disambiguators are available and documented in
98 this file. Low-level disambiguators dealing with points-to
99 information are in tree-ssa-structalias.cc. */
101 static int nonoverlapping_refs_since_match_p (tree, tree, tree, tree, bool);
102 static bool nonoverlapping_component_refs_p (const_tree, const_tree);
104 /* Query statistics for the different low-level disambiguators.
105 A high-level query may trigger multiple of them. */
107 static struct {
108 unsigned HOST_WIDE_INT refs_may_alias_p_may_alias;
109 unsigned HOST_WIDE_INT refs_may_alias_p_no_alias;
110 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias;
111 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias;
112 unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias;
113 unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias;
114 unsigned HOST_WIDE_INT aliasing_component_refs_p_may_alias;
115 unsigned HOST_WIDE_INT aliasing_component_refs_p_no_alias;
116 unsigned HOST_WIDE_INT nonoverlapping_component_refs_p_may_alias;
117 unsigned HOST_WIDE_INT nonoverlapping_component_refs_p_no_alias;
118 unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_may_alias;
119 unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_must_overlap;
120 unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_no_alias;
121 unsigned HOST_WIDE_INT stmt_kills_ref_p_no;
122 unsigned HOST_WIDE_INT stmt_kills_ref_p_yes;
123 unsigned HOST_WIDE_INT modref_use_may_alias;
124 unsigned HOST_WIDE_INT modref_use_no_alias;
125 unsigned HOST_WIDE_INT modref_clobber_may_alias;
126 unsigned HOST_WIDE_INT modref_clobber_no_alias;
127 unsigned HOST_WIDE_INT modref_kill_no;
128 unsigned HOST_WIDE_INT modref_kill_yes;
129 unsigned HOST_WIDE_INT modref_tests;
130 unsigned HOST_WIDE_INT modref_baseptr_tests;
131 } alias_stats;
133 void
134 dump_alias_stats (FILE *s)
136 fprintf (s, "\nAlias oracle query stats:\n");
137 fprintf (s, " refs_may_alias_p: "
138 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
139 HOST_WIDE_INT_PRINT_DEC" queries\n",
140 alias_stats.refs_may_alias_p_no_alias,
141 alias_stats.refs_may_alias_p_no_alias
142 + alias_stats.refs_may_alias_p_may_alias);
143 fprintf (s, " ref_maybe_used_by_call_p: "
144 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
145 HOST_WIDE_INT_PRINT_DEC" queries\n",
146 alias_stats.ref_maybe_used_by_call_p_no_alias,
147 alias_stats.refs_may_alias_p_no_alias
148 + alias_stats.ref_maybe_used_by_call_p_may_alias);
149 fprintf (s, " call_may_clobber_ref_p: "
150 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
151 HOST_WIDE_INT_PRINT_DEC" queries\n",
152 alias_stats.call_may_clobber_ref_p_no_alias,
153 alias_stats.call_may_clobber_ref_p_no_alias
154 + alias_stats.call_may_clobber_ref_p_may_alias);
155 fprintf (s, " stmt_kills_ref_p: "
156 HOST_WIDE_INT_PRINT_DEC" kills, "
157 HOST_WIDE_INT_PRINT_DEC" queries\n",
158 alias_stats.stmt_kills_ref_p_yes + alias_stats.modref_kill_yes,
159 alias_stats.stmt_kills_ref_p_yes + alias_stats.modref_kill_yes
160 + alias_stats.stmt_kills_ref_p_no + alias_stats.modref_kill_no);
161 fprintf (s, " nonoverlapping_component_refs_p: "
162 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
163 HOST_WIDE_INT_PRINT_DEC" queries\n",
164 alias_stats.nonoverlapping_component_refs_p_no_alias,
165 alias_stats.nonoverlapping_component_refs_p_no_alias
166 + alias_stats.nonoverlapping_component_refs_p_may_alias);
167 fprintf (s, " nonoverlapping_refs_since_match_p: "
168 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
169 HOST_WIDE_INT_PRINT_DEC" must overlaps, "
170 HOST_WIDE_INT_PRINT_DEC" queries\n",
171 alias_stats.nonoverlapping_refs_since_match_p_no_alias,
172 alias_stats.nonoverlapping_refs_since_match_p_must_overlap,
173 alias_stats.nonoverlapping_refs_since_match_p_no_alias
174 + alias_stats.nonoverlapping_refs_since_match_p_may_alias
175 + alias_stats.nonoverlapping_refs_since_match_p_must_overlap);
176 fprintf (s, " aliasing_component_refs_p: "
177 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
178 HOST_WIDE_INT_PRINT_DEC" queries\n",
179 alias_stats.aliasing_component_refs_p_no_alias,
180 alias_stats.aliasing_component_refs_p_no_alias
181 + alias_stats.aliasing_component_refs_p_may_alias);
182 dump_alias_stats_in_alias_c (s);
183 fprintf (s, "\nModref stats:\n");
184 fprintf (s, " modref kill: "
185 HOST_WIDE_INT_PRINT_DEC" kills, "
186 HOST_WIDE_INT_PRINT_DEC" queries\n",
187 alias_stats.modref_kill_yes,
188 alias_stats.modref_kill_yes
189 + alias_stats.modref_kill_no);
190 fprintf (s, " modref use: "
191 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
192 HOST_WIDE_INT_PRINT_DEC" queries\n",
193 alias_stats.modref_use_no_alias,
194 alias_stats.modref_use_no_alias
195 + alias_stats.modref_use_may_alias);
196 fprintf (s, " modref clobber: "
197 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
198 HOST_WIDE_INT_PRINT_DEC" queries\n"
199 " " HOST_WIDE_INT_PRINT_DEC" tbaa queries (%f per modref query)\n"
200 " " HOST_WIDE_INT_PRINT_DEC" base compares (%f per modref query)\n",
201 alias_stats.modref_clobber_no_alias,
202 alias_stats.modref_clobber_no_alias
203 + alias_stats.modref_clobber_may_alias,
204 alias_stats.modref_tests,
205 ((double)alias_stats.modref_tests)
206 / (alias_stats.modref_clobber_no_alias
207 + alias_stats.modref_clobber_may_alias),
208 alias_stats.modref_baseptr_tests,
209 ((double)alias_stats.modref_baseptr_tests)
210 / (alias_stats.modref_clobber_no_alias
211 + alias_stats.modref_clobber_may_alias));
215 /* Return true, if dereferencing PTR may alias with a global variable.
216 When ESCAPED_LOCAL_P is true escaped local memory is also considered
217 global. */
219 bool
220 ptr_deref_may_alias_global_p (tree ptr, bool escaped_local_p)
222 struct ptr_info_def *pi;
224 /* If we end up with a pointer constant here that may point
225 to global memory. */
226 if (TREE_CODE (ptr) != SSA_NAME)
227 return true;
229 pi = SSA_NAME_PTR_INFO (ptr);
231 /* If we do not have points-to information for this variable,
232 we have to punt. */
233 if (!pi)
234 return true;
236 /* ??? This does not use TBAA to prune globals ptr may not access. */
237 return pt_solution_includes_global (&pi->pt, escaped_local_p);
240 /* Return true if dereferencing PTR may alias DECL.
241 The caller is responsible for applying TBAA to see if PTR
242 may access DECL at all. */
244 static bool
245 ptr_deref_may_alias_decl_p (tree ptr, tree decl)
247 struct ptr_info_def *pi;
249 /* Conversions are irrelevant for points-to information and
250 data-dependence analysis can feed us those. */
251 STRIP_NOPS (ptr);
253 /* Anything we do not explicilty handle aliases. */
254 if ((TREE_CODE (ptr) != SSA_NAME
255 && TREE_CODE (ptr) != ADDR_EXPR
256 && TREE_CODE (ptr) != POINTER_PLUS_EXPR)
257 || !POINTER_TYPE_P (TREE_TYPE (ptr))
258 || (!VAR_P (decl)
259 && TREE_CODE (decl) != PARM_DECL
260 && TREE_CODE (decl) != RESULT_DECL))
261 return true;
263 /* Disregard pointer offsetting. */
264 if (TREE_CODE (ptr) == POINTER_PLUS_EXPR)
268 ptr = TREE_OPERAND (ptr, 0);
270 while (TREE_CODE (ptr) == POINTER_PLUS_EXPR);
271 return ptr_deref_may_alias_decl_p (ptr, decl);
274 /* ADDR_EXPR pointers either just offset another pointer or directly
275 specify the pointed-to set. */
276 if (TREE_CODE (ptr) == ADDR_EXPR)
278 tree base = get_base_address (TREE_OPERAND (ptr, 0));
279 if (base
280 && (TREE_CODE (base) == MEM_REF
281 || TREE_CODE (base) == TARGET_MEM_REF))
282 ptr = TREE_OPERAND (base, 0);
283 else if (base
284 && DECL_P (base))
285 return compare_base_decls (base, decl) != 0;
286 else if (base
287 && CONSTANT_CLASS_P (base))
288 return false;
289 else
290 return true;
293 /* Non-aliased variables cannot be pointed to. */
294 if (!may_be_aliased (decl))
295 return false;
297 /* If we do not have useful points-to information for this pointer
298 we cannot disambiguate anything else. */
299 pi = SSA_NAME_PTR_INFO (ptr);
300 if (!pi)
301 return true;
303 return pt_solution_includes (&pi->pt, decl);
306 /* Return true if dereferenced PTR1 and PTR2 may alias.
307 The caller is responsible for applying TBAA to see if accesses
308 through PTR1 and PTR2 may conflict at all. */
310 bool
311 ptr_derefs_may_alias_p (tree ptr1, tree ptr2)
313 struct ptr_info_def *pi1, *pi2;
315 /* Conversions are irrelevant for points-to information and
316 data-dependence analysis can feed us those. */
317 STRIP_NOPS (ptr1);
318 STRIP_NOPS (ptr2);
320 /* Disregard pointer offsetting. */
321 if (TREE_CODE (ptr1) == POINTER_PLUS_EXPR)
325 ptr1 = TREE_OPERAND (ptr1, 0);
327 while (TREE_CODE (ptr1) == POINTER_PLUS_EXPR);
328 return ptr_derefs_may_alias_p (ptr1, ptr2);
330 if (TREE_CODE (ptr2) == POINTER_PLUS_EXPR)
334 ptr2 = TREE_OPERAND (ptr2, 0);
336 while (TREE_CODE (ptr2) == POINTER_PLUS_EXPR);
337 return ptr_derefs_may_alias_p (ptr1, ptr2);
340 /* ADDR_EXPR pointers either just offset another pointer or directly
341 specify the pointed-to set. */
342 if (TREE_CODE (ptr1) == ADDR_EXPR)
344 tree base = get_base_address (TREE_OPERAND (ptr1, 0));
345 if (base
346 && (TREE_CODE (base) == MEM_REF
347 || TREE_CODE (base) == TARGET_MEM_REF))
348 return ptr_derefs_may_alias_p (TREE_OPERAND (base, 0), ptr2);
349 else if (base
350 && DECL_P (base))
351 return ptr_deref_may_alias_decl_p (ptr2, base);
352 /* Try ptr2 when ptr1 points to a constant. */
353 else if (base
354 && !CONSTANT_CLASS_P (base))
355 return true;
357 if (TREE_CODE (ptr2) == ADDR_EXPR)
359 tree base = get_base_address (TREE_OPERAND (ptr2, 0));
360 if (base
361 && (TREE_CODE (base) == MEM_REF
362 || TREE_CODE (base) == TARGET_MEM_REF))
363 return ptr_derefs_may_alias_p (ptr1, TREE_OPERAND (base, 0));
364 else if (base
365 && DECL_P (base))
366 return ptr_deref_may_alias_decl_p (ptr1, base);
367 else
368 return true;
371 /* From here we require SSA name pointers. Anything else aliases. */
372 if (TREE_CODE (ptr1) != SSA_NAME
373 || TREE_CODE (ptr2) != SSA_NAME
374 || !POINTER_TYPE_P (TREE_TYPE (ptr1))
375 || !POINTER_TYPE_P (TREE_TYPE (ptr2)))
376 return true;
378 /* We may end up with two empty points-to solutions for two same pointers.
379 In this case we still want to say both pointers alias, so shortcut
380 that here. */
381 if (ptr1 == ptr2)
382 return true;
384 /* If we do not have useful points-to information for either pointer
385 we cannot disambiguate anything else. */
386 pi1 = SSA_NAME_PTR_INFO (ptr1);
387 pi2 = SSA_NAME_PTR_INFO (ptr2);
388 if (!pi1 || !pi2)
389 return true;
391 /* ??? This does not use TBAA to prune decls from the intersection
392 that not both pointers may access. */
393 return pt_solutions_intersect (&pi1->pt, &pi2->pt);
396 /* Return true if dereferencing PTR may alias *REF.
397 The caller is responsible for applying TBAA to see if PTR
398 may access *REF at all. */
400 static bool
401 ptr_deref_may_alias_ref_p_1 (tree ptr, ao_ref *ref)
403 tree base = ao_ref_base (ref);
405 if (TREE_CODE (base) == MEM_REF
406 || TREE_CODE (base) == TARGET_MEM_REF)
407 return ptr_derefs_may_alias_p (ptr, TREE_OPERAND (base, 0));
408 else if (DECL_P (base))
409 return ptr_deref_may_alias_decl_p (ptr, base);
411 return true;
414 /* Returns true if PTR1 and PTR2 compare unequal because of points-to. */
416 bool
417 ptrs_compare_unequal (tree ptr1, tree ptr2)
419 /* First resolve the pointers down to a SSA name pointer base or
420 a VAR_DECL, PARM_DECL or RESULT_DECL. This explicitely does
421 not yet try to handle LABEL_DECLs, FUNCTION_DECLs, CONST_DECLs
422 or STRING_CSTs which needs points-to adjustments to track them
423 in the points-to sets. */
424 tree obj1 = NULL_TREE;
425 tree obj2 = NULL_TREE;
426 if (TREE_CODE (ptr1) == ADDR_EXPR)
428 tree tem = get_base_address (TREE_OPERAND (ptr1, 0));
429 if (! tem)
430 return false;
431 if (VAR_P (tem)
432 || TREE_CODE (tem) == PARM_DECL
433 || TREE_CODE (tem) == RESULT_DECL)
434 obj1 = tem;
435 else if (TREE_CODE (tem) == MEM_REF)
436 ptr1 = TREE_OPERAND (tem, 0);
438 if (TREE_CODE (ptr2) == ADDR_EXPR)
440 tree tem = get_base_address (TREE_OPERAND (ptr2, 0));
441 if (! tem)
442 return false;
443 if (VAR_P (tem)
444 || TREE_CODE (tem) == PARM_DECL
445 || TREE_CODE (tem) == RESULT_DECL)
446 obj2 = tem;
447 else if (TREE_CODE (tem) == MEM_REF)
448 ptr2 = TREE_OPERAND (tem, 0);
451 /* Canonicalize ptr vs. object. */
452 if (TREE_CODE (ptr1) == SSA_NAME && obj2)
454 std::swap (ptr1, ptr2);
455 std::swap (obj1, obj2);
458 if (obj1 && obj2)
459 /* Other code handles this correctly, no need to duplicate it here. */;
460 else if (obj1 && TREE_CODE (ptr2) == SSA_NAME)
462 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr2);
463 /* We may not use restrict to optimize pointer comparisons.
464 See PR71062. So we have to assume that restrict-pointed-to
465 may be in fact obj1. */
466 if (!pi
467 || pi->pt.vars_contains_restrict
468 || pi->pt.vars_contains_interposable)
469 return false;
470 if (VAR_P (obj1)
471 && (TREE_STATIC (obj1) || DECL_EXTERNAL (obj1)))
473 varpool_node *node = varpool_node::get (obj1);
474 /* If obj1 may bind to NULL give up (see below). */
475 if (! node
476 || ! node->nonzero_address ()
477 || ! decl_binds_to_current_def_p (obj1))
478 return false;
480 return !pt_solution_includes (&pi->pt, obj1);
483 /* ??? We'd like to handle ptr1 != NULL and ptr1 != ptr2
484 but those require pt.null to be conservatively correct. */
486 return false;
489 /* Returns whether reference REF to BASE may refer to global memory.
490 When ESCAPED_LOCAL_P is true escaped local memory is also considered
491 global. */
493 static bool
494 ref_may_alias_global_p_1 (tree base, bool escaped_local_p)
496 if (DECL_P (base))
497 return (is_global_var (base)
498 || (escaped_local_p
499 && pt_solution_includes (&cfun->gimple_df->escaped, base)));
500 else if (TREE_CODE (base) == MEM_REF
501 || TREE_CODE (base) == TARGET_MEM_REF)
502 return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0),
503 escaped_local_p);
504 return true;
507 bool
508 ref_may_alias_global_p (ao_ref *ref, bool escaped_local_p)
510 tree base = ao_ref_base (ref);
511 return ref_may_alias_global_p_1 (base, escaped_local_p);
514 bool
515 ref_may_alias_global_p (tree ref, bool escaped_local_p)
517 tree base = get_base_address (ref);
518 return ref_may_alias_global_p_1 (base, escaped_local_p);
521 /* Return true whether STMT may clobber global memory.
522 When ESCAPED_LOCAL_P is true escaped local memory is also considered
523 global. */
525 bool
526 stmt_may_clobber_global_p (gimple *stmt, bool escaped_local_p)
528 tree lhs;
530 if (!gimple_vdef (stmt))
531 return false;
533 /* ??? We can ask the oracle whether an artificial pointer
534 dereference with a pointer with points-to information covering
535 all global memory (what about non-address taken memory?) maybe
536 clobbered by this call. As there is at the moment no convenient
537 way of doing that without generating garbage do some manual
538 checking instead.
539 ??? We could make a NULL ao_ref argument to the various
540 predicates special, meaning any global memory. */
542 switch (gimple_code (stmt))
544 case GIMPLE_ASSIGN:
545 lhs = gimple_assign_lhs (stmt);
546 return (TREE_CODE (lhs) != SSA_NAME
547 && ref_may_alias_global_p (lhs, escaped_local_p));
548 case GIMPLE_CALL:
549 return true;
550 default:
551 return true;
556 /* Dump alias information on FILE. */
558 void
559 dump_alias_info (FILE *file)
561 unsigned i;
562 tree ptr;
563 const char *funcname
564 = lang_hooks.decl_printable_name (current_function_decl, 2);
565 tree var;
567 fprintf (file, "\n\nAlias information for %s\n\n", funcname);
569 fprintf (file, "Aliased symbols\n\n");
571 FOR_EACH_LOCAL_DECL (cfun, i, var)
573 if (may_be_aliased (var))
574 dump_variable (file, var);
577 fprintf (file, "\nCall clobber information\n");
579 fprintf (file, "\nESCAPED");
580 dump_points_to_solution (file, &cfun->gimple_df->escaped);
582 fprintf (file, "\n\nFlow-insensitive points-to information\n\n");
584 FOR_EACH_SSA_NAME (i, ptr, cfun)
586 struct ptr_info_def *pi;
588 if (!POINTER_TYPE_P (TREE_TYPE (ptr))
589 || SSA_NAME_IN_FREE_LIST (ptr))
590 continue;
592 pi = SSA_NAME_PTR_INFO (ptr);
593 if (pi)
594 dump_points_to_info_for (file, ptr);
597 fprintf (file, "\n");
601 /* Dump alias information on stderr. */
603 DEBUG_FUNCTION void
604 debug_alias_info (void)
606 dump_alias_info (stderr);
610 /* Dump the points-to set *PT into FILE. */
612 void
613 dump_points_to_solution (FILE *file, struct pt_solution *pt)
615 if (pt->anything)
616 fprintf (file, ", points-to anything");
618 if (pt->nonlocal)
619 fprintf (file, ", points-to non-local");
621 if (pt->escaped)
622 fprintf (file, ", points-to escaped");
624 if (pt->ipa_escaped)
625 fprintf (file, ", points-to unit escaped");
627 if (pt->null)
628 fprintf (file, ", points-to NULL");
630 if (pt->vars)
632 fprintf (file, ", points-to vars: ");
633 dump_decl_set (file, pt->vars);
634 if (pt->vars_contains_nonlocal
635 || pt->vars_contains_escaped
636 || pt->vars_contains_escaped_heap
637 || pt->vars_contains_restrict)
639 const char *comma = "";
640 fprintf (file, " (");
641 if (pt->vars_contains_nonlocal)
643 fprintf (file, "nonlocal");
644 comma = ", ";
646 if (pt->vars_contains_escaped)
648 fprintf (file, "%sescaped", comma);
649 comma = ", ";
651 if (pt->vars_contains_escaped_heap)
653 fprintf (file, "%sescaped heap", comma);
654 comma = ", ";
656 if (pt->vars_contains_restrict)
658 fprintf (file, "%srestrict", comma);
659 comma = ", ";
661 if (pt->vars_contains_interposable)
662 fprintf (file, "%sinterposable", comma);
663 fprintf (file, ")");
669 /* Unified dump function for pt_solution. */
671 DEBUG_FUNCTION void
672 debug (pt_solution &ref)
674 dump_points_to_solution (stderr, &ref);
677 DEBUG_FUNCTION void
678 debug (pt_solution *ptr)
680 if (ptr)
681 debug (*ptr);
682 else
683 fprintf (stderr, "<nil>\n");
687 /* Dump points-to information for SSA_NAME PTR into FILE. */
689 void
690 dump_points_to_info_for (FILE *file, tree ptr)
692 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
694 print_generic_expr (file, ptr, dump_flags);
696 if (pi)
697 dump_points_to_solution (file, &pi->pt);
698 else
699 fprintf (file, ", points-to anything");
701 fprintf (file, "\n");
705 /* Dump points-to information for VAR into stderr. */
707 DEBUG_FUNCTION void
708 debug_points_to_info_for (tree var)
710 dump_points_to_info_for (stderr, var);
714 /* Initializes the alias-oracle reference representation *R from REF. */
716 void
717 ao_ref_init (ao_ref *r, tree ref)
719 r->ref = ref;
720 r->base = NULL_TREE;
721 r->offset = 0;
722 r->size = -1;
723 r->max_size = -1;
724 r->ref_alias_set = -1;
725 r->base_alias_set = -1;
726 r->volatile_p = ref ? TREE_THIS_VOLATILE (ref) : false;
729 /* Returns the base object of the memory reference *REF. */
731 tree
732 ao_ref_base (ao_ref *ref)
734 bool reverse;
736 if (ref->base)
737 return ref->base;
738 ref->base = get_ref_base_and_extent (ref->ref, &ref->offset, &ref->size,
739 &ref->max_size, &reverse);
740 return ref->base;
743 /* Returns the base object alias set of the memory reference *REF. */
745 alias_set_type
746 ao_ref_base_alias_set (ao_ref *ref)
748 tree base_ref;
749 if (ref->base_alias_set != -1)
750 return ref->base_alias_set;
751 if (!ref->ref)
752 return 0;
753 base_ref = ref->ref;
754 if (TREE_CODE (base_ref) == WITH_SIZE_EXPR)
755 base_ref = TREE_OPERAND (base_ref, 0);
756 while (handled_component_p (base_ref))
757 base_ref = TREE_OPERAND (base_ref, 0);
758 ref->base_alias_set = get_alias_set (base_ref);
759 return ref->base_alias_set;
762 /* Returns the reference alias set of the memory reference *REF. */
764 alias_set_type
765 ao_ref_alias_set (ao_ref *ref)
767 if (ref->ref_alias_set != -1)
768 return ref->ref_alias_set;
769 if (!ref->ref)
770 return 0;
771 ref->ref_alias_set = get_alias_set (ref->ref);
772 return ref->ref_alias_set;
775 /* Returns a type satisfying
776 get_deref_alias_set (type) == ao_ref_base_alias_set (REF). */
778 tree
779 ao_ref_base_alias_ptr_type (ao_ref *ref)
781 tree base_ref;
783 if (!ref->ref)
784 return NULL_TREE;
785 base_ref = ref->ref;
786 if (TREE_CODE (base_ref) == WITH_SIZE_EXPR)
787 base_ref = TREE_OPERAND (base_ref, 0);
788 while (handled_component_p (base_ref))
789 base_ref = TREE_OPERAND (base_ref, 0);
790 tree ret = reference_alias_ptr_type (base_ref);
791 return ret;
794 /* Returns a type satisfying
795 get_deref_alias_set (type) == ao_ref_alias_set (REF). */
797 tree
798 ao_ref_alias_ptr_type (ao_ref *ref)
800 if (!ref->ref)
801 return NULL_TREE;
802 tree ret = reference_alias_ptr_type (ref->ref);
803 return ret;
806 /* Return the alignment of the access *REF and store it in the *ALIGN
807 and *BITPOS pairs. Returns false if no alignment could be determined.
808 See get_object_alignment_2 for details. */
810 bool
811 ao_ref_alignment (ao_ref *ref, unsigned int *align,
812 unsigned HOST_WIDE_INT *bitpos)
814 if (ref->ref)
815 return get_object_alignment_1 (ref->ref, align, bitpos);
817 /* When we just have ref->base we cannot use get_object_alignment since
818 that will eventually use the type of the appearant access while for
819 example ao_ref_init_from_ptr_and_range is not careful to adjust that. */
820 *align = BITS_PER_UNIT;
821 HOST_WIDE_INT offset;
822 if (!ref->offset.is_constant (&offset)
823 || !get_object_alignment_2 (ref->base, align, bitpos, true))
824 return false;
825 *bitpos += (unsigned HOST_WIDE_INT)offset * BITS_PER_UNIT;
826 *bitpos = *bitpos & (*align - 1);
827 return true;
830 /* Init an alias-oracle reference representation from a gimple pointer
831 PTR a range specified by OFFSET, SIZE and MAX_SIZE under the assumption
832 that RANGE_KNOWN is set.
834 The access is assumed to be only to or after of the pointer target adjusted
835 by the offset, not before it (even in the case RANGE_KNOWN is false). */
837 void
838 ao_ref_init_from_ptr_and_range (ao_ref *ref, tree ptr,
839 bool range_known,
840 poly_int64 offset,
841 poly_int64 size,
842 poly_int64 max_size)
844 poly_int64 t, extra_offset = 0;
846 ref->ref = NULL_TREE;
847 if (TREE_CODE (ptr) == SSA_NAME)
849 gimple *stmt = SSA_NAME_DEF_STMT (ptr);
850 if (gimple_assign_single_p (stmt)
851 && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
852 ptr = gimple_assign_rhs1 (stmt);
853 else if (is_gimple_assign (stmt)
854 && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
855 && ptrdiff_tree_p (gimple_assign_rhs2 (stmt), &extra_offset))
857 ptr = gimple_assign_rhs1 (stmt);
858 extra_offset *= BITS_PER_UNIT;
862 if (TREE_CODE (ptr) == ADDR_EXPR)
864 ref->base = get_addr_base_and_unit_offset (TREE_OPERAND (ptr, 0), &t);
865 if (ref->base)
866 ref->offset = BITS_PER_UNIT * t;
867 else
869 range_known = false;
870 ref->offset = 0;
871 ref->base = get_base_address (TREE_OPERAND (ptr, 0));
874 else
876 gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
877 ref->base = build2 (MEM_REF, char_type_node,
878 ptr, null_pointer_node);
879 ref->offset = 0;
881 ref->offset += extra_offset + offset;
882 if (range_known)
884 ref->max_size = max_size;
885 ref->size = size;
887 else
888 ref->max_size = ref->size = -1;
889 ref->ref_alias_set = 0;
890 ref->base_alias_set = 0;
891 ref->volatile_p = false;
894 /* Init an alias-oracle reference representation from a gimple pointer
895 PTR and a gimple size SIZE in bytes. If SIZE is NULL_TREE then the
896 size is assumed to be unknown. The access is assumed to be only
897 to or after of the pointer target, not before it. */
899 void
900 ao_ref_init_from_ptr_and_size (ao_ref *ref, tree ptr, tree size)
902 poly_int64 size_hwi;
903 if (size
904 && poly_int_tree_p (size, &size_hwi)
905 && coeffs_in_range_p (size_hwi, 0, HOST_WIDE_INT_MAX / BITS_PER_UNIT))
907 size_hwi = size_hwi * BITS_PER_UNIT;
908 ao_ref_init_from_ptr_and_range (ref, ptr, true, 0, size_hwi, size_hwi);
910 else
911 ao_ref_init_from_ptr_and_range (ref, ptr, false, 0, -1, -1);
914 /* S1 and S2 are TYPE_SIZE or DECL_SIZE. Compare them:
915 Return -1 if S1 < S2
916 Return 1 if S1 > S2
917 Return 0 if equal or incomparable. */
919 static int
920 compare_sizes (tree s1, tree s2)
922 if (!s1 || !s2)
923 return 0;
925 poly_uint64 size1;
926 poly_uint64 size2;
928 if (!poly_int_tree_p (s1, &size1) || !poly_int_tree_p (s2, &size2))
929 return 0;
930 if (known_lt (size1, size2))
931 return -1;
932 if (known_lt (size2, size1))
933 return 1;
934 return 0;
937 /* Compare TYPE1 and TYPE2 by its size.
938 Return -1 if size of TYPE1 < size of TYPE2
939 Return 1 if size of TYPE1 > size of TYPE2
940 Return 0 if types are of equal sizes or we can not compare them. */
942 static int
943 compare_type_sizes (tree type1, tree type2)
945 /* Be conservative for arrays and vectors. We want to support partial
946 overlap on int[3] and int[3] as tested in gcc.dg/torture/alias-2.c. */
947 while (TREE_CODE (type1) == ARRAY_TYPE
948 || TREE_CODE (type1) == VECTOR_TYPE)
949 type1 = TREE_TYPE (type1);
950 while (TREE_CODE (type2) == ARRAY_TYPE
951 || TREE_CODE (type2) == VECTOR_TYPE)
952 type2 = TREE_TYPE (type2);
953 return compare_sizes (TYPE_SIZE (type1), TYPE_SIZE (type2));
956 /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
957 purpose of TBAA. Return 0 if they are distinct and -1 if we cannot
958 decide. */
960 static inline int
961 same_type_for_tbaa (tree type1, tree type2)
963 type1 = TYPE_MAIN_VARIANT (type1);
964 type2 = TYPE_MAIN_VARIANT (type2);
966 /* Handle the most common case first. */
967 if (type1 == type2)
968 return 1;
970 /* If we would have to do structural comparison bail out. */
971 if (TYPE_STRUCTURAL_EQUALITY_P (type1)
972 || TYPE_STRUCTURAL_EQUALITY_P (type2))
973 return -1;
975 /* Compare the canonical types. */
976 if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
977 return 1;
979 /* ??? Array types are not properly unified in all cases as we have
980 spurious changes in the index types for example. Removing this
981 causes all sorts of problems with the Fortran frontend. */
982 if (TREE_CODE (type1) == ARRAY_TYPE
983 && TREE_CODE (type2) == ARRAY_TYPE)
984 return -1;
986 /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
987 object of one of its constrained subtypes, e.g. when a function with an
988 unconstrained parameter passed by reference is called on an object and
989 inlined. But, even in the case of a fixed size, type and subtypes are
990 not equivalent enough as to share the same TYPE_CANONICAL, since this
991 would mean that conversions between them are useless, whereas they are
992 not (e.g. type and subtypes can have different modes). So, in the end,
993 they are only guaranteed to have the same alias set. */
994 alias_set_type set1 = get_alias_set (type1);
995 alias_set_type set2 = get_alias_set (type2);
996 if (set1 == set2)
997 return -1;
999 /* Pointers to void are considered compatible with all other pointers,
1000 so for two pointers see what the alias set resolution thinks. */
1001 if (POINTER_TYPE_P (type1)
1002 && POINTER_TYPE_P (type2)
1003 && alias_sets_conflict_p (set1, set2))
1004 return -1;
1006 /* The types are known to be not equal. */
1007 return 0;
1010 /* Return true if TYPE is a composite type (i.e. we may apply one of handled
1011 components on it). */
1013 static bool
1014 type_has_components_p (tree type)
1016 return AGGREGATE_TYPE_P (type) || VECTOR_TYPE_P (type)
1017 || TREE_CODE (type) == COMPLEX_TYPE;
1020 /* MATCH1 and MATCH2 which are part of access path of REF1 and REF2
1021 respectively are either pointing to same address or are completely
1022 disjoint. If PARTIAL_OVERLAP is true, assume that outermost arrays may
1023 just partly overlap.
1025 Try to disambiguate using the access path starting from the match
1026 and return false if there is no conflict.
1028 Helper for aliasing_component_refs_p. */
1030 static bool
1031 aliasing_matching_component_refs_p (tree match1, tree ref1,
1032 poly_int64 offset1, poly_int64 max_size1,
1033 tree match2, tree ref2,
1034 poly_int64 offset2, poly_int64 max_size2,
1035 bool partial_overlap)
1037 poly_int64 offadj, sztmp, msztmp;
1038 bool reverse;
1040 if (!partial_overlap)
1042 get_ref_base_and_extent (match2, &offadj, &sztmp, &msztmp, &reverse);
1043 offset2 -= offadj;
1044 get_ref_base_and_extent (match1, &offadj, &sztmp, &msztmp, &reverse);
1045 offset1 -= offadj;
1046 if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
1048 ++alias_stats.aliasing_component_refs_p_no_alias;
1049 return false;
1053 int cmp = nonoverlapping_refs_since_match_p (match1, ref1, match2, ref2,
1054 partial_overlap);
1055 if (cmp == 1
1056 || (cmp == -1 && nonoverlapping_component_refs_p (ref1, ref2)))
1058 ++alias_stats.aliasing_component_refs_p_no_alias;
1059 return false;
1061 ++alias_stats.aliasing_component_refs_p_may_alias;
1062 return true;
1065 /* Return true if REF is reference to zero sized trailing array. I.e.
1066 struct foo {int bar; int array[0];} *fooptr;
1067 fooptr->array. */
1069 static bool
1070 component_ref_to_zero_sized_trailing_array_p (tree ref)
1072 return (TREE_CODE (ref) == COMPONENT_REF
1073 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 1))) == ARRAY_TYPE
1074 && (!TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)))
1075 || integer_zerop (TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)))))
1076 && array_ref_flexible_size_p (ref));
1079 /* Worker for aliasing_component_refs_p. Most parameters match parameters of
1080 aliasing_component_refs_p.
1082 Walk access path REF2 and try to find type matching TYPE1
1083 (which is a start of possibly aliasing access path REF1).
1084 If match is found, try to disambiguate.
1086 Return 0 for sucessful disambiguation.
1087 Return 1 if match was found but disambiguation failed
1088 Return -1 if there is no match.
1089 In this case MAYBE_MATCH is set to 0 if there is no type matching TYPE1
1090 in access patch REF2 and -1 if we are not sure. */
1092 static int
1093 aliasing_component_refs_walk (tree ref1, tree type1, tree base1,
1094 poly_int64 offset1, poly_int64 max_size1,
1095 tree end_struct_ref1,
1096 tree ref2, tree base2,
1097 poly_int64 offset2, poly_int64 max_size2,
1098 bool *maybe_match)
1100 tree ref = ref2;
1101 int same_p = 0;
1103 while (true)
1105 /* We walk from inner type to the outer types. If type we see is
1106 already too large to be part of type1, terminate the search. */
1107 int cmp = compare_type_sizes (type1, TREE_TYPE (ref));
1109 if (cmp < 0
1110 && (!end_struct_ref1
1111 || compare_type_sizes (TREE_TYPE (end_struct_ref1),
1112 TREE_TYPE (ref)) < 0))
1113 break;
1114 /* If types may be of same size, see if we can decide about their
1115 equality. */
1116 if (cmp == 0)
1118 same_p = same_type_for_tbaa (TREE_TYPE (ref), type1);
1119 if (same_p == 1)
1120 break;
1121 /* In case we can't decide whether types are same try to
1122 continue looking for the exact match.
1123 Remember however that we possibly saw a match
1124 to bypass the access path continuations tests we do later. */
1125 if (same_p == -1)
1126 *maybe_match = true;
1128 if (!handled_component_p (ref))
1129 break;
1130 ref = TREE_OPERAND (ref, 0);
1132 if (same_p == 1)
1134 bool partial_overlap = false;
1136 /* We assume that arrays can overlap by multiple of their elements
1137 size as tested in gcc.dg/torture/alias-2.c.
1138 This partial overlap happen only when both arrays are bases of
1139 the access and not contained within another component ref.
1140 To be safe we also assume partial overlap for VLAs. */
1141 if (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE
1142 && (!TYPE_SIZE (TREE_TYPE (base1))
1143 || TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) != INTEGER_CST
1144 || ref == base2))
1146 /* Setting maybe_match to true triggers
1147 nonoverlapping_component_refs_p test later that still may do
1148 useful disambiguation. */
1149 *maybe_match = true;
1150 partial_overlap = true;
1152 return aliasing_matching_component_refs_p (base1, ref1,
1153 offset1, max_size1,
1154 ref, ref2,
1155 offset2, max_size2,
1156 partial_overlap);
1158 return -1;
1161 /* Consider access path1 base1....ref1 and access path2 base2...ref2.
1162 Return true if they can be composed to single access path
1163 base1...ref1...base2...ref2.
1165 REF_TYPE1 if type of REF1. END_STRUCT_PAST_END1 is true if there is
1166 a trailing array access after REF1 in the non-TBAA part of the access.
1167 REF1_ALIAS_SET is the alias set of REF1.
1169 BASE_TYPE2 is type of base2. END_STRUCT_REF2 is non-NULL if there is
1170 a trailing array access in the TBAA part of access path2.
1171 BASE2_ALIAS_SET is the alias set of base2. */
1173 bool
1174 access_path_may_continue_p (tree ref_type1, bool end_struct_past_end1,
1175 alias_set_type ref1_alias_set,
1176 tree base_type2, tree end_struct_ref2,
1177 alias_set_type base2_alias_set)
1179 /* Access path can not continue past types with no components. */
1180 if (!type_has_components_p (ref_type1))
1181 return false;
1183 /* If first access path ends by too small type to hold base of
1184 the second access path, typically paths can not continue.
1186 Punt if end_struct_past_end1 is true. We want to support arbitrary
1187 type puning past first COMPONENT_REF to union because redundant store
1188 elimination depends on this, see PR92152. For this reason we can not
1189 check size of the reference because types may partially overlap. */
1190 if (!end_struct_past_end1)
1192 if (compare_type_sizes (ref_type1, base_type2) < 0)
1193 return false;
1194 /* If the path2 contains trailing array access we can strenghten the check
1195 to verify that also the size of element of the trailing array fits.
1196 In fact we could check for offset + type_size, but we do not track
1197 offsets and this is quite side case. */
1198 if (end_struct_ref2
1199 && compare_type_sizes (ref_type1, TREE_TYPE (end_struct_ref2)) < 0)
1200 return false;
1202 return (base2_alias_set == ref1_alias_set
1203 || alias_set_subset_of (base2_alias_set, ref1_alias_set));
1206 /* Determine if the two component references REF1 and REF2 which are
1207 based on access types TYPE1 and TYPE2 and of which at least one is based
1208 on an indirect reference may alias.
1209 REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
1210 are the respective alias sets. */
1212 static bool
1213 aliasing_component_refs_p (tree ref1,
1214 alias_set_type ref1_alias_set,
1215 alias_set_type base1_alias_set,
1216 poly_int64 offset1, poly_int64 max_size1,
1217 tree ref2,
1218 alias_set_type ref2_alias_set,
1219 alias_set_type base2_alias_set,
1220 poly_int64 offset2, poly_int64 max_size2)
1222 /* If one reference is a component references through pointers try to find a
1223 common base and apply offset based disambiguation. This handles
1224 for example
1225 struct A { int i; int j; } *q;
1226 struct B { struct A a; int k; } *p;
1227 disambiguating q->i and p->a.j. */
1228 tree base1, base2;
1229 tree type1, type2;
1230 bool maybe_match = false;
1231 tree end_struct_ref1 = NULL, end_struct_ref2 = NULL;
1232 bool end_struct_past_end1 = false;
1233 bool end_struct_past_end2 = false;
1235 /* Choose bases and base types to search for.
1236 The access path is as follows:
1237 base....end_of_tbaa_ref...actual_ref
1238 At one place in the access path may be a reference to zero sized or
1239 trailing array.
1241 We generally discard the segment after end_of_tbaa_ref however
1242 we need to be careful in case it contains zero sized or trailing array.
1243 These may happen after reference to union and in this case we need to
1244 not disambiguate type puning scenarios.
1246 We set:
1247 base1 to point to base
1249 ref1 to point to end_of_tbaa_ref
1251 end_struct_ref1 to point the trailing reference (if it exists
1252 in range base....end_of_tbaa_ref
1254 end_struct_past_end1 is true if this trailing reference occurs in
1255 end_of_tbaa_ref...actual_ref. */
1256 base1 = ref1;
1257 while (handled_component_p (base1))
1259 /* Generally access paths are monotous in the size of object. The
1260 exception are trailing arrays of structures. I.e.
1261 struct a {int array[0];};
1263 struct a {int array1[0]; int array[];};
1264 Such struct has size 0 but accesses to a.array may have non-zero size.
1265 In this case the size of TREE_TYPE (base1) is smaller than
1266 size of TREE_TYPE (TREE_OPERAND (base1, 0)).
1268 Because we compare sizes of arrays just by sizes of their elements,
1269 we only need to care about zero sized array fields here. */
1270 if (component_ref_to_zero_sized_trailing_array_p (base1))
1272 gcc_checking_assert (!end_struct_ref1);
1273 end_struct_ref1 = base1;
1275 if (ends_tbaa_access_path_p (base1))
1277 ref1 = TREE_OPERAND (base1, 0);
1278 if (end_struct_ref1)
1280 end_struct_past_end1 = true;
1281 end_struct_ref1 = NULL;
1284 base1 = TREE_OPERAND (base1, 0);
1286 type1 = TREE_TYPE (base1);
1287 base2 = ref2;
1288 while (handled_component_p (base2))
1290 if (component_ref_to_zero_sized_trailing_array_p (base2))
1292 gcc_checking_assert (!end_struct_ref2);
1293 end_struct_ref2 = base2;
1295 if (ends_tbaa_access_path_p (base2))
1297 ref2 = TREE_OPERAND (base2, 0);
1298 if (end_struct_ref2)
1300 end_struct_past_end2 = true;
1301 end_struct_ref2 = NULL;
1304 base2 = TREE_OPERAND (base2, 0);
1306 type2 = TREE_TYPE (base2);
1308 /* Now search for the type1 in the access path of ref2. This
1309 would be a common base for doing offset based disambiguation on.
1310 This however only makes sense if type2 is big enough to hold type1. */
1311 int cmp_outer = compare_type_sizes (type2, type1);
1313 /* If type2 is big enough to contain type1 walk its access path.
1314 We also need to care of arrays at the end of structs that may extend
1315 beyond the end of structure. If this occurs in the TBAA part of the
1316 access path, we need to consider the increased type as well. */
1317 if (cmp_outer >= 0
1318 || (end_struct_ref2
1319 && compare_type_sizes (TREE_TYPE (end_struct_ref2), type1) >= 0))
1321 int res = aliasing_component_refs_walk (ref1, type1, base1,
1322 offset1, max_size1,
1323 end_struct_ref1,
1324 ref2, base2, offset2, max_size2,
1325 &maybe_match);
1326 if (res != -1)
1327 return res;
1330 /* If we didn't find a common base, try the other way around. */
1331 if (cmp_outer <= 0
1332 || (end_struct_ref1
1333 && compare_type_sizes (TREE_TYPE (end_struct_ref1), type1) <= 0))
1335 int res = aliasing_component_refs_walk (ref2, type2, base2,
1336 offset2, max_size2,
1337 end_struct_ref2,
1338 ref1, base1, offset1, max_size1,
1339 &maybe_match);
1340 if (res != -1)
1341 return res;
1344 /* In the following code we make an assumption that the types in access
1345 paths do not overlap and thus accesses alias only if one path can be
1346 continuation of another. If we was not able to decide about equivalence,
1347 we need to give up. */
1348 if (maybe_match)
1350 if (!nonoverlapping_component_refs_p (ref1, ref2))
1352 ++alias_stats.aliasing_component_refs_p_may_alias;
1353 return true;
1355 ++alias_stats.aliasing_component_refs_p_no_alias;
1356 return false;
1359 if (access_path_may_continue_p (TREE_TYPE (ref1), end_struct_past_end1,
1360 ref1_alias_set,
1361 type2, end_struct_ref2,
1362 base2_alias_set)
1363 || access_path_may_continue_p (TREE_TYPE (ref2), end_struct_past_end2,
1364 ref2_alias_set,
1365 type1, end_struct_ref1,
1366 base1_alias_set))
1368 ++alias_stats.aliasing_component_refs_p_may_alias;
1369 return true;
1371 ++alias_stats.aliasing_component_refs_p_no_alias;
1372 return false;
1375 /* FIELD1 and FIELD2 are two fields of component refs. We assume
1376 that bases of both component refs are either equivalent or nonoverlapping.
1377 We do not assume that the containers of FIELD1 and FIELD2 are of the
1378 same type or size.
1380 Return 0 in case the base address of component_refs are same then
1381 FIELD1 and FIELD2 have same address. Note that FIELD1 and FIELD2
1382 may not be of same type or size.
1384 Return 1 if FIELD1 and FIELD2 are non-overlapping.
1386 Return -1 otherwise.
1388 Main difference between 0 and -1 is to let
1389 nonoverlapping_component_refs_since_match_p discover the semantically
1390 equivalent part of the access path.
1392 Note that this function is used even with -fno-strict-aliasing
1393 and makes use of no TBAA assumptions. */
1395 static int
1396 nonoverlapping_component_refs_p_1 (const_tree field1, const_tree field2)
1398 /* If both fields are of the same type, we could save hard work of
1399 comparing offsets. */
1400 tree type1 = DECL_CONTEXT (field1);
1401 tree type2 = DECL_CONTEXT (field2);
1403 if (TREE_CODE (type1) == RECORD_TYPE
1404 && DECL_BIT_FIELD_REPRESENTATIVE (field1))
1405 field1 = DECL_BIT_FIELD_REPRESENTATIVE (field1);
1406 if (TREE_CODE (type2) == RECORD_TYPE
1407 && DECL_BIT_FIELD_REPRESENTATIVE (field2))
1408 field2 = DECL_BIT_FIELD_REPRESENTATIVE (field2);
1410 /* ??? Bitfields can overlap at RTL level so punt on them.
1411 FIXME: RTL expansion should be fixed by adjusting the access path
1412 when producing MEM_ATTRs for MEMs which are wider than
1413 the bitfields similarly as done in set_mem_attrs_minus_bitpos. */
1414 if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
1415 return -1;
1417 /* Assume that different FIELD_DECLs never overlap within a RECORD_TYPE. */
1418 if (type1 == type2 && TREE_CODE (type1) == RECORD_TYPE)
1419 return field1 != field2;
1421 /* In common case the offsets and bit offsets will be the same.
1422 However if frontends do not agree on the alignment, they may be
1423 different even if they actually represent same address.
1424 Try the common case first and if that fails calcualte the
1425 actual bit offset. */
1426 if (tree_int_cst_equal (DECL_FIELD_OFFSET (field1),
1427 DECL_FIELD_OFFSET (field2))
1428 && tree_int_cst_equal (DECL_FIELD_BIT_OFFSET (field1),
1429 DECL_FIELD_BIT_OFFSET (field2)))
1430 return 0;
1432 /* Note that it may be possible to use component_ref_field_offset
1433 which would provide offsets as trees. However constructing and folding
1434 trees is expensive and does not seem to be worth the compile time
1435 cost. */
1437 poly_uint64 offset1, offset2;
1438 poly_uint64 bit_offset1, bit_offset2;
1440 if (poly_int_tree_p (DECL_FIELD_OFFSET (field1), &offset1)
1441 && poly_int_tree_p (DECL_FIELD_OFFSET (field2), &offset2)
1442 && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field1), &bit_offset1)
1443 && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field2), &bit_offset2))
1445 offset1 = (offset1 << LOG2_BITS_PER_UNIT) + bit_offset1;
1446 offset2 = (offset2 << LOG2_BITS_PER_UNIT) + bit_offset2;
1448 if (known_eq (offset1, offset2))
1449 return 0;
1451 poly_uint64 size1, size2;
1453 if (poly_int_tree_p (DECL_SIZE (field1), &size1)
1454 && poly_int_tree_p (DECL_SIZE (field2), &size2)
1455 && !ranges_maybe_overlap_p (offset1, size1, offset2, size2))
1456 return 1;
1458 /* Resort to slower overlap checking by looking for matching types in
1459 the middle of access path. */
1460 return -1;
1463 /* Return low bound of array. Do not produce new trees
1464 and thus do not care about particular type of integer constant
1465 and placeholder exprs. */
1467 static tree
1468 cheap_array_ref_low_bound (tree ref)
1470 tree domain_type = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (ref, 0)));
1472 /* Avoid expensive array_ref_low_bound.
1473 low bound is either stored in operand2, or it is TYPE_MIN_VALUE of domain
1474 type or it is zero. */
1475 if (TREE_OPERAND (ref, 2))
1476 return TREE_OPERAND (ref, 2);
1477 else if (domain_type && TYPE_MIN_VALUE (domain_type))
1478 return TYPE_MIN_VALUE (domain_type);
1479 else
1480 return integer_zero_node;
1483 /* REF1 and REF2 are ARRAY_REFs with either same base address or which are
1484 completely disjoint.
1486 Return 1 if the refs are non-overlapping.
1487 Return 0 if they are possibly overlapping but if so the overlap again
1488 starts on the same address.
1489 Return -1 otherwise. */
1492 nonoverlapping_array_refs_p (tree ref1, tree ref2)
1494 tree index1 = TREE_OPERAND (ref1, 1);
1495 tree index2 = TREE_OPERAND (ref2, 1);
1496 tree low_bound1 = cheap_array_ref_low_bound (ref1);
1497 tree low_bound2 = cheap_array_ref_low_bound (ref2);
1499 /* Handle zero offsets first: we do not need to match type size in this
1500 case. */
1501 if (operand_equal_p (index1, low_bound1, 0)
1502 && operand_equal_p (index2, low_bound2, 0))
1503 return 0;
1505 /* If type sizes are different, give up.
1507 Avoid expensive array_ref_element_size.
1508 If operand 3 is present it denotes size in the alignmnet units.
1509 Otherwise size is TYPE_SIZE of the element type.
1510 Handle only common cases where types are of the same "kind". */
1511 if ((TREE_OPERAND (ref1, 3) == NULL) != (TREE_OPERAND (ref2, 3) == NULL))
1512 return -1;
1514 tree elmt_type1 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref1, 0)));
1515 tree elmt_type2 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref2, 0)));
1517 if (TREE_OPERAND (ref1, 3))
1519 if (TYPE_ALIGN (elmt_type1) != TYPE_ALIGN (elmt_type2)
1520 || !operand_equal_p (TREE_OPERAND (ref1, 3),
1521 TREE_OPERAND (ref2, 3), 0))
1522 return -1;
1524 else
1526 if (!operand_equal_p (TYPE_SIZE_UNIT (elmt_type1),
1527 TYPE_SIZE_UNIT (elmt_type2), 0))
1528 return -1;
1531 /* Since we know that type sizes are the same, there is no need to return
1532 -1 after this point. Partial overlap can not be introduced. */
1534 /* We may need to fold trees in this case.
1535 TODO: Handle integer constant case at least. */
1536 if (!operand_equal_p (low_bound1, low_bound2, 0))
1537 return 0;
1539 if (TREE_CODE (index1) == INTEGER_CST && TREE_CODE (index2) == INTEGER_CST)
1541 if (tree_int_cst_equal (index1, index2))
1542 return 0;
1543 return 1;
1545 /* TODO: We can use VRP to further disambiguate here. */
1546 return 0;
1549 /* Try to disambiguate REF1 and REF2 under the assumption that MATCH1 and
1550 MATCH2 either point to the same address or are disjoint.
1551 MATCH1 and MATCH2 are assumed to be ref in the access path of REF1 and REF2
1552 respectively or NULL in the case we established equivalence of bases.
1553 If PARTIAL_OVERLAP is true assume that the toplevel arrays may actually
1554 overlap by exact multiply of their element size.
1556 This test works by matching the initial segment of the access path
1557 and does not rely on TBAA thus is safe for !flag_strict_aliasing if
1558 match was determined without use of TBAA oracle.
1560 Return 1 if we can determine that component references REF1 and REF2,
1561 that are within a common DECL, cannot overlap.
1563 Return 0 if paths are same and thus there is nothing to disambiguate more
1564 (i.e. there is must alias assuming there is must alias between MATCH1 and
1565 MATCH2)
1567 Return -1 if we can not determine 0 or 1 - this happens when we met
1568 non-matching types was met in the path.
1569 In this case it may make sense to continue by other disambiguation
1570 oracles. */
1572 static int
1573 nonoverlapping_refs_since_match_p (tree match1, tree ref1,
1574 tree match2, tree ref2,
1575 bool partial_overlap)
1577 int ntbaa1 = 0, ntbaa2 = 0;
1578 /* Early return if there are no references to match, we do not need
1579 to walk the access paths.
1581 Do not consider this as may-alias for stats - it is more useful
1582 to have information how many disambiguations happened provided that
1583 the query was meaningful. */
1585 if (match1 == ref1 || !handled_component_p (ref1)
1586 || match2 == ref2 || !handled_component_p (ref2))
1587 return -1;
1589 auto_vec<tree, 16> component_refs1;
1590 auto_vec<tree, 16> component_refs2;
1592 /* Create the stack of handled components for REF1. */
1593 while (handled_component_p (ref1) && ref1 != match1)
1595 /* We use TBAA only to re-synchronize after mismatched refs. So we
1596 do not need to truncate access path after TBAA part ends. */
1597 if (ends_tbaa_access_path_p (ref1))
1598 ntbaa1 = 0;
1599 else
1600 ntbaa1++;
1601 component_refs1.safe_push (ref1);
1602 ref1 = TREE_OPERAND (ref1, 0);
1605 /* Create the stack of handled components for REF2. */
1606 while (handled_component_p (ref2) && ref2 != match2)
1608 if (ends_tbaa_access_path_p (ref2))
1609 ntbaa2 = 0;
1610 else
1611 ntbaa2++;
1612 component_refs2.safe_push (ref2);
1613 ref2 = TREE_OPERAND (ref2, 0);
1616 if (!flag_strict_aliasing)
1618 ntbaa1 = 0;
1619 ntbaa2 = 0;
1622 bool mem_ref1 = TREE_CODE (ref1) == MEM_REF && ref1 != match1;
1623 bool mem_ref2 = TREE_CODE (ref2) == MEM_REF && ref2 != match2;
1625 /* If only one of access path starts with MEM_REF check that offset is 0
1626 so the addresses stays the same after stripping it.
1627 TODO: In this case we may walk the other access path until we get same
1628 offset.
1630 If both starts with MEM_REF, offset has to be same. */
1631 if ((mem_ref1 && !mem_ref2 && !integer_zerop (TREE_OPERAND (ref1, 1)))
1632 || (mem_ref2 && !mem_ref1 && !integer_zerop (TREE_OPERAND (ref2, 1)))
1633 || (mem_ref1 && mem_ref2
1634 && !tree_int_cst_equal (TREE_OPERAND (ref1, 1),
1635 TREE_OPERAND (ref2, 1))))
1637 ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1638 return -1;
1641 /* TARGET_MEM_REF are never wrapped in handled components, so we do not need
1642 to handle them here at all. */
1643 gcc_checking_assert (TREE_CODE (ref1) != TARGET_MEM_REF
1644 && TREE_CODE (ref2) != TARGET_MEM_REF);
1646 /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
1647 rank. This is sufficient because we start from the same DECL and you
1648 cannot reference several fields at a time with COMPONENT_REFs (unlike
1649 with ARRAY_RANGE_REFs for arrays) so you always need the same number
1650 of them to access a sub-component, unless you're in a union, in which
1651 case the return value will precisely be false. */
1652 while (true)
1654 /* Track if we seen unmatched ref with non-zero offset. In this case
1655 we must look for partial overlaps. */
1656 bool seen_unmatched_ref_p = false;
1658 /* First match ARRAY_REFs an try to disambiguate. */
1659 if (!component_refs1.is_empty ()
1660 && !component_refs2.is_empty ())
1662 unsigned int narray_refs1=0, narray_refs2=0;
1664 /* We generally assume that both access paths starts by same sequence
1665 of refs. However if number of array refs is not in sync, try
1666 to recover and pop elts until number match. This helps the case
1667 where one access path starts by array and other by element. */
1668 for (narray_refs1 = 0; narray_refs1 < component_refs1.length ();
1669 narray_refs1++)
1670 if (TREE_CODE (component_refs1 [component_refs1.length()
1671 - 1 - narray_refs1]) != ARRAY_REF)
1672 break;
1674 for (narray_refs2 = 0; narray_refs2 < component_refs2.length ();
1675 narray_refs2++)
1676 if (TREE_CODE (component_refs2 [component_refs2.length()
1677 - 1 - narray_refs2]) != ARRAY_REF)
1678 break;
1679 for (; narray_refs1 > narray_refs2; narray_refs1--)
1681 ref1 = component_refs1.pop ();
1682 ntbaa1--;
1684 /* If index is non-zero we need to check whether the reference
1685 does not break the main invariant that bases are either
1686 disjoint or equal. Consider the example:
1688 unsigned char out[][1];
1689 out[1]="a";
1690 out[i][0];
1692 Here bases out and out are same, but after removing the
1693 [i] index, this invariant no longer holds, because
1694 out[i] points to the middle of array out.
1696 TODO: If size of type of the skipped reference is an integer
1697 multiply of the size of type of the other reference this
1698 invariant can be verified, but even then it is not completely
1699 safe with !flag_strict_aliasing if the other reference contains
1700 unbounded array accesses.
1701 See */
1703 if (!operand_equal_p (TREE_OPERAND (ref1, 1),
1704 cheap_array_ref_low_bound (ref1), 0))
1705 return 0;
1707 for (; narray_refs2 > narray_refs1; narray_refs2--)
1709 ref2 = component_refs2.pop ();
1710 ntbaa2--;
1711 if (!operand_equal_p (TREE_OPERAND (ref2, 1),
1712 cheap_array_ref_low_bound (ref2), 0))
1713 return 0;
1715 /* Try to disambiguate matched arrays. */
1716 for (unsigned int i = 0; i < narray_refs1; i++)
1718 int cmp = nonoverlapping_array_refs_p (component_refs1.pop (),
1719 component_refs2.pop ());
1720 ntbaa1--;
1721 ntbaa2--;
1722 if (cmp == 1 && !partial_overlap)
1724 ++alias_stats
1725 .nonoverlapping_refs_since_match_p_no_alias;
1726 return 1;
1728 if (cmp == -1)
1730 seen_unmatched_ref_p = true;
1731 /* We can not maintain the invariant that bases are either
1732 same or completely disjoint. However we can still recover
1733 from type based alias analysis if we reach references to
1734 same sizes. We do not attempt to match array sizes, so
1735 just finish array walking and look for component refs. */
1736 if (ntbaa1 < 0 || ntbaa2 < 0)
1738 ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1739 return -1;
1741 for (i++; i < narray_refs1; i++)
1743 component_refs1.pop ();
1744 component_refs2.pop ();
1745 ntbaa1--;
1746 ntbaa2--;
1748 break;
1750 partial_overlap = false;
1754 /* Next look for component_refs. */
1757 if (component_refs1.is_empty ())
1759 ++alias_stats
1760 .nonoverlapping_refs_since_match_p_must_overlap;
1761 return 0;
1763 ref1 = component_refs1.pop ();
1764 ntbaa1--;
1765 if (TREE_CODE (ref1) != COMPONENT_REF)
1767 seen_unmatched_ref_p = true;
1768 if (ntbaa1 < 0 || ntbaa2 < 0)
1770 ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1771 return -1;
1775 while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
1779 if (component_refs2.is_empty ())
1781 ++alias_stats
1782 .nonoverlapping_refs_since_match_p_must_overlap;
1783 return 0;
1785 ref2 = component_refs2.pop ();
1786 ntbaa2--;
1787 if (TREE_CODE (ref2) != COMPONENT_REF)
1789 if (ntbaa1 < 0 || ntbaa2 < 0)
1791 ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1792 return -1;
1794 seen_unmatched_ref_p = true;
1797 while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0))));
1799 /* BIT_FIELD_REF and VIEW_CONVERT_EXPR are taken off the vectors
1800 earlier. */
1801 gcc_checking_assert (TREE_CODE (ref1) == COMPONENT_REF
1802 && TREE_CODE (ref2) == COMPONENT_REF);
1804 tree field1 = TREE_OPERAND (ref1, 1);
1805 tree field2 = TREE_OPERAND (ref2, 1);
1807 /* ??? We cannot simply use the type of operand #0 of the refs here
1808 as the Fortran compiler smuggles type punning into COMPONENT_REFs
1809 for common blocks instead of using unions like everyone else. */
1810 tree type1 = DECL_CONTEXT (field1);
1811 tree type2 = DECL_CONTEXT (field2);
1813 partial_overlap = false;
1815 /* If we skipped array refs on type of different sizes, we can
1816 no longer be sure that there are not partial overlaps. */
1817 if (seen_unmatched_ref_p && ntbaa1 >= 0 && ntbaa2 >= 0
1818 && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
1820 ++alias_stats
1821 .nonoverlapping_refs_since_match_p_may_alias;
1822 return -1;
1825 int cmp = nonoverlapping_component_refs_p_1 (field1, field2);
1826 if (cmp == -1)
1828 ++alias_stats
1829 .nonoverlapping_refs_since_match_p_may_alias;
1830 return -1;
1832 else if (cmp == 1)
1834 ++alias_stats
1835 .nonoverlapping_refs_since_match_p_no_alias;
1836 return 1;
1841 /* Return TYPE_UID which can be used to match record types we consider
1842 same for TBAA purposes. */
1844 static inline int
1845 ncr_type_uid (const_tree field)
1847 /* ??? We cannot simply use the type of operand #0 of the refs here
1848 as the Fortran compiler smuggles type punning into COMPONENT_REFs
1849 for common blocks instead of using unions like everyone else. */
1850 tree type = DECL_FIELD_CONTEXT (field);
1851 /* With LTO types considered same_type_for_tbaa_p
1852 from different translation unit may not have same
1853 main variant. They however have same TYPE_CANONICAL. */
1854 if (TYPE_CANONICAL (type))
1855 return TYPE_UID (TYPE_CANONICAL (type));
1856 return TYPE_UID (type);
1859 /* qsort compare function to sort FIELD_DECLs after their
1860 DECL_FIELD_CONTEXT TYPE_UID. */
1862 static inline int
1863 ncr_compar (const void *field1_, const void *field2_)
1865 const_tree field1 = *(const_tree *) const_cast <void *>(field1_);
1866 const_tree field2 = *(const_tree *) const_cast <void *>(field2_);
1867 unsigned int uid1 = ncr_type_uid (field1);
1868 unsigned int uid2 = ncr_type_uid (field2);
1870 if (uid1 < uid2)
1871 return -1;
1872 else if (uid1 > uid2)
1873 return 1;
1874 return 0;
1877 /* Return true if we can determine that the fields referenced cannot
1878 overlap for any pair of objects. This relies on TBAA. */
1880 static bool
1881 nonoverlapping_component_refs_p (const_tree x, const_tree y)
1883 /* Early return if we have nothing to do.
1885 Do not consider this as may-alias for stats - it is more useful
1886 to have information how many disambiguations happened provided that
1887 the query was meaningful. */
1888 if (!flag_strict_aliasing
1889 || !x || !y
1890 || !handled_component_p (x)
1891 || !handled_component_p (y))
1892 return false;
1894 auto_vec<const_tree, 16> fieldsx;
1895 while (handled_component_p (x))
1897 if (TREE_CODE (x) == COMPONENT_REF)
1899 tree field = TREE_OPERAND (x, 1);
1900 tree type = DECL_FIELD_CONTEXT (field);
1901 if (TREE_CODE (type) == RECORD_TYPE)
1902 fieldsx.safe_push (field);
1904 else if (ends_tbaa_access_path_p (x))
1905 fieldsx.truncate (0);
1906 x = TREE_OPERAND (x, 0);
1908 if (fieldsx.length () == 0)
1909 return false;
1910 auto_vec<const_tree, 16> fieldsy;
1911 while (handled_component_p (y))
1913 if (TREE_CODE (y) == COMPONENT_REF)
1915 tree field = TREE_OPERAND (y, 1);
1916 tree type = DECL_FIELD_CONTEXT (field);
1917 if (TREE_CODE (type) == RECORD_TYPE)
1918 fieldsy.safe_push (TREE_OPERAND (y, 1));
1920 else if (ends_tbaa_access_path_p (y))
1921 fieldsy.truncate (0);
1922 y = TREE_OPERAND (y, 0);
1924 if (fieldsy.length () == 0)
1926 ++alias_stats.nonoverlapping_component_refs_p_may_alias;
1927 return false;
1930 /* Most common case first. */
1931 if (fieldsx.length () == 1
1932 && fieldsy.length () == 1)
1934 if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldsx[0]),
1935 DECL_FIELD_CONTEXT (fieldsy[0])) == 1
1936 && nonoverlapping_component_refs_p_1 (fieldsx[0], fieldsy[0]) == 1)
1938 ++alias_stats.nonoverlapping_component_refs_p_no_alias;
1939 return true;
1941 else
1943 ++alias_stats.nonoverlapping_component_refs_p_may_alias;
1944 return false;
1948 if (fieldsx.length () == 2)
1950 if (ncr_compar (&fieldsx[0], &fieldsx[1]) == 1)
1951 std::swap (fieldsx[0], fieldsx[1]);
1953 else
1954 fieldsx.qsort (ncr_compar);
1956 if (fieldsy.length () == 2)
1958 if (ncr_compar (&fieldsy[0], &fieldsy[1]) == 1)
1959 std::swap (fieldsy[0], fieldsy[1]);
1961 else
1962 fieldsy.qsort (ncr_compar);
1964 unsigned i = 0, j = 0;
1967 const_tree fieldx = fieldsx[i];
1968 const_tree fieldy = fieldsy[j];
1970 /* We're left with accessing different fields of a structure,
1971 no possible overlap. */
1972 if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldx),
1973 DECL_FIELD_CONTEXT (fieldy)) == 1
1974 && nonoverlapping_component_refs_p_1 (fieldx, fieldy) == 1)
1976 ++alias_stats.nonoverlapping_component_refs_p_no_alias;
1977 return true;
1980 if (ncr_type_uid (fieldx) < ncr_type_uid (fieldy))
1982 i++;
1983 if (i == fieldsx.length ())
1984 break;
1986 else
1988 j++;
1989 if (j == fieldsy.length ())
1990 break;
1993 while (1);
1995 ++alias_stats.nonoverlapping_component_refs_p_may_alias;
1996 return false;
2000 /* Return true if two memory references based on the variables BASE1
2001 and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
2002 [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. REF1 and REF2
2003 if non-NULL are the complete memory reference trees. */
2005 static bool
2006 decl_refs_may_alias_p (tree ref1, tree base1,
2007 poly_int64 offset1, poly_int64 max_size1,
2008 poly_int64 size1,
2009 tree ref2, tree base2,
2010 poly_int64 offset2, poly_int64 max_size2,
2011 poly_int64 size2)
2013 gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
2015 /* If both references are based on different variables, they cannot alias. */
2016 if (compare_base_decls (base1, base2) == 0)
2017 return false;
2019 /* If both references are based on the same variable, they cannot alias if
2020 the accesses do not overlap. */
2021 if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
2022 return false;
2024 /* If there is must alias, there is no use disambiguating further. */
2025 if (known_eq (size1, max_size1) && known_eq (size2, max_size2))
2026 return true;
2028 /* For components with variable position, the above test isn't sufficient,
2029 so we disambiguate component references manually. */
2030 if (ref1 && ref2
2031 && handled_component_p (ref1) && handled_component_p (ref2)
2032 && nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2, false) == 1)
2033 return false;
2035 return true;
2038 /* Return true if access with BASE is view converted.
2039 Base must not be stripped from inner MEM_REF (&decl)
2040 which is done by ao_ref_base and thus one extra walk
2041 of handled components is needed. */
2043 static bool
2044 view_converted_memref_p (tree base)
2046 if (TREE_CODE (base) != MEM_REF && TREE_CODE (base) != TARGET_MEM_REF)
2047 return false;
2048 return same_type_for_tbaa (TREE_TYPE (base),
2049 TREE_TYPE (TREE_OPERAND (base, 1))) != 1;
2052 /* Return true if an indirect reference based on *PTR1 constrained
2053 to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
2054 constrained to [OFFSET2, OFFSET2 + MAX_SIZE2). *PTR1 and BASE2 have
2055 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
2056 in which case they are computed on-demand. REF1 and REF2
2057 if non-NULL are the complete memory reference trees. */
2059 static bool
2060 indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
2061 poly_int64 offset1, poly_int64 max_size1,
2062 poly_int64 size1,
2063 alias_set_type ref1_alias_set,
2064 alias_set_type base1_alias_set,
2065 tree ref2 ATTRIBUTE_UNUSED, tree base2,
2066 poly_int64 offset2, poly_int64 max_size2,
2067 poly_int64 size2,
2068 alias_set_type ref2_alias_set,
2069 alias_set_type base2_alias_set, bool tbaa_p)
2071 tree ptr1;
2072 tree ptrtype1, dbase2;
2074 gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
2075 || TREE_CODE (base1) == TARGET_MEM_REF)
2076 && DECL_P (base2));
2078 ptr1 = TREE_OPERAND (base1, 0);
2079 poly_offset_int moff = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
2081 /* If only one reference is based on a variable, they cannot alias if
2082 the pointer access is beyond the extent of the variable access.
2083 (the pointer base cannot validly point to an offset less than zero
2084 of the variable).
2085 ??? IVOPTs creates bases that do not honor this restriction,
2086 so do not apply this optimization for TARGET_MEM_REFs. */
2087 if (TREE_CODE (base1) != TARGET_MEM_REF
2088 && !ranges_maybe_overlap_p (offset1 + moff, -1, offset2, max_size2))
2089 return false;
2091 /* If the pointer based access is bigger than the variable they cannot
2092 alias. This is similar to the check below where we use TBAA to
2093 increase the size of the pointer based access based on the dynamic
2094 type of a containing object we can infer from it. */
2095 poly_int64 dsize2;
2096 if (known_size_p (size1)
2097 && poly_int_tree_p (DECL_SIZE (base2), &dsize2)
2098 && known_lt (dsize2, size1))
2099 return false;
2101 /* They also cannot alias if the pointer may not point to the decl. */
2102 if (!ptr_deref_may_alias_decl_p (ptr1, base2))
2103 return false;
2105 /* Disambiguations that rely on strict aliasing rules follow. */
2106 if (!flag_strict_aliasing || !tbaa_p)
2107 return true;
2109 /* If the alias set for a pointer access is zero all bets are off. */
2110 if (base1_alias_set == 0 || base2_alias_set == 0)
2111 return true;
2113 /* When we are trying to disambiguate an access with a pointer dereference
2114 as base versus one with a decl as base we can use both the size
2115 of the decl and its dynamic type for extra disambiguation.
2116 ??? We do not know anything about the dynamic type of the decl
2117 other than that its alias-set contains base2_alias_set as a subset
2118 which does not help us here. */
2119 /* As we know nothing useful about the dynamic type of the decl just
2120 use the usual conflict check rather than a subset test.
2121 ??? We could introduce -fvery-strict-aliasing when the language
2122 does not allow decls to have a dynamic type that differs from their
2123 static type. Then we can check
2124 !alias_set_subset_of (base1_alias_set, base2_alias_set) instead. */
2125 if (base1_alias_set != base2_alias_set
2126 && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
2127 return false;
2129 ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
2131 /* If the size of the access relevant for TBAA through the pointer
2132 is bigger than the size of the decl we can't possibly access the
2133 decl via that pointer. */
2134 if (/* ??? This in turn may run afoul when a decl of type T which is
2135 a member of union type U is accessed through a pointer to
2136 type U and sizeof T is smaller than sizeof U. */
2137 TREE_CODE (TREE_TYPE (ptrtype1)) != UNION_TYPE
2138 && TREE_CODE (TREE_TYPE (ptrtype1)) != QUAL_UNION_TYPE
2139 && compare_sizes (DECL_SIZE (base2),
2140 TYPE_SIZE (TREE_TYPE (ptrtype1))) < 0)
2141 return false;
2143 if (!ref2)
2144 return true;
2146 /* If the decl is accessed via a MEM_REF, reconstruct the base
2147 we can use for TBAA and an appropriately adjusted offset. */
2148 dbase2 = ref2;
2149 while (handled_component_p (dbase2))
2150 dbase2 = TREE_OPERAND (dbase2, 0);
2151 poly_int64 doffset1 = offset1;
2152 poly_offset_int doffset2 = offset2;
2153 if (TREE_CODE (dbase2) == MEM_REF
2154 || TREE_CODE (dbase2) == TARGET_MEM_REF)
2156 doffset2 -= mem_ref_offset (dbase2) << LOG2_BITS_PER_UNIT;
2157 tree ptrtype2 = TREE_TYPE (TREE_OPERAND (dbase2, 1));
2158 /* If second reference is view-converted, give up now. */
2159 if (same_type_for_tbaa (TREE_TYPE (dbase2), TREE_TYPE (ptrtype2)) != 1)
2160 return true;
2163 /* If first reference is view-converted, give up now. */
2164 if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1)
2165 return true;
2167 /* If both references are through the same type, they do not alias
2168 if the accesses do not overlap. This does extra disambiguation
2169 for mixed/pointer accesses but requires strict aliasing.
2170 For MEM_REFs we require that the component-ref offset we computed
2171 is relative to the start of the type which we ensure by
2172 comparing rvalue and access type and disregarding the constant
2173 pointer offset.
2175 But avoid treating variable length arrays as "objects", instead assume they
2176 can overlap by an exact multiple of their element size.
2177 See gcc.dg/torture/alias-2.c. */
2178 if (((TREE_CODE (base1) != TARGET_MEM_REF
2179 || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
2180 && (TREE_CODE (dbase2) != TARGET_MEM_REF
2181 || (!TMR_INDEX (dbase2) && !TMR_INDEX2 (dbase2))))
2182 && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1)
2184 bool partial_overlap = (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE
2185 && (TYPE_SIZE (TREE_TYPE (base1))
2186 && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1)))
2187 != INTEGER_CST));
2188 if (!partial_overlap
2189 && !ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2))
2190 return false;
2191 if (!ref1 || !ref2
2192 /* If there is must alias, there is no use disambiguating further. */
2193 || (!partial_overlap
2194 && known_eq (size1, max_size1) && known_eq (size2, max_size2)))
2195 return true;
2196 int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2,
2197 partial_overlap);
2198 if (res == -1)
2199 return !nonoverlapping_component_refs_p (ref1, ref2);
2200 return !res;
2203 /* Do access-path based disambiguation. */
2204 if (ref1 && ref2
2205 && (handled_component_p (ref1) || handled_component_p (ref2)))
2206 return aliasing_component_refs_p (ref1,
2207 ref1_alias_set, base1_alias_set,
2208 offset1, max_size1,
2209 ref2,
2210 ref2_alias_set, base2_alias_set,
2211 offset2, max_size2);
2213 return true;
2216 /* Return true if two indirect references based on *PTR1
2217 and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
2218 [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. *PTR1 and *PTR2 have
2219 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
2220 in which case they are computed on-demand. REF1 and REF2
2221 if non-NULL are the complete memory reference trees. */
2223 static bool
2224 indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
2225 poly_int64 offset1, poly_int64 max_size1,
2226 poly_int64 size1,
2227 alias_set_type ref1_alias_set,
2228 alias_set_type base1_alias_set,
2229 tree ref2 ATTRIBUTE_UNUSED, tree base2,
2230 poly_int64 offset2, poly_int64 max_size2,
2231 poly_int64 size2,
2232 alias_set_type ref2_alias_set,
2233 alias_set_type base2_alias_set, bool tbaa_p)
2235 tree ptr1;
2236 tree ptr2;
2237 tree ptrtype1, ptrtype2;
2239 gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
2240 || TREE_CODE (base1) == TARGET_MEM_REF)
2241 && (TREE_CODE (base2) == MEM_REF
2242 || TREE_CODE (base2) == TARGET_MEM_REF));
2244 ptr1 = TREE_OPERAND (base1, 0);
2245 ptr2 = TREE_OPERAND (base2, 0);
2247 /* If both bases are based on pointers they cannot alias if they may not
2248 point to the same memory object or if they point to the same object
2249 and the accesses do not overlap. */
2250 if ((!cfun || gimple_in_ssa_p (cfun))
2251 && operand_equal_p (ptr1, ptr2, 0)
2252 && (((TREE_CODE (base1) != TARGET_MEM_REF
2253 || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
2254 && (TREE_CODE (base2) != TARGET_MEM_REF
2255 || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2))))
2256 || (TREE_CODE (base1) == TARGET_MEM_REF
2257 && TREE_CODE (base2) == TARGET_MEM_REF
2258 && (TMR_STEP (base1) == TMR_STEP (base2)
2259 || (TMR_STEP (base1) && TMR_STEP (base2)
2260 && operand_equal_p (TMR_STEP (base1),
2261 TMR_STEP (base2), 0)))
2262 && (TMR_INDEX (base1) == TMR_INDEX (base2)
2263 || (TMR_INDEX (base1) && TMR_INDEX (base2)
2264 && operand_equal_p (TMR_INDEX (base1),
2265 TMR_INDEX (base2), 0)))
2266 && (TMR_INDEX2 (base1) == TMR_INDEX2 (base2)
2267 || (TMR_INDEX2 (base1) && TMR_INDEX2 (base2)
2268 && operand_equal_p (TMR_INDEX2 (base1),
2269 TMR_INDEX2 (base2), 0))))))
2271 poly_offset_int moff1 = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
2272 poly_offset_int moff2 = mem_ref_offset (base2) << LOG2_BITS_PER_UNIT;
2273 if (!ranges_maybe_overlap_p (offset1 + moff1, max_size1,
2274 offset2 + moff2, max_size2))
2275 return false;
2276 /* If there is must alias, there is no use disambiguating further. */
2277 if (known_eq (size1, max_size1) && known_eq (size2, max_size2))
2278 return true;
2279 if (ref1 && ref2)
2281 int res = nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2,
2282 false);
2283 if (res != -1)
2284 return !res;
2287 if (!ptr_derefs_may_alias_p (ptr1, ptr2))
2288 return false;
2290 /* Disambiguations that rely on strict aliasing rules follow. */
2291 if (!flag_strict_aliasing || !tbaa_p)
2292 return true;
2294 ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
2295 ptrtype2 = TREE_TYPE (TREE_OPERAND (base2, 1));
2297 /* If the alias set for a pointer access is zero all bets are off. */
2298 if (base1_alias_set == 0
2299 || base2_alias_set == 0)
2300 return true;
2302 /* Do type-based disambiguation. */
2303 if (base1_alias_set != base2_alias_set
2304 && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
2305 return false;
2307 /* If either reference is view-converted, give up now. */
2308 if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
2309 || same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) != 1)
2310 return true;
2312 /* If both references are through the same type, they do not alias
2313 if the accesses do not overlap. This does extra disambiguation
2314 for mixed/pointer accesses but requires strict aliasing. */
2315 if ((TREE_CODE (base1) != TARGET_MEM_REF
2316 || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
2317 && (TREE_CODE (base2) != TARGET_MEM_REF
2318 || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2)))
2319 && same_type_for_tbaa (TREE_TYPE (ptrtype1),
2320 TREE_TYPE (ptrtype2)) == 1)
2322 /* But avoid treating arrays as "objects", instead assume they
2323 can overlap by an exact multiple of their element size.
2324 See gcc.dg/torture/alias-2.c. */
2325 bool partial_overlap = TREE_CODE (TREE_TYPE (ptrtype1)) == ARRAY_TYPE;
2327 if (!partial_overlap
2328 && !ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
2329 return false;
2330 if (!ref1 || !ref2
2331 || (!partial_overlap
2332 && known_eq (size1, max_size1) && known_eq (size2, max_size2)))
2333 return true;
2334 int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2,
2335 partial_overlap);
2336 if (res == -1)
2337 return !nonoverlapping_component_refs_p (ref1, ref2);
2338 return !res;
2341 /* Do access-path based disambiguation. */
2342 if (ref1 && ref2
2343 && (handled_component_p (ref1) || handled_component_p (ref2)))
2344 return aliasing_component_refs_p (ref1,
2345 ref1_alias_set, base1_alias_set,
2346 offset1, max_size1,
2347 ref2,
2348 ref2_alias_set, base2_alias_set,
2349 offset2, max_size2);
2351 return true;
2354 /* Return true, if the two memory references REF1 and REF2 may alias. */
2356 static bool
2357 refs_may_alias_p_2 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
2359 tree base1, base2;
2360 poly_int64 offset1 = 0, offset2 = 0;
2361 poly_int64 max_size1 = -1, max_size2 = -1;
2362 bool var1_p, var2_p, ind1_p, ind2_p;
2364 gcc_checking_assert ((!ref1->ref
2365 || TREE_CODE (ref1->ref) == SSA_NAME
2366 || DECL_P (ref1->ref)
2367 || TREE_CODE (ref1->ref) == STRING_CST
2368 || handled_component_p (ref1->ref)
2369 || TREE_CODE (ref1->ref) == MEM_REF
2370 || TREE_CODE (ref1->ref) == TARGET_MEM_REF
2371 || TREE_CODE (ref1->ref) == WITH_SIZE_EXPR)
2372 && (!ref2->ref
2373 || TREE_CODE (ref2->ref) == SSA_NAME
2374 || DECL_P (ref2->ref)
2375 || TREE_CODE (ref2->ref) == STRING_CST
2376 || handled_component_p (ref2->ref)
2377 || TREE_CODE (ref2->ref) == MEM_REF
2378 || TREE_CODE (ref2->ref) == TARGET_MEM_REF
2379 || TREE_CODE (ref2->ref) == WITH_SIZE_EXPR));
2381 /* Decompose the references into their base objects and the access. */
2382 base1 = ao_ref_base (ref1);
2383 offset1 = ref1->offset;
2384 max_size1 = ref1->max_size;
2385 base2 = ao_ref_base (ref2);
2386 offset2 = ref2->offset;
2387 max_size2 = ref2->max_size;
2389 /* We can end up with registers or constants as bases for example from
2390 *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
2391 which is seen as a struct copy. */
2392 if (TREE_CODE (base1) == SSA_NAME
2393 || TREE_CODE (base1) == CONST_DECL
2394 || TREE_CODE (base1) == CONSTRUCTOR
2395 || TREE_CODE (base1) == ADDR_EXPR
2396 || CONSTANT_CLASS_P (base1)
2397 || TREE_CODE (base2) == SSA_NAME
2398 || TREE_CODE (base2) == CONST_DECL
2399 || TREE_CODE (base2) == CONSTRUCTOR
2400 || TREE_CODE (base2) == ADDR_EXPR
2401 || CONSTANT_CLASS_P (base2))
2402 return false;
2404 /* Two volatile accesses always conflict. */
2405 if (ref1->volatile_p
2406 && ref2->volatile_p)
2407 return true;
2409 /* refN->ref may convey size information, do not confuse our workers
2410 with that but strip it - ao_ref_base took it into account already. */
2411 tree ref1ref = ref1->ref;
2412 if (ref1ref && TREE_CODE (ref1ref) == WITH_SIZE_EXPR)
2413 ref1ref = TREE_OPERAND (ref1ref, 0);
2414 tree ref2ref = ref2->ref;
2415 if (ref2ref && TREE_CODE (ref2ref) == WITH_SIZE_EXPR)
2416 ref2ref = TREE_OPERAND (ref2ref, 0);
2418 /* Defer to simple offset based disambiguation if we have
2419 references based on two decls. Do this before defering to
2420 TBAA to handle must-alias cases in conformance with the
2421 GCC extension of allowing type-punning through unions. */
2422 var1_p = DECL_P (base1);
2423 var2_p = DECL_P (base2);
2424 if (var1_p && var2_p)
2425 return decl_refs_may_alias_p (ref1ref, base1, offset1, max_size1,
2426 ref1->size,
2427 ref2ref, base2, offset2, max_size2,
2428 ref2->size);
2430 /* We can end up referring to code via function and label decls.
2431 As we likely do not properly track code aliases conservatively
2432 bail out. */
2433 if (TREE_CODE (base1) == FUNCTION_DECL
2434 || TREE_CODE (base1) == LABEL_DECL
2435 || TREE_CODE (base2) == FUNCTION_DECL
2436 || TREE_CODE (base2) == LABEL_DECL)
2437 return true;
2439 /* Handle restrict based accesses.
2440 ??? ao_ref_base strips inner MEM_REF [&decl], recover from that
2441 here. */
2442 tree rbase1 = base1;
2443 tree rbase2 = base2;
2444 if (var1_p)
2446 rbase1 = ref1ref;
2447 if (rbase1)
2448 while (handled_component_p (rbase1))
2449 rbase1 = TREE_OPERAND (rbase1, 0);
2451 if (var2_p)
2453 rbase2 = ref2ref;
2454 if (rbase2)
2455 while (handled_component_p (rbase2))
2456 rbase2 = TREE_OPERAND (rbase2, 0);
2458 if (rbase1 && rbase2
2459 && (TREE_CODE (rbase1) == MEM_REF || TREE_CODE (rbase1) == TARGET_MEM_REF)
2460 && (TREE_CODE (rbase2) == MEM_REF || TREE_CODE (rbase2) == TARGET_MEM_REF)
2461 /* If the accesses are in the same restrict clique... */
2462 && MR_DEPENDENCE_CLIQUE (rbase1) == MR_DEPENDENCE_CLIQUE (rbase2)
2463 /* But based on different pointers they do not alias. */
2464 && MR_DEPENDENCE_BASE (rbase1) != MR_DEPENDENCE_BASE (rbase2))
2465 return false;
2467 ind1_p = (TREE_CODE (base1) == MEM_REF
2468 || TREE_CODE (base1) == TARGET_MEM_REF);
2469 ind2_p = (TREE_CODE (base2) == MEM_REF
2470 || TREE_CODE (base2) == TARGET_MEM_REF);
2472 /* Canonicalize the pointer-vs-decl case. */
2473 if (ind1_p && var2_p)
2475 std::swap (offset1, offset2);
2476 std::swap (max_size1, max_size2);
2477 std::swap (base1, base2);
2478 std::swap (ref1, ref2);
2479 std::swap (ref1ref, ref2ref);
2480 var1_p = true;
2481 ind1_p = false;
2482 var2_p = false;
2483 ind2_p = true;
2486 /* First defer to TBAA if possible. */
2487 if (tbaa_p
2488 && flag_strict_aliasing
2489 && !alias_sets_conflict_p (ao_ref_alias_set (ref1),
2490 ao_ref_alias_set (ref2)))
2491 return false;
2493 /* If the reference is based on a pointer that points to memory
2494 that may not be written to then the other reference cannot possibly
2495 clobber it. */
2496 if ((TREE_CODE (TREE_OPERAND (base2, 0)) == SSA_NAME
2497 && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base2, 0)))
2498 || (ind1_p
2499 && TREE_CODE (TREE_OPERAND (base1, 0)) == SSA_NAME
2500 && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base1, 0))))
2501 return false;
2503 /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators. */
2504 if (var1_p && ind2_p)
2505 return indirect_ref_may_alias_decl_p (ref2ref, base2,
2506 offset2, max_size2, ref2->size,
2507 ao_ref_alias_set (ref2),
2508 ao_ref_base_alias_set (ref2),
2509 ref1ref, base1,
2510 offset1, max_size1, ref1->size,
2511 ao_ref_alias_set (ref1),
2512 ao_ref_base_alias_set (ref1),
2513 tbaa_p);
2514 else if (ind1_p && ind2_p)
2515 return indirect_refs_may_alias_p (ref1ref, base1,
2516 offset1, max_size1, ref1->size,
2517 ao_ref_alias_set (ref1),
2518 ao_ref_base_alias_set (ref1),
2519 ref2ref, base2,
2520 offset2, max_size2, ref2->size,
2521 ao_ref_alias_set (ref2),
2522 ao_ref_base_alias_set (ref2),
2523 tbaa_p);
2525 gcc_unreachable ();
2528 /* Return true, if the two memory references REF1 and REF2 may alias
2529 and update statistics. */
2531 bool
2532 refs_may_alias_p_1 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
2534 bool res = refs_may_alias_p_2 (ref1, ref2, tbaa_p);
2535 if (res)
2536 ++alias_stats.refs_may_alias_p_may_alias;
2537 else
2538 ++alias_stats.refs_may_alias_p_no_alias;
2539 return res;
2542 static bool
2543 refs_may_alias_p (tree ref1, ao_ref *ref2, bool tbaa_p)
2545 ao_ref r1;
2546 ao_ref_init (&r1, ref1);
2547 return refs_may_alias_p_1 (&r1, ref2, tbaa_p);
2550 bool
2551 refs_may_alias_p (tree ref1, tree ref2, bool tbaa_p)
2553 ao_ref r1, r2;
2554 ao_ref_init (&r1, ref1);
2555 ao_ref_init (&r2, ref2);
2556 return refs_may_alias_p_1 (&r1, &r2, tbaa_p);
2559 /* Returns true if there is a anti-dependence for the STORE that
2560 executes after the LOAD. */
2562 bool
2563 refs_anti_dependent_p (tree load, tree store)
2565 ao_ref r1, r2;
2566 ao_ref_init (&r1, load);
2567 ao_ref_init (&r2, store);
2568 return refs_may_alias_p_1 (&r1, &r2, false);
2571 /* Returns true if there is a output dependence for the stores
2572 STORE1 and STORE2. */
2574 bool
2575 refs_output_dependent_p (tree store1, tree store2)
2577 ao_ref r1, r2;
2578 ao_ref_init (&r1, store1);
2579 ao_ref_init (&r2, store2);
2580 return refs_may_alias_p_1 (&r1, &r2, false);
2583 /* Returns true if and only if REF may alias any access stored in TT.
2584 IF TBAA_P is true, use TBAA oracle. */
2586 static bool
2587 modref_may_conflict (const gcall *stmt,
2588 modref_tree <alias_set_type> *tt, ao_ref *ref, bool tbaa_p)
2590 alias_set_type base_set, ref_set;
2591 bool global_memory_ok = false;
2593 if (tt->every_base)
2594 return true;
2596 if (!dbg_cnt (ipa_mod_ref))
2597 return true;
2599 base_set = ao_ref_base_alias_set (ref);
2601 ref_set = ao_ref_alias_set (ref);
2603 int num_tests = 0, max_tests = param_modref_max_tests;
2604 for (auto base_node : tt->bases)
2606 if (tbaa_p && flag_strict_aliasing)
2608 if (num_tests >= max_tests)
2609 return true;
2610 alias_stats.modref_tests++;
2611 if (!alias_sets_conflict_p (base_set, base_node->base))
2612 continue;
2613 num_tests++;
2616 if (base_node->every_ref)
2617 return true;
2619 for (auto ref_node : base_node->refs)
2621 /* Do not repeat same test as before. */
2622 if ((ref_set != base_set || base_node->base != ref_node->ref)
2623 && tbaa_p && flag_strict_aliasing)
2625 if (num_tests >= max_tests)
2626 return true;
2627 alias_stats.modref_tests++;
2628 if (!alias_sets_conflict_p (ref_set, ref_node->ref))
2629 continue;
2630 num_tests++;
2633 if (ref_node->every_access)
2634 return true;
2636 /* TBAA checks did not disambiguate, try individual accesses. */
2637 for (auto access_node : ref_node->accesses)
2639 if (num_tests >= max_tests)
2640 return true;
2642 if (access_node.parm_index == MODREF_GLOBAL_MEMORY_PARM)
2644 if (global_memory_ok)
2645 continue;
2646 if (ref_may_alias_global_p (ref, true))
2647 return true;
2648 global_memory_ok = true;
2649 num_tests++;
2650 continue;
2653 tree arg = access_node.get_call_arg (stmt);
2654 if (!arg)
2655 return true;
2657 alias_stats.modref_baseptr_tests++;
2659 if (integer_zerop (arg) && flag_delete_null_pointer_checks)
2660 continue;
2662 /* PTA oracle will be unhapy of arg is not an pointer. */
2663 if (!POINTER_TYPE_P (TREE_TYPE (arg)))
2664 return true;
2666 /* If we don't have base pointer, give up. */
2667 if (!ref->ref && !ref->base)
2668 continue;
2670 ao_ref ref2;
2671 if (access_node.get_ao_ref (stmt, &ref2))
2673 ref2.ref_alias_set = ref_node->ref;
2674 ref2.base_alias_set = base_node->base;
2675 if (refs_may_alias_p_1 (&ref2, ref, tbaa_p))
2676 return true;
2678 else if (ptr_deref_may_alias_ref_p_1 (arg, ref))
2679 return true;
2681 num_tests++;
2685 return false;
2688 /* Check if REF conflicts with call using "fn spec" attribute.
2689 If CLOBBER is true we are checking for writes, otherwise check loads.
2691 Return 0 if there are no conflicts (except for possible function call
2692 argument reads), 1 if there are conflicts and -1 if we can not decide by
2693 fn spec. */
2695 static int
2696 check_fnspec (gcall *call, ao_ref *ref, bool clobber)
2698 attr_fnspec fnspec = gimple_call_fnspec (call);
2699 if (fnspec.known_p ())
2701 if (clobber
2702 ? !fnspec.global_memory_written_p ()
2703 : !fnspec.global_memory_read_p ())
2705 for (unsigned int i = 0; i < gimple_call_num_args (call); i++)
2706 if (POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, i)))
2707 && (!fnspec.arg_specified_p (i)
2708 || (clobber ? fnspec.arg_maybe_written_p (i)
2709 : fnspec.arg_maybe_read_p (i))))
2711 ao_ref dref;
2712 tree size = NULL_TREE;
2713 unsigned int size_arg;
2715 if (!fnspec.arg_specified_p (i))
2717 else if (fnspec.arg_max_access_size_given_by_arg_p
2718 (i, &size_arg))
2719 size = gimple_call_arg (call, size_arg);
2720 else if (fnspec.arg_access_size_given_by_type_p (i))
2722 tree callee = gimple_call_fndecl (call);
2723 tree t = TYPE_ARG_TYPES (TREE_TYPE (callee));
2725 for (unsigned int p = 0; p < i; p++)
2726 t = TREE_CHAIN (t);
2727 size = TYPE_SIZE_UNIT (TREE_TYPE (TREE_VALUE (t)));
2729 ao_ref_init_from_ptr_and_size (&dref,
2730 gimple_call_arg (call, i),
2731 size);
2732 if (refs_may_alias_p_1 (&dref, ref, false))
2733 return 1;
2735 if (clobber
2736 && fnspec.errno_maybe_written_p ()
2737 && flag_errno_math
2738 && targetm.ref_may_alias_errno (ref))
2739 return 1;
2740 return 0;
2744 /* FIXME: we should handle barriers more consistently, but for now leave the
2745 check here. */
2746 if (gimple_call_builtin_p (call, BUILT_IN_NORMAL))
2747 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (call)))
2749 /* __sync_* builtins and some OpenMP builtins act as threading
2750 barriers. */
2751 #undef DEF_SYNC_BUILTIN
2752 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
2753 #include "sync-builtins.def"
2754 #undef DEF_SYNC_BUILTIN
2755 case BUILT_IN_GOMP_ATOMIC_START:
2756 case BUILT_IN_GOMP_ATOMIC_END:
2757 case BUILT_IN_GOMP_BARRIER:
2758 case BUILT_IN_GOMP_BARRIER_CANCEL:
2759 case BUILT_IN_GOMP_TASKWAIT:
2760 case BUILT_IN_GOMP_TASKGROUP_END:
2761 case BUILT_IN_GOMP_CRITICAL_START:
2762 case BUILT_IN_GOMP_CRITICAL_END:
2763 case BUILT_IN_GOMP_CRITICAL_NAME_START:
2764 case BUILT_IN_GOMP_CRITICAL_NAME_END:
2765 case BUILT_IN_GOMP_LOOP_END:
2766 case BUILT_IN_GOMP_LOOP_END_CANCEL:
2767 case BUILT_IN_GOMP_ORDERED_START:
2768 case BUILT_IN_GOMP_ORDERED_END:
2769 case BUILT_IN_GOMP_SECTIONS_END:
2770 case BUILT_IN_GOMP_SECTIONS_END_CANCEL:
2771 case BUILT_IN_GOMP_SINGLE_COPY_START:
2772 case BUILT_IN_GOMP_SINGLE_COPY_END:
2773 return 1;
2775 default:
2776 return -1;
2778 return -1;
2781 /* If the call CALL may use the memory reference REF return true,
2782 otherwise return false. */
2784 static bool
2785 ref_maybe_used_by_call_p_1 (gcall *call, ao_ref *ref, bool tbaa_p)
2787 tree base, callee;
2788 unsigned i;
2789 int flags = gimple_call_flags (call);
2791 if (flags & (ECF_CONST|ECF_NOVOPS))
2792 goto process_args;
2794 /* A call that is not without side-effects might involve volatile
2795 accesses and thus conflicts with all other volatile accesses. */
2796 if (ref->volatile_p)
2797 return true;
2799 if (gimple_call_internal_p (call))
2800 switch (gimple_call_internal_fn (call))
2802 case IFN_MASK_STORE:
2803 case IFN_SCATTER_STORE:
2804 case IFN_MASK_SCATTER_STORE:
2805 case IFN_LEN_STORE:
2806 return false;
2807 case IFN_MASK_STORE_LANES:
2808 goto process_args;
2809 case IFN_MASK_LOAD:
2810 case IFN_LEN_LOAD:
2811 case IFN_MASK_LOAD_LANES:
2813 ao_ref rhs_ref;
2814 tree lhs = gimple_call_lhs (call);
2815 if (lhs)
2817 ao_ref_init_from_ptr_and_size (&rhs_ref,
2818 gimple_call_arg (call, 0),
2819 TYPE_SIZE_UNIT (TREE_TYPE (lhs)));
2820 rhs_ref.ref_alias_set = rhs_ref.base_alias_set
2821 = tbaa_p ? get_deref_alias_set (TREE_TYPE
2822 (gimple_call_arg (call, 1))) : 0;
2823 return refs_may_alias_p_1 (ref, &rhs_ref, tbaa_p);
2825 break;
2827 default:;
2830 callee = gimple_call_fndecl (call);
2831 if (callee != NULL_TREE)
2833 struct cgraph_node *node = cgraph_node::get (callee);
2834 /* We can not safely optimize based on summary of calle if it does
2835 not always bind to current def: it is possible that memory load
2836 was optimized out earlier and the interposed variant may not be
2837 optimized this way. */
2838 if (node && node->binds_to_current_def_p ())
2840 modref_summary *summary = get_modref_function_summary (node);
2841 if (summary && !summary->calls_interposable)
2843 if (!modref_may_conflict (call, summary->loads, ref, tbaa_p))
2845 alias_stats.modref_use_no_alias++;
2846 if (dump_file && (dump_flags & TDF_DETAILS))
2848 fprintf (dump_file,
2849 "ipa-modref: call stmt ");
2850 print_gimple_stmt (dump_file, call, 0);
2851 fprintf (dump_file,
2852 "ipa-modref: call to %s does not use ",
2853 node->dump_name ());
2854 if (!ref->ref && ref->base)
2856 fprintf (dump_file, "base: ");
2857 print_generic_expr (dump_file, ref->base);
2859 else if (ref->ref)
2861 fprintf (dump_file, "ref: ");
2862 print_generic_expr (dump_file, ref->ref);
2864 fprintf (dump_file, " alias sets: %i->%i\n",
2865 ao_ref_base_alias_set (ref),
2866 ao_ref_alias_set (ref));
2868 goto process_args;
2870 alias_stats.modref_use_may_alias++;
2875 base = ao_ref_base (ref);
2876 if (!base)
2877 return true;
2879 /* If the reference is based on a decl that is not aliased the call
2880 cannot possibly use it. */
2881 if (DECL_P (base)
2882 && !may_be_aliased (base)
2883 /* But local statics can be used through recursion. */
2884 && !is_global_var (base))
2885 goto process_args;
2887 if (int res = check_fnspec (call, ref, false))
2889 if (res == 1)
2890 return true;
2892 else
2893 goto process_args;
2895 /* Check if base is a global static variable that is not read
2896 by the function. */
2897 if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
2899 struct cgraph_node *node = cgraph_node::get (callee);
2900 bitmap read;
2901 int id;
2903 /* FIXME: Callee can be an OMP builtin that does not have a call graph
2904 node yet. We should enforce that there are nodes for all decls in the
2905 IL and remove this check instead. */
2906 if (node
2907 && (id = ipa_reference_var_uid (base)) != -1
2908 && (read = ipa_reference_get_read_global (node))
2909 && !bitmap_bit_p (read, id))
2910 goto process_args;
2913 /* Check if the base variable is call-used. */
2914 if (DECL_P (base))
2916 if (pt_solution_includes (gimple_call_use_set (call), base))
2917 return true;
2919 else if ((TREE_CODE (base) == MEM_REF
2920 || TREE_CODE (base) == TARGET_MEM_REF)
2921 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
2923 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
2924 if (!pi)
2925 return true;
2927 if (pt_solutions_intersect (gimple_call_use_set (call), &pi->pt))
2928 return true;
2930 else
2931 return true;
2933 /* Inspect call arguments for passed-by-value aliases. */
2934 process_args:
2935 for (i = 0; i < gimple_call_num_args (call); ++i)
2937 tree op = gimple_call_arg (call, i);
2938 int flags = gimple_call_arg_flags (call, i);
2940 if (flags & (EAF_UNUSED | EAF_NO_DIRECT_READ))
2941 continue;
2943 if (TREE_CODE (op) == WITH_SIZE_EXPR)
2944 op = TREE_OPERAND (op, 0);
2946 if (TREE_CODE (op) != SSA_NAME
2947 && !is_gimple_min_invariant (op))
2949 ao_ref r;
2950 ao_ref_init (&r, op);
2951 if (refs_may_alias_p_1 (&r, ref, tbaa_p))
2952 return true;
2956 return false;
2959 static bool
2960 ref_maybe_used_by_call_p (gcall *call, ao_ref *ref, bool tbaa_p)
2962 bool res;
2963 res = ref_maybe_used_by_call_p_1 (call, ref, tbaa_p);
2964 if (res)
2965 ++alias_stats.ref_maybe_used_by_call_p_may_alias;
2966 else
2967 ++alias_stats.ref_maybe_used_by_call_p_no_alias;
2968 return res;
2972 /* If the statement STMT may use the memory reference REF return
2973 true, otherwise return false. */
2975 bool
2976 ref_maybe_used_by_stmt_p (gimple *stmt, ao_ref *ref, bool tbaa_p)
2978 if (is_gimple_assign (stmt))
2980 tree rhs;
2982 /* All memory assign statements are single. */
2983 if (!gimple_assign_single_p (stmt))
2984 return false;
2986 rhs = gimple_assign_rhs1 (stmt);
2987 if (is_gimple_reg (rhs)
2988 || is_gimple_min_invariant (rhs)
2989 || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
2990 return false;
2992 return refs_may_alias_p (rhs, ref, tbaa_p);
2994 else if (is_gimple_call (stmt))
2995 return ref_maybe_used_by_call_p (as_a <gcall *> (stmt), ref, tbaa_p);
2996 else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
2998 tree retval = gimple_return_retval (return_stmt);
2999 if (retval
3000 && TREE_CODE (retval) != SSA_NAME
3001 && !is_gimple_min_invariant (retval)
3002 && refs_may_alias_p (retval, ref, tbaa_p))
3003 return true;
3004 /* If ref escapes the function then the return acts as a use. */
3005 tree base = ao_ref_base (ref);
3006 if (!base)
3008 else if (DECL_P (base))
3009 return is_global_var (base);
3010 else if (TREE_CODE (base) == MEM_REF
3011 || TREE_CODE (base) == TARGET_MEM_REF)
3012 return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0), false);
3013 return false;
3016 return true;
3019 bool
3020 ref_maybe_used_by_stmt_p (gimple *stmt, tree ref, bool tbaa_p)
3022 ao_ref r;
3023 ao_ref_init (&r, ref);
3024 return ref_maybe_used_by_stmt_p (stmt, &r, tbaa_p);
3027 /* If the call in statement CALL may clobber the memory reference REF
3028 return true, otherwise return false. */
3030 bool
3031 call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref, bool tbaa_p)
3033 tree base;
3034 tree callee;
3036 /* If the call is pure or const it cannot clobber anything. */
3037 if (gimple_call_flags (call)
3038 & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
3039 return false;
3040 if (gimple_call_internal_p (call))
3041 switch (auto fn = gimple_call_internal_fn (call))
3043 /* Treat these internal calls like ECF_PURE for aliasing,
3044 they don't write to any memory the program should care about.
3045 They have important other side-effects, and read memory,
3046 so can't be ECF_NOVOPS. */
3047 case IFN_UBSAN_NULL:
3048 case IFN_UBSAN_BOUNDS:
3049 case IFN_UBSAN_VPTR:
3050 case IFN_UBSAN_OBJECT_SIZE:
3051 case IFN_UBSAN_PTR:
3052 case IFN_ASAN_CHECK:
3053 return false;
3054 case IFN_MASK_STORE:
3055 case IFN_LEN_STORE:
3056 case IFN_MASK_STORE_LANES:
3058 tree rhs = gimple_call_arg (call,
3059 internal_fn_stored_value_index (fn));
3060 ao_ref lhs_ref;
3061 ao_ref_init_from_ptr_and_size (&lhs_ref, gimple_call_arg (call, 0),
3062 TYPE_SIZE_UNIT (TREE_TYPE (rhs)));
3063 lhs_ref.ref_alias_set = lhs_ref.base_alias_set
3064 = tbaa_p ? get_deref_alias_set
3065 (TREE_TYPE (gimple_call_arg (call, 1))) : 0;
3066 return refs_may_alias_p_1 (ref, &lhs_ref, tbaa_p);
3068 default:
3069 break;
3072 callee = gimple_call_fndecl (call);
3074 if (callee != NULL_TREE && !ref->volatile_p)
3076 struct cgraph_node *node = cgraph_node::get (callee);
3077 if (node)
3079 modref_summary *summary = get_modref_function_summary (node);
3080 if (summary)
3082 if (!modref_may_conflict (call, summary->stores, ref, tbaa_p)
3083 && (!summary->writes_errno
3084 || !targetm.ref_may_alias_errno (ref)))
3086 alias_stats.modref_clobber_no_alias++;
3087 if (dump_file && (dump_flags & TDF_DETAILS))
3089 fprintf (dump_file,
3090 "ipa-modref: call stmt ");
3091 print_gimple_stmt (dump_file, call, 0);
3092 fprintf (dump_file,
3093 "ipa-modref: call to %s does not clobber ",
3094 node->dump_name ());
3095 if (!ref->ref && ref->base)
3097 fprintf (dump_file, "base: ");
3098 print_generic_expr (dump_file, ref->base);
3100 else if (ref->ref)
3102 fprintf (dump_file, "ref: ");
3103 print_generic_expr (dump_file, ref->ref);
3105 fprintf (dump_file, " alias sets: %i->%i\n",
3106 ao_ref_base_alias_set (ref),
3107 ao_ref_alias_set (ref));
3109 return false;
3111 alias_stats.modref_clobber_may_alias++;
3116 base = ao_ref_base (ref);
3117 if (!base)
3118 return true;
3120 if (TREE_CODE (base) == SSA_NAME
3121 || CONSTANT_CLASS_P (base))
3122 return false;
3124 /* A call that is not without side-effects might involve volatile
3125 accesses and thus conflicts with all other volatile accesses. */
3126 if (ref->volatile_p)
3127 return true;
3129 /* If the reference is based on a decl that is not aliased the call
3130 cannot possibly clobber it. */
3131 if (DECL_P (base)
3132 && !may_be_aliased (base)
3133 /* But local non-readonly statics can be modified through recursion
3134 or the call may implement a threading barrier which we must
3135 treat as may-def. */
3136 && (TREE_READONLY (base)
3137 || !is_global_var (base)))
3138 return false;
3140 /* If the reference is based on a pointer that points to memory
3141 that may not be written to then the call cannot possibly clobber it. */
3142 if ((TREE_CODE (base) == MEM_REF
3143 || TREE_CODE (base) == TARGET_MEM_REF)
3144 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
3145 && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base, 0)))
3146 return false;
3148 if (int res = check_fnspec (call, ref, true))
3150 if (res == 1)
3151 return true;
3153 else
3154 return false;
3156 /* Check if base is a global static variable that is not written
3157 by the function. */
3158 if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
3160 struct cgraph_node *node = cgraph_node::get (callee);
3161 bitmap written;
3162 int id;
3164 if (node
3165 && (id = ipa_reference_var_uid (base)) != -1
3166 && (written = ipa_reference_get_written_global (node))
3167 && !bitmap_bit_p (written, id))
3168 return false;
3171 /* Check if the base variable is call-clobbered. */
3172 if (DECL_P (base))
3173 return pt_solution_includes (gimple_call_clobber_set (call), base);
3174 else if ((TREE_CODE (base) == MEM_REF
3175 || TREE_CODE (base) == TARGET_MEM_REF)
3176 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
3178 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
3179 if (!pi)
3180 return true;
3182 return pt_solutions_intersect (gimple_call_clobber_set (call), &pi->pt);
3185 return true;
3188 /* If the call in statement CALL may clobber the memory reference REF
3189 return true, otherwise return false. */
3191 bool
3192 call_may_clobber_ref_p (gcall *call, tree ref, bool tbaa_p)
3194 bool res;
3195 ao_ref r;
3196 ao_ref_init (&r, ref);
3197 res = call_may_clobber_ref_p_1 (call, &r, tbaa_p);
3198 if (res)
3199 ++alias_stats.call_may_clobber_ref_p_may_alias;
3200 else
3201 ++alias_stats.call_may_clobber_ref_p_no_alias;
3202 return res;
3206 /* If the statement STMT may clobber the memory reference REF return true,
3207 otherwise return false. */
3209 bool
3210 stmt_may_clobber_ref_p_1 (gimple *stmt, ao_ref *ref, bool tbaa_p)
3212 if (is_gimple_call (stmt))
3214 tree lhs = gimple_call_lhs (stmt);
3215 if (lhs
3216 && TREE_CODE (lhs) != SSA_NAME)
3218 ao_ref r;
3219 ao_ref_init (&r, lhs);
3220 if (refs_may_alias_p_1 (ref, &r, tbaa_p))
3221 return true;
3224 return call_may_clobber_ref_p_1 (as_a <gcall *> (stmt), ref, tbaa_p);
3226 else if (gimple_assign_single_p (stmt))
3228 tree lhs = gimple_assign_lhs (stmt);
3229 if (TREE_CODE (lhs) != SSA_NAME)
3231 ao_ref r;
3232 ao_ref_init (&r, lhs);
3233 return refs_may_alias_p_1 (ref, &r, tbaa_p);
3236 else if (gimple_code (stmt) == GIMPLE_ASM)
3237 return true;
3239 return false;
3242 bool
3243 stmt_may_clobber_ref_p (gimple *stmt, tree ref, bool tbaa_p)
3245 ao_ref r;
3246 ao_ref_init (&r, ref);
3247 return stmt_may_clobber_ref_p_1 (stmt, &r, tbaa_p);
3250 /* Return true if store1 and store2 described by corresponding tuples
3251 <BASE, OFFSET, SIZE, MAX_SIZE> have the same size and store to the same
3252 address. */
3254 static bool
3255 same_addr_size_stores_p (tree base1, poly_int64 offset1, poly_int64 size1,
3256 poly_int64 max_size1,
3257 tree base2, poly_int64 offset2, poly_int64 size2,
3258 poly_int64 max_size2)
3260 /* Offsets need to be 0. */
3261 if (maybe_ne (offset1, 0)
3262 || maybe_ne (offset2, 0))
3263 return false;
3265 bool base1_obj_p = SSA_VAR_P (base1);
3266 bool base2_obj_p = SSA_VAR_P (base2);
3268 /* We need one object. */
3269 if (base1_obj_p == base2_obj_p)
3270 return false;
3271 tree obj = base1_obj_p ? base1 : base2;
3273 /* And we need one MEM_REF. */
3274 bool base1_memref_p = TREE_CODE (base1) == MEM_REF;
3275 bool base2_memref_p = TREE_CODE (base2) == MEM_REF;
3276 if (base1_memref_p == base2_memref_p)
3277 return false;
3278 tree memref = base1_memref_p ? base1 : base2;
3280 /* Sizes need to be valid. */
3281 if (!known_size_p (max_size1)
3282 || !known_size_p (max_size2)
3283 || !known_size_p (size1)
3284 || !known_size_p (size2))
3285 return false;
3287 /* Max_size needs to match size. */
3288 if (maybe_ne (max_size1, size1)
3289 || maybe_ne (max_size2, size2))
3290 return false;
3292 /* Sizes need to match. */
3293 if (maybe_ne (size1, size2))
3294 return false;
3297 /* Check that memref is a store to pointer with singleton points-to info. */
3298 if (!integer_zerop (TREE_OPERAND (memref, 1)))
3299 return false;
3300 tree ptr = TREE_OPERAND (memref, 0);
3301 if (TREE_CODE (ptr) != SSA_NAME)
3302 return false;
3303 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
3304 unsigned int pt_uid;
3305 if (pi == NULL
3306 || !pt_solution_singleton_or_null_p (&pi->pt, &pt_uid))
3307 return false;
3309 /* Be conservative with non-call exceptions when the address might
3310 be NULL. */
3311 if (cfun->can_throw_non_call_exceptions && pi->pt.null)
3312 return false;
3314 /* Check that ptr points relative to obj. */
3315 unsigned int obj_uid = DECL_PT_UID (obj);
3316 if (obj_uid != pt_uid)
3317 return false;
3319 /* Check that the object size is the same as the store size. That ensures us
3320 that ptr points to the start of obj. */
3321 return (DECL_SIZE (obj)
3322 && poly_int_tree_p (DECL_SIZE (obj))
3323 && known_eq (wi::to_poly_offset (DECL_SIZE (obj)), size1));
3326 /* Return true if REF is killed by an store described by
3327 BASE, OFFSET, SIZE and MAX_SIZE. */
3329 static bool
3330 store_kills_ref_p (tree base, poly_int64 offset, poly_int64 size,
3331 poly_int64 max_size, ao_ref *ref)
3333 poly_int64 ref_offset = ref->offset;
3334 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
3335 so base == ref->base does not always hold. */
3336 if (base != ref->base)
3338 /* Try using points-to info. */
3339 if (same_addr_size_stores_p (base, offset, size, max_size, ref->base,
3340 ref->offset, ref->size, ref->max_size))
3341 return true;
3343 /* If both base and ref->base are MEM_REFs, only compare the
3344 first operand, and if the second operand isn't equal constant,
3345 try to add the offsets into offset and ref_offset. */
3346 if (TREE_CODE (base) == MEM_REF && TREE_CODE (ref->base) == MEM_REF
3347 && TREE_OPERAND (base, 0) == TREE_OPERAND (ref->base, 0))
3349 if (!tree_int_cst_equal (TREE_OPERAND (base, 1),
3350 TREE_OPERAND (ref->base, 1)))
3352 poly_offset_int off1 = mem_ref_offset (base);
3353 off1 <<= LOG2_BITS_PER_UNIT;
3354 off1 += offset;
3355 poly_offset_int off2 = mem_ref_offset (ref->base);
3356 off2 <<= LOG2_BITS_PER_UNIT;
3357 off2 += ref_offset;
3358 if (!off1.to_shwi (&offset) || !off2.to_shwi (&ref_offset))
3359 size = -1;
3362 else
3363 size = -1;
3365 /* For a must-alias check we need to be able to constrain
3366 the access properly. */
3367 return (known_eq (size, max_size)
3368 && known_subrange_p (ref_offset, ref->max_size, offset, size));
3371 /* If STMT kills the memory reference REF return true, otherwise
3372 return false. */
3374 bool
3375 stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
3377 if (!ao_ref_base (ref))
3378 return false;
3380 if (gimple_has_lhs (stmt)
3381 && TREE_CODE (gimple_get_lhs (stmt)) != SSA_NAME
3382 /* The assignment is not necessarily carried out if it can throw
3383 and we can catch it in the current function where we could inspect
3384 the previous value. Similarly if the function can throw externally
3385 and the ref does not die on the function return.
3386 ??? We only need to care about the RHS throwing. For aggregate
3387 assignments or similar calls and non-call exceptions the LHS
3388 might throw as well.
3389 ??? We also should care about possible longjmp, but since we
3390 do not understand that longjmp is not using global memory we will
3391 not consider a kill here since the function call will be considered
3392 as possibly using REF. */
3393 && !stmt_can_throw_internal (cfun, stmt)
3394 && (!stmt_can_throw_external (cfun, stmt)
3395 || !ref_may_alias_global_p (ref, false)))
3397 tree lhs = gimple_get_lhs (stmt);
3398 /* If LHS is literally a base of the access we are done. */
3399 if (ref->ref)
3401 tree base = ref->ref;
3402 tree innermost_dropped_array_ref = NULL_TREE;
3403 if (handled_component_p (base))
3405 tree saved_lhs0 = NULL_TREE;
3406 if (handled_component_p (lhs))
3408 saved_lhs0 = TREE_OPERAND (lhs, 0);
3409 TREE_OPERAND (lhs, 0) = integer_zero_node;
3413 /* Just compare the outermost handled component, if
3414 they are equal we have found a possible common
3415 base. */
3416 tree saved_base0 = TREE_OPERAND (base, 0);
3417 TREE_OPERAND (base, 0) = integer_zero_node;
3418 bool res = operand_equal_p (lhs, base, 0);
3419 TREE_OPERAND (base, 0) = saved_base0;
3420 if (res)
3421 break;
3422 /* Remember if we drop an array-ref that we need to
3423 double-check not being at struct end. */
3424 if (TREE_CODE (base) == ARRAY_REF
3425 || TREE_CODE (base) == ARRAY_RANGE_REF)
3426 innermost_dropped_array_ref = base;
3427 /* Otherwise drop handled components of the access. */
3428 base = saved_base0;
3430 while (handled_component_p (base));
3431 if (saved_lhs0)
3432 TREE_OPERAND (lhs, 0) = saved_lhs0;
3434 /* Finally check if the lhs has the same address and size as the
3435 base candidate of the access. Watch out if we have dropped
3436 an array-ref that might have flexible size, this means ref->ref
3437 may be outside of the TYPE_SIZE of its base. */
3438 if ((! innermost_dropped_array_ref
3439 || ! array_ref_flexible_size_p (innermost_dropped_array_ref))
3440 && (lhs == base
3441 || (((TYPE_SIZE (TREE_TYPE (lhs))
3442 == TYPE_SIZE (TREE_TYPE (base)))
3443 || (TYPE_SIZE (TREE_TYPE (lhs))
3444 && TYPE_SIZE (TREE_TYPE (base))
3445 && operand_equal_p (TYPE_SIZE (TREE_TYPE (lhs)),
3446 TYPE_SIZE (TREE_TYPE (base)),
3447 0)))
3448 && operand_equal_p (lhs, base,
3449 OEP_ADDRESS_OF
3450 | OEP_MATCH_SIDE_EFFECTS))))
3452 ++alias_stats.stmt_kills_ref_p_yes;
3453 return true;
3457 /* Now look for non-literal equal bases with the restriction of
3458 handling constant offset and size. */
3459 /* For a must-alias check we need to be able to constrain
3460 the access properly. */
3461 if (!ref->max_size_known_p ())
3463 ++alias_stats.stmt_kills_ref_p_no;
3464 return false;
3466 poly_int64 size, offset, max_size;
3467 bool reverse;
3468 tree base = get_ref_base_and_extent (lhs, &offset, &size, &max_size,
3469 &reverse);
3470 if (store_kills_ref_p (base, offset, size, max_size, ref))
3472 ++alias_stats.stmt_kills_ref_p_yes;
3473 return true;
3477 if (is_gimple_call (stmt))
3479 tree callee = gimple_call_fndecl (stmt);
3480 struct cgraph_node *node;
3481 modref_summary *summary;
3483 /* Try to disambiguate using modref summary. Modref records a vector
3484 of stores with known offsets relative to function parameters that must
3485 happen every execution of function. Find if we have a matching
3486 store and verify that function can not use the value. */
3487 if (callee != NULL_TREE
3488 && (node = cgraph_node::get (callee)) != NULL
3489 && node->binds_to_current_def_p ()
3490 && (summary = get_modref_function_summary (node)) != NULL
3491 && summary->kills.length ()
3492 /* Check that we can not trap while evaulating function
3493 parameters. This check is overly conservative. */
3494 && (!cfun->can_throw_non_call_exceptions
3495 || (!stmt_can_throw_internal (cfun, stmt)
3496 && (!stmt_can_throw_external (cfun, stmt)
3497 || !ref_may_alias_global_p (ref, false)))))
3499 for (auto kill : summary->kills)
3501 ao_ref dref;
3503 /* We only can do useful compares if we know the access range
3504 precisely. */
3505 if (!kill.get_ao_ref (as_a <gcall *> (stmt), &dref))
3506 continue;
3507 if (store_kills_ref_p (ao_ref_base (&dref), dref.offset,
3508 dref.size, dref.max_size, ref))
3510 /* For store to be killed it needs to not be used
3511 earlier. */
3512 if (ref_maybe_used_by_call_p_1 (as_a <gcall *> (stmt), ref,
3513 true)
3514 || !dbg_cnt (ipa_mod_ref))
3515 break;
3516 if (dump_file && (dump_flags & TDF_DETAILS))
3518 fprintf (dump_file,
3519 "ipa-modref: call stmt ");
3520 print_gimple_stmt (dump_file, stmt, 0);
3521 fprintf (dump_file,
3522 "ipa-modref: call to %s kills ",
3523 node->dump_name ());
3524 print_generic_expr (dump_file, ref->base);
3525 fprintf (dump_file, "\n");
3527 ++alias_stats.modref_kill_yes;
3528 return true;
3531 ++alias_stats.modref_kill_no;
3533 if (callee != NULL_TREE
3534 && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
3535 switch (DECL_FUNCTION_CODE (callee))
3537 case BUILT_IN_FREE:
3539 tree ptr = gimple_call_arg (stmt, 0);
3540 tree base = ao_ref_base (ref);
3541 if (base && TREE_CODE (base) == MEM_REF
3542 && TREE_OPERAND (base, 0) == ptr)
3544 ++alias_stats.stmt_kills_ref_p_yes;
3545 return true;
3547 break;
3550 case BUILT_IN_MEMCPY:
3551 case BUILT_IN_MEMPCPY:
3552 case BUILT_IN_MEMMOVE:
3553 case BUILT_IN_MEMSET:
3554 case BUILT_IN_MEMCPY_CHK:
3555 case BUILT_IN_MEMPCPY_CHK:
3556 case BUILT_IN_MEMMOVE_CHK:
3557 case BUILT_IN_MEMSET_CHK:
3558 case BUILT_IN_STRNCPY:
3559 case BUILT_IN_STPNCPY:
3560 case BUILT_IN_CALLOC:
3562 /* For a must-alias check we need to be able to constrain
3563 the access properly. */
3564 if (!ref->max_size_known_p ())
3566 ++alias_stats.stmt_kills_ref_p_no;
3567 return false;
3569 tree dest;
3570 tree len;
3572 /* In execution order a calloc call will never kill
3573 anything. However, DSE will (ab)use this interface
3574 to ask if a calloc call writes the same memory locations
3575 as a later assignment, memset, etc. So handle calloc
3576 in the expected way. */
3577 if (DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC)
3579 tree arg0 = gimple_call_arg (stmt, 0);
3580 tree arg1 = gimple_call_arg (stmt, 1);
3581 if (TREE_CODE (arg0) != INTEGER_CST
3582 || TREE_CODE (arg1) != INTEGER_CST)
3584 ++alias_stats.stmt_kills_ref_p_no;
3585 return false;
3588 dest = gimple_call_lhs (stmt);
3589 if (!dest)
3591 ++alias_stats.stmt_kills_ref_p_no;
3592 return false;
3594 len = fold_build2 (MULT_EXPR, TREE_TYPE (arg0), arg0, arg1);
3596 else
3598 dest = gimple_call_arg (stmt, 0);
3599 len = gimple_call_arg (stmt, 2);
3601 if (!poly_int_tree_p (len))
3602 return false;
3603 ao_ref dref;
3604 ao_ref_init_from_ptr_and_size (&dref, dest, len);
3605 if (store_kills_ref_p (ao_ref_base (&dref), dref.offset,
3606 dref.size, dref.max_size, ref))
3608 ++alias_stats.stmt_kills_ref_p_yes;
3609 return true;
3611 break;
3614 case BUILT_IN_VA_END:
3616 tree ptr = gimple_call_arg (stmt, 0);
3617 if (TREE_CODE (ptr) == ADDR_EXPR)
3619 tree base = ao_ref_base (ref);
3620 if (TREE_OPERAND (ptr, 0) == base)
3622 ++alias_stats.stmt_kills_ref_p_yes;
3623 return true;
3626 break;
3629 default:;
3632 ++alias_stats.stmt_kills_ref_p_no;
3633 return false;
3636 bool
3637 stmt_kills_ref_p (gimple *stmt, tree ref)
3639 ao_ref r;
3640 ao_ref_init (&r, ref);
3641 return stmt_kills_ref_p (stmt, &r);
3645 /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
3646 TARGET or a statement clobbering the memory reference REF in which
3647 case false is returned. The walk starts with VUSE, one argument of PHI. */
3649 static bool
3650 maybe_skip_until (gimple *phi, tree &target, basic_block target_bb,
3651 ao_ref *ref, tree vuse, bool tbaa_p, unsigned int &limit,
3652 bitmap *visited, bool abort_on_visited,
3653 void *(*translate)(ao_ref *, tree, void *, translate_flags *),
3654 translate_flags disambiguate_only,
3655 void *data)
3657 basic_block bb = gimple_bb (phi);
3659 if (!*visited)
3661 *visited = BITMAP_ALLOC (NULL);
3662 bitmap_tree_view (*visited);
3665 bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
3667 /* Walk until we hit the target. */
3668 while (vuse != target)
3670 gimple *def_stmt = SSA_NAME_DEF_STMT (vuse);
3671 /* If we are searching for the target VUSE by walking up to
3672 TARGET_BB dominating the original PHI we are finished once
3673 we reach a default def or a definition in a block dominating
3674 that block. Update TARGET and return. */
3675 if (!target
3676 && (gimple_nop_p (def_stmt)
3677 || dominated_by_p (CDI_DOMINATORS,
3678 target_bb, gimple_bb (def_stmt))))
3680 target = vuse;
3681 return true;
3684 /* Recurse for PHI nodes. */
3685 if (gimple_code (def_stmt) == GIMPLE_PHI)
3687 /* An already visited PHI node ends the walk successfully. */
3688 if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (def_stmt))))
3689 return !abort_on_visited;
3690 vuse = get_continuation_for_phi (def_stmt, ref, tbaa_p, limit,
3691 visited, abort_on_visited,
3692 translate, data, disambiguate_only);
3693 if (!vuse)
3694 return false;
3695 continue;
3697 else if (gimple_nop_p (def_stmt))
3698 return false;
3699 else
3701 /* A clobbering statement or the end of the IL ends it failing. */
3702 if ((int)limit <= 0)
3703 return false;
3704 --limit;
3705 if (stmt_may_clobber_ref_p_1 (def_stmt, ref, tbaa_p))
3707 translate_flags tf = disambiguate_only;
3708 if (translate
3709 && (*translate) (ref, vuse, data, &tf) == NULL)
3711 else
3712 return false;
3715 /* If we reach a new basic-block see if we already skipped it
3716 in a previous walk that ended successfully. */
3717 if (gimple_bb (def_stmt) != bb)
3719 if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (vuse)))
3720 return !abort_on_visited;
3721 bb = gimple_bb (def_stmt);
3723 vuse = gimple_vuse (def_stmt);
3725 return true;
3729 /* Starting from a PHI node for the virtual operand of the memory reference
3730 REF find a continuation virtual operand that allows to continue walking
3731 statements dominating PHI skipping only statements that cannot possibly
3732 clobber REF. Decrements LIMIT for each alias disambiguation done
3733 and aborts the walk, returning NULL_TREE if it reaches zero.
3734 Returns NULL_TREE if no suitable virtual operand can be found. */
3736 tree
3737 get_continuation_for_phi (gimple *phi, ao_ref *ref, bool tbaa_p,
3738 unsigned int &limit, bitmap *visited,
3739 bool abort_on_visited,
3740 void *(*translate)(ao_ref *, tree, void *,
3741 translate_flags *),
3742 void *data,
3743 translate_flags disambiguate_only)
3745 unsigned nargs = gimple_phi_num_args (phi);
3747 /* Through a single-argument PHI we can simply look through. */
3748 if (nargs == 1)
3749 return PHI_ARG_DEF (phi, 0);
3751 /* For two or more arguments try to pairwise skip non-aliasing code
3752 until we hit the phi argument definition that dominates the other one. */
3753 basic_block phi_bb = gimple_bb (phi);
3754 tree arg0, arg1;
3755 unsigned i;
3757 /* Find a candidate for the virtual operand which definition
3758 dominates those of all others. */
3759 /* First look if any of the args themselves satisfy this. */
3760 for (i = 0; i < nargs; ++i)
3762 arg0 = PHI_ARG_DEF (phi, i);
3763 if (SSA_NAME_IS_DEFAULT_DEF (arg0))
3764 break;
3765 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (arg0));
3766 if (def_bb != phi_bb
3767 && dominated_by_p (CDI_DOMINATORS, phi_bb, def_bb))
3768 break;
3769 arg0 = NULL_TREE;
3771 /* If not, look if we can reach such candidate by walking defs
3772 until we hit the immediate dominator. maybe_skip_until will
3773 do that for us. */
3774 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
3776 /* Then check against the (to be) found candidate. */
3777 for (i = 0; i < nargs; ++i)
3779 arg1 = PHI_ARG_DEF (phi, i);
3780 if (arg1 == arg0)
3782 else if (! maybe_skip_until (phi, arg0, dom, ref, arg1, tbaa_p,
3783 limit, visited,
3784 abort_on_visited,
3785 translate,
3786 /* Do not valueize when walking over
3787 backedges. */
3788 dominated_by_p
3789 (CDI_DOMINATORS,
3790 gimple_bb (SSA_NAME_DEF_STMT (arg1)),
3791 phi_bb)
3792 ? TR_DISAMBIGUATE
3793 : disambiguate_only, data))
3794 return NULL_TREE;
3797 return arg0;
3800 /* Based on the memory reference REF and its virtual use VUSE call
3801 WALKER for each virtual use that is equivalent to VUSE, including VUSE
3802 itself. That is, for each virtual use for which its defining statement
3803 does not clobber REF.
3805 WALKER is called with REF, the current virtual use and DATA. If
3806 WALKER returns non-NULL the walk stops and its result is returned.
3807 At the end of a non-successful walk NULL is returned.
3809 TRANSLATE if non-NULL is called with a pointer to REF, the virtual
3810 use which definition is a statement that may clobber REF and DATA.
3811 If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
3812 If TRANSLATE returns non-NULL the walk stops and its result is returned.
3813 If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
3814 to adjust REF and *DATA to make that valid.
3816 VALUEIZE if non-NULL is called with the next VUSE that is considered
3817 and return value is substituted for that. This can be used to
3818 implement optimistic value-numbering for example. Note that the
3819 VUSE argument is assumed to be valueized already.
3821 LIMIT specifies the number of alias queries we are allowed to do,
3822 the walk stops when it reaches zero and NULL is returned. LIMIT
3823 is decremented by the number of alias queries (plus adjustments
3824 done by the callbacks) upon return.
3826 TODO: Cache the vector of equivalent vuses per ref, vuse pair. */
3828 void *
3829 walk_non_aliased_vuses (ao_ref *ref, tree vuse, bool tbaa_p,
3830 void *(*walker)(ao_ref *, tree, void *),
3831 void *(*translate)(ao_ref *, tree, void *,
3832 translate_flags *),
3833 tree (*valueize)(tree),
3834 unsigned &limit, void *data)
3836 bitmap visited = NULL;
3837 void *res;
3838 bool translated = false;
3840 timevar_push (TV_ALIAS_STMT_WALK);
3844 gimple *def_stmt;
3846 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
3847 res = (*walker) (ref, vuse, data);
3848 /* Abort walk. */
3849 if (res == (void *)-1)
3851 res = NULL;
3852 break;
3854 /* Lookup succeeded. */
3855 else if (res != NULL)
3856 break;
3858 if (valueize)
3860 vuse = valueize (vuse);
3861 if (!vuse)
3863 res = NULL;
3864 break;
3867 def_stmt = SSA_NAME_DEF_STMT (vuse);
3868 if (gimple_nop_p (def_stmt))
3869 break;
3870 else if (gimple_code (def_stmt) == GIMPLE_PHI)
3871 vuse = get_continuation_for_phi (def_stmt, ref, tbaa_p, limit,
3872 &visited, translated, translate, data);
3873 else
3875 if ((int)limit <= 0)
3877 res = NULL;
3878 break;
3880 --limit;
3881 if (stmt_may_clobber_ref_p_1 (def_stmt, ref, tbaa_p))
3883 if (!translate)
3884 break;
3885 translate_flags disambiguate_only = TR_TRANSLATE;
3886 res = (*translate) (ref, vuse, data, &disambiguate_only);
3887 /* Failed lookup and translation. */
3888 if (res == (void *)-1)
3890 res = NULL;
3891 break;
3893 /* Lookup succeeded. */
3894 else if (res != NULL)
3895 break;
3896 /* Translation succeeded, continue walking. */
3897 translated = translated || disambiguate_only == TR_TRANSLATE;
3899 vuse = gimple_vuse (def_stmt);
3902 while (vuse);
3904 if (visited)
3905 BITMAP_FREE (visited);
3907 timevar_pop (TV_ALIAS_STMT_WALK);
3909 return res;
3913 /* Based on the memory reference REF call WALKER for each vdef whose
3914 defining statement may clobber REF, starting with VDEF. If REF
3915 is NULL_TREE, each defining statement is visited.
3917 WALKER is called with REF, the current vdef and DATA. If WALKER
3918 returns true the walk is stopped, otherwise it continues.
3920 If function entry is reached, FUNCTION_ENTRY_REACHED is set to true.
3921 The pointer may be NULL and then we do not track this information.
3923 At PHI nodes walk_aliased_vdefs forks into one walk for each
3924 PHI argument (but only one walk continues at merge points), the
3925 return value is true if any of the walks was successful.
3927 The function returns the number of statements walked or -1 if
3928 LIMIT stmts were walked and the walk was aborted at this point.
3929 If LIMIT is zero the walk is not aborted. */
3931 static int
3932 walk_aliased_vdefs_1 (ao_ref *ref, tree vdef,
3933 bool (*walker)(ao_ref *, tree, void *), void *data,
3934 bitmap *visited, unsigned int cnt,
3935 bool *function_entry_reached, unsigned limit)
3939 gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
3941 if (*visited
3942 && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
3943 return cnt;
3945 if (gimple_nop_p (def_stmt))
3947 if (function_entry_reached)
3948 *function_entry_reached = true;
3949 return cnt;
3951 else if (gimple_code (def_stmt) == GIMPLE_PHI)
3953 unsigned i;
3954 if (!*visited)
3956 *visited = BITMAP_ALLOC (NULL);
3957 bitmap_tree_view (*visited);
3959 for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
3961 int res = walk_aliased_vdefs_1 (ref,
3962 gimple_phi_arg_def (def_stmt, i),
3963 walker, data, visited, cnt,
3964 function_entry_reached, limit);
3965 if (res == -1)
3966 return -1;
3967 cnt = res;
3969 return cnt;
3972 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
3973 cnt++;
3974 if (cnt == limit)
3975 return -1;
3976 if ((!ref
3977 || stmt_may_clobber_ref_p_1 (def_stmt, ref))
3978 && (*walker) (ref, vdef, data))
3979 return cnt;
3981 vdef = gimple_vuse (def_stmt);
3983 while (1);
3987 walk_aliased_vdefs (ao_ref *ref, tree vdef,
3988 bool (*walker)(ao_ref *, tree, void *), void *data,
3989 bitmap *visited,
3990 bool *function_entry_reached, unsigned int limit)
3992 bitmap local_visited = NULL;
3993 int ret;
3995 timevar_push (TV_ALIAS_STMT_WALK);
3997 if (function_entry_reached)
3998 *function_entry_reached = false;
4000 ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
4001 visited ? visited : &local_visited, 0,
4002 function_entry_reached, limit);
4003 if (local_visited)
4004 BITMAP_FREE (local_visited);
4006 timevar_pop (TV_ALIAS_STMT_WALK);
4008 return ret;
4011 /* Verify validity of the fnspec string.
4012 See attr-fnspec.h for details. */
4014 void
4015 attr_fnspec::verify ()
4017 bool err = false;
4018 if (!len)
4019 return;
4021 /* Check return value specifier. */
4022 if (len < return_desc_size)
4023 err = true;
4024 else if ((len - return_desc_size) % arg_desc_size)
4025 err = true;
4026 else if ((str[0] < '1' || str[0] > '4')
4027 && str[0] != '.' && str[0] != 'm')
4028 err = true;
4030 switch (str[1])
4032 case ' ':
4033 case 'p':
4034 case 'P':
4035 case 'c':
4036 case 'C':
4037 break;
4038 default:
4039 err = true;
4041 if (err)
4042 internal_error ("invalid fn spec attribute \"%s\"", str);
4044 /* Now check all parameters. */
4045 for (unsigned int i = 0; arg_specified_p (i); i++)
4047 unsigned int idx = arg_idx (i);
4048 switch (str[idx])
4050 case 'x':
4051 case 'X':
4052 case 'r':
4053 case 'R':
4054 case 'o':
4055 case 'O':
4056 case 'w':
4057 case 'W':
4058 case '.':
4059 if ((str[idx + 1] >= '1' && str[idx + 1] <= '9')
4060 || str[idx + 1] == 't')
4062 if (str[idx] != 'r' && str[idx] != 'R'
4063 && str[idx] != 'w' && str[idx] != 'W'
4064 && str[idx] != 'o' && str[idx] != 'O')
4065 err = true;
4066 if (str[idx + 1] != 't'
4067 /* Size specified is scalar, so it should be described
4068 by ". " if specified at all. */
4069 && (arg_specified_p (str[idx + 1] - '1')
4070 && str[arg_idx (str[idx + 1] - '1')] != '.'))
4071 err = true;
4073 else if (str[idx + 1] != ' ')
4074 err = true;
4075 break;
4076 default:
4077 if (str[idx] < '1' || str[idx] > '9')
4078 err = true;
4080 if (err)
4081 internal_error ("invalid fn spec attribute \"%s\" arg %i", str, i);
4085 /* Return ture if TYPE1 and TYPE2 will always give the same answer
4086 when compared wit hother types using same_type_for_tbaa_p. */
4088 static bool
4089 types_equal_for_same_type_for_tbaa_p (tree type1, tree type2,
4090 bool lto_streaming_safe)
4092 /* We use same_type_for_tbaa_p to match types in the access path.
4093 This check is overly conservative. */
4094 type1 = TYPE_MAIN_VARIANT (type1);
4095 type2 = TYPE_MAIN_VARIANT (type2);
4097 if (TYPE_STRUCTURAL_EQUALITY_P (type1)
4098 != TYPE_STRUCTURAL_EQUALITY_P (type2))
4099 return false;
4100 if (TYPE_STRUCTURAL_EQUALITY_P (type1))
4101 return true;
4103 if (lto_streaming_safe)
4104 return type1 == type2;
4105 else
4106 return TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2);
4109 /* Compare REF1 and REF2 and return flags specifying their differences.
4110 If LTO_STREAMING_SAFE is true do not use alias sets and canonical
4111 types that are going to be recomputed.
4112 If TBAA is true also compare TBAA metadata. */
4115 ao_compare::compare_ao_refs (ao_ref *ref1, ao_ref *ref2,
4116 bool lto_streaming_safe,
4117 bool tbaa)
4119 if (TREE_THIS_VOLATILE (ref1->ref) != TREE_THIS_VOLATILE (ref2->ref))
4120 return SEMANTICS;
4121 tree base1 = ao_ref_base (ref1);
4122 tree base2 = ao_ref_base (ref2);
4124 if (!known_eq (ref1->offset, ref2->offset)
4125 || !known_eq (ref1->size, ref2->size)
4126 || !known_eq (ref1->max_size, ref2->max_size))
4127 return SEMANTICS;
4129 /* For variable accesses we need to compare actual paths
4130 to check that both refs are accessing same address and the access size. */
4131 if (!known_eq (ref1->size, ref1->max_size))
4133 if (!operand_equal_p (TYPE_SIZE (TREE_TYPE (ref1->ref)),
4134 TYPE_SIZE (TREE_TYPE (ref2->ref)), 0))
4135 return SEMANTICS;
4136 tree r1 = ref1->ref;
4137 tree r2 = ref2->ref;
4139 /* Handle toplevel COMPONENT_REFs of bitfields.
4140 Those are special since they are not allowed in
4141 ADDR_EXPR. */
4142 if (TREE_CODE (r1) == COMPONENT_REF
4143 && DECL_BIT_FIELD (TREE_OPERAND (r1, 1)))
4145 if (TREE_CODE (r2) != COMPONENT_REF
4146 || !DECL_BIT_FIELD (TREE_OPERAND (r2, 1)))
4147 return SEMANTICS;
4148 tree field1 = TREE_OPERAND (r1, 1);
4149 tree field2 = TREE_OPERAND (r2, 1);
4150 if (!operand_equal_p (DECL_FIELD_OFFSET (field1),
4151 DECL_FIELD_OFFSET (field2), 0)
4152 || !operand_equal_p (DECL_FIELD_BIT_OFFSET (field1),
4153 DECL_FIELD_BIT_OFFSET (field2), 0)
4154 || !operand_equal_p (DECL_SIZE (field1), DECL_SIZE (field2), 0)
4155 || !types_compatible_p (TREE_TYPE (r1),
4156 TREE_TYPE (r2)))
4157 return SEMANTICS;
4158 r1 = TREE_OPERAND (r1, 0);
4159 r2 = TREE_OPERAND (r2, 0);
4161 else if (TREE_CODE (r2) == COMPONENT_REF
4162 && DECL_BIT_FIELD (TREE_OPERAND (r2, 1)))
4163 return SEMANTICS;
4165 /* Similarly for bit field refs. */
4166 if (TREE_CODE (r1) == BIT_FIELD_REF)
4168 if (TREE_CODE (r2) != BIT_FIELD_REF
4169 || !operand_equal_p (TREE_OPERAND (r1, 1),
4170 TREE_OPERAND (r2, 1), 0)
4171 || !operand_equal_p (TREE_OPERAND (r1, 2),
4172 TREE_OPERAND (r2, 2), 0)
4173 || !types_compatible_p (TREE_TYPE (r1),
4174 TREE_TYPE (r2)))
4175 return SEMANTICS;
4176 r1 = TREE_OPERAND (r1, 0);
4177 r2 = TREE_OPERAND (r2, 0);
4179 else if (TREE_CODE (r2) == BIT_FIELD_REF)
4180 return SEMANTICS;
4182 /* Now we can compare the address of actual memory access. */
4183 if (!operand_equal_p (r1, r2, OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS))
4184 return SEMANTICS;
4186 /* For constant accesses we get more matches by comparing offset only. */
4187 else if (!operand_equal_p (base1, base2,
4188 OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS))
4189 return SEMANTICS;
4191 /* We can't simply use get_object_alignment_1 on the full
4192 reference as for accesses with variable indexes this reports
4193 too conservative alignment. */
4194 unsigned int align1, align2;
4195 unsigned HOST_WIDE_INT bitpos1, bitpos2;
4196 bool known1 = get_object_alignment_1 (base1, &align1, &bitpos1);
4197 bool known2 = get_object_alignment_1 (base2, &align2, &bitpos2);
4198 /* ??? For MEMREF get_object_alignment_1 determines aligned from
4199 TYPE_ALIGN but still returns false. This seem to contradict
4200 its description. So compare even if alignment is unknown. */
4201 if (known1 != known2
4202 || (bitpos1 != bitpos2 || align1 != align2))
4203 return SEMANTICS;
4205 /* Now we know that accesses are semantically same. */
4206 int flags = 0;
4208 /* ao_ref_base strips inner MEM_REF [&decl], recover from that here. */
4209 tree rbase1 = ref1->ref;
4210 if (rbase1)
4211 while (handled_component_p (rbase1))
4212 rbase1 = TREE_OPERAND (rbase1, 0);
4213 tree rbase2 = ref2->ref;
4214 while (handled_component_p (rbase2))
4215 rbase2 = TREE_OPERAND (rbase2, 0);
4217 /* MEM_REFs and TARGET_MEM_REFs record dependence cliques which are used to
4218 implement restrict pointers. MR_DEPENDENCE_CLIQUE 0 means no information.
4219 Otherwise we need to match bases and cliques. */
4220 if ((((TREE_CODE (rbase1) == MEM_REF || TREE_CODE (rbase1) == TARGET_MEM_REF)
4221 && MR_DEPENDENCE_CLIQUE (rbase1))
4222 || ((TREE_CODE (rbase2) == MEM_REF || TREE_CODE (rbase2) == TARGET_MEM_REF)
4223 && MR_DEPENDENCE_CLIQUE (rbase2)))
4224 && (TREE_CODE (rbase1) != TREE_CODE (rbase2)
4225 || MR_DEPENDENCE_CLIQUE (rbase1) != MR_DEPENDENCE_CLIQUE (rbase2)
4226 || (MR_DEPENDENCE_BASE (rbase1) != MR_DEPENDENCE_BASE (rbase2))))
4227 flags |= DEPENDENCE_CLIQUE;
4229 if (!tbaa)
4230 return flags;
4232 /* Alias sets are not stable across LTO sreaming; be conservative here
4233 and compare types the alias sets are ultimately based on. */
4234 if (lto_streaming_safe)
4236 tree t1 = ao_ref_alias_ptr_type (ref1);
4237 tree t2 = ao_ref_alias_ptr_type (ref2);
4238 if (!alias_ptr_types_compatible_p (t1, t2))
4239 flags |= REF_ALIAS_SET;
4241 t1 = ao_ref_base_alias_ptr_type (ref1);
4242 t2 = ao_ref_base_alias_ptr_type (ref2);
4243 if (!alias_ptr_types_compatible_p (t1, t2))
4244 flags |= BASE_ALIAS_SET;
4246 else
4248 if (ao_ref_alias_set (ref1) != ao_ref_alias_set (ref2))
4249 flags |= REF_ALIAS_SET;
4250 if (ao_ref_base_alias_set (ref1) != ao_ref_base_alias_set (ref2))
4251 flags |= BASE_ALIAS_SET;
4254 /* Access path is used only on non-view-converted references. */
4255 bool view_converted = view_converted_memref_p (rbase1);
4256 if (view_converted_memref_p (rbase2) != view_converted)
4257 return flags | ACCESS_PATH;
4258 else if (view_converted)
4259 return flags;
4262 /* Find start of access paths and look for trailing arrays. */
4263 tree c1 = ref1->ref, c2 = ref2->ref;
4264 tree end_struct_ref1 = NULL, end_struct_ref2 = NULL;
4265 int nskipped1 = 0, nskipped2 = 0;
4266 int i = 0;
4268 for (tree p1 = ref1->ref; handled_component_p (p1); p1 = TREE_OPERAND (p1, 0))
4270 if (component_ref_to_zero_sized_trailing_array_p (p1))
4271 end_struct_ref1 = p1;
4272 if (ends_tbaa_access_path_p (p1))
4273 c1 = p1, nskipped1 = i;
4274 i++;
4276 for (tree p2 = ref2->ref; handled_component_p (p2); p2 = TREE_OPERAND (p2, 0))
4278 if (component_ref_to_zero_sized_trailing_array_p (p2))
4279 end_struct_ref2 = p2;
4280 if (ends_tbaa_access_path_p (p2))
4281 c2 = p2, nskipped1 = i;
4282 i++;
4285 /* For variable accesses we can not rely on offset match bellow.
4286 We know that paths are struturally same, so only check that
4287 starts of TBAA paths did not diverge. */
4288 if (!known_eq (ref1->size, ref1->max_size)
4289 && nskipped1 != nskipped2)
4290 return flags | ACCESS_PATH;
4292 /* Information about trailing refs is used by
4293 aliasing_component_refs_p that is applied only if paths
4294 has handled components.. */
4295 if (!handled_component_p (c1) && !handled_component_p (c2))
4297 else if ((end_struct_ref1 != NULL) != (end_struct_ref2 != NULL))
4298 return flags | ACCESS_PATH;
4299 if (end_struct_ref1
4300 && TYPE_MAIN_VARIANT (TREE_TYPE (end_struct_ref1))
4301 != TYPE_MAIN_VARIANT (TREE_TYPE (end_struct_ref2)))
4302 return flags | ACCESS_PATH;
4304 /* Now compare all handled components of the access path.
4305 We have three oracles that cares about access paths:
4306 - aliasing_component_refs_p
4307 - nonoverlapping_refs_since_match_p
4308 - nonoverlapping_component_refs_p
4309 We need to match things these oracles compare.
4311 It is only necessary to check types for compatibility
4312 and offsets. Rest of what oracles compares are actual
4313 addresses. Those are already known to be same:
4314 - for constant accesses we check offsets
4315 - for variable accesses we already matched
4316 the path lexically with operand_equal_p. */
4317 while (true)
4319 bool comp1 = handled_component_p (c1);
4320 bool comp2 = handled_component_p (c2);
4322 if (comp1 != comp2)
4323 return flags | ACCESS_PATH;
4324 if (!comp1)
4325 break;
4327 if (TREE_CODE (c1) != TREE_CODE (c2))
4328 return flags | ACCESS_PATH;
4330 /* aliasing_component_refs_p attempts to find type match within
4331 the paths. For that reason both types needs to be equal
4332 with respect to same_type_for_tbaa_p. */
4333 if (!types_equal_for_same_type_for_tbaa_p (TREE_TYPE (c1),
4334 TREE_TYPE (c2),
4335 lto_streaming_safe))
4336 return flags | ACCESS_PATH;
4337 if (component_ref_to_zero_sized_trailing_array_p (c1)
4338 != component_ref_to_zero_sized_trailing_array_p (c2))
4339 return flags | ACCESS_PATH;
4341 /* aliasing_matching_component_refs_p compares
4342 offsets within the path. Other properties are ignored.
4343 Do not bother to verify offsets in variable accesses. Here we
4344 already compared them by operand_equal_p so they are
4345 structurally same. */
4346 if (!known_eq (ref1->size, ref1->max_size))
4348 poly_int64 offadj1, sztmc1, msztmc1;
4349 bool reverse1;
4350 get_ref_base_and_extent (c1, &offadj1, &sztmc1, &msztmc1, &reverse1);
4351 poly_int64 offadj2, sztmc2, msztmc2;
4352 bool reverse2;
4353 get_ref_base_and_extent (c2, &offadj2, &sztmc2, &msztmc2, &reverse2);
4354 if (!known_eq (offadj1, offadj2))
4355 return flags | ACCESS_PATH;
4357 c1 = TREE_OPERAND (c1, 0);
4358 c2 = TREE_OPERAND (c2, 0);
4360 /* Finally test the access type. */
4361 if (!types_equal_for_same_type_for_tbaa_p (TREE_TYPE (c1),
4362 TREE_TYPE (c2),
4363 lto_streaming_safe))
4364 return flags | ACCESS_PATH;
4365 return flags;
4368 /* Hash REF to HSTATE. If LTO_STREAMING_SAFE do not use alias sets
4369 and canonical types. */
4370 void
4371 ao_compare::hash_ao_ref (ao_ref *ref, bool lto_streaming_safe, bool tbaa,
4372 inchash::hash &hstate)
4374 tree base = ao_ref_base (ref);
4375 tree tbase = base;
4377 if (!known_eq (ref->size, ref->max_size))
4379 tree r = ref->ref;
4380 if (TREE_CODE (r) == COMPONENT_REF
4381 && DECL_BIT_FIELD (TREE_OPERAND (r, 1)))
4383 tree field = TREE_OPERAND (r, 1);
4384 hash_operand (DECL_FIELD_OFFSET (field), hstate, 0);
4385 hash_operand (DECL_FIELD_BIT_OFFSET (field), hstate, 0);
4386 hash_operand (DECL_SIZE (field), hstate, 0);
4387 r = TREE_OPERAND (r, 0);
4389 if (TREE_CODE (r) == BIT_FIELD_REF)
4391 hash_operand (TREE_OPERAND (r, 1), hstate, 0);
4392 hash_operand (TREE_OPERAND (r, 2), hstate, 0);
4393 r = TREE_OPERAND (r, 0);
4395 hash_operand (TYPE_SIZE (TREE_TYPE (ref->ref)), hstate, 0);
4396 hash_operand (r, hstate, OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS);
4398 else
4400 hash_operand (tbase, hstate, OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS);
4401 hstate.add_poly_int (ref->offset);
4402 hstate.add_poly_int (ref->size);
4403 hstate.add_poly_int (ref->max_size);
4405 if (!lto_streaming_safe && tbaa)
4407 hstate.add_int (ao_ref_alias_set (ref));
4408 hstate.add_int (ao_ref_base_alias_set (ref));