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 ssa_name_pt_solution. 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 60242222 : ptr_deref_may_alias_global_p (tree ptr, bool escaped_local_p)
222 : {
223 60242222 : const pt_solution *pt;
224 :
225 : /* If we end up with a pointer constant here that may point
226 : to global memory. */
227 60242222 : if (TREE_CODE (ptr) != SSA_NAME || !POINTER_TYPE_P (TREE_TYPE (ptr)))
228 : return true;
229 :
230 53090885 : pt = ssa_name_pt_solution (ptr);
231 :
232 : /* If we do not have points-to information for this variable,
233 : we have to punt. */
234 47648606 : if (!pt)
235 : return true;
236 :
237 : /* ??? This does not use TBAA to prune globals ptr may not access. */
238 47008597 : return pt_solution_includes_global (pt, escaped_local_p);
239 : }
240 :
241 : /* Return true, if dereferencing PTR may alias with a local automatic
242 : variable. */
243 :
244 : bool
245 0 : ptr_deref_may_alias_auto_p (tree ptr)
246 : {
247 0 : const pt_solution *pt;
248 :
249 : /* If we end up with a pointer constant here that may point
250 : to local stack memory. */
251 0 : if (TREE_CODE (ptr) != SSA_NAME || !POINTER_TYPE_P (TREE_TYPE (ptr)))
252 : return true;
253 :
254 0 : pt = ssa_name_pt_solution (ptr);
255 :
256 : /* If we do not have points-to information for this variable,
257 : we have to punt. */
258 0 : if (!pt)
259 : return true;
260 :
261 0 : return pt_solution_includes_auto (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 218089363 : ptr_deref_may_alias_decl_p (tree ptr, tree decl)
271 : {
272 218089363 : const pt_solution *pt;
273 :
274 : /* Conversions are irrelevant for points-to information and
275 : data-dependence analysis can feed us those. */
276 218089363 : STRIP_NOPS (ptr);
277 :
278 : /* Anything we do not explicitly handle aliases. */
279 218089363 : if ((TREE_CODE (ptr) != SSA_NAME
280 2334983 : && TREE_CODE (ptr) != ADDR_EXPR
281 1159440 : && TREE_CODE (ptr) != POINTER_PLUS_EXPR)
282 216929923 : || !POINTER_TYPE_P (TREE_TYPE (ptr))
283 435018902 : || (!VAR_P (decl)
284 : && TREE_CODE (decl) != PARM_DECL
285 : && TREE_CODE (decl) != RESULT_DECL))
286 : return true;
287 :
288 : /* Disregard pointer offsetting. */
289 216928352 : 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 216928352 : if (TREE_CODE (ptr) == ADDR_EXPR)
302 : {
303 1174410 : tree base = get_base_address (TREE_OPERAND (ptr, 0));
304 1174410 : if (base
305 1174410 : && (TREE_CODE (base) == MEM_REF
306 1174410 : || TREE_CODE (base) == TARGET_MEM_REF))
307 19743 : ptr = TREE_OPERAND (base, 0);
308 1154667 : else if (base
309 1154667 : && DECL_P (base))
310 1154336 : return compare_base_decls (base, decl) != 0;
311 331 : else if (base
312 331 : && CONSTANT_CLASS_P (base))
313 : return false;
314 : else
315 0 : return true;
316 : }
317 :
318 : /* Non-aliased variables cannot be pointed to. */
319 215773685 : if (!may_be_aliased (decl))
320 : return false;
321 :
322 : /* From here we require a SSA name pointer. Anything else aliases. */
323 81702386 : if (TREE_CODE (ptr) != SSA_NAME
324 81702386 : || !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 81702386 : pt = ssa_name_pt_solution (ptr);
330 80776977 : if (!pt)
331 : return true;
332 :
333 80507498 : return pt_solution_includes (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 71579638 : ptr_derefs_may_alias_p (tree ptr1, tree ptr2)
342 : {
343 72777136 : const pt_solution *pt1, *pt2;
344 :
345 : /* Conversions are irrelevant for points-to information and
346 : data-dependence analysis can feed us those. */
347 72777136 : STRIP_NOPS (ptr1);
348 72777136 : STRIP_NOPS (ptr2);
349 :
350 : /* Disregard pointer offsetting. */
351 72777136 : if (TREE_CODE (ptr1) == POINTER_PLUS_EXPR)
352 : {
353 481539 : do
354 : {
355 481539 : ptr1 = TREE_OPERAND (ptr1, 0);
356 : }
357 481539 : while (TREE_CODE (ptr1) == POINTER_PLUS_EXPR);
358 : return ptr_derefs_may_alias_p (ptr1, ptr2);
359 : }
360 72295597 : if (TREE_CODE (ptr2) == POINTER_PLUS_EXPR)
361 : {
362 486556 : do
363 : {
364 486556 : ptr2 = TREE_OPERAND (ptr2, 0);
365 : }
366 486556 : 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 71809041 : if (TREE_CODE (ptr1) == ADDR_EXPR)
373 : {
374 829062 : tree base = get_base_address (TREE_OPERAND (ptr1, 0));
375 829062 : if (base
376 829062 : && (TREE_CODE (base) == MEM_REF
377 829062 : || TREE_CODE (base) == TARGET_MEM_REF))
378 115995 : return ptr_derefs_may_alias_p (TREE_OPERAND (base, 0), ptr2);
379 713067 : else if (base
380 713067 : && DECL_P (base))
381 711878 : return ptr_deref_may_alias_decl_p (ptr2, base);
382 : /* Try ptr2 when ptr1 points to a constant. */
383 : else if (base
384 1189 : && !CONSTANT_CLASS_P (base))
385 : return true;
386 : }
387 70981168 : if (TREE_CODE (ptr2) == ADDR_EXPR)
388 : {
389 360910 : tree base = get_base_address (TREE_OPERAND (ptr2, 0));
390 360910 : if (base
391 360910 : && (TREE_CODE (base) == MEM_REF
392 360910 : || TREE_CODE (base) == TARGET_MEM_REF))
393 113408 : return ptr_derefs_may_alias_p (ptr1, TREE_OPERAND (base, 0));
394 247502 : else if (base
395 247502 : && DECL_P (base))
396 247241 : 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 70620258 : if (TREE_CODE (ptr1) != SSA_NAME
403 70459248 : || TREE_CODE (ptr2) != SSA_NAME
404 70434500 : || !POINTER_TYPE_P (TREE_TYPE (ptr1))
405 141044957 : || !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 70424542 : 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 66510685 : pt1 = ssa_name_pt_solution (ptr1);
417 66510685 : pt2 = ssa_name_pt_solution (ptr2);
418 66510685 : if (!pt1 || !pt2)
419 : return true;
420 :
421 : /* ??? This does not use TBAA to prune decls from the intersection
422 : that not both pointers may access. */
423 62627966 : return pt_solutions_intersect (pt1, pt2);
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 1710879 : ptr_deref_may_alias_ref_p_1 (tree ptr, ao_ref *ref)
432 : {
433 1710879 : tree base = ao_ref_base (ref);
434 :
435 1710879 : if (TREE_CODE (base) == MEM_REF
436 1710879 : || TREE_CODE (base) == TARGET_MEM_REF)
437 130636 : return ptr_derefs_may_alias_p (ptr, TREE_OPERAND (base, 0));
438 1580243 : else if (DECL_P (base))
439 1577559 : 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 58296521 : 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 58296521 : tree obj1 = NULL_TREE;
455 58296521 : tree obj2 = NULL_TREE;
456 58296521 : if (TREE_CODE (ptr1) == ADDR_EXPR)
457 : {
458 56407 : tree tem = get_base_address (TREE_OPERAND (ptr1, 0));
459 56407 : if (! tem)
460 : return false;
461 56407 : 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 9468 : ptr1 = TREE_OPERAND (tem, 0);
467 : }
468 58296521 : if (TREE_CODE (ptr2) == ADDR_EXPR)
469 : {
470 9727611 : tree tem = get_base_address (TREE_OPERAND (ptr2, 0));
471 9727611 : if (! tem)
472 : return false;
473 9727611 : 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 160032 : ptr2 = TREE_OPERAND (tem, 0);
479 : }
480 :
481 : /* Canonicalize ptr vs. object. */
482 58296521 : if (TREE_CODE (ptr1) == SSA_NAME && obj2)
483 : {
484 : std::swap (ptr1, ptr2);
485 : std::swap (obj1, obj2);
486 : }
487 :
488 58296521 : if (obj1 && obj2)
489 : /* Other code handles this correctly, no need to duplicate it here. */;
490 6190161 : else if (obj1 && TREE_CODE (ptr2) == SSA_NAME)
491 : {
492 6178946 : const pt_solution *pt = ssa_name_pt_solution (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 5401021 : if (!pt
497 4939693 : || pt->vars_contains_restrict
498 4932213 : || pt->vars_contains_interposable)
499 : return false;
500 4265495 : if (VAR_P (obj1)
501 4265495 : && (TREE_STATIC (obj1) || DECL_EXTERNAL (obj1)))
502 : {
503 1194909 : varpool_node *node = varpool_node::get (obj1);
504 : /* If obj1 may bind to NULL give up (see below). */
505 1194909 : if (! node
506 1194909 : || ! node->nonzero_address ()
507 2389782 : || ! decl_binds_to_current_def_p (obj1))
508 : return false;
509 : }
510 3360002 : return !pt_solution_includes (pt, obj1);
511 : }
512 52104626 : else if (TREE_CODE (ptr1) == SSA_NAME)
513 : {
514 45658005 : const pt_solution *pt1 = ssa_name_pt_solution (ptr1);
515 39793496 : if (!pt1
516 34751857 : || pt1->vars_contains_restrict
517 33756987 : || pt1->vars_contains_interposable)
518 : return false;
519 31973942 : if (integer_zerop (ptr2) && ptr_nonnull_p (ptr1))
520 : return true;
521 31931723 : if (TREE_CODE (ptr2) == SSA_NAME)
522 : {
523 10502096 : const pt_solution *pt2 = ssa_name_pt_solution (ptr2);
524 9956671 : if (!pt2
525 9838750 : || pt2->vars_contains_restrict
526 9832725 : || pt2->vars_contains_interposable)
527 : return false;
528 17942854 : if ((ptr_nonnull_p (ptr1) || ptr_nonnull_p (ptr2))
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 4219395 : && (!pt1->vars_contains_nonlocal
534 59158 : || !pt2->vars_contains_nonlocal)
535 13936084 : && (!pt_solution_includes_const_pool (pt1)
536 3881348 : || !pt_solution_includes_const_pool (pt2)))
537 334304 : return !pt_solutions_intersect (pt1, pt2);
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 56697226 : ref_may_alias_global_p_1 (tree base, bool escaped_local_p)
550 : {
551 56697226 : if (DECL_P (base))
552 44145894 : return (is_global_var (base)
553 44145894 : || (escaped_local_p
554 1513872 : && pt_solution_includes (&cfun->gimple_df->escaped_return,
555 : base)));
556 12551332 : else if (TREE_CODE (base) == MEM_REF
557 12551332 : || TREE_CODE (base) == TARGET_MEM_REF)
558 12539830 : return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0),
559 12539830 : escaped_local_p);
560 : return true;
561 : }
562 :
563 : bool
564 11415109 : ref_may_alias_global_p (ao_ref *ref, bool escaped_local_p)
565 : {
566 11415109 : tree base = ao_ref_base (ref);
567 11415109 : return ref_may_alias_global_p_1 (base, escaped_local_p);
568 : }
569 :
570 : bool
571 45282117 : ref_may_alias_global_p (tree ref, bool escaped_local_p)
572 : {
573 45282117 : tree base = get_base_address (ref);
574 45282117 : 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 184237552 : stmt_may_clobber_global_p (gimple *stmt, bool escaped_local_p)
583 : {
584 184237552 : tree lhs;
585 :
586 336396667 : 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 45519571 : switch (gimple_code (stmt))
599 : {
600 45282117 : case GIMPLE_ASSIGN:
601 45282117 : lhs = gimple_assign_lhs (stmt);
602 45282117 : return (TREE_CODE (lhs) != SSA_NAME
603 45282117 : && 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 3336 : FOR_EACH_SSA_NAME (i, ptr, cfun)
644 : {
645 2550 : const pt_solution *pt;
646 :
647 4656 : if (!POINTER_TYPE_P (TREE_TYPE (ptr))
648 2597 : || SSA_NAME_IN_FREE_LIST (ptr))
649 2059 : continue;
650 :
651 3261 : pt = ssa_name_pt_solution (ptr);
652 485 : if (pt)
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, const 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->const_pool)
687 0 : fprintf (file, ", points-to const-pool");
688 :
689 1051 : if (pt->vars)
690 : {
691 1048 : fprintf (file, ", points-to vars: ");
692 1048 : dump_decl_set (file, pt->vars);
693 1048 : if (pt->vars_contains_nonlocal
694 914 : || pt->vars_contains_escaped
695 837 : || pt->vars_contains_escaped_heap
696 837 : || pt->vars_contains_restrict
697 837 : || pt->vars_contains_interposable)
698 : {
699 211 : const char *comma = "";
700 211 : fprintf (file, " (");
701 211 : if (pt->vars_contains_nonlocal)
702 : {
703 134 : fprintf (file, "nonlocal");
704 134 : comma = ", ";
705 : }
706 211 : if (pt->vars_contains_escaped)
707 : {
708 139 : fprintf (file, "%sescaped", comma);
709 139 : comma = ", ";
710 : }
711 211 : if (pt->vars_contains_escaped_heap)
712 : {
713 0 : fprintf (file, "%sescaped heap", comma);
714 0 : comma = ", ";
715 : }
716 211 : if (pt->vars_contains_restrict)
717 : {
718 58 : fprintf (file, "%srestrict", comma);
719 58 : comma = ", ";
720 : }
721 211 : if (pt->vars_contains_interposable)
722 0 : fprintf (file, "%sinterposable", comma);
723 211 : fprintf (file, ")");
724 : }
725 : }
726 1051 : }
727 :
728 :
729 : /* Unified dump function for pt_solution. */
730 :
731 : DEBUG_FUNCTION void
732 0 : debug (pt_solution &ref)
733 : {
734 0 : dump_points_to_solution (stderr, &ref);
735 0 : }
736 :
737 : DEBUG_FUNCTION void
738 0 : debug (pt_solution *ptr)
739 : {
740 0 : if (ptr)
741 0 : debug (*ptr);
742 : else
743 0 : fprintf (stderr, "<nil>\n");
744 0 : }
745 :
746 :
747 : /* Dump points-to information for SSA_NAME PTR into FILE. */
748 :
749 : void
750 485 : dump_points_to_info_for (FILE *file, tree ptr)
751 : {
752 485 : const pt_solution *pt = ssa_name_pt_solution (ptr);
753 :
754 485 : print_generic_expr (file, ptr, dump_flags);
755 :
756 485 : if (pt)
757 485 : dump_points_to_solution (file, pt);
758 : else
759 0 : fprintf (file, ", points-to anything");
760 :
761 485 : fprintf (file, "\n");
762 485 : }
763 :
764 :
765 : /* Dump points-to information for VAR into stderr. */
766 :
767 : DEBUG_FUNCTION void
768 0 : debug_points_to_info_for (tree var)
769 : {
770 0 : dump_points_to_info_for (stderr, var);
771 0 : }
772 :
773 :
774 : /* Initializes the alias-oracle reference representation *R from REF. */
775 :
776 : void
777 2880908870 : ao_ref_init (ao_ref *r, tree ref)
778 : {
779 2880908870 : r->ref = ref;
780 2880908870 : r->base = NULL_TREE;
781 2880908870 : r->offset = 0;
782 2880908870 : r->size = -1;
783 2880908870 : r->max_size = -1;
784 2880908870 : r->ref_alias_set = -1;
785 2880908870 : r->base_alias_set = -1;
786 2880908870 : r->volatile_p = ref ? TREE_THIS_VOLATILE (ref) : false;
787 2880908870 : }
788 :
789 : /* Returns the base object of the memory reference *REF. */
790 :
791 : tree
792 5625592169 : ao_ref_base (ao_ref *ref)
793 : {
794 5625592169 : bool reverse;
795 :
796 5625592169 : if (ref->base)
797 : return ref->base;
798 2611667210 : ref->base = get_ref_base_and_extent (ref->ref, &ref->offset, &ref->size,
799 : &ref->max_size, &reverse);
800 2611667210 : return ref->base;
801 : }
802 :
803 : /* Returns the base object alias set of the memory reference *REF. */
804 :
805 : alias_set_type
806 1043358272 : ao_ref_base_alias_set (ao_ref *ref)
807 : {
808 1043358272 : tree base_ref;
809 1043358272 : if (ref->base_alias_set != -1)
810 : return ref->base_alias_set;
811 804620269 : if (!ref->ref)
812 : return 0;
813 766582705 : base_ref = ref->ref;
814 766582705 : if (TREE_CODE (base_ref) == WITH_SIZE_EXPR)
815 4 : base_ref = TREE_OPERAND (base_ref, 0);
816 1234969707 : while (handled_component_p (base_ref))
817 468387002 : base_ref = TREE_OPERAND (base_ref, 0);
818 766582705 : ref->base_alias_set = get_alias_set (base_ref);
819 766582705 : return ref->base_alias_set;
820 : }
821 :
822 : /* Returns the reference alias set of the memory reference *REF. */
823 :
824 : alias_set_type
825 1331927253 : ao_ref_alias_set (ao_ref *ref)
826 : {
827 1331927253 : if (ref->ref_alias_set != -1)
828 : return ref->ref_alias_set;
829 534925923 : if (!ref->ref)
830 : return 0;
831 534925921 : ref->ref_alias_set = get_alias_set (ref->ref);
832 534925921 : return ref->ref_alias_set;
833 : }
834 :
835 : /* Returns a type satisfying
836 : get_deref_alias_set (type) == ao_ref_base_alias_set (REF). */
837 :
838 : tree
839 350484 : ao_ref_base_alias_ptr_type (ao_ref *ref)
840 : {
841 350484 : tree base_ref;
842 :
843 350484 : if (!ref->ref)
844 : return NULL_TREE;
845 350484 : base_ref = ref->ref;
846 350484 : if (TREE_CODE (base_ref) == WITH_SIZE_EXPR)
847 0 : base_ref = TREE_OPERAND (base_ref, 0);
848 479939 : while (handled_component_p (base_ref))
849 129455 : base_ref = TREE_OPERAND (base_ref, 0);
850 350484 : tree ret = reference_alias_ptr_type (base_ref);
851 350484 : return ret;
852 : }
853 :
854 : /* Returns a type satisfying
855 : get_deref_alias_set (type) == ao_ref_alias_set (REF). */
856 :
857 : tree
858 350484 : ao_ref_alias_ptr_type (ao_ref *ref)
859 : {
860 350484 : if (!ref->ref)
861 : return NULL_TREE;
862 350484 : tree ret = reference_alias_ptr_type (ref->ref);
863 350484 : return ret;
864 : }
865 :
866 : /* Return the alignment of the access *REF and store it in the *ALIGN
867 : and *BITPOS pairs. Returns false if no alignment could be determined.
868 : See get_object_alignment_2 for details. */
869 :
870 : bool
871 98601 : ao_ref_alignment (ao_ref *ref, unsigned int *align,
872 : unsigned HOST_WIDE_INT *bitpos)
873 : {
874 98601 : if (ref->ref)
875 96961 : return get_object_alignment_1 (ref->ref, align, bitpos);
876 :
877 : /* When we just have ref->base we cannot use get_object_alignment since
878 : that will eventually use the type of the apparent access while for
879 : example ao_ref_init_from_ptr_and_range is not careful to adjust that. */
880 1640 : *align = BITS_PER_UNIT;
881 1640 : HOST_WIDE_INT offset;
882 1640 : if (!ref->offset.is_constant (&offset)
883 1640 : || !get_object_alignment_2 (ref->base, align, bitpos, true))
884 : return false;
885 1401 : *bitpos += (unsigned HOST_WIDE_INT)offset * BITS_PER_UNIT;
886 1401 : *bitpos = *bitpos & (*align - 1);
887 1401 : return true;
888 : }
889 :
890 : /* Init an alias-oracle reference representation from a gimple pointer
891 : PTR a range specified by OFFSET, SIZE and MAX_SIZE under the assumption
892 : that RANGE_KNOWN is set.
893 :
894 : The access is assumed to be only to or after of the pointer target adjusted
895 : by the offset, not before it (even in the case RANGE_KNOWN is false). */
896 :
897 : void
898 40745744 : ao_ref_init_from_ptr_and_range (ao_ref *ref, tree ptr,
899 : bool range_known,
900 : poly_int64 offset,
901 : poly_int64 size,
902 : poly_int64 max_size)
903 : {
904 40745744 : poly_int64 t, extra_offset = 0;
905 :
906 40745744 : ref->ref = NULL_TREE;
907 40745744 : if (TREE_CODE (ptr) == SSA_NAME)
908 : {
909 27280119 : gimple *stmt = SSA_NAME_DEF_STMT (ptr);
910 27280119 : if (gimple_assign_single_p (stmt)
911 27280119 : && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
912 4121398 : ptr = gimple_assign_rhs1 (stmt);
913 23158721 : else if (is_gimple_assign (stmt)
914 15356075 : && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
915 29196363 : && ptrdiff_tree_p (gimple_assign_rhs2 (stmt), &extra_offset))
916 : {
917 405851 : ptr = gimple_assign_rhs1 (stmt);
918 405851 : extra_offset *= BITS_PER_UNIT;
919 : }
920 : }
921 :
922 40745744 : if (TREE_CODE (ptr) == ADDR_EXPR)
923 : {
924 17517227 : ref->base = get_addr_base_and_unit_offset (TREE_OPERAND (ptr, 0), &t);
925 17517227 : if (ref->base
926 32182832 : && coeffs_in_range_p (t, -HOST_WIDE_INT_MAX / BITS_PER_UNIT,
927 : HOST_WIDE_INT_MAX / BITS_PER_UNIT))
928 14665427 : ref->offset = BITS_PER_UNIT * t;
929 : else
930 : {
931 2851800 : range_known = false;
932 2851800 : ref->offset = 0;
933 2851800 : ref->base = get_base_address (TREE_OPERAND (ptr, 0));
934 : }
935 : }
936 : else
937 : {
938 23228517 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
939 23228517 : ref->base = build2 (MEM_REF, char_type_node,
940 : ptr, null_pointer_node);
941 23228517 : ref->offset = 0;
942 : }
943 40745744 : ref->offset += extra_offset + offset;
944 40745744 : if (range_known)
945 : {
946 21275876 : ref->max_size = max_size;
947 21275876 : ref->size = size;
948 : }
949 : else
950 19469868 : ref->max_size = ref->size = -1;
951 40745744 : ref->ref_alias_set = 0;
952 40745744 : ref->base_alias_set = 0;
953 40745744 : ref->volatile_p = false;
954 40745744 : }
955 :
956 : /* Init an alias-oracle reference representation from a gimple pointer
957 : PTR and a gimple size SIZE in bytes. If SIZE is NULL_TREE then the
958 : size is assumed to be unknown. The access is assumed to be only
959 : to or after of the pointer target, not before it. */
960 :
961 : void
962 10791145 : ao_ref_init_from_ptr_and_size (ao_ref *ref, tree ptr, tree size)
963 : {
964 10791145 : poly_int64 size_hwi;
965 10791145 : if (size
966 5334999 : && poly_int_tree_p (size, &size_hwi)
967 15419956 : && coeffs_in_range_p (size_hwi, 0, HOST_WIDE_INT_MAX / BITS_PER_UNIT))
968 : {
969 4628119 : size_hwi = size_hwi * BITS_PER_UNIT;
970 4628119 : ao_ref_init_from_ptr_and_range (ref, ptr, true, 0, size_hwi, size_hwi);
971 : }
972 : else
973 6163026 : ao_ref_init_from_ptr_and_range (ref, ptr, false, 0, -1, -1);
974 10791145 : }
975 :
976 : /* S1 and S2 are TYPE_SIZE or DECL_SIZE. Compare them:
977 : Return -1 if S1 < S2
978 : Return 1 if S1 > S2
979 : Return 0 if equal or incomparable. */
980 :
981 : static int
982 9015311 : compare_sizes (tree s1, tree s2)
983 : {
984 9015311 : if (!s1 || !s2)
985 : return 0;
986 :
987 9005893 : poly_uint64 size1;
988 9005893 : poly_uint64 size2;
989 :
990 9005893 : if (!poly_int_tree_p (s1, &size1) || !poly_int_tree_p (s2, &size2))
991 : return 0;
992 9005339 : if (known_lt (size1, size2))
993 : return -1;
994 6474327 : if (known_lt (size2, size1))
995 2880017 : return 1;
996 : return 0;
997 : }
998 :
999 : /* Compare TYPE1 and TYPE2 by its size.
1000 : Return -1 if size of TYPE1 < size of TYPE2
1001 : Return 1 if size of TYPE1 > size of TYPE2
1002 : Return 0 if types are of equal sizes or we can not compare them. */
1003 :
1004 : static int
1005 7634876 : compare_type_sizes (tree type1, tree type2)
1006 : {
1007 : /* Be conservative for arrays and vectors. We want to support partial
1008 : overlap on int[3] and int[3] as tested in gcc.dg/torture/alias-2.c. */
1009 7634876 : while (TREE_CODE (type1) == ARRAY_TYPE
1010 8412336 : || VECTOR_TYPE_P (type1))
1011 777460 : type1 = TREE_TYPE (type1);
1012 7823435 : while (TREE_CODE (type2) == ARRAY_TYPE
1013 7823435 : || VECTOR_TYPE_P (type2))
1014 188559 : type2 = TREE_TYPE (type2);
1015 7634876 : return compare_sizes (TYPE_SIZE (type1), TYPE_SIZE (type2));
1016 : }
1017 :
1018 : /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
1019 : purpose of TBAA. Return 0 if they are distinct and -1 if we cannot
1020 : decide. */
1021 :
1022 : static inline int
1023 878831607 : same_type_for_tbaa (tree type1, tree type2)
1024 : {
1025 878831607 : type1 = TYPE_MAIN_VARIANT (type1);
1026 878831607 : type2 = TYPE_MAIN_VARIANT (type2);
1027 :
1028 : /* Handle the most common case first. */
1029 878831607 : if (type1 == type2)
1030 : return 1;
1031 :
1032 : /* If we would have to do structural comparison bail out. */
1033 141560184 : if (TYPE_STRUCTURAL_EQUALITY_P (type1)
1034 141560184 : || TYPE_STRUCTURAL_EQUALITY_P (type2))
1035 : return -1;
1036 :
1037 : /* Compare the canonical types. */
1038 89393051 : if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
1039 : return 1;
1040 :
1041 : /* ??? Array types are not properly unified in all cases as we have
1042 : spurious changes in the index types for example. Removing this
1043 : causes all sorts of problems with the Fortran frontend. */
1044 88498912 : if (TREE_CODE (type1) == ARRAY_TYPE
1045 5040259 : && TREE_CODE (type2) == ARRAY_TYPE)
1046 : return -1;
1047 :
1048 : /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
1049 : object of one of its constrained subtypes, e.g. when a function with an
1050 : unconstrained parameter passed by reference is called on an object and
1051 : inlined. But, even in the case of a fixed size, type and subtypes are
1052 : not equivalent enough as to share the same TYPE_CANONICAL, since this
1053 : would mean that conversions between them are useless, whereas they are
1054 : not (e.g. type and subtypes can have different modes). So, in the end,
1055 : they are only guaranteed to have the same alias set. */
1056 88192623 : alias_set_type set1 = get_alias_set (type1);
1057 88192623 : alias_set_type set2 = get_alias_set (type2);
1058 88192623 : if (set1 == set2)
1059 : return -1;
1060 :
1061 : /* Pointers to void are considered compatible with all other pointers,
1062 : so for two pointers see what the alias set resolution thinks. */
1063 50052646 : if (POINTER_TYPE_P (type1)
1064 11454001 : && POINTER_TYPE_P (type2)
1065 50230877 : && alias_sets_conflict_p (set1, set2))
1066 178231 : return -1;
1067 :
1068 : /* The types are known to be not equal. */
1069 : return 0;
1070 : }
1071 :
1072 : /* Return true if TYPE is a composite type (i.e. we may apply one of handled
1073 : components on it). */
1074 :
1075 : static bool
1076 1948533 : type_has_components_p (tree type)
1077 : {
1078 1948533 : return AGGREGATE_TYPE_P (type) || VECTOR_TYPE_P (type)
1079 1948533 : || TREE_CODE (type) == COMPLEX_TYPE;
1080 : }
1081 :
1082 : /* MATCH1 and MATCH2 which are part of access path of REF1 and REF2
1083 : respectively are either pointing to same address or are completely
1084 : disjoint. If PARTIAL_OVERLAP is true, assume that outermost arrays may
1085 : just partly overlap.
1086 :
1087 : Try to disambiguate using the access path starting from the match
1088 : and return false if there is no conflict.
1089 :
1090 : Helper for aliasing_component_refs_p. */
1091 :
1092 : static bool
1093 961488 : aliasing_matching_component_refs_p (tree match1, tree ref1,
1094 : poly_int64 offset1, poly_int64 max_size1,
1095 : tree match2, tree ref2,
1096 : poly_int64 offset2, poly_int64 max_size2,
1097 : bool partial_overlap)
1098 : {
1099 961488 : poly_int64 offadj, sztmp, msztmp;
1100 961488 : bool reverse;
1101 :
1102 961488 : if (!partial_overlap)
1103 : {
1104 961484 : get_ref_base_and_extent (match2, &offadj, &sztmp, &msztmp, &reverse);
1105 961484 : offset2 -= offadj;
1106 961484 : get_ref_base_and_extent (match1, &offadj, &sztmp, &msztmp, &reverse);
1107 961484 : offset1 -= offadj;
1108 961484 : if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
1109 : {
1110 61702 : ++alias_stats.aliasing_component_refs_p_no_alias;
1111 61702 : return false;
1112 : }
1113 : }
1114 :
1115 899786 : int cmp = nonoverlapping_refs_since_match_p (match1, ref1, match2, ref2,
1116 : partial_overlap);
1117 899786 : if (cmp == 1
1118 899786 : || (cmp == -1 && nonoverlapping_component_refs_p (ref1, ref2)))
1119 : {
1120 450 : ++alias_stats.aliasing_component_refs_p_no_alias;
1121 450 : return false;
1122 : }
1123 899336 : ++alias_stats.aliasing_component_refs_p_may_alias;
1124 899336 : return true;
1125 : }
1126 :
1127 : /* Return true if REF is reference to zero sized trailing array. I.e.
1128 : struct foo {int bar; int array[0];} *fooptr;
1129 : fooptr->array. */
1130 :
1131 : static bool
1132 6236513 : component_ref_to_zero_sized_trailing_array_p (tree ref)
1133 : {
1134 6236513 : return (TREE_CODE (ref) == COMPONENT_REF
1135 5592975 : && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 1))) == ARRAY_TYPE
1136 131772 : && (!TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)))
1137 46896 : || integer_zerop (TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)))))
1138 6321462 : && array_ref_flexible_size_p (ref));
1139 : }
1140 :
1141 : /* Worker for aliasing_component_refs_p. Most parameters match parameters of
1142 : aliasing_component_refs_p.
1143 :
1144 : Walk access path REF2 and try to find type matching TYPE1
1145 : (which is a start of possibly aliasing access path REF1).
1146 : If match is found, try to disambiguate.
1147 :
1148 : Return 0 for successful disambiguation.
1149 : Return 1 if match was found but disambiguation failed
1150 : Return -1 if there is no match.
1151 : In this case MAYBE_MATCH is set to 0 if there is no type matching TYPE1
1152 : in access patch REF2 and -1 if we are not sure. */
1153 :
1154 : static int
1155 2645961 : aliasing_component_refs_walk (tree ref1, tree type1, tree base1,
1156 : poly_int64 offset1, poly_int64 max_size1,
1157 : tree end_struct_ref1,
1158 : tree ref2, tree base2,
1159 : poly_int64 offset2, poly_int64 max_size2,
1160 : bool *maybe_match)
1161 : {
1162 2645961 : tree ref = ref2;
1163 2645961 : int same_p = 0;
1164 :
1165 7402347 : while (true)
1166 : {
1167 : /* We walk from inner type to the outer types. If type we see is
1168 : already too large to be part of type1, terminate the search. */
1169 5024154 : int cmp = compare_type_sizes (type1, TREE_TYPE (ref));
1170 :
1171 5024154 : if (cmp < 0
1172 5024154 : && (!end_struct_ref1
1173 60 : || compare_type_sizes (TREE_TYPE (end_struct_ref1),
1174 60 : TREE_TYPE (ref)) < 0))
1175 : break;
1176 : /* If types may be of same size, see if we can decide about their
1177 : equality. */
1178 3665988 : if (cmp == 0)
1179 : {
1180 2676787 : same_p = same_type_for_tbaa (TREE_TYPE (ref), type1);
1181 2676787 : if (same_p == 1)
1182 : break;
1183 : /* In case we can't decide whether types are same try to
1184 : continue looking for the exact match.
1185 : Remember however that we possibly saw a match
1186 : to bypass the access path continuations tests we do later. */
1187 1715299 : if (same_p == -1)
1188 632817 : *maybe_match = true;
1189 : }
1190 2704500 : if (!handled_component_p (ref))
1191 : break;
1192 2378193 : ref = TREE_OPERAND (ref, 0);
1193 2378193 : }
1194 2645961 : if (same_p == 1)
1195 : {
1196 961488 : bool partial_overlap = false;
1197 :
1198 : /* We assume that arrays can overlap by multiple of their elements
1199 : size as tested in gcc.dg/torture/alias-2.c.
1200 : This partial overlap happen only when both arrays are bases of
1201 : the access and not contained within another component ref.
1202 : To be safe we also assume partial overlap for VLAs. */
1203 961488 : if (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE
1204 961488 : && (!TYPE_SIZE (TREE_TYPE (base1))
1205 1788 : || TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) != INTEGER_CST
1206 1788 : || ref == base2))
1207 : {
1208 : /* Setting maybe_match to true triggers
1209 : nonoverlapping_component_refs_p test later that still may do
1210 : useful disambiguation. */
1211 4 : *maybe_match = true;
1212 4 : partial_overlap = true;
1213 : }
1214 961488 : return aliasing_matching_component_refs_p (base1, ref1,
1215 : offset1, max_size1,
1216 : ref, ref2,
1217 : offset2, max_size2,
1218 961488 : partial_overlap);
1219 : }
1220 : return -1;
1221 : }
1222 :
1223 : /* Consider access path1 base1....ref1 and access path2 base2...ref2.
1224 : Return true if they can be composed to single access path
1225 : base1...ref1...base2...ref2.
1226 :
1227 : REF_TYPE1 if type of REF1. END_STRUCT_PAST_END1 is true if there is
1228 : a trailing array access after REF1 in the non-TBAA part of the access.
1229 : REF1_ALIAS_SET is the alias set of REF1.
1230 :
1231 : BASE_TYPE2 is type of base2. END_STRUCT_REF2 is non-NULL if there is
1232 : a trailing array access in the TBAA part of access path2.
1233 : BASE2_ALIAS_SET is the alias set of base2. */
1234 :
1235 : bool
1236 1948533 : access_path_may_continue_p (tree ref_type1, bool end_struct_past_end1,
1237 : alias_set_type ref1_alias_set,
1238 : tree base_type2, tree end_struct_ref2,
1239 : alias_set_type base2_alias_set)
1240 : {
1241 : /* Access path can not continue past types with no components. */
1242 1948533 : if (!type_has_components_p (ref_type1))
1243 : return false;
1244 :
1245 : /* If first access path ends by too small type to hold base of
1246 : the second access path, typically paths can not continue.
1247 :
1248 : Punt if end_struct_past_end1 is true. We want to support arbitrary
1249 : type puning past first COMPONENT_REF to union because redundant store
1250 : elimination depends on this, see PR92152. For this reason we can not
1251 : check size of the reference because types may partially overlap. */
1252 182120 : if (!end_struct_past_end1)
1253 : {
1254 182075 : if (compare_type_sizes (ref_type1, base_type2) < 0)
1255 : return false;
1256 : /* If the path2 contains trailing array access we can strengthen the check
1257 : to verify that also the size of element of the trailing array fits.
1258 : In fact we could check for offset + type_size, but we do not track
1259 : offsets and this is quite side case. */
1260 164296 : if (end_struct_ref2
1261 164296 : && compare_type_sizes (ref_type1, TREE_TYPE (end_struct_ref2)) < 0)
1262 : return false;
1263 : }
1264 164341 : return (base2_alias_set == ref1_alias_set
1265 164341 : || alias_set_subset_of (base2_alias_set, ref1_alias_set));
1266 : }
1267 :
1268 : /* Determine if the two component references REF1 and REF2 which are
1269 : based on access types TYPE1 and TYPE2 and of which at least one is based
1270 : on an indirect reference may alias.
1271 : REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
1272 : are the respective alias sets. */
1273 :
1274 : static bool
1275 2428526 : aliasing_component_refs_p (tree ref1,
1276 : alias_set_type ref1_alias_set,
1277 : alias_set_type base1_alias_set,
1278 : poly_int64 offset1, poly_int64 max_size1,
1279 : tree ref2,
1280 : alias_set_type ref2_alias_set,
1281 : alias_set_type base2_alias_set,
1282 : poly_int64 offset2, poly_int64 max_size2)
1283 : {
1284 : /* If one reference is a component references through pointers try to find a
1285 : common base and apply offset based disambiguation. This handles
1286 : for example
1287 : struct A { int i; int j; } *q;
1288 : struct B { struct A a; int k; } *p;
1289 : disambiguating q->i and p->a.j. */
1290 2428526 : tree base1, base2;
1291 2428526 : tree type1, type2;
1292 2428526 : bool maybe_match = false;
1293 2428526 : tree end_struct_ref1 = NULL, end_struct_ref2 = NULL;
1294 2428526 : bool end_struct_past_end1 = false;
1295 2428526 : bool end_struct_past_end2 = false;
1296 :
1297 : /* Choose bases and base types to search for.
1298 : The access path is as follows:
1299 : base....end_of_tbaa_ref...actual_ref
1300 : At one place in the access path may be a reference to zero sized or
1301 : trailing array.
1302 :
1303 : We generally discard the segment after end_of_tbaa_ref however
1304 : we need to be careful in case it contains zero sized or trailing array.
1305 : These may happen after reference to union and in this case we need to
1306 : not disambiguate type puning scenarios.
1307 :
1308 : We set:
1309 : base1 to point to base
1310 :
1311 : ref1 to point to end_of_tbaa_ref
1312 :
1313 : end_struct_ref1 to point the trailing reference (if it exists
1314 : in range base....end_of_tbaa_ref
1315 :
1316 : end_struct_past_end1 is true if this trailing reference occurs in
1317 : end_of_tbaa_ref...actual_ref. */
1318 2428526 : base1 = ref1;
1319 5076999 : while (handled_component_p (base1))
1320 : {
1321 : /* Generally access paths are monotous in the size of object. The
1322 : exception are trailing arrays of structures. I.e.
1323 : struct a {int array[0];};
1324 : or
1325 : struct a {int array1[0]; int array[];};
1326 : Such struct has size 0 but accesses to a.array may have non-zero size.
1327 : In this case the size of TREE_TYPE (base1) is smaller than
1328 : size of TREE_TYPE (TREE_OPERAND (base1, 0)).
1329 :
1330 : Because we compare sizes of arrays just by sizes of their elements,
1331 : we only need to care about zero sized array fields here. */
1332 2648473 : if (component_ref_to_zero_sized_trailing_array_p (base1))
1333 : {
1334 75185 : gcc_checking_assert (!end_struct_ref1);
1335 : end_struct_ref1 = base1;
1336 : }
1337 2648473 : if (ends_tbaa_access_path_p (base1))
1338 : {
1339 27184 : ref1 = TREE_OPERAND (base1, 0);
1340 27184 : if (end_struct_ref1)
1341 : {
1342 1 : end_struct_past_end1 = true;
1343 1 : end_struct_ref1 = NULL;
1344 : }
1345 : }
1346 2648473 : base1 = TREE_OPERAND (base1, 0);
1347 : }
1348 2428526 : type1 = TREE_TYPE (base1);
1349 2428526 : base2 = ref2;
1350 5603108 : while (handled_component_p (base2))
1351 : {
1352 3174582 : if (component_ref_to_zero_sized_trailing_array_p (base2))
1353 : {
1354 9247 : gcc_checking_assert (!end_struct_ref2);
1355 : end_struct_ref2 = base2;
1356 : }
1357 3174582 : if (ends_tbaa_access_path_p (base2))
1358 : {
1359 100373 : ref2 = TREE_OPERAND (base2, 0);
1360 100373 : if (end_struct_ref2)
1361 : {
1362 44 : end_struct_past_end2 = true;
1363 44 : end_struct_ref2 = NULL;
1364 : }
1365 : }
1366 3174582 : base2 = TREE_OPERAND (base2, 0);
1367 : }
1368 2428526 : type2 = TREE_TYPE (base2);
1369 :
1370 : /* Now search for the type1 in the access path of ref2. This
1371 : would be a common base for doing offset based disambiguation on.
1372 : This however only makes sense if type2 is big enough to hold type1. */
1373 2428526 : int cmp_outer = compare_type_sizes (type2, type1);
1374 :
1375 : /* If type2 is big enough to contain type1 walk its access path.
1376 : We also need to care of arrays at the end of structs that may extend
1377 : beyond the end of structure. If this occurs in the TBAA part of the
1378 : access path, we need to consider the increased type as well. */
1379 2428526 : if (cmp_outer >= 0
1380 2428526 : || (end_struct_ref2
1381 1 : && compare_type_sizes (TREE_TYPE (end_struct_ref2), type1) >= 0))
1382 : {
1383 1307180 : int res = aliasing_component_refs_walk (ref1, type1, base1,
1384 : offset1, max_size1,
1385 : end_struct_ref1,
1386 : ref2, base2, offset2, max_size2,
1387 : &maybe_match);
1388 1307180 : if (res != -1)
1389 646589 : return res;
1390 : }
1391 :
1392 : /* If we didn't find a common base, try the other way around. */
1393 1781937 : if (cmp_outer <= 0
1394 1781937 : || (end_struct_ref1
1395 60 : && compare_type_sizes (TREE_TYPE (end_struct_ref1), type2) <= 0))
1396 : {
1397 1338781 : int res = aliasing_component_refs_walk (ref2, type2, base2,
1398 : offset2, max_size2,
1399 : end_struct_ref2,
1400 : ref1, base1, offset1, max_size1,
1401 : &maybe_match);
1402 1338781 : if (res != -1)
1403 314899 : return res;
1404 : }
1405 :
1406 : /* In the following code we make an assumption that the types in access
1407 : paths do not overlap and thus accesses alias only if one path can be
1408 : continuation of another. If we was not able to decide about equivalence,
1409 : we need to give up. */
1410 1467038 : if (maybe_match)
1411 : {
1412 477349 : if (!nonoverlapping_component_refs_p (ref1, ref2))
1413 : {
1414 475541 : ++alias_stats.aliasing_component_refs_p_may_alias;
1415 475541 : return true;
1416 : }
1417 1808 : ++alias_stats.aliasing_component_refs_p_no_alias;
1418 1808 : return false;
1419 : }
1420 :
1421 989689 : if (access_path_may_continue_p (TREE_TYPE (ref1), end_struct_past_end1,
1422 : ref1_alias_set,
1423 : type2, end_struct_ref2,
1424 : base2_alias_set)
1425 989689 : || access_path_may_continue_p (TREE_TYPE (ref2), end_struct_past_end2,
1426 : ref2_alias_set,
1427 : type1, end_struct_ref1,
1428 : base1_alias_set))
1429 : {
1430 163674 : ++alias_stats.aliasing_component_refs_p_may_alias;
1431 163674 : return true;
1432 : }
1433 826015 : ++alias_stats.aliasing_component_refs_p_no_alias;
1434 826015 : return false;
1435 : }
1436 :
1437 : /* FIELD1 and FIELD2 are two fields of component refs. We assume
1438 : that bases of both component refs are either equivalent or nonoverlapping.
1439 : We do not assume that the containers of FIELD1 and FIELD2 are of the
1440 : same type or size.
1441 :
1442 : Return 0 in case the base address of component_refs are same then
1443 : FIELD1 and FIELD2 have same address. Note that FIELD1 and FIELD2
1444 : may not be of same type or size.
1445 :
1446 : Return 1 if FIELD1 and FIELD2 are non-overlapping.
1447 :
1448 : Return -1 otherwise.
1449 :
1450 : Main difference between 0 and -1 is to let
1451 : nonoverlapping_component_refs_since_match_p discover the semantically
1452 : equivalent part of the access path.
1453 :
1454 : Note that this function is used even with -fno-strict-aliasing
1455 : and makes use of no TBAA assumptions. */
1456 :
1457 : static int
1458 3468816 : nonoverlapping_component_refs_p_1 (const_tree field1, const_tree field2)
1459 : {
1460 : /* If both fields are of the same type, we could save hard work of
1461 : comparing offsets. */
1462 3468816 : tree type1 = DECL_CONTEXT (field1);
1463 3468816 : tree type2 = DECL_CONTEXT (field2);
1464 :
1465 3468816 : if (TREE_CODE (type1) == RECORD_TYPE
1466 6802665 : && DECL_BIT_FIELD_REPRESENTATIVE (field1))
1467 : field1 = DECL_BIT_FIELD_REPRESENTATIVE (field1);
1468 3468816 : if (TREE_CODE (type2) == RECORD_TYPE
1469 6802665 : && DECL_BIT_FIELD_REPRESENTATIVE (field2))
1470 : field2 = DECL_BIT_FIELD_REPRESENTATIVE (field2);
1471 :
1472 : /* ??? Bitfields can overlap at RTL level so punt on them.
1473 : FIXME: RTL expansion should be fixed by adjusting the access path
1474 : when producing MEM_ATTRs for MEMs which are wider than
1475 : the bitfields similarly as done in set_mem_attrs_minus_bitpos. */
1476 3468816 : if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
1477 : return -1;
1478 :
1479 : /* Assume that different FIELD_DECLs never overlap within a RECORD_TYPE. */
1480 3468816 : if (type1 == type2 && TREE_CODE (type1) == RECORD_TYPE)
1481 3308509 : return field1 != field2;
1482 :
1483 : /* In common case the offsets and bit offsets will be the same.
1484 : However if frontends do not agree on the alignment, they may be
1485 : different even if they actually represent same address.
1486 : Try the common case first and if that fails calculate the
1487 : actual bit offset. */
1488 160307 : if (tree_int_cst_equal (DECL_FIELD_OFFSET (field1),
1489 160307 : DECL_FIELD_OFFSET (field2))
1490 295262 : && tree_int_cst_equal (DECL_FIELD_BIT_OFFSET (field1),
1491 134955 : DECL_FIELD_BIT_OFFSET (field2)))
1492 : return 0;
1493 :
1494 : /* Note that it may be possible to use component_ref_field_offset
1495 : which would provide offsets as trees. However constructing and folding
1496 : trees is expensive and does not seem to be worth the compile time
1497 : cost. */
1498 :
1499 26211 : poly_uint64 offset1, offset2;
1500 26211 : poly_uint64 bit_offset1, bit_offset2;
1501 :
1502 26211 : if (poly_int_tree_p (DECL_FIELD_OFFSET (field1), &offset1)
1503 26211 : && poly_int_tree_p (DECL_FIELD_OFFSET (field2), &offset2)
1504 26211 : && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field1), &bit_offset1)
1505 52422 : && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field2), &bit_offset2))
1506 : {
1507 26211 : offset1 = (offset1 << LOG2_BITS_PER_UNIT) + bit_offset1;
1508 26211 : offset2 = (offset2 << LOG2_BITS_PER_UNIT) + bit_offset2;
1509 :
1510 26211 : if (known_eq (offset1, offset2))
1511 22648 : return 0;
1512 :
1513 26211 : poly_uint64 size1, size2;
1514 :
1515 26211 : if (poly_int_tree_p (DECL_SIZE (field1), &size1)
1516 26211 : && poly_int_tree_p (DECL_SIZE (field2), &size2)
1517 52422 : && !ranges_maybe_overlap_p (offset1, size1, offset2, size2))
1518 : return 1;
1519 : }
1520 : /* Resort to slower overlap checking by looking for matching types in
1521 : the middle of access path. */
1522 : return -1;
1523 : }
1524 :
1525 : /* Return low bound of array. Do not produce new trees
1526 : and thus do not care about particular type of integer constant
1527 : and placeholder exprs. */
1528 :
1529 : static tree
1530 17670808 : cheap_array_ref_low_bound (tree ref)
1531 : {
1532 17670808 : tree domain_type = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (ref, 0)));
1533 :
1534 : /* Avoid expensive array_ref_low_bound.
1535 : low bound is either stored in operand2, or it is TYPE_MIN_VALUE of domain
1536 : type or it is zero. */
1537 17670808 : if (TREE_OPERAND (ref, 2))
1538 81325 : return TREE_OPERAND (ref, 2);
1539 17589483 : else if (domain_type && TYPE_MIN_VALUE (domain_type))
1540 17582563 : return TYPE_MIN_VALUE (domain_type);
1541 : else
1542 6920 : return integer_zero_node;
1543 : }
1544 :
1545 : /* REF1 and REF2 are ARRAY_REFs with either same base address or which are
1546 : completely disjoint.
1547 :
1548 : Return 1 if the refs are non-overlapping.
1549 : Return 0 if they are possibly overlapping but if so the overlap again
1550 : starts on the same address.
1551 : Return -1 otherwise. */
1552 :
1553 : int
1554 8817054 : nonoverlapping_array_refs_p (tree ref1, tree ref2)
1555 : {
1556 8817054 : tree index1 = TREE_OPERAND (ref1, 1);
1557 8817054 : tree index2 = TREE_OPERAND (ref2, 1);
1558 8817054 : tree low_bound1 = cheap_array_ref_low_bound (ref1);
1559 8817054 : tree low_bound2 = cheap_array_ref_low_bound (ref2);
1560 :
1561 : /* Handle zero offsets first: we do not need to match type size in this
1562 : case. */
1563 8817054 : if (operand_equal_p (index1, low_bound1, 0)
1564 8817054 : && operand_equal_p (index2, low_bound2, 0))
1565 : return 0;
1566 :
1567 : /* If type sizes are different, give up.
1568 :
1569 : Avoid expensive array_ref_element_size.
1570 : If operand 3 is present it denotes size in the alignment units.
1571 : Otherwise size is TYPE_SIZE of the element type.
1572 : Handle only common cases where types are of the same "kind". */
1573 8737999 : if ((TREE_OPERAND (ref1, 3) == NULL) != (TREE_OPERAND (ref2, 3) == NULL))
1574 : return -1;
1575 :
1576 8737999 : tree elmt_type1 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref1, 0)));
1577 8737999 : tree elmt_type2 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref2, 0)));
1578 :
1579 8737999 : if (TREE_OPERAND (ref1, 3))
1580 : {
1581 4064 : if (TYPE_ALIGN (elmt_type1) != TYPE_ALIGN (elmt_type2)
1582 8128 : || !operand_equal_p (TREE_OPERAND (ref1, 3),
1583 4064 : TREE_OPERAND (ref2, 3), 0))
1584 : return -1;
1585 : }
1586 : else
1587 : {
1588 8733935 : if (!operand_equal_p (TYPE_SIZE_UNIT (elmt_type1),
1589 8733935 : TYPE_SIZE_UNIT (elmt_type2), 0))
1590 : return -1;
1591 : }
1592 :
1593 : /* Since we know that type sizes are the same, there is no need to return
1594 : -1 after this point. Partial overlap can not be introduced. */
1595 :
1596 : /* We may need to fold trees in this case.
1597 : TODO: Handle integer constant case at least. */
1598 8729490 : if (!operand_equal_p (low_bound1, low_bound2, 0))
1599 : return 0;
1600 :
1601 8729490 : if (TREE_CODE (index1) == INTEGER_CST && TREE_CODE (index2) == INTEGER_CST)
1602 : {
1603 312910 : if (tree_int_cst_equal (index1, index2))
1604 : return 0;
1605 231455 : return 1;
1606 : }
1607 : /* TODO: We can use VRP to further disambiguate here. */
1608 : return 0;
1609 : }
1610 :
1611 : /* Try to disambiguate REF1 and REF2 under the assumption that MATCH1 and
1612 : MATCH2 either point to the same address or are disjoint.
1613 : MATCH1 and MATCH2 are assumed to be ref in the access path of REF1 and REF2
1614 : respectively or NULL in the case we established equivalence of bases.
1615 : If PARTIAL_OVERLAP is true assume that the toplevel arrays may actually
1616 : overlap by exact multiply of their element size.
1617 :
1618 : This test works by matching the initial segment of the access path
1619 : and does not rely on TBAA thus is safe for !flag_strict_aliasing if
1620 : match was determined without use of TBAA oracle.
1621 :
1622 : Return 1 if we can determine that component references REF1 and REF2,
1623 : that are within a common DECL, cannot overlap.
1624 :
1625 : Return 0 if paths are same and thus there is nothing to disambiguate more
1626 : (i.e. there is must alias assuming there is must alias between MATCH1 and
1627 : MATCH2)
1628 :
1629 : Return -1 if we can not determine 0 or 1 - this happens when we met
1630 : non-matching types was met in the path.
1631 : In this case it may make sense to continue by other disambiguation
1632 : oracles. */
1633 :
1634 : static int
1635 9352500 : nonoverlapping_refs_since_match_p (tree match1, tree ref1,
1636 : tree match2, tree ref2,
1637 : bool partial_overlap)
1638 : {
1639 9352500 : int ntbaa1 = 0, ntbaa2 = 0;
1640 : /* Early return if there are no references to match, we do not need
1641 : to walk the access paths.
1642 :
1643 : Do not consider this as may-alias for stats - it is more useful
1644 : to have information how many disambiguations happened provided that
1645 : the query was meaningful. */
1646 :
1647 8506842 : if (match1 == ref1 || !handled_component_p (ref1)
1648 17857737 : || match2 == ref2 || !handled_component_p (ref2))
1649 : return -1;
1650 :
1651 8486530 : auto_vec<tree, 16> component_refs1;
1652 8486530 : auto_vec<tree, 16> component_refs2;
1653 :
1654 : /* Create the stack of handled components for REF1. */
1655 21679971 : while (handled_component_p (ref1) && ref1 != match1)
1656 : {
1657 : /* We use TBAA only to re-synchronize after mismatched refs. So we
1658 : do not need to truncate access path after TBAA part ends. */
1659 13193441 : if (ends_tbaa_access_path_p (ref1))
1660 : ntbaa1 = 0;
1661 : else
1662 12970070 : ntbaa1++;
1663 13193441 : component_refs1.safe_push (ref1);
1664 13193441 : ref1 = TREE_OPERAND (ref1, 0);
1665 : }
1666 :
1667 : /* Create the stack of handled components for REF2. */
1668 21640260 : while (handled_component_p (ref2) && ref2 != match2)
1669 : {
1670 13153730 : if (ends_tbaa_access_path_p (ref2))
1671 : ntbaa2 = 0;
1672 : else
1673 12913604 : ntbaa2++;
1674 13153730 : component_refs2.safe_push (ref2);
1675 13153730 : ref2 = TREE_OPERAND (ref2, 0);
1676 : }
1677 :
1678 8486530 : if (!flag_strict_aliasing)
1679 : {
1680 497307 : ntbaa1 = 0;
1681 497307 : ntbaa2 = 0;
1682 : }
1683 :
1684 8486530 : bool mem_ref1 = TREE_CODE (ref1) == MEM_REF && ref1 != match1;
1685 8486530 : bool mem_ref2 = TREE_CODE (ref2) == MEM_REF && ref2 != match2;
1686 :
1687 : /* If only one of access path starts with MEM_REF check that offset is 0
1688 : so the addresses stays the same after stripping it.
1689 : TODO: In this case we may walk the other access path until we get same
1690 : offset.
1691 :
1692 : If both starts with MEM_REF, offset has to be same. */
1693 73242 : if ((mem_ref1 && !mem_ref2 && !integer_zerop (TREE_OPERAND (ref1, 1)))
1694 8458549 : || (mem_ref2 && !mem_ref1 && !integer_zerop (TREE_OPERAND (ref2, 1)))
1695 16934372 : || (mem_ref1 && mem_ref2
1696 1164216 : && !tree_int_cst_equal (TREE_OPERAND (ref1, 1),
1697 1164216 : TREE_OPERAND (ref2, 1))))
1698 : {
1699 67299 : ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1700 67299 : return -1;
1701 : }
1702 :
1703 : /* TARGET_MEM_REF are never wrapped in handled components, so we do not need
1704 : to handle them here at all. */
1705 8419231 : gcc_checking_assert (TREE_CODE (ref1) != TARGET_MEM_REF
1706 : && TREE_CODE (ref2) != TARGET_MEM_REF);
1707 :
1708 : /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
1709 : rank. This is sufficient because we start from the same DECL and you
1710 : cannot reference several fields at a time with COMPONENT_REFs (unlike
1711 : with ARRAY_RANGE_REFs for arrays) so you always need the same number
1712 : of them to access a sub-component, unless you're in a union, in which
1713 : case the return value will precisely be false. */
1714 10779975 : while (true)
1715 : {
1716 : /* Track if we seen unmatched ref with non-zero offset. In this case
1717 : we must look for partial overlaps. */
1718 10779975 : bool seen_unmatched_ref_p = false;
1719 :
1720 : /* First match ARRAY_REFs an try to disambiguate. */
1721 20843738 : if (!component_refs1.is_empty ()
1722 10510057 : && !component_refs2.is_empty ())
1723 : {
1724 19235445 : unsigned int narray_refs1=0, narray_refs2=0;
1725 :
1726 : /* We generally assume that both access paths starts by same sequence
1727 : of refs. However if number of array refs is not in sync, try
1728 : to recover and pop elts until number match. This helps the case
1729 : where one access path starts by array and other by element. */
1730 19235445 : for (narray_refs1 = 0; narray_refs1 < component_refs1.length ();
1731 : narray_refs1++)
1732 12816212 : if (TREE_CODE (component_refs1 [component_refs1.length()
1733 : - 1 - narray_refs1]) != ARRAY_REF)
1734 : break;
1735 :
1736 19238983 : for (narray_refs2 = 0; narray_refs2 < component_refs2.length ();
1737 : narray_refs2++)
1738 12826146 : if (TREE_CODE (component_refs2 [component_refs2.length()
1739 : - 1 - narray_refs2]) != ARRAY_REF)
1740 : break;
1741 10034918 : for (; narray_refs1 > narray_refs2; narray_refs1--)
1742 : {
1743 16581 : ref1 = component_refs1.pop ();
1744 16581 : ntbaa1--;
1745 :
1746 : /* If index is non-zero we need to check whether the reference
1747 : does not break the main invariant that bases are either
1748 : disjoint or equal. Consider the example:
1749 :
1750 : unsigned char out[][1];
1751 : out[1]="a";
1752 : out[i][0];
1753 :
1754 : Here bases out and out are same, but after removing the
1755 : [i] index, this invariant no longer holds, because
1756 : out[i] points to the middle of array out.
1757 :
1758 : TODO: If size of type of the skipped reference is an integer
1759 : multiply of the size of type of the other reference this
1760 : invariant can be verified, but even then it is not completely
1761 : safe with !flag_strict_aliasing if the other reference contains
1762 : unbounded array accesses.
1763 : See */
1764 :
1765 16581 : if (!operand_equal_p (TREE_OPERAND (ref1, 1),
1766 16581 : cheap_array_ref_low_bound (ref1), 0))
1767 : return 0;
1768 : }
1769 10018378 : for (; narray_refs2 > narray_refs1; narray_refs2--)
1770 : {
1771 20119 : ref2 = component_refs2.pop ();
1772 20119 : ntbaa2--;
1773 20119 : if (!operand_equal_p (TREE_OPERAND (ref2, 1),
1774 20119 : cheap_array_ref_low_bound (ref2), 0))
1775 : return 0;
1776 : }
1777 : /* Try to disambiguate matched arrays. */
1778 18580834 : for (unsigned int i = 0; i < narray_refs1; i++)
1779 : {
1780 17634108 : int cmp = nonoverlapping_array_refs_p (component_refs1.pop (),
1781 8817054 : component_refs2.pop ());
1782 8817054 : ntbaa1--;
1783 8817054 : ntbaa2--;
1784 8817054 : if (cmp == 1 && !partial_overlap)
1785 : {
1786 225970 : ++alias_stats
1787 225970 : .nonoverlapping_refs_since_match_p_no_alias;
1788 225970 : return 1;
1789 : }
1790 8591084 : if (cmp == -1)
1791 : {
1792 8509 : seen_unmatched_ref_p = true;
1793 : /* We can not maintain the invariant that bases are either
1794 : same or completely disjoint. However we can still recover
1795 : from type based alias analysis if we reach references to
1796 : same sizes. We do not attempt to match array sizes, so
1797 : just finish array walking and look for component refs. */
1798 8509 : if (ntbaa1 < 0 || ntbaa2 < 0)
1799 : {
1800 7645 : ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1801 7645 : return -1;
1802 : }
1803 1802 : for (i++; i < narray_refs1; i++)
1804 : {
1805 938 : component_refs1.pop ();
1806 938 : component_refs2.pop ();
1807 938 : ntbaa1--;
1808 938 : ntbaa2--;
1809 : }
1810 : break;
1811 : }
1812 8582575 : partial_overlap = false;
1813 : }
1814 : }
1815 :
1816 : /* Next look for component_refs. */
1817 10574039 : do
1818 : {
1819 10574039 : if (component_refs1.is_empty ())
1820 : {
1821 6976500 : ++alias_stats
1822 6976500 : .nonoverlapping_refs_since_match_p_must_overlap;
1823 6976500 : return 0;
1824 : }
1825 3597539 : ref1 = component_refs1.pop ();
1826 3597539 : ntbaa1--;
1827 3597539 : if (TREE_CODE (ref1) != COMPONENT_REF)
1828 : {
1829 111397 : seen_unmatched_ref_p = true;
1830 111397 : if (ntbaa1 < 0 || ntbaa2 < 0)
1831 : {
1832 47415 : ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1833 47415 : return -1;
1834 : }
1835 : }
1836 : }
1837 7036266 : while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
1838 :
1839 3486142 : do
1840 : {
1841 3486142 : if (component_refs2.is_empty ())
1842 : {
1843 20668 : ++alias_stats
1844 20668 : .nonoverlapping_refs_since_match_p_must_overlap;
1845 20668 : return 0;
1846 : }
1847 3465474 : ref2 = component_refs2.pop ();
1848 3465474 : ntbaa2--;
1849 3465474 : if (TREE_CODE (ref2) != COMPONENT_REF)
1850 : {
1851 48 : if (ntbaa1 < 0 || ntbaa2 < 0)
1852 : {
1853 48 : ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
1854 48 : return -1;
1855 : }
1856 : seen_unmatched_ref_p = true;
1857 : }
1858 : }
1859 6930852 : while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0))));
1860 :
1861 : /* BIT_FIELD_REF and VIEW_CONVERT_EXPR are taken off the vectors
1862 : earlier. */
1863 3465426 : gcc_checking_assert (TREE_CODE (ref1) == COMPONENT_REF
1864 : && TREE_CODE (ref2) == COMPONENT_REF);
1865 :
1866 3465426 : tree field1 = TREE_OPERAND (ref1, 1);
1867 3465426 : tree field2 = TREE_OPERAND (ref2, 1);
1868 :
1869 : /* ??? We cannot simply use the type of operand #0 of the refs here
1870 : as the Fortran compiler smuggles type punning into COMPONENT_REFs
1871 : for common blocks instead of using unions like everyone else. */
1872 3465426 : tree type1 = DECL_CONTEXT (field1);
1873 3465426 : tree type2 = DECL_CONTEXT (field2);
1874 :
1875 3465426 : partial_overlap = false;
1876 :
1877 : /* If we skipped array refs on type of different sizes, we can
1878 : no longer be sure that there are not partial overlaps. */
1879 432 : if (seen_unmatched_ref_p && ntbaa1 >= 0 && ntbaa2 >= 0
1880 3465858 : && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
1881 : {
1882 0 : ++alias_stats
1883 0 : .nonoverlapping_refs_since_match_p_may_alias;
1884 0 : return -1;
1885 : }
1886 :
1887 3465426 : int cmp = nonoverlapping_component_refs_p_1 (field1, field2);
1888 3465426 : if (cmp == -1)
1889 : {
1890 3563 : ++alias_stats
1891 3563 : .nonoverlapping_refs_since_match_p_may_alias;
1892 3563 : return -1;
1893 : }
1894 3461863 : else if (cmp == 1)
1895 : {
1896 1101119 : ++alias_stats
1897 1101119 : .nonoverlapping_refs_since_match_p_no_alias;
1898 1101119 : return 1;
1899 : }
1900 : }
1901 8486530 : }
1902 :
1903 : /* Return TYPE_UID which can be used to match record types we consider
1904 : same for TBAA purposes. */
1905 :
1906 : static inline int
1907 163554 : ncr_type_uid (const_tree field)
1908 : {
1909 : /* ??? We cannot simply use the type of operand #0 of the refs here
1910 : as the Fortran compiler smuggles type punning into COMPONENT_REFs
1911 : for common blocks instead of using unions like everyone else. */
1912 163554 : tree type = DECL_FIELD_CONTEXT (field);
1913 : /* With LTO types considered same_type_for_tbaa_p
1914 : from different translation unit may not have same
1915 : main variant. They however have same TYPE_CANONICAL. */
1916 163554 : if (TYPE_CANONICAL (type))
1917 163554 : return TYPE_UID (TYPE_CANONICAL (type));
1918 0 : return TYPE_UID (type);
1919 : }
1920 :
1921 : /* qsort compare function to sort FIELD_DECLs after their
1922 : DECL_FIELD_CONTEXT TYPE_UID. */
1923 :
1924 : static inline int
1925 71903 : ncr_compar (const void *field1_, const void *field2_)
1926 : {
1927 71903 : const_tree field1 = *(const_tree *) const_cast <void *>(field1_);
1928 71903 : const_tree field2 = *(const_tree *) const_cast <void *>(field2_);
1929 71903 : unsigned int uid1 = ncr_type_uid (field1);
1930 71903 : unsigned int uid2 = ncr_type_uid (field2);
1931 :
1932 71903 : if (uid1 < uid2)
1933 : return -1;
1934 28409 : else if (uid1 > uid2)
1935 28409 : return 1;
1936 : return 0;
1937 : }
1938 :
1939 : /* Return true if we can determine that the fields referenced cannot
1940 : overlap for any pair of objects. This relies on TBAA. */
1941 :
1942 : static bool
1943 1340630 : nonoverlapping_component_refs_p (const_tree x, const_tree y)
1944 : {
1945 : /* Early return if we have nothing to do.
1946 :
1947 : Do not consider this as may-alias for stats - it is more useful
1948 : to have information how many disambiguations happened provided that
1949 : the query was meaningful. */
1950 1340630 : if (!flag_strict_aliasing
1951 1340630 : || !x || !y
1952 171101 : || !handled_component_p (x)
1953 1340630 : || !handled_component_p (y))
1954 : return false;
1955 :
1956 100618 : auto_vec<const_tree, 16> fieldsx;
1957 317640 : while (handled_component_p (x))
1958 : {
1959 217022 : if (TREE_CODE (x) == COMPONENT_REF)
1960 : {
1961 129615 : tree field = TREE_OPERAND (x, 1);
1962 129615 : tree type = DECL_FIELD_CONTEXT (field);
1963 129615 : if (TREE_CODE (type) == RECORD_TYPE)
1964 129323 : fieldsx.safe_push (field);
1965 : }
1966 87407 : else if (ends_tbaa_access_path_p (x))
1967 2248 : fieldsx.truncate (0);
1968 217022 : x = TREE_OPERAND (x, 0);
1969 : }
1970 171559 : if (fieldsx.length () == 0)
1971 : return false;
1972 70941 : auto_vec<const_tree, 16> fieldsy;
1973 156464 : while (handled_component_p (y))
1974 : {
1975 85523 : if (TREE_CODE (y) == COMPONENT_REF)
1976 : {
1977 19247 : tree field = TREE_OPERAND (y, 1);
1978 19247 : tree type = DECL_FIELD_CONTEXT (field);
1979 19247 : if (TREE_CODE (type) == RECORD_TYPE)
1980 18955 : fieldsy.safe_push (TREE_OPERAND (y, 1));
1981 : }
1982 66276 : else if (ends_tbaa_access_path_p (y))
1983 140 : fieldsy.truncate (0);
1984 85523 : y = TREE_OPERAND (y, 0);
1985 : }
1986 70941 : if (fieldsy.length () == 0)
1987 : {
1988 61959 : ++alias_stats.nonoverlapping_component_refs_p_may_alias;
1989 61959 : return false;
1990 : }
1991 :
1992 : /* Most common case first. */
1993 8982 : if (fieldsx.length () == 1
1994 8982 : && fieldsy.length () == 1)
1995 : {
1996 9660 : if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldsx[0]),
1997 4830 : DECL_FIELD_CONTEXT (fieldsy[0])) == 1
1998 8024 : && nonoverlapping_component_refs_p_1 (fieldsx[0], fieldsy[0]) == 1)
1999 : {
2000 1808 : ++alias_stats.nonoverlapping_component_refs_p_no_alias;
2001 1808 : return true;
2002 : }
2003 : else
2004 : {
2005 3022 : ++alias_stats.nonoverlapping_component_refs_p_may_alias;
2006 3022 : return false;
2007 : }
2008 : }
2009 :
2010 4152 : if (fieldsx.length () == 2)
2011 : {
2012 314 : if (ncr_compar (&fieldsx[0], &fieldsx[1]) == 1)
2013 172 : std::swap (fieldsx[0], fieldsx[1]);
2014 : }
2015 : else
2016 3838 : fieldsx.qsort (ncr_compar);
2017 :
2018 4152 : if (fieldsy.length () == 2)
2019 : {
2020 166 : if (ncr_compar (&fieldsy[0], &fieldsy[1]) == 1)
2021 106 : std::swap (fieldsy[0], fieldsy[1]);
2022 : }
2023 : else
2024 3986 : fieldsy.qsort (ncr_compar);
2025 :
2026 4152 : unsigned i = 0, j = 0;
2027 9874 : do
2028 : {
2029 9874 : const_tree fieldx = fieldsx[i];
2030 9874 : const_tree fieldy = fieldsy[j];
2031 :
2032 : /* We're left with accessing different fields of a structure,
2033 : no possible overlap. */
2034 19748 : if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldx),
2035 9874 : DECL_FIELD_CONTEXT (fieldy)) == 1
2036 9874 : && nonoverlapping_component_refs_p_1 (fieldx, fieldy) == 1)
2037 : {
2038 0 : ++alias_stats.nonoverlapping_component_refs_p_no_alias;
2039 0 : return true;
2040 : }
2041 :
2042 9874 : if (ncr_type_uid (fieldx) < ncr_type_uid (fieldy))
2043 : {
2044 3573 : i++;
2045 7146 : if (i == fieldsx.length ())
2046 : break;
2047 : }
2048 : else
2049 : {
2050 6301 : j++;
2051 12602 : if (j == fieldsy.length ())
2052 : break;
2053 : }
2054 : }
2055 : while (1);
2056 :
2057 4152 : ++alias_stats.nonoverlapping_component_refs_p_may_alias;
2058 4152 : return false;
2059 171559 : }
2060 :
2061 :
2062 : /* Return true if two memory references based on the variables BASE1
2063 : and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
2064 : [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. REF1 and REF2
2065 : if non-NULL are the complete memory reference trees. */
2066 :
2067 : static bool
2068 1553832528 : decl_refs_may_alias_p (tree ref1, tree base1,
2069 : poly_int64 offset1, poly_int64 max_size1,
2070 : poly_int64 size1,
2071 : tree ref2, tree base2,
2072 : poly_int64 offset2, poly_int64 max_size2,
2073 : poly_int64 size2)
2074 : {
2075 1553832528 : gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
2076 :
2077 : /* If both references are based on different variables, they cannot alias. */
2078 1553832528 : if (compare_base_decls (base1, base2) == 0)
2079 : return false;
2080 :
2081 : /* If both references are based on the same variable, they cannot alias if
2082 : the accesses do not overlap. */
2083 209551893 : if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
2084 : return false;
2085 :
2086 : /* If there is must alias, there is no use disambiguating further. */
2087 62537463 : if (known_eq (size1, max_size1) && known_eq (size2, max_size2))
2088 : return true;
2089 :
2090 : /* For components with variable position, the above test isn't sufficient,
2091 : so we disambiguate component references manually. */
2092 10676837 : if (ref1 && ref2
2093 8086762 : && handled_component_p (ref1) && handled_component_p (ref2)
2094 17951868 : && nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2, false) == 1)
2095 1113689 : return false;
2096 :
2097 : return true;
2098 : }
2099 :
2100 : /* Return true if access with BASE is view converted.
2101 : Base must not be stripped from inner MEM_REF (&decl)
2102 : which is done by ao_ref_base and thus one extra walk
2103 : of handled components is needed. */
2104 :
2105 : bool
2106 1269496415 : view_converted_memref_p (tree base)
2107 : {
2108 1269496415 : if (TREE_CODE (base) != MEM_REF && TREE_CODE (base) != TARGET_MEM_REF)
2109 : return false;
2110 850488059 : return (same_type_for_tbaa (TREE_TYPE (base),
2111 850488059 : TREE_TYPE (TREE_TYPE (TREE_OPERAND (base, 1))))
2112 850488059 : != 1);
2113 : }
2114 :
2115 : /* Return true if an indirect reference based on *PTR1 constrained
2116 : to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
2117 : constrained to [OFFSET2, OFFSET2 + MAX_SIZE2). *PTR1 and BASE2 have
2118 : the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
2119 : in which case they are computed on-demand. REF1 and REF2
2120 : if non-NULL are the complete memory reference trees. */
2121 :
2122 : static bool
2123 309765373 : indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
2124 : poly_int64 offset1, poly_int64 max_size1,
2125 : poly_int64 size1,
2126 : alias_set_type ref1_alias_set,
2127 : alias_set_type base1_alias_set,
2128 : tree ref2 ATTRIBUTE_UNUSED, tree base2,
2129 : poly_int64 offset2, poly_int64 max_size2,
2130 : poly_int64 size2,
2131 : alias_set_type ref2_alias_set,
2132 : alias_set_type base2_alias_set, bool tbaa_p)
2133 : {
2134 309765373 : tree ptr1;
2135 309765373 : tree ptrtype1, dbase2;
2136 :
2137 309765373 : gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
2138 : || TREE_CODE (base1) == TARGET_MEM_REF)
2139 : && DECL_P (base2));
2140 :
2141 309765373 : ptr1 = TREE_OPERAND (base1, 0);
2142 309765373 : poly_offset_int moff = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
2143 :
2144 : /* If only one reference is based on a variable, they cannot alias if
2145 : the pointer access is beyond the extent of the variable access.
2146 : (the pointer base cannot validly point to an offset less than zero
2147 : of the variable).
2148 : ??? IVOPTs creates bases that do not honor this restriction,
2149 : so do not apply this optimization for TARGET_MEM_REFs. */
2150 309765373 : if (TREE_CODE (base1) != TARGET_MEM_REF
2151 309765373 : && !ranges_maybe_overlap_p (offset1 + moff, -1, offset2, max_size2))
2152 75355934 : return false;
2153 :
2154 : /* If the pointer based access is bigger than the variable they cannot
2155 : alias. This is similar to the check below where we use TBAA to
2156 : increase the size of the pointer based access based on the dynamic
2157 : type of a containing object we can infer from it. */
2158 234409439 : poly_int64 dsize2;
2159 234409439 : if (known_size_p (size1)
2160 218459492 : && poly_int_tree_p (DECL_SIZE (base2), &dsize2)
2161 414936148 : && known_lt (dsize2, size1))
2162 : return false;
2163 :
2164 : /* They also cannot alias if the pointer may not point to the decl. */
2165 215552685 : if (!ptr_deref_may_alias_decl_p (ptr1, base2))
2166 : return false;
2167 :
2168 : /* Disambiguations that rely on strict aliasing rules follow. */
2169 31636875 : if (!flag_strict_aliasing || !tbaa_p)
2170 : return true;
2171 :
2172 : /* If the alias set for a pointer access is zero all bets are off. */
2173 6819487 : if (base1_alias_set == 0 || base2_alias_set == 0)
2174 : return true;
2175 :
2176 : /* When we are trying to disambiguate an access with a pointer dereference
2177 : as base versus one with a decl as base we can use both the size
2178 : of the decl and its dynamic type for extra disambiguation.
2179 : ??? We do not know anything about the dynamic type of the decl
2180 : other than that its alias-set contains base2_alias_set as a subset
2181 : which does not help us here. */
2182 : /* As we know nothing useful about the dynamic type of the decl just
2183 : use the usual conflict check rather than a subset test.
2184 : ??? We could introduce -fvery-strict-aliasing when the language
2185 : does not allow decls to have a dynamic type that differs from their
2186 : static type. Then we can check
2187 : !alias_set_subset_of (base1_alias_set, base2_alias_set) instead. */
2188 1644159 : if (base1_alias_set != base2_alias_set
2189 1644159 : && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
2190 : return false;
2191 :
2192 1415576 : ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
2193 :
2194 : /* If the size of the access relevant for TBAA through the pointer
2195 : is bigger than the size of the decl we can't possibly access the
2196 : decl via that pointer. */
2197 1415576 : if (/* ??? This in turn may run afoul when a decl of type T which is
2198 : a member of union type U is accessed through a pointer to
2199 : type U and sizeof T is smaller than sizeof U. */
2200 1415576 : TREE_CODE (TREE_TYPE (ptrtype1)) != UNION_TYPE
2201 1380435 : && TREE_CODE (TREE_TYPE (ptrtype1)) != QUAL_UNION_TYPE
2202 2796011 : && compare_sizes (DECL_SIZE (base2),
2203 1380435 : TYPE_SIZE (TREE_TYPE (ptrtype1))) < 0)
2204 : return false;
2205 :
2206 1381916 : if (!ref2)
2207 : return true;
2208 :
2209 : /* If the decl is accessed via a MEM_REF, reconstruct the base
2210 : we can use for TBAA and an appropriately adjusted offset. */
2211 : dbase2 = ref2;
2212 2254672 : while (handled_component_p (dbase2))
2213 945076 : dbase2 = TREE_OPERAND (dbase2, 0);
2214 1309596 : poly_int64 doffset1 = offset1;
2215 1309596 : poly_offset_int doffset2 = offset2;
2216 1309596 : if (TREE_CODE (dbase2) == MEM_REF
2217 1309596 : || TREE_CODE (dbase2) == TARGET_MEM_REF)
2218 : {
2219 924678 : doffset2 -= mem_ref_offset (dbase2) << LOG2_BITS_PER_UNIT;
2220 462339 : tree ptrtype2 = TREE_TYPE (TREE_OPERAND (dbase2, 1));
2221 : /* If second reference is view-converted, give up now. */
2222 462339 : if (same_type_for_tbaa (TREE_TYPE (dbase2), TREE_TYPE (ptrtype2)) != 1)
2223 : return true;
2224 : }
2225 :
2226 : /* If first reference is view-converted, give up now. */
2227 1203880 : if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1)
2228 : return true;
2229 :
2230 : /* If both references are through the same type, they do not alias
2231 : if the accesses do not overlap. This does extra disambiguation
2232 : for mixed/pointer accesses but requires strict aliasing.
2233 : For MEM_REFs we require that the component-ref offset we computed
2234 : is relative to the start of the type which we ensure by
2235 : comparing rvalue and access type and disregarding the constant
2236 : pointer offset.
2237 :
2238 : But avoid treating variable length arrays as "objects", instead assume they
2239 : can overlap by an exact multiple of their element size.
2240 : See gcc.dg/torture/alias-2.c. */
2241 1098845 : if (((TREE_CODE (base1) != TARGET_MEM_REF
2242 210791 : || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
2243 1063498 : && (TREE_CODE (dbase2) != TARGET_MEM_REF
2244 27656 : || (!TMR_INDEX (dbase2) && !TMR_INDEX2 (dbase2))))
2245 2134971 : && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1)
2246 : {
2247 340899 : bool partial_overlap = (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE
2248 340899 : && (TYPE_SIZE (TREE_TYPE (base1))
2249 2560 : && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1)))
2250 662037 : != INTEGER_CST));
2251 340899 : if (!partial_overlap
2252 340899 : && !ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2))
2253 : return false;
2254 321138 : if (!ref1 || !ref2
2255 : /* If there is must alias, there is no use disambiguating further. */
2256 321138 : || (!partial_overlap
2257 308518 : && known_eq (size1, max_size1) && known_eq (size2, max_size2)))
2258 : return true;
2259 3580 : int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2,
2260 : partial_overlap);
2261 3580 : if (res == -1)
2262 3269 : return !nonoverlapping_component_refs_p (ref1, ref2);
2263 311 : return !res;
2264 : }
2265 :
2266 : /* Do access-path based disambiguation. */
2267 757946 : if (ref1 && ref2
2268 1290824 : && (handled_component_p (ref1) || handled_component_p (ref2)))
2269 552610 : return aliasing_component_refs_p (ref1,
2270 : ref1_alias_set, base1_alias_set,
2271 : offset1, max_size1,
2272 : ref2,
2273 : ref2_alias_set, base2_alias_set,
2274 552610 : offset2, max_size2);
2275 :
2276 : return true;
2277 : }
2278 :
2279 : /* Return true if two indirect references based on *PTR1
2280 : and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
2281 : [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. *PTR1 and *PTR2 have
2282 : the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
2283 : in which case they are computed on-demand. REF1 and REF2
2284 : if non-NULL are the complete memory reference trees. */
2285 :
2286 : static bool
2287 99694611 : indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
2288 : poly_int64 offset1, poly_int64 max_size1,
2289 : poly_int64 size1,
2290 : alias_set_type ref1_alias_set,
2291 : alias_set_type base1_alias_set,
2292 : tree ref2 ATTRIBUTE_UNUSED, tree base2,
2293 : poly_int64 offset2, poly_int64 max_size2,
2294 : poly_int64 size2,
2295 : alias_set_type ref2_alias_set,
2296 : alias_set_type base2_alias_set, bool tbaa_p)
2297 : {
2298 99694611 : tree ptr1;
2299 99694611 : tree ptr2;
2300 99694611 : tree ptrtype1, ptrtype2;
2301 :
2302 99694611 : gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
2303 : || TREE_CODE (base1) == TARGET_MEM_REF)
2304 : && (TREE_CODE (base2) == MEM_REF
2305 : || TREE_CODE (base2) == TARGET_MEM_REF));
2306 :
2307 99694611 : ptr1 = TREE_OPERAND (base1, 0);
2308 99694611 : ptr2 = TREE_OPERAND (base2, 0);
2309 :
2310 : /* If both bases are based on pointers they cannot alias if they may not
2311 : point to the same memory object or if they point to the same object
2312 : and the accesses do not overlap. */
2313 99694611 : if ((!cfun || gimple_in_ssa_p (cfun))
2314 63625081 : && operand_equal_p (ptr1, ptr2, 0)
2315 132799937 : && (((TREE_CODE (base1) != TARGET_MEM_REF
2316 1179906 : || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
2317 33016509 : && (TREE_CODE (base2) != TARGET_MEM_REF
2318 1082017 : || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2))))
2319 104547 : || (TREE_CODE (base1) == TARGET_MEM_REF
2320 92541 : && TREE_CODE (base2) == TARGET_MEM_REF
2321 86009 : && (TMR_STEP (base1) == TMR_STEP (base2)
2322 13573 : || (TMR_STEP (base1) && TMR_STEP (base2)
2323 2691 : && operand_equal_p (TMR_STEP (base1),
2324 2691 : TMR_STEP (base2), 0)))
2325 72436 : && (TMR_INDEX (base1) == TMR_INDEX (base2)
2326 11140 : || (TMR_INDEX (base1) && TMR_INDEX (base2)
2327 9750 : && operand_equal_p (TMR_INDEX (base1),
2328 9750 : TMR_INDEX (base2), 0)))
2329 61296 : && (TMR_INDEX2 (base1) == TMR_INDEX2 (base2)
2330 0 : || (TMR_INDEX2 (base1) && TMR_INDEX2 (base2)
2331 0 : && operand_equal_p (TMR_INDEX2 (base1),
2332 0 : TMR_INDEX2 (base2), 0))))))
2333 : {
2334 33062075 : poly_offset_int moff1 = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
2335 33062075 : poly_offset_int moff2 = mem_ref_offset (base2) << LOG2_BITS_PER_UNIT;
2336 33062075 : if (!ranges_maybe_overlap_p (offset1 + moff1, max_size1,
2337 33062075 : offset2 + moff2, max_size2))
2338 32743870 : return false;
2339 : /* If there is must alias, there is no use disambiguating further. */
2340 4278335 : if (known_eq (size1, max_size1) && known_eq (size2, max_size2))
2341 : return true;
2342 1238353 : if (ref1 && ref2)
2343 : {
2344 931251 : int res = nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2,
2345 : false);
2346 931251 : if (res != -1)
2347 920148 : return !res;
2348 : }
2349 : }
2350 66950741 : if (!ptr_derefs_may_alias_p (ptr1, ptr2))
2351 : return false;
2352 :
2353 : /* Disambiguations that rely on strict aliasing rules follow. */
2354 38228177 : if (!flag_strict_aliasing || !tbaa_p)
2355 : return true;
2356 :
2357 15171698 : ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
2358 15171698 : ptrtype2 = TREE_TYPE (TREE_OPERAND (base2, 1));
2359 :
2360 : /* If the alias set for a pointer access is zero all bets are off. */
2361 15171698 : if (base1_alias_set == 0
2362 15171698 : || base2_alias_set == 0)
2363 : return true;
2364 :
2365 : /* Do type-based disambiguation. */
2366 10072355 : if (base1_alias_set != base2_alias_set
2367 10072355 : && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
2368 : return false;
2369 :
2370 : /* If either reference is view-converted, give up now. */
2371 9244453 : if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
2372 9244453 : || same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) != 1)
2373 : return true;
2374 :
2375 : /* If both references are through the same type, they do not alias
2376 : if the accesses do not overlap. This does extra disambiguation
2377 : for mixed/pointer accesses but requires strict aliasing. */
2378 6676396 : if ((TREE_CODE (base1) != TARGET_MEM_REF
2379 1169264 : || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
2380 6326973 : && (TREE_CODE (base2) != TARGET_MEM_REF
2381 993036 : || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2)))
2382 12869430 : && same_type_for_tbaa (TREE_TYPE (ptrtype1),
2383 6193034 : TREE_TYPE (ptrtype2)) == 1)
2384 : {
2385 : /* But avoid treating arrays as "objects", instead assume they
2386 : can overlap by an exact multiple of their element size.
2387 : See gcc.dg/torture/alias-2.c. */
2388 4111258 : bool partial_overlap = TREE_CODE (TREE_TYPE (ptrtype1)) == ARRAY_TYPE;
2389 :
2390 4111258 : if (!partial_overlap
2391 4111258 : && !ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
2392 : return false;
2393 3751254 : if (!ref1 || !ref2
2394 3751254 : || (!partial_overlap
2395 3094722 : && known_eq (size1, max_size1) && known_eq (size2, max_size2)))
2396 : return true;
2397 242852 : int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2,
2398 : partial_overlap);
2399 242852 : if (res == -1)
2400 63718 : return !nonoverlapping_component_refs_p (ref1, ref2);
2401 179134 : return !res;
2402 : }
2403 :
2404 : /* Do access-path based disambiguation. */
2405 2565138 : if (ref1 && ref2
2406 3744175 : && (handled_component_p (ref1) || handled_component_p (ref2)))
2407 1875916 : return aliasing_component_refs_p (ref1,
2408 : ref1_alias_set, base1_alias_set,
2409 : offset1, max_size1,
2410 : ref2,
2411 : ref2_alias_set, base2_alias_set,
2412 1875916 : offset2, max_size2);
2413 :
2414 : return true;
2415 : }
2416 :
2417 : /* Return true, if the two memory references REF1 and REF2 may alias. */
2418 :
2419 : static bool
2420 2047205115 : refs_may_alias_p_2 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
2421 : {
2422 2047205115 : tree base1, base2;
2423 2047205115 : poly_int64 offset1 = 0, offset2 = 0;
2424 2047205115 : poly_int64 max_size1 = -1, max_size2 = -1;
2425 2047205115 : bool var1_p, var2_p, ind1_p, ind2_p;
2426 :
2427 2047205115 : gcc_checking_assert ((!ref1->ref
2428 : || TREE_CODE (ref1->ref) == SSA_NAME
2429 : || DECL_P (ref1->ref)
2430 : || TREE_CODE (ref1->ref) == STRING_CST
2431 : || handled_component_p (ref1->ref)
2432 : || TREE_CODE (ref1->ref) == MEM_REF
2433 : || TREE_CODE (ref1->ref) == TARGET_MEM_REF
2434 : || TREE_CODE (ref1->ref) == WITH_SIZE_EXPR)
2435 : && (!ref2->ref
2436 : || TREE_CODE (ref2->ref) == SSA_NAME
2437 : || DECL_P (ref2->ref)
2438 : || TREE_CODE (ref2->ref) == STRING_CST
2439 : || handled_component_p (ref2->ref)
2440 : || TREE_CODE (ref2->ref) == MEM_REF
2441 : || TREE_CODE (ref2->ref) == TARGET_MEM_REF
2442 : || TREE_CODE (ref2->ref) == WITH_SIZE_EXPR));
2443 :
2444 : /* Decompose the references into their base objects and the access. */
2445 2047205115 : base1 = ao_ref_base (ref1);
2446 2047205115 : offset1 = ref1->offset;
2447 2047205115 : max_size1 = ref1->max_size;
2448 2047205115 : base2 = ao_ref_base (ref2);
2449 2047205115 : offset2 = ref2->offset;
2450 2047205115 : max_size2 = ref2->max_size;
2451 :
2452 : /* We can end up with registers or constants as bases for example from
2453 : *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
2454 : which is seen as a struct copy. */
2455 2047205115 : if (TREE_CODE (base1) == SSA_NAME
2456 2047199602 : || TREE_CODE (base1) == CONST_DECL
2457 2045186133 : || TREE_CODE (base1) == CONSTRUCTOR
2458 2045186133 : || TREE_CODE (base1) == ADDR_EXPR
2459 2045186125 : || CONSTANT_CLASS_P (base1)
2460 2038660580 : || TREE_CODE (base2) == SSA_NAME
2461 2038660580 : || TREE_CODE (base2) == CONST_DECL
2462 2038563164 : || TREE_CODE (base2) == CONSTRUCTOR
2463 2038563164 : || TREE_CODE (base2) == ADDR_EXPR
2464 2038563164 : || CONSTANT_CLASS_P (base2))
2465 : return false;
2466 :
2467 : /* Two volatile accesses always conflict. */
2468 2038495517 : if (ref1->volatile_p
2469 5902441 : && ref2->volatile_p)
2470 : return true;
2471 :
2472 : /* refN->ref may convey size information, do not confuse our workers
2473 : with that but strip it - ao_ref_base took it into account already. */
2474 2034841791 : tree ref1ref = ref1->ref;
2475 2034841791 : if (ref1ref && TREE_CODE (ref1ref) == WITH_SIZE_EXPR)
2476 162 : ref1ref = TREE_OPERAND (ref1ref, 0);
2477 2034841791 : tree ref2ref = ref2->ref;
2478 2034841791 : if (ref2ref && TREE_CODE (ref2ref) == WITH_SIZE_EXPR)
2479 0 : ref2ref = TREE_OPERAND (ref2ref, 0);
2480 :
2481 : /* Defer to simple offset based disambiguation if we have
2482 : references based on two decls. Do this before deferring to
2483 : TBAA to handle must-alias cases in conformance with the
2484 : GCC extension of allowing type-punning through unions. */
2485 2034841791 : var1_p = DECL_P (base1);
2486 2034841791 : var2_p = DECL_P (base2);
2487 2034841791 : if (var1_p && var2_p)
2488 1553832528 : return decl_refs_may_alias_p (ref1ref, base1, offset1, max_size1,
2489 : ref1->size,
2490 : ref2ref, base2, offset2, max_size2,
2491 1553832528 : ref2->size);
2492 :
2493 : /* We can end up referring to code via function and label decls.
2494 : As we likely do not properly track code aliases conservatively
2495 : bail out. */
2496 481009263 : if (TREE_CODE (base1) == FUNCTION_DECL
2497 481009263 : || TREE_CODE (base1) == LABEL_DECL
2498 480020104 : || TREE_CODE (base2) == FUNCTION_DECL
2499 480007917 : || TREE_CODE (base2) == LABEL_DECL)
2500 : return true;
2501 :
2502 : /* Handle restrict based accesses.
2503 : ??? ao_ref_base strips inner MEM_REF [&decl], recover from that
2504 : here. */
2505 480007917 : tree rbase1 = base1;
2506 480007917 : tree rbase2 = base2;
2507 480007917 : if (var1_p)
2508 : {
2509 228416562 : rbase1 = ref1ref;
2510 228416562 : if (rbase1)
2511 298188768 : while (handled_component_p (rbase1))
2512 109187023 : rbase1 = TREE_OPERAND (rbase1, 0);
2513 : }
2514 480007917 : if (var2_p)
2515 : {
2516 123872929 : rbase2 = ref2ref;
2517 123872929 : if (rbase2)
2518 202346858 : while (handled_component_p (rbase2))
2519 86742496 : rbase2 = TREE_OPERAND (rbase2, 0);
2520 : }
2521 480007917 : if (rbase1 && rbase2
2522 432324533 : && (TREE_CODE (rbase1) == MEM_REF || TREE_CODE (rbase1) == TARGET_MEM_REF)
2523 278118499 : && (TREE_CODE (rbase2) == MEM_REF || TREE_CODE (rbase2) == TARGET_MEM_REF)
2524 : /* If the accesses are in the same restrict clique... */
2525 194977895 : && MR_DEPENDENCE_CLIQUE (rbase1) == MR_DEPENDENCE_CLIQUE (rbase2)
2526 : /* But based on different pointers they do not alias. */
2527 643961959 : && MR_DEPENDENCE_BASE (rbase1) != MR_DEPENDENCE_BASE (rbase2))
2528 : return false;
2529 :
2530 461114556 : ind1_p = (TREE_CODE (base1) == MEM_REF
2531 461114556 : || TREE_CODE (base1) == TARGET_MEM_REF);
2532 461114556 : ind2_p = (TREE_CODE (base2) == MEM_REF
2533 461114556 : || TREE_CODE (base2) == TARGET_MEM_REF);
2534 :
2535 : /* Canonicalize the pointer-vs-decl case. */
2536 461114556 : if (ind1_p && var2_p)
2537 : {
2538 122768064 : std::swap (offset1, offset2);
2539 122768064 : std::swap (max_size1, max_size2);
2540 122768064 : std::swap (base1, base2);
2541 122768064 : std::swap (ref1, ref2);
2542 122768064 : std::swap (ref1ref, ref2ref);
2543 122768064 : var1_p = true;
2544 122768064 : ind1_p = false;
2545 122768064 : var2_p = false;
2546 122768064 : ind2_p = true;
2547 : }
2548 :
2549 : /* First defer to TBAA if possible. */
2550 461114556 : if (tbaa_p
2551 208918345 : && flag_strict_aliasing
2552 602619812 : && !alias_sets_conflict_p (ao_ref_alias_set (ref1),
2553 : ao_ref_alias_set (ref2)))
2554 : return false;
2555 :
2556 : /* If the reference is based on a pointer that points to memory
2557 : that may not be written to then the other reference cannot possibly
2558 : clobber it. */
2559 410134832 : if ((TREE_CODE (TREE_OPERAND (base2, 0)) == SSA_NAME
2560 408764720 : && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base2, 0)))
2561 818336686 : || (ind1_p
2562 99806593 : && TREE_CODE (TREE_OPERAND (base1, 0)) == SSA_NAME
2563 99609703 : && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base1, 0))))
2564 : return false;
2565 :
2566 : /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators. */
2567 409459984 : if (var1_p && ind2_p)
2568 309765373 : return indirect_ref_may_alias_decl_p (ref2ref, base2,
2569 : offset2, max_size2, ref2->size,
2570 : ao_ref_alias_set (ref2),
2571 : ao_ref_base_alias_set (ref2),
2572 : ref1ref, base1,
2573 : offset1, max_size1, ref1->size,
2574 : ao_ref_alias_set (ref1),
2575 : ao_ref_base_alias_set (ref1),
2576 309765373 : tbaa_p);
2577 99694611 : else if (ind1_p && ind2_p)
2578 99694611 : return indirect_refs_may_alias_p (ref1ref, base1,
2579 : offset1, max_size1, ref1->size,
2580 : ao_ref_alias_set (ref1),
2581 : ao_ref_base_alias_set (ref1),
2582 : ref2ref, base2,
2583 : offset2, max_size2, ref2->size,
2584 : ao_ref_alias_set (ref2),
2585 : ao_ref_base_alias_set (ref2),
2586 99694611 : tbaa_p);
2587 :
2588 0 : gcc_unreachable ();
2589 : }
2590 :
2591 : /* Return true, if the two memory references REF1 and REF2 may alias
2592 : and update statistics. */
2593 :
2594 : bool
2595 2047205115 : refs_may_alias_p_1 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
2596 : {
2597 2047205115 : bool res = refs_may_alias_p_2 (ref1, ref2, tbaa_p);
2598 2047205115 : if (res)
2599 137331193 : ++alias_stats.refs_may_alias_p_may_alias;
2600 : else
2601 1909873922 : ++alias_stats.refs_may_alias_p_no_alias;
2602 2047205115 : return res;
2603 : }
2604 :
2605 : static bool
2606 64469486 : refs_may_alias_p (tree ref1, ao_ref *ref2, bool tbaa_p)
2607 : {
2608 64469486 : ao_ref r1;
2609 64469486 : ao_ref_init (&r1, ref1);
2610 64469486 : return refs_may_alias_p_1 (&r1, ref2, tbaa_p);
2611 : }
2612 :
2613 : bool
2614 1029362 : refs_may_alias_p (tree ref1, tree ref2, bool tbaa_p)
2615 : {
2616 1029362 : ao_ref r1, r2;
2617 1029362 : ao_ref_init (&r1, ref1);
2618 1029362 : ao_ref_init (&r2, ref2);
2619 1029362 : return refs_may_alias_p_1 (&r1, &r2, tbaa_p);
2620 : }
2621 :
2622 : /* Returns true if there is a anti-dependence for the STORE that
2623 : executes after the LOAD. */
2624 :
2625 : bool
2626 409569 : refs_anti_dependent_p (tree load, tree store)
2627 : {
2628 409569 : ao_ref r1, r2;
2629 409569 : ao_ref_init (&r1, load);
2630 409569 : ao_ref_init (&r2, store);
2631 409569 : return refs_may_alias_p_1 (&r1, &r2, false);
2632 : }
2633 :
2634 : /* Returns true if there is a output dependence for the stores
2635 : STORE1 and STORE2. */
2636 :
2637 : bool
2638 2995414 : refs_output_dependent_p (tree store1, tree store2)
2639 : {
2640 2995414 : ao_ref r1, r2;
2641 2995414 : ao_ref_init (&r1, store1);
2642 2995414 : ao_ref_init (&r2, store2);
2643 2995414 : return refs_may_alias_p_1 (&r1, &r2, false);
2644 : }
2645 :
2646 : /* Returns true if and only if REF may alias any access stored in TT.
2647 : IF TBAA_P is true, use TBAA oracle. */
2648 :
2649 : static bool
2650 49520272 : modref_may_conflict (const gcall *stmt,
2651 : modref_tree <alias_set_type> *tt, ao_ref *ref, bool tbaa_p)
2652 : {
2653 49520272 : alias_set_type base_set, ref_set;
2654 49520272 : bool global_memory_ok = false;
2655 :
2656 49520272 : if (tt->every_base)
2657 : return true;
2658 :
2659 9212029 : if (!dbg_cnt (ipa_mod_ref))
2660 : return true;
2661 :
2662 9212029 : base_set = ao_ref_base_alias_set (ref);
2663 :
2664 9212029 : ref_set = ao_ref_alias_set (ref);
2665 :
2666 9212029 : int num_tests = 0, max_tests = param_modref_max_tests;
2667 37401152 : for (auto base_node : tt->bases)
2668 : {
2669 13993642 : if (tbaa_p && flag_strict_aliasing)
2670 : {
2671 10680266 : if (num_tests >= max_tests)
2672 : return true;
2673 10680266 : alias_stats.modref_tests++;
2674 10680266 : if (!alias_sets_conflict_p (base_set, base_node->base))
2675 3655690 : continue;
2676 7024576 : num_tests++;
2677 : }
2678 :
2679 10337952 : if (base_node->every_ref)
2680 : return true;
2681 :
2682 39231390 : for (auto ref_node : base_node->refs)
2683 : {
2684 : /* Do not repeat same test as before. */
2685 12012273 : if ((ref_set != base_set || base_node->base != ref_node->ref)
2686 7431764 : && tbaa_p && flag_strict_aliasing)
2687 : {
2688 4846398 : if (num_tests >= max_tests)
2689 : return true;
2690 4815126 : alias_stats.modref_tests++;
2691 4815126 : if (!alias_sets_conflict_p (ref_set, ref_node->ref))
2692 1158036 : continue;
2693 3657090 : num_tests++;
2694 : }
2695 :
2696 10822965 : if (ref_node->every_access)
2697 : return true;
2698 :
2699 : /* TBAA checks did not disambiguate, try individual accesses. */
2700 34620547 : for (auto access_node : ref_node->accesses)
2701 : {
2702 9883285 : if (num_tests >= max_tests)
2703 1758738 : return true;
2704 :
2705 9883285 : if (access_node.parm_index == MODREF_GLOBAL_MEMORY_PARM)
2706 : {
2707 1986675 : if (global_memory_ok)
2708 1349051 : continue;
2709 1986675 : if (ref_may_alias_global_p (ref, true))
2710 : return true;
2711 1319231 : global_memory_ok = true;
2712 1319231 : num_tests++;
2713 1319231 : continue;
2714 : }
2715 :
2716 7896610 : tree arg = access_node.get_call_arg (stmt);
2717 7896610 : if (!arg)
2718 : return true;
2719 :
2720 7895517 : alias_stats.modref_baseptr_tests++;
2721 :
2722 7895517 : if (integer_zerop (arg) && flag_delete_null_pointer_checks)
2723 29820 : continue;
2724 :
2725 : /* PTA oracle will be unhapy of arg is not an pointer. */
2726 7865697 : if (!POINTER_TYPE_P (TREE_TYPE (arg)))
2727 : return true;
2728 :
2729 : /* If we don't have base pointer, give up. */
2730 7865697 : if (!ref->ref && !ref->base)
2731 0 : continue;
2732 :
2733 7865697 : ao_ref ref2;
2734 7865697 : if (access_node.get_ao_ref (stmt, &ref2))
2735 : {
2736 6154818 : ref2.ref_alias_set = ref_node->ref;
2737 6154818 : ref2.base_alias_set = base_node->base;
2738 6154818 : if (refs_may_alias_p_1 (&ref2, ref, tbaa_p))
2739 : return true;
2740 : }
2741 1710879 : else if (ptr_deref_may_alias_ref_p_1 (arg, ref))
2742 : return true;
2743 :
2744 6775496 : num_tests++;
2745 : }
2746 : }
2747 : }
2748 : return false;
2749 : }
2750 :
2751 : /* Check if REF conflicts with call using "fn spec" attribute.
2752 : If CLOBBER is true we are checking for writes, otherwise check loads.
2753 :
2754 : Return 0 if there are no conflicts (except for possible function call
2755 : argument reads), 1 if there are conflicts and -1 if we can not decide by
2756 : fn spec. */
2757 :
2758 : static int
2759 158971345 : check_fnspec (gcall *call, ao_ref *ref, bool clobber)
2760 : {
2761 158971345 : attr_fnspec fnspec = gimple_call_fnspec (call);
2762 158971345 : if (fnspec.known_p ())
2763 : {
2764 79382667 : if (clobber
2765 79382667 : ? !fnspec.global_memory_written_p ()
2766 9212051 : : !fnspec.global_memory_read_p ())
2767 : {
2768 94812302 : for (unsigned int i = 0; i < gimple_call_num_args (call); i++)
2769 91973107 : if (POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, i)))
2770 64879871 : && (!fnspec.arg_specified_p (i)
2771 37724281 : || (clobber ? fnspec.arg_maybe_written_p (i)
2772 3493084 : : fnspec.arg_maybe_read_p (i))))
2773 : {
2774 23433173 : ao_ref dref;
2775 23433173 : tree size = NULL_TREE;
2776 23433173 : unsigned int size_arg;
2777 :
2778 23433173 : if (!fnspec.arg_specified_p (i))
2779 : ;
2780 23429590 : else if (fnspec.arg_max_access_size_given_by_arg_p
2781 23429590 : (i, &size_arg))
2782 15535034 : size = gimple_call_arg (call, size_arg);
2783 7894556 : else if (fnspec.arg_access_size_given_by_type_p (i))
2784 : {
2785 28164 : tree callee = gimple_call_fndecl (call);
2786 28164 : tree t = TYPE_ARG_TYPES (TREE_TYPE (callee));
2787 :
2788 57639 : for (unsigned int p = 0; p < i; p++)
2789 29475 : t = TREE_CHAIN (t);
2790 28164 : size = TYPE_SIZE_UNIT (TREE_TYPE (TREE_VALUE (t)));
2791 : }
2792 15563198 : poly_int64 size_hwi;
2793 15563198 : if (size
2794 15563198 : && poly_int_tree_p (size, &size_hwi)
2795 28460922 : && coeffs_in_range_p (size_hwi, 0,
2796 : HOST_WIDE_INT_MAX / BITS_PER_UNIT))
2797 : {
2798 12896186 : size_hwi = size_hwi * BITS_PER_UNIT;
2799 12896186 : ao_ref_init_from_ptr_and_range (&dref,
2800 : gimple_call_arg (call, i),
2801 : true, 0, -1, size_hwi);
2802 : }
2803 : else
2804 10536987 : ao_ref_init_from_ptr_and_range (&dref,
2805 : gimple_call_arg (call, i),
2806 : false, 0, -1, -1);
2807 23433173 : if (refs_may_alias_p_1 (&dref, ref, false))
2808 4682723 : return 1;
2809 : }
2810 29991202 : if (clobber
2811 26221952 : && fnspec.errno_maybe_written_p ()
2812 38170900 : && targetm.ref_may_alias_errno (ref))
2813 26712 : return 1;
2814 : return 0;
2815 : }
2816 : }
2817 :
2818 : /* FIXME: we should handle barriers more consistently, but for now leave the
2819 : check here. */
2820 124297420 : if (gimple_call_builtin_p (call, BUILT_IN_NORMAL))
2821 6786017 : switch (DECL_FUNCTION_CODE (gimple_call_fndecl (call)))
2822 : {
2823 : /* __sync_* builtins and some OpenMP builtins act as threading
2824 : barriers. */
2825 : #undef DEF_SYNC_BUILTIN
2826 : #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
2827 : #include "sync-builtins.def"
2828 : #undef DEF_SYNC_BUILTIN
2829 : case BUILT_IN_GOMP_ATOMIC_START:
2830 : case BUILT_IN_GOMP_ATOMIC_END:
2831 : case BUILT_IN_GOMP_REDUCTION_START:
2832 : case BUILT_IN_GOMP_REDUCTION_END:
2833 : case BUILT_IN_GOMP_BARRIER:
2834 : case BUILT_IN_GOMP_BARRIER_CANCEL:
2835 : case BUILT_IN_GOMP_TASKWAIT:
2836 : case BUILT_IN_GOMP_TASKGROUP_END:
2837 : case BUILT_IN_GOMP_CRITICAL_START:
2838 : case BUILT_IN_GOMP_CRITICAL_END:
2839 : case BUILT_IN_GOMP_CRITICAL_NAME_START:
2840 : case BUILT_IN_GOMP_CRITICAL_NAME_END:
2841 : case BUILT_IN_GOMP_LOOP_END:
2842 : case BUILT_IN_GOMP_LOOP_END_CANCEL:
2843 : case BUILT_IN_GOMP_ORDERED_START:
2844 : case BUILT_IN_GOMP_ORDERED_END:
2845 : case BUILT_IN_GOMP_SECTIONS_END:
2846 : case BUILT_IN_GOMP_SECTIONS_END_CANCEL:
2847 : case BUILT_IN_GOMP_SINGLE_COPY_START:
2848 : case BUILT_IN_GOMP_SINGLE_COPY_END:
2849 : return 1;
2850 :
2851 5378879 : default:
2852 5378879 : return -1;
2853 : }
2854 : return -1;
2855 : }
2856 :
2857 : /* If the call CALL may use the memory reference REF return true,
2858 : otherwise return false. */
2859 :
2860 : static bool
2861 47478197 : ref_maybe_used_by_call_p_1 (gcall *call, ao_ref *ref, bool tbaa_p)
2862 : {
2863 47478197 : tree base, callee;
2864 47478197 : unsigned i;
2865 47478197 : int flags = gimple_call_flags (call);
2866 :
2867 47478197 : if (flags & (ECF_CONST|ECF_NOVOPS))
2868 379003 : goto process_args;
2869 :
2870 : /* A call that is not without side-effects might involve volatile
2871 : accesses and thus conflicts with all other volatile accesses. */
2872 47099194 : if (ref->volatile_p)
2873 : return true;
2874 :
2875 47099018 : if (gimple_call_internal_p (call))
2876 75943 : switch (gimple_call_internal_fn (call))
2877 : {
2878 : case IFN_MASK_STORE:
2879 : case IFN_SCATTER_STORE:
2880 : case IFN_MASK_SCATTER_STORE:
2881 : case IFN_LEN_STORE:
2882 : case IFN_MASK_LEN_STORE:
2883 : return false;
2884 0 : case IFN_MASK_STORE_LANES:
2885 0 : case IFN_MASK_LEN_STORE_LANES:
2886 0 : goto process_args;
2887 832 : case IFN_MASK_LOAD:
2888 832 : case IFN_LEN_LOAD:
2889 832 : case IFN_MASK_LEN_LOAD:
2890 832 : case IFN_MASK_LOAD_LANES:
2891 832 : case IFN_MASK_LEN_LOAD_LANES:
2892 832 : {
2893 832 : ao_ref rhs_ref;
2894 832 : tree lhs = gimple_call_lhs (call);
2895 832 : if (lhs)
2896 : {
2897 832 : ao_ref_init_from_ptr_and_size (&rhs_ref,
2898 : gimple_call_arg (call, 0),
2899 832 : TYPE_SIZE_UNIT (TREE_TYPE (lhs)));
2900 : /* We cannot make this a known-size access since otherwise
2901 : we disambiguate against refs to decls that are smaller. */
2902 832 : rhs_ref.size = -1;
2903 1664 : rhs_ref.ref_alias_set = rhs_ref.base_alias_set
2904 1660 : = tbaa_p ? get_deref_alias_set (TREE_TYPE
2905 : (gimple_call_arg (call, 1))) : 0;
2906 832 : return refs_may_alias_p_1 (ref, &rhs_ref, tbaa_p);
2907 : }
2908 0 : break;
2909 : }
2910 : default:;
2911 : }
2912 :
2913 47092717 : callee = gimple_call_fndecl (call);
2914 47092717 : if (callee != NULL_TREE)
2915 : {
2916 45555656 : struct cgraph_node *node = cgraph_node::get (callee);
2917 : /* We can not safely optimize based on summary of callee if it does
2918 : not always bind to current def: it is possible that memory load
2919 : was optimized out earlier and the interposed variant may not be
2920 : optimized this way. */
2921 45555656 : if (node && node->binds_to_current_def_p ())
2922 : {
2923 6301986 : modref_summary *summary = get_modref_function_summary (node);
2924 6301986 : if (summary && !summary->calls_interposable)
2925 : {
2926 3762340 : if (!modref_may_conflict (call, summary->loads, ref, tbaa_p))
2927 : {
2928 651681 : alias_stats.modref_use_no_alias++;
2929 651681 : if (dump_file && (dump_flags & TDF_DETAILS))
2930 : {
2931 24 : fprintf (dump_file,
2932 : "ipa-modref: call stmt ");
2933 24 : print_gimple_stmt (dump_file, call, 0);
2934 24 : fprintf (dump_file,
2935 : "ipa-modref: call to %s does not use ",
2936 : node->dump_name ());
2937 24 : if (!ref->ref && ref->base)
2938 : {
2939 3 : fprintf (dump_file, "base: ");
2940 3 : print_generic_expr (dump_file, ref->base);
2941 : }
2942 21 : else if (ref->ref)
2943 : {
2944 21 : fprintf (dump_file, "ref: ");
2945 21 : print_generic_expr (dump_file, ref->ref);
2946 : }
2947 24 : fprintf (dump_file, " alias sets: %i->%i\n",
2948 : ao_ref_base_alias_set (ref),
2949 : ao_ref_alias_set (ref));
2950 : }
2951 651681 : goto process_args;
2952 : }
2953 3110659 : alias_stats.modref_use_may_alias++;
2954 : }
2955 : }
2956 : }
2957 :
2958 46441036 : base = ao_ref_base (ref);
2959 46441036 : if (!base)
2960 : return true;
2961 :
2962 : /* If the reference is based on a decl that is not aliased the call
2963 : cannot possibly use it. */
2964 46441036 : if (DECL_P (base)
2965 41390505 : && !may_be_aliased (base)
2966 : /* But local statics can be used through recursion. */
2967 69478857 : && !is_global_var (base))
2968 22719119 : goto process_args;
2969 :
2970 23721917 : if (int res = check_fnspec (call, ref, false))
2971 : {
2972 19952667 : if (res == 1)
2973 : return true;
2974 : }
2975 : else
2976 3769250 : goto process_args;
2977 :
2978 : /* Check if base is a global static variable that is not read
2979 : by the function. */
2980 19410482 : if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
2981 : {
2982 1008684 : struct cgraph_node *node = cgraph_node::get (callee);
2983 1008684 : bitmap read;
2984 1008684 : int id;
2985 :
2986 : /* FIXME: Callee can be an OMP builtin that does not have a call graph
2987 : node yet. We should enforce that there are nodes for all decls in the
2988 : IL and remove this check instead. */
2989 1008684 : if (node
2990 1007985 : && (id = ipa_reference_var_uid (base)) != -1
2991 155122 : && (read = ipa_reference_get_read_global (node))
2992 1026484 : && !bitmap_bit_p (read, id))
2993 12586 : goto process_args;
2994 : }
2995 :
2996 : /* Check if the base variable is call-used. */
2997 19397896 : if (DECL_P (base))
2998 : {
2999 15893533 : if (pt_solution_includes (gimple_call_use_set (call), base))
3000 : return true;
3001 : }
3002 3504363 : else if ((TREE_CODE (base) == MEM_REF
3003 3504363 : || TREE_CODE (base) == TARGET_MEM_REF)
3004 3504363 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
3005 : {
3006 3504122 : const pt_solution *pt = ssa_name_pt_solution (TREE_OPERAND (base, 0));
3007 3493594 : if (!pt)
3008 : return true;
3009 :
3010 3491743 : if (pt_solutions_intersect (gimple_call_use_set (call), pt))
3011 : return true;
3012 : }
3013 : else
3014 : return true;
3015 :
3016 : /* Inspect call arguments for passed-by-value aliases. */
3017 31288107 : process_args:
3018 90268518 : for (i = 0; i < gimple_call_num_args (call); ++i)
3019 : {
3020 63262029 : tree op = gimple_call_arg (call, i);
3021 63262029 : int flags = gimple_call_arg_flags (call, i);
3022 :
3023 63262029 : if (flags & (EAF_UNUSED | EAF_NO_DIRECT_READ))
3024 791787 : continue;
3025 :
3026 62470242 : if (TREE_CODE (op) == WITH_SIZE_EXPR)
3027 504 : op = TREE_OPERAND (op, 0);
3028 :
3029 62470242 : if (TREE_CODE (op) != SSA_NAME
3030 62470242 : && !is_gimple_min_invariant (op))
3031 : {
3032 11250808 : ao_ref r;
3033 11250808 : ao_ref_init (&r, op);
3034 11250808 : if (refs_may_alias_p_1 (&r, ref, tbaa_p))
3035 4281618 : return true;
3036 : }
3037 : }
3038 :
3039 : return false;
3040 : }
3041 :
3042 : static bool
3043 47468863 : ref_maybe_used_by_call_p (gcall *call, ao_ref *ref, bool tbaa_p)
3044 : {
3045 47468863 : bool res;
3046 47468863 : res = ref_maybe_used_by_call_p_1 (call, ref, tbaa_p);
3047 47468863 : if (res)
3048 20460286 : ++alias_stats.ref_maybe_used_by_call_p_may_alias;
3049 : else
3050 27008577 : ++alias_stats.ref_maybe_used_by_call_p_no_alias;
3051 47468863 : return res;
3052 : }
3053 :
3054 :
3055 : /* If the statement STMT may use the memory reference REF return
3056 : true, otherwise return false. */
3057 :
3058 : bool
3059 377442962 : ref_maybe_used_by_stmt_p (gimple *stmt, ao_ref *ref, bool tbaa_p)
3060 : {
3061 377442962 : if (is_gimple_assign (stmt))
3062 : {
3063 323645563 : tree rhs;
3064 :
3065 : /* All memory assign statements are single. */
3066 323645563 : if (!gimple_assign_single_p (stmt))
3067 : return false;
3068 :
3069 323645563 : rhs = gimple_assign_rhs1 (stmt);
3070 323645563 : if (is_gimple_reg (rhs)
3071 263084189 : || is_gimple_min_invariant (rhs)
3072 428546442 : || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
3073 : return false;
3074 :
3075 62330408 : return refs_may_alias_p (rhs, ref, tbaa_p);
3076 : }
3077 53797399 : else if (is_gimple_call (stmt))
3078 47468863 : return ref_maybe_used_by_call_p (as_a <gcall *> (stmt), ref, tbaa_p);
3079 6328536 : else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
3080 : {
3081 5570195 : tree retval = gimple_return_retval (return_stmt);
3082 5570195 : if (retval
3083 2940480 : && TREE_CODE (retval) != SSA_NAME
3084 2312608 : && !is_gimple_min_invariant (retval)
3085 7709273 : && refs_may_alias_p (retval, ref, tbaa_p))
3086 : return true;
3087 : /* If ref escapes the function then the return acts as a use. */
3088 3971324 : tree base = ao_ref_base (ref);
3089 3971324 : if (!base)
3090 : ;
3091 3971324 : else if (DECL_P (base))
3092 1515330 : return is_global_var (base);
3093 2455994 : else if (TREE_CODE (base) == MEM_REF
3094 2455994 : || TREE_CODE (base) == TARGET_MEM_REF)
3095 2455896 : return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0), false);
3096 : return false;
3097 : }
3098 :
3099 : return true;
3100 : }
3101 :
3102 : bool
3103 829835 : ref_maybe_used_by_stmt_p (gimple *stmt, tree ref, bool tbaa_p)
3104 : {
3105 829835 : ao_ref r;
3106 829835 : ao_ref_init (&r, ref);
3107 829835 : return ref_maybe_used_by_stmt_p (stmt, &r, tbaa_p);
3108 : }
3109 :
3110 : /* If the call in statement CALL may clobber the memory reference REF
3111 : return true, otherwise return false. */
3112 :
3113 : bool
3114 342007845 : call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref, bool tbaa_p)
3115 : {
3116 342007845 : tree base;
3117 342007845 : tree callee;
3118 :
3119 : /* If the call is pure or const it cannot clobber anything. */
3120 342007845 : if (gimple_call_flags (call)
3121 342007845 : & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
3122 : return false;
3123 336682376 : if (gimple_call_internal_p (call))
3124 914252 : switch (auto fn = gimple_call_internal_fn (call))
3125 : {
3126 : /* Treat these internal calls like ECF_PURE for aliasing,
3127 : they don't write to any memory the program should care about.
3128 : They have important other side-effects, and read memory,
3129 : so can't be ECF_NOVOPS. */
3130 : case IFN_UBSAN_NULL:
3131 : case IFN_UBSAN_BOUNDS:
3132 : case IFN_UBSAN_VPTR:
3133 : case IFN_UBSAN_OBJECT_SIZE:
3134 : case IFN_UBSAN_PTR:
3135 : case IFN_ASAN_CHECK:
3136 : return false;
3137 7761 : case IFN_MASK_STORE:
3138 7761 : case IFN_LEN_STORE:
3139 7761 : case IFN_MASK_LEN_STORE:
3140 7761 : case IFN_MASK_STORE_LANES:
3141 7761 : case IFN_MASK_LEN_STORE_LANES:
3142 7761 : {
3143 7761 : tree rhs = gimple_call_arg (call,
3144 7761 : internal_fn_stored_value_index (fn));
3145 7761 : ao_ref lhs_ref;
3146 7761 : ao_ref_init_from_ptr_and_size (&lhs_ref, gimple_call_arg (call, 0),
3147 7761 : TYPE_SIZE_UNIT (TREE_TYPE (rhs)));
3148 : /* We cannot make this a known-size access since otherwise
3149 : we disambiguate against refs to decls that are smaller. */
3150 7761 : lhs_ref.size = -1;
3151 15522 : lhs_ref.ref_alias_set = lhs_ref.base_alias_set
3152 7761 : = tbaa_p ? get_deref_alias_set
3153 7268 : (TREE_TYPE (gimple_call_arg (call, 1))) : 0;
3154 7761 : return refs_may_alias_p_1 (ref, &lhs_ref, tbaa_p);
3155 : }
3156 : default:
3157 : break;
3158 : }
3159 :
3160 336105981 : callee = gimple_call_fndecl (call);
3161 :
3162 336105981 : if (callee != NULL_TREE && !ref->volatile_p)
3163 : {
3164 315938693 : struct cgraph_node *node = cgraph_node::get (callee);
3165 315938693 : if (node)
3166 : {
3167 315654715 : modref_summary *summary = get_modref_function_summary (node);
3168 315654715 : if (summary)
3169 : {
3170 45757932 : if (!modref_may_conflict (call, summary->stores, ref, tbaa_p)
3171 45757932 : && (!summary->writes_errno
3172 280749 : || !targetm.ref_may_alias_errno (ref)))
3173 : {
3174 4773640 : alias_stats.modref_clobber_no_alias++;
3175 4773640 : if (dump_file && (dump_flags & TDF_DETAILS))
3176 : {
3177 52 : fprintf (dump_file,
3178 : "ipa-modref: call stmt ");
3179 52 : print_gimple_stmt (dump_file, call, 0);
3180 52 : fprintf (dump_file,
3181 : "ipa-modref: call to %s does not clobber ",
3182 : node->dump_name ());
3183 52 : if (!ref->ref && ref->base)
3184 : {
3185 32 : fprintf (dump_file, "base: ");
3186 32 : print_generic_expr (dump_file, ref->base);
3187 : }
3188 20 : else if (ref->ref)
3189 : {
3190 20 : fprintf (dump_file, "ref: ");
3191 20 : print_generic_expr (dump_file, ref->ref);
3192 : }
3193 52 : fprintf (dump_file, " alias sets: %i->%i\n",
3194 : ao_ref_base_alias_set (ref),
3195 : ao_ref_alias_set (ref));
3196 : }
3197 : return false;
3198 : }
3199 40984292 : alias_stats.modref_clobber_may_alias++;
3200 : }
3201 : }
3202 : }
3203 :
3204 331332341 : base = ao_ref_base (ref);
3205 331332341 : if (!base)
3206 : return true;
3207 :
3208 331332341 : if (TREE_CODE (base) == SSA_NAME
3209 331330262 : || CONSTANT_CLASS_P (base))
3210 : return false;
3211 :
3212 : /* A call that is not without side-effects might involve volatile
3213 : accesses and thus conflicts with all other volatile accesses. */
3214 323161449 : if (ref->volatile_p)
3215 : return true;
3216 :
3217 : /* If the reference is based on a decl that is not aliased the call
3218 : cannot possibly clobber it. */
3219 321662076 : if (DECL_P (base)
3220 291353417 : && !may_be_aliased (base)
3221 : /* But local non-readonly statics can be modified through recursion
3222 : or the call may implement a threading barrier which we must
3223 : treat as may-def. */
3224 517958860 : && (TREE_READONLY (base)
3225 188795883 : || !is_global_var (base)))
3226 : return false;
3227 :
3228 : /* If the reference is based on a pointer that points to memory
3229 : that may not be written to then the call cannot possibly clobber it. */
3230 135584763 : if ((TREE_CODE (base) == MEM_REF
3231 135584763 : || TREE_CODE (base) == TARGET_MEM_REF)
3232 30308659 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
3233 165492381 : && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base, 0)))
3234 : return false;
3235 :
3236 135249428 : if (int res = check_fnspec (call, ref, true))
3237 : {
3238 109054188 : if (res == 1)
3239 : return true;
3240 : }
3241 : else
3242 : return false;
3243 :
3244 : /* Check if base is a global static variable that is not written
3245 : by the function. */
3246 103479800 : if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
3247 : {
3248 11022228 : struct cgraph_node *node = cgraph_node::get (callee);
3249 11022228 : bitmap written;
3250 11022228 : int id;
3251 :
3252 11022228 : if (node
3253 11021726 : && (id = ipa_reference_var_uid (base)) != -1
3254 4909172 : && (written = ipa_reference_get_written_global (node))
3255 11121476 : && !bitmap_bit_p (written, id))
3256 : return false;
3257 : }
3258 :
3259 : /* Check if the base variable is call-clobbered. */
3260 103397524 : if (DECL_P (base))
3261 80988139 : return pt_solution_includes (gimple_call_clobber_set (call), base);
3262 22409385 : else if ((TREE_CODE (base) == MEM_REF
3263 22409385 : || TREE_CODE (base) == TARGET_MEM_REF)
3264 22409385 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
3265 : {
3266 22074913 : const pt_solution *pt = ssa_name_pt_solution (TREE_OPERAND (base, 0));
3267 21352583 : if (!pt)
3268 : return true;
3269 :
3270 21253903 : return pt_solutions_intersect (gimple_call_clobber_set (call), pt);
3271 : }
3272 :
3273 : return true;
3274 : }
3275 :
3276 : /* If the call in statement CALL may clobber the memory reference REF
3277 : return true, otherwise return false. */
3278 :
3279 : bool
3280 383514 : call_may_clobber_ref_p (gcall *call, tree ref, bool tbaa_p)
3281 : {
3282 383514 : bool res;
3283 383514 : ao_ref r;
3284 383514 : ao_ref_init (&r, ref);
3285 383514 : res = call_may_clobber_ref_p_1 (call, &r, tbaa_p);
3286 383514 : if (res)
3287 44218 : ++alias_stats.call_may_clobber_ref_p_may_alias;
3288 : else
3289 339296 : ++alias_stats.call_may_clobber_ref_p_no_alias;
3290 383514 : return res;
3291 : }
3292 :
3293 :
3294 : /* If the statement STMT may clobber the memory reference REF return true,
3295 : otherwise return false. */
3296 :
3297 : bool
3298 2027180432 : stmt_may_clobber_ref_p_1 (gimple *stmt, ao_ref *ref, bool tbaa_p)
3299 : {
3300 2027180432 : if (is_gimple_call (stmt))
3301 : {
3302 347540127 : tree lhs = gimple_call_lhs (stmt);
3303 347540127 : if (lhs
3304 159385922 : && TREE_CODE (lhs) != SSA_NAME)
3305 : {
3306 60980122 : ao_ref r;
3307 60980122 : ao_ref_init (&r, lhs);
3308 60980122 : if (refs_may_alias_p_1 (ref, &r, tbaa_p))
3309 6021995 : return true;
3310 : }
3311 :
3312 341518132 : return call_may_clobber_ref_p_1 (as_a <gcall *> (stmt), ref, tbaa_p);
3313 : }
3314 1679640305 : else if (gimple_assign_single_p (stmt))
3315 : {
3316 1671196491 : tree lhs = gimple_assign_lhs (stmt);
3317 1671196491 : if (TREE_CODE (lhs) != SSA_NAME)
3318 : {
3319 1670262320 : ao_ref r;
3320 1670262320 : ao_ref_init (&r, lhs);
3321 1670262320 : return refs_may_alias_p_1 (ref, &r, tbaa_p);
3322 : }
3323 : }
3324 8443814 : else if (gimple_code (stmt) == GIMPLE_ASM)
3325 7254514 : return true;
3326 :
3327 : return false;
3328 : }
3329 :
3330 : bool
3331 4452985 : stmt_may_clobber_ref_p (gimple *stmt, tree ref, bool tbaa_p)
3332 : {
3333 4452985 : ao_ref r;
3334 4452985 : ao_ref_init (&r, ref);
3335 4452985 : return stmt_may_clobber_ref_p_1 (stmt, &r, tbaa_p);
3336 : }
3337 :
3338 : /* Return true if store1 and store2 described by corresponding tuples
3339 : <BASE, OFFSET, SIZE, MAX_SIZE> have the same size and store to the same
3340 : address. */
3341 :
3342 : static bool
3343 142306062 : same_addr_size_stores_p (tree base1, poly_int64 offset1, poly_int64 size1,
3344 : poly_int64 max_size1,
3345 : tree base2, poly_int64 offset2, poly_int64 size2,
3346 : poly_int64 max_size2)
3347 : {
3348 : /* Offsets need to be 0. */
3349 142306062 : if (maybe_ne (offset1, 0)
3350 142306062 : || maybe_ne (offset2, 0))
3351 : return false;
3352 :
3353 41548054 : bool base1_obj_p = SSA_VAR_P (base1);
3354 41548054 : bool base2_obj_p = SSA_VAR_P (base2);
3355 :
3356 : /* We need one object. */
3357 41548054 : if (base1_obj_p == base2_obj_p)
3358 : return false;
3359 5229367 : tree obj = base1_obj_p ? base1 : base2;
3360 :
3361 : /* And we need one MEM_REF. */
3362 5229367 : bool base1_memref_p = TREE_CODE (base1) == MEM_REF;
3363 5229367 : bool base2_memref_p = TREE_CODE (base2) == MEM_REF;
3364 5229367 : if (base1_memref_p == base2_memref_p)
3365 : return false;
3366 5127693 : tree memref = base1_memref_p ? base1 : base2;
3367 :
3368 : /* Sizes need to be valid. */
3369 5127693 : if (!known_size_p (max_size1)
3370 5103914 : || !known_size_p (max_size2)
3371 5103588 : || !known_size_p (size1)
3372 10231281 : || !known_size_p (size2))
3373 : return false;
3374 :
3375 : /* Max_size needs to match size. */
3376 5103588 : if (maybe_ne (max_size1, size1)
3377 5103588 : || maybe_ne (max_size2, size2))
3378 : return false;
3379 :
3380 : /* Sizes need to match. */
3381 5056558 : if (maybe_ne (size1, size2))
3382 : return false;
3383 :
3384 :
3385 : /* Check that memref is a store to pointer with singleton points-to info. */
3386 1306987 : if (!integer_zerop (TREE_OPERAND (memref, 1)))
3387 : return false;
3388 973424 : tree ptr = TREE_OPERAND (memref, 0);
3389 973424 : if (TREE_CODE (ptr) != SSA_NAME)
3390 : return false;
3391 973128 : const pt_solution *pt = ssa_name_pt_solution (ptr);
3392 904216 : unsigned int pt_uid;
3393 904216 : if (pt == NULL
3394 904216 : || !pt_solution_singleton_or_null_p (pt, &pt_uid))
3395 : return false;
3396 :
3397 : /* Be conservative with non-call exceptions when the address might
3398 : be NULL. */
3399 224814 : if (cfun->can_throw_non_call_exceptions && !ptr_nonnull_p (ptr))
3400 : return false;
3401 :
3402 : /* Check that ptr points relative to obj. */
3403 224808 : unsigned int obj_uid = DECL_PT_UID (obj);
3404 224808 : if (obj_uid != pt_uid)
3405 : return false;
3406 :
3407 : /* Check that the object size is the same as the store size. That ensures us
3408 : that ptr points to the start of obj. */
3409 34453 : return (DECL_SIZE (obj)
3410 34453 : && poly_int_tree_p (DECL_SIZE (obj))
3411 103208 : && known_eq (wi::to_poly_offset (DECL_SIZE (obj)), size1));
3412 : }
3413 :
3414 : /* Return true if REF is killed by an store described by
3415 : BASE, OFFSET, SIZE and MAX_SIZE. */
3416 :
3417 : static bool
3418 240845856 : store_kills_ref_p (tree base, poly_int64 offset, poly_int64 size,
3419 : poly_int64 max_size, ao_ref *ref)
3420 : {
3421 240845856 : poly_int64 ref_offset = ref->offset;
3422 : /* We can get MEM[symbol: sZ, index: D.8862_1] here,
3423 : so base == ref->base does not always hold. */
3424 240845856 : if (base != ref->base)
3425 : {
3426 : /* Try using points-to info. */
3427 142306062 : if (same_addr_size_stores_p (base, offset, size, max_size, ref->base,
3428 : ref->offset, ref->size, ref->max_size))
3429 : return true;
3430 :
3431 : /* If both base and ref->base are MEM_REFs, only compare the
3432 : first operand, and if the second operand isn't equal constant,
3433 : try to add the offsets into offset and ref_offset. */
3434 37035651 : if (TREE_CODE (base) == MEM_REF && TREE_CODE (ref->base) == MEM_REF
3435 169229387 : && TREE_OPERAND (base, 0) == TREE_OPERAND (ref->base, 0))
3436 : {
3437 20000212 : if (!tree_int_cst_equal (TREE_OPERAND (base, 1),
3438 20000212 : TREE_OPERAND (ref->base, 1)))
3439 : {
3440 7393002 : poly_offset_int off1 = mem_ref_offset (base);
3441 7393002 : off1 <<= LOG2_BITS_PER_UNIT;
3442 7393002 : off1 += offset;
3443 7393002 : poly_offset_int off2 = mem_ref_offset (ref->base);
3444 7393002 : off2 <<= LOG2_BITS_PER_UNIT;
3445 7393002 : off2 += ref_offset;
3446 7393002 : if (!off1.to_shwi (&offset) || !off2.to_shwi (&ref_offset))
3447 0 : size = -1;
3448 : }
3449 : }
3450 : else
3451 122305699 : size = -1;
3452 : }
3453 : /* For a must-alias check we need to be able to constrain
3454 : the access properly. */
3455 240845705 : return (known_eq (size, max_size)
3456 240845705 : && known_subrange_p (ref_offset, ref->max_size, offset, size));
3457 : }
3458 :
3459 : /* If STMT kills the memory reference REF return true, otherwise
3460 : return false. */
3461 :
3462 : bool
3463 294307789 : stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
3464 : {
3465 294307789 : if (!ao_ref_base (ref))
3466 : return false;
3467 :
3468 294307789 : if (gimple_has_lhs (stmt)
3469 254668623 : && TREE_CODE (gimple_get_lhs (stmt)) != SSA_NAME
3470 : /* The assignment is not necessarily carried out if it can throw
3471 : and we can catch it in the current function where we could inspect
3472 : the previous value. Similarly if the function can throw externally
3473 : and the ref does not die on the function return.
3474 : ??? We only need to care about the RHS throwing. For aggregate
3475 : assignments or similar calls and non-call exceptions the LHS
3476 : might throw as well.
3477 : ??? We also should care about possible longjmp, but since we
3478 : do not understand that longjmp is not using global memory we will
3479 : not consider a kill here since the function call will be considered
3480 : as possibly using REF. */
3481 248534837 : && !stmt_can_throw_internal (cfun, stmt)
3482 269303141 : && (!stmt_can_throw_external (cfun, stmt)
3483 3680336 : || !ref_may_alias_global_p (ref, false)))
3484 : {
3485 244269200 : tree lhs = gimple_get_lhs (stmt);
3486 : /* If LHS is literally a base of the access we are done. */
3487 244269200 : if (ref->ref)
3488 : {
3489 242829211 : tree base = ref->ref;
3490 242829211 : tree innermost_dropped_array_ref = NULL_TREE;
3491 242829211 : if (handled_component_p (base))
3492 : {
3493 151567286 : tree saved_lhs0 = NULL_TREE;
3494 268263731 : if (handled_component_p (lhs))
3495 : {
3496 116696445 : saved_lhs0 = TREE_OPERAND (lhs, 0);
3497 116696445 : TREE_OPERAND (lhs, 0) = integer_zero_node;
3498 : }
3499 256473679 : do
3500 : {
3501 : /* Just compare the outermost handled component, if
3502 : they are equal we have found a possible common
3503 : base. */
3504 256473679 : tree saved_base0 = TREE_OPERAND (base, 0);
3505 256473679 : TREE_OPERAND (base, 0) = integer_zero_node;
3506 256473679 : bool res = operand_equal_p (lhs, base, 0);
3507 256473679 : TREE_OPERAND (base, 0) = saved_base0;
3508 256473679 : if (res)
3509 : break;
3510 : /* Remember if we drop an array-ref that we need to
3511 : double-check not being at struct end. */
3512 241484184 : if (TREE_CODE (base) == ARRAY_REF
3513 241484184 : || TREE_CODE (base) == ARRAY_RANGE_REF)
3514 67117169 : innermost_dropped_array_ref = base;
3515 : /* Otherwise drop handled components of the access. */
3516 241484184 : base = saved_base0;
3517 : }
3518 378061975 : while (handled_component_p (base));
3519 151567286 : if (saved_lhs0)
3520 116696445 : TREE_OPERAND (lhs, 0) = saved_lhs0;
3521 : }
3522 : /* Finally check if the lhs has the same address and size as the
3523 : base candidate of the access. Watch out if we have dropped
3524 : an array-ref that might have flexible size, this means ref->ref
3525 : may be outside of the TYPE_SIZE of its base. */
3526 151567286 : if ((! innermost_dropped_array_ref
3527 66321928 : || ! array_ref_flexible_size_p (innermost_dropped_array_ref))
3528 298286956 : && (lhs == base
3529 229568098 : || (((TYPE_SIZE (TREE_TYPE (lhs))
3530 229568098 : == TYPE_SIZE (TREE_TYPE (base)))
3531 155690855 : || (TYPE_SIZE (TREE_TYPE (lhs))
3532 155690792 : && TYPE_SIZE (TREE_TYPE (base))
3533 155690695 : && operand_equal_p (TYPE_SIZE (TREE_TYPE (lhs)),
3534 155690695 : TYPE_SIZE (TREE_TYPE (base)),
3535 : 0)))
3536 73877243 : && operand_equal_p (lhs, base,
3537 : OEP_ADDRESS_OF
3538 : | OEP_MATCH_SIDE_EFFECTS))))
3539 : {
3540 3105467 : ++alias_stats.stmt_kills_ref_p_yes;
3541 5974254 : return true;
3542 : }
3543 : }
3544 :
3545 : /* Now look for non-literal equal bases with the restriction of
3546 : handling constant offset and size. */
3547 : /* For a must-alias check we need to be able to constrain
3548 : the access properly. */
3549 241163733 : if (!ref->max_size_known_p ())
3550 : {
3551 1310127 : ++alias_stats.stmt_kills_ref_p_no;
3552 1310127 : return false;
3553 : }
3554 239853606 : poly_int64 size, offset, max_size;
3555 239853606 : bool reverse;
3556 239853606 : tree base = get_ref_base_and_extent (lhs, &offset, &size, &max_size,
3557 : &reverse);
3558 239853606 : if (store_kills_ref_p (base, offset, size, max_size, ref))
3559 : {
3560 1558660 : ++alias_stats.stmt_kills_ref_p_yes;
3561 1558660 : return true;
3562 : }
3563 : }
3564 :
3565 288333535 : if (is_gimple_call (stmt))
3566 : {
3567 24117704 : tree callee = gimple_call_fndecl (stmt);
3568 24117704 : struct cgraph_node *node;
3569 24117704 : modref_summary *summary;
3570 :
3571 : /* Try to disambiguate using modref summary. Modref records a vector
3572 : of stores with known offsets relative to function parameters that must
3573 : happen every execution of function. Find if we have a matching
3574 : store and verify that function can not use the value. */
3575 24117704 : if (callee != NULL_TREE
3576 22929257 : && (node = cgraph_node::get (callee)) != NULL
3577 22885251 : && node->binds_to_current_def_p ()
3578 2521775 : && (summary = get_modref_function_summary (node)) != NULL
3579 1481358 : && summary->kills.length ()
3580 : /* Check that we can not trap while evaluating function
3581 : parameters. This check is overly conservative. */
3582 24221479 : && (!cfun->can_throw_non_call_exceptions
3583 0 : || (!stmt_can_throw_internal (cfun, stmt)
3584 0 : && (!stmt_can_throw_external (cfun, stmt)
3585 0 : || !ref_may_alias_global_p (ref, false)))))
3586 : {
3587 434936 : for (auto kill : summary->kills)
3588 : {
3589 132945 : ao_ref dref;
3590 :
3591 : /* We only can do useful compares if we know the access range
3592 : precisely. */
3593 132945 : if (!kill.get_ao_ref (as_a <gcall *> (stmt), &dref))
3594 24 : continue;
3595 132921 : if (store_kills_ref_p (ao_ref_base (&dref), dref.offset,
3596 : dref.size, dref.max_size, ref))
3597 : {
3598 : /* For store to be killed it needs to not be used
3599 : earlier. */
3600 9334 : if (ref_maybe_used_by_call_p_1 (as_a <gcall *> (stmt), ref,
3601 : true)
3602 9334 : || !dbg_cnt (ipa_mod_ref))
3603 : break;
3604 4004 : if (dump_file && (dump_flags & TDF_DETAILS))
3605 : {
3606 2 : fprintf (dump_file,
3607 : "ipa-modref: call stmt ");
3608 2 : print_gimple_stmt (dump_file, stmt, 0);
3609 2 : fprintf (dump_file,
3610 : "ipa-modref: call to %s kills ",
3611 : node->dump_name ());
3612 2 : print_generic_expr (dump_file, ref->base);
3613 2 : fprintf (dump_file, "\n");
3614 : }
3615 4004 : ++alias_stats.modref_kill_yes;
3616 4004 : return true;
3617 : }
3618 : }
3619 99771 : ++alias_stats.modref_kill_no;
3620 : }
3621 24113700 : if (callee != NULL_TREE
3622 24113700 : && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
3623 4907605 : switch (DECL_FUNCTION_CODE (callee))
3624 : {
3625 668281 : case BUILT_IN_FREE:
3626 668281 : {
3627 668281 : tree ptr = gimple_call_arg (stmt, 0);
3628 668281 : tree base = ao_ref_base (ref);
3629 668281 : if (base && TREE_CODE (base) == MEM_REF
3630 822520 : && TREE_OPERAND (base, 0) == ptr)
3631 : {
3632 28916 : ++alias_stats.stmt_kills_ref_p_yes;
3633 28916 : return true;
3634 : }
3635 : break;
3636 : }
3637 :
3638 1384423 : case BUILT_IN_MEMCPY:
3639 1384423 : case BUILT_IN_MEMPCPY:
3640 1384423 : case BUILT_IN_MEMMOVE:
3641 1384423 : case BUILT_IN_MEMSET:
3642 1384423 : case BUILT_IN_MEMCPY_CHK:
3643 1384423 : case BUILT_IN_MEMPCPY_CHK:
3644 1384423 : case BUILT_IN_MEMMOVE_CHK:
3645 1384423 : case BUILT_IN_MEMSET_CHK:
3646 1384423 : case BUILT_IN_STRNCPY:
3647 1384423 : case BUILT_IN_STPNCPY:
3648 1384423 : case BUILT_IN_CALLOC:
3649 1384423 : {
3650 : /* For a must-alias check we need to be able to constrain
3651 : the access properly. */
3652 1384423 : if (!ref->max_size_known_p ())
3653 : {
3654 68572 : ++alias_stats.stmt_kills_ref_p_no;
3655 530540 : return false;
3656 : }
3657 1315851 : tree dest;
3658 1315851 : tree len;
3659 :
3660 : /* In execution order a calloc call will never kill
3661 : anything. However, DSE will (ab)use this interface
3662 : to ask if a calloc call writes the same memory locations
3663 : as a later assignment, memset, etc. So handle calloc
3664 : in the expected way. */
3665 1315851 : if (DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC)
3666 : {
3667 1848 : tree arg0 = gimple_call_arg (stmt, 0);
3668 1848 : tree arg1 = gimple_call_arg (stmt, 1);
3669 1848 : if (TREE_CODE (arg0) != INTEGER_CST
3670 1706 : || TREE_CODE (arg1) != INTEGER_CST)
3671 : {
3672 174 : ++alias_stats.stmt_kills_ref_p_no;
3673 174 : return false;
3674 : }
3675 :
3676 1674 : dest = gimple_call_lhs (stmt);
3677 1674 : if (!dest)
3678 : {
3679 1 : ++alias_stats.stmt_kills_ref_p_no;
3680 1 : return false;
3681 : }
3682 1673 : len = fold_build2 (MULT_EXPR, TREE_TYPE (arg0), arg0, arg1);
3683 : }
3684 : else
3685 : {
3686 1314003 : dest = gimple_call_arg (stmt, 0);
3687 1314003 : len = gimple_call_arg (stmt, 2);
3688 : }
3689 1315676 : if (!poly_int_tree_p (len))
3690 : return false;
3691 859329 : ao_ref dref;
3692 859329 : ao_ref_init_from_ptr_and_size (&dref, dest, len);
3693 859329 : if (store_kills_ref_p (ao_ref_base (&dref), dref.offset,
3694 : dref.size, dref.max_size, ref))
3695 : {
3696 5446 : ++alias_stats.stmt_kills_ref_p_yes;
3697 5446 : return true;
3698 : }
3699 853883 : break;
3700 : }
3701 :
3702 5931 : case BUILT_IN_VA_END:
3703 5931 : {
3704 5931 : tree ptr = gimple_call_arg (stmt, 0);
3705 5931 : if (TREE_CODE (ptr) == ADDR_EXPR)
3706 : {
3707 5880 : tree base = ao_ref_base (ref);
3708 5880 : if (TREE_OPERAND (ptr, 0) == base)
3709 : {
3710 1417 : ++alias_stats.stmt_kills_ref_p_yes;
3711 1417 : return true;
3712 : }
3713 : }
3714 : break;
3715 : }
3716 :
3717 : default:;
3718 : }
3719 : }
3720 287768658 : ++alias_stats.stmt_kills_ref_p_no;
3721 287768658 : return false;
3722 : }
3723 :
3724 : bool
3725 0 : stmt_kills_ref_p (gimple *stmt, tree ref)
3726 : {
3727 0 : ao_ref r;
3728 0 : ao_ref_init (&r, ref);
3729 0 : return stmt_kills_ref_p (stmt, &r);
3730 : }
3731 :
3732 : /* Return whether REF can be subject to store data races. */
3733 :
3734 : bool
3735 164798 : ref_can_have_store_data_races (tree ref)
3736 : {
3737 : /* With -fallow-store-data-races do not care about them. */
3738 164798 : if (flag_store_data_races)
3739 : return false;
3740 :
3741 163846 : tree base = get_base_address (ref);
3742 163846 : if (auto_var_p (base)
3743 163846 : && ! may_be_aliased (base))
3744 : /* Automatic variables not aliased are not subject to
3745 : data races. */
3746 : return false;
3747 :
3748 : return true;
3749 : }
3750 :
3751 :
3752 : /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
3753 : TARGET or a statement clobbering the memory reference REF in which
3754 : case false is returned. The walk starts with VUSE, one argument of PHI. */
3755 :
3756 : static bool
3757 132605225 : maybe_skip_until (gimple *phi, tree &target, basic_block target_bb,
3758 : ao_ref *ref, tree vuse, bool tbaa_p, unsigned int &limit,
3759 : bitmap *visited,
3760 : void *(*translate)(ao_ref *, tree, void *, translate_flags *),
3761 : bool (*is_backedge)(edge, void *),
3762 : translate_flags disambiguate_only,
3763 : void *data)
3764 : {
3765 132605225 : basic_block bb = gimple_bb (phi);
3766 :
3767 132605225 : if (!*visited)
3768 : {
3769 24860353 : *visited = BITMAP_ALLOC (NULL);
3770 24860353 : bitmap_tree_view (*visited);
3771 : }
3772 :
3773 132605225 : bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
3774 :
3775 : /* Walk until we hit the target. */
3776 599558208 : while (vuse != target)
3777 : {
3778 419780155 : gimple *def_stmt = SSA_NAME_DEF_STMT (vuse);
3779 : /* If we are searching for the target VUSE by walking up to
3780 : TARGET_BB dominating the original PHI we are finished once
3781 : we reach a default def or a definition in a block dominating
3782 : that block. Update TARGET and return. */
3783 419780155 : if (!target
3784 419780155 : && (gimple_nop_p (def_stmt)
3785 70358870 : || dominated_by_p (CDI_DOMINATORS,
3786 70358870 : target_bb, gimple_bb (def_stmt))))
3787 : {
3788 19702250 : target = vuse;
3789 19702250 : return true;
3790 : }
3791 :
3792 : /* When we reach the original PHI we are done. TARGET must be
3793 : reached via other edges in the caller. */
3794 400077905 : if (def_stmt == phi)
3795 : return true;
3796 : /* Recurse for other PHI nodes. */
3797 369526969 : else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
3798 : {
3799 : /* An already visited PHI node ends the walk successfully. */
3800 45783372 : if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (phi))))
3801 : return true;
3802 40962457 : vuse = get_continuation_for_phi (phi, ref, tbaa_p, limit,
3803 : visited, translate, data, is_backedge,
3804 : disambiguate_only);
3805 40962457 : if (!vuse)
3806 : return false;
3807 36215247 : continue;
3808 : }
3809 323743597 : 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 323743597 : if ((int)limit <= 0)
3815 : return false;
3816 323708154 : --limit;
3817 323708154 : if (stmt_may_clobber_ref_p_1 (def_stmt, ref, tbaa_p))
3818 : {
3819 19166390 : translate_flags tf = disambiguate_only;
3820 19166390 : if (translate
3821 19166390 : && (*translate) (ref, vuse, data, &tf) == NULL)
3822 : ;
3823 : else
3824 15766001 : 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 307942153 : if (gimple_bb (def_stmt) != bb)
3830 : {
3831 133302240 : if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (vuse)))
3832 : return true;
3833 123492598 : bb = gimple_bb (def_stmt);
3834 : }
3835 632480269 : vuse = gimple_vuse (def_stmt);
3836 : }
3837 : return true;
3838 : }
3839 :
3840 : /* qsort comparator for a pair of int and bool. For same int sort
3841 : true before false. */
3842 :
3843 : static int
3844 925301909 : cmp_intpair (const void *a_, const void *b_)
3845 : {
3846 925301909 : auto a = (const std::pair<int, bool> *)a_;
3847 925301909 : auto b = (const std::pair<int, bool> *)b_;
3848 925301909 : if (a->first == b->first)
3849 47627897 : return (int)b->second - (int)a->second;
3850 877674012 : return a->first - b->first;
3851 : }
3852 :
3853 : /* Starting from a PHI node for the virtual operand of the memory reference
3854 : REF find a continuation virtual operand that allows to continue walking
3855 : statements dominating PHI skipping only statements that cannot possibly
3856 : clobber REF. Decrements LIMIT for each alias disambiguation done
3857 : and aborts the walk, returning NULL_TREE if it reaches zero.
3858 : Returns NULL_TREE if no suitable virtual operand can be found. */
3859 :
3860 : tree
3861 105031837 : get_continuation_for_phi (gphi *phi, ao_ref *ref, bool tbaa_p,
3862 : unsigned int &limit, bitmap *visited,
3863 : void *(*translate)(ao_ref *, tree, void *,
3864 : translate_flags *),
3865 : void *data,
3866 : bool (*is_backedge)(edge, void *),
3867 : translate_flags disambiguate_only)
3868 : {
3869 105031837 : unsigned nargs = gimple_phi_num_args (phi);
3870 :
3871 : /* Through a single-argument PHI we can simply look through. */
3872 105031837 : if (nargs == 1)
3873 4662372 : return PHI_ARG_DEF (phi, 0);
3874 :
3875 : /* For two or more arguments try to pairwise skip non-aliasing code
3876 : until we hit the phi argument definition that dominates the other one. */
3877 100369465 : basic_block phi_bb = gimple_bb (phi);
3878 100369465 : tree arg0, arg1;
3879 100369465 : unsigned i;
3880 :
3881 : /* Find a candidate for the virtual operand which definition
3882 : dominates those of all others. */
3883 : /* First look if any of the args themselves satisfy this. */
3884 186126144 : for (i = 0; i < nargs; ++i)
3885 : {
3886 161729229 : arg0 = PHI_ARG_DEF (phi, i);
3887 161729229 : if (SSA_NAME_IS_DEFAULT_DEF (arg0))
3888 : break;
3889 158395632 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (arg0));
3890 158395632 : if (def_bb != phi_bb
3891 158395632 : && dominated_by_p (CDI_DOMINATORS, phi_bb, def_bb))
3892 : break;
3893 85756679 : arg0 = NULL_TREE;
3894 : }
3895 : /* If not, look if we can reach such candidate by walking defs
3896 : until we hit the immediate dominator. maybe_skip_until will
3897 : do that for us. */
3898 100369465 : basic_block dom = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
3899 :
3900 : /* Sort the PHI arguments so we can quickly avoid walking duplicates.
3901 : Keep pairs of PHI arg and edge backedge state, sorting the backedge
3902 : case first which is the conservative walk kind in case we have
3903 : a duplicate PHI arg reachable both via a forward and a backward
3904 : edge. */
3905 100369465 : auto_vec<std::pair<int, bool>, 10> args;
3906 333868159 : for (i = 0; i < nargs; ++i)
3907 233498694 : args.safe_push (std::make_pair (SSA_NAME_VERSION (PHI_ARG_DEF (phi, i)),
3908 : (!is_backedge
3909 447166693 : || is_backedge
3910 213667999 : (gimple_phi_arg_edge (phi, i),
3911 : data))));
3912 100369465 : args.qsort (cmp_intpair);
3913 :
3914 : /* Then check against the (to be) found candidate. */
3915 292782864 : for (i = 0; i < nargs; ++i)
3916 : {
3917 212962053 : arg1 = ssa_name (args[i].first);
3918 212962053 : if (arg1 == arg0)
3919 : ;
3920 134429848 : else if (i > 0 && args[i].first == args[i-1].first)
3921 : /* Already walked paths can be skipped. */
3922 : ;
3923 132605225 : else if (! maybe_skip_until (phi, arg0, dom, ref, arg1, tbaa_p,
3924 : limit, visited, translate, is_backedge,
3925 : /* Do not valueize when walking over
3926 : backedges. */
3927 132605225 : !args[i].second
3928 : ? disambiguate_only : TR_DISAMBIGUATE,
3929 : data))
3930 : return NULL_TREE;
3931 : }
3932 :
3933 79820811 : return arg0;
3934 100369465 : }
3935 :
3936 : /* Based on the memory reference REF and its virtual use VUSE call
3937 : WALKER for each virtual use that is equivalent to VUSE, including VUSE
3938 : itself. That is, for each virtual use for which its defining statement
3939 : does not clobber REF.
3940 :
3941 : WALKER is called with REF, the current virtual use and DATA. If
3942 : WALKER returns non-NULL the walk stops and its result is returned.
3943 : At the end of a non-successful walk NULL is returned.
3944 :
3945 : TRANSLATE if non-NULL is called with a pointer to REF, the virtual
3946 : use which definition is a statement that may clobber REF and DATA.
3947 : If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
3948 : If TRANSLATE returns non-NULL the walk stops and its result is returned.
3949 : If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
3950 : to adjust REF and *DATA to make that valid.
3951 :
3952 : VALUEIZE if non-NULL is called with the next VUSE that is considered
3953 : and return value is substituted for that. This can be used to
3954 : implement optimistic value-numbering for example. Note that the
3955 : VUSE argument is assumed to be valueized already.
3956 :
3957 : LIMIT specifies the number of alias queries we are allowed to do,
3958 : the walk stops when it reaches zero and NULL is returned. LIMIT
3959 : is decremented by the number of alias queries (plus adjustments
3960 : done by the callbacks) upon return.
3961 :
3962 : TODO: Cache the vector of equivalent vuses per ref, vuse pair. */
3963 :
3964 : void *
3965 70127965 : walk_non_aliased_vuses (ao_ref *ref, tree vuse, bool tbaa_p,
3966 : void *(*walker)(ao_ref *, tree, void *),
3967 : void *(*translate)(ao_ref *, tree, void *,
3968 : translate_flags *),
3969 : bool (*is_backedge)(edge, void *),
3970 : tree (*valueize)(tree),
3971 : unsigned &limit, void *data)
3972 : {
3973 70127965 : bitmap visited = NULL;
3974 70127965 : void *res;
3975 :
3976 70127965 : timevar_push (TV_ALIAS_STMT_WALK);
3977 :
3978 1126430252 : do
3979 : {
3980 1126430252 : gimple *def_stmt;
3981 :
3982 : /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
3983 1126430252 : res = (*walker) (ref, vuse, data);
3984 : /* Abort walk. */
3985 1126430252 : if (res == (void *)-1)
3986 : {
3987 : res = NULL;
3988 : break;
3989 : }
3990 : /* Lookup succeeded. */
3991 1126430022 : else if (res != NULL)
3992 : break;
3993 :
3994 1117752922 : if (valueize)
3995 : {
3996 1099103122 : vuse = valueize (vuse);
3997 1099103122 : if (!vuse)
3998 : {
3999 : res = NULL;
4000 : break;
4001 : }
4002 : }
4003 1101187545 : def_stmt = SSA_NAME_DEF_STMT (vuse);
4004 1101187545 : if (gimple_nop_p (def_stmt))
4005 : break;
4006 1098479667 : else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
4007 60859655 : vuse = get_continuation_for_phi (phi, ref, tbaa_p, limit,
4008 : &visited, translate, data,
4009 : is_backedge);
4010 : else
4011 : {
4012 1037620012 : if ((int)limit <= 0)
4013 : {
4014 : res = NULL;
4015 : break;
4016 : }
4017 1037372319 : --limit;
4018 1037372319 : if (stmt_may_clobber_ref_p_1 (def_stmt, ref, tbaa_p))
4019 : {
4020 33306565 : if (!translate)
4021 : break;
4022 27984093 : translate_flags disambiguate_only = TR_TRANSLATE;
4023 27984093 : res = (*translate) (ref, vuse, data, &disambiguate_only);
4024 : /* Failed lookup and translation. */
4025 27984093 : if (res == (void *)-1)
4026 : {
4027 : res = NULL;
4028 : break;
4029 : }
4030 : /* Lookup succeeded. */
4031 6612991 : else if (res != NULL)
4032 : break;
4033 : /* Translation succeeded, continue walking. Regions skipped
4034 : so far were only verified to not clobber the original ref,
4035 : so forget about them. */
4036 5380449 : if (disambiguate_only == TR_TRANSLATE && visited)
4037 527191 : bitmap_clear (visited);
4038 : }
4039 1009446203 : vuse = gimple_vuse (def_stmt);
4040 : }
4041 : }
4042 1070305858 : while (vuse);
4043 :
4044 70127965 : if (visited)
4045 22344976 : BITMAP_FREE (visited);
4046 :
4047 70127965 : timevar_pop (TV_ALIAS_STMT_WALK);
4048 :
4049 70127965 : return res;
4050 : }
4051 :
4052 :
4053 : /* Based on the memory reference REF call WALKER for each vdef whose
4054 : defining statement may clobber REF, starting with VDEF. If REF
4055 : is NULL_TREE, each defining statement is visited.
4056 :
4057 : WALKER is called with REF, the current vdef and DATA. If WALKER
4058 : returns true the walk is stopped, otherwise it continues.
4059 :
4060 : If function entry is reached, FUNCTION_ENTRY_REACHED is set to true.
4061 : The pointer may be NULL and then we do not track this information.
4062 :
4063 : At PHI nodes walk_aliased_vdefs forks into one walk for each
4064 : PHI argument (but only one walk continues at merge points), the
4065 : return value is true if any of the walks was successful.
4066 :
4067 : The function returns the number of statements walked or -1 if
4068 : LIMIT stmts were walked and the walk was aborted at this point.
4069 : If LIMIT is zero the walk is not aborted. */
4070 :
4071 : static int
4072 298117264 : walk_aliased_vdefs_1 (ao_ref *ref, tree vdef,
4073 : bool (*walker)(ao_ref *, tree, void *), void *data,
4074 : bitmap *visited, unsigned int cnt,
4075 : bool *function_entry_reached, unsigned limit)
4076 : {
4077 1589094098 : do
4078 : {
4079 943605681 : gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
4080 :
4081 943605681 : if (*visited
4082 943605681 : && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
4083 168092742 : return cnt;
4084 :
4085 775512939 : if (gimple_nop_p (def_stmt))
4086 : {
4087 24931878 : if (function_entry_reached)
4088 3978642 : *function_entry_reached = true;
4089 24931878 : return cnt;
4090 : }
4091 750581061 : else if (gimple_code (def_stmt) == GIMPLE_PHI)
4092 : {
4093 89482675 : unsigned i;
4094 89482675 : if (!*visited)
4095 : {
4096 8256306 : *visited = BITMAP_ALLOC (NULL);
4097 8256306 : bitmap_tree_view (*visited);
4098 : }
4099 283153930 : for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
4100 : {
4101 198734473 : int res = walk_aliased_vdefs_1 (ref,
4102 : gimple_phi_arg_def (def_stmt, i),
4103 : walker, data, visited, cnt,
4104 : function_entry_reached, limit);
4105 198734473 : if (res == -1)
4106 : return -1;
4107 193671255 : cnt = res;
4108 : }
4109 84419457 : return cnt;
4110 : }
4111 :
4112 : /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
4113 661098386 : cnt++;
4114 661098386 : if (cnt == limit)
4115 : return -1;
4116 660953409 : if ((!ref
4117 583049969 : || stmt_may_clobber_ref_p_1 (def_stmt, ref))
4118 736939468 : && (*walker) (ref, vdef, data))
4119 15464992 : return cnt;
4120 :
4121 645488417 : vdef = gimple_vuse (def_stmt);
4122 645488417 : }
4123 : while (1);
4124 : }
4125 :
4126 : int
4127 99382791 : walk_aliased_vdefs (ao_ref *ref, tree vdef,
4128 : bool (*walker)(ao_ref *, tree, void *), void *data,
4129 : bitmap *visited,
4130 : bool *function_entry_reached, unsigned int limit)
4131 : {
4132 99382791 : bitmap local_visited = NULL;
4133 99382791 : int ret;
4134 :
4135 99382791 : timevar_push (TV_ALIAS_STMT_WALK);
4136 :
4137 99382791 : if (function_entry_reached)
4138 4996825 : *function_entry_reached = false;
4139 :
4140 126413088 : ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
4141 : visited ? visited : &local_visited, 0,
4142 : function_entry_reached, limit);
4143 99382791 : if (local_visited)
4144 8256306 : BITMAP_FREE (local_visited);
4145 :
4146 99382791 : timevar_pop (TV_ALIAS_STMT_WALK);
4147 :
4148 99382791 : return ret;
4149 : }
4150 :
4151 : /* Verify validity of the fnspec string.
4152 : See attr-fnspec.h for details. */
4153 :
4154 : void
4155 469515855 : attr_fnspec::verify ()
4156 : {
4157 469515855 : bool err = false;
4158 469515855 : if (!len)
4159 : return;
4160 :
4161 : /* Check return value specifier. */
4162 152647045 : if (len < return_desc_size)
4163 : err = true;
4164 152647045 : else if ((len - return_desc_size) % arg_desc_size)
4165 : err = true;
4166 152647045 : else if ((str[0] < '1' || str[0] > '4')
4167 152647045 : && str[0] != '.' && str[0] != 'm')
4168 0 : err = true;
4169 :
4170 152647045 : switch (str[1])
4171 : {
4172 : case ' ':
4173 : case 'p':
4174 : case 'P':
4175 : case 'c':
4176 : case 'C':
4177 : break;
4178 : default:
4179 : err = true;
4180 : }
4181 152647045 : if (err)
4182 0 : internal_error ("invalid fn spec attribute \"%s\"", str);
4183 :
4184 : /* Now check all parameters. */
4185 449700770 : for (unsigned int i = 0; arg_specified_p (i); i++)
4186 : {
4187 297053725 : unsigned int idx = arg_idx (i);
4188 297053725 : switch (str[idx])
4189 : {
4190 277208978 : case 'x':
4191 277208978 : case 'X':
4192 277208978 : case 'r':
4193 277208978 : case 'R':
4194 277208978 : case 'o':
4195 277208978 : case 'O':
4196 277208978 : case 'w':
4197 277208978 : case 'W':
4198 277208978 : case '.':
4199 277208978 : if ((str[idx + 1] >= '1' && str[idx + 1] <= '9')
4200 277208978 : || str[idx + 1] == 't')
4201 : {
4202 44476704 : if (str[idx] != 'r' && str[idx] != 'R'
4203 : && str[idx] != 'w' && str[idx] != 'W'
4204 : && str[idx] != 'o' && str[idx] != 'O')
4205 44476704 : err = true;
4206 44476704 : if (str[idx + 1] != 't'
4207 : /* Size specified is scalar, so it should be described
4208 : by ". " if specified at all. */
4209 44476704 : && (arg_specified_p (str[idx + 1] - '1')
4210 0 : && str[arg_idx (str[idx + 1] - '1')] != '.'))
4211 : err = true;
4212 : }
4213 232732274 : else if (str[idx + 1] != ' ')
4214 : err = true;
4215 : break;
4216 19844747 : default:
4217 19844747 : if (str[idx] < '1' || str[idx] > '9')
4218 : err = true;
4219 : }
4220 297053725 : if (err)
4221 0 : internal_error ("invalid fn spec attribute \"%s\" arg %i", str, i);
4222 : }
4223 : }
4224 :
4225 : /* Return true if TYPE1 and TYPE2 will always give the same answer
4226 : when compared with other types using same_type_for_tbaa. */
4227 :
4228 : static bool
4229 22833673 : types_equal_for_same_type_for_tbaa_p (tree type1, tree type2,
4230 : bool lto_streaming_safe)
4231 : {
4232 : /* We use same_type_for_tbaa_p to match types in the access path.
4233 : This check is overly conservative. */
4234 22833673 : type1 = TYPE_MAIN_VARIANT (type1);
4235 22833673 : type2 = TYPE_MAIN_VARIANT (type2);
4236 :
4237 22833673 : if (TYPE_STRUCTURAL_EQUALITY_P (type1)
4238 22833673 : != TYPE_STRUCTURAL_EQUALITY_P (type2))
4239 : return false;
4240 22555006 : if (TYPE_STRUCTURAL_EQUALITY_P (type1))
4241 : return true;
4242 :
4243 18814497 : if (lto_streaming_safe)
4244 90786 : return type1 == type2;
4245 : else
4246 18723711 : return TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2);
4247 : }
4248 :
4249 : /* Return true if TYPE1 and TYPE2 will always give the same answer
4250 : when compared with other types using same_type_for_tbaa. */
4251 :
4252 : bool
4253 22604395 : types_equal_for_same_type_for_tbaa_p (tree type1, tree type2)
4254 : {
4255 22604395 : return types_equal_for_same_type_for_tbaa_p (type1, type2,
4256 22604395 : lto_streaming_expected_p ());
4257 : }
4258 :
4259 : /* Compare REF1 and REF2 and return flags specifying their differences.
4260 : If LTO_STREAMING_SAFE is true do not use alias sets and canonical
4261 : types that are going to be recomputed.
4262 : If TBAA is true also compare TBAA metadata. */
4263 :
4264 : int
4265 132569 : ao_compare::compare_ao_refs (ao_ref *ref1, ao_ref *ref2,
4266 : bool lto_streaming_safe,
4267 : bool tbaa)
4268 : {
4269 132569 : if (TREE_THIS_VOLATILE (ref1->ref) != TREE_THIS_VOLATILE (ref2->ref))
4270 : return SEMANTICS;
4271 132557 : tree base1 = ao_ref_base (ref1);
4272 132557 : tree base2 = ao_ref_base (ref2);
4273 :
4274 132557 : if (!known_eq (ref1->offset, ref2->offset)
4275 132557 : || !known_eq (ref1->size, ref2->size)
4276 265114 : || !known_eq (ref1->max_size, ref2->max_size))
4277 : return SEMANTICS;
4278 :
4279 : /* For variable accesses we need to compare actual paths
4280 : to check that both refs are accessing same address and the access size. */
4281 132549 : if (!known_eq (ref1->size, ref1->max_size))
4282 : {
4283 3496 : if (!operand_equal_p (TYPE_SIZE (TREE_TYPE (ref1->ref)),
4284 3496 : TYPE_SIZE (TREE_TYPE (ref2->ref)), 0))
4285 : return SEMANTICS;
4286 3496 : tree r1 = ref1->ref;
4287 3496 : tree r2 = ref2->ref;
4288 :
4289 : /* Handle toplevel COMPONENT_REFs of bitfields.
4290 : Those are special since they are not allowed in
4291 : ADDR_EXPR. */
4292 3496 : if (TREE_CODE (r1) == COMPONENT_REF
4293 3496 : && DECL_BIT_FIELD (TREE_OPERAND (r1, 1)))
4294 : {
4295 0 : if (TREE_CODE (r2) != COMPONENT_REF
4296 0 : || !DECL_BIT_FIELD (TREE_OPERAND (r2, 1)))
4297 : return SEMANTICS;
4298 0 : tree field1 = TREE_OPERAND (r1, 1);
4299 0 : tree field2 = TREE_OPERAND (r2, 1);
4300 0 : if (!operand_equal_p (DECL_FIELD_OFFSET (field1),
4301 0 : DECL_FIELD_OFFSET (field2), 0)
4302 0 : || !operand_equal_p (DECL_FIELD_BIT_OFFSET (field1),
4303 0 : DECL_FIELD_BIT_OFFSET (field2), 0)
4304 0 : || !operand_equal_p (DECL_SIZE (field1), DECL_SIZE (field2), 0)
4305 0 : || !types_compatible_p (TREE_TYPE (r1),
4306 0 : TREE_TYPE (r2)))
4307 : return SEMANTICS;
4308 0 : r1 = TREE_OPERAND (r1, 0);
4309 0 : r2 = TREE_OPERAND (r2, 0);
4310 : }
4311 3496 : else if (TREE_CODE (r2) == COMPONENT_REF
4312 3496 : && DECL_BIT_FIELD (TREE_OPERAND (r2, 1)))
4313 : return SEMANTICS;
4314 :
4315 : /* Similarly for bit field refs. */
4316 3496 : if (TREE_CODE (r1) == BIT_FIELD_REF)
4317 : {
4318 0 : if (TREE_CODE (r2) != BIT_FIELD_REF
4319 0 : || !operand_equal_p (TREE_OPERAND (r1, 1),
4320 0 : TREE_OPERAND (r2, 1), 0)
4321 0 : || !operand_equal_p (TREE_OPERAND (r1, 2),
4322 0 : TREE_OPERAND (r2, 2), 0)
4323 0 : || !types_compatible_p (TREE_TYPE (r1),
4324 0 : TREE_TYPE (r2)))
4325 : return SEMANTICS;
4326 0 : r1 = TREE_OPERAND (r1, 0);
4327 0 : r2 = TREE_OPERAND (r2, 0);
4328 : }
4329 3496 : else if (TREE_CODE (r2) == BIT_FIELD_REF)
4330 : return SEMANTICS;
4331 :
4332 : /* Now we can compare the address of actual memory access. */
4333 3496 : if (!operand_equal_p (r1, r2, OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS))
4334 : return SEMANTICS;
4335 : }
4336 : /* For constant accesses we get more matches by comparing offset only. */
4337 129053 : else if (!operand_equal_p (base1, base2,
4338 : OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS))
4339 : return SEMANTICS;
4340 :
4341 : /* We can't simply use get_object_alignment_1 on the full
4342 : reference as for accesses with variable indexes this reports
4343 : too conservative alignment. */
4344 132346 : unsigned int align1, align2;
4345 132346 : unsigned HOST_WIDE_INT bitpos1, bitpos2;
4346 132346 : bool known1 = get_object_alignment_1 (base1, &align1, &bitpos1);
4347 132346 : bool known2 = get_object_alignment_1 (base2, &align2, &bitpos2);
4348 : /* ??? For MEMREF get_object_alignment_1 determines aligned from
4349 : TYPE_ALIGN but still returns false. This seem to contradict
4350 : its description. So compare even if alignment is unknown. */
4351 132346 : if (known1 != known2
4352 132346 : || (bitpos1 != bitpos2 || align1 != align2))
4353 : return SEMANTICS;
4354 :
4355 : /* Now we know that accesses are semantically same. */
4356 132131 : int flags = 0;
4357 :
4358 : /* ao_ref_base strips inner MEM_REF [&decl], recover from that here. */
4359 132131 : tree rbase1 = ref1->ref;
4360 132131 : if (rbase1)
4361 236751 : while (handled_component_p (rbase1))
4362 104620 : rbase1 = TREE_OPERAND (rbase1, 0);
4363 132131 : tree rbase2 = ref2->ref;
4364 236727 : while (handled_component_p (rbase2))
4365 104596 : rbase2 = TREE_OPERAND (rbase2, 0);
4366 :
4367 : /* MEM_REFs and TARGET_MEM_REFs record dependence cliques which are used to
4368 : implement restrict pointers. MR_DEPENDENCE_CLIQUE 0 means no information.
4369 : Otherwise we need to match bases and cliques. */
4370 132131 : if ((((TREE_CODE (rbase1) == MEM_REF || TREE_CODE (rbase1) == TARGET_MEM_REF)
4371 85289 : && MR_DEPENDENCE_CLIQUE (rbase1))
4372 108690 : || ((TREE_CODE (rbase2) == MEM_REF || TREE_CODE (rbase2) == TARGET_MEM_REF)
4373 61848 : && MR_DEPENDENCE_CLIQUE (rbase2)))
4374 155572 : && (TREE_CODE (rbase1) != TREE_CODE (rbase2)
4375 23441 : || MR_DEPENDENCE_CLIQUE (rbase1) != MR_DEPENDENCE_CLIQUE (rbase2)
4376 23361 : || (MR_DEPENDENCE_BASE (rbase1) != MR_DEPENDENCE_BASE (rbase2))))
4377 : flags |= DEPENDENCE_CLIQUE;
4378 :
4379 132131 : if (!tbaa)
4380 : return flags;
4381 :
4382 : /* Alias sets are not stable across LTO sreaming; be conservative here
4383 : and compare types the alias sets are ultimately based on. */
4384 132074 : if (lto_streaming_safe)
4385 : {
4386 3002 : tree t1 = ao_ref_alias_ptr_type (ref1);
4387 3002 : tree t2 = ao_ref_alias_ptr_type (ref2);
4388 3002 : if (!alias_ptr_types_compatible_p (t1, t2))
4389 13 : flags |= REF_ALIAS_SET;
4390 :
4391 3002 : t1 = ao_ref_base_alias_ptr_type (ref1);
4392 3002 : t2 = ao_ref_base_alias_ptr_type (ref2);
4393 3002 : if (!alias_ptr_types_compatible_p (t1, t2))
4394 22 : flags |= BASE_ALIAS_SET;
4395 : }
4396 : else
4397 : {
4398 129072 : if (ao_ref_alias_set (ref1) != ao_ref_alias_set (ref2))
4399 0 : flags |= REF_ALIAS_SET;
4400 129072 : if (ao_ref_base_alias_set (ref1) != ao_ref_base_alias_set (ref2))
4401 0 : flags |= BASE_ALIAS_SET;
4402 : }
4403 :
4404 : /* Access path is used only on non-view-converted references. */
4405 132074 : bool view_converted = view_converted_memref_p (rbase1);
4406 132074 : if (view_converted_memref_p (rbase2) != view_converted)
4407 0 : return flags | ACCESS_PATH;
4408 132074 : else if (view_converted)
4409 : return flags;
4410 :
4411 :
4412 : /* Find start of access paths and look for trailing arrays. */
4413 127073 : tree c1 = ref1->ref, c2 = ref2->ref;
4414 127073 : tree end_struct_ref1 = NULL, end_struct_ref2 = NULL;
4415 127073 : int nskipped1 = 0, nskipped2 = 0;
4416 127073 : int i = 0;
4417 :
4418 231567 : for (tree p1 = ref1->ref; handled_component_p (p1); p1 = TREE_OPERAND (p1, 0))
4419 : {
4420 104494 : if (component_ref_to_zero_sized_trailing_array_p (p1))
4421 133 : end_struct_ref1 = p1;
4422 104494 : if (ends_tbaa_access_path_p (p1))
4423 5190 : c1 = p1, nskipped1 = i;
4424 104494 : i++;
4425 : }
4426 127073 : i = 0;
4427 231543 : for (tree p2 = ref2->ref; handled_component_p (p2); p2 = TREE_OPERAND (p2, 0))
4428 : {
4429 104470 : if (component_ref_to_zero_sized_trailing_array_p (p2))
4430 140 : end_struct_ref2 = p2;
4431 104470 : if (ends_tbaa_access_path_p (p2))
4432 5190 : c2 = p2, nskipped2 = i;
4433 104470 : i++;
4434 : }
4435 :
4436 : /* For variable accesses we can not rely on offset match below.
4437 : We know that paths are struturally same, so only check that
4438 : starts of TBAA paths did not diverge. */
4439 127073 : if (!known_eq (ref1->size, ref1->max_size)
4440 127073 : && nskipped1 != nskipped2)
4441 0 : return flags | ACCESS_PATH;
4442 :
4443 : /* Information about trailing refs is used by
4444 : aliasing_component_refs_p that is applied only if paths
4445 : has handled components.. */
4446 127073 : if (!handled_component_p (c1) && !handled_component_p (c2))
4447 : ;
4448 62263 : else if ((end_struct_ref1 != NULL) != (end_struct_ref2 != NULL))
4449 27 : return flags | ACCESS_PATH;
4450 127046 : if (end_struct_ref1
4451 127169 : && same_type_for_tbaa (TREE_TYPE (end_struct_ref1),
4452 123 : TREE_TYPE (end_struct_ref2)) != 1)
4453 3 : return flags | ACCESS_PATH;
4454 :
4455 : /* Now compare all handled components of the access path.
4456 : We have three oracles that cares about access paths:
4457 : - aliasing_component_refs_p
4458 : - nonoverlapping_refs_since_match_p
4459 : - nonoverlapping_component_refs_p
4460 : We need to match things these oracles compare.
4461 :
4462 : It is only necessary to check types for compatibility
4463 : and offsets. Rest of what oracles compares are actual
4464 : addresses. Those are already known to be same:
4465 : - for constant accesses we check offsets
4466 : - for variable accesses we already matched
4467 : the path lexically with operand_equal_p. */
4468 331537 : while (true)
4469 : {
4470 229290 : bool comp1 = handled_component_p (c1);
4471 229290 : bool comp2 = handled_component_p (c2);
4472 :
4473 229290 : if (comp1 != comp2)
4474 12 : return flags | ACCESS_PATH;
4475 229278 : if (!comp1)
4476 : break;
4477 :
4478 102359 : if (TREE_CODE (c1) != TREE_CODE (c2))
4479 0 : return flags | ACCESS_PATH;
4480 :
4481 : /* aliasing_component_refs_p attempts to find type match within
4482 : the paths. For that reason both types needs to be equal
4483 : with respect to same_type_for_tbaa_p. */
4484 102359 : if (!types_equal_for_same_type_for_tbaa_p (TREE_TYPE (c1),
4485 102359 : TREE_TYPE (c2),
4486 : lto_streaming_safe))
4487 112 : return flags | ACCESS_PATH;
4488 204494 : if (component_ref_to_zero_sized_trailing_array_p (c1)
4489 102247 : != component_ref_to_zero_sized_trailing_array_p (c2))
4490 0 : return flags | ACCESS_PATH;
4491 :
4492 : /* aliasing_matching_component_refs_p compares
4493 : offsets within the path. Other properties are ignored.
4494 : Do not bother to verify offsets in variable accesses. Here we
4495 : already compared them by operand_equal_p so they are
4496 : structurally same. */
4497 102247 : if (!known_eq (ref1->size, ref1->max_size))
4498 : {
4499 4216 : poly_int64 offadj1, sztmc1, msztmc1;
4500 4216 : bool reverse1;
4501 4216 : get_ref_base_and_extent (c1, &offadj1, &sztmc1, &msztmc1, &reverse1);
4502 4216 : poly_int64 offadj2, sztmc2, msztmc2;
4503 4216 : bool reverse2;
4504 4216 : get_ref_base_and_extent (c2, &offadj2, &sztmc2, &msztmc2, &reverse2);
4505 4216 : if (!known_eq (offadj1, offadj2))
4506 0 : return flags | ACCESS_PATH;
4507 : }
4508 102247 : c1 = TREE_OPERAND (c1, 0);
4509 102247 : c2 = TREE_OPERAND (c2, 0);
4510 102247 : }
4511 : /* Finally test the access type. */
4512 126919 : if (!types_equal_for_same_type_for_tbaa_p (TREE_TYPE (c1),
4513 126919 : TREE_TYPE (c2),
4514 : lto_streaming_safe))
4515 1749 : return flags | ACCESS_PATH;
4516 : return flags;
4517 : }
4518 :
4519 : /* Hash REF to HSTATE. If LTO_STREAMING_SAFE do not use alias sets
4520 : and canonical types. */
4521 : void
4522 8545143 : ao_compare::hash_ao_ref (ao_ref *ref, bool lto_streaming_safe, bool tbaa,
4523 : inchash::hash &hstate)
4524 : {
4525 8545143 : tree base = ao_ref_base (ref);
4526 8545143 : tree tbase = base;
4527 :
4528 8545143 : if (!known_eq (ref->size, ref->max_size))
4529 : {
4530 429702 : tree r = ref->ref;
4531 429702 : if (TREE_CODE (r) == COMPONENT_REF
4532 429702 : && DECL_BIT_FIELD (TREE_OPERAND (r, 1)))
4533 : {
4534 1715 : tree field = TREE_OPERAND (r, 1);
4535 1715 : hash_operand (DECL_FIELD_OFFSET (field), hstate, 0);
4536 1715 : hash_operand (DECL_FIELD_BIT_OFFSET (field), hstate, 0);
4537 1715 : hash_operand (DECL_SIZE (field), hstate, 0);
4538 1715 : r = TREE_OPERAND (r, 0);
4539 : }
4540 429702 : if (TREE_CODE (r) == BIT_FIELD_REF)
4541 : {
4542 1704 : hash_operand (TREE_OPERAND (r, 1), hstate, 0);
4543 1704 : hash_operand (TREE_OPERAND (r, 2), hstate, 0);
4544 1704 : r = TREE_OPERAND (r, 0);
4545 : }
4546 429702 : hash_operand (TYPE_SIZE (TREE_TYPE (ref->ref)), hstate, 0);
4547 429702 : hash_operand (r, hstate, OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS);
4548 : }
4549 : else
4550 : {
4551 8115441 : hash_operand (tbase, hstate, OEP_ADDRESS_OF | OEP_MATCH_SIDE_EFFECTS);
4552 8115441 : hstate.add_poly_int (ref->offset);
4553 8115441 : hstate.add_poly_int (ref->size);
4554 8115441 : hstate.add_poly_int (ref->max_size);
4555 : }
4556 8545143 : if (!lto_streaming_safe && tbaa)
4557 : {
4558 8200145 : hstate.add_int (ao_ref_alias_set (ref));
4559 8200145 : hstate.add_int (ao_ref_base_alias_set (ref));
4560 : }
4561 8545143 : }
|