Line data Source code
1 : /* Alias analysis for trees.
2 : Copyright (C) 2004-2026 Free Software Foundation, Inc.
3 : Contributed by Diego Novillo <dnovillo@redhat.com>
4 :
5 : This file is part of GCC.
6 :
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.
11 :
12 : GCC is distributed in the hope that it will be useful,
13 : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : GNU General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "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"
51 : #include "ipa-utils.h"
52 :
53 : /* Broad overview of how alias analysis on gimple works:
54 :
55 : Statements clobbering or using memory are linked through the
56 : virtual operand factored use-def chain. The virtual operand
57 : is unique per function, its symbol is accessible via gimple_vop (cfun).
58 : Virtual operands are used for efficiently walking memory statements
59 : in the gimple IL and are useful for things like value-numbering as
60 : a generation count for memory references.
61 :
62 : SSA_NAME pointers may have associated points-to information
63 : accessible via the SSA_NAME_PTR_INFO macro. Flow-insensitive
64 : points-to information is (re-)computed by the TODO_rebuild_alias
65 : pass manager todo. Points-to information is also used for more
66 : precise tracking of call-clobbered and call-used variables and
67 : related disambiguations.
68 :
69 : This file contains functions for disambiguating memory references,
70 : the so called alias-oracle and tools for walking of the gimple IL.
71 :
72 : The main alias-oracle entry-points are
73 :
74 : bool stmt_may_clobber_ref_p (gimple *, tree)
75 :
76 : This function queries if a statement may invalidate (parts of)
77 : the memory designated by the reference tree argument.
78 :
79 : bool ref_maybe_used_by_stmt_p (gimple *, tree)
80 :
81 : This function queries if a statement may need (parts of) the
82 : memory designated by the reference tree argument.
83 :
84 : There are variants of these functions that only handle the call
85 : part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
86 : Note that these do not disambiguate against a possible call lhs.
87 :
88 : bool refs_may_alias_p (tree, tree)
89 :
90 : This function tries to disambiguate two reference trees.
91 :
92 : bool ptr_deref_may_alias_global_p (tree, bool)
93 :
94 : This function queries if dereferencing a pointer variable may
95 : alias global memory. If bool argument is true, global memory
96 : is considered to also include function local memory that escaped.
97 :
98 : More low-level disambiguators are available and documented in
99 : this file. Low-level disambiguators dealing with points-to
100 : information are in tree-ssa-structalias.cc. */
101 :
102 : static int nonoverlapping_refs_since_match_p (tree, tree, tree, tree, bool);
103 : static bool nonoverlapping_component_refs_p (const_tree, const_tree);
104 :
105 : /* Query statistics for the different low-level disambiguators.
106 : A high-level query may trigger multiple of them. */
107 :
108 : static struct {
109 : unsigned HOST_WIDE_INT refs_may_alias_p_may_alias;
110 : unsigned HOST_WIDE_INT refs_may_alias_p_no_alias;
111 : unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias;
112 : unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias;
113 : unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias;
114 : unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias;
115 : unsigned HOST_WIDE_INT aliasing_component_refs_p_may_alias;
116 : unsigned HOST_WIDE_INT aliasing_component_refs_p_no_alias;
117 : unsigned HOST_WIDE_INT nonoverlapping_component_refs_p_may_alias;
118 : unsigned HOST_WIDE_INT nonoverlapping_component_refs_p_no_alias;
119 : unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_may_alias;
120 : unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_must_overlap;
121 : unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_no_alias;
122 : unsigned HOST_WIDE_INT stmt_kills_ref_p_no;
123 : unsigned HOST_WIDE_INT stmt_kills_ref_p_yes;
124 : unsigned HOST_WIDE_INT modref_use_may_alias;
125 : unsigned HOST_WIDE_INT modref_use_no_alias;
126 : unsigned HOST_WIDE_INT modref_clobber_may_alias;
127 : unsigned HOST_WIDE_INT modref_clobber_no_alias;
128 : unsigned HOST_WIDE_INT modref_kill_no;
129 : unsigned HOST_WIDE_INT modref_kill_yes;
130 : unsigned HOST_WIDE_INT modref_tests;
131 : unsigned HOST_WIDE_INT modref_baseptr_tests;
132 : } alias_stats;
133 :
134 : void
135 0 : dump_alias_stats (FILE *s)
136 : {
137 0 : fprintf (s, "\nAlias oracle query stats:\n");
138 0 : fprintf (s, " refs_may_alias_p: "
139 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
140 : HOST_WIDE_INT_PRINT_DEC" queries\n",
141 : alias_stats.refs_may_alias_p_no_alias,
142 0 : alias_stats.refs_may_alias_p_no_alias
143 0 : + alias_stats.refs_may_alias_p_may_alias);
144 0 : fprintf (s, " ref_maybe_used_by_call_p: "
145 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
146 : HOST_WIDE_INT_PRINT_DEC" queries\n",
147 : alias_stats.ref_maybe_used_by_call_p_no_alias,
148 0 : alias_stats.refs_may_alias_p_no_alias
149 0 : + alias_stats.ref_maybe_used_by_call_p_may_alias);
150 0 : fprintf (s, " call_may_clobber_ref_p: "
151 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
152 : HOST_WIDE_INT_PRINT_DEC" queries\n",
153 : alias_stats.call_may_clobber_ref_p_no_alias,
154 0 : alias_stats.call_may_clobber_ref_p_no_alias
155 0 : + alias_stats.call_may_clobber_ref_p_may_alias);
156 0 : fprintf (s, " stmt_kills_ref_p: "
157 : HOST_WIDE_INT_PRINT_DEC" kills, "
158 : HOST_WIDE_INT_PRINT_DEC" queries\n",
159 : alias_stats.stmt_kills_ref_p_yes + alias_stats.modref_kill_yes,
160 0 : alias_stats.stmt_kills_ref_p_yes + alias_stats.modref_kill_yes
161 0 : + alias_stats.stmt_kills_ref_p_no + alias_stats.modref_kill_no);
162 0 : fprintf (s, " nonoverlapping_component_refs_p: "
163 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
164 : HOST_WIDE_INT_PRINT_DEC" queries\n",
165 : alias_stats.nonoverlapping_component_refs_p_no_alias,
166 0 : alias_stats.nonoverlapping_component_refs_p_no_alias
167 0 : + alias_stats.nonoverlapping_component_refs_p_may_alias);
168 0 : fprintf (s, " nonoverlapping_refs_since_match_p: "
169 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
170 : HOST_WIDE_INT_PRINT_DEC" must overlaps, "
171 : HOST_WIDE_INT_PRINT_DEC" queries\n",
172 : alias_stats.nonoverlapping_refs_since_match_p_no_alias,
173 : alias_stats.nonoverlapping_refs_since_match_p_must_overlap,
174 0 : alias_stats.nonoverlapping_refs_since_match_p_no_alias
175 0 : + alias_stats.nonoverlapping_refs_since_match_p_may_alias
176 0 : + alias_stats.nonoverlapping_refs_since_match_p_must_overlap);
177 0 : fprintf (s, " aliasing_component_refs_p: "
178 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
179 : HOST_WIDE_INT_PRINT_DEC" queries\n",
180 : alias_stats.aliasing_component_refs_p_no_alias,
181 0 : alias_stats.aliasing_component_refs_p_no_alias
182 0 : + alias_stats.aliasing_component_refs_p_may_alias);
183 0 : dump_alias_stats_in_alias_c (s);
184 0 : fprintf (s, "\nModref stats:\n");
185 0 : fprintf (s, " modref kill: "
186 : HOST_WIDE_INT_PRINT_DEC" kills, "
187 : HOST_WIDE_INT_PRINT_DEC" queries\n",
188 : alias_stats.modref_kill_yes,
189 0 : alias_stats.modref_kill_yes
190 0 : + alias_stats.modref_kill_no);
191 0 : fprintf (s, " modref use: "
192 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
193 : HOST_WIDE_INT_PRINT_DEC" queries\n",
194 : alias_stats.modref_use_no_alias,
195 0 : alias_stats.modref_use_no_alias
196 0 : + alias_stats.modref_use_may_alias);
197 0 : fprintf (s, " modref clobber: "
198 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
199 : HOST_WIDE_INT_PRINT_DEC" queries\n"
200 : " " HOST_WIDE_INT_PRINT_DEC" tbaa queries (%f per modref query)\n"
201 : " " HOST_WIDE_INT_PRINT_DEC" base compares (%f per modref query)\n",
202 : alias_stats.modref_clobber_no_alias,
203 : alias_stats.modref_clobber_no_alias
204 : + alias_stats.modref_clobber_may_alias,
205 : alias_stats.modref_tests,
206 0 : ((double)alias_stats.modref_tests)
207 : / (alias_stats.modref_clobber_no_alias
208 : + alias_stats.modref_clobber_may_alias),
209 : alias_stats.modref_baseptr_tests,
210 0 : ((double)alias_stats.modref_baseptr_tests)
211 0 : / (alias_stats.modref_clobber_no_alias
212 0 : + alias_stats.modref_clobber_may_alias));
213 0 : }
214 :
215 :
216 : /* Return true, if dereferencing PTR may alias with a global variable.
217 : When ESCAPED_LOCAL_P is true escaped local memory is also considered
218 : global. */
219 :
220 : bool
221 59616736 : ptr_deref_may_alias_global_p (tree ptr, bool escaped_local_p)
222 : {
223 59616736 : struct ptr_info_def *pi;
224 :
225 : /* If we end up with a pointer constant here that may point
226 : to global memory. */
227 59616736 : if (TREE_CODE (ptr) != SSA_NAME)
228 : return true;
229 :
230 59610566 : pi = SSA_NAME_PTR_INFO (ptr);
231 :
232 : /* If we do not have points-to information for this variable,
233 : we have to punt. */
234 59610566 : if (!pi)
235 : return true;
236 :
237 : /* ??? This does not use TBAA to prune globals ptr may not access. */
238 47609161 : return pt_solution_includes_global (&pi->pt, escaped_local_p);
239 : }
240 :
241 : /* Return true, if dereferencing PTR may alias with a local automatic
242 : variable. */
243 :
244 : bool
245 16218 : ptr_deref_may_alias_auto_p (tree ptr)
246 : {
247 16218 : struct ptr_info_def *pi;
248 :
249 : /* If we end up with a pointer constant here that may point
250 : to local stack memory. */
251 16218 : if (TREE_CODE (ptr) != SSA_NAME)
252 : return true;
253 :
254 16218 : pi = SSA_NAME_PTR_INFO (ptr);
255 :
256 : /* If we do not have points-to information for this variable,
257 : we have to punt. */
258 16218 : if (!pi)
259 : return true;
260 :
261 6711 : return pt_solution_includes_auto (&pi->pt);
262 : }
263 :
264 :
265 : /* Return true if dereferencing PTR may alias DECL.
266 : The caller is responsible for applying TBAA to see if PTR
267 : may access DECL at all. */
268 :
269 : static bool
270 217272095 : ptr_deref_may_alias_decl_p (tree ptr, tree decl)
271 : {
272 217272095 : struct ptr_info_def *pi;
273 :
274 : /* Conversions are irrelevant for points-to information and
275 : data-dependence analysis can feed us those. */
276 217272095 : STRIP_NOPS (ptr);
277 :
278 : /* Anything we do not explicitly handle aliases. */
279 217272095 : if ((TREE_CODE (ptr) != SSA_NAME
280 2348618 : && TREE_CODE (ptr) != ADDR_EXPR
281 1118987 : && TREE_CODE (ptr) != POINTER_PLUS_EXPR)
282 216153108 : || !POINTER_TYPE_P (TREE_TYPE (ptr))
283 433424819 : || (!VAR_P (decl)
284 : && TREE_CODE (decl) != PARM_DECL
285 : && TREE_CODE (decl) != RESULT_DECL))
286 : return true;
287 :
288 : /* Disregard pointer offsetting. */
289 216151663 : if (TREE_CODE (ptr) == POINTER_PLUS_EXPR)
290 : {
291 0 : do
292 : {
293 0 : ptr = TREE_OPERAND (ptr, 0);
294 : }
295 0 : while (TREE_CODE (ptr) == POINTER_PLUS_EXPR);
296 : return ptr_deref_may_alias_decl_p (ptr, decl);
297 : }
298 :
299 : /* ADDR_EXPR pointers either just offset another pointer or directly
300 : specify the pointed-to set. */
301 216151663 : if (TREE_CODE (ptr) == ADDR_EXPR)
302 : {
303 1228608 : tree base = get_base_address (TREE_OPERAND (ptr, 0));
304 1228608 : if (base
305 1228608 : && (TREE_CODE (base) == MEM_REF
306 1228608 : || TREE_CODE (base) == TARGET_MEM_REF))
307 19561 : ptr = TREE_OPERAND (base, 0);
308 1209047 : else if (base
309 1209047 : && DECL_P (base))
310 1208695 : return compare_base_decls (base, decl) != 0;
311 352 : else if (base
312 352 : && CONSTANT_CLASS_P (base))
313 : return false;
314 : else
315 : return true;
316 : }
317 :
318 : /* Non-aliased variables cannot be pointed to. */
319 214942616 : if (!may_be_aliased (decl))
320 : return false;
321 :
322 : /* From here we require a SSA name pointer. Anything else aliases. */
323 81011298 : if (TREE_CODE (ptr) != SSA_NAME
324 81011298 : || !POINTER_TYPE_P (TREE_TYPE (ptr)))
325 : return true;
326 :
327 : /* If we do not have useful points-to information for this pointer
328 : we cannot disambiguate anything else. */
329 81011298 : pi = SSA_NAME_PTR_INFO (ptr);
330 81011298 : if (!pi)
331 : return true;
332 :
333 79966422 : return pt_solution_includes (&pi->pt, decl);
334 : }
335 :
336 : /* Return true if dereferenced PTR1 and PTR2 may alias.
337 : The caller is responsible for applying TBAA to see if accesses
338 : through PTR1 and PTR2 may conflict at all. */
339 :
340 : bool
341 70721317 : ptr_derefs_may_alias_p (tree ptr1, tree ptr2)
342 : {
343 72062819 : struct ptr_info_def *pi1, *pi2;
344 :
345 : /* Conversions are irrelevant for points-to information and
346 : data-dependence analysis can feed us those. */
347 72062819 : STRIP_NOPS (ptr1);
348 72062819 : STRIP_NOPS (ptr2);
349 :
350 : /* Disregard pointer offsetting. */
351 72062819 : if (TREE_CODE (ptr1) == POINTER_PLUS_EXPR)
352 : {
353 548719 : do
354 : {
355 548719 : ptr1 = TREE_OPERAND (ptr1, 0);
356 : }
357 548719 : while (TREE_CODE (ptr1) == POINTER_PLUS_EXPR);
358 : return ptr_derefs_may_alias_p (ptr1, ptr2);
359 : }
360 71514100 : if (TREE_CODE (ptr2) == POINTER_PLUS_EXPR)
361 : {
362 563152 : do
363 : {
364 563152 : ptr2 = TREE_OPERAND (ptr2, 0);
365 : }
366 563152 : while (TREE_CODE (ptr2) == POINTER_PLUS_EXPR);
367 : return ptr_derefs_may_alias_p (ptr1, ptr2);
368 : }
369 :
370 : /* ADDR_EXPR pointers either just offset another pointer or directly
371 : specify the pointed-to set. */
372 70950948 : if (TREE_CODE (ptr1) == ADDR_EXPR)
373 : {
374 870905 : tree base = get_base_address (TREE_OPERAND (ptr1, 0));
375 870905 : if (base
376 870905 : && (TREE_CODE (base) == MEM_REF
377 870905 : || TREE_CODE (base) == TARGET_MEM_REF))
378 116964 : return ptr_derefs_may_alias_p (TREE_OPERAND (base, 0), ptr2);
379 753941 : else if (base
380 753941 : && DECL_P (base))
381 751483 : return ptr_deref_may_alias_decl_p (ptr2, base);
382 : /* Try ptr2 when ptr1 points to a constant. */
383 : else if (base
384 2458 : && !CONSTANT_CLASS_P (base))
385 : return true;
386 : }
387 70082501 : if (TREE_CODE (ptr2) == ADDR_EXPR)
388 : {
389 343678 : tree base = get_base_address (TREE_OPERAND (ptr2, 0));
390 343678 : if (base
391 343678 : && (TREE_CODE (base) == MEM_REF
392 343678 : || TREE_CODE (base) == TARGET_MEM_REF))
393 112667 : return ptr_derefs_may_alias_p (ptr1, TREE_OPERAND (base, 0));
394 231011 : else if (base
395 231011 : && DECL_P (base))
396 229539 : return ptr_deref_may_alias_decl_p (ptr1, base);
397 : else
398 : return true;
399 : }
400 :
401 : /* From here we require SSA name pointers. Anything else aliases. */
402 69738823 : if (TREE_CODE (ptr1) != SSA_NAME
403 69581777 : || TREE_CODE (ptr2) != SSA_NAME
404 69557024 : || !POINTER_TYPE_P (TREE_TYPE (ptr1))
405 139286047 : || !POINTER_TYPE_P (TREE_TYPE (ptr2)))
406 : return true;
407 :
408 : /* We may end up with two empty points-to solutions for two same pointers.
409 : In this case we still want to say both pointers alias, so shortcut
410 : that here. */
411 69547067 : if (ptr1 == ptr2)
412 : return true;
413 :
414 : /* If we do not have useful points-to information for either pointer
415 : we cannot disambiguate anything else. */
416 65668121 : pi1 = SSA_NAME_PTR_INFO (ptr1);
417 65668121 : pi2 = SSA_NAME_PTR_INFO (ptr2);
418 65668121 : if (!pi1 || !pi2)
419 : return true;
420 :
421 : /* ??? This does not use TBAA to prune decls from the intersection
422 : that not both pointers may access. */
423 62967871 : return pt_solutions_intersect (&pi1->pt, &pi2->pt);
424 : }
425 :
426 : /* Return true if dereferencing PTR may alias *REF.
427 : The caller is responsible for applying TBAA to see if PTR
428 : may access *REF at all. */
429 :
430 : static bool
431 1740390 : ptr_deref_may_alias_ref_p_1 (tree ptr, ao_ref *ref)
432 : {
433 1740390 : tree base = ao_ref_base (ref);
434 :
435 1740390 : if (TREE_CODE (base) == MEM_REF
436 1740390 : || TREE_CODE (base) == TARGET_MEM_REF)
437 141482 : return ptr_derefs_may_alias_p (ptr, TREE_OPERAND (base, 0));
438 1598908 : else if (DECL_P (base))
439 1596631 : return ptr_deref_may_alias_decl_p (ptr, base);
440 :
441 : return true;
442 : }
443 :
444 : /* Returns true if PTR1 and PTR2 compare unequal because of points-to. */
445 :
446 : bool
447 58610879 : ptrs_compare_unequal (tree ptr1, tree ptr2)
448 : {
449 : /* First resolve the pointers down to a SSA name pointer base or
450 : a VAR_DECL, PARM_DECL or RESULT_DECL. This explicitly does
451 : not yet try to handle LABEL_DECLs, FUNCTION_DECLs, CONST_DECLs
452 : or STRING_CSTs which needs points-to adjustments to track them
453 : in the points-to sets. */
454 58610879 : tree obj1 = NULL_TREE;
455 58610879 : tree obj2 = NULL_TREE;
456 58610879 : if (TREE_CODE (ptr1) == ADDR_EXPR)
457 : {
458 58173 : tree tem = get_base_address (TREE_OPERAND (ptr1, 0));
459 58173 : if (! tem)
460 : return false;
461 58173 : if (VAR_P (tem)
462 : || TREE_CODE (tem) == PARM_DECL
463 : || TREE_CODE (tem) == RESULT_DECL)
464 : obj1 = tem;
465 : else if (TREE_CODE (tem) == MEM_REF)
466 10803 : ptr1 = TREE_OPERAND (tem, 0);
467 : }
468 58610879 : if (TREE_CODE (ptr2) == ADDR_EXPR)
469 : {
470 9968857 : tree tem = get_base_address (TREE_OPERAND (ptr2, 0));
471 9968857 : if (! tem)
472 : return false;
473 9968857 : if (VAR_P (tem)
474 : || TREE_CODE (tem) == PARM_DECL
475 : || TREE_CODE (tem) == RESULT_DECL)
476 : obj2 = tem;
477 : else if (TREE_CODE (tem) == MEM_REF)
478 171129 : ptr2 = TREE_OPERAND (tem, 0);
479 : }
480 :
481 : /* Canonicalize ptr vs. object. */
482 58610879 : if (TREE_CODE (ptr1) == SSA_NAME && obj2)
483 : {
484 : std::swap (ptr1, ptr2);
485 : std::swap (obj1, obj2);
486 : }
487 :
488 58610879 : if (obj1 && obj2)
489 : /* Other code handles this correctly, no need to duplicate it here. */;
490 6379542 : else if (obj1 && TREE_CODE (ptr2) == SSA_NAME)
491 : {
492 6367923 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr2);
493 : /* We may not use restrict to optimize pointer comparisons.
494 : See PR71062. So we have to assume that restrict-pointed-to
495 : may be in fact obj1. */
496 6367923 : if (!pi
497 5170600 : || pi->pt.vars_contains_restrict
498 5161278 : || pi->pt.vars_contains_interposable)
499 : return false;
500 4441176 : if (VAR_P (obj1)
501 4441176 : && (TREE_STATIC (obj1) || DECL_EXTERNAL (obj1)))
502 : {
503 1138683 : varpool_node *node = varpool_node::get (obj1);
504 : /* If obj1 may bind to NULL give up (see below). */
505 1138683 : if (! node
506 1138683 : || ! node->nonzero_address ()
507 2277330 : || ! decl_binds_to_current_def_p (obj1))
508 852579 : return false;
509 : }
510 3588597 : return !pt_solution_includes (&pi->pt, obj1);
511 : }
512 52230193 : else if (TREE_CODE (ptr1) == SSA_NAME)
513 : {
514 45752354 : struct ptr_info_def *pi1 = SSA_NAME_PTR_INFO (ptr1);
515 45752354 : if (!pi1
516 34868621 : || pi1->pt.vars_contains_restrict
517 33874719 : || pi1->pt.vars_contains_interposable)
518 : return false;
519 31855045 : if (integer_zerop (ptr2) && !pi1->pt.null)
520 : return true;
521 31833012 : if (TREE_CODE (ptr2) == SSA_NAME)
522 : {
523 10689050 : struct ptr_info_def *pi2 = SSA_NAME_PTR_INFO (ptr2);
524 10689050 : if (!pi2
525 10080510 : || pi2->pt.vars_contains_restrict
526 10074348 : || pi2->pt.vars_contains_interposable)
527 : return false;
528 8353326 : if ((!pi1->pt.null || !pi2->pt.null)
529 : /* ??? We do not represent FUNCTION_DECL and LABEL_DECL
530 : in pt.vars but only set pt.vars_contains_nonlocal. This
531 : makes compares involving those and other nonlocals
532 : imprecise. */
533 4170982 : && (!pi1->pt.vars_contains_nonlocal
534 65639 : || !pi2->pt.vars_contains_nonlocal)
535 14107148 : && (!pt_solution_includes_const_pool (&pi1->pt)
536 3773724 : || !pt_solution_includes_const_pool (&pi2->pt)))
537 460489 : return !pt_solutions_intersect (&pi1->pt, &pi2->pt);
538 : }
539 : }
540 :
541 : return false;
542 : }
543 :
544 : /* Returns whether reference REF to BASE may refer to global memory.
545 : When ESCAPED_LOCAL_P is true escaped local memory is also considered
546 : global. */
547 :
548 : static bool
549 56077014 : ref_may_alias_global_p_1 (tree base, bool escaped_local_p)
550 : {
551 56077014 : if (DECL_P (base))
552 43691697 : return (is_global_var (base)
553 43691697 : || (escaped_local_p
554 1053184 : && pt_solution_includes (&cfun->gimple_df->escaped_return,
555 : base)));
556 12385317 : else if (TREE_CODE (base) == MEM_REF
557 12385317 : || TREE_CODE (base) == TARGET_MEM_REF)
558 12374215 : return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0),
559 12374215 : escaped_local_p);
560 : return true;
561 : }
562 :
563 : bool
564 11297794 : ref_may_alias_global_p (ao_ref *ref, bool escaped_local_p)
565 : {
566 11297794 : tree base = ao_ref_base (ref);
567 11297794 : return ref_may_alias_global_p_1 (base, escaped_local_p);
568 : }
569 :
570 : bool
571 44779220 : ref_may_alias_global_p (tree ref, bool escaped_local_p)
572 : {
573 44779220 : tree base = get_base_address (ref);
574 44779220 : return ref_may_alias_global_p_1 (base, escaped_local_p);
575 : }
576 :
577 : /* Return true whether STMT may clobber global memory.
578 : When ESCAPED_LOCAL_P is true escaped local memory is also considered
579 : global. */
580 :
581 : bool
582 182466636 : stmt_may_clobber_global_p (gimple *stmt, bool escaped_local_p)
583 : {
584 182466636 : tree lhs;
585 :
586 364119466 : if (!gimple_vdef (stmt))
587 : return false;
588 :
589 : /* ??? We can ask the oracle whether an artificial pointer
590 : dereference with a pointer with points-to information covering
591 : all global memory (what about non-address taken memory?) maybe
592 : clobbered by this call. As there is at the moment no convenient
593 : way of doing that without generating garbage do some manual
594 : checking instead.
595 : ??? We could make a NULL ao_ref argument to the various
596 : predicates special, meaning any global memory. */
597 :
598 45019738 : switch (gimple_code (stmt))
599 : {
600 44779220 : case GIMPLE_ASSIGN:
601 44779220 : lhs = gimple_assign_lhs (stmt);
602 44779220 : return (TREE_CODE (lhs) != SSA_NAME
603 44779220 : && ref_may_alias_global_p (lhs, escaped_local_p));
604 : case GIMPLE_CALL:
605 : return true;
606 : default:
607 : return true;
608 : }
609 : }
610 :
611 :
612 : /* Dump alias information on FILE. */
613 :
614 : void
615 283 : dump_alias_info (FILE *file)
616 : {
617 283 : unsigned i;
618 283 : tree ptr;
619 283 : const char *funcname
620 283 : = lang_hooks.decl_printable_name (current_function_decl, 2);
621 283 : tree var;
622 :
623 283 : fprintf (file, "\n\nAlias information for %s\n\n", funcname);
624 :
625 283 : fprintf (file, "Aliased symbols\n\n");
626 :
627 1122 : FOR_EACH_LOCAL_DECL (cfun, i, var)
628 : {
629 585 : if (may_be_aliased (var))
630 351 : dump_variable (file, var);
631 : }
632 :
633 283 : fprintf (file, "\nCall clobber information\n");
634 :
635 283 : fprintf (file, "\nESCAPED");
636 283 : dump_points_to_solution (file, &cfun->gimple_df->escaped);
637 :
638 283 : fprintf (file, "\nESCAPED_RETURN");
639 283 : dump_points_to_solution (file, &cfun->gimple_df->escaped_return);
640 :
641 283 : fprintf (file, "\n\nFlow-insensitive points-to information\n\n");
642 :
643 3052 : FOR_EACH_SSA_NAME (i, ptr, cfun)
644 : {
645 2549 : struct ptr_info_def *pi;
646 :
647 4654 : if (!POINTER_TYPE_P (TREE_TYPE (ptr))
648 2596 : || SSA_NAME_IN_FREE_LIST (ptr))
649 2058 : continue;
650 :
651 491 : pi = SSA_NAME_PTR_INFO (ptr);
652 491 : if (pi)
653 485 : dump_points_to_info_for (file, ptr);
654 : }
655 :
656 283 : fprintf (file, "\n");
657 283 : }
658 :
659 :
660 : /* Dump alias information on stderr. */
661 :
662 : DEBUG_FUNCTION void
663 0 : debug_alias_info (void)
664 : {
665 0 : dump_alias_info (stderr);
666 0 : }
667 :
668 :
669 : /* Dump the points-to set *PT into FILE. */
670 :
671 : void
672 1051 : dump_points_to_solution (FILE *file, struct pt_solution *pt)
673 : {
674 1051 : if (pt->anything)
675 3 : fprintf (file, ", points-to anything");
676 :
677 1051 : if (pt->nonlocal)
678 633 : fprintf (file, ", points-to non-local");
679 :
680 1051 : if (pt->escaped)
681 420 : fprintf (file, ", points-to escaped");
682 :
683 1051 : if (pt->ipa_escaped)
684 0 : fprintf (file, ", points-to unit escaped");
685 :
686 1051 : if (pt->null)
687 611 : fprintf (file, ", points-to NULL");
688 :
689 1051 : if (pt->const_pool)
690 0 : fprintf (file, ", points-to const-pool");
691 :
692 1051 : if (pt->vars)
693 : {
694 1048 : fprintf (file, ", points-to vars: ");
695 1048 : dump_decl_set (file, pt->vars);
696 1048 : if (pt->vars_contains_nonlocal
697 914 : || pt->vars_contains_escaped
698 837 : || pt->vars_contains_escaped_heap
699 837 : || pt->vars_contains_restrict
700 837 : || pt->vars_contains_interposable)
701 : {
702 211 : const char *comma = "";
703 211 : fprintf (file, " (");
704 211 : if (pt->vars_contains_nonlocal)
705 : {
706 134 : fprintf (file, "nonlocal");
707 134 : comma = ", ";
708 : }
709 211 : if (pt->vars_contains_escaped)
710 : {
711 139 : fprintf (file, "%sescaped", comma);
712 139 : comma = ", ";
713 : }
714 211 : if (pt->vars_contains_escaped_heap)
715 : {
716 0 : fprintf (file, "%sescaped heap", comma);
717 0 : comma = ", ";
718 : }
719 211 : if (pt->vars_contains_restrict)
720 : {
721 58 : fprintf (file, "%srestrict", comma);
722 58 : comma = ", ";
723 : }
724 211 : if (pt->vars_contains_interposable)
725 0 : fprintf (file, "%sinterposable", comma);
726 211 : fprintf (file, ")");
727 : }
728 : }
729 1051 : }
730 :
731 :
732 : /* Unified dump function for pt_solution. */
733 :
734 : DEBUG_FUNCTION void
735 0 : debug (pt_solution &ref)
736 : {
737 0 : dump_points_to_solution (stderr, &ref);
738 0 : }
739 :
740 : DEBUG_FUNCTION void
741 0 : debug (pt_solution *ptr)
742 : {
743 0 : if (ptr)
744 0 : debug (*ptr);
745 : else
746 0 : fprintf (stderr, "<nil>\n");
747 0 : }
748 :
749 :
750 : /* Dump points-to information for SSA_NAME PTR into FILE. */
751 :
752 : void
753 485 : dump_points_to_info_for (FILE *file, tree ptr)
754 : {
755 485 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
756 :
757 485 : print_generic_expr (file, ptr, dump_flags);
758 :
759 485 : if (pi)
760 485 : dump_points_to_solution (file, &pi->pt);
761 : else
762 0 : fprintf (file, ", points-to anything");
763 :
764 485 : fprintf (file, "\n");
765 485 : }
766 :
767 :
768 : /* Dump points-to information for VAR into stderr. */
769 :
770 : DEBUG_FUNCTION void
771 0 : debug_points_to_info_for (tree var)
772 : {
773 0 : dump_points_to_info_for (stderr, var);
774 0 : }
775 :
776 :
777 : /* Initializes the alias-oracle reference representation *R from REF. */
778 :
779 : void
780 2863427770 : ao_ref_init (ao_ref *r, tree ref)
781 : {
782 2863427770 : r->ref = ref;
783 2863427770 : r->base = NULL_TREE;
784 2863427770 : r->offset = 0;
785 2863427770 : r->size = -1;
786 2863427770 : r->max_size = -1;
787 2863427770 : r->ref_alias_set = -1;
788 2863427770 : r->base_alias_set = -1;
789 2863427770 : r->volatile_p = ref ? TREE_THIS_VOLATILE (ref) : false;
790 2863427770 : }
791 :
792 : /* Returns the base object of the memory reference *REF. */
793 :
794 : tree
795 5594317377 : ao_ref_base (ao_ref *ref)
796 : {
797 5594317377 : bool reverse;
798 :
799 5594317377 : if (ref->base)
800 : return ref->base;
801 2590248782 : ref->base = get_ref_base_and_extent (ref->ref, &ref->offset, &ref->size,
802 : &ref->max_size, &reverse);
803 2590248782 : return ref->base;
804 : }
805 :
806 : /* Returns the base object alias set of the memory reference *REF. */
807 :
808 : alias_set_type
809 1035583038 : ao_ref_base_alias_set (ao_ref *ref)
810 : {
811 1035583038 : tree base_ref;
812 1035583038 : if (ref->base_alias_set != -1)
813 : return ref->base_alias_set;
814 799584459 : if (!ref->ref)
815 : return 0;
816 762061028 : base_ref = ref->ref;
817 762061028 : if (TREE_CODE (base_ref) == WITH_SIZE_EXPR)
818 4 : base_ref = TREE_OPERAND (base_ref, 0);
819 1224261355 : while (handled_component_p (base_ref))
820 462200327 : base_ref = TREE_OPERAND (base_ref, 0);
821 762061028 : ref->base_alias_set = get_alias_set (base_ref);
822 762061028 : return ref->base_alias_set;
823 : }
824 :
825 : /* Returns the reference alias set of the memory reference *REF. */
826 :
827 : alias_set_type
828 1318417530 : ao_ref_alias_set (ao_ref *ref)
829 : {
830 1318417530 : if (ref->ref_alias_set != -1)
831 : return ref->ref_alias_set;
832 529561522 : if (!ref->ref)
833 : return 0;
834 529561520 : ref->ref_alias_set = get_alias_set (ref->ref);
835 529561520 : return ref->ref_alias_set;
836 : }
837 :
838 : /* Returns a type satisfying
839 : get_deref_alias_set (type) == ao_ref_base_alias_set (REF). */
840 :
841 : tree
842 326565 : ao_ref_base_alias_ptr_type (ao_ref *ref)
843 : {
844 326565 : tree base_ref;
845 :
846 326565 : if (!ref->ref)
847 : return NULL_TREE;
848 326565 : base_ref = ref->ref;
849 326565 : if (TREE_CODE (base_ref) == WITH_SIZE_EXPR)
850 0 : base_ref = TREE_OPERAND (base_ref, 0);
851 436014 : while (handled_component_p (base_ref))
852 109449 : base_ref = TREE_OPERAND (base_ref, 0);
853 326565 : tree ret = reference_alias_ptr_type (base_ref);
854 326565 : return ret;
855 : }
856 :
857 : /* Returns a type satisfying
858 : get_deref_alias_set (type) == ao_ref_alias_set (REF). */
859 :
860 : tree
861 326565 : ao_ref_alias_ptr_type (ao_ref *ref)
862 : {
863 326565 : if (!ref->ref)
864 : return NULL_TREE;
865 326565 : tree ret = reference_alias_ptr_type (ref->ref);
866 326565 : return ret;
867 : }
868 :
869 : /* Return the alignment of the access *REF and store it in the *ALIGN
870 : and *BITPOS pairs. Returns false if no alignment could be determined.
871 : See get_object_alignment_2 for details. */
872 :
873 : bool
874 95386 : ao_ref_alignment (ao_ref *ref, unsigned int *align,
875 : unsigned HOST_WIDE_INT *bitpos)
876 : {
877 95386 : if (ref->ref)
878 93776 : return get_object_alignment_1 (ref->ref, align, bitpos);
879 :
880 : /* When we just have ref->base we cannot use get_object_alignment since
881 : that will eventually use the type of the apparent access while for
882 : example ao_ref_init_from_ptr_and_range is not careful to adjust that. */
883 1610 : *align = BITS_PER_UNIT;
884 1610 : HOST_WIDE_INT offset;
885 1610 : if (!ref->offset.is_constant (&offset)
886 1610 : || !get_object_alignment_2 (ref->base, align, bitpos, true))
887 : return false;
888 1378 : *bitpos += (unsigned HOST_WIDE_INT)offset * BITS_PER_UNIT;
889 1378 : *bitpos = *bitpos & (*align - 1);
890 1378 : return true;
891 : }
892 :
893 : /* Init an alias-oracle reference representation from a gimple pointer
894 : PTR a range specified by OFFSET, SIZE and MAX_SIZE under the assumption
895 : that RANGE_KNOWN is set.
896 :
897 : The access is assumed to be only to or after of the pointer target adjusted
898 : by the offset, not before it (even in the case RANGE_KNOWN is false). */
899 :
900 : void
901 40054434 : ao_ref_init_from_ptr_and_range (ao_ref *ref, tree ptr,
902 : bool range_known,
903 : poly_int64 offset,
904 : poly_int64 size,
905 : poly_int64 max_size)
906 : {
907 40054434 : poly_int64 t, extra_offset = 0;
908 :
909 40054434 : ref->ref = NULL_TREE;
910 40054434 : if (TREE_CODE (ptr) == SSA_NAME)
911 : {
912 26979575 : gimple *stmt = SSA_NAME_DEF_STMT (ptr);
913 26979575 : if (gimple_assign_single_p (stmt)
914 26979575 : && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
915 4063543 : ptr = gimple_assign_rhs1 (stmt);
916 22916032 : else if (is_gimple_assign (stmt)
917 15422132 : && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
918 28900667 : && ptrdiff_tree_p (gimple_assign_rhs2 (stmt), &extra_offset))
919 : {
920 384206 : ptr = gimple_assign_rhs1 (stmt);
921 384206 : extra_offset *= BITS_PER_UNIT;
922 : }
923 : }
924 :
925 40054434 : if (TREE_CODE (ptr) == ADDR_EXPR)
926 : {
927 17070952 : ref->base = get_addr_base_and_unit_offset (TREE_OPERAND (ptr, 0), &t);
928 17070952 : if (ref->base
929 31298265 : && coeffs_in_range_p (t, -HOST_WIDE_INT_MAX / BITS_PER_UNIT,
930 : HOST_WIDE_INT_MAX / BITS_PER_UNIT))
931 14227135 : ref->offset = BITS_PER_UNIT * t;
932 : else
933 : {
934 2843817 : range_known = false;
935 2843817 : ref->offset = 0;
936 2843817 : ref->base = get_base_address (TREE_OPERAND (ptr, 0));
937 : }
938 : }
939 : else
940 : {
941 22983482 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
942 22983482 : ref->base = build2 (MEM_REF, char_type_node,
943 : ptr, null_pointer_node);
944 22983482 : ref->offset = 0;
945 : }
946 40054434 : ref->offset += extra_offset + offset;
947 40054434 : if (range_known)
948 : {
949 20688111 : ref->max_size = max_size;
950 20688111 : ref->size = size;
951 : }
952 : else
953 19366323 : ref->max_size = ref->size = -1;
954 40054434 : ref->ref_alias_set = 0;
955 40054434 : ref->base_alias_set = 0;
956 40054434 : ref->volatile_p = false;
957 40054434 : }
958 :
959 : /* Init an alias-oracle reference representation from a gimple pointer
960 : PTR and a gimple size SIZE in bytes. If SIZE is NULL_TREE then the
961 : size is assumed to be unknown. The access is assumed to be only
962 : to or after of the pointer target, not before it. */
963 :
964 : void
965 10634380 : ao_ref_init_from_ptr_and_size (ao_ref *ref, tree ptr, tree size)
966 : {
967 10634380 : poly_int64 size_hwi;
968 10634380 : if (size
969 5233691 : && poly_int_tree_p (size, &size_hwi)
970 15155918 : && coeffs_in_range_p (size_hwi, 0, HOST_WIDE_INT_MAX / BITS_PER_UNIT))
971 : {
972 4520846 : size_hwi = size_hwi * BITS_PER_UNIT;
973 4520846 : ao_ref_init_from_ptr_and_range (ref, ptr, true, 0, size_hwi, size_hwi);
974 : }
975 : else
976 6113534 : ao_ref_init_from_ptr_and_range (ref, ptr, false, 0, -1, -1);
977 10634380 : }
978 :
979 : /* S1 and S2 are TYPE_SIZE or DECL_SIZE. Compare them:
980 : Return -1 if S1 < S2
981 : Return 1 if S1 > S2
982 : Return 0 if equal or incomparable. */
983 :
984 : static int
985 8863384 : compare_sizes (tree s1, tree s2)
986 : {
987 8863384 : if (!s1 || !s2)
988 : return 0;
989 :
990 8852938 : poly_uint64 size1;
991 8852938 : poly_uint64 size2;
992 :
993 8852938 : if (!poly_int_tree_p (s1, &size1) || !poly_int_tree_p (s2, &size2))
994 542 : return 0;
995 8852396 : if (known_lt (size1, size2))
996 : return -1;
997 6344926 : if (known_lt (size2, size1))
998 : return 1;
999 : return 0;
1000 : }
1001 :
1002 : /* Compare TYPE1 and TYPE2 by its size.
1003 : Return -1 if size of TYPE1 < size of TYPE2
1004 : Return 1 if size of TYPE1 > size of TYPE2
1005 : Return 0 if types are of equal sizes or we can not compare them. */
1006 :
1007 : static int
1008 7527278 : compare_type_sizes (tree type1, tree type2)
1009 : {
1010 : /* Be conservative for arrays and vectors. We want to support partial
1011 : overlap on int[3] and int[3] as tested in gcc.dg/torture/alias-2.c. */
1012 7527278 : while (TREE_CODE (type1) == ARRAY_TYPE
1013 8278280 : || VECTOR_TYPE_P (type1))
1014 751002 : type1 = TREE_TYPE (type1);
1015 7716879 : while (TREE_CODE (type2) == ARRAY_TYPE
1016 7716879 : || VECTOR_TYPE_P (type2))
1017 189601 : type2 = TREE_TYPE (type2);
1018 7527278 : return compare_sizes (TYPE_SIZE (type1), TYPE_SIZE (type2));
1019 : }
1020 :
1021 : /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
1022 : purpose of TBAA. Return 0 if they are distinct and -1 if we cannot
1023 : decide. */
1024 :
1025 : static inline int
1026 871771360 : same_type_for_tbaa (tree type1, tree type2)
1027 : {
1028 871771360 : type1 = TYPE_MAIN_VARIANT (type1);
1029 871771360 : type2 = TYPE_MAIN_VARIANT (type2);
1030 :
1031 : /* Handle the most common case first. */
1032 871771360 : if (type1 == type2)
1033 : return 1;
1034 :
1035 : /* If we would have to do structural comparison bail out. */
1036 137917951 : if (TYPE_STRUCTURAL_EQUALITY_P (type1)
1037 137917951 : || TYPE_STRUCTURAL_EQUALITY_P (type2))
1038 : return -1;
1039 :
1040 : /* Compare the canonical types. */
1041 85449569 : if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
1042 : return 1;
1043 :
1044 : /* ??? Array types are not properly unified in all cases as we have
1045 : spurious changes in the index types for example. Removing this
1046 : causes all sorts of problems with the Fortran frontend. */
1047 84594540 : if (TREE_CODE (type1) == ARRAY_TYPE
1048 4907782 : && TREE_CODE (type2) == ARRAY_TYPE)
1049 : return -1;
1050 :
1051 : /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
1052 : object of one of its constrained subtypes, e.g. when a function with an
1053 : unconstrained parameter passed by reference is called on an object and
1054 : inlined. But, even in the case of a fixed size, type and subtypes are
1055 : not equivalent enough as to share the same TYPE_CANONICAL, since this
1056 : would mean that conversions between them are useless, whereas they are
1057 : not (e.g. type and subtypes can have different modes). So, in the end,
1058 : they are only guaranteed to have the same alias set. */
1059 84290045 : alias_set_type set1 = get_alias_set (type1);
1060 84290045 : alias_set_type set2 = get_alias_set (type2);
1061 84290045 : if (set1 == set2)
1062 : return -1;
1063 :
1064 : /* Pointers to void are considered compatible with all other pointers,
1065 : so for two pointers see what the alias set resolution thinks. */
1066 47208067 : if (POINTER_TYPE_P (type1)
1067 10883144 : && POINTER_TYPE_P (type2)
1068 47386426 : && alias_sets_conflict_p (set1, set2))
1069 : return -1;
1070 :
1071 : /* The types are known to be not equal. */
1072 : return 0;
1073 : }
1074 :
1075 : /* Return true if TYPE is a composite type (i.e. we may apply one of handled
1076 : components on it). */
1077 :
1078 : static bool
1079 1948892 : type_has_components_p (tree type)
1080 : {
1081 1948892 : return AGGREGATE_TYPE_P (type) || VECTOR_TYPE_P (type)
1082 1948892 : || TREE_CODE (type) == COMPLEX_TYPE;
1083 : }
1084 :
1085 : /* MATCH1 and MATCH2 which are part of access path of REF1 and REF2
1086 : respectively are either pointing to same address or are completely
1087 : disjoint. If PARTIAL_OVERLAP is true, assume that outermost arrays may
1088 : just partly overlap.
1089 :
1090 : Try to disambiguate using the access path starting from the match
1091 : and return false if there is no conflict.
1092 :
1093 : Helper for aliasing_component_refs_p. */
1094 :
1095 : static bool
1096 917466 : aliasing_matching_component_refs_p (tree match1, tree ref1,
1097 : poly_int64 offset1, poly_int64 max_size1,
1098 : tree match2, tree ref2,
1099 : poly_int64 offset2, poly_int64 max_size2,
1100 : bool partial_overlap)
1101 : {
1102 917466 : poly_int64 offadj, sztmp, msztmp;
1103 917466 : bool reverse;
1104 :
1105 917466 : if (!partial_overlap)
1106 : {
1107 917462 : get_ref_base_and_extent (match2, &offadj, &sztmp, &msztmp, &reverse);
1108 917462 : offset2 -= offadj;
1109 917462 : get_ref_base_and_extent (match1, &offadj, &sztmp, &msztmp, &reverse);
1110 917462 : offset1 -= offadj;
1111 917462 : if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
1112 : {
1113 62912 : ++alias_stats.aliasing_component_refs_p_no_alias;
1114 62912 : return false;
1115 : }
1116 : }
1117 :
1118 854554 : int cmp = nonoverlapping_refs_since_match_p (match1, ref1, match2, ref2,
1119 : partial_overlap);
1120 854554 : if (cmp == 1
1121 854554 : || (cmp == -1 && nonoverlapping_component_refs_p (ref1, ref2)))
1122 : {
1123 322 : ++alias_stats.aliasing_component_refs_p_no_alias;
1124 322 : return false;
1125 : }
1126 854232 : ++alias_stats.aliasing_component_refs_p_may_alias;
1127 854232 : return true;
1128 : }
1129 :
1130 : /* Return true if REF is reference to zero sized trailing array. I.e.
1131 : struct foo {int bar; int array[0];} *fooptr;
1132 : fooptr->array. */
1133 :
1134 : static bool
1135 6112013 : component_ref_to_zero_sized_trailing_array_p (tree ref)
1136 : {
1137 6112013 : return (TREE_CODE (ref) == COMPONENT_REF
1138 5503361 : && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 1))) == ARRAY_TYPE
1139 123924 : && (!TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)))
1140 39612 : || integer_zerop (TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)))))
1141 6196402 : && array_ref_flexible_size_p (ref));
1142 : }
1143 :
1144 : /* Worker for aliasing_component_refs_p. Most parameters match parameters of
1145 : aliasing_component_refs_p.
1146 :
1147 : Walk access path REF2 and try to find type matching TYPE1
1148 : (which is a start of possibly aliasing access path REF1).
1149 : If match is found, try to disambiguate.
1150 :
1151 : Return 0 for successful disambiguation.
1152 : Return 1 if match was found but disambiguation failed
1153 : Return -1 if there is no match.
1154 : In this case MAYBE_MATCH is set to 0 if there is no type matching TYPE1
1155 : in access patch REF2 and -1 if we are not sure. */
1156 :
1157 : static int
1158 2596581 : aliasing_component_refs_walk (tree ref1, tree type1, tree base1,
1159 : poly_int64 offset1, poly_int64 max_size1,
1160 : tree end_struct_ref1,
1161 : tree ref2, tree base2,
1162 : poly_int64 offset2, poly_int64 max_size2,
1163 : bool *maybe_match)
1164 : {
1165 2596581 : tree ref = ref2;
1166 2596581 : int same_p = 0;
1167 :
1168 7350151 : while (true)
1169 : {
1170 : /* We walk from inner type to the outer types. If type we see is
1171 : already too large to be part of type1, terminate the search. */
1172 4973366 : int cmp = compare_type_sizes (type1, TREE_TYPE (ref));
1173 :
1174 4973366 : if (cmp < 0
1175 4973366 : && (!end_struct_ref1
1176 60 : || compare_type_sizes (TREE_TYPE (end_struct_ref1),
1177 60 : TREE_TYPE (ref)) < 0))
1178 : break;
1179 : /* If types may be of same size, see if we can decide about their
1180 : equality. */
1181 3622573 : if (cmp == 0)
1182 : {
1183 2630826 : same_p = same_type_for_tbaa (TREE_TYPE (ref), type1);
1184 2630826 : if (same_p == 1)
1185 : break;
1186 : /* In case we can't decide whether types are same try to
1187 : continue looking for the exact match.
1188 : Remember however that we possibly saw a match
1189 : to bypass the access path continuations tests we do later. */
1190 1713360 : if (same_p == -1)
1191 626565 : *maybe_match = true;
1192 : }
1193 2705107 : if (!handled_component_p (ref))
1194 : break;
1195 2376785 : ref = TREE_OPERAND (ref, 0);
1196 2376785 : }
1197 2596581 : if (same_p == 1)
1198 : {
1199 917466 : bool partial_overlap = false;
1200 :
1201 : /* We assume that arrays can overlap by multiple of their elements
1202 : size as tested in gcc.dg/torture/alias-2.c.
1203 : This partial overlap happen only when both arrays are bases of
1204 : the access and not contained within another component ref.
1205 : To be safe we also assume partial overlap for VLAs. */
1206 917466 : if (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE
1207 917466 : && (!TYPE_SIZE (TREE_TYPE (base1))
1208 1797 : || TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) != INTEGER_CST
1209 1797 : || ref == base2))
1210 : {
1211 : /* Setting maybe_match to true triggers
1212 : nonoverlapping_component_refs_p test later that still may do
1213 : useful disambiguation. */
1214 4 : *maybe_match = true;
1215 4 : partial_overlap = true;
1216 : }
1217 917466 : return aliasing_matching_component_refs_p (base1, ref1,
1218 : offset1, max_size1,
1219 : ref, ref2,
1220 : offset2, max_size2,
1221 917466 : partial_overlap);
1222 : }
1223 : return -1;
1224 : }
1225 :
1226 : /* Consider access path1 base1....ref1 and access path2 base2...ref2.
1227 : Return true if they can be composed to single access path
1228 : base1...ref1...base2...ref2.
1229 :
1230 : REF_TYPE1 if type of REF1. END_STRUCT_PAST_END1 is true if there is
1231 : a trailing array access after REF1 in the non-TBAA part of the access.
1232 : REF1_ALIAS_SET is the alias set of REF1.
1233 :
1234 : BASE_TYPE2 is type of base2. END_STRUCT_REF2 is non-NULL if there is
1235 : a trailing array access in the TBAA part of access path2.
1236 : BASE2_ALIAS_SET is the alias set of base2. */
1237 :
1238 : bool
1239 1948892 : access_path_may_continue_p (tree ref_type1, bool end_struct_past_end1,
1240 : alias_set_type ref1_alias_set,
1241 : tree base_type2, tree end_struct_ref2,
1242 : alias_set_type base2_alias_set)
1243 : {
1244 : /* Access path can not continue past types with no components. */
1245 1948892 : if (!type_has_components_p (ref_type1))
1246 : return false;
1247 :
1248 : /* If first access path ends by too small type to hold base of
1249 : the second access path, typically paths can not continue.
1250 :
1251 : Punt if end_struct_past_end1 is true. We want to support arbitrary
1252 : type puning past first COMPONENT_REF to union because redundant store
1253 : elimination depends on this, see PR92152. For this reason we can not
1254 : check size of the reference because types may partially overlap. */
1255 176109 : if (!end_struct_past_end1)
1256 : {
1257 176060 : if (compare_type_sizes (ref_type1, base_type2) < 0)
1258 : return false;
1259 : /* If the path2 contains trailing array access we can strengthen the check
1260 : to verify that also the size of element of the trailing array fits.
1261 : In fact we could check for offset + type_size, but we do not track
1262 : offsets and this is quite side case. */
1263 159695 : if (end_struct_ref2
1264 159695 : && compare_type_sizes (ref_type1, TREE_TYPE (end_struct_ref2)) < 0)
1265 : return false;
1266 : }
1267 159744 : return (base2_alias_set == ref1_alias_set
1268 159744 : || alias_set_subset_of (base2_alias_set, ref1_alias_set));
1269 : }
1270 :
1271 : /* Determine if the two component references REF1 and REF2 which are
1272 : based on access types TYPE1 and TYPE2 and of which at least one is based
1273 : on an indirect reference may alias.
1274 : REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
1275 : are the respective alias sets. */
1276 :
1277 : static bool
1278 2377731 : aliasing_component_refs_p (tree ref1,
1279 : alias_set_type ref1_alias_set,
1280 : alias_set_type base1_alias_set,
1281 : poly_int64 offset1, poly_int64 max_size1,
1282 : tree ref2,
1283 : alias_set_type ref2_alias_set,
1284 : alias_set_type base2_alias_set,
1285 : poly_int64 offset2, poly_int64 max_size2)
1286 : {
1287 : /* If one reference is a component references through pointers try to find a
1288 : common base and apply offset based disambiguation. This handles
1289 : for example
1290 : struct A { int i; int j; } *q;
1291 : struct B { struct A a; int k; } *p;
1292 : disambiguating q->i and p->a.j. */
1293 2377731 : tree base1, base2;
1294 2377731 : tree type1, type2;
1295 2377731 : bool maybe_match = false;
1296 2377731 : tree end_struct_ref1 = NULL, end_struct_ref2 = NULL;
1297 2377731 : bool end_struct_past_end1 = false;
1298 2377731 : bool end_struct_past_end2 = false;
1299 :
1300 : /* Choose bases and base types to search for.
1301 : The access path is as follows:
1302 : base....end_of_tbaa_ref...actual_ref
1303 : At one place in the access path may be a reference to zero sized or
1304 : trailing array.
1305 :
1306 : We generally discard the segment after end_of_tbaa_ref however
1307 : we need to be careful in case it contains zero sized or trailing array.
1308 : These may happen after reference to union and in this case we need to
1309 : not disambiguate type puning scenarios.
1310 :
1311 : We set:
1312 : base1 to point to base
1313 :
1314 : ref1 to point to end_of_tbaa_ref
1315 :
1316 : end_struct_ref1 to point the trailing reference (if it exists
1317 : in range base....end_of_tbaa_ref
1318 :
1319 : end_struct_past_end1 is true if this trailing reference occurs in
1320 : end_of_tbaa_ref...actual_ref. */
1321 2377731 : base1 = ref1;
1322 5014047 : while (handled_component_p (base1))
1323 : {
1324 : /* Generally access paths are monotous in the size of object. The
1325 : exception are trailing arrays of structures. I.e.
1326 : struct a {int array[0];};
1327 : or
1328 : struct a {int array1[0]; int array[];};
1329 : Such struct has size 0 but accesses to a.array may have non-zero size.
1330 : In this case the size of TREE_TYPE (base1) is smaller than
1331 : size of TREE_TYPE (TREE_OPERAND (base1, 0)).
1332 :
1333 : Because we compare sizes of arrays just by sizes of their elements,
1334 : we only need to care about zero sized array fields here. */
1335 2636316 : if (component_ref_to_zero_sized_trailing_array_p (base1))
1336 : {
1337 74663 : gcc_checking_assert (!end_struct_ref1);
1338 : end_struct_ref1 = base1;
1339 : }
1340 2636316 : if (ends_tbaa_access_path_p (base1))
1341 : {
1342 26735 : ref1 = TREE_OPERAND (base1, 0);
1343 26735 : if (end_struct_ref1)
1344 : {
1345 1 : end_struct_past_end1 = true;
1346 1 : end_struct_ref1 = NULL;
1347 : }
1348 : }
1349 2636316 : base1 = TREE_OPERAND (base1, 0);
1350 : }
1351 2377731 : type1 = TREE_TYPE (base1);
1352 2377731 : base2 = ref2;
1353 5510274 : while (handled_component_p (base2))
1354 : {
1355 3132543 : if (component_ref_to_zero_sized_trailing_array_p (base2))
1356 : {
1357 9465 : gcc_checking_assert (!end_struct_ref2);
1358 : end_struct_ref2 = base2;
1359 : }
1360 3132543 : if (ends_tbaa_access_path_p (base2))
1361 : {
1362 98355 : ref2 = TREE_OPERAND (base2, 0);
1363 98355 : if (end_struct_ref2)
1364 : {
1365 48 : end_struct_past_end2 = true;
1366 48 : end_struct_ref2 = NULL;
1367 : }
1368 : }
1369 3132543 : base2 = TREE_OPERAND (base2, 0);
1370 : }
1371 2377731 : type2 = TREE_TYPE (base2);
1372 :
1373 : /* Now search for the type1 in the access path of ref2. This
1374 : would be a common base for doing offset based disambiguation on.
1375 : This however only makes sense if type2 is big enough to hold type1. */
1376 2377731 : int cmp_outer = compare_type_sizes (type2, type1);
1377 :
1378 : /* If type2 is big enough to contain type1 walk its access path.
1379 : We also need to care of arrays at the end of structs that may extend
1380 : beyond the end of structure. If this occurs in the TBAA part of the
1381 : access path, we need to consider the increased type as well. */
1382 2377731 : if (cmp_outer >= 0
1383 2377731 : || (end_struct_ref2
1384 1 : && compare_type_sizes (TREE_TYPE (end_struct_ref2), type1) >= 0))
1385 : {
1386 1271091 : int res = aliasing_component_refs_walk (ref1, type1, base1,
1387 : offset1, max_size1,
1388 : end_struct_ref1,
1389 : ref2, base2, offset2, max_size2,
1390 : &maybe_match);
1391 1271091 : if (res != -1)
1392 607804 : return res;
1393 : }
1394 :
1395 : /* If we didn't find a common base, try the other way around. */
1396 1769927 : if (cmp_outer <= 0
1397 1769927 : || (end_struct_ref1
1398 60 : && compare_type_sizes (TREE_TYPE (end_struct_ref1), type2) <= 0))
1399 : {
1400 1325490 : int res = aliasing_component_refs_walk (ref2, type2, base2,
1401 : offset2, max_size2,
1402 : end_struct_ref2,
1403 : ref1, base1, offset1, max_size1,
1404 : &maybe_match);
1405 1325490 : if (res != -1)
1406 309662 : return res;
1407 : }
1408 :
1409 : /* In the following code we make an assumption that the types in access
1410 : paths do not overlap and thus accesses alias only if one path can be
1411 : continuation of another. If we was not able to decide about equivalence,
1412 : we need to give up. */
1413 1460265 : if (maybe_match)
1414 : {
1415 470918 : if (!nonoverlapping_component_refs_p (ref1, ref2))
1416 : {
1417 469110 : ++alias_stats.aliasing_component_refs_p_may_alias;
1418 469110 : return true;
1419 : }
1420 1808 : ++alias_stats.aliasing_component_refs_p_no_alias;
1421 1808 : return false;
1422 : }
1423 :
1424 989347 : if (access_path_may_continue_p (TREE_TYPE (ref1), end_struct_past_end1,
1425 : ref1_alias_set,
1426 : type2, end_struct_ref2,
1427 : base2_alias_set)
1428 989347 : || access_path_may_continue_p (TREE_TYPE (ref2), end_struct_past_end2,
1429 : ref2_alias_set,
1430 : type1, end_struct_ref1,
1431 : base1_alias_set))
1432 : {
1433 158889 : ++alias_stats.aliasing_component_refs_p_may_alias;
1434 158889 : return true;
1435 : }
1436 830458 : ++alias_stats.aliasing_component_refs_p_no_alias;
1437 830458 : return false;
1438 : }
1439 :
1440 : /* FIELD1 and FIELD2 are two fields of component refs. We assume
1441 : that bases of both component refs are either equivalent or nonoverlapping.
1442 : We do not assume that the containers of FIELD1 and FIELD2 are of the
1443 : same type or size.
1444 :
1445 : Return 0 in case the base address of component_refs are same then
1446 : FIELD1 and FIELD2 have same address. Note that FIELD1 and FIELD2
1447 : may not be of same type or size.
1448 :
1449 : Return 1 if FIELD1 and FIELD2 are non-overlapping.
1450 :
1451 : Return -1 otherwise.
1452 :
1453 : Main difference between 0 and -1 is to let
1454 : nonoverlapping_component_refs_since_match_p discover the semantically
1455 : equivalent part of the access path.
1456 :
1457 : Note that this function is used even with -fno-strict-aliasing
1458 : and makes use of no TBAA assumptions. */
1459 :
1460 : static int
1461 3401998 : nonoverlapping_component_refs_p_1 (const_tree field1, const_tree field2)
1462 : {
1463 : /* If both fields are of the same type, we could save hard work of
1464 : comparing offsets. */
1465 3401998 : tree type1 = DECL_CONTEXT (field1);
1466 3401998 : tree type2 = DECL_CONTEXT (field2);
1467 :
1468 3401998 : if (TREE_CODE (type1) == RECORD_TYPE
1469 6670068 : && DECL_BIT_FIELD_REPRESENTATIVE (field1))
1470 : field1 = DECL_BIT_FIELD_REPRESENTATIVE (field1);
1471 3401998 : if (TREE_CODE (type2) == RECORD_TYPE
1472 6670068 : && DECL_BIT_FIELD_REPRESENTATIVE (field2))
1473 : field2 = DECL_BIT_FIELD_REPRESENTATIVE (field2);
1474 :
1475 : /* ??? Bitfields can overlap at RTL level so punt on them.
1476 : FIXME: RTL expansion should be fixed by adjusting the access path
1477 : when producing MEM_ATTRs for MEMs which are wider than
1478 : the bitfields similarly as done in set_mem_attrs_minus_bitpos. */
1479 3401998 : if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
1480 : return -1;
1481 :
1482 : /* Assume that different FIELD_DECLs never overlap within a RECORD_TYPE. */
1483 3401998 : if (type1 == type2 && TREE_CODE (type1) == RECORD_TYPE)
1484 3245176 : return field1 != field2;
1485 :
1486 : /* In common case the offsets and bit offsets will be the same.
1487 : However if frontends do not agree on the alignment, they may be
1488 : different even if they actually represent same address.
1489 : Try the common case first and if that fails calculate the
1490 : actual bit offset. */
1491 156822 : if (tree_int_cst_equal (DECL_FIELD_OFFSET (field1),
1492 156822 : DECL_FIELD_OFFSET (field2))
1493 288856 : && tree_int_cst_equal (DECL_FIELD_BIT_OFFSET (field1),
1494 132034 : DECL_FIELD_BIT_OFFSET (field2)))
1495 : return 0;
1496 :
1497 : /* Note that it may be possible to use component_ref_field_offset
1498 : which would provide offsets as trees. However constructing and folding
1499 : trees is expensive and does not seem to be worth the compile time
1500 : cost. */
1501 :
1502 25513 : poly_uint64 offset1, offset2;
1503 25513 : poly_uint64 bit_offset1, bit_offset2;
1504 :
1505 25513 : if (poly_int_tree_p (DECL_FIELD_OFFSET (field1), &offset1)
1506 25513 : && poly_int_tree_p (DECL_FIELD_OFFSET (field2), &offset2)
1507 25513 : && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field1), &bit_offset1)
1508 51026 : && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field2), &bit_offset2))
1509 : {
1510 25513 : offset1 = (offset1 << LOG2_BITS_PER_UNIT) + bit_offset1;
1511 25513 : offset2 = (offset2 << LOG2_BITS_PER_UNIT) + bit_offset2;
1512 :
1513 25513 : if (known_eq (offset1, offset2))
1514 22091 : return 0;
1515 :
1516 25513 : poly_uint64 size1, size2;
1517 :
1518 25513 : if (poly_int_tree_p (DECL_SIZE (field1), &size1)
1519 25513 : && poly_int_tree_p (DECL_SIZE (field2), &size2)
1520 51026 : && !ranges_maybe_overlap_p (offset1, size1, offset2, size2))
1521 : return 1;
1522 : }
1523 : /* Resort to slower overlap checking by looking for matching types in
1524 : the middle of access path. */
1525 : return -1;
1526 : }
1527 :
1528 : /* Return low bound of array. Do not produce new trees
1529 : and thus do not care about particular type of integer constant
1530 : and placeholder exprs. */
1531 :
1532 : static tree
1533 17530201 : cheap_array_ref_low_bound (tree ref)
1534 : {
1535 17530201 : tree domain_type = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (ref, 0)));
1536 :
1537 : /* Avoid expensive array_ref_low_bound.
1538 : low bound is either stored in operand2, or it is TYPE_MIN_VALUE of domain
1539 : type or it is zero. */
1540 17530201 : if (TREE_OPERAND (ref, 2))
1541 80949 : return TREE_OPERAND (ref, 2);
1542 17449252 : else if (domain_type && TYPE_MIN_VALUE (domain_type))
1543 17442338 : return TYPE_MIN_VALUE (domain_type);
1544 : else
1545 6914 : return integer_zero_node;
1546 : }
1547 :
1548 : /* REF1 and REF2 are ARRAY_REFs with either same base address or which are
1549 : completely disjoint.
1550 :
1551 : Return 1 if the refs are non-overlapping.
1552 : Return 0 if they are possibly overlapping but if so the overlap again
1553 : starts on the same address.
1554 : Return -1 otherwise. */
1555 :
1556 : int
1557 8747548 : nonoverlapping_array_refs_p (tree ref1, tree ref2)
1558 : {
1559 8747548 : tree index1 = TREE_OPERAND (ref1, 1);
1560 8747548 : tree index2 = TREE_OPERAND (ref2, 1);
1561 8747548 : tree low_bound1 = cheap_array_ref_low_bound (ref1);
1562 8747548 : tree low_bound2 = cheap_array_ref_low_bound (ref2);
1563 :
1564 : /* Handle zero offsets first: we do not need to match type size in this
1565 : case. */
1566 8747548 : if (operand_equal_p (index1, low_bound1, 0)
1567 8747548 : && operand_equal_p (index2, low_bound2, 0))
1568 : return 0;
1569 :
1570 : /* If type sizes are different, give up.
1571 :
1572 : Avoid expensive array_ref_element_size.
1573 : If operand 3 is present it denotes size in the alignment units.
1574 : Otherwise size is TYPE_SIZE of the element type.
1575 : Handle only common cases where types are of the same "kind". */
1576 8670516 : if ((TREE_OPERAND (ref1, 3) == NULL) != (TREE_OPERAND (ref2, 3) == NULL))
1577 : return -1;
1578 :
1579 8670516 : tree elmt_type1 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref1, 0)));
1580 8670516 : tree elmt_type2 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref2, 0)));
1581 :
1582 8670516 : if (TREE_OPERAND (ref1, 3))
1583 : {
1584 4216 : if (TYPE_ALIGN (elmt_type1) != TYPE_ALIGN (elmt_type2)
1585 8432 : || !operand_equal_p (TREE_OPERAND (ref1, 3),
1586 4216 : TREE_OPERAND (ref2, 3), 0))
1587 646 : return -1;
1588 : }
1589 : else
1590 : {
1591 8666300 : if (!operand_equal_p (TYPE_SIZE_UNIT (elmt_type1),
1592 8666300 : TYPE_SIZE_UNIT (elmt_type2), 0))
1593 : return -1;
1594 : }
1595 :
1596 : /* Since we know that type sizes are the same, there is no need to return
1597 : -1 after this point. Partial overlap can not be introduced. */
1598 :
1599 : /* We may need to fold trees in this case.
1600 : TODO: Handle integer constant case at least. */
1601 8661828 : if (!operand_equal_p (low_bound1, low_bound2, 0))
1602 : return 0;
1603 :
1604 8661828 : if (TREE_CODE (index1) == INTEGER_CST && TREE_CODE (index2) == INTEGER_CST)
1605 : {
1606 311274 : if (tree_int_cst_equal (index1, index2))
1607 : return 0;
1608 : return 1;
1609 : }
1610 : /* TODO: We can use VRP to further disambiguate here. */
1611 : return 0;
1612 : }
1613 :
1614 : /* Try to disambiguate REF1 and REF2 under the assumption that MATCH1 and
1615 : MATCH2 either point to the same address or are disjoint.
1616 : MATCH1 and MATCH2 are assumed to be ref in the access path of REF1 and REF2
1617 : respectively or NULL in the case we established equivalence of bases.
1618 : If PARTIAL_OVERLAP is true assume that the toplevel arrays may actually
1619 : overlap by exact multiply of their element size.
1620 :
1621 : This test works by matching the initial segment of the access path
1622 : and does not rely on TBAA thus is safe for !flag_strict_aliasing if
1623 : match was determined without use of TBAA oracle.
1624 :
1625 : Return 1 if we can determine that component references REF1 and REF2,
1626 : that are within a common DECL, cannot overlap.
1627 :
1628 : Return 0 if paths are same and thus there is nothing to disambiguate more
1629 : (i.e. there is must alias assuming there is must alias between MATCH1 and
1630 : MATCH2)
1631 :
1632 : Return -1 if we can not determine 0 or 1 - this happens when we met
1633 : non-matching types was met in the path.
1634 : In this case it may make sense to continue by other disambiguation
1635 : oracles. */
1636 :
1637 : static int
1638 9225504 : nonoverlapping_refs_since_match_p (tree match1, tree ref1,
1639 : tree match2, tree ref2,
1640 : bool partial_overlap)
1641 : {
1642 9225504 : int ntbaa1 = 0, ntbaa2 = 0;
1643 : /* Early return if there are no references to match, we do not need
1644 : to walk the access paths.
1645 :
1646 : Do not consider this as may-alias for stats - it is more useful
1647 : to have information how many disambiguations happened provided that
1648 : the query was meaningful. */
1649 :
1650 8424433 : if (match1 == ref1 || !handled_component_p (ref1)
1651 17648371 : || match2 == ref2 || !handled_component_p (ref2))
1652 : return -1;
1653 :
1654 8404920 : auto_vec<tree, 16> component_refs1;
1655 8404920 : auto_vec<tree, 16> component_refs2;
1656 :
1657 : /* Create the stack of handled components for REF1. */
1658 21431053 : while (handled_component_p (ref1) && ref1 != match1)
1659 : {
1660 : /* We use TBAA only to re-synchronize after mismatched refs. So we
1661 : do not need to truncate access path after TBAA part ends. */
1662 13026133 : if (ends_tbaa_access_path_p (ref1))
1663 : ntbaa1 = 0;
1664 : else
1665 12807862 : ntbaa1++;
1666 13026133 : component_refs1.safe_push (ref1);
1667 13026133 : ref1 = TREE_OPERAND (ref1, 0);
1668 : }
1669 :
1670 : /* Create the stack of handled components for REF2. */
1671 21392976 : while (handled_component_p (ref2) && ref2 != match2)
1672 : {
1673 12988056 : if (ends_tbaa_access_path_p (ref2))
1674 : ntbaa2 = 0;
1675 : else
1676 12749233 : ntbaa2++;
1677 12988056 : component_refs2.safe_push (ref2);
1678 12988056 : ref2 = TREE_OPERAND (ref2, 0);
1679 : }
1680 :
1681 8404920 : if (!flag_strict_aliasing)
1682 : {
1683 493923 : ntbaa1 = 0;
1684 493923 : ntbaa2 = 0;
1685 : }
1686 :
1687 8404920 : bool mem_ref1 = TREE_CODE (ref1) == MEM_REF && ref1 != match1;
1688 8404920 : bool mem_ref2 = TREE_CODE (ref2) == MEM_REF && ref2 != match2;
1689 :
1690 : /* If only one of access path starts with MEM_REF check that offset is 0
1691 : so the addresses stays the same after stripping it.
1692 : TODO: In this case we may walk the other access path until we get same
1693 : offset.
1694 :
1695 : If both starts with MEM_REF, offset has to be same. */
1696 74082 : if ((mem_ref1 && !mem_ref2 && !integer_zerop (TREE_OPERAND (ref1, 1)))
1697 8377371 : || (mem_ref2 && !mem_ref1 && !integer_zerop (TREE_OPERAND (ref2, 1)))
1698 16771638 : || (mem_ref1 && mem_ref2
1699 1161760 : && !tree_int_cst_equal (TREE_OPERAND (ref1, 1),
1700 1161760 : TREE_OPERAND (ref2, 1))))
1701 : {
1702 64403 : ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1703 64403 : return -1;
1704 : }
1705 :
1706 : /* TARGET_MEM_REF are never wrapped in handled components, so we do not need
1707 : to handle them here at all. */
1708 8340517 : gcc_checking_assert (TREE_CODE (ref1) != TARGET_MEM_REF
1709 : && TREE_CODE (ref2) != TARGET_MEM_REF);
1710 :
1711 : /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
1712 : rank. This is sufficient because we start from the same DECL and you
1713 : cannot reference several fields at a time with COMPONENT_REFs (unlike
1714 : with ARRAY_RANGE_REFs for arrays) so you always need the same number
1715 : of them to access a sub-component, unless you're in a union, in which
1716 : case the return value will precisely be false. */
1717 10648019 : while (true)
1718 : {
1719 : /* Track if we seen unmatched ref with non-zero offset. In this case
1720 : we must look for partial overlaps. */
1721 10648019 : bool seen_unmatched_ref_p = false;
1722 :
1723 : /* First match ARRAY_REFs an try to disambiguate. */
1724 20586605 : if (!component_refs1.is_empty ()
1725 10379828 : && !component_refs2.is_empty ())
1726 : {
1727 19039916 : unsigned int narray_refs1=0, narray_refs2=0;
1728 :
1729 : /* We generally assume that both access paths starts by same sequence
1730 : of refs. However if number of array refs is not in sync, try
1731 : to recover and pop elts until number match. This helps the case
1732 : where one access path starts by array and other by element. */
1733 19039916 : for (narray_refs1 = 0; narray_refs1 < component_refs1.length ();
1734 : narray_refs1++)
1735 12672901 : if (TREE_CODE (component_refs1 [component_refs1.length()
1736 : - 1 - narray_refs1]) != ARRAY_REF)
1737 : break;
1738 :
1739 19044485 : for (narray_refs2 = 0; narray_refs2 < component_refs2.length ();
1740 : narray_refs2++)
1741 12683111 : if (TREE_CODE (component_refs2 [component_refs2.length()
1742 : - 1 - narray_refs2]) != ARRAY_REF)
1743 : break;
1744 9910167 : for (; narray_refs1 > narray_refs2; narray_refs1--)
1745 : {
1746 15268 : ref1 = component_refs1.pop ();
1747 15268 : ntbaa1--;
1748 :
1749 : /* If index is non-zero we need to check whether the reference
1750 : does not break the main invariant that bases are either
1751 : disjoint or equal. Consider the example:
1752 :
1753 : unsigned char out[][1];
1754 : out[1]="a";
1755 : out[i][0];
1756 :
1757 : Here bases out and out are same, but after removing the
1758 : [i] index, this invariant no longer holds, because
1759 : out[i] points to the middle of array out.
1760 :
1761 : TODO: If size of type of the skipped reference is an integer
1762 : multiply of the size of type of the other reference this
1763 : invariant can be verified, but even then it is not completely
1764 : safe with !flag_strict_aliasing if the other reference contains
1765 : unbounded array accesses.
1766 : See */
1767 :
1768 15268 : if (!operand_equal_p (TREE_OPERAND (ref1, 1),
1769 15268 : cheap_array_ref_low_bound (ref1), 0))
1770 : return 0;
1771 : }
1772 9894936 : for (; narray_refs2 > narray_refs1; narray_refs2--)
1773 : {
1774 19837 : ref2 = component_refs2.pop ();
1775 19837 : ntbaa2--;
1776 19837 : if (!operand_equal_p (TREE_OPERAND (ref2, 1),
1777 19837 : cheap_array_ref_low_bound (ref2), 0))
1778 : return 0;
1779 : }
1780 : /* Try to disambiguate matched arrays. */
1781 18388302 : for (unsigned int i = 0; i < narray_refs1; i++)
1782 : {
1783 17495096 : int cmp = nonoverlapping_array_refs_p (component_refs1.pop (),
1784 8747548 : component_refs2.pop ());
1785 8747548 : ntbaa1--;
1786 8747548 : ntbaa2--;
1787 8747548 : if (cmp == 1 && !partial_overlap)
1788 : {
1789 225657 : ++alias_stats
1790 225657 : .nonoverlapping_refs_since_match_p_no_alias;
1791 225657 : return 1;
1792 : }
1793 8521891 : if (cmp == -1)
1794 : {
1795 8688 : seen_unmatched_ref_p = true;
1796 : /* We can not maintain the invariant that bases are either
1797 : same or completely disjoint. However we can still recover
1798 : from type based alias analysis if we reach references to
1799 : same sizes. We do not attempt to match array sizes, so
1800 : just finish array walking and look for component refs. */
1801 8688 : if (ntbaa1 < 0 || ntbaa2 < 0)
1802 : {
1803 7823 : ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1804 7823 : return -1;
1805 : }
1806 1804 : for (i++; i < narray_refs1; i++)
1807 : {
1808 939 : component_refs1.pop ();
1809 939 : component_refs2.pop ();
1810 939 : ntbaa1--;
1811 939 : ntbaa2--;
1812 : }
1813 : break;
1814 : }
1815 8513203 : partial_overlap = false;
1816 : }
1817 : }
1818 :
1819 : /* Next look for component_refs. */
1820 10442869 : do
1821 : {
1822 10442869 : if (component_refs1.is_empty ())
1823 : {
1824 6917932 : ++alias_stats
1825 6917932 : .nonoverlapping_refs_since_match_p_must_overlap;
1826 6917932 : return 0;
1827 : }
1828 3524937 : ref1 = component_refs1.pop ();
1829 3524937 : ntbaa1--;
1830 3524937 : if (TREE_CODE (ref1) != COMPONENT_REF)
1831 : {
1832 106475 : seen_unmatched_ref_p = true;
1833 106475 : if (ntbaa1 < 0 || ntbaa2 < 0)
1834 : {
1835 43434 : ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1836 43434 : return -1;
1837 : }
1838 : }
1839 : }
1840 6899965 : while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
1841 :
1842 3418462 : do
1843 : {
1844 3418462 : if (component_refs2.is_empty ())
1845 : {
1846 19850 : ++alias_stats
1847 19850 : .nonoverlapping_refs_since_match_p_must_overlap;
1848 19850 : return 0;
1849 : }
1850 3398612 : ref2 = component_refs2.pop ();
1851 3398612 : ntbaa2--;
1852 3398612 : if (TREE_CODE (ref2) != COMPONENT_REF)
1853 : {
1854 48 : if (ntbaa1 < 0 || ntbaa2 < 0)
1855 : {
1856 48 : ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1857 48 : return -1;
1858 : }
1859 : seen_unmatched_ref_p = true;
1860 : }
1861 : }
1862 6797128 : while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0))));
1863 :
1864 : /* BIT_FIELD_REF and VIEW_CONVERT_EXPR are taken off the vectors
1865 : earlier. */
1866 3398564 : gcc_checking_assert (TREE_CODE (ref1) == COMPONENT_REF
1867 : && TREE_CODE (ref2) == COMPONENT_REF);
1868 :
1869 3398564 : tree field1 = TREE_OPERAND (ref1, 1);
1870 3398564 : tree field2 = TREE_OPERAND (ref2, 1);
1871 :
1872 : /* ??? We cannot simply use the type of operand #0 of the refs here
1873 : as the Fortran compiler smuggles type punning into COMPONENT_REFs
1874 : for common blocks instead of using unions like everyone else. */
1875 3398564 : tree type1 = DECL_CONTEXT (field1);
1876 3398564 : tree type2 = DECL_CONTEXT (field2);
1877 :
1878 3398564 : partial_overlap = false;
1879 :
1880 : /* If we skipped array refs on type of different sizes, we can
1881 : no longer be sure that there are not partial overlaps. */
1882 432 : if (seen_unmatched_ref_p && ntbaa1 >= 0 && ntbaa2 >= 0
1883 3398996 : && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
1884 : {
1885 0 : ++alias_stats
1886 0 : .nonoverlapping_refs_since_match_p_may_alias;
1887 0 : return -1;
1888 : }
1889 :
1890 3398564 : int cmp = nonoverlapping_component_refs_p_1 (field1, field2);
1891 3398564 : if (cmp == -1)
1892 : {
1893 3422 : ++alias_stats
1894 3422 : .nonoverlapping_refs_since_match_p_may_alias;
1895 3422 : return -1;
1896 : }
1897 3395142 : else if (cmp == 1)
1898 : {
1899 1087640 : ++alias_stats
1900 1087640 : .nonoverlapping_refs_since_match_p_no_alias;
1901 1087640 : return 1;
1902 : }
1903 : }
1904 8404920 : }
1905 :
1906 : /* Return TYPE_UID which can be used to match record types we consider
1907 : same for TBAA purposes. */
1908 :
1909 : static inline int
1910 130486 : ncr_type_uid (const_tree field)
1911 : {
1912 : /* ??? We cannot simply use the type of operand #0 of the refs here
1913 : as the Fortran compiler smuggles type punning into COMPONENT_REFs
1914 : for common blocks instead of using unions like everyone else. */
1915 130486 : tree type = DECL_FIELD_CONTEXT (field);
1916 : /* With LTO types considered same_type_for_tbaa_p
1917 : from different translation unit may not have same
1918 : main variant. They however have same TYPE_CANONICAL. */
1919 130486 : if (TYPE_CANONICAL (type))
1920 130486 : return TYPE_UID (TYPE_CANONICAL (type));
1921 0 : return TYPE_UID (type);
1922 : }
1923 :
1924 : /* qsort compare function to sort FIELD_DECLs after their
1925 : DECL_FIELD_CONTEXT TYPE_UID. */
1926 :
1927 : static inline int
1928 57005 : ncr_compar (const void *field1_, const void *field2_)
1929 : {
1930 57005 : const_tree field1 = *(const_tree *) const_cast <void *>(field1_);
1931 57005 : const_tree field2 = *(const_tree *) const_cast <void *>(field2_);
1932 57005 : unsigned int uid1 = ncr_type_uid (field1);
1933 57005 : unsigned int uid2 = ncr_type_uid (field2);
1934 :
1935 57005 : if (uid1 < uid2)
1936 : return -1;
1937 22415 : else if (uid1 > uid2)
1938 22415 : return 1;
1939 : return 0;
1940 : }
1941 :
1942 : /* Return true if we can determine that the fields referenced cannot
1943 : overlap for any pair of objects. This relies on TBAA. */
1944 :
1945 : static bool
1946 1289118 : nonoverlapping_component_refs_p (const_tree x, const_tree y)
1947 : {
1948 : /* Early return if we have nothing to do.
1949 :
1950 : Do not consider this as may-alias for stats - it is more useful
1951 : to have information how many disambiguations happened provided that
1952 : the query was meaningful. */
1953 1289118 : if (!flag_strict_aliasing
1954 1289118 : || !x || !y
1955 164495 : || !handled_component_p (x)
1956 1289118 : || !handled_component_p (y))
1957 : return false;
1958 :
1959 99824 : auto_vec<const_tree, 16> fieldsx;
1960 315989 : while (handled_component_p (x))
1961 : {
1962 216165 : if (TREE_CODE (x) == COMPONENT_REF)
1963 : {
1964 127726 : tree field = TREE_OPERAND (x, 1);
1965 127726 : tree type = DECL_FIELD_CONTEXT (field);
1966 127726 : if (TREE_CODE (type) == RECORD_TYPE)
1967 127444 : fieldsx.safe_push (field);
1968 : }
1969 88439 : else if (ends_tbaa_access_path_p (x))
1970 2470 : fieldsx.truncate (0);
1971 216165 : x = TREE_OPERAND (x, 0);
1972 : }
1973 169082 : if (fieldsx.length () == 0)
1974 : return false;
1975 69258 : auto_vec<const_tree, 16> fieldsy;
1976 150933 : while (handled_component_p (y))
1977 : {
1978 81675 : if (TREE_CODE (y) == COMPONENT_REF)
1979 : {
1980 15834 : tree field = TREE_OPERAND (y, 1);
1981 15834 : tree type = DECL_FIELD_CONTEXT (field);
1982 15834 : if (TREE_CODE (type) == RECORD_TYPE)
1983 15552 : fieldsy.safe_push (TREE_OPERAND (y, 1));
1984 : }
1985 65841 : else if (ends_tbaa_access_path_p (y))
1986 188 : fieldsy.truncate (0);
1987 81675 : y = TREE_OPERAND (y, 0);
1988 : }
1989 69258 : if (fieldsy.length () == 0)
1990 : {
1991 61403 : ++alias_stats.nonoverlapping_component_refs_p_may_alias;
1992 61403 : return false;
1993 : }
1994 :
1995 : /* Most common case first. */
1996 7855 : if (fieldsx.length () == 1
1997 7855 : && fieldsy.length () == 1)
1998 : {
1999 9038 : if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldsx[0]),
2000 4519 : DECL_FIELD_CONTEXT (fieldsy[0])) == 1
2001 7767 : && nonoverlapping_component_refs_p_1 (fieldsx[0], fieldsy[0]) == 1)
2002 : {
2003 1808 : ++alias_stats.nonoverlapping_component_refs_p_no_alias;
2004 1808 : return true;
2005 : }
2006 : else
2007 : {
2008 2711 : ++alias_stats.nonoverlapping_component_refs_p_may_alias;
2009 2711 : return false;
2010 : }
2011 : }
2012 :
2013 3336 : if (fieldsx.length () == 2)
2014 : {
2015 304 : if (ncr_compar (&fieldsx[0], &fieldsx[1]) == 1)
2016 162 : std::swap (fieldsx[0], fieldsx[1]);
2017 : }
2018 : else
2019 3032 : fieldsx.qsort (ncr_compar);
2020 :
2021 3336 : if (fieldsy.length () == 2)
2022 : {
2023 104 : if (ncr_compar (&fieldsy[0], &fieldsy[1]) == 1)
2024 44 : std::swap (fieldsy[0], fieldsy[1]);
2025 : }
2026 : else
2027 3232 : fieldsy.qsort (ncr_compar);
2028 :
2029 : unsigned i = 0, j = 0;
2030 8238 : do
2031 : {
2032 8238 : const_tree fieldx = fieldsx[i];
2033 8238 : const_tree fieldy = fieldsy[j];
2034 :
2035 : /* We're left with accessing different fields of a structure,
2036 : no possible overlap. */
2037 16476 : if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldx),
2038 8238 : DECL_FIELD_CONTEXT (fieldy)) == 1
2039 8238 : && nonoverlapping_component_refs_p_1 (fieldx, fieldy) == 1)
2040 : {
2041 0 : ++alias_stats.nonoverlapping_component_refs_p_no_alias;
2042 0 : return true;
2043 : }
2044 :
2045 8238 : if (ncr_type_uid (fieldx) < ncr_type_uid (fieldy))
2046 : {
2047 2773 : i++;
2048 5546 : if (i == fieldsx.length ())
2049 : break;
2050 : }
2051 : else
2052 : {
2053 5465 : j++;
2054 10930 : if (j == fieldsy.length ())
2055 : break;
2056 : }
2057 : }
2058 : while (1);
2059 :
2060 3336 : ++alias_stats.nonoverlapping_component_refs_p_may_alias;
2061 3336 : return false;
2062 169082 : }
2063 :
2064 :
2065 : /* Return true if two memory references based on the variables BASE1
2066 : and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
2067 : [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. REF1 and REF2
2068 : if non-NULL are the complete memory reference trees. */
2069 :
2070 : static bool
2071 1550748256 : decl_refs_may_alias_p (tree ref1, tree base1,
2072 : poly_int64 offset1, poly_int64 max_size1,
2073 : poly_int64 size1,
2074 : tree ref2, tree base2,
2075 : poly_int64 offset2, poly_int64 max_size2,
2076 : poly_int64 size2)
2077 : {
2078 1550748256 : gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
2079 :
2080 : /* If both references are based on different variables, they cannot alias. */
2081 1550748256 : if (compare_base_decls (base1, base2) == 0)
2082 : return false;
2083 :
2084 : /* If both references are based on the same variable, they cannot alias if
2085 : the accesses do not overlap. */
2086 208763000 : if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
2087 : return false;
2088 :
2089 : /* If there is must alias, there is no use disambiguating further. */
2090 62152644 : if (known_eq (size1, max_size1) && known_eq (size2, max_size2))
2091 : return true;
2092 :
2093 : /* For components with variable position, the above test isn't sufficient,
2094 : so we disambiguate component references manually. */
2095 10627766 : if (ref1 && ref2
2096 8017503 : && handled_component_p (ref1) && handled_component_p (ref2)
2097 17848572 : && nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2, false) == 1)
2098 : return false;
2099 :
2100 : return true;
2101 : }
2102 :
2103 : /* Return true if access with BASE is view converted.
2104 : Base must not be stripped from inner MEM_REF (&decl)
2105 : which is done by ao_ref_base and thus one extra walk
2106 : of handled components is needed. */
2107 :
2108 : bool
2109 1259033636 : view_converted_memref_p (tree base)
2110 : {
2111 1259033636 : if (TREE_CODE (base) != MEM_REF && TREE_CODE (base) != TARGET_MEM_REF)
2112 : return false;
2113 843793983 : return (same_type_for_tbaa (TREE_TYPE (base),
2114 843793983 : TREE_TYPE (TREE_TYPE (TREE_OPERAND (base, 1))))
2115 843793983 : != 1);
2116 : }
2117 :
2118 : /* Return true if an indirect reference based on *PTR1 constrained
2119 : to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
2120 : constrained to [OFFSET2, OFFSET2 + MAX_SIZE2). *PTR1 and BASE2 have
2121 : the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
2122 : in which case they are computed on-demand. REF1 and REF2
2123 : if non-NULL are the complete memory reference trees. */
2124 :
2125 : static bool
2126 308750069 : indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
2127 : poly_int64 offset1, poly_int64 max_size1,
2128 : poly_int64 size1,
2129 : alias_set_type ref1_alias_set,
2130 : alias_set_type base1_alias_set,
2131 : tree ref2 ATTRIBUTE_UNUSED, tree base2,
2132 : poly_int64 offset2, poly_int64 max_size2,
2133 : poly_int64 size2,
2134 : alias_set_type ref2_alias_set,
2135 : alias_set_type base2_alias_set, bool tbaa_p)
2136 : {
2137 308750069 : tree ptr1;
2138 308750069 : tree ptrtype1, dbase2;
2139 :
2140 308750069 : gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
2141 : || TREE_CODE (base1) == TARGET_MEM_REF)
2142 : && DECL_P (base2));
2143 :
2144 308750069 : ptr1 = TREE_OPERAND (base1, 0);
2145 308750069 : poly_offset_int moff = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
2146 :
2147 : /* If only one reference is based on a variable, they cannot alias if
2148 : the pointer access is beyond the extent of the variable access.
2149 : (the pointer base cannot validly point to an offset less than zero
2150 : of the variable).
2151 : ??? IVOPTs creates bases that do not honor this restriction,
2152 : so do not apply this optimization for TARGET_MEM_REFs. */
2153 308750069 : if (TREE_CODE (base1) != TARGET_MEM_REF
2154 308750069 : && !ranges_maybe_overlap_p (offset1 + moff, -1, offset2, max_size2))
2155 74901876 : return false;
2156 :
2157 : /* If the pointer based access is bigger than the variable they cannot
2158 : alias. This is similar to the check below where we use TBAA to
2159 : increase the size of the pointer based access based on the dynamic
2160 : type of a containing object we can infer from it. */
2161 233848193 : poly_int64 dsize2;
2162 233848193 : if (known_size_p (size1)
2163 218062764 : && poly_int_tree_p (DECL_SIZE (base2), &dsize2)
2164 414489535 : && known_lt (dsize2, size1))
2165 : return false;
2166 :
2167 : /* They also cannot alias if the pointer may not point to the decl. */
2168 214694442 : if (!ptr_deref_may_alias_decl_p (ptr1, base2))
2169 : return false;
2170 :
2171 : /* Disambiguations that rely on strict aliasing rules follow. */
2172 31876993 : if (!flag_strict_aliasing || !tbaa_p)
2173 : return true;
2174 :
2175 : /* If the alias set for a pointer access is zero all bets are off. */
2176 6553015 : if (base1_alias_set == 0 || base2_alias_set == 0)
2177 : return true;
2178 :
2179 : /* When we are trying to disambiguate an access with a pointer dereference
2180 : as base versus one with a decl as base we can use both the size
2181 : of the decl and its dynamic type for extra disambiguation.
2182 : ??? We do not know anything about the dynamic type of the decl
2183 : other than that its alias-set contains base2_alias_set as a subset
2184 : which does not help us here. */
2185 : /* As we know nothing useful about the dynamic type of the decl just
2186 : use the usual conflict check rather than a subset test.
2187 : ??? We could introduce -fvery-strict-aliasing when the language
2188 : does not allow decls to have a dynamic type that differs from their
2189 : static type. Then we can check
2190 : !alias_set_subset_of (base1_alias_set, base2_alias_set) instead. */
2191 1583969 : if (base1_alias_set != base2_alias_set
2192 1583969 : && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
2193 : return false;
2194 :
2195 1369024 : ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
2196 :
2197 : /* If the size of the access relevant for TBAA through the pointer
2198 : is bigger than the size of the decl we can't possibly access the
2199 : decl via that pointer. */
2200 1369024 : if (/* ??? This in turn may run afoul when a decl of type T which is
2201 : a member of union type U is accessed through a pointer to
2202 : type U and sizeof T is smaller than sizeof U. */
2203 1369024 : TREE_CODE (TREE_TYPE (ptrtype1)) != UNION_TYPE
2204 1336106 : && TREE_CODE (TREE_TYPE (ptrtype1)) != QUAL_UNION_TYPE
2205 2705130 : && compare_sizes (DECL_SIZE (base2),
2206 1336106 : TYPE_SIZE (TREE_TYPE (ptrtype1))) < 0)
2207 : return false;
2208 :
2209 1335413 : if (!ref2)
2210 : return true;
2211 :
2212 : /* If the decl is accessed via a MEM_REF, reconstruct the base
2213 : we can use for TBAA and an appropriately adjusted offset. */
2214 : dbase2 = ref2;
2215 2182073 : while (handled_component_p (dbase2))
2216 917850 : dbase2 = TREE_OPERAND (dbase2, 0);
2217 1264223 : poly_int64 doffset1 = offset1;
2218 1264223 : poly_offset_int doffset2 = offset2;
2219 1264223 : if (TREE_CODE (dbase2) == MEM_REF
2220 1264223 : || TREE_CODE (dbase2) == TARGET_MEM_REF)
2221 : {
2222 909204 : doffset2 -= mem_ref_offset (dbase2) << LOG2_BITS_PER_UNIT;
2223 454602 : tree ptrtype2 = TREE_TYPE (TREE_OPERAND (dbase2, 1));
2224 : /* If second reference is view-converted, give up now. */
2225 454602 : if (same_type_for_tbaa (TREE_TYPE (dbase2), TREE_TYPE (ptrtype2)) != 1)
2226 : return true;
2227 : }
2228 :
2229 : /* If first reference is view-converted, give up now. */
2230 1165272 : if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1)
2231 : return true;
2232 :
2233 : /* If both references are through the same type, they do not alias
2234 : if the accesses do not overlap. This does extra disambiguation
2235 : for mixed/pointer accesses but requires strict aliasing.
2236 : For MEM_REFs we require that the component-ref offset we computed
2237 : is relative to the start of the type which we ensure by
2238 : comparing rvalue and access type and disregarding the constant
2239 : pointer offset.
2240 :
2241 : But avoid treating variable length arrays as "objects", instead assume they
2242 : can overlap by an exact multiple of their element size.
2243 : See gcc.dg/torture/alias-2.c. */
2244 1064694 : if (((TREE_CODE (base1) != TARGET_MEM_REF
2245 183434 : || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
2246 1029176 : && (TREE_CODE (dbase2) != TARGET_MEM_REF
2247 21309 : || (!TMR_INDEX (dbase2) && !TMR_INDEX2 (dbase2))))
2248 2072578 : && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1)
2249 : {
2250 339366 : bool partial_overlap = (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE
2251 339366 : && (TYPE_SIZE (TREE_TYPE (base1))
2252 2284 : && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1)))
2253 658149 : != INTEGER_CST));
2254 339366 : if (!partial_overlap
2255 339366 : && !ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2))
2256 : return false;
2257 318783 : if (!ref1 || !ref2
2258 : /* If there is must alias, there is no use disambiguating further. */
2259 318783 : || (!partial_overlap
2260 306049 : && known_eq (size1, max_size1) && known_eq (size2, max_size2)))
2261 : return true;
2262 3465 : int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2,
2263 : partial_overlap);
2264 3465 : if (res == -1)
2265 3355 : return !nonoverlapping_component_refs_p (ref1, ref2);
2266 110 : return !res;
2267 : }
2268 :
2269 : /* Do access-path based disambiguation. */
2270 725328 : if (ref1 && ref2
2271 1227609 : && (handled_component_p (ref1) || handled_component_p (ref2)))
2272 527305 : return aliasing_component_refs_p (ref1,
2273 : ref1_alias_set, base1_alias_set,
2274 : offset1, max_size1,
2275 : ref2,
2276 : ref2_alias_set, base2_alias_set,
2277 527305 : offset2, max_size2);
2278 :
2279 : return true;
2280 : }
2281 :
2282 : /* Return true if two indirect references based on *PTR1
2283 : and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
2284 : [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. *PTR1 and *PTR2 have
2285 : the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
2286 : in which case they are computed on-demand. REF1 and REF2
2287 : if non-NULL are the complete memory reference trees. */
2288 :
2289 : static bool
2290 98451176 : indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
2291 : poly_int64 offset1, poly_int64 max_size1,
2292 : poly_int64 size1,
2293 : alias_set_type ref1_alias_set,
2294 : alias_set_type base1_alias_set,
2295 : tree ref2 ATTRIBUTE_UNUSED, tree base2,
2296 : poly_int64 offset2, poly_int64 max_size2,
2297 : poly_int64 size2,
2298 : alias_set_type ref2_alias_set,
2299 : alias_set_type base2_alias_set, bool tbaa_p)
2300 : {
2301 98451176 : tree ptr1;
2302 98451176 : tree ptr2;
2303 98451176 : tree ptrtype1, ptrtype2;
2304 :
2305 98451176 : gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
2306 : || TREE_CODE (base1) == TARGET_MEM_REF)
2307 : && (TREE_CODE (base2) == MEM_REF
2308 : || TREE_CODE (base2) == TARGET_MEM_REF));
2309 :
2310 98451176 : ptr1 = TREE_OPERAND (base1, 0);
2311 98451176 : ptr2 = TREE_OPERAND (base2, 0);
2312 :
2313 : /* If both bases are based on pointers they cannot alias if they may not
2314 : point to the same memory object or if they point to the same object
2315 : and the accesses do not overlap. */
2316 98451176 : if ((!cfun || gimple_in_ssa_p (cfun))
2317 62470534 : && operand_equal_p (ptr1, ptr2, 0)
2318 131284117 : && (((TREE_CODE (base1) != TARGET_MEM_REF
2319 1171240 : || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
2320 32741744 : && (TREE_CODE (base2) != TARGET_MEM_REF
2321 1070410 : || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2))))
2322 107907 : || (TREE_CODE (base1) == TARGET_MEM_REF
2323 94901 : && TREE_CODE (base2) == TARGET_MEM_REF
2324 88350 : && (TMR_STEP (base1) == TMR_STEP (base2)
2325 13466 : || (TMR_STEP (base1) && TMR_STEP (base2)
2326 2778 : && operand_equal_p (TMR_STEP (base1),
2327 2778 : TMR_STEP (base2), 0)))
2328 74884 : && (TMR_INDEX (base1) == TMR_INDEX (base2)
2329 10761 : || (TMR_INDEX (base1) && TMR_INDEX (base2)
2330 9312 : && operand_equal_p (TMR_INDEX (base1),
2331 9312 : TMR_INDEX (base2), 0)))
2332 64123 : && (TMR_INDEX2 (base1) == TMR_INDEX2 (base2)
2333 0 : || (TMR_INDEX2 (base1) && TMR_INDEX2 (base2)
2334 0 : && operand_equal_p (TMR_INDEX2 (base1),
2335 0 : TMR_INDEX2 (base2), 0))))))
2336 : {
2337 32789157 : poly_offset_int moff1 = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
2338 32789157 : poly_offset_int moff2 = mem_ref_offset (base2) << LOG2_BITS_PER_UNIT;
2339 32789157 : if (!ranges_maybe_overlap_p (offset1 + moff1, max_size1,
2340 32789157 : offset2 + moff2, max_size2))
2341 32485226 : return false;
2342 : /* If there is must alias, there is no use disambiguating further. */
2343 4233299 : if (known_eq (size1, max_size1) && known_eq (size2, max_size2))
2344 : return true;
2345 1216563 : if (ref1 && ref2)
2346 : {
2347 923554 : int res = nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2,
2348 : false);
2349 923554 : if (res != -1)
2350 912632 : return !res;
2351 : }
2352 : }
2353 65965950 : if (!ptr_derefs_may_alias_p (ptr1, ptr2))
2354 : return false;
2355 :
2356 : /* Disambiguations that rely on strict aliasing rules follow. */
2357 38550916 : if (!flag_strict_aliasing || !tbaa_p)
2358 : return true;
2359 :
2360 15104721 : ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
2361 15104721 : ptrtype2 = TREE_TYPE (TREE_OPERAND (base2, 1));
2362 :
2363 : /* If the alias set for a pointer access is zero all bets are off. */
2364 15104721 : if (base1_alias_set == 0
2365 15104721 : || base2_alias_set == 0)
2366 : return true;
2367 :
2368 : /* Do type-based disambiguation. */
2369 10093834 : if (base1_alias_set != base2_alias_set
2370 10093834 : && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
2371 : return false;
2372 :
2373 : /* If either reference is view-converted, give up now. */
2374 9320581 : if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
2375 9320581 : || same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) != 1)
2376 2722985 : return true;
2377 :
2378 : /* If both references are through the same type, they do not alias
2379 : if the accesses do not overlap. This does extra disambiguation
2380 : for mixed/pointer accesses but requires strict aliasing. */
2381 6597596 : if ((TREE_CODE (base1) != TARGET_MEM_REF
2382 1180402 : || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
2383 6221728 : && (TREE_CODE (base2) != TARGET_MEM_REF
2384 1012363 : || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2)))
2385 12677994 : && same_type_for_tbaa (TREE_TYPE (ptrtype1),
2386 6080398 : TREE_TYPE (ptrtype2)) == 1)
2387 : {
2388 : /* But avoid treating arrays as "objects", instead assume they
2389 : can overlap by an exact multiple of their element size.
2390 : See gcc.dg/torture/alias-2.c. */
2391 4018336 : bool partial_overlap = TREE_CODE (TREE_TYPE (ptrtype1)) == ARRAY_TYPE;
2392 :
2393 4018336 : if (!partial_overlap
2394 4018336 : && !ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
2395 : return false;
2396 3661636 : if (!ref1 || !ref2
2397 3661636 : || (!partial_overlap
2398 3030563 : && known_eq (size1, max_size1) && known_eq (size2, max_size2)))
2399 : return true;
2400 223125 : int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2,
2401 : partial_overlap);
2402 223125 : if (res == -1)
2403 61885 : return !nonoverlapping_component_refs_p (ref1, ref2);
2404 161240 : return !res;
2405 : }
2406 :
2407 : /* Do access-path based disambiguation. */
2408 2579260 : if (ref1 && ref2
2409 3793179 : && (handled_component_p (ref1) || handled_component_p (ref2)))
2410 1850426 : return aliasing_component_refs_p (ref1,
2411 : ref1_alias_set, base1_alias_set,
2412 : offset1, max_size1,
2413 : ref2,
2414 : ref2_alias_set, base2_alias_set,
2415 1850426 : offset2, max_size2);
2416 :
2417 : return true;
2418 : }
2419 :
2420 : /* Return true, if the two memory references REF1 and REF2 may alias. */
2421 :
2422 : static bool
2423 2040629672 : refs_may_alias_p_2 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
2424 : {
2425 2040629672 : tree base1, base2;
2426 2040629672 : poly_int64 offset1 = 0, offset2 = 0;
2427 2040629672 : poly_int64 max_size1 = -1, max_size2 = -1;
2428 2040629672 : bool var1_p, var2_p, ind1_p, ind2_p;
2429 :
2430 2040629672 : gcc_checking_assert ((!ref1->ref
2431 : || TREE_CODE (ref1->ref) == SSA_NAME
2432 : || DECL_P (ref1->ref)
2433 : || TREE_CODE (ref1->ref) == STRING_CST
2434 : || handled_component_p (ref1->ref)
2435 : || TREE_CODE (ref1->ref) == MEM_REF
2436 : || TREE_CODE (ref1->ref) == TARGET_MEM_REF
2437 : || TREE_CODE (ref1->ref) == WITH_SIZE_EXPR)
2438 : && (!ref2->ref
2439 : || TREE_CODE (ref2->ref) == SSA_NAME
2440 : || DECL_P (ref2->ref)
2441 : || TREE_CODE (ref2->ref) == STRING_CST
2442 : || handled_component_p (ref2->ref)
2443 : || TREE_CODE (ref2->ref) == MEM_REF
2444 : || TREE_CODE (ref2->ref) == TARGET_MEM_REF
2445 : || TREE_CODE (ref2->ref) == WITH_SIZE_EXPR));
2446 :
2447 : /* Decompose the references into their base objects and the access. */
2448 2040629672 : base1 = ao_ref_base (ref1);
2449 2040629672 : offset1 = ref1->offset;
2450 2040629672 : max_size1 = ref1->max_size;
2451 2040629672 : base2 = ao_ref_base (ref2);
2452 2040629672 : offset2 = ref2->offset;
2453 2040629672 : max_size2 = ref2->max_size;
2454 :
2455 : /* We can end up with registers or constants as bases for example from
2456 : *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
2457 : which is seen as a struct copy. */
2458 2040629672 : if (TREE_CODE (base1) == SSA_NAME
2459 2040626367 : || TREE_CODE (base1) == CONST_DECL
2460 2038648052 : || TREE_CODE (base1) == CONSTRUCTOR
2461 2038648052 : || TREE_CODE (base1) == ADDR_EXPR
2462 2038648044 : || CONSTANT_CLASS_P (base1)
2463 2032136644 : || TREE_CODE (base2) == SSA_NAME
2464 2032136644 : || TREE_CODE (base2) == CONST_DECL
2465 2032038779 : || TREE_CODE (base2) == CONSTRUCTOR
2466 2032038779 : || TREE_CODE (base2) == ADDR_EXPR
2467 2032038779 : || CONSTANT_CLASS_P (base2))
2468 : return false;
2469 :
2470 : /* Two volatile accesses always conflict. */
2471 2031992582 : if (ref1->volatile_p
2472 5888035 : && ref2->volatile_p)
2473 : return true;
2474 :
2475 : /* refN->ref may convey size information, do not confuse our workers
2476 : with that but strip it - ao_ref_base took it into account already. */
2477 2028363233 : tree ref1ref = ref1->ref;
2478 2028363233 : if (ref1ref && TREE_CODE (ref1ref) == WITH_SIZE_EXPR)
2479 162 : ref1ref = TREE_OPERAND (ref1ref, 0);
2480 2028363233 : tree ref2ref = ref2->ref;
2481 2028363233 : if (ref2ref && TREE_CODE (ref2ref) == WITH_SIZE_EXPR)
2482 0 : ref2ref = TREE_OPERAND (ref2ref, 0);
2483 :
2484 : /* Defer to simple offset based disambiguation if we have
2485 : references based on two decls. Do this before deferring to
2486 : TBAA to handle must-alias cases in conformance with the
2487 : GCC extension of allowing type-punning through unions. */
2488 2028363233 : var1_p = DECL_P (base1);
2489 2028363233 : var2_p = DECL_P (base2);
2490 2028363233 : if (var1_p && var2_p)
2491 1550748256 : return decl_refs_may_alias_p (ref1ref, base1, offset1, max_size1,
2492 : ref1->size,
2493 : ref2ref, base2, offset2, max_size2,
2494 1550748256 : ref2->size);
2495 :
2496 : /* We can end up referring to code via function and label decls.
2497 : As we likely do not properly track code aliases conservatively
2498 : bail out. */
2499 477614977 : if (TREE_CODE (base1) == FUNCTION_DECL
2500 477614977 : || TREE_CODE (base1) == LABEL_DECL
2501 476636737 : || TREE_CODE (base2) == FUNCTION_DECL
2502 476624215 : || TREE_CODE (base2) == LABEL_DECL)
2503 : return true;
2504 :
2505 : /* Handle restrict based accesses.
2506 : ??? ao_ref_base strips inner MEM_REF [&decl], recover from that
2507 : here. */
2508 476624215 : tree rbase1 = base1;
2509 476624215 : tree rbase2 = base2;
2510 476624215 : if (var1_p)
2511 : {
2512 228261861 : rbase1 = ref1ref;
2513 228261861 : if (rbase1)
2514 297052693 : while (handled_component_p (rbase1))
2515 108713094 : rbase1 = TREE_OPERAND (rbase1, 0);
2516 : }
2517 476624215 : if (var2_p)
2518 : {
2519 122313263 : rbase2 = ref2ref;
2520 122313263 : if (rbase2)
2521 200506857 : while (handled_component_p (rbase2))
2522 85930787 : rbase2 = TREE_OPERAND (rbase2, 0);
2523 : }
2524 476624215 : if (rbase1 && rbase2
2525 428964760 : && (TREE_CODE (rbase1) == MEM_REF || TREE_CODE (rbase1) == TARGET_MEM_REF)
2526 275269797 : && (TREE_CODE (rbase2) == MEM_REF || TREE_CODE (rbase2) == TARGET_MEM_REF)
2527 : /* If the accesses are in the same restrict clique... */
2528 193205282 : && MR_DEPENDENCE_CLIQUE (rbase1) == MR_DEPENDENCE_CLIQUE (rbase2)
2529 : /* But based on different pointers they do not alias. */
2530 639130024 : && MR_DEPENDENCE_BASE (rbase1) != MR_DEPENDENCE_BASE (rbase2))
2531 : return false;
2532 :
2533 457646752 : ind1_p = (TREE_CODE (base1) == MEM_REF
2534 457646752 : || TREE_CODE (base1) == TARGET_MEM_REF);
2535 457646752 : ind2_p = (TREE_CODE (base2) == MEM_REF
2536 457646752 : || TREE_CODE (base2) == TARGET_MEM_REF);
2537 :
2538 : /* Canonicalize the pointer-vs-decl case. */
2539 457646752 : if (ind1_p && var2_p)
2540 : {
2541 120904325 : std::swap (offset1, offset2);
2542 120904325 : std::swap (max_size1, max_size2);
2543 120904325 : std::swap (base1, base2);
2544 120904325 : std::swap (ref1, ref2);
2545 120904325 : std::swap (ref1ref, ref2ref);
2546 120904325 : var1_p = true;
2547 120904325 : ind1_p = false;
2548 120904325 : var2_p = false;
2549 120904325 : ind2_p = true;
2550 : }
2551 :
2552 : /* First defer to TBAA if possible. */
2553 457646752 : if (tbaa_p
2554 206372657 : && flag_strict_aliasing
2555 596396503 : && !alias_sets_conflict_p (ao_ref_alias_set (ref1),
2556 : ao_ref_alias_set (ref2)))
2557 : return false;
2558 :
2559 : /* If the reference is based on a pointer that points to memory
2560 : that may not be written to then the other reference cannot possibly
2561 : clobber it. */
2562 407816032 : if ((TREE_CODE (TREE_OPERAND (base2, 0)) == SSA_NAME
2563 406474041 : && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base2, 0)))
2564 813768506 : || (ind1_p
2565 98544396 : && TREE_CODE (TREE_OPERAND (base1, 0)) == SSA_NAME
2566 98346536 : && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base1, 0))))
2567 : return false;
2568 :
2569 : /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators. */
2570 407201245 : if (var1_p && ind2_p)
2571 308750069 : return indirect_ref_may_alias_decl_p (ref2ref, base2,
2572 : offset2, max_size2, ref2->size,
2573 : ao_ref_alias_set (ref2),
2574 : ao_ref_base_alias_set (ref2),
2575 : ref1ref, base1,
2576 : offset1, max_size1, ref1->size,
2577 : ao_ref_alias_set (ref1),
2578 : ao_ref_base_alias_set (ref1),
2579 308750069 : tbaa_p);
2580 98451176 : else if (ind1_p && ind2_p)
2581 98451176 : return indirect_refs_may_alias_p (ref1ref, base1,
2582 : offset1, max_size1, ref1->size,
2583 : ao_ref_alias_set (ref1),
2584 : ao_ref_base_alias_set (ref1),
2585 : ref2ref, base2,
2586 : offset2, max_size2, ref2->size,
2587 : ao_ref_alias_set (ref2),
2588 : ao_ref_base_alias_set (ref2),
2589 98451176 : tbaa_p);
2590 :
2591 0 : gcc_unreachable ();
2592 : }
2593 :
2594 : /* Return true, if the two memory references REF1 and REF2 may alias
2595 : and update statistics. */
2596 :
2597 : bool
2598 2040629672 : refs_may_alias_p_1 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
2599 : {
2600 2040629672 : bool res = refs_may_alias_p_2 (ref1, ref2, tbaa_p);
2601 2040629672 : if (res)
2602 137522465 : ++alias_stats.refs_may_alias_p_may_alias;
2603 : else
2604 1903107207 : ++alias_stats.refs_may_alias_p_no_alias;
2605 2040629672 : return res;
2606 : }
2607 :
2608 : static bool
2609 66115191 : refs_may_alias_p (tree ref1, ao_ref *ref2, bool tbaa_p)
2610 : {
2611 66115191 : ao_ref r1;
2612 66115191 : ao_ref_init (&r1, ref1);
2613 66115191 : return refs_may_alias_p_1 (&r1, ref2, tbaa_p);
2614 : }
2615 :
2616 : bool
2617 1062808 : refs_may_alias_p (tree ref1, tree ref2, bool tbaa_p)
2618 : {
2619 1062808 : ao_ref r1, r2;
2620 1062808 : ao_ref_init (&r1, ref1);
2621 1062808 : ao_ref_init (&r2, ref2);
2622 1062808 : return refs_may_alias_p_1 (&r1, &r2, tbaa_p);
2623 : }
2624 :
2625 : /* Returns true if there is a anti-dependence for the STORE that
2626 : executes after the LOAD. */
2627 :
2628 : bool
2629 486279 : refs_anti_dependent_p (tree load, tree store)
2630 : {
2631 486279 : ao_ref r1, r2;
2632 486279 : ao_ref_init (&r1, load);
2633 486279 : ao_ref_init (&r2, store);
2634 486279 : return refs_may_alias_p_1 (&r1, &r2, false);
2635 : }
2636 :
2637 : /* Returns true if there is a output dependence for the stores
2638 : STORE1 and STORE2. */
2639 :
2640 : bool
2641 2965473 : refs_output_dependent_p (tree store1, tree store2)
2642 : {
2643 2965473 : ao_ref r1, r2;
2644 2965473 : ao_ref_init (&r1, store1);
2645 2965473 : ao_ref_init (&r2, store2);
2646 2965473 : return refs_may_alias_p_1 (&r1, &r2, false);
2647 : }
2648 :
2649 : /* Returns true if and only if REF may alias any access stored in TT.
2650 : IF TBAA_P is true, use TBAA oracle. */
2651 :
2652 : static bool
2653 48760891 : modref_may_conflict (const gcall *stmt,
2654 : modref_tree <alias_set_type> *tt, ao_ref *ref, bool tbaa_p)
2655 : {
2656 48760891 : alias_set_type base_set, ref_set;
2657 48760891 : bool global_memory_ok = false;
2658 :
2659 48760891 : if (tt->every_base)
2660 : return true;
2661 :
2662 8484442 : if (!dbg_cnt (ipa_mod_ref))
2663 : return true;
2664 :
2665 8484442 : base_set = ao_ref_base_alias_set (ref);
2666 :
2667 8484442 : ref_set = ao_ref_alias_set (ref);
2668 :
2669 8484442 : int num_tests = 0, max_tests = param_modref_max_tests;
2670 34486886 : for (auto base_node : tt->bases)
2671 : {
2672 13066126 : if (tbaa_p && flag_strict_aliasing)
2673 : {
2674 9952353 : if (num_tests >= max_tests)
2675 : return true;
2676 9952353 : alias_stats.modref_tests++;
2677 9952353 : if (!alias_sets_conflict_p (base_set, base_node->base))
2678 3520109 : continue;
2679 6432244 : num_tests++;
2680 : }
2681 :
2682 9546017 : if (base_node->every_ref)
2683 : return true;
2684 :
2685 36108892 : for (auto ref_node : base_node->refs)
2686 : {
2687 : /* Do not repeat same test as before. */
2688 11083871 : if ((ref_set != base_set || base_node->base != ref_node->ref)
2689 6632591 : && tbaa_p && flag_strict_aliasing)
2690 : {
2691 4194716 : if (num_tests >= max_tests)
2692 : return true;
2693 4163444 : alias_stats.modref_tests++;
2694 4163444 : if (!alias_sets_conflict_p (ref_set, ref_node->ref))
2695 1085314 : continue;
2696 3078130 : num_tests++;
2697 : }
2698 :
2699 9967285 : if (ref_node->every_access)
2700 : return true;
2701 :
2702 : /* TBAA checks did not disambiguate, try individual accesses. */
2703 31374022 : for (auto access_node : ref_node->accesses)
2704 : {
2705 8968960 : if (num_tests >= max_tests)
2706 1603824 : return true;
2707 :
2708 8968960 : if (access_node.parm_index == MODREF_GLOBAL_MEMORY_PARM)
2709 : {
2710 1509354 : if (global_memory_ok)
2711 967106 : continue;
2712 1509354 : if (ref_may_alias_global_p (ref, true))
2713 : return true;
2714 938856 : global_memory_ok = true;
2715 938856 : num_tests++;
2716 938856 : continue;
2717 : }
2718 :
2719 7459606 : tree arg = access_node.get_call_arg (stmt);
2720 7459606 : if (!arg)
2721 : return true;
2722 :
2723 7458523 : alias_stats.modref_baseptr_tests++;
2724 :
2725 7458523 : if (integer_zerop (arg) && flag_delete_null_pointer_checks)
2726 28250 : continue;
2727 :
2728 : /* PTA oracle will be unhapy of arg is not an pointer. */
2729 7430273 : if (!POINTER_TYPE_P (TREE_TYPE (arg)))
2730 : return true;
2731 :
2732 : /* If we don't have base pointer, give up. */
2733 7430273 : if (!ref->ref && !ref->base)
2734 0 : continue;
2735 :
2736 7430273 : ao_ref ref2;
2737 7430273 : if (access_node.get_ao_ref (stmt, &ref2))
2738 : {
2739 5689883 : ref2.ref_alias_set = ref_node->ref;
2740 5689883 : ref2.base_alias_set = base_node->base;
2741 5689883 : if (refs_may_alias_p_1 (&ref2, ref, tbaa_p))
2742 : return true;
2743 : }
2744 1740390 : else if (ptr_deref_may_alias_ref_p_1 (arg, ref))
2745 : return true;
2746 :
2747 6398030 : num_tests++;
2748 : }
2749 : }
2750 : }
2751 : return false;
2752 : }
2753 :
2754 : /* Check if REF conflicts with call using "fn spec" attribute.
2755 : If CLOBBER is true we are checking for writes, otherwise check loads.
2756 :
2757 : Return 0 if there are no conflicts (except for possible function call
2758 : argument reads), 1 if there are conflicts and -1 if we can not decide by
2759 : fn spec. */
2760 :
2761 : static int
2762 157096498 : check_fnspec (gcall *call, ao_ref *ref, bool clobber)
2763 : {
2764 157096498 : attr_fnspec fnspec = gimple_call_fnspec (call);
2765 157096498 : if (fnspec.known_p ())
2766 : {
2767 78349155 : if (clobber
2768 78349155 : ? !fnspec.global_memory_written_p ()
2769 8977235 : : !fnspec.global_memory_read_p ())
2770 : {
2771 93340220 : for (unsigned int i = 0; i < gimple_call_num_args (call); i++)
2772 90651092 : if (POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, i)))
2773 64115654 : && (!fnspec.arg_specified_p (i)
2774 37516791 : || (clobber ? fnspec.arg_maybe_written_p (i)
2775 3452245 : : fnspec.arg_maybe_read_p (i))))
2776 : {
2777 23368563 : ao_ref dref;
2778 23368563 : tree size = NULL_TREE;
2779 23368563 : unsigned int size_arg;
2780 :
2781 23368563 : if (!fnspec.arg_specified_p (i))
2782 : ;
2783 23365026 : else if (fnspec.arg_max_access_size_given_by_arg_p
2784 23365026 : (i, &size_arg))
2785 15442850 : size = gimple_call_arg (call, size_arg);
2786 7922176 : else if (fnspec.arg_access_size_given_by_type_p (i))
2787 : {
2788 27960 : tree callee = gimple_call_fndecl (call);
2789 27960 : tree t = TYPE_ARG_TYPES (TREE_TYPE (callee));
2790 :
2791 57231 : for (unsigned int p = 0; p < i; p++)
2792 29271 : t = TREE_CHAIN (t);
2793 27960 : size = TYPE_SIZE_UNIT (TREE_TYPE (TREE_VALUE (t)));
2794 : }
2795 15470810 : poly_int64 size_hwi;
2796 15470810 : if (size
2797 15470810 : && poly_int_tree_p (size, &size_hwi)
2798 28350948 : && coeffs_in_range_p (size_hwi, 0,
2799 : HOST_WIDE_INT_MAX / BITS_PER_UNIT))
2800 : {
2801 12878602 : size_hwi = size_hwi * BITS_PER_UNIT;
2802 12878602 : ao_ref_init_from_ptr_and_range (&dref,
2803 : gimple_call_arg (call, i),
2804 : true, 0, -1, size_hwi);
2805 : }
2806 : else
2807 10489961 : ao_ref_init_from_ptr_and_range (&dref,
2808 : gimple_call_arg (call, i),
2809 : false, 0, -1, -1);
2810 23368563 : if (refs_may_alias_p_1 (&dref, ref, false))
2811 4866062 : return 1;
2812 : }
2813 29284454 : if (clobber
2814 25641091 : && fnspec.errno_maybe_written_p ()
2815 37122806 : && targetm.ref_may_alias_errno (ref))
2816 : return 1;
2817 29258602 : return 0;
2818 : }
2819 : }
2820 :
2821 : /* FIXME: we should handle barriers more consistently, but for now leave the
2822 : check here. */
2823 122945982 : if (gimple_call_builtin_p (call, BUILT_IN_NORMAL))
2824 6684618 : switch (DECL_FUNCTION_CODE (gimple_call_fndecl (call)))
2825 : {
2826 : /* __sync_* builtins and some OpenMP builtins act as threading
2827 : barriers. */
2828 : #undef DEF_SYNC_BUILTIN
2829 : #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
2830 : #include "sync-builtins.def"
2831 : #undef DEF_SYNC_BUILTIN
2832 : case BUILT_IN_GOMP_ATOMIC_START:
2833 : case BUILT_IN_GOMP_ATOMIC_END:
2834 : case BUILT_IN_GOMP_REDUCTION_START:
2835 : case BUILT_IN_GOMP_REDUCTION_END:
2836 : case BUILT_IN_GOMP_BARRIER:
2837 : case BUILT_IN_GOMP_BARRIER_CANCEL:
2838 : case BUILT_IN_GOMP_TASKWAIT:
2839 : case BUILT_IN_GOMP_TASKGROUP_END:
2840 : case BUILT_IN_GOMP_CRITICAL_START:
2841 : case BUILT_IN_GOMP_CRITICAL_END:
2842 : case BUILT_IN_GOMP_CRITICAL_NAME_START:
2843 : case BUILT_IN_GOMP_CRITICAL_NAME_END:
2844 : case BUILT_IN_GOMP_LOOP_END:
2845 : case BUILT_IN_GOMP_LOOP_END_CANCEL:
2846 : case BUILT_IN_GOMP_ORDERED_START:
2847 : case BUILT_IN_GOMP_ORDERED_END:
2848 : case BUILT_IN_GOMP_SECTIONS_END:
2849 : case BUILT_IN_GOMP_SECTIONS_END_CANCEL:
2850 : case BUILT_IN_GOMP_SINGLE_COPY_START:
2851 : case BUILT_IN_GOMP_SINGLE_COPY_END:
2852 : return 1;
2853 :
2854 : default:
2855 : return -1;
2856 : }
2857 : return -1;
2858 : }
2859 :
2860 : /* If the call CALL may use the memory reference REF return true,
2861 : otherwise return false. */
2862 :
2863 : static bool
2864 47111343 : ref_maybe_used_by_call_p_1 (gcall *call, ao_ref *ref, bool tbaa_p)
2865 : {
2866 47111343 : tree base, callee;
2867 47111343 : unsigned i;
2868 47111343 : int flags = gimple_call_flags (call);
2869 :
2870 47111343 : if (flags & (ECF_CONST|ECF_NOVOPS))
2871 369964 : goto process_args;
2872 :
2873 : /* A call that is not without side-effects might involve volatile
2874 : accesses and thus conflicts with all other volatile accesses. */
2875 46741379 : if (ref->volatile_p)
2876 : return true;
2877 :
2878 46741204 : if (gimple_call_internal_p (call))
2879 69822 : switch (gimple_call_internal_fn (call))
2880 : {
2881 : case IFN_MASK_STORE:
2882 : case IFN_SCATTER_STORE:
2883 : case IFN_MASK_SCATTER_STORE:
2884 : case IFN_LEN_STORE:
2885 : case IFN_MASK_LEN_STORE:
2886 : return false;
2887 0 : case IFN_MASK_STORE_LANES:
2888 0 : case IFN_MASK_LEN_STORE_LANES:
2889 0 : goto process_args;
2890 826 : case IFN_MASK_LOAD:
2891 826 : case IFN_LEN_LOAD:
2892 826 : case IFN_MASK_LEN_LOAD:
2893 826 : case IFN_MASK_LOAD_LANES:
2894 826 : case IFN_MASK_LEN_LOAD_LANES:
2895 826 : {
2896 826 : ao_ref rhs_ref;
2897 826 : tree lhs = gimple_call_lhs (call);
2898 826 : if (lhs)
2899 : {
2900 826 : ao_ref_init_from_ptr_and_size (&rhs_ref,
2901 : gimple_call_arg (call, 0),
2902 826 : TYPE_SIZE_UNIT (TREE_TYPE (lhs)));
2903 : /* We cannot make this a known-size access since otherwise
2904 : we disambiguate against refs to decls that are smaller. */
2905 826 : rhs_ref.size = -1;
2906 1652 : rhs_ref.ref_alias_set = rhs_ref.base_alias_set
2907 1652 : = tbaa_p ? get_deref_alias_set (TREE_TYPE
2908 : (gimple_call_arg (call, 1))) : 0;
2909 826 : return refs_may_alias_p_1 (ref, &rhs_ref, tbaa_p);
2910 : }
2911 0 : break;
2912 : }
2913 : default:;
2914 : }
2915 :
2916 46734855 : callee = gimple_call_fndecl (call);
2917 46734855 : if (callee != NULL_TREE)
2918 : {
2919 45242754 : struct cgraph_node *node = cgraph_node::get (callee);
2920 : /* We can not safely optimize based on summary of callee if it does
2921 : not always bind to current def: it is possible that memory load
2922 : was optimized out earlier and the interposed variant may not be
2923 : optimized this way. */
2924 45242754 : if (node && node->binds_to_current_def_p ())
2925 : {
2926 5752943 : modref_summary *summary = get_modref_function_summary (node);
2927 5752943 : if (summary && !summary->calls_interposable)
2928 : {
2929 3313307 : if (!modref_may_conflict (call, summary->loads, ref, tbaa_p))
2930 : {
2931 640536 : alias_stats.modref_use_no_alias++;
2932 640536 : if (dump_file && (dump_flags & TDF_DETAILS))
2933 : {
2934 24 : fprintf (dump_file,
2935 : "ipa-modref: call stmt ");
2936 24 : print_gimple_stmt (dump_file, call, 0);
2937 24 : fprintf (dump_file,
2938 : "ipa-modref: call to %s does not use ",
2939 : node->dump_name ());
2940 24 : if (!ref->ref && ref->base)
2941 : {
2942 3 : fprintf (dump_file, "base: ");
2943 3 : print_generic_expr (dump_file, ref->base);
2944 : }
2945 21 : else if (ref->ref)
2946 : {
2947 21 : fprintf (dump_file, "ref: ");
2948 21 : print_generic_expr (dump_file, ref->ref);
2949 : }
2950 24 : fprintf (dump_file, " alias sets: %i->%i\n",
2951 : ao_ref_base_alias_set (ref),
2952 : ao_ref_alias_set (ref));
2953 : }
2954 640536 : goto process_args;
2955 : }
2956 2672771 : alias_stats.modref_use_may_alias++;
2957 : }
2958 : }
2959 : }
2960 :
2961 46094319 : base = ao_ref_base (ref);
2962 46094319 : if (!base)
2963 : return true;
2964 :
2965 : /* If the reference is based on a decl that is not aliased the call
2966 : cannot possibly use it. */
2967 46094319 : if (DECL_P (base)
2968 41119970 : && !may_be_aliased (base)
2969 : /* But local statics can be used through recursion. */
2970 69210778 : && !is_global_var (base))
2971 22808844 : goto process_args;
2972 :
2973 23285475 : if (int res = check_fnspec (call, ref, false))
2974 : {
2975 19642112 : if (res == 1)
2976 : return true;
2977 : }
2978 : else
2979 3643363 : goto process_args;
2980 :
2981 : /* Check if base is a global static variable that is not read
2982 : by the function. */
2983 19105110 : if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
2984 : {
2985 973448 : struct cgraph_node *node = cgraph_node::get (callee);
2986 973448 : bitmap read;
2987 973448 : int id;
2988 :
2989 : /* FIXME: Callee can be an OMP builtin that does not have a call graph
2990 : node yet. We should enforce that there are nodes for all decls in the
2991 : IL and remove this check instead. */
2992 973448 : if (node
2993 972734 : && (id = ipa_reference_var_uid (base)) != -1
2994 153221 : && (read = ipa_reference_get_read_global (node))
2995 991098 : && !bitmap_bit_p (read, id))
2996 12383 : goto process_args;
2997 : }
2998 :
2999 : /* Check if the base variable is call-used. */
3000 19092727 : if (DECL_P (base))
3001 : {
3002 15623625 : if (pt_solution_includes (gimple_call_use_set (call), base))
3003 : return true;
3004 : }
3005 3469102 : else if ((TREE_CODE (base) == MEM_REF
3006 3469102 : || TREE_CODE (base) == TARGET_MEM_REF)
3007 3469102 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
3008 : {
3009 3468870 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
3010 3468870 : if (!pi)
3011 : return true;
3012 :
3013 3459391 : if (pt_solutions_intersect (gimple_call_use_set (call), &pi->pt))
3014 : return true;
3015 : }
3016 : else
3017 : return true;
3018 :
3019 : /* Inspect call arguments for passed-by-value aliases. */
3020 : process_args:
3021 90357072 : for (i = 0; i < gimple_call_num_args (call); ++i)
3022 : {
3023 63491207 : tree op = gimple_call_arg (call, i);
3024 63491207 : int flags = gimple_call_arg_flags (call, i);
3025 :
3026 63491207 : if (flags & (EAF_UNUSED | EAF_NO_DIRECT_READ))
3027 772263 : continue;
3028 :
3029 62718944 : if (TREE_CODE (op) == WITH_SIZE_EXPR)
3030 504 : op = TREE_OPERAND (op, 0);
3031 :
3032 62718944 : if (TREE_CODE (op) != SSA_NAME
3033 62718944 : && !is_gimple_min_invariant (op))
3034 : {
3035 10680186 : ao_ref r;
3036 10680186 : ao_ref_init (&r, op);
3037 10680186 : if (refs_may_alias_p_1 (&r, ref, tbaa_p))
3038 4250756 : return true;
3039 : }
3040 : }
3041 :
3042 : return false;
3043 : }
3044 :
3045 : static bool
3046 47103077 : ref_maybe_used_by_call_p (gcall *call, ao_ref *ref, bool tbaa_p)
3047 : {
3048 47103077 : bool res;
3049 47103077 : res = ref_maybe_used_by_call_p_1 (call, ref, tbaa_p);
3050 47103077 : if (res)
3051 20234503 : ++alias_stats.ref_maybe_used_by_call_p_may_alias;
3052 : else
3053 26868574 : ++alias_stats.ref_maybe_used_by_call_p_no_alias;
3054 47103077 : return res;
3055 : }
3056 :
3057 :
3058 : /* If the statement STMT may use the memory reference REF return
3059 : true, otherwise return false. */
3060 :
3061 : bool
3062 374457131 : ref_maybe_used_by_stmt_p (gimple *stmt, ao_ref *ref, bool tbaa_p)
3063 : {
3064 374457131 : if (is_gimple_assign (stmt))
3065 : {
3066 321056572 : tree rhs;
3067 :
3068 : /* All memory assign statements are single. */
3069 321056572 : if (!gimple_assign_single_p (stmt))
3070 : return false;
3071 :
3072 321056572 : rhs = gimple_assign_rhs1 (stmt);
3073 321056572 : if (is_gimple_reg (rhs)
3074 260971361 : || is_gimple_min_invariant (rhs)
3075 426297878 : || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
3076 257066434 : return false;
3077 :
3078 63990138 : return refs_may_alias_p (rhs, ref, tbaa_p);
3079 : }
3080 53400559 : else if (is_gimple_call (stmt))
3081 47103077 : return ref_maybe_used_by_call_p (as_a <gcall *> (stmt), ref, tbaa_p);
3082 6297482 : else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
3083 : {
3084 5523772 : tree retval = gimple_return_retval (return_stmt);
3085 5523772 : if (retval
3086 2919719 : && TREE_CODE (retval) != SSA_NAME
3087 2295543 : && !is_gimple_min_invariant (retval)
3088 7648825 : && refs_may_alias_p (retval, ref, tbaa_p))
3089 : return true;
3090 : /* If ref escapes the function then the return acts as a use. */
3091 3931730 : tree base = ao_ref_base (ref);
3092 3931730 : if (!base)
3093 : ;
3094 3931730 : else if (DECL_P (base))
3095 1479080 : return is_global_var (base);
3096 2452650 : else if (TREE_CODE (base) == MEM_REF
3097 2452650 : || TREE_CODE (base) == TARGET_MEM_REF)
3098 2452553 : return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0), false);
3099 : return false;
3100 : }
3101 :
3102 : return true;
3103 : }
3104 :
3105 : bool
3106 799897 : ref_maybe_used_by_stmt_p (gimple *stmt, tree ref, bool tbaa_p)
3107 : {
3108 799897 : ao_ref r;
3109 799897 : ao_ref_init (&r, ref);
3110 799897 : return ref_maybe_used_by_stmt_p (stmt, &r, tbaa_p);
3111 : }
3112 :
3113 : /* If the call in statement CALL may clobber the memory reference REF
3114 : return true, otherwise return false. */
3115 :
3116 : bool
3117 341222261 : call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref, bool tbaa_p)
3118 : {
3119 341222261 : tree base;
3120 341222261 : tree callee;
3121 :
3122 : /* If the call is pure or const it cannot clobber anything. */
3123 341222261 : if (gimple_call_flags (call)
3124 341222261 : & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
3125 : return false;
3126 334711355 : if (gimple_call_internal_p (call))
3127 818897 : switch (auto fn = gimple_call_internal_fn (call))
3128 : {
3129 : /* Treat these internal calls like ECF_PURE for aliasing,
3130 : they don't write to any memory the program should care about.
3131 : They have important other side-effects, and read memory,
3132 : so can't be ECF_NOVOPS. */
3133 : case IFN_UBSAN_NULL:
3134 : case IFN_UBSAN_BOUNDS:
3135 : case IFN_UBSAN_VPTR:
3136 : case IFN_UBSAN_OBJECT_SIZE:
3137 : case IFN_UBSAN_PTR:
3138 : case IFN_ASAN_CHECK:
3139 : return false;
3140 7798 : case IFN_MASK_STORE:
3141 7798 : case IFN_LEN_STORE:
3142 7798 : case IFN_MASK_LEN_STORE:
3143 7798 : case IFN_MASK_STORE_LANES:
3144 7798 : case IFN_MASK_LEN_STORE_LANES:
3145 7798 : {
3146 7798 : tree rhs = gimple_call_arg (call,
3147 7798 : internal_fn_stored_value_index (fn));
3148 7798 : ao_ref lhs_ref;
3149 7798 : ao_ref_init_from_ptr_and_size (&lhs_ref, gimple_call_arg (call, 0),
3150 7798 : TYPE_SIZE_UNIT (TREE_TYPE (rhs)));
3151 : /* We cannot make this a known-size access since otherwise
3152 : we disambiguate against refs to decls that are smaller. */
3153 7798 : lhs_ref.size = -1;
3154 15596 : lhs_ref.ref_alias_set = lhs_ref.base_alias_set
3155 7798 : = tbaa_p ? get_deref_alias_set
3156 7254 : (TREE_TYPE (gimple_call_arg (call, 1))) : 0;
3157 7798 : return refs_may_alias_p_1 (ref, &lhs_ref, tbaa_p);
3158 : }
3159 : default:
3160 : break;
3161 : }
3162 :
3163 334226839 : callee = gimple_call_fndecl (call);
3164 :
3165 334226839 : if (callee != NULL_TREE && !ref->volatile_p)
3166 : {
3167 314118421 : struct cgraph_node *node = cgraph_node::get (callee);
3168 314118421 : if (node)
3169 : {
3170 313830358 : modref_summary *summary = get_modref_function_summary (node);
3171 313830358 : if (summary)
3172 : {
3173 45447584 : if (!modref_may_conflict (call, summary->stores, ref, tbaa_p)
3174 45447584 : && (!summary->writes_errno
3175 272488 : || !targetm.ref_may_alias_errno (ref)))
3176 : {
3177 4238799 : alias_stats.modref_clobber_no_alias++;
3178 4238799 : if (dump_file && (dump_flags & TDF_DETAILS))
3179 : {
3180 52 : fprintf (dump_file,
3181 : "ipa-modref: call stmt ");
3182 52 : print_gimple_stmt (dump_file, call, 0);
3183 52 : fprintf (dump_file,
3184 : "ipa-modref: call to %s does not clobber ",
3185 : node->dump_name ());
3186 52 : if (!ref->ref && ref->base)
3187 : {
3188 32 : fprintf (dump_file, "base: ");
3189 32 : print_generic_expr (dump_file, ref->base);
3190 : }
3191 20 : else if (ref->ref)
3192 : {
3193 20 : fprintf (dump_file, "ref: ");
3194 20 : print_generic_expr (dump_file, ref->ref);
3195 : }
3196 52 : fprintf (dump_file, " alias sets: %i->%i\n",
3197 : ao_ref_base_alias_set (ref),
3198 : ao_ref_alias_set (ref));
3199 : }
3200 4238799 : return false;
3201 : }
3202 41208785 : alias_stats.modref_clobber_may_alias++;
3203 : }
3204 : }
3205 : }
3206 :
3207 329988040 : base = ao_ref_base (ref);
3208 329988040 : if (!base)
3209 : return true;
3210 :
3211 329988040 : if (TREE_CODE (base) == SSA_NAME
3212 329987445 : || CONSTANT_CLASS_P (base))
3213 : return false;
3214 :
3215 : /* A call that is not without side-effects might involve volatile
3216 : accesses and thus conflicts with all other volatile accesses. */
3217 321782221 : if (ref->volatile_p)
3218 : return true;
3219 :
3220 : /* If the reference is based on a decl that is not aliased the call
3221 : cannot possibly clobber it. */
3222 320321353 : if (DECL_P (base)
3223 290575539 : && !may_be_aliased (base)
3224 : /* But local non-readonly statics can be modified through recursion
3225 : or the call may implement a threading barrier which we must
3226 : treat as may-def. */
3227 516620620 : && (TREE_READONLY (base)
3228 188992170 : || !is_global_var (base)))
3229 : return false;
3230 :
3231 : /* If the reference is based on a pointer that points to memory
3232 : that may not be written to then the call cannot possibly clobber it. */
3233 134133247 : if ((TREE_CODE (base) == MEM_REF
3234 134133247 : || TREE_CODE (base) == TARGET_MEM_REF)
3235 29745814 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
3236 163496758 : && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base, 0)))
3237 : return false;
3238 :
3239 133811023 : if (int res = check_fnspec (call, ref, true))
3240 : {
3241 108195784 : if (res == 1)
3242 : return true;
3243 : }
3244 : else
3245 : return false;
3246 :
3247 : /* Check if base is a global static variable that is not written
3248 : by the function. */
3249 102459501 : if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
3250 : {
3251 10940975 : struct cgraph_node *node = cgraph_node::get (callee);
3252 10940975 : bitmap written;
3253 10940975 : int id;
3254 :
3255 10940975 : if (node
3256 10940470 : && (id = ipa_reference_var_uid (base)) != -1
3257 4832029 : && (written = ipa_reference_get_written_global (node))
3258 11036852 : && !bitmap_bit_p (written, id))
3259 : return false;
3260 : }
3261 :
3262 : /* Check if the base variable is call-clobbered. */
3263 102380447 : if (DECL_P (base))
3264 80489088 : return pt_solution_includes (gimple_call_clobber_set (call), base);
3265 21891359 : else if ((TREE_CODE (base) == MEM_REF
3266 21891359 : || TREE_CODE (base) == TARGET_MEM_REF)
3267 21891359 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
3268 : {
3269 21575759 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
3270 21575759 : if (!pi)
3271 : return true;
3272 :
3273 20748044 : return pt_solutions_intersect (gimple_call_clobber_set (call), &pi->pt);
3274 : }
3275 :
3276 : return true;
3277 : }
3278 :
3279 : /* If the call in statement CALL may clobber the memory reference REF
3280 : return true, otherwise return false. */
3281 :
3282 : bool
3283 361427 : call_may_clobber_ref_p (gcall *call, tree ref, bool tbaa_p)
3284 : {
3285 361427 : bool res;
3286 361427 : ao_ref r;
3287 361427 : ao_ref_init (&r, ref);
3288 361427 : res = call_may_clobber_ref_p_1 (call, &r, tbaa_p);
3289 361427 : if (res)
3290 42754 : ++alias_stats.call_may_clobber_ref_p_may_alias;
3291 : else
3292 318673 : ++alias_stats.call_may_clobber_ref_p_no_alias;
3293 361427 : return res;
3294 : }
3295 :
3296 :
3297 : /* If the statement STMT may clobber the memory reference REF return true,
3298 : otherwise return false. */
3299 :
3300 : bool
3301 2013538659 : stmt_may_clobber_ref_p_1 (gimple *stmt, ao_ref *ref, bool tbaa_p)
3302 : {
3303 2013538659 : if (is_gimple_call (stmt))
3304 : {
3305 346740188 : tree lhs = gimple_call_lhs (stmt);
3306 346740188 : if (lhs
3307 159892462 : && TREE_CODE (lhs) != SSA_NAME)
3308 : {
3309 62082883 : ao_ref r;
3310 62082883 : ao_ref_init (&r, lhs);
3311 62082883 : if (refs_may_alias_p_1 (ref, &r, tbaa_p))
3312 5978324 : return true;
3313 : }
3314 :
3315 340761864 : return call_may_clobber_ref_p_1 (as_a <gcall *> (stmt), ref, tbaa_p);
3316 : }
3317 1666798471 : else if (gimple_assign_single_p (stmt))
3318 : {
3319 1658354219 : tree lhs = gimple_assign_lhs (stmt);
3320 1658354219 : if (TREE_CODE (lhs) != SSA_NAME)
3321 : {
3322 1657447174 : ao_ref r;
3323 1657447174 : ao_ref_init (&r, lhs);
3324 1657447174 : return refs_may_alias_p_1 (ref, &r, tbaa_p);
3325 : }
3326 : }
3327 8444252 : else if (gimple_code (stmt) == GIMPLE_ASM)
3328 : return true;
3329 :
3330 : return false;
3331 : }
3332 :
3333 : bool
3334 4323390 : stmt_may_clobber_ref_p (gimple *stmt, tree ref, bool tbaa_p)
3335 : {
3336 4323390 : ao_ref r;
3337 4323390 : ao_ref_init (&r, ref);
3338 4323390 : return stmt_may_clobber_ref_p_1 (stmt, &r, tbaa_p);
3339 : }
3340 :
3341 : /* Return true if store1 and store2 described by corresponding tuples
3342 : <BASE, OFFSET, SIZE, MAX_SIZE> have the same size and store to the same
3343 : address. */
3344 :
3345 : static bool
3346 141882462 : same_addr_size_stores_p (tree base1, poly_int64 offset1, poly_int64 size1,
3347 : poly_int64 max_size1,
3348 : tree base2, poly_int64 offset2, poly_int64 size2,
3349 : poly_int64 max_size2)
3350 : {
3351 : /* Offsets need to be 0. */
3352 141882462 : if (maybe_ne (offset1, 0)
3353 141882462 : || maybe_ne (offset2, 0))
3354 : return false;
3355 :
3356 41549483 : bool base1_obj_p = SSA_VAR_P (base1);
3357 41549483 : bool base2_obj_p = SSA_VAR_P (base2);
3358 :
3359 : /* We need one object. */
3360 41549483 : if (base1_obj_p == base2_obj_p)
3361 : return false;
3362 5173720 : tree obj = base1_obj_p ? base1 : base2;
3363 :
3364 : /* And we need one MEM_REF. */
3365 5173720 : bool base1_memref_p = TREE_CODE (base1) == MEM_REF;
3366 5173720 : bool base2_memref_p = TREE_CODE (base2) == MEM_REF;
3367 5173720 : if (base1_memref_p == base2_memref_p)
3368 : return false;
3369 5076812 : tree memref = base1_memref_p ? base1 : base2;
3370 :
3371 : /* Sizes need to be valid. */
3372 5076812 : if (!known_size_p (max_size1)
3373 5054105 : || !known_size_p (max_size2)
3374 5053774 : || !known_size_p (size1)
3375 10130586 : || !known_size_p (size2))
3376 : return false;
3377 :
3378 : /* Max_size needs to match size. */
3379 5053774 : if (maybe_ne (max_size1, size1)
3380 5053774 : || maybe_ne (max_size2, size2))
3381 : return false;
3382 :
3383 : /* Sizes need to match. */
3384 5006977 : if (maybe_ne (size1, size2))
3385 : return false;
3386 :
3387 :
3388 : /* Check that memref is a store to pointer with singleton points-to info. */
3389 1296785 : if (!integer_zerop (TREE_OPERAND (memref, 1)))
3390 : return false;
3391 971868 : tree ptr = TREE_OPERAND (memref, 0);
3392 971868 : if (TREE_CODE (ptr) != SSA_NAME)
3393 : return false;
3394 971591 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
3395 971591 : unsigned int pt_uid;
3396 971591 : if (pi == NULL
3397 971591 : || !pt_solution_singleton_or_null_p (&pi->pt, &pt_uid))
3398 749001 : return false;
3399 :
3400 : /* Be conservative with non-call exceptions when the address might
3401 : be NULL. */
3402 222590 : if (cfun->can_throw_non_call_exceptions && pi->pt.null)
3403 : return false;
3404 :
3405 : /* Check that ptr points relative to obj. */
3406 222584 : unsigned int obj_uid = DECL_PT_UID (obj);
3407 222584 : if (obj_uid != pt_uid)
3408 : return false;
3409 :
3410 : /* Check that the object size is the same as the store size. That ensures us
3411 : that ptr points to the start of obj. */
3412 36812 : return (DECL_SIZE (obj)
3413 36812 : && poly_int_tree_p (DECL_SIZE (obj))
3414 110292 : && known_eq (wi::to_poly_offset (DECL_SIZE (obj)), size1));
3415 : }
3416 :
3417 : /* Return true if REF is killed by an store described by
3418 : BASE, OFFSET, SIZE and MAX_SIZE. */
3419 :
3420 : static bool
3421 238769118 : store_kills_ref_p (tree base, poly_int64 offset, poly_int64 size,
3422 : poly_int64 max_size, ao_ref *ref)
3423 : {
3424 238769118 : poly_int64 ref_offset = ref->offset;
3425 : /* We can get MEM[symbol: sZ, index: D.8862_1] here,
3426 : so base == ref->base does not always hold. */
3427 238769118 : if (base != ref->base)
3428 : {
3429 : /* Try using points-to info. */
3430 141882462 : if (same_addr_size_stores_p (base, offset, size, max_size, ref->base,
3431 : ref->offset, ref->size, ref->max_size))
3432 : return true;
3433 :
3434 : /* If both base and ref->base are MEM_REFs, only compare the
3435 : first operand, and if the second operand isn't equal constant,
3436 : try to add the offsets into offset and ref_offset. */
3437 36944619 : if (TREE_CODE (base) == MEM_REF && TREE_CODE (ref->base) == MEM_REF
3438 168608920 : && TREE_OPERAND (base, 0) == TREE_OPERAND (ref->base, 0))
3439 : {
3440 19895697 : if (!tree_int_cst_equal (TREE_OPERAND (base, 1),
3441 19895697 : TREE_OPERAND (ref->base, 1)))
3442 : {
3443 7337617 : poly_offset_int off1 = mem_ref_offset (base);
3444 7337617 : off1 <<= LOG2_BITS_PER_UNIT;
3445 7337617 : off1 += offset;
3446 7337617 : poly_offset_int off2 = mem_ref_offset (ref->base);
3447 7337617 : off2 <<= LOG2_BITS_PER_UNIT;
3448 7337617 : off2 += ref_offset;
3449 7337617 : if (!off1.to_shwi (&offset) || !off2.to_shwi (&ref_offset))
3450 0 : size = -1;
3451 : }
3452 : }
3453 : else
3454 121986621 : size = -1;
3455 : }
3456 : /* For a must-alias check we need to be able to constrain
3457 : the access properly. */
3458 238768974 : return (known_eq (size, max_size)
3459 238768974 : && known_subrange_p (ref_offset, ref->max_size, offset, size));
3460 : }
3461 :
3462 : /* If STMT kills the memory reference REF return true, otherwise
3463 : return false. */
3464 :
3465 : bool
3466 291306907 : stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
3467 : {
3468 291306907 : if (!ao_ref_base (ref))
3469 : return false;
3470 :
3471 291306907 : if (gimple_has_lhs (stmt)
3472 252814253 : && TREE_CODE (gimple_get_lhs (stmt)) != SSA_NAME
3473 : /* The assignment is not necessarily carried out if it can throw
3474 : and we can catch it in the current function where we could inspect
3475 : the previous value. Similarly if the function can throw externally
3476 : and the ref does not die on the function return.
3477 : ??? We only need to care about the RHS throwing. For aggregate
3478 : assignments or similar calls and non-call exceptions the LHS
3479 : might throw as well.
3480 : ??? We also should care about possible longjmp, but since we
3481 : do not understand that longjmp is not using global memory we will
3482 : not consider a kill here since the function call will be considered
3483 : as possibly using REF. */
3484 246823282 : && !stmt_can_throw_internal (cfun, stmt)
3485 267277266 : && (!stmt_can_throw_external (cfun, stmt)
3486 4190702 : || !ref_may_alias_global_p (ref, false)))
3487 : {
3488 242133103 : tree lhs = gimple_get_lhs (stmt);
3489 : /* If LHS is literally a base of the access we are done. */
3490 242133103 : if (ref->ref)
3491 : {
3492 240723972 : tree base = ref->ref;
3493 240723972 : tree innermost_dropped_array_ref = NULL_TREE;
3494 240723972 : if (handled_component_p (base))
3495 : {
3496 149577059 : tree saved_lhs0 = NULL_TREE;
3497 265204449 : if (handled_component_p (lhs))
3498 : {
3499 115627390 : saved_lhs0 = TREE_OPERAND (lhs, 0);
3500 115627390 : TREE_OPERAND (lhs, 0) = integer_zero_node;
3501 : }
3502 252866692 : do
3503 : {
3504 : /* Just compare the outermost handled component, if
3505 : they are equal we have found a possible common
3506 : base. */
3507 252866692 : tree saved_base0 = TREE_OPERAND (base, 0);
3508 252866692 : TREE_OPERAND (base, 0) = integer_zero_node;
3509 252866692 : bool res = operand_equal_p (lhs, base, 0);
3510 252866692 : TREE_OPERAND (base, 0) = saved_base0;
3511 252866692 : if (res)
3512 : break;
3513 : /* Remember if we drop an array-ref that we need to
3514 : double-check not being at struct end. */
3515 238009536 : if (TREE_CODE (base) == ARRAY_REF
3516 238009536 : || TREE_CODE (base) == ARRAY_RANGE_REF)
3517 66118926 : innermost_dropped_array_ref = base;
3518 : /* Otherwise drop handled components of the access. */
3519 238009536 : base = saved_base0;
3520 : }
3521 372729439 : while (handled_component_p (base));
3522 149577059 : if (saved_lhs0)
3523 115627390 : TREE_OPERAND (lhs, 0) = saved_lhs0;
3524 : }
3525 : /* Finally check if the lhs has the same address and size as the
3526 : base candidate of the access. Watch out if we have dropped
3527 : an array-ref that might have flexible size, this means ref->ref
3528 : may be outside of the TYPE_SIZE of its base. */
3529 149577059 : if ((! innermost_dropped_array_ref
3530 65328434 : || ! array_ref_flexible_size_p (innermost_dropped_array_ref))
3531 379496264 : && (lhs == base
3532 227552910 : || (((TYPE_SIZE (TREE_TYPE (lhs))
3533 227552910 : == TYPE_SIZE (TREE_TYPE (base)))
3534 154202012 : || (TYPE_SIZE (TREE_TYPE (lhs))
3535 154201949 : && TYPE_SIZE (TREE_TYPE (base))
3536 154201854 : && operand_equal_p (TYPE_SIZE (TREE_TYPE (lhs)),
3537 154201854 : TYPE_SIZE (TREE_TYPE (base)),
3538 : 0)))
3539 73350898 : && operand_equal_p (lhs, base,
3540 : OEP_ADDRESS_OF
3541 : | OEP_MATCH_SIDE_EFFECTS))))
3542 : {
3543 3077768 : ++alias_stats.stmt_kills_ref_p_yes;
3544 8967422 : return true;
3545 : }
3546 : }
3547 :
3548 : /* Now look for non-literal equal bases with the restriction of
3549 : handling constant offset and size. */
3550 : /* For a must-alias check we need to be able to constrain
3551 : the access properly. */
3552 239055335 : if (!ref->max_size_known_p ())
3553 : {
3554 1285437 : ++alias_stats.stmt_kills_ref_p_no;
3555 1285437 : return false;
3556 : }
3557 237769898 : poly_int64 size, offset, max_size;
3558 237769898 : bool reverse;
3559 237769898 : tree base = get_ref_base_and_extent (lhs, &offset, &size, &max_size,
3560 : &reverse);
3561 237769898 : if (store_kills_ref_p (base, offset, size, max_size, ref))
3562 : {
3563 1526449 : ++alias_stats.stmt_kills_ref_p_yes;
3564 1526449 : return true;
3565 : }
3566 : }
3567 :
3568 285417253 : if (is_gimple_call (stmt))
3569 : {
3570 24229593 : tree callee = gimple_call_fndecl (stmt);
3571 24229593 : struct cgraph_node *node;
3572 24229593 : modref_summary *summary;
3573 :
3574 : /* Try to disambiguate using modref summary. Modref records a vector
3575 : of stores with known offsets relative to function parameters that must
3576 : happen every execution of function. Find if we have a matching
3577 : store and verify that function can not use the value. */
3578 24229593 : if (callee != NULL_TREE
3579 23070342 : && (node = cgraph_node::get (callee)) != NULL
3580 23027956 : && node->binds_to_current_def_p ()
3581 2180944 : && (summary = get_modref_function_summary (node)) != NULL
3582 1170722 : && summary->kills.length ()
3583 : /* Check that we can not trap while evaluating function
3584 : parameters. This check is overly conservative. */
3585 24329035 : && (!cfun->can_throw_non_call_exceptions
3586 0 : || (!stmt_can_throw_internal (cfun, stmt)
3587 0 : && (!stmt_can_throw_external (cfun, stmt)
3588 0 : || !ref_may_alias_global_p (ref, false)))))
3589 : {
3590 418800 : for (auto kill : summary->kills)
3591 : {
3592 128740 : ao_ref dref;
3593 :
3594 : /* We only can do useful compares if we know the access range
3595 : precisely. */
3596 128740 : if (!kill.get_ao_ref (as_a <gcall *> (stmt), &dref))
3597 24 : continue;
3598 128716 : if (store_kills_ref_p (ao_ref_base (&dref), dref.offset,
3599 : dref.size, dref.max_size, ref))
3600 : {
3601 : /* For store to be killed it needs to not be used
3602 : earlier. */
3603 8266 : if (ref_maybe_used_by_call_p_1 (as_a <gcall *> (stmt), ref,
3604 : true)
3605 8266 : || !dbg_cnt (ipa_mod_ref))
3606 : break;
3607 3434 : if (dump_file && (dump_flags & TDF_DETAILS))
3608 : {
3609 2 : fprintf (dump_file,
3610 : "ipa-modref: call stmt ");
3611 2 : print_gimple_stmt (dump_file, stmt, 0);
3612 2 : fprintf (dump_file,
3613 : "ipa-modref: call to %s kills ",
3614 : node->dump_name ());
3615 2 : print_generic_expr (dump_file, ref->base);
3616 2 : fprintf (dump_file, "\n");
3617 : }
3618 3434 : ++alias_stats.modref_kill_yes;
3619 3434 : return true;
3620 : }
3621 : }
3622 96008 : ++alias_stats.modref_kill_no;
3623 : }
3624 24226159 : if (callee != NULL_TREE
3625 24226159 : && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
3626 4763184 : switch (DECL_FUNCTION_CODE (callee))
3627 : {
3628 636818 : case BUILT_IN_FREE:
3629 636818 : {
3630 636818 : tree ptr = gimple_call_arg (stmt, 0);
3631 636818 : tree base = ao_ref_base (ref);
3632 636818 : if (base && TREE_CODE (base) == MEM_REF
3633 780552 : && TREE_OPERAND (base, 0) == ptr)
3634 : {
3635 27948 : ++alias_stats.stmt_kills_ref_p_yes;
3636 27948 : return true;
3637 : }
3638 : break;
3639 : }
3640 :
3641 1381416 : case BUILT_IN_MEMCPY:
3642 1381416 : case BUILT_IN_MEMPCPY:
3643 1381416 : case BUILT_IN_MEMMOVE:
3644 1381416 : case BUILT_IN_MEMSET:
3645 1381416 : case BUILT_IN_MEMCPY_CHK:
3646 1381416 : case BUILT_IN_MEMPCPY_CHK:
3647 1381416 : case BUILT_IN_MEMMOVE_CHK:
3648 1381416 : case BUILT_IN_MEMSET_CHK:
3649 1381416 : case BUILT_IN_STRNCPY:
3650 1381416 : case BUILT_IN_STPNCPY:
3651 1381416 : case BUILT_IN_CALLOC:
3652 1381416 : {
3653 : /* For a must-alias check we need to be able to constrain
3654 : the access properly. */
3655 1381416 : if (!ref->max_size_known_p ())
3656 : {
3657 64149 : ++alias_stats.stmt_kills_ref_p_no;
3658 580405 : return false;
3659 : }
3660 1317267 : tree dest;
3661 1317267 : tree len;
3662 :
3663 : /* In execution order a calloc call will never kill
3664 : anything. However, DSE will (ab)use this interface
3665 : to ask if a calloc call writes the same memory locations
3666 : as a later assignment, memset, etc. So handle calloc
3667 : in the expected way. */
3668 1317267 : if (DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC)
3669 : {
3670 1680 : tree arg0 = gimple_call_arg (stmt, 0);
3671 1680 : tree arg1 = gimple_call_arg (stmt, 1);
3672 1680 : if (TREE_CODE (arg0) != INTEGER_CST
3673 1538 : || TREE_CODE (arg1) != INTEGER_CST)
3674 : {
3675 174 : ++alias_stats.stmt_kills_ref_p_no;
3676 174 : return false;
3677 : }
3678 :
3679 1506 : dest = gimple_call_lhs (stmt);
3680 1506 : if (!dest)
3681 : {
3682 1 : ++alias_stats.stmt_kills_ref_p_no;
3683 1 : return false;
3684 : }
3685 1505 : len = fold_build2 (MULT_EXPR, TREE_TYPE (arg0), arg0, arg1);
3686 : }
3687 : else
3688 : {
3689 1315587 : dest = gimple_call_arg (stmt, 0);
3690 1315587 : len = gimple_call_arg (stmt, 2);
3691 : }
3692 1317092 : if (!poly_int_tree_p (len))
3693 : return false;
3694 870504 : ao_ref dref;
3695 870504 : ao_ref_init_from_ptr_and_size (&dref, dest, len);
3696 870504 : if (store_kills_ref_p (ao_ref_base (&dref), dref.offset,
3697 : dref.size, dref.max_size, ref))
3698 : {
3699 5344 : ++alias_stats.stmt_kills_ref_p_yes;
3700 5344 : return true;
3701 : }
3702 865160 : break;
3703 : }
3704 :
3705 5840 : case BUILT_IN_VA_END:
3706 5840 : {
3707 5840 : tree ptr = gimple_call_arg (stmt, 0);
3708 5840 : if (TREE_CODE (ptr) == ADDR_EXPR)
3709 : {
3710 5789 : tree base = ao_ref_base (ref);
3711 5789 : if (TREE_OPERAND (ptr, 0) == base)
3712 : {
3713 1378 : ++alias_stats.stmt_kills_ref_p_yes;
3714 1378 : return true;
3715 : }
3716 : }
3717 : break;
3718 : }
3719 :
3720 : default:;
3721 : }
3722 : }
3723 284868237 : ++alias_stats.stmt_kills_ref_p_no;
3724 284868237 : return false;
3725 : }
3726 :
3727 : bool
3728 0 : stmt_kills_ref_p (gimple *stmt, tree ref)
3729 : {
3730 0 : ao_ref r;
3731 0 : ao_ref_init (&r, ref);
3732 0 : return stmt_kills_ref_p (stmt, &r);
3733 : }
3734 :
3735 : /* Return whether REF can be subject to store data races. */
3736 :
3737 : bool
3738 34298 : ref_can_have_store_data_races (tree ref)
3739 : {
3740 : /* With -fallow-store-data-races do not care about them. */
3741 34298 : if (flag_store_data_races)
3742 : return false;
3743 :
3744 34096 : tree base = get_base_address (ref);
3745 34096 : if (auto_var_p (base)
3746 34096 : && ! may_be_aliased (base))
3747 : /* Automatic variables not aliased are not subject to
3748 : data races. */
3749 : return false;
3750 :
3751 : return true;
3752 : }
3753 :
3754 :
3755 : /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
3756 : TARGET or a statement clobbering the memory reference REF in which
3757 : case false is returned. The walk starts with VUSE, one argument of PHI. */
3758 :
3759 : static bool
3760 133719220 : maybe_skip_until (gimple *phi, tree &target, basic_block target_bb,
3761 : ao_ref *ref, tree vuse, bool tbaa_p, unsigned int &limit,
3762 : bitmap *visited, bool abort_on_visited,
3763 : void *(*translate)(ao_ref *, tree, void *, translate_flags *),
3764 : bool (*is_backedge)(edge, void *),
3765 : translate_flags disambiguate_only,
3766 : void *data)
3767 : {
3768 133719220 : basic_block bb = gimple_bb (phi);
3769 :
3770 133719220 : if (!*visited)
3771 : {
3772 24657951 : *visited = BITMAP_ALLOC (NULL);
3773 24657951 : bitmap_tree_view (*visited);
3774 : }
3775 :
3776 133719220 : bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
3777 :
3778 : /* Walk until we hit the target. */
3779 133719220 : while (vuse != target)
3780 : {
3781 421916361 : gimple *def_stmt = SSA_NAME_DEF_STMT (vuse);
3782 : /* If we are searching for the target VUSE by walking up to
3783 : TARGET_BB dominating the original PHI we are finished once
3784 : we reach a default def or a definition in a block dominating
3785 : that block. Update TARGET and return. */
3786 421916361 : if (!target
3787 421916361 : && (gimple_nop_p (def_stmt)
3788 71988137 : || dominated_by_p (CDI_DOMINATORS,
3789 71988137 : target_bb, gimple_bb (def_stmt))))
3790 : {
3791 19688348 : target = vuse;
3792 19688348 : return true;
3793 : }
3794 :
3795 : /* Recurse for PHI nodes. */
3796 402228013 : if (gphi *phi = dyn_cast <gphi *> (def_stmt))
3797 : {
3798 : /* An already visited PHI node ends the walk successfully. */
3799 76434350 : if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (phi))))
3800 35669010 : return !abort_on_visited;
3801 40765340 : vuse = get_continuation_for_phi (phi, ref, tbaa_p, limit,
3802 : visited, abort_on_visited,
3803 : translate, data, is_backedge,
3804 : disambiguate_only);
3805 40765340 : if (!vuse)
3806 : return false;
3807 36360228 : continue;
3808 : }
3809 325793663 : else if (gimple_nop_p (def_stmt))
3810 : return false;
3811 : else
3812 : {
3813 : /* A clobbering statement or the end of the IL ends it failing. */
3814 325793663 : if ((int)limit <= 0)
3815 : return false;
3816 325758608 : --limit;
3817 325758608 : if (stmt_may_clobber_ref_p_1 (def_stmt, ref, tbaa_p))
3818 : {
3819 19004060 : translate_flags tf = disambiguate_only;
3820 19004060 : if (translate
3821 19004060 : && (*translate) (ref, vuse, data, &tf) == NULL)
3822 : ;
3823 : else
3824 15678623 : return false;
3825 : }
3826 : }
3827 : /* If we reach a new basic-block see if we already skipped it
3828 : in a previous walk that ended successfully. */
3829 310079985 : if (gimple_bb (def_stmt) != bb)
3830 : {
3831 134990805 : if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (vuse)))
3832 11108175 : return !abort_on_visited;
3833 123882630 : bb = gimple_bb (def_stmt);
3834 : }
3835 768023068 : vuse = gimple_vuse (def_stmt);
3836 : }
3837 : return true;
3838 : }
3839 :
3840 :
3841 : /* Starting from a PHI node for the virtual operand of the memory reference
3842 : REF find a continuation virtual operand that allows to continue walking
3843 : statements dominating PHI skipping only statements that cannot possibly
3844 : clobber REF. Decrements LIMIT for each alias disambiguation done
3845 : and aborts the walk, returning NULL_TREE if it reaches zero.
3846 : Returns NULL_TREE if no suitable virtual operand can be found. */
3847 :
3848 : tree
3849 104557937 : get_continuation_for_phi (gphi *phi, ao_ref *ref, bool tbaa_p,
3850 : unsigned int &limit, bitmap *visited,
3851 : bool abort_on_visited,
3852 : void *(*translate)(ao_ref *, tree, void *,
3853 : translate_flags *),
3854 : void *data,
3855 : bool (*is_backedge)(edge, void *),
3856 : translate_flags disambiguate_only)
3857 : {
3858 104557937 : unsigned nargs = gimple_phi_num_args (phi);
3859 :
3860 : /* Through a single-argument PHI we can simply look through. */
3861 104557937 : if (nargs == 1)
3862 4544879 : return PHI_ARG_DEF (phi, 0);
3863 :
3864 : /* For two or more arguments try to pairwise skip non-aliasing code
3865 : until we hit the phi argument definition that dominates the other one. */
3866 100013058 : basic_block phi_bb = gimple_bb (phi);
3867 100013058 : tree arg0, arg1;
3868 100013058 : unsigned i;
3869 :
3870 : /* Find a candidate for the virtual operand which definition
3871 : dominates those of all others. */
3872 : /* First look if any of the args themselves satisfy this. */
3873 184492608 : for (i = 0; i < nargs; ++i)
3874 : {
3875 160386554 : arg0 = PHI_ARG_DEF (phi, i);
3876 160386554 : if (SSA_NAME_IS_DEFAULT_DEF (arg0))
3877 : break;
3878 157115953 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (arg0));
3879 157115953 : if (def_bb != phi_bb
3880 157115953 : && dominated_by_p (CDI_DOMINATORS, phi_bb, def_bb))
3881 : break;
3882 84479550 : arg0 = NULL_TREE;
3883 : }
3884 : /* If not, look if we can reach such candidate by walking defs
3885 : until we hit the immediate dominator. maybe_skip_until will
3886 : do that for us. */
3887 100013058 : basic_block dom = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
3888 :
3889 : /* Then check against the (to be) found candidate. */
3890 389428891 : for (i = 0; i < nargs; ++i)
3891 : {
3892 209648957 : arg1 = PHI_ARG_DEF (phi, i);
3893 209648957 : if (arg1 == arg0)
3894 : ;
3895 267438440 : else if (! maybe_skip_until (phi, arg0, dom, ref, arg1, tbaa_p,
3896 : limit, visited,
3897 : abort_on_visited,
3898 : translate, is_backedge,
3899 : /* Do not valueize when walking over
3900 : backedges. */
3901 : (is_backedge
3902 124406619 : && !is_backedge
3903 124406619 : (gimple_phi_arg_edge (phi, i), data))
3904 : ? disambiguate_only : TR_DISAMBIGUATE,
3905 : data))
3906 : return NULL_TREE;
3907 : }
3908 :
3909 79766876 : return arg0;
3910 : }
3911 :
3912 : /* Based on the memory reference REF and its virtual use VUSE call
3913 : WALKER for each virtual use that is equivalent to VUSE, including VUSE
3914 : itself. That is, for each virtual use for which its defining statement
3915 : does not clobber REF.
3916 :
3917 : WALKER is called with REF, the current virtual use and DATA. If
3918 : WALKER returns non-NULL the walk stops and its result is returned.
3919 : At the end of a non-successful walk NULL is returned.
3920 :
3921 : TRANSLATE if non-NULL is called with a pointer to REF, the virtual
3922 : use which definition is a statement that may clobber REF and DATA.
3923 : If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
3924 : If TRANSLATE returns non-NULL the walk stops and its result is returned.
3925 : If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
3926 : to adjust REF and *DATA to make that valid.
3927 :
3928 : VALUEIZE if non-NULL is called with the next VUSE that is considered
3929 : and return value is substituted for that. This can be used to
3930 : implement optimistic value-numbering for example. Note that the
3931 : VUSE argument is assumed to be valueized already.
3932 :
3933 : LIMIT specifies the number of alias queries we are allowed to do,
3934 : the walk stops when it reaches zero and NULL is returned. LIMIT
3935 : is decremented by the number of alias queries (plus adjustments
3936 : done by the callbacks) upon return.
3937 :
3938 : TODO: Cache the vector of equivalent vuses per ref, vuse pair. */
3939 :
3940 : void *
3941 69456143 : walk_non_aliased_vuses (ao_ref *ref, tree vuse, bool tbaa_p,
3942 : void *(*walker)(ao_ref *, tree, void *),
3943 : void *(*translate)(ao_ref *, tree, void *,
3944 : translate_flags *),
3945 : bool (*is_backedge)(edge, void *),
3946 : tree (*valueize)(tree),
3947 : unsigned &limit, void *data)
3948 : {
3949 69456143 : bitmap visited = NULL;
3950 69456143 : void *res;
3951 69456143 : bool translated = false;
3952 :
3953 69456143 : timevar_push (TV_ALIAS_STMT_WALK);
3954 :
3955 1115302348 : do
3956 : {
3957 1115302348 : gimple *def_stmt;
3958 :
3959 : /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
3960 1115302348 : res = (*walker) (ref, vuse, data);
3961 : /* Abort walk. */
3962 1115302348 : if (res == (void *)-1)
3963 : {
3964 : res = NULL;
3965 : break;
3966 : }
3967 : /* Lookup succeeded. */
3968 1115302153 : else if (res != NULL)
3969 : break;
3970 :
3971 1106774065 : if (valueize)
3972 : {
3973 1088180065 : vuse = valueize (vuse);
3974 1088180065 : if (!vuse)
3975 : {
3976 : res = NULL;
3977 : break;
3978 : }
3979 : }
3980 1090397319 : def_stmt = SSA_NAME_DEF_STMT (vuse);
3981 1090397319 : if (gimple_nop_p (def_stmt))
3982 : break;
3983 1087732808 : else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
3984 60580330 : vuse = get_continuation_for_phi (phi, ref, tbaa_p, limit,
3985 : &visited, translated, translate, data,
3986 : is_backedge);
3987 : else
3988 : {
3989 1027152478 : if ((int)limit <= 0)
3990 : {
3991 : res = NULL;
3992 : break;
3993 : }
3994 1026907021 : --limit;
3995 1026907021 : if (stmt_may_clobber_ref_p_1 (def_stmt, ref, tbaa_p))
3996 : {
3997 32914410 : if (!translate)
3998 : break;
3999 27620690 : translate_flags disambiguate_only = TR_TRANSLATE;
4000 27620690 : res = (*translate) (ref, vuse, data, &disambiguate_only);
4001 : /* Failed lookup and translation. */
4002 27620690 : if (res == (void *)-1)
4003 : {
4004 : res = NULL;
4005 : break;
4006 : }
4007 : /* Lookup succeeded. */
4008 6446066 : else if (res != NULL)
4009 : break;
4010 : /* Translation succeeded, continue walking. */
4011 8468665 : translated = translated || disambiguate_only == TR_TRANSLATE;
4012 : }
4013 999246622 : vuse = gimple_vuse (def_stmt);
4014 : }
4015 : }
4016 1059826952 : while (vuse);
4017 :
4018 69456143 : if (visited)
4019 22123034 : BITMAP_FREE (visited);
4020 :
4021 69456143 : timevar_pop (TV_ALIAS_STMT_WALK);
4022 :
4023 69456143 : return res;
4024 : }
4025 :
4026 :
4027 : /* Based on the memory reference REF call WALKER for each vdef whose
4028 : defining statement may clobber REF, starting with VDEF. If REF
4029 : is NULL_TREE, each defining statement is visited.
4030 :
4031 : WALKER is called with REF, the current vdef and DATA. If WALKER
4032 : returns true the walk is stopped, otherwise it continues.
4033 :
4034 : If function entry is reached, FUNCTION_ENTRY_REACHED is set to true.
4035 : The pointer may be NULL and then we do not track this information.
4036 :
4037 : At PHI nodes walk_aliased_vdefs forks into one walk for each
4038 : PHI argument (but only one walk continues at merge points), the
4039 : return value is true if any of the walks was successful.
4040 :
4041 : The function returns the number of statements walked or -1 if
4042 : LIMIT stmts were walked and the walk was aborted at this point.
4043 : If LIMIT is zero the walk is not aborted. */
4044 :
4045 : static int
4046 294365435 : walk_aliased_vdefs_1 (ao_ref *ref, tree vdef,
4047 : bool (*walker)(ao_ref *, tree, void *), void *data,
4048 : bitmap *visited, unsigned int cnt,
4049 : bool *function_entry_reached, unsigned limit)
4050 : {
4051 934505111 : do
4052 : {
4053 1869010222 : gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
4054 :
4055 934505111 : if (*visited
4056 934505111 : && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
4057 165314633 : return cnt;
4058 :
4059 769190478 : if (gimple_nop_p (def_stmt))
4060 : {
4061 24783593 : if (function_entry_reached)
4062 3939606 : *function_entry_reached = true;
4063 24783593 : return cnt;
4064 : }
4065 744406885 : else if (gimple_code (def_stmt) == GIMPLE_PHI)
4066 : {
4067 88691757 : unsigned i;
4068 88691757 : if (!*visited)
4069 : {
4070 8177976 : *visited = BITMAP_ALLOC (NULL);
4071 8177976 : bitmap_tree_view (*visited);
4072 : }
4073 279548126 : for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
4074 : {
4075 195918352 : int res = walk_aliased_vdefs_1 (ref,
4076 : gimple_phi_arg_def (def_stmt, i),
4077 : walker, data, visited, cnt,
4078 : function_entry_reached, limit);
4079 195918352 : if (res == -1)
4080 : return -1;
4081 190856369 : cnt = res;
4082 : }
4083 83629774 : return cnt;
4084 : }
4085 :
4086 : /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
4087 655715128 : cnt++;
4088 655715128 : if (cnt == limit)
4089 : return -1;
4090 655561294 : if ((!ref
4091 579138251 : || stmt_may_clobber_ref_p_1 (def_stmt, ref))
4092 730982056 : && (*walker) (ref, vdef, data))
4093 15421618 : return cnt;
4094 :
4095 1574644787 : vdef = gimple_vuse (def_stmt);
4096 : }
4097 : while (1);
4098 : }
4099 :
4100 : int
4101 98447083 : walk_aliased_vdefs (ao_ref *ref, tree vdef,
4102 : bool (*walker)(ao_ref *, tree, void *), void *data,
4103 : bitmap *visited,
4104 : bool *function_entry_reached, unsigned int limit)
4105 : {
4106 98447083 : bitmap local_visited = NULL;
4107 98447083 : int ret;
4108 :
4109 98447083 : timevar_push (TV_ALIAS_STMT_WALK);
4110 :
4111 98447083 : if (function_entry_reached)
4112 4960047 : *function_entry_reached = false;
4113 :
4114 170038600 : ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
4115 : visited ? visited : &local_visited, 0,
4116 : function_entry_reached, limit);
4117 98447083 : if (local_visited)
4118 8177976 : BITMAP_FREE (local_visited);
4119 :
4120 98447083 : timevar_pop (TV_ALIAS_STMT_WALK);
4121 :
4122 98447083 : return ret;
4123 : }
4124 :
4125 : /* Verify validity of the fnspec string.
4126 : See attr-fnspec.h for details. */
4127 :
4128 : void
4129 461451689 : attr_fnspec::verify ()
4130 : {
4131 461451689 : bool err = false;
4132 461451689 : if (!len)
4133 : return;
4134 :
4135 : /* Check return value specifier. */
4136 148678333 : if (len < return_desc_size)
4137 : err = true;
4138 148678333 : else if ((len - return_desc_size) % arg_desc_size)
4139 : err = true;
4140 148678333 : else if ((str[0] < '1' || str[0] > '4')
4141 148678333 : && str[0] != '.' && str[0] != 'm')
4142 0 : err = true;
4143 :
4144 148678333 : switch (str[1])
4145 : {
4146 : case ' ':
4147 : case 'p':
4148 : case 'P':
4149 : case 'c':
4150 : case 'C':
4151 : break;
4152 : default:
4153 : err = true;
4154 : }
4155 148678333 : if (err)
4156 0 : internal_error ("invalid fn spec attribute \"%s\"", str);
4157 :
4158 : /* Now check all parameters. */
4159 439134169 : for (unsigned int i = 0; arg_specified_p (i); i++)
4160 : {
4161 290455836 : unsigned int idx = arg_idx (i);
4162 290455836 : switch (str[idx])
4163 : {
4164 270654205 : case 'x':
4165 270654205 : case 'X':
4166 270654205 : case 'r':
4167 270654205 : case 'R':
4168 270654205 : case 'o':
4169 270654205 : case 'O':
4170 270654205 : case 'w':
4171 270654205 : case 'W':
4172 270654205 : case '.':
4173 270654205 : if ((str[idx + 1] >= '1' && str[idx + 1] <= '9')
4174 270654205 : || str[idx + 1] == 't')
4175 : {
4176 43072203 : if (str[idx] != 'r' && str[idx] != 'R'
4177 : && str[idx] != 'w' && str[idx] != 'W'
4178 : && str[idx] != 'o' && str[idx] != 'O')
4179 43072203 : err = true;
4180 43072203 : if (str[idx + 1] != 't'
4181 : /* Size specified is scalar, so it should be described
4182 : by ". " if specified at all. */
4183 43072203 : && (arg_specified_p (str[idx + 1] - '1')
4184 0 : && str[arg_idx (str[idx + 1] - '1')] != '.'))
4185 : err = true;
4186 : }
4187 227582002 : else if (str[idx + 1] != ' ')
4188 : err = true;
4189 : break;
4190 19801631 : default:
4191 19801631 : if (str[idx] < '1' || str[idx] > '9')
4192 : err = true;
4193 : }
4194 290455836 : if (err)
4195 0 : internal_error ("invalid fn spec attribute \"%s\" arg %i", str, i);
4196 : }
4197 : }
4198 :
4199 : /* Return true if TYPE1 and TYPE2 will always give the same answer
4200 : when compared with other types using same_type_for_tbaa. */
4201 :
4202 : static bool
4203 22485920 : types_equal_for_same_type_for_tbaa_p (tree type1, tree type2,
4204 : bool lto_streaming_safe)
4205 : {
4206 : /* We use same_type_for_tbaa_p to match types in the access path.
4207 : This check is overly conservative. */
4208 22485920 : type1 = TYPE_MAIN_VARIANT (type1);
4209 22485920 : type2 = TYPE_MAIN_VARIANT (type2);
4210 :
4211 22485920 : if (TYPE_STRUCTURAL_EQUALITY_P (type1)
4212 22485920 : != TYPE_STRUCTURAL_EQUALITY_P (type2))
4213 : return false;
4214 22207369 : if (TYPE_STRUCTURAL_EQUALITY_P (type1))
4215 : return true;
4216 :
4217 18467218 : if (lto_streaming_safe)
4218 88177 : return type1 == type2;
4219 : else
4220 18379041 : return TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2);
4221 : }
4222 :
4223 : /* Return true if TYPE1 and TYPE2 will always give the same answer
4224 : when compared with other types using same_type_for_tbaa. */
4225 :
4226 : bool
4227 22288124 : types_equal_for_same_type_for_tbaa_p (tree type1, tree type2)
4228 : {
4229 22288124 : return types_equal_for_same_type_for_tbaa_p (type1, type2,
4230 22288124 : lto_streaming_expected_p ());
4231 : }
4232 :
4233 : /* Compare REF1 and REF2 and return flags specifying their differences.
4234 : If LTO_STREAMING_SAFE is true do not use alias sets and canonical
4235 : types that are going to be recomputed.
4236 : If TBAA is true also compare TBAA metadata. */
4237 :
4238 : int
4239 117245 : ao_compare::compare_ao_refs (ao_ref *ref1, ao_ref *ref2,
4240 : bool lto_streaming_safe,
4241 : bool tbaa)
4242 : {
4243 117245 : if (TREE_THIS_VOLATILE (ref1->ref) != TREE_THIS_VOLATILE (ref2->ref))
4244 : return SEMANTICS;
4245 117233 : tree base1 = ao_ref_base (ref1);
4246 117233 : tree base2 = ao_ref_base (ref2);
4247 :
4248 117233 : if (!known_eq (ref1->offset, ref2->offset)
4249 117233 : || !known_eq (ref1->size, ref2->size)
4250 234466 : || !known_eq (ref1->max_size, ref2->max_size))
4251 : return SEMANTICS;
4252 :
4253 : /* For variable accesses we need to compare actual paths
4254 : to check that both refs are accessing same address and the access size. */
4255 117225 : if (!known_eq (ref1->size, ref1->max_size))
4256 : {
4257 2042 : if (!operand_equal_p (TYPE_SIZE (TREE_TYPE (ref1->ref)),
4258 2042 : TYPE_SIZE (TREE_TYPE (ref2->ref)), 0))
4259 : return SEMANTICS;
4260 2042 : tree r1 = ref1->ref;
4261 2042 : tree r2 = ref2->ref;
4262 :
4263 : /* Handle toplevel COMPONENT_REFs of bitfields.
4264 : Those are special since they are not allowed in
4265 : ADDR_EXPR. */
4266 2042 : if (TREE_CODE (r1) == COMPONENT_REF
4267 2042 : && DECL_BIT_FIELD (TREE_OPERAND (r1, 1)))
4268 : {
4269 0 : if (TREE_CODE (r2) != COMPONENT_REF
4270 0 : || !DECL_BIT_FIELD (TREE_OPERAND (r2, 1)))
4271 : return SEMANTICS;
4272 0 : tree field1 = TREE_OPERAND (r1, 1);
4273 0 : tree field2 = TREE_OPERAND (r2, 1);
4274 0 : if (!operand_equal_p (DECL_FIELD_OFFSET (field1),
4275 0 : DECL_FIELD_OFFSET (field2), 0)
4276 0 : || !operand_equal_p (DECL_FIELD_BIT_OFFSET (field1),
4277 0 : DECL_FIELD_BIT_OFFSET (field2), 0)
4278 0 : || !operand_equal_p (DECL_SIZE (field1), DECL_SIZE (field2), 0)
4279 0 : || !types_compatible_p (TREE_TYPE (r1),
4280 0 : TREE_TYPE (r2)))
4281 0 : return SEMANTICS;
4282 0 : r1 = TREE_OPERAND (r1, 0);
4283 0 : r2 = TREE_OPERAND (r2, 0);
4284 : }
4285 2042 : else if (TREE_CODE (r2) == COMPONENT_REF
4286 2042 : && DECL_BIT_FIELD (TREE_OPERAND (r2, 1)))
4287 : return SEMANTICS;
4288 :
4289 : /* Similarly for bit field refs. */
4290 2042 : if (TREE_CODE (r1) == BIT_FIELD_REF)
4291 : {
4292 0 : if (TREE_CODE (r2) != BIT_FIELD_REF
4293 0 : || !operand_equal_p (TREE_OPERAND (r1, 1),
4294 0 : TREE_OPERAND (r2, 1), 0)
4295 0 : || !operand_equal_p (TREE_OPERAND (r1, 2),
4296 0 : TREE_OPERAND (r2, 2), 0)
4297 0 : || !types_compatible_p (TREE_TYPE (r1),
4298 0 : TREE_TYPE (r2)))
4299 0 : return SEMANTICS;
4300 0 : r1 = TREE_OPERAND (r1, 0);
4301 0 : r2 = TREE_OPERAND (r2, 0);
4302 : }
4303 2042 : else if (TREE_CODE (r2) == BIT_FIELD_REF)
4304 : return SEMANTICS;
4305 :
4306 : /* Now we can compare the address of actual memory access. */
4307 2042 : if (!operand_equal_p (r1, r2, OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS))
4308 : return SEMANTICS;
4309 : }
4310 : /* For constant accesses we get more matches by comparing offset only. */
4311 115183 : else if (!operand_equal_p (base1, base2,
4312 : OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS))
4313 : return SEMANTICS;
4314 :
4315 : /* We can't simply use get_object_alignment_1 on the full
4316 : reference as for accesses with variable indexes this reports
4317 : too conservative alignment. */
4318 117064 : unsigned int align1, align2;
4319 117064 : unsigned HOST_WIDE_INT bitpos1, bitpos2;
4320 117064 : bool known1 = get_object_alignment_1 (base1, &align1, &bitpos1);
4321 117064 : bool known2 = get_object_alignment_1 (base2, &align2, &bitpos2);
4322 : /* ??? For MEMREF get_object_alignment_1 determines aligned from
4323 : TYPE_ALIGN but still returns false. This seem to contradict
4324 : its description. So compare even if alignment is unknown. */
4325 117064 : if (known1 != known2
4326 117064 : || (bitpos1 != bitpos2 || align1 != align2))
4327 : return SEMANTICS;
4328 :
4329 : /* Now we know that accesses are semantically same. */
4330 116849 : int flags = 0;
4331 :
4332 : /* ao_ref_base strips inner MEM_REF [&decl], recover from that here. */
4333 116849 : tree rbase1 = ref1->ref;
4334 116849 : if (rbase1)
4335 203248 : while (handled_component_p (rbase1))
4336 86399 : rbase1 = TREE_OPERAND (rbase1, 0);
4337 116849 : tree rbase2 = ref2->ref;
4338 203224 : while (handled_component_p (rbase2))
4339 86375 : rbase2 = TREE_OPERAND (rbase2, 0);
4340 :
4341 : /* MEM_REFs and TARGET_MEM_REFs record dependence cliques which are used to
4342 : implement restrict pointers. MR_DEPENDENCE_CLIQUE 0 means no information.
4343 : Otherwise we need to match bases and cliques. */
4344 116849 : if ((((TREE_CODE (rbase1) == MEM_REF || TREE_CODE (rbase1) == TARGET_MEM_REF)
4345 73107 : && MR_DEPENDENCE_CLIQUE (rbase1))
4346 100046 : || ((TREE_CODE (rbase2) == MEM_REF || TREE_CODE (rbase2) == TARGET_MEM_REF)
4347 56304 : && MR_DEPENDENCE_CLIQUE (rbase2)))
4348 133652 : && (TREE_CODE (rbase1) != TREE_CODE (rbase2)
4349 16803 : || MR_DEPENDENCE_CLIQUE (rbase1) != MR_DEPENDENCE_CLIQUE (rbase2)
4350 16724 : || (MR_DEPENDENCE_BASE (rbase1) != MR_DEPENDENCE_BASE (rbase2))))
4351 : flags |= DEPENDENCE_CLIQUE;
4352 :
4353 116849 : if (!tbaa)
4354 : return flags;
4355 :
4356 : /* Alias sets are not stable across LTO sreaming; be conservative here
4357 : and compare types the alias sets are ultimately based on. */
4358 116820 : if (lto_streaming_safe)
4359 : {
4360 2812 : tree t1 = ao_ref_alias_ptr_type (ref1);
4361 2812 : tree t2 = ao_ref_alias_ptr_type (ref2);
4362 2812 : if (!alias_ptr_types_compatible_p (t1, t2))
4363 13 : flags |= REF_ALIAS_SET;
4364 :
4365 2812 : t1 = ao_ref_base_alias_ptr_type (ref1);
4366 2812 : t2 = ao_ref_base_alias_ptr_type (ref2);
4367 2812 : if (!alias_ptr_types_compatible_p (t1, t2))
4368 22 : flags |= BASE_ALIAS_SET;
4369 : }
4370 : else
4371 : {
4372 114008 : if (ao_ref_alias_set (ref1) != ao_ref_alias_set (ref2))
4373 0 : flags |= REF_ALIAS_SET;
4374 114008 : if (ao_ref_base_alias_set (ref1) != ao_ref_base_alias_set (ref2))
4375 0 : flags |= BASE_ALIAS_SET;
4376 : }
4377 :
4378 : /* Access path is used only on non-view-converted references. */
4379 116820 : bool view_converted = view_converted_memref_p (rbase1);
4380 116820 : if (view_converted_memref_p (rbase2) != view_converted)
4381 0 : return flags | ACCESS_PATH;
4382 116820 : else if (view_converted)
4383 : return flags;
4384 :
4385 :
4386 : /* Find start of access paths and look for trailing arrays. */
4387 112526 : tree c1 = ref1->ref, c2 = ref2->ref;
4388 112526 : tree end_struct_ref1 = NULL, end_struct_ref2 = NULL;
4389 112526 : int nskipped1 = 0, nskipped2 = 0;
4390 112526 : int i = 0;
4391 :
4392 198803 : for (tree p1 = ref1->ref; handled_component_p (p1); p1 = TREE_OPERAND (p1, 0))
4393 : {
4394 86277 : if (component_ref_to_zero_sized_trailing_array_p (p1))
4395 69 : end_struct_ref1 = p1;
4396 86277 : if (ends_tbaa_access_path_p (p1))
4397 3454 : c1 = p1, nskipped1 = i;
4398 86277 : i++;
4399 : }
4400 112526 : i = 0;
4401 198779 : for (tree p2 = ref2->ref; handled_component_p (p2); p2 = TREE_OPERAND (p2, 0))
4402 : {
4403 86253 : if (component_ref_to_zero_sized_trailing_array_p (p2))
4404 76 : end_struct_ref2 = p2;
4405 86253 : if (ends_tbaa_access_path_p (p2))
4406 3454 : c2 = p2, nskipped2 = i;
4407 86253 : i++;
4408 : }
4409 :
4410 : /* For variable accesses we can not rely on offset match below.
4411 : We know that paths are struturally same, so only check that
4412 : starts of TBAA paths did not diverge. */
4413 112526 : if (!known_eq (ref1->size, ref1->max_size)
4414 112526 : && nskipped1 != nskipped2)
4415 0 : return flags | ACCESS_PATH;
4416 :
4417 : /* Information about trailing refs is used by
4418 : aliasing_component_refs_p that is applied only if paths
4419 : has handled components.. */
4420 112526 : if (!handled_component_p (c1) && !handled_component_p (c2))
4421 : ;
4422 51121 : else if ((end_struct_ref1 != NULL) != (end_struct_ref2 != NULL))
4423 27 : return flags | ACCESS_PATH;
4424 112499 : if (end_struct_ref1
4425 112558 : && same_type_for_tbaa (TREE_TYPE (end_struct_ref1),
4426 59 : TREE_TYPE (end_struct_ref2)) != 1)
4427 3 : return flags | ACCESS_PATH;
4428 :
4429 : /* Now compare all handled components of the access path.
4430 : We have three oracles that cares about access paths:
4431 : - aliasing_component_refs_p
4432 : - nonoverlapping_refs_since_match_p
4433 : - nonoverlapping_component_refs_p
4434 : We need to match things these oracles compare.
4435 :
4436 : It is only necessary to check types for compatibility
4437 : and offsets. Rest of what oracles compares are actual
4438 : addresses. Those are already known to be same:
4439 : - for constant accesses we check offsets
4440 : - for variable accesses we already matched
4441 : the path lexically with operand_equal_p. */
4442 283120 : while (true)
4443 : {
4444 197808 : bool comp1 = handled_component_p (c1);
4445 197808 : bool comp2 = handled_component_p (c2);
4446 :
4447 197808 : if (comp1 != comp2)
4448 12 : return flags | ACCESS_PATH;
4449 197796 : if (!comp1)
4450 : break;
4451 :
4452 85420 : if (TREE_CODE (c1) != TREE_CODE (c2))
4453 0 : return flags | ACCESS_PATH;
4454 :
4455 : /* aliasing_component_refs_p attempts to find type match within
4456 : the paths. For that reason both types needs to be equal
4457 : with respect to same_type_for_tbaa_p. */
4458 85420 : if (!types_equal_for_same_type_for_tbaa_p (TREE_TYPE (c1),
4459 85420 : TREE_TYPE (c2),
4460 : lto_streaming_safe))
4461 108 : return flags | ACCESS_PATH;
4462 170624 : if (component_ref_to_zero_sized_trailing_array_p (c1)
4463 85312 : != component_ref_to_zero_sized_trailing_array_p (c2))
4464 0 : return flags | ACCESS_PATH;
4465 :
4466 : /* aliasing_matching_component_refs_p compares
4467 : offsets within the path. Other properties are ignored.
4468 : Do not bother to verify offsets in variable accesses. Here we
4469 : already compared them by operand_equal_p so they are
4470 : structurally same. */
4471 85312 : if (!known_eq (ref1->size, ref1->max_size))
4472 : {
4473 2592 : poly_int64 offadj1, sztmc1, msztmc1;
4474 2592 : bool reverse1;
4475 2592 : get_ref_base_and_extent (c1, &offadj1, &sztmc1, &msztmc1, &reverse1);
4476 2592 : poly_int64 offadj2, sztmc2, msztmc2;
4477 2592 : bool reverse2;
4478 2592 : get_ref_base_and_extent (c2, &offadj2, &sztmc2, &msztmc2, &reverse2);
4479 2592 : if (!known_eq (offadj1, offadj2))
4480 0 : return flags | ACCESS_PATH;
4481 : }
4482 85312 : c1 = TREE_OPERAND (c1, 0);
4483 85312 : c2 = TREE_OPERAND (c2, 0);
4484 85312 : }
4485 : /* Finally test the access type. */
4486 112376 : if (!types_equal_for_same_type_for_tbaa_p (TREE_TYPE (c1),
4487 112376 : TREE_TYPE (c2),
4488 : lto_streaming_safe))
4489 1564 : return flags | ACCESS_PATH;
4490 : return flags;
4491 : }
4492 :
4493 : /* Hash REF to HSTATE. If LTO_STREAMING_SAFE do not use alias sets
4494 : and canonical types. */
4495 : void
4496 8368862 : ao_compare::hash_ao_ref (ao_ref *ref, bool lto_streaming_safe, bool tbaa,
4497 : inchash::hash &hstate)
4498 : {
4499 8368862 : tree base = ao_ref_base (ref);
4500 8368862 : tree tbase = base;
4501 :
4502 8368862 : if (!known_eq (ref->size, ref->max_size))
4503 : {
4504 424015 : tree r = ref->ref;
4505 424015 : if (TREE_CODE (r) == COMPONENT_REF
4506 424015 : && DECL_BIT_FIELD (TREE_OPERAND (r, 1)))
4507 : {
4508 1713 : tree field = TREE_OPERAND (r, 1);
4509 1713 : hash_operand (DECL_FIELD_OFFSET (field), hstate, 0);
4510 1713 : hash_operand (DECL_FIELD_BIT_OFFSET (field), hstate, 0);
4511 1713 : hash_operand (DECL_SIZE (field), hstate, 0);
4512 1713 : r = TREE_OPERAND (r, 0);
4513 : }
4514 424015 : if (TREE_CODE (r) == BIT_FIELD_REF)
4515 : {
4516 1704 : hash_operand (TREE_OPERAND (r, 1), hstate, 0);
4517 1704 : hash_operand (TREE_OPERAND (r, 2), hstate, 0);
4518 1704 : r = TREE_OPERAND (r, 0);
4519 : }
4520 424015 : hash_operand (TYPE_SIZE (TREE_TYPE (ref->ref)), hstate, 0);
4521 424015 : hash_operand (r, hstate, OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS);
4522 : }
4523 : else
4524 : {
4525 7944847 : hash_operand (tbase, hstate, OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS);
4526 7944847 : hstate.add_poly_int (ref->offset);
4527 7944847 : hstate.add_poly_int (ref->size);
4528 7944847 : hstate.add_poly_int (ref->max_size);
4529 : }
4530 8368862 : if (!lto_streaming_safe && tbaa)
4531 : {
4532 8047403 : hstate.add_int (ao_ref_alias_set (ref));
4533 8047403 : hstate.add_int (ao_ref_base_alias_set (ref));
4534 : }
4535 8368862 : }
|
