1 /* Alias analysis for trees.
2 Copyright (C) 2004-2014 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "timevar.h" /* for TV_ALIAS_STMT_WALK */
30 #include "langhooks.h"
33 #include "tree-pretty-print.h"
35 #include "tree-ssa-alias.h"
36 #include "internal-fn.h"
38 #include "gimple-expr.h"
41 #include "gimple-ssa.h"
42 #include "stringpool.h"
43 #include "tree-ssanames.h"
46 #include "tree-inline.h"
48 #include "alloc-pool.h"
49 #include "tree-ssa-alias.h"
52 #include "ipa-reference.h"
54 /* Broad overview of how alias analysis on gimple works:
56 Statements clobbering or using memory are linked through the
57 virtual operand factored use-def chain. The virtual operand
58 is unique per function, its symbol is accessible via gimple_vop (cfun).
59 Virtual operands are used for efficiently walking memory statements
60 in the gimple IL and are useful for things like value-numbering as
61 a generation count for memory references.
63 SSA_NAME pointers may have associated points-to information
64 accessible via the SSA_NAME_PTR_INFO macro. Flow-insensitive
65 points-to information is (re-)computed by the TODO_rebuild_alias
66 pass manager todo. Points-to information is also used for more
67 precise tracking of call-clobbered and call-used variables and
68 related disambiguations.
70 This file contains functions for disambiguating memory references,
71 the so called alias-oracle and tools for walking of the gimple IL.
73 The main alias-oracle entry-points are
75 bool stmt_may_clobber_ref_p (gimple, tree)
77 This function queries if a statement may invalidate (parts of)
78 the memory designated by the reference tree argument.
80 bool ref_maybe_used_by_stmt_p (gimple, tree)
82 This function queries if a statement may need (parts of) the
83 memory designated by the reference tree argument.
85 There are variants of these functions that only handle the call
86 part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
87 Note that these do not disambiguate against a possible call lhs.
89 bool refs_may_alias_p (tree, tree)
91 This function tries to disambiguate two reference trees.
93 bool ptr_deref_may_alias_global_p (tree)
95 This function queries if dereferencing a pointer variable may
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.c. */
103 /* Query statistics for the different low-level disambiguators.
104 A high-level query may trigger multiple of them. */
107 unsigned HOST_WIDE_INT refs_may_alias_p_may_alias
;
108 unsigned HOST_WIDE_INT refs_may_alias_p_no_alias
;
109 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias
;
110 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias
;
111 unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias
;
112 unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias
;
116 dump_alias_stats (FILE *s
)
118 fprintf (s
, "\nAlias oracle query stats:\n");
119 fprintf (s
, " refs_may_alias_p: "
120 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
121 HOST_WIDE_INT_PRINT_DEC
" queries\n",
122 alias_stats
.refs_may_alias_p_no_alias
,
123 alias_stats
.refs_may_alias_p_no_alias
124 + alias_stats
.refs_may_alias_p_may_alias
);
125 fprintf (s
, " ref_maybe_used_by_call_p: "
126 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
127 HOST_WIDE_INT_PRINT_DEC
" queries\n",
128 alias_stats
.ref_maybe_used_by_call_p_no_alias
,
129 alias_stats
.refs_may_alias_p_no_alias
130 + alias_stats
.ref_maybe_used_by_call_p_may_alias
);
131 fprintf (s
, " call_may_clobber_ref_p: "
132 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
133 HOST_WIDE_INT_PRINT_DEC
" queries\n",
134 alias_stats
.call_may_clobber_ref_p_no_alias
,
135 alias_stats
.call_may_clobber_ref_p_no_alias
136 + alias_stats
.call_may_clobber_ref_p_may_alias
);
140 /* Return true, if dereferencing PTR may alias with a global variable. */
143 ptr_deref_may_alias_global_p (tree ptr
)
145 struct ptr_info_def
*pi
;
147 /* If we end up with a pointer constant here that may point
149 if (TREE_CODE (ptr
) != SSA_NAME
)
152 pi
= SSA_NAME_PTR_INFO (ptr
);
154 /* If we do not have points-to information for this variable,
159 /* ??? This does not use TBAA to prune globals ptr may not access. */
160 return pt_solution_includes_global (&pi
->pt
);
163 /* Return true if dereferencing PTR may alias DECL.
164 The caller is responsible for applying TBAA to see if PTR
165 may access DECL at all. */
168 ptr_deref_may_alias_decl_p (tree ptr
, tree decl
)
170 struct ptr_info_def
*pi
;
172 /* Conversions are irrelevant for points-to information and
173 data-dependence analysis can feed us those. */
176 /* Anything we do not explicilty handle aliases. */
177 if ((TREE_CODE (ptr
) != SSA_NAME
178 && TREE_CODE (ptr
) != ADDR_EXPR
179 && TREE_CODE (ptr
) != POINTER_PLUS_EXPR
)
180 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
181 || (TREE_CODE (decl
) != VAR_DECL
182 && TREE_CODE (decl
) != PARM_DECL
183 && TREE_CODE (decl
) != RESULT_DECL
))
186 /* Disregard pointer offsetting. */
187 if (TREE_CODE (ptr
) == POINTER_PLUS_EXPR
)
191 ptr
= TREE_OPERAND (ptr
, 0);
193 while (TREE_CODE (ptr
) == POINTER_PLUS_EXPR
);
194 return ptr_deref_may_alias_decl_p (ptr
, decl
);
197 /* ADDR_EXPR pointers either just offset another pointer or directly
198 specify the pointed-to set. */
199 if (TREE_CODE (ptr
) == ADDR_EXPR
)
201 tree base
= get_base_address (TREE_OPERAND (ptr
, 0));
203 && (TREE_CODE (base
) == MEM_REF
204 || TREE_CODE (base
) == TARGET_MEM_REF
))
205 ptr
= TREE_OPERAND (base
, 0);
210 && CONSTANT_CLASS_P (base
))
216 /* Non-aliased variables can not be pointed to. */
217 if (!may_be_aliased (decl
))
220 /* If we do not have useful points-to information for this pointer
221 we cannot disambiguate anything else. */
222 pi
= SSA_NAME_PTR_INFO (ptr
);
226 return pt_solution_includes (&pi
->pt
, decl
);
229 /* Return true if dereferenced PTR1 and PTR2 may alias.
230 The caller is responsible for applying TBAA to see if accesses
231 through PTR1 and PTR2 may conflict at all. */
234 ptr_derefs_may_alias_p (tree ptr1
, tree ptr2
)
236 struct ptr_info_def
*pi1
, *pi2
;
238 /* Conversions are irrelevant for points-to information and
239 data-dependence analysis can feed us those. */
243 /* Disregard pointer offsetting. */
244 if (TREE_CODE (ptr1
) == POINTER_PLUS_EXPR
)
248 ptr1
= TREE_OPERAND (ptr1
, 0);
250 while (TREE_CODE (ptr1
) == POINTER_PLUS_EXPR
);
251 return ptr_derefs_may_alias_p (ptr1
, ptr2
);
253 if (TREE_CODE (ptr2
) == POINTER_PLUS_EXPR
)
257 ptr2
= TREE_OPERAND (ptr2
, 0);
259 while (TREE_CODE (ptr2
) == POINTER_PLUS_EXPR
);
260 return ptr_derefs_may_alias_p (ptr1
, ptr2
);
263 /* ADDR_EXPR pointers either just offset another pointer or directly
264 specify the pointed-to set. */
265 if (TREE_CODE (ptr1
) == ADDR_EXPR
)
267 tree base
= get_base_address (TREE_OPERAND (ptr1
, 0));
269 && (TREE_CODE (base
) == MEM_REF
270 || TREE_CODE (base
) == TARGET_MEM_REF
))
271 return ptr_derefs_may_alias_p (TREE_OPERAND (base
, 0), ptr2
);
274 return ptr_deref_may_alias_decl_p (ptr2
, base
);
278 if (TREE_CODE (ptr2
) == ADDR_EXPR
)
280 tree base
= get_base_address (TREE_OPERAND (ptr2
, 0));
282 && (TREE_CODE (base
) == MEM_REF
283 || TREE_CODE (base
) == TARGET_MEM_REF
))
284 return ptr_derefs_may_alias_p (ptr1
, TREE_OPERAND (base
, 0));
287 return ptr_deref_may_alias_decl_p (ptr1
, base
);
292 /* From here we require SSA name pointers. Anything else aliases. */
293 if (TREE_CODE (ptr1
) != SSA_NAME
294 || TREE_CODE (ptr2
) != SSA_NAME
295 || !POINTER_TYPE_P (TREE_TYPE (ptr1
))
296 || !POINTER_TYPE_P (TREE_TYPE (ptr2
)))
299 /* We may end up with two empty points-to solutions for two same pointers.
300 In this case we still want to say both pointers alias, so shortcut
305 /* If we do not have useful points-to information for either pointer
306 we cannot disambiguate anything else. */
307 pi1
= SSA_NAME_PTR_INFO (ptr1
);
308 pi2
= SSA_NAME_PTR_INFO (ptr2
);
312 /* ??? This does not use TBAA to prune decls from the intersection
313 that not both pointers may access. */
314 return pt_solutions_intersect (&pi1
->pt
, &pi2
->pt
);
317 /* Return true if dereferencing PTR may alias *REF.
318 The caller is responsible for applying TBAA to see if PTR
319 may access *REF at all. */
322 ptr_deref_may_alias_ref_p_1 (tree ptr
, ao_ref
*ref
)
324 tree base
= ao_ref_base (ref
);
326 if (TREE_CODE (base
) == MEM_REF
327 || TREE_CODE (base
) == TARGET_MEM_REF
)
328 return ptr_derefs_may_alias_p (ptr
, TREE_OPERAND (base
, 0));
329 else if (DECL_P (base
))
330 return ptr_deref_may_alias_decl_p (ptr
, base
);
335 /* Return true whether REF may refer to global memory. */
338 ref_may_alias_global_p (tree ref
)
340 tree base
= get_base_address (ref
);
342 return is_global_var (base
);
343 else if (TREE_CODE (base
) == MEM_REF
344 || TREE_CODE (base
) == TARGET_MEM_REF
)
345 return ptr_deref_may_alias_global_p (TREE_OPERAND (base
, 0));
349 /* Return true whether STMT may clobber global memory. */
352 stmt_may_clobber_global_p (gimple stmt
)
356 if (!gimple_vdef (stmt
))
359 /* ??? We can ask the oracle whether an artificial pointer
360 dereference with a pointer with points-to information covering
361 all global memory (what about non-address taken memory?) maybe
362 clobbered by this call. As there is at the moment no convenient
363 way of doing that without generating garbage do some manual
365 ??? We could make a NULL ao_ref argument to the various
366 predicates special, meaning any global memory. */
368 switch (gimple_code (stmt
))
371 lhs
= gimple_assign_lhs (stmt
);
372 return (TREE_CODE (lhs
) != SSA_NAME
373 && ref_may_alias_global_p (lhs
));
382 /* Dump alias information on FILE. */
385 dump_alias_info (FILE *file
)
389 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
392 fprintf (file
, "\n\nAlias information for %s\n\n", funcname
);
394 fprintf (file
, "Aliased symbols\n\n");
396 FOR_EACH_LOCAL_DECL (cfun
, i
, var
)
398 if (may_be_aliased (var
))
399 dump_variable (file
, var
);
402 fprintf (file
, "\nCall clobber information\n");
404 fprintf (file
, "\nESCAPED");
405 dump_points_to_solution (file
, &cfun
->gimple_df
->escaped
);
407 fprintf (file
, "\n\nFlow-insensitive points-to information\n\n");
409 for (i
= 1; i
< num_ssa_names
; i
++)
411 tree ptr
= ssa_name (i
);
412 struct ptr_info_def
*pi
;
415 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
416 || SSA_NAME_IN_FREE_LIST (ptr
))
419 pi
= SSA_NAME_PTR_INFO (ptr
);
421 dump_points_to_info_for (file
, ptr
);
424 fprintf (file
, "\n");
428 /* Dump alias information on stderr. */
431 debug_alias_info (void)
433 dump_alias_info (stderr
);
437 /* Dump the points-to set *PT into FILE. */
440 dump_points_to_solution (FILE *file
, struct pt_solution
*pt
)
443 fprintf (file
, ", points-to anything");
446 fprintf (file
, ", points-to non-local");
449 fprintf (file
, ", points-to escaped");
452 fprintf (file
, ", points-to unit escaped");
455 fprintf (file
, ", points-to NULL");
459 fprintf (file
, ", points-to vars: ");
460 dump_decl_set (file
, pt
->vars
);
461 if (pt
->vars_contains_nonlocal
462 && pt
->vars_contains_escaped_heap
)
463 fprintf (file
, " (nonlocal, escaped heap)");
464 else if (pt
->vars_contains_nonlocal
465 && pt
->vars_contains_escaped
)
466 fprintf (file
, " (nonlocal, escaped)");
467 else if (pt
->vars_contains_nonlocal
)
468 fprintf (file
, " (nonlocal)");
469 else if (pt
->vars_contains_escaped_heap
)
470 fprintf (file
, " (escaped heap)");
471 else if (pt
->vars_contains_escaped
)
472 fprintf (file
, " (escaped)");
477 /* Unified dump function for pt_solution. */
480 debug (pt_solution
&ref
)
482 dump_points_to_solution (stderr
, &ref
);
486 debug (pt_solution
*ptr
)
491 fprintf (stderr
, "<nil>\n");
495 /* Dump points-to information for SSA_NAME PTR into FILE. */
498 dump_points_to_info_for (FILE *file
, tree ptr
)
500 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
502 print_generic_expr (file
, ptr
, dump_flags
);
505 dump_points_to_solution (file
, &pi
->pt
);
507 fprintf (file
, ", points-to anything");
509 fprintf (file
, "\n");
513 /* Dump points-to information for VAR into stderr. */
516 debug_points_to_info_for (tree var
)
518 dump_points_to_info_for (stderr
, var
);
522 /* Initializes the alias-oracle reference representation *R from REF. */
525 ao_ref_init (ao_ref
*r
, tree ref
)
532 r
->ref_alias_set
= -1;
533 r
->base_alias_set
= -1;
534 r
->volatile_p
= ref
? TREE_THIS_VOLATILE (ref
) : false;
537 /* Returns the base object of the memory reference *REF. */
540 ao_ref_base (ao_ref
*ref
)
544 ref
->base
= get_ref_base_and_extent (ref
->ref
, &ref
->offset
, &ref
->size
,
549 /* Returns the base object alias set of the memory reference *REF. */
551 static alias_set_type
552 ao_ref_base_alias_set (ao_ref
*ref
)
555 if (ref
->base_alias_set
!= -1)
556 return ref
->base_alias_set
;
560 while (handled_component_p (base_ref
))
561 base_ref
= TREE_OPERAND (base_ref
, 0);
562 ref
->base_alias_set
= get_alias_set (base_ref
);
563 return ref
->base_alias_set
;
566 /* Returns the reference alias set of the memory reference *REF. */
569 ao_ref_alias_set (ao_ref
*ref
)
571 if (ref
->ref_alias_set
!= -1)
572 return ref
->ref_alias_set
;
573 ref
->ref_alias_set
= get_alias_set (ref
->ref
);
574 return ref
->ref_alias_set
;
577 /* Init an alias-oracle reference representation from a gimple pointer
578 PTR and a gimple size SIZE in bytes. If SIZE is NULL_TREE then the
579 size is assumed to be unknown. The access is assumed to be only
580 to or after of the pointer target, not before it. */
583 ao_ref_init_from_ptr_and_size (ao_ref
*ref
, tree ptr
, tree size
)
585 HOST_WIDE_INT t
, size_hwi
, extra_offset
= 0;
586 ref
->ref
= NULL_TREE
;
587 if (TREE_CODE (ptr
) == SSA_NAME
)
589 gimple stmt
= SSA_NAME_DEF_STMT (ptr
);
590 if (gimple_assign_single_p (stmt
)
591 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
592 ptr
= gimple_assign_rhs1 (stmt
);
593 else if (is_gimple_assign (stmt
)
594 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
595 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
)
597 ptr
= gimple_assign_rhs1 (stmt
);
598 extra_offset
= BITS_PER_UNIT
599 * int_cst_value (gimple_assign_rhs2 (stmt
));
603 if (TREE_CODE (ptr
) == ADDR_EXPR
)
605 ref
->base
= get_addr_base_and_unit_offset (TREE_OPERAND (ptr
, 0), &t
);
607 ref
->offset
= BITS_PER_UNIT
* t
;
612 ref
->base
= get_base_address (TREE_OPERAND (ptr
, 0));
617 ref
->base
= build2 (MEM_REF
, char_type_node
,
618 ptr
, null_pointer_node
);
621 ref
->offset
+= extra_offset
;
623 && tree_fits_shwi_p (size
)
624 && (size_hwi
= tree_to_shwi (size
)) <= HOST_WIDE_INT_MAX
/ BITS_PER_UNIT
)
625 ref
->max_size
= ref
->size
= size_hwi
* BITS_PER_UNIT
;
627 ref
->max_size
= ref
->size
= -1;
628 ref
->ref_alias_set
= 0;
629 ref
->base_alias_set
= 0;
630 ref
->volatile_p
= false;
633 /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
634 purpose of TBAA. Return 0 if they are distinct and -1 if we cannot
638 same_type_for_tbaa (tree type1
, tree type2
)
640 type1
= TYPE_MAIN_VARIANT (type1
);
641 type2
= TYPE_MAIN_VARIANT (type2
);
643 /* If we would have to do structural comparison bail out. */
644 if (TYPE_STRUCTURAL_EQUALITY_P (type1
)
645 || TYPE_STRUCTURAL_EQUALITY_P (type2
))
648 /* Compare the canonical types. */
649 if (TYPE_CANONICAL (type1
) == TYPE_CANONICAL (type2
))
652 /* ??? Array types are not properly unified in all cases as we have
653 spurious changes in the index types for example. Removing this
654 causes all sorts of problems with the Fortran frontend. */
655 if (TREE_CODE (type1
) == ARRAY_TYPE
656 && TREE_CODE (type2
) == ARRAY_TYPE
)
659 /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
660 object of one of its constrained subtypes, e.g. when a function with an
661 unconstrained parameter passed by reference is called on an object and
662 inlined. But, even in the case of a fixed size, type and subtypes are
663 not equivalent enough as to share the same TYPE_CANONICAL, since this
664 would mean that conversions between them are useless, whereas they are
665 not (e.g. type and subtypes can have different modes). So, in the end,
666 they are only guaranteed to have the same alias set. */
667 if (get_alias_set (type1
) == get_alias_set (type2
))
671 return equivalent_struct_types_for_tbaa (type1
, type2
);
673 /* The types are known to be not equal. */
677 /* Determine if the two component references REF1 and REF2 which are
678 based on access types TYPE1 and TYPE2 and of which at least one is based
679 on an indirect reference may alias. REF2 is the only one that can
680 be a decl in which case REF2_IS_DECL is true.
681 REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
682 are the respective alias sets. */
685 aliasing_component_refs_p (tree ref1
,
686 alias_set_type ref1_alias_set
,
687 alias_set_type base1_alias_set
,
688 HOST_WIDE_INT offset1
, HOST_WIDE_INT max_size1
,
690 alias_set_type ref2_alias_set
,
691 alias_set_type base2_alias_set
,
692 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
,
695 /* If one reference is a component references through pointers try to find a
696 common base and apply offset based disambiguation. This handles
698 struct A { int i; int j; } *q;
699 struct B { struct A a; int k; } *p;
700 disambiguating q->i and p->a.j. */
706 /* Choose bases and base types to search for. */
708 while (handled_component_p (base1
))
709 base1
= TREE_OPERAND (base1
, 0);
710 type1
= TREE_TYPE (base1
);
712 while (handled_component_p (base2
))
713 base2
= TREE_OPERAND (base2
, 0);
714 type2
= TREE_TYPE (base2
);
716 /* Now search for the type1 in the access path of ref2. This
717 would be a common base for doing offset based disambiguation on. */
719 while (handled_component_p (*refp
)
720 && same_type_for_tbaa (TREE_TYPE (*refp
), type1
) == 0)
721 refp
= &TREE_OPERAND (*refp
, 0);
722 same_p
= same_type_for_tbaa (TREE_TYPE (*refp
), type1
);
723 /* If we couldn't compare types we have to bail out. */
726 else if (same_p
== 1)
728 HOST_WIDE_INT offadj
, sztmp
, msztmp
;
729 get_ref_base_and_extent (*refp
, &offadj
, &sztmp
, &msztmp
);
731 get_ref_base_and_extent (base1
, &offadj
, &sztmp
, &msztmp
);
733 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
735 /* If we didn't find a common base, try the other way around. */
737 while (handled_component_p (*refp
)
738 && same_type_for_tbaa (TREE_TYPE (*refp
), type2
) == 0)
739 refp
= &TREE_OPERAND (*refp
, 0);
740 same_p
= same_type_for_tbaa (TREE_TYPE (*refp
), type2
);
741 /* If we couldn't compare types we have to bail out. */
744 else if (same_p
== 1)
746 HOST_WIDE_INT offadj
, sztmp
, msztmp
;
747 get_ref_base_and_extent (*refp
, &offadj
, &sztmp
, &msztmp
);
749 get_ref_base_and_extent (base2
, &offadj
, &sztmp
, &msztmp
);
751 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
754 /* If we have two type access paths B1.path1 and B2.path2 they may
755 only alias if either B1 is in B2.path2 or B2 is in B1.path1.
756 But we can still have a path that goes B1.path1...B2.path2 with
757 a part that we do not see. So we can only disambiguate now
758 if there is no B2 in the tail of path1 and no B1 on the
760 if (base1_alias_set
== ref2_alias_set
761 || alias_set_subset_of (base1_alias_set
, ref2_alias_set
))
763 /* If this is ptr vs. decl then we know there is no ptr ... decl path. */
765 return (base2_alias_set
== ref1_alias_set
766 || alias_set_subset_of (base2_alias_set
, ref1_alias_set
));
770 /* Return true if we can determine that component references REF1 and REF2,
771 that are within a common DECL, cannot overlap. */
774 nonoverlapping_component_refs_of_decl_p (tree ref1
, tree ref2
)
776 auto_vec
<tree
, 16> component_refs1
;
777 auto_vec
<tree
, 16> component_refs2
;
779 /* Create the stack of handled components for REF1. */
780 while (handled_component_p (ref1
))
782 component_refs1
.safe_push (ref1
);
783 ref1
= TREE_OPERAND (ref1
, 0);
785 if (TREE_CODE (ref1
) == MEM_REF
)
787 if (!integer_zerop (TREE_OPERAND (ref1
, 1)))
789 ref1
= TREE_OPERAND (TREE_OPERAND (ref1
, 0), 0);
792 /* Create the stack of handled components for REF2. */
793 while (handled_component_p (ref2
))
795 component_refs2
.safe_push (ref2
);
796 ref2
= TREE_OPERAND (ref2
, 0);
798 if (TREE_CODE (ref2
) == MEM_REF
)
800 if (!integer_zerop (TREE_OPERAND (ref2
, 1)))
802 ref2
= TREE_OPERAND (TREE_OPERAND (ref2
, 0), 0);
805 /* We must have the same base DECL. */
806 gcc_assert (ref1
== ref2
);
808 /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
809 rank. This is sufficient because we start from the same DECL and you
810 cannot reference several fields at a time with COMPONENT_REFs (unlike
811 with ARRAY_RANGE_REFs for arrays) so you always need the same number
812 of them to access a sub-component, unless you're in a union, in which
813 case the return value will precisely be false. */
818 if (component_refs1
.is_empty ())
820 ref1
= component_refs1
.pop ();
822 while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1
, 0))));
826 if (component_refs2
.is_empty ())
828 ref2
= component_refs2
.pop ();
830 while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2
, 0))));
832 /* Beware of BIT_FIELD_REF. */
833 if (TREE_CODE (ref1
) != COMPONENT_REF
834 || TREE_CODE (ref2
) != COMPONENT_REF
)
837 tree field1
= TREE_OPERAND (ref1
, 1);
838 tree field2
= TREE_OPERAND (ref2
, 1);
840 /* ??? We cannot simply use the type of operand #0 of the refs here
841 as the Fortran compiler smuggles type punning into COMPONENT_REFs
842 for common blocks instead of using unions like everyone else. */
843 tree type1
= DECL_CONTEXT (field1
);
844 tree type2
= DECL_CONTEXT (field2
);
846 /* We cannot disambiguate fields in a union or qualified union. */
847 if (type1
!= type2
|| TREE_CODE (type1
) != RECORD_TYPE
)
850 /* Different fields of the same record type cannot overlap.
851 ??? Bitfields can overlap at RTL level so punt on them. */
852 if (field1
!= field2
)
854 component_refs1
.release ();
855 component_refs2
.release ();
856 return !(DECL_BIT_FIELD (field1
) && DECL_BIT_FIELD (field2
));
861 component_refs1
.release ();
862 component_refs2
.release ();
866 /* qsort compare function to sort FIELD_DECLs after their
867 DECL_FIELD_CONTEXT TYPE_UID. */
870 ncr_compar (const void *field1_
, const void *field2_
)
872 const_tree field1
= *(const_tree
*) const_cast <void *>(field1_
);
873 const_tree field2
= *(const_tree
*) const_cast <void *>(field2_
);
874 unsigned int uid1
= TYPE_UID (DECL_FIELD_CONTEXT (field1
));
875 unsigned int uid2
= TYPE_UID (DECL_FIELD_CONTEXT (field2
));
878 else if (uid1
> uid2
)
883 /* Return true if we can determine that the fields referenced cannot
884 overlap for any pair of objects. */
887 nonoverlapping_component_refs_p (const_tree x
, const_tree y
)
889 if (!flag_strict_aliasing
891 || TREE_CODE (x
) != COMPONENT_REF
892 || TREE_CODE (y
) != COMPONENT_REF
)
895 auto_vec
<const_tree
, 16> fieldsx
;
896 while (TREE_CODE (x
) == COMPONENT_REF
)
898 tree field
= TREE_OPERAND (x
, 1);
899 tree type
= DECL_FIELD_CONTEXT (field
);
900 if (TREE_CODE (type
) == RECORD_TYPE
)
901 fieldsx
.safe_push (field
);
902 x
= TREE_OPERAND (x
, 0);
904 if (fieldsx
.length () == 0)
906 auto_vec
<const_tree
, 16> fieldsy
;
907 while (TREE_CODE (y
) == COMPONENT_REF
)
909 tree field
= TREE_OPERAND (y
, 1);
910 tree type
= DECL_FIELD_CONTEXT (field
);
911 if (TREE_CODE (type
) == RECORD_TYPE
)
912 fieldsy
.safe_push (TREE_OPERAND (y
, 1));
913 y
= TREE_OPERAND (y
, 0);
915 if (fieldsy
.length () == 0)
918 /* Most common case first. */
919 if (fieldsx
.length () == 1
920 && fieldsy
.length () == 1)
921 return ((DECL_FIELD_CONTEXT (fieldsx
[0])
922 == DECL_FIELD_CONTEXT (fieldsy
[0]))
923 && fieldsx
[0] != fieldsy
[0]
924 && !(DECL_BIT_FIELD (fieldsx
[0]) && DECL_BIT_FIELD (fieldsy
[0])));
926 if (fieldsx
.length () == 2)
928 if (ncr_compar (&fieldsx
[0], &fieldsx
[1]) == 1)
930 const_tree tem
= fieldsx
[0];
931 fieldsx
[0] = fieldsx
[1];
936 fieldsx
.qsort (ncr_compar
);
938 if (fieldsy
.length () == 2)
940 if (ncr_compar (&fieldsy
[0], &fieldsy
[1]) == 1)
942 const_tree tem
= fieldsy
[0];
943 fieldsy
[0] = fieldsy
[1];
948 fieldsy
.qsort (ncr_compar
);
950 unsigned i
= 0, j
= 0;
953 const_tree fieldx
= fieldsx
[i
];
954 const_tree fieldy
= fieldsy
[j
];
955 tree typex
= DECL_FIELD_CONTEXT (fieldx
);
956 tree typey
= DECL_FIELD_CONTEXT (fieldy
);
959 /* We're left with accessing different fields of a structure,
960 no possible overlap, unless they are both bitfields. */
961 if (fieldx
!= fieldy
)
962 return !(DECL_BIT_FIELD (fieldx
) && DECL_BIT_FIELD (fieldy
));
964 if (TYPE_UID (typex
) < TYPE_UID (typey
))
967 if (i
== fieldsx
.length ())
973 if (j
== fieldsy
.length ())
983 /* Return true if two memory references based on the variables BASE1
984 and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
985 [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. REF1 and REF2
986 if non-NULL are the complete memory reference trees. */
989 decl_refs_may_alias_p (tree ref1
, tree base1
,
990 HOST_WIDE_INT offset1
, HOST_WIDE_INT max_size1
,
991 tree ref2
, tree base2
,
992 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
)
994 gcc_checking_assert (DECL_P (base1
) && DECL_P (base2
));
996 /* If both references are based on different variables, they cannot alias. */
1000 /* If both references are based on the same variable, they cannot alias if
1001 the accesses do not overlap. */
1002 if (!ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
))
1005 /* For components with variable position, the above test isn't sufficient,
1006 so we disambiguate component references manually. */
1008 && handled_component_p (ref1
) && handled_component_p (ref2
)
1009 && nonoverlapping_component_refs_of_decl_p (ref1
, ref2
))
1015 /* Return true if an indirect reference based on *PTR1 constrained
1016 to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
1017 constrained to [OFFSET2, OFFSET2 + MAX_SIZE2). *PTR1 and BASE2 have
1018 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
1019 in which case they are computed on-demand. REF1 and REF2
1020 if non-NULL are the complete memory reference trees. */
1023 indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED
, tree base1
,
1024 HOST_WIDE_INT offset1
,
1025 HOST_WIDE_INT max_size1 ATTRIBUTE_UNUSED
,
1026 alias_set_type ref1_alias_set
,
1027 alias_set_type base1_alias_set
,
1028 tree ref2 ATTRIBUTE_UNUSED
, tree base2
,
1029 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
,
1030 alias_set_type ref2_alias_set
,
1031 alias_set_type base2_alias_set
, bool tbaa_p
)
1034 tree ptrtype1
, dbase2
;
1035 HOST_WIDE_INT offset1p
= offset1
, offset2p
= offset2
;
1036 HOST_WIDE_INT doffset1
, doffset2
;
1039 gcc_checking_assert ((TREE_CODE (base1
) == MEM_REF
1040 || TREE_CODE (base1
) == TARGET_MEM_REF
)
1043 ptr1
= TREE_OPERAND (base1
, 0);
1045 /* The offset embedded in MEM_REFs can be negative. Bias them
1046 so that the resulting offset adjustment is positive. */
1047 moff
= mem_ref_offset (base1
);
1048 moff
= moff
.lshift (BITS_PER_UNIT
== 8 ? 3 : exact_log2 (BITS_PER_UNIT
));
1049 if (moff
.is_negative ())
1050 offset2p
+= (-moff
).low
;
1052 offset1p
+= moff
.low
;
1054 /* If only one reference is based on a variable, they cannot alias if
1055 the pointer access is beyond the extent of the variable access.
1056 (the pointer base cannot validly point to an offset less than zero
1058 ??? IVOPTs creates bases that do not honor this restriction,
1059 so do not apply this optimization for TARGET_MEM_REFs. */
1060 if (TREE_CODE (base1
) != TARGET_MEM_REF
1061 && !ranges_overlap_p (MAX (0, offset1p
), -1, offset2p
, max_size2
))
1063 /* They also cannot alias if the pointer may not point to the decl. */
1064 if (!ptr_deref_may_alias_decl_p (ptr1
, base2
))
1067 /* Disambiguations that rely on strict aliasing rules follow. */
1068 if (!flag_strict_aliasing
|| !tbaa_p
)
1071 ptrtype1
= TREE_TYPE (TREE_OPERAND (base1
, 1));
1073 /* If the alias set for a pointer access is zero all bets are off. */
1074 if (base1_alias_set
== -1)
1075 base1_alias_set
= get_deref_alias_set (ptrtype1
);
1076 if (base1_alias_set
== 0)
1078 if (base2_alias_set
== -1)
1079 base2_alias_set
= get_alias_set (base2
);
1081 /* When we are trying to disambiguate an access with a pointer dereference
1082 as base versus one with a decl as base we can use both the size
1083 of the decl and its dynamic type for extra disambiguation.
1084 ??? We do not know anything about the dynamic type of the decl
1085 other than that its alias-set contains base2_alias_set as a subset
1086 which does not help us here. */
1087 /* As we know nothing useful about the dynamic type of the decl just
1088 use the usual conflict check rather than a subset test.
1089 ??? We could introduce -fvery-strict-aliasing when the language
1090 does not allow decls to have a dynamic type that differs from their
1091 static type. Then we can check
1092 !alias_set_subset_of (base1_alias_set, base2_alias_set) instead. */
1093 if (base1_alias_set
!= base2_alias_set
1094 && !alias_sets_conflict_p (base1_alias_set
, base2_alias_set
))
1096 /* If the size of the access relevant for TBAA through the pointer
1097 is bigger than the size of the decl we can't possibly access the
1098 decl via that pointer. */
1099 if (DECL_SIZE (base2
) && COMPLETE_TYPE_P (TREE_TYPE (ptrtype1
))
1100 && TREE_CODE (DECL_SIZE (base2
)) == INTEGER_CST
1101 && TREE_CODE (TYPE_SIZE (TREE_TYPE (ptrtype1
))) == INTEGER_CST
1102 /* ??? This in turn may run afoul when a decl of type T which is
1103 a member of union type U is accessed through a pointer to
1104 type U and sizeof T is smaller than sizeof U. */
1105 && TREE_CODE (TREE_TYPE (ptrtype1
)) != UNION_TYPE
1106 && TREE_CODE (TREE_TYPE (ptrtype1
)) != QUAL_UNION_TYPE
1107 && tree_int_cst_lt (DECL_SIZE (base2
), TYPE_SIZE (TREE_TYPE (ptrtype1
))))
1113 /* If the decl is accessed via a MEM_REF, reconstruct the base
1114 we can use for TBAA and an appropriately adjusted offset. */
1116 while (handled_component_p (dbase2
))
1117 dbase2
= TREE_OPERAND (dbase2
, 0);
1120 if (TREE_CODE (dbase2
) == MEM_REF
1121 || TREE_CODE (dbase2
) == TARGET_MEM_REF
)
1123 double_int moff
= mem_ref_offset (dbase2
);
1124 moff
= moff
.lshift (BITS_PER_UNIT
== 8 ? 3 : exact_log2 (BITS_PER_UNIT
));
1125 if (moff
.is_negative ())
1126 doffset1
-= (-moff
).low
;
1128 doffset2
-= moff
.low
;
1131 /* If either reference is view-converted, give up now. */
1132 if (same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (ptrtype1
)) != 1
1133 || same_type_for_tbaa (TREE_TYPE (dbase2
), TREE_TYPE (base2
)) != 1)
1136 /* If both references are through the same type, they do not alias
1137 if the accesses do not overlap. This does extra disambiguation
1138 for mixed/pointer accesses but requires strict aliasing.
1139 For MEM_REFs we require that the component-ref offset we computed
1140 is relative to the start of the type which we ensure by
1141 comparing rvalue and access type and disregarding the constant
1143 if ((TREE_CODE (base1
) != TARGET_MEM_REF
1144 || (!TMR_INDEX (base1
) && !TMR_INDEX2 (base1
)))
1145 && same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (dbase2
)) == 1)
1146 return ranges_overlap_p (doffset1
, max_size1
, doffset2
, max_size2
);
1149 && nonoverlapping_component_refs_p (ref1
, ref2
))
1152 /* Do access-path based disambiguation. */
1154 && (handled_component_p (ref1
) || handled_component_p (ref2
)))
1155 return aliasing_component_refs_p (ref1
,
1156 ref1_alias_set
, base1_alias_set
,
1159 ref2_alias_set
, base2_alias_set
,
1160 offset2
, max_size2
, true);
1165 /* Return true if two indirect references based on *PTR1
1166 and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
1167 [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. *PTR1 and *PTR2 have
1168 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
1169 in which case they are computed on-demand. REF1 and REF2
1170 if non-NULL are the complete memory reference trees. */
1173 indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED
, tree base1
,
1174 HOST_WIDE_INT offset1
, HOST_WIDE_INT max_size1
,
1175 alias_set_type ref1_alias_set
,
1176 alias_set_type base1_alias_set
,
1177 tree ref2 ATTRIBUTE_UNUSED
, tree base2
,
1178 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
,
1179 alias_set_type ref2_alias_set
,
1180 alias_set_type base2_alias_set
, bool tbaa_p
)
1184 tree ptrtype1
, ptrtype2
;
1186 gcc_checking_assert ((TREE_CODE (base1
) == MEM_REF
1187 || TREE_CODE (base1
) == TARGET_MEM_REF
)
1188 && (TREE_CODE (base2
) == MEM_REF
1189 || TREE_CODE (base2
) == TARGET_MEM_REF
));
1191 ptr1
= TREE_OPERAND (base1
, 0);
1192 ptr2
= TREE_OPERAND (base2
, 0);
1194 /* If both bases are based on pointers they cannot alias if they may not
1195 point to the same memory object or if they point to the same object
1196 and the accesses do not overlap. */
1197 if ((!cfun
|| gimple_in_ssa_p (cfun
))
1198 && operand_equal_p (ptr1
, ptr2
, 0)
1199 && (((TREE_CODE (base1
) != TARGET_MEM_REF
1200 || (!TMR_INDEX (base1
) && !TMR_INDEX2 (base1
)))
1201 && (TREE_CODE (base2
) != TARGET_MEM_REF
1202 || (!TMR_INDEX (base2
) && !TMR_INDEX2 (base2
))))
1203 || (TREE_CODE (base1
) == TARGET_MEM_REF
1204 && TREE_CODE (base2
) == TARGET_MEM_REF
1205 && (TMR_STEP (base1
) == TMR_STEP (base2
)
1206 || (TMR_STEP (base1
) && TMR_STEP (base2
)
1207 && operand_equal_p (TMR_STEP (base1
),
1208 TMR_STEP (base2
), 0)))
1209 && (TMR_INDEX (base1
) == TMR_INDEX (base2
)
1210 || (TMR_INDEX (base1
) && TMR_INDEX (base2
)
1211 && operand_equal_p (TMR_INDEX (base1
),
1212 TMR_INDEX (base2
), 0)))
1213 && (TMR_INDEX2 (base1
) == TMR_INDEX2 (base2
)
1214 || (TMR_INDEX2 (base1
) && TMR_INDEX2 (base2
)
1215 && operand_equal_p (TMR_INDEX2 (base1
),
1216 TMR_INDEX2 (base2
), 0))))))
1219 /* The offset embedded in MEM_REFs can be negative. Bias them
1220 so that the resulting offset adjustment is positive. */
1221 moff
= mem_ref_offset (base1
);
1222 moff
= moff
.lshift (BITS_PER_UNIT
== 8 ? 3 : exact_log2 (BITS_PER_UNIT
));
1223 if (moff
.is_negative ())
1224 offset2
+= (-moff
).low
;
1226 offset1
+= moff
.low
;
1227 moff
= mem_ref_offset (base2
);
1228 moff
= moff
.lshift (BITS_PER_UNIT
== 8 ? 3 : exact_log2 (BITS_PER_UNIT
));
1229 if (moff
.is_negative ())
1230 offset1
+= (-moff
).low
;
1232 offset2
+= moff
.low
;
1233 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1235 if (!ptr_derefs_may_alias_p (ptr1
, ptr2
))
1238 /* Disambiguations that rely on strict aliasing rules follow. */
1239 if (!flag_strict_aliasing
|| !tbaa_p
)
1242 ptrtype1
= TREE_TYPE (TREE_OPERAND (base1
, 1));
1243 ptrtype2
= TREE_TYPE (TREE_OPERAND (base2
, 1));
1245 /* If the alias set for a pointer access is zero all bets are off. */
1246 if (base1_alias_set
== -1)
1247 base1_alias_set
= get_deref_alias_set (ptrtype1
);
1248 if (base1_alias_set
== 0)
1250 if (base2_alias_set
== -1)
1251 base2_alias_set
= get_deref_alias_set (ptrtype2
);
1252 if (base2_alias_set
== 0)
1255 /* If both references are through the same type, they do not alias
1256 if the accesses do not overlap. This does extra disambiguation
1257 for mixed/pointer accesses but requires strict aliasing. */
1258 if ((TREE_CODE (base1
) != TARGET_MEM_REF
1259 || (!TMR_INDEX (base1
) && !TMR_INDEX2 (base1
)))
1260 && (TREE_CODE (base2
) != TARGET_MEM_REF
1261 || (!TMR_INDEX (base2
) && !TMR_INDEX2 (base2
)))
1262 && same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (ptrtype1
)) == 1
1263 && same_type_for_tbaa (TREE_TYPE (base2
), TREE_TYPE (ptrtype2
)) == 1
1264 && same_type_for_tbaa (TREE_TYPE (ptrtype1
),
1265 TREE_TYPE (ptrtype2
)) == 1)
1266 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1268 /* Do type-based disambiguation. */
1269 if (base1_alias_set
!= base2_alias_set
1270 && !alias_sets_conflict_p (base1_alias_set
, base2_alias_set
))
1273 /* If either reference is view-converted, give up now. */
1274 if (same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (ptrtype1
)) != 1
1275 || same_type_for_tbaa (TREE_TYPE (base2
), TREE_TYPE (ptrtype2
)) != 1)
1279 && nonoverlapping_component_refs_p (ref1
, ref2
))
1282 /* Do access-path based disambiguation. */
1284 && (handled_component_p (ref1
) || handled_component_p (ref2
)))
1285 return aliasing_component_refs_p (ref1
,
1286 ref1_alias_set
, base1_alias_set
,
1289 ref2_alias_set
, base2_alias_set
,
1290 offset2
, max_size2
, false);
1295 /* Return true, if the two memory references REF1 and REF2 may alias. */
1298 refs_may_alias_p_1 (ao_ref
*ref1
, ao_ref
*ref2
, bool tbaa_p
)
1301 HOST_WIDE_INT offset1
= 0, offset2
= 0;
1302 HOST_WIDE_INT max_size1
= -1, max_size2
= -1;
1303 bool var1_p
, var2_p
, ind1_p
, ind2_p
;
1305 gcc_checking_assert ((!ref1
->ref
1306 || TREE_CODE (ref1
->ref
) == SSA_NAME
1307 || DECL_P (ref1
->ref
)
1308 || TREE_CODE (ref1
->ref
) == STRING_CST
1309 || handled_component_p (ref1
->ref
)
1310 || TREE_CODE (ref1
->ref
) == MEM_REF
1311 || TREE_CODE (ref1
->ref
) == TARGET_MEM_REF
)
1313 || TREE_CODE (ref2
->ref
) == SSA_NAME
1314 || DECL_P (ref2
->ref
)
1315 || TREE_CODE (ref2
->ref
) == STRING_CST
1316 || handled_component_p (ref2
->ref
)
1317 || TREE_CODE (ref2
->ref
) == MEM_REF
1318 || TREE_CODE (ref2
->ref
) == TARGET_MEM_REF
));
1320 if (!dbg_cnt (alias
))
1323 /* Decompose the references into their base objects and the access. */
1324 base1
= ao_ref_base (ref1
);
1325 offset1
= ref1
->offset
;
1326 max_size1
= ref1
->max_size
;
1327 base2
= ao_ref_base (ref2
);
1328 offset2
= ref2
->offset
;
1329 max_size2
= ref2
->max_size
;
1331 /* We can end up with registers or constants as bases for example from
1332 *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
1333 which is seen as a struct copy. */
1334 if (TREE_CODE (base1
) == SSA_NAME
1335 || TREE_CODE (base1
) == CONST_DECL
1336 || TREE_CODE (base1
) == CONSTRUCTOR
1337 || TREE_CODE (base1
) == ADDR_EXPR
1338 || CONSTANT_CLASS_P (base1
)
1339 || TREE_CODE (base2
) == SSA_NAME
1340 || TREE_CODE (base2
) == CONST_DECL
1341 || TREE_CODE (base2
) == CONSTRUCTOR
1342 || TREE_CODE (base2
) == ADDR_EXPR
1343 || CONSTANT_CLASS_P (base2
))
1346 /* We can end up referring to code via function and label decls.
1347 As we likely do not properly track code aliases conservatively
1349 if (TREE_CODE (base1
) == FUNCTION_DECL
1350 || TREE_CODE (base1
) == LABEL_DECL
1351 || TREE_CODE (base2
) == FUNCTION_DECL
1352 || TREE_CODE (base2
) == LABEL_DECL
)
1355 /* Two volatile accesses always conflict. */
1356 if (ref1
->volatile_p
1357 && ref2
->volatile_p
)
1360 /* Defer to simple offset based disambiguation if we have
1361 references based on two decls. Do this before defering to
1362 TBAA to handle must-alias cases in conformance with the
1363 GCC extension of allowing type-punning through unions. */
1364 var1_p
= DECL_P (base1
);
1365 var2_p
= DECL_P (base2
);
1366 if (var1_p
&& var2_p
)
1367 return decl_refs_may_alias_p (ref1
->ref
, base1
, offset1
, max_size1
,
1368 ref2
->ref
, base2
, offset2
, max_size2
);
1370 ind1_p
= (TREE_CODE (base1
) == MEM_REF
1371 || TREE_CODE (base1
) == TARGET_MEM_REF
);
1372 ind2_p
= (TREE_CODE (base2
) == MEM_REF
1373 || TREE_CODE (base2
) == TARGET_MEM_REF
);
1375 /* Canonicalize the pointer-vs-decl case. */
1376 if (ind1_p
&& var2_p
)
1381 tmp1
= offset1
; offset1
= offset2
; offset2
= tmp1
;
1382 tmp1
= max_size1
; max_size1
= max_size2
; max_size2
= tmp1
;
1383 tmp2
= base1
; base1
= base2
; base2
= tmp2
;
1384 tmp3
= ref1
; ref1
= ref2
; ref2
= tmp3
;
1391 /* First defer to TBAA if possible. */
1393 && flag_strict_aliasing
1394 && !alias_sets_conflict_p (ao_ref_alias_set (ref1
),
1395 ao_ref_alias_set (ref2
)))
1398 /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators. */
1399 if (var1_p
&& ind2_p
)
1400 return indirect_ref_may_alias_decl_p (ref2
->ref
, base2
,
1402 ao_ref_alias_set (ref2
), -1,
1405 ao_ref_alias_set (ref1
),
1406 ao_ref_base_alias_set (ref1
),
1409 /* Handle restrict based accesses.
1410 ??? ao_ref_base strips inner MEM_REF [&decl], recover from that
1412 tree rbase1
= base1
;
1413 tree rbase2
= base2
;
1418 while (handled_component_p (rbase1
))
1419 rbase1
= TREE_OPERAND (rbase1
, 0);
1425 while (handled_component_p (rbase2
))
1426 rbase2
= TREE_OPERAND (rbase2
, 0);
1428 if (rbase1
&& rbase2
1429 && (TREE_CODE (base1
) == MEM_REF
|| TREE_CODE (base1
) == TARGET_MEM_REF
)
1430 && (TREE_CODE (base2
) == MEM_REF
|| TREE_CODE (base2
) == TARGET_MEM_REF
)
1431 /* If the accesses are in the same restrict clique... */
1432 && MR_DEPENDENCE_CLIQUE (base1
) == MR_DEPENDENCE_CLIQUE (base2
)
1433 /* But based on different pointers they do not alias. */
1434 && MR_DEPENDENCE_BASE (base1
) != MR_DEPENDENCE_BASE (base2
))
1437 if (ind1_p
&& ind2_p
)
1438 return indirect_refs_may_alias_p (ref1
->ref
, base1
,
1440 ao_ref_alias_set (ref1
), -1,
1443 ao_ref_alias_set (ref2
), -1,
1446 /* We really do not want to end up here, but returning true is safe. */
1447 #ifdef ENABLE_CHECKING
1455 refs_may_alias_p (tree ref1
, tree ref2
)
1459 ao_ref_init (&r1
, ref1
);
1460 ao_ref_init (&r2
, ref2
);
1461 res
= refs_may_alias_p_1 (&r1
, &r2
, true);
1463 ++alias_stats
.refs_may_alias_p_may_alias
;
1465 ++alias_stats
.refs_may_alias_p_no_alias
;
1469 /* Returns true if there is a anti-dependence for the STORE that
1470 executes after the LOAD. */
1473 refs_anti_dependent_p (tree load
, tree store
)
1476 ao_ref_init (&r1
, load
);
1477 ao_ref_init (&r2
, store
);
1478 return refs_may_alias_p_1 (&r1
, &r2
, false);
1481 /* Returns true if there is a output dependence for the stores
1482 STORE1 and STORE2. */
1485 refs_output_dependent_p (tree store1
, tree store2
)
1488 ao_ref_init (&r1
, store1
);
1489 ao_ref_init (&r2
, store2
);
1490 return refs_may_alias_p_1 (&r1
, &r2
, false);
1493 /* If the call CALL may use the memory reference REF return true,
1494 otherwise return false. */
1497 ref_maybe_used_by_call_p_1 (gimple call
, ao_ref
*ref
)
1501 int flags
= gimple_call_flags (call
);
1503 /* Const functions without a static chain do not implicitly use memory. */
1504 if (!gimple_call_chain (call
)
1505 && (flags
& (ECF_CONST
|ECF_NOVOPS
)))
1508 base
= ao_ref_base (ref
);
1512 /* A call that is not without side-effects might involve volatile
1513 accesses and thus conflicts with all other volatile accesses. */
1514 if (ref
->volatile_p
)
1517 /* If the reference is based on a decl that is not aliased the call
1518 cannot possibly use it. */
1520 && !may_be_aliased (base
)
1521 /* But local statics can be used through recursion. */
1522 && !is_global_var (base
))
1525 callee
= gimple_call_fndecl (call
);
1527 /* Handle those builtin functions explicitly that do not act as
1528 escape points. See tree-ssa-structalias.c:find_func_aliases
1529 for the list of builtins we might need to handle here. */
1530 if (callee
!= NULL_TREE
1531 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
1532 switch (DECL_FUNCTION_CODE (callee
))
1534 /* All the following functions read memory pointed to by
1535 their second argument. strcat/strncat additionally
1536 reads memory pointed to by the first argument. */
1537 case BUILT_IN_STRCAT
:
1538 case BUILT_IN_STRNCAT
:
1541 ao_ref_init_from_ptr_and_size (&dref
,
1542 gimple_call_arg (call
, 0),
1544 if (refs_may_alias_p_1 (&dref
, ref
, false))
1548 case BUILT_IN_STRCPY
:
1549 case BUILT_IN_STRNCPY
:
1550 case BUILT_IN_MEMCPY
:
1551 case BUILT_IN_MEMMOVE
:
1552 case BUILT_IN_MEMPCPY
:
1553 case BUILT_IN_STPCPY
:
1554 case BUILT_IN_STPNCPY
:
1555 case BUILT_IN_TM_MEMCPY
:
1556 case BUILT_IN_TM_MEMMOVE
:
1559 tree size
= NULL_TREE
;
1560 if (gimple_call_num_args (call
) == 3)
1561 size
= gimple_call_arg (call
, 2);
1562 ao_ref_init_from_ptr_and_size (&dref
,
1563 gimple_call_arg (call
, 1),
1565 return refs_may_alias_p_1 (&dref
, ref
, false);
1567 case BUILT_IN_STRCAT_CHK
:
1568 case BUILT_IN_STRNCAT_CHK
:
1571 ao_ref_init_from_ptr_and_size (&dref
,
1572 gimple_call_arg (call
, 0),
1574 if (refs_may_alias_p_1 (&dref
, ref
, false))
1578 case BUILT_IN_STRCPY_CHK
:
1579 case BUILT_IN_STRNCPY_CHK
:
1580 case BUILT_IN_MEMCPY_CHK
:
1581 case BUILT_IN_MEMMOVE_CHK
:
1582 case BUILT_IN_MEMPCPY_CHK
:
1583 case BUILT_IN_STPCPY_CHK
:
1584 case BUILT_IN_STPNCPY_CHK
:
1587 tree size
= NULL_TREE
;
1588 if (gimple_call_num_args (call
) == 4)
1589 size
= gimple_call_arg (call
, 2);
1590 ao_ref_init_from_ptr_and_size (&dref
,
1591 gimple_call_arg (call
, 1),
1593 return refs_may_alias_p_1 (&dref
, ref
, false);
1595 case BUILT_IN_BCOPY
:
1598 tree size
= gimple_call_arg (call
, 2);
1599 ao_ref_init_from_ptr_and_size (&dref
,
1600 gimple_call_arg (call
, 0),
1602 return refs_may_alias_p_1 (&dref
, ref
, false);
1605 /* The following functions read memory pointed to by their
1607 CASE_BUILT_IN_TM_LOAD (1):
1608 CASE_BUILT_IN_TM_LOAD (2):
1609 CASE_BUILT_IN_TM_LOAD (4):
1610 CASE_BUILT_IN_TM_LOAD (8):
1611 CASE_BUILT_IN_TM_LOAD (FLOAT
):
1612 CASE_BUILT_IN_TM_LOAD (DOUBLE
):
1613 CASE_BUILT_IN_TM_LOAD (LDOUBLE
):
1614 CASE_BUILT_IN_TM_LOAD (M64
):
1615 CASE_BUILT_IN_TM_LOAD (M128
):
1616 CASE_BUILT_IN_TM_LOAD (M256
):
1617 case BUILT_IN_TM_LOG
:
1618 case BUILT_IN_TM_LOG_1
:
1619 case BUILT_IN_TM_LOG_2
:
1620 case BUILT_IN_TM_LOG_4
:
1621 case BUILT_IN_TM_LOG_8
:
1622 case BUILT_IN_TM_LOG_FLOAT
:
1623 case BUILT_IN_TM_LOG_DOUBLE
:
1624 case BUILT_IN_TM_LOG_LDOUBLE
:
1625 case BUILT_IN_TM_LOG_M64
:
1626 case BUILT_IN_TM_LOG_M128
:
1627 case BUILT_IN_TM_LOG_M256
:
1628 return ptr_deref_may_alias_ref_p_1 (gimple_call_arg (call
, 0), ref
);
1630 /* These read memory pointed to by the first argument. */
1631 case BUILT_IN_STRDUP
:
1632 case BUILT_IN_STRNDUP
:
1635 tree size
= NULL_TREE
;
1636 if (gimple_call_num_args (call
) == 2)
1637 size
= gimple_call_arg (call
, 1);
1638 ao_ref_init_from_ptr_and_size (&dref
,
1639 gimple_call_arg (call
, 0),
1641 return refs_may_alias_p_1 (&dref
, ref
, false);
1643 /* These read memory pointed to by the first argument. */
1644 case BUILT_IN_INDEX
:
1645 case BUILT_IN_STRCHR
:
1646 case BUILT_IN_STRRCHR
:
1649 ao_ref_init_from_ptr_and_size (&dref
,
1650 gimple_call_arg (call
, 0),
1652 return refs_may_alias_p_1 (&dref
, ref
, false);
1654 /* These read memory pointed to by the first argument with size
1655 in the third argument. */
1656 case BUILT_IN_MEMCHR
:
1659 ao_ref_init_from_ptr_and_size (&dref
,
1660 gimple_call_arg (call
, 0),
1661 gimple_call_arg (call
, 2));
1662 return refs_may_alias_p_1 (&dref
, ref
, false);
1664 /* These read memory pointed to by the first and second arguments. */
1665 case BUILT_IN_STRSTR
:
1666 case BUILT_IN_STRPBRK
:
1669 ao_ref_init_from_ptr_and_size (&dref
,
1670 gimple_call_arg (call
, 0),
1672 if (refs_may_alias_p_1 (&dref
, ref
, false))
1674 ao_ref_init_from_ptr_and_size (&dref
,
1675 gimple_call_arg (call
, 1),
1677 return refs_may_alias_p_1 (&dref
, ref
, false);
1680 /* The following builtins do not read from memory. */
1682 case BUILT_IN_MALLOC
:
1683 case BUILT_IN_POSIX_MEMALIGN
:
1684 case BUILT_IN_CALLOC
:
1685 case BUILT_IN_ALLOCA
:
1686 case BUILT_IN_ALLOCA_WITH_ALIGN
:
1687 case BUILT_IN_STACK_SAVE
:
1688 case BUILT_IN_STACK_RESTORE
:
1689 case BUILT_IN_MEMSET
:
1690 case BUILT_IN_TM_MEMSET
:
1691 case BUILT_IN_MEMSET_CHK
:
1692 case BUILT_IN_FREXP
:
1693 case BUILT_IN_FREXPF
:
1694 case BUILT_IN_FREXPL
:
1695 case BUILT_IN_GAMMA_R
:
1696 case BUILT_IN_GAMMAF_R
:
1697 case BUILT_IN_GAMMAL_R
:
1698 case BUILT_IN_LGAMMA_R
:
1699 case BUILT_IN_LGAMMAF_R
:
1700 case BUILT_IN_LGAMMAL_R
:
1702 case BUILT_IN_MODFF
:
1703 case BUILT_IN_MODFL
:
1704 case BUILT_IN_REMQUO
:
1705 case BUILT_IN_REMQUOF
:
1706 case BUILT_IN_REMQUOL
:
1707 case BUILT_IN_SINCOS
:
1708 case BUILT_IN_SINCOSF
:
1709 case BUILT_IN_SINCOSL
:
1710 case BUILT_IN_ASSUME_ALIGNED
:
1711 case BUILT_IN_VA_END
:
1713 /* __sync_* builtins and some OpenMP builtins act as threading
1715 #undef DEF_SYNC_BUILTIN
1716 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1717 #include "sync-builtins.def"
1718 #undef DEF_SYNC_BUILTIN
1719 case BUILT_IN_GOMP_ATOMIC_START
:
1720 case BUILT_IN_GOMP_ATOMIC_END
:
1721 case BUILT_IN_GOMP_BARRIER
:
1722 case BUILT_IN_GOMP_BARRIER_CANCEL
:
1723 case BUILT_IN_GOMP_TASKWAIT
:
1724 case BUILT_IN_GOMP_TASKGROUP_END
:
1725 case BUILT_IN_GOMP_CRITICAL_START
:
1726 case BUILT_IN_GOMP_CRITICAL_END
:
1727 case BUILT_IN_GOMP_CRITICAL_NAME_START
:
1728 case BUILT_IN_GOMP_CRITICAL_NAME_END
:
1729 case BUILT_IN_GOMP_LOOP_END
:
1730 case BUILT_IN_GOMP_LOOP_END_CANCEL
:
1731 case BUILT_IN_GOMP_ORDERED_START
:
1732 case BUILT_IN_GOMP_ORDERED_END
:
1733 case BUILT_IN_GOMP_SECTIONS_END
:
1734 case BUILT_IN_GOMP_SECTIONS_END_CANCEL
:
1735 case BUILT_IN_GOMP_SINGLE_COPY_START
:
1736 case BUILT_IN_GOMP_SINGLE_COPY_END
:
1740 /* Fallthru to general call handling. */;
1743 /* Check if base is a global static variable that is not read
1745 if (callee
!= NULL_TREE
1746 && TREE_CODE (base
) == VAR_DECL
1747 && TREE_STATIC (base
))
1749 struct cgraph_node
*node
= cgraph_get_node (callee
);
1752 /* FIXME: Callee can be an OMP builtin that does not have a call graph
1753 node yet. We should enforce that there are nodes for all decls in the
1754 IL and remove this check instead. */
1756 && (not_read
= ipa_reference_get_not_read_global (node
))
1757 && bitmap_bit_p (not_read
, DECL_UID (base
)))
1761 /* Check if the base variable is call-used. */
1764 if (pt_solution_includes (gimple_call_use_set (call
), base
))
1767 else if ((TREE_CODE (base
) == MEM_REF
1768 || TREE_CODE (base
) == TARGET_MEM_REF
)
1769 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
1771 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (TREE_OPERAND (base
, 0));
1775 if (pt_solutions_intersect (gimple_call_use_set (call
), &pi
->pt
))
1781 /* Inspect call arguments for passed-by-value aliases. */
1783 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1785 tree op
= gimple_call_arg (call
, i
);
1786 int flags
= gimple_call_arg_flags (call
, i
);
1788 if (flags
& EAF_UNUSED
)
1791 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
1792 op
= TREE_OPERAND (op
, 0);
1794 if (TREE_CODE (op
) != SSA_NAME
1795 && !is_gimple_min_invariant (op
))
1798 ao_ref_init (&r
, op
);
1799 if (refs_may_alias_p_1 (&r
, ref
, true))
1808 ref_maybe_used_by_call_p (gimple call
, tree ref
)
1812 ao_ref_init (&r
, ref
);
1813 res
= ref_maybe_used_by_call_p_1 (call
, &r
);
1815 ++alias_stats
.ref_maybe_used_by_call_p_may_alias
;
1817 ++alias_stats
.ref_maybe_used_by_call_p_no_alias
;
1822 /* If the statement STMT may use the memory reference REF return
1823 true, otherwise return false. */
1826 ref_maybe_used_by_stmt_p (gimple stmt
, tree ref
)
1828 if (is_gimple_assign (stmt
))
1832 /* All memory assign statements are single. */
1833 if (!gimple_assign_single_p (stmt
))
1836 rhs
= gimple_assign_rhs1 (stmt
);
1837 if (is_gimple_reg (rhs
)
1838 || is_gimple_min_invariant (rhs
)
1839 || gimple_assign_rhs_code (stmt
) == CONSTRUCTOR
)
1842 return refs_may_alias_p (rhs
, ref
);
1844 else if (is_gimple_call (stmt
))
1845 return ref_maybe_used_by_call_p (stmt
, ref
);
1846 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
1848 tree retval
= gimple_return_retval (stmt
);
1851 && TREE_CODE (retval
) != SSA_NAME
1852 && !is_gimple_min_invariant (retval
)
1853 && refs_may_alias_p (retval
, ref
))
1855 /* If ref escapes the function then the return acts as a use. */
1856 base
= get_base_address (ref
);
1859 else if (DECL_P (base
))
1860 return is_global_var (base
);
1861 else if (TREE_CODE (base
) == MEM_REF
1862 || TREE_CODE (base
) == TARGET_MEM_REF
)
1863 return ptr_deref_may_alias_global_p (TREE_OPERAND (base
, 0));
1870 /* If the call in statement CALL may clobber the memory reference REF
1871 return true, otherwise return false. */
1874 call_may_clobber_ref_p_1 (gimple call
, ao_ref
*ref
)
1879 /* If the call is pure or const it cannot clobber anything. */
1880 if (gimple_call_flags (call
)
1881 & (ECF_PURE
|ECF_CONST
|ECF_LOOPING_CONST_OR_PURE
|ECF_NOVOPS
))
1884 base
= ao_ref_base (ref
);
1888 if (TREE_CODE (base
) == SSA_NAME
1889 || CONSTANT_CLASS_P (base
))
1892 /* A call that is not without side-effects might involve volatile
1893 accesses and thus conflicts with all other volatile accesses. */
1894 if (ref
->volatile_p
)
1897 /* If the reference is based on a decl that is not aliased the call
1898 cannot possibly clobber it. */
1900 && !may_be_aliased (base
)
1901 /* But local non-readonly statics can be modified through recursion
1902 or the call may implement a threading barrier which we must
1903 treat as may-def. */
1904 && (TREE_READONLY (base
)
1905 || !is_global_var (base
)))
1908 callee
= gimple_call_fndecl (call
);
1910 /* Handle those builtin functions explicitly that do not act as
1911 escape points. See tree-ssa-structalias.c:find_func_aliases
1912 for the list of builtins we might need to handle here. */
1913 if (callee
!= NULL_TREE
1914 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
1915 switch (DECL_FUNCTION_CODE (callee
))
1917 /* All the following functions clobber memory pointed to by
1918 their first argument. */
1919 case BUILT_IN_STRCPY
:
1920 case BUILT_IN_STRNCPY
:
1921 case BUILT_IN_MEMCPY
:
1922 case BUILT_IN_MEMMOVE
:
1923 case BUILT_IN_MEMPCPY
:
1924 case BUILT_IN_STPCPY
:
1925 case BUILT_IN_STPNCPY
:
1926 case BUILT_IN_STRCAT
:
1927 case BUILT_IN_STRNCAT
:
1928 case BUILT_IN_MEMSET
:
1929 case BUILT_IN_TM_MEMSET
:
1930 CASE_BUILT_IN_TM_STORE (1):
1931 CASE_BUILT_IN_TM_STORE (2):
1932 CASE_BUILT_IN_TM_STORE (4):
1933 CASE_BUILT_IN_TM_STORE (8):
1934 CASE_BUILT_IN_TM_STORE (FLOAT
):
1935 CASE_BUILT_IN_TM_STORE (DOUBLE
):
1936 CASE_BUILT_IN_TM_STORE (LDOUBLE
):
1937 CASE_BUILT_IN_TM_STORE (M64
):
1938 CASE_BUILT_IN_TM_STORE (M128
):
1939 CASE_BUILT_IN_TM_STORE (M256
):
1940 case BUILT_IN_TM_MEMCPY
:
1941 case BUILT_IN_TM_MEMMOVE
:
1944 tree size
= NULL_TREE
;
1945 /* Don't pass in size for strncat, as the maximum size
1946 is strlen (dest) + n + 1 instead of n, resp.
1947 n + 1 at dest + strlen (dest), but strlen (dest) isn't
1949 if (gimple_call_num_args (call
) == 3
1950 && DECL_FUNCTION_CODE (callee
) != BUILT_IN_STRNCAT
)
1951 size
= gimple_call_arg (call
, 2);
1952 ao_ref_init_from_ptr_and_size (&dref
,
1953 gimple_call_arg (call
, 0),
1955 return refs_may_alias_p_1 (&dref
, ref
, false);
1957 case BUILT_IN_STRCPY_CHK
:
1958 case BUILT_IN_STRNCPY_CHK
:
1959 case BUILT_IN_MEMCPY_CHK
:
1960 case BUILT_IN_MEMMOVE_CHK
:
1961 case BUILT_IN_MEMPCPY_CHK
:
1962 case BUILT_IN_STPCPY_CHK
:
1963 case BUILT_IN_STPNCPY_CHK
:
1964 case BUILT_IN_STRCAT_CHK
:
1965 case BUILT_IN_STRNCAT_CHK
:
1966 case BUILT_IN_MEMSET_CHK
:
1969 tree size
= NULL_TREE
;
1970 /* Don't pass in size for __strncat_chk, as the maximum size
1971 is strlen (dest) + n + 1 instead of n, resp.
1972 n + 1 at dest + strlen (dest), but strlen (dest) isn't
1974 if (gimple_call_num_args (call
) == 4
1975 && DECL_FUNCTION_CODE (callee
) != BUILT_IN_STRNCAT_CHK
)
1976 size
= gimple_call_arg (call
, 2);
1977 ao_ref_init_from_ptr_and_size (&dref
,
1978 gimple_call_arg (call
, 0),
1980 return refs_may_alias_p_1 (&dref
, ref
, false);
1982 case BUILT_IN_BCOPY
:
1985 tree size
= gimple_call_arg (call
, 2);
1986 ao_ref_init_from_ptr_and_size (&dref
,
1987 gimple_call_arg (call
, 1),
1989 return refs_may_alias_p_1 (&dref
, ref
, false);
1991 /* Allocating memory does not have any side-effects apart from
1992 being the definition point for the pointer. */
1993 case BUILT_IN_MALLOC
:
1994 case BUILT_IN_CALLOC
:
1995 case BUILT_IN_STRDUP
:
1996 case BUILT_IN_STRNDUP
:
1997 /* Unix98 specifies that errno is set on allocation failure. */
1999 && targetm
.ref_may_alias_errno (ref
))
2002 case BUILT_IN_STACK_SAVE
:
2003 case BUILT_IN_ALLOCA
:
2004 case BUILT_IN_ALLOCA_WITH_ALIGN
:
2005 case BUILT_IN_ASSUME_ALIGNED
:
2007 /* But posix_memalign stores a pointer into the memory pointed to
2008 by its first argument. */
2009 case BUILT_IN_POSIX_MEMALIGN
:
2011 tree ptrptr
= gimple_call_arg (call
, 0);
2013 ao_ref_init_from_ptr_and_size (&dref
, ptrptr
,
2014 TYPE_SIZE_UNIT (ptr_type_node
));
2015 return (refs_may_alias_p_1 (&dref
, ref
, false)
2017 && targetm
.ref_may_alias_errno (ref
)));
2019 /* Freeing memory kills the pointed-to memory. More importantly
2020 the call has to serve as a barrier for moving loads and stores
2023 case BUILT_IN_VA_END
:
2025 tree ptr
= gimple_call_arg (call
, 0);
2026 return ptr_deref_may_alias_ref_p_1 (ptr
, ref
);
2028 case BUILT_IN_GAMMA_R
:
2029 case BUILT_IN_GAMMAF_R
:
2030 case BUILT_IN_GAMMAL_R
:
2031 case BUILT_IN_LGAMMA_R
:
2032 case BUILT_IN_LGAMMAF_R
:
2033 case BUILT_IN_LGAMMAL_R
:
2035 tree out
= gimple_call_arg (call
, 1);
2036 if (ptr_deref_may_alias_ref_p_1 (out
, ref
))
2038 if (flag_errno_math
)
2042 case BUILT_IN_FREXP
:
2043 case BUILT_IN_FREXPF
:
2044 case BUILT_IN_FREXPL
:
2046 case BUILT_IN_MODFF
:
2047 case BUILT_IN_MODFL
:
2049 tree out
= gimple_call_arg (call
, 1);
2050 return ptr_deref_may_alias_ref_p_1 (out
, ref
);
2052 case BUILT_IN_REMQUO
:
2053 case BUILT_IN_REMQUOF
:
2054 case BUILT_IN_REMQUOL
:
2056 tree out
= gimple_call_arg (call
, 2);
2057 if (ptr_deref_may_alias_ref_p_1 (out
, ref
))
2059 if (flag_errno_math
)
2063 case BUILT_IN_SINCOS
:
2064 case BUILT_IN_SINCOSF
:
2065 case BUILT_IN_SINCOSL
:
2067 tree sin
= gimple_call_arg (call
, 1);
2068 tree cos
= gimple_call_arg (call
, 2);
2069 return (ptr_deref_may_alias_ref_p_1 (sin
, ref
)
2070 || ptr_deref_may_alias_ref_p_1 (cos
, ref
));
2072 /* __sync_* builtins and some OpenMP builtins act as threading
2074 #undef DEF_SYNC_BUILTIN
2075 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
2076 #include "sync-builtins.def"
2077 #undef DEF_SYNC_BUILTIN
2078 case BUILT_IN_GOMP_ATOMIC_START
:
2079 case BUILT_IN_GOMP_ATOMIC_END
:
2080 case BUILT_IN_GOMP_BARRIER
:
2081 case BUILT_IN_GOMP_BARRIER_CANCEL
:
2082 case BUILT_IN_GOMP_TASKWAIT
:
2083 case BUILT_IN_GOMP_TASKGROUP_END
:
2084 case BUILT_IN_GOMP_CRITICAL_START
:
2085 case BUILT_IN_GOMP_CRITICAL_END
:
2086 case BUILT_IN_GOMP_CRITICAL_NAME_START
:
2087 case BUILT_IN_GOMP_CRITICAL_NAME_END
:
2088 case BUILT_IN_GOMP_LOOP_END
:
2089 case BUILT_IN_GOMP_LOOP_END_CANCEL
:
2090 case BUILT_IN_GOMP_ORDERED_START
:
2091 case BUILT_IN_GOMP_ORDERED_END
:
2092 case BUILT_IN_GOMP_SECTIONS_END
:
2093 case BUILT_IN_GOMP_SECTIONS_END_CANCEL
:
2094 case BUILT_IN_GOMP_SINGLE_COPY_START
:
2095 case BUILT_IN_GOMP_SINGLE_COPY_END
:
2098 /* Fallthru to general call handling. */;
2101 /* Check if base is a global static variable that is not written
2103 if (callee
!= NULL_TREE
2104 && TREE_CODE (base
) == VAR_DECL
2105 && TREE_STATIC (base
))
2107 struct cgraph_node
*node
= cgraph_get_node (callee
);
2111 && (not_written
= ipa_reference_get_not_written_global (node
))
2112 && bitmap_bit_p (not_written
, DECL_UID (base
)))
2116 /* Check if the base variable is call-clobbered. */
2118 return pt_solution_includes (gimple_call_clobber_set (call
), base
);
2119 else if ((TREE_CODE (base
) == MEM_REF
2120 || TREE_CODE (base
) == TARGET_MEM_REF
)
2121 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
2123 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (TREE_OPERAND (base
, 0));
2127 return pt_solutions_intersect (gimple_call_clobber_set (call
), &pi
->pt
);
2133 /* If the call in statement CALL may clobber the memory reference REF
2134 return true, otherwise return false. */
2137 call_may_clobber_ref_p (gimple call
, tree ref
)
2141 ao_ref_init (&r
, ref
);
2142 res
= call_may_clobber_ref_p_1 (call
, &r
);
2144 ++alias_stats
.call_may_clobber_ref_p_may_alias
;
2146 ++alias_stats
.call_may_clobber_ref_p_no_alias
;
2151 /* If the statement STMT may clobber the memory reference REF return true,
2152 otherwise return false. */
2155 stmt_may_clobber_ref_p_1 (gimple stmt
, ao_ref
*ref
)
2157 if (is_gimple_call (stmt
))
2159 tree lhs
= gimple_call_lhs (stmt
);
2161 && TREE_CODE (lhs
) != SSA_NAME
)
2164 ao_ref_init (&r
, lhs
);
2165 if (refs_may_alias_p_1 (ref
, &r
, true))
2169 return call_may_clobber_ref_p_1 (stmt
, ref
);
2171 else if (gimple_assign_single_p (stmt
))
2173 tree lhs
= gimple_assign_lhs (stmt
);
2174 if (TREE_CODE (lhs
) != SSA_NAME
)
2177 ao_ref_init (&r
, lhs
);
2178 return refs_may_alias_p_1 (ref
, &r
, true);
2181 else if (gimple_code (stmt
) == GIMPLE_ASM
)
2188 stmt_may_clobber_ref_p (gimple stmt
, tree ref
)
2191 ao_ref_init (&r
, ref
);
2192 return stmt_may_clobber_ref_p_1 (stmt
, &r
);
2195 /* If STMT kills the memory reference REF return true, otherwise
2199 stmt_kills_ref_p_1 (gimple stmt
, ao_ref
*ref
)
2201 /* For a must-alias check we need to be able to constrain
2202 the access properly.
2203 FIXME: except for BUILTIN_FREE. */
2204 if (!ao_ref_base (ref
)
2205 || ref
->max_size
== -1)
2208 if (gimple_has_lhs (stmt
)
2209 && TREE_CODE (gimple_get_lhs (stmt
)) != SSA_NAME
2210 /* The assignment is not necessarily carried out if it can throw
2211 and we can catch it in the current function where we could inspect
2213 ??? We only need to care about the RHS throwing. For aggregate
2214 assignments or similar calls and non-call exceptions the LHS
2215 might throw as well. */
2216 && !stmt_can_throw_internal (stmt
))
2218 tree base
, lhs
= gimple_get_lhs (stmt
);
2219 HOST_WIDE_INT size
, offset
, max_size
, ref_offset
= ref
->offset
;
2220 base
= get_ref_base_and_extent (lhs
, &offset
, &size
, &max_size
);
2221 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
2222 so base == ref->base does not always hold. */
2223 if (base
!= ref
->base
)
2225 /* If both base and ref->base are MEM_REFs, only compare the
2226 first operand, and if the second operand isn't equal constant,
2227 try to add the offsets into offset and ref_offset. */
2228 if (TREE_CODE (base
) == MEM_REF
&& TREE_CODE (ref
->base
) == MEM_REF
2229 && TREE_OPERAND (base
, 0) == TREE_OPERAND (ref
->base
, 0))
2231 if (!tree_int_cst_equal (TREE_OPERAND (base
, 1),
2232 TREE_OPERAND (ref
->base
, 1)))
2234 double_int off1
= mem_ref_offset (base
);
2235 off1
= off1
.lshift (BITS_PER_UNIT
== 8
2236 ? 3 : exact_log2 (BITS_PER_UNIT
));
2237 off1
= off1
+ double_int::from_shwi (offset
);
2238 double_int off2
= mem_ref_offset (ref
->base
);
2239 off2
= off2
.lshift (BITS_PER_UNIT
== 8
2240 ? 3 : exact_log2 (BITS_PER_UNIT
));
2241 off2
= off2
+ double_int::from_shwi (ref_offset
);
2242 if (off1
.fits_shwi () && off2
.fits_shwi ())
2244 offset
= off1
.to_shwi ();
2245 ref_offset
= off2
.to_shwi ();
2254 /* For a must-alias check we need to be able to constrain
2255 the access properly. */
2256 if (size
!= -1 && size
== max_size
)
2258 if (offset
<= ref_offset
2259 && offset
+ size
>= ref_offset
+ ref
->max_size
)
2264 if (is_gimple_call (stmt
))
2266 tree callee
= gimple_call_fndecl (stmt
);
2267 if (callee
!= NULL_TREE
2268 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
2269 switch (DECL_FUNCTION_CODE (callee
))
2273 tree ptr
= gimple_call_arg (stmt
, 0);
2274 tree base
= ao_ref_base (ref
);
2275 if (base
&& TREE_CODE (base
) == MEM_REF
2276 && TREE_OPERAND (base
, 0) == ptr
)
2281 case BUILT_IN_MEMCPY
:
2282 case BUILT_IN_MEMPCPY
:
2283 case BUILT_IN_MEMMOVE
:
2284 case BUILT_IN_MEMSET
:
2285 case BUILT_IN_MEMCPY_CHK
:
2286 case BUILT_IN_MEMPCPY_CHK
:
2287 case BUILT_IN_MEMMOVE_CHK
:
2288 case BUILT_IN_MEMSET_CHK
:
2290 tree dest
= gimple_call_arg (stmt
, 0);
2291 tree len
= gimple_call_arg (stmt
, 2);
2292 if (!tree_fits_shwi_p (len
))
2294 tree rbase
= ref
->base
;
2295 double_int roffset
= double_int::from_shwi (ref
->offset
);
2297 ao_ref_init_from_ptr_and_size (&dref
, dest
, len
);
2298 tree base
= ao_ref_base (&dref
);
2299 double_int offset
= double_int::from_shwi (dref
.offset
);
2300 double_int bpu
= double_int::from_uhwi (BITS_PER_UNIT
);
2301 if (!base
|| dref
.size
== -1)
2303 if (TREE_CODE (base
) == MEM_REF
)
2305 if (TREE_CODE (rbase
) != MEM_REF
)
2307 // Compare pointers.
2308 offset
+= bpu
* mem_ref_offset (base
);
2309 roffset
+= bpu
* mem_ref_offset (rbase
);
2310 base
= TREE_OPERAND (base
, 0);
2311 rbase
= TREE_OPERAND (rbase
, 0);
2315 double_int size
= bpu
* tree_to_double_int (len
);
2316 double_int rsize
= double_int::from_uhwi (ref
->max_size
);
2317 if (offset
.sle (roffset
)
2318 && (roffset
+ rsize
).sle (offset
+ size
))
2324 case BUILT_IN_VA_END
:
2326 tree ptr
= gimple_call_arg (stmt
, 0);
2327 if (TREE_CODE (ptr
) == ADDR_EXPR
)
2329 tree base
= ao_ref_base (ref
);
2330 if (TREE_OPERAND (ptr
, 0) == base
)
2343 stmt_kills_ref_p (gimple stmt
, tree ref
)
2346 ao_ref_init (&r
, ref
);
2347 return stmt_kills_ref_p_1 (stmt
, &r
);
2351 /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
2352 TARGET or a statement clobbering the memory reference REF in which
2353 case false is returned. The walk starts with VUSE, one argument of PHI. */
2356 maybe_skip_until (gimple phi
, tree target
, ao_ref
*ref
,
2357 tree vuse
, unsigned int *cnt
, bitmap
*visited
,
2358 bool abort_on_visited
)
2360 basic_block bb
= gimple_bb (phi
);
2363 *visited
= BITMAP_ALLOC (NULL
);
2365 bitmap_set_bit (*visited
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
2367 /* Walk until we hit the target. */
2368 while (vuse
!= target
)
2370 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
2371 /* Recurse for PHI nodes. */
2372 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2374 /* An already visited PHI node ends the walk successfully. */
2375 if (bitmap_bit_p (*visited
, SSA_NAME_VERSION (PHI_RESULT (def_stmt
))))
2376 return !abort_on_visited
;
2377 vuse
= get_continuation_for_phi (def_stmt
, ref
, cnt
,
2378 visited
, abort_on_visited
);
2383 else if (gimple_nop_p (def_stmt
))
2387 /* A clobbering statement or the end of the IL ends it failing. */
2389 if (stmt_may_clobber_ref_p_1 (def_stmt
, ref
))
2392 /* If we reach a new basic-block see if we already skipped it
2393 in a previous walk that ended successfully. */
2394 if (gimple_bb (def_stmt
) != bb
)
2396 if (!bitmap_set_bit (*visited
, SSA_NAME_VERSION (vuse
)))
2397 return !abort_on_visited
;
2398 bb
= gimple_bb (def_stmt
);
2400 vuse
= gimple_vuse (def_stmt
);
2405 /* For two PHI arguments ARG0 and ARG1 try to skip non-aliasing code
2406 until we hit the phi argument definition that dominates the other one.
2407 Return that, or NULL_TREE if there is no such definition. */
2410 get_continuation_for_phi_1 (gimple phi
, tree arg0
, tree arg1
,
2411 ao_ref
*ref
, unsigned int *cnt
,
2412 bitmap
*visited
, bool abort_on_visited
)
2414 gimple def0
= SSA_NAME_DEF_STMT (arg0
);
2415 gimple def1
= SSA_NAME_DEF_STMT (arg1
);
2420 else if (gimple_nop_p (def0
)
2421 || (!gimple_nop_p (def1
)
2422 && dominated_by_p (CDI_DOMINATORS
,
2423 gimple_bb (def1
), gimple_bb (def0
))))
2425 if (maybe_skip_until (phi
, arg0
, ref
, arg1
, cnt
,
2426 visited
, abort_on_visited
))
2429 else if (gimple_nop_p (def1
)
2430 || dominated_by_p (CDI_DOMINATORS
,
2431 gimple_bb (def0
), gimple_bb (def1
)))
2433 if (maybe_skip_until (phi
, arg1
, ref
, arg0
, cnt
,
2434 visited
, abort_on_visited
))
2437 /* Special case of a diamond:
2439 goto (cond) ? L1 : L2
2440 L1: store1 = ... #MEM_2 = vuse(MEM_1)
2442 L2: store2 = ... #MEM_3 = vuse(MEM_1)
2443 L3: MEM_4 = PHI<MEM_2, MEM_3>
2444 We were called with the PHI at L3, MEM_2 and MEM_3 don't
2445 dominate each other, but still we can easily skip this PHI node
2446 if we recognize that the vuse MEM operand is the same for both,
2447 and that we can skip both statements (they don't clobber us).
2448 This is still linear. Don't use maybe_skip_until, that might
2449 potentially be slow. */
2450 else if ((common_vuse
= gimple_vuse (def0
))
2451 && common_vuse
== gimple_vuse (def1
))
2454 if (!stmt_may_clobber_ref_p_1 (def0
, ref
)
2455 && !stmt_may_clobber_ref_p_1 (def1
, ref
))
2463 /* Starting from a PHI node for the virtual operand of the memory reference
2464 REF find a continuation virtual operand that allows to continue walking
2465 statements dominating PHI skipping only statements that cannot possibly
2466 clobber REF. Increments *CNT for each alias disambiguation done.
2467 Returns NULL_TREE if no suitable virtual operand can be found. */
2470 get_continuation_for_phi (gimple phi
, ao_ref
*ref
,
2471 unsigned int *cnt
, bitmap
*visited
,
2472 bool abort_on_visited
)
2474 unsigned nargs
= gimple_phi_num_args (phi
);
2476 /* Through a single-argument PHI we can simply look through. */
2478 return PHI_ARG_DEF (phi
, 0);
2480 /* For two or more arguments try to pairwise skip non-aliasing code
2481 until we hit the phi argument definition that dominates the other one. */
2482 else if (nargs
>= 2)
2487 /* Find a candidate for the virtual operand which definition
2488 dominates those of all others. */
2489 arg0
= PHI_ARG_DEF (phi
, 0);
2490 if (!SSA_NAME_IS_DEFAULT_DEF (arg0
))
2491 for (i
= 1; i
< nargs
; ++i
)
2493 arg1
= PHI_ARG_DEF (phi
, i
);
2494 if (SSA_NAME_IS_DEFAULT_DEF (arg1
))
2499 if (dominated_by_p (CDI_DOMINATORS
,
2500 gimple_bb (SSA_NAME_DEF_STMT (arg0
)),
2501 gimple_bb (SSA_NAME_DEF_STMT (arg1
))))
2505 /* Then pairwise reduce against the found candidate. */
2506 for (i
= 0; i
< nargs
; ++i
)
2508 arg1
= PHI_ARG_DEF (phi
, i
);
2509 arg0
= get_continuation_for_phi_1 (phi
, arg0
, arg1
, ref
,
2510 cnt
, visited
, abort_on_visited
);
2521 /* Based on the memory reference REF and its virtual use VUSE call
2522 WALKER for each virtual use that is equivalent to VUSE, including VUSE
2523 itself. That is, for each virtual use for which its defining statement
2524 does not clobber REF.
2526 WALKER is called with REF, the current virtual use and DATA. If
2527 WALKER returns non-NULL the walk stops and its result is returned.
2528 At the end of a non-successful walk NULL is returned.
2530 TRANSLATE if non-NULL is called with a pointer to REF, the virtual
2531 use which definition is a statement that may clobber REF and DATA.
2532 If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
2533 If TRANSLATE returns non-NULL the walk stops and its result is returned.
2534 If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
2535 to adjust REF and *DATA to make that valid.
2537 TODO: Cache the vector of equivalent vuses per ref, vuse pair. */
2540 walk_non_aliased_vuses (ao_ref
*ref
, tree vuse
,
2541 void *(*walker
)(ao_ref
*, tree
, unsigned int, void *),
2542 void *(*translate
)(ao_ref
*, tree
, void *), void *data
)
2544 bitmap visited
= NULL
;
2546 unsigned int cnt
= 0;
2547 bool translated
= false;
2549 timevar_push (TV_ALIAS_STMT_WALK
);
2555 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
2556 res
= (*walker
) (ref
, vuse
, cnt
, data
);
2558 if (res
== (void *)-1)
2563 /* Lookup succeeded. */
2564 else if (res
!= NULL
)
2567 def_stmt
= SSA_NAME_DEF_STMT (vuse
);
2568 if (gimple_nop_p (def_stmt
))
2570 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2571 vuse
= get_continuation_for_phi (def_stmt
, ref
, &cnt
,
2572 &visited
, translated
);
2576 if (stmt_may_clobber_ref_p_1 (def_stmt
, ref
))
2580 res
= (*translate
) (ref
, vuse
, data
);
2581 /* Failed lookup and translation. */
2582 if (res
== (void *)-1)
2587 /* Lookup succeeded. */
2588 else if (res
!= NULL
)
2590 /* Translation succeeded, continue walking. */
2593 vuse
= gimple_vuse (def_stmt
);
2599 BITMAP_FREE (visited
);
2601 timevar_pop (TV_ALIAS_STMT_WALK
);
2607 /* Based on the memory reference REF call WALKER for each vdef which
2608 defining statement may clobber REF, starting with VDEF. If REF
2609 is NULL_TREE, each defining statement is visited.
2611 WALKER is called with REF, the current vdef and DATA. If WALKER
2612 returns true the walk is stopped, otherwise it continues.
2614 At PHI nodes walk_aliased_vdefs forks into one walk for reach
2615 PHI argument (but only one walk continues on merge points), the
2616 return value is true if any of the walks was successful.
2618 The function returns the number of statements walked. */
2621 walk_aliased_vdefs_1 (ao_ref
*ref
, tree vdef
,
2622 bool (*walker
)(ao_ref
*, tree
, void *), void *data
,
2623 bitmap
*visited
, unsigned int cnt
)
2627 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
2630 && !bitmap_set_bit (*visited
, SSA_NAME_VERSION (vdef
)))
2633 if (gimple_nop_p (def_stmt
))
2635 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2639 *visited
= BITMAP_ALLOC (NULL
);
2640 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); ++i
)
2641 cnt
+= walk_aliased_vdefs_1 (ref
, gimple_phi_arg_def (def_stmt
, i
),
2642 walker
, data
, visited
, 0);
2646 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
2649 || stmt_may_clobber_ref_p_1 (def_stmt
, ref
))
2650 && (*walker
) (ref
, vdef
, data
))
2653 vdef
= gimple_vuse (def_stmt
);
2659 walk_aliased_vdefs (ao_ref
*ref
, tree vdef
,
2660 bool (*walker
)(ao_ref
*, tree
, void *), void *data
,
2663 bitmap local_visited
= NULL
;
2666 timevar_push (TV_ALIAS_STMT_WALK
);
2668 ret
= walk_aliased_vdefs_1 (ref
, vdef
, walker
, data
,
2669 visited
? visited
: &local_visited
, 0);
2671 BITMAP_FREE (local_visited
);
2673 timevar_pop (TV_ALIAS_STMT_WALK
);