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"
33 #include "hard-reg-set.h"
36 #include "dominance.h"
37 #include "basic-block.h"
38 #include "timevar.h" /* for TV_ALIAS_STMT_WALK */
39 #include "langhooks.h"
41 #include "tree-pretty-print.h"
43 #include "tree-ssa-alias.h"
44 #include "internal-fn.h"
46 #include "gimple-expr.h"
49 #include "gimple-ssa.h"
50 #include "stringpool.h"
51 #include "tree-ssanames.h"
54 #include "tree-inline.h"
56 #include "alloc-pool.h"
57 #include "tree-ssa-alias.h"
58 #include "ipa-reference.h"
60 /* Broad overview of how alias analysis on gimple works:
62 Statements clobbering or using memory are linked through the
63 virtual operand factored use-def chain. The virtual operand
64 is unique per function, its symbol is accessible via gimple_vop (cfun).
65 Virtual operands are used for efficiently walking memory statements
66 in the gimple IL and are useful for things like value-numbering as
67 a generation count for memory references.
69 SSA_NAME pointers may have associated points-to information
70 accessible via the SSA_NAME_PTR_INFO macro. Flow-insensitive
71 points-to information is (re-)computed by the TODO_rebuild_alias
72 pass manager todo. Points-to information is also used for more
73 precise tracking of call-clobbered and call-used variables and
74 related disambiguations.
76 This file contains functions for disambiguating memory references,
77 the so called alias-oracle and tools for walking of the gimple IL.
79 The main alias-oracle entry-points are
81 bool stmt_may_clobber_ref_p (gimple, tree)
83 This function queries if a statement may invalidate (parts of)
84 the memory designated by the reference tree argument.
86 bool ref_maybe_used_by_stmt_p (gimple, tree)
88 This function queries if a statement may need (parts of) the
89 memory designated by the reference tree argument.
91 There are variants of these functions that only handle the call
92 part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
93 Note that these do not disambiguate against a possible call lhs.
95 bool refs_may_alias_p (tree, tree)
97 This function tries to disambiguate two reference trees.
99 bool ptr_deref_may_alias_global_p (tree)
101 This function queries if dereferencing a pointer variable may
104 More low-level disambiguators are available and documented in
105 this file. Low-level disambiguators dealing with points-to
106 information are in tree-ssa-structalias.c. */
109 /* Query statistics for the different low-level disambiguators.
110 A high-level query may trigger multiple of them. */
113 unsigned HOST_WIDE_INT refs_may_alias_p_may_alias
;
114 unsigned HOST_WIDE_INT refs_may_alias_p_no_alias
;
115 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias
;
116 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias
;
117 unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias
;
118 unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias
;
122 dump_alias_stats (FILE *s
)
124 fprintf (s
, "\nAlias oracle query stats:\n");
125 fprintf (s
, " refs_may_alias_p: "
126 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
127 HOST_WIDE_INT_PRINT_DEC
" queries\n",
128 alias_stats
.refs_may_alias_p_no_alias
,
129 alias_stats
.refs_may_alias_p_no_alias
130 + alias_stats
.refs_may_alias_p_may_alias
);
131 fprintf (s
, " ref_maybe_used_by_call_p: "
132 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
133 HOST_WIDE_INT_PRINT_DEC
" queries\n",
134 alias_stats
.ref_maybe_used_by_call_p_no_alias
,
135 alias_stats
.refs_may_alias_p_no_alias
136 + alias_stats
.ref_maybe_used_by_call_p_may_alias
);
137 fprintf (s
, " call_may_clobber_ref_p: "
138 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
139 HOST_WIDE_INT_PRINT_DEC
" queries\n",
140 alias_stats
.call_may_clobber_ref_p_no_alias
,
141 alias_stats
.call_may_clobber_ref_p_no_alias
142 + alias_stats
.call_may_clobber_ref_p_may_alias
);
146 /* Return true, if dereferencing PTR may alias with a global variable. */
149 ptr_deref_may_alias_global_p (tree ptr
)
151 struct ptr_info_def
*pi
;
153 /* If we end up with a pointer constant here that may point
155 if (TREE_CODE (ptr
) != SSA_NAME
)
158 pi
= SSA_NAME_PTR_INFO (ptr
);
160 /* If we do not have points-to information for this variable,
165 /* ??? This does not use TBAA to prune globals ptr may not access. */
166 return pt_solution_includes_global (&pi
->pt
);
169 /* Return true if dereferencing PTR may alias DECL.
170 The caller is responsible for applying TBAA to see if PTR
171 may access DECL at all. */
174 ptr_deref_may_alias_decl_p (tree ptr
, tree decl
)
176 struct ptr_info_def
*pi
;
178 /* Conversions are irrelevant for points-to information and
179 data-dependence analysis can feed us those. */
182 /* Anything we do not explicilty handle aliases. */
183 if ((TREE_CODE (ptr
) != SSA_NAME
184 && TREE_CODE (ptr
) != ADDR_EXPR
185 && TREE_CODE (ptr
) != POINTER_PLUS_EXPR
)
186 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
187 || (TREE_CODE (decl
) != VAR_DECL
188 && TREE_CODE (decl
) != PARM_DECL
189 && TREE_CODE (decl
) != RESULT_DECL
))
192 /* Disregard pointer offsetting. */
193 if (TREE_CODE (ptr
) == POINTER_PLUS_EXPR
)
197 ptr
= TREE_OPERAND (ptr
, 0);
199 while (TREE_CODE (ptr
) == POINTER_PLUS_EXPR
);
200 return ptr_deref_may_alias_decl_p (ptr
, decl
);
203 /* ADDR_EXPR pointers either just offset another pointer or directly
204 specify the pointed-to set. */
205 if (TREE_CODE (ptr
) == ADDR_EXPR
)
207 tree base
= get_base_address (TREE_OPERAND (ptr
, 0));
209 && (TREE_CODE (base
) == MEM_REF
210 || TREE_CODE (base
) == TARGET_MEM_REF
))
211 ptr
= TREE_OPERAND (base
, 0);
216 && CONSTANT_CLASS_P (base
))
222 /* Non-aliased variables can not be pointed to. */
223 if (!may_be_aliased (decl
))
226 /* If we do not have useful points-to information for this pointer
227 we cannot disambiguate anything else. */
228 pi
= SSA_NAME_PTR_INFO (ptr
);
232 return pt_solution_includes (&pi
->pt
, decl
);
235 /* Return true if dereferenced PTR1 and PTR2 may alias.
236 The caller is responsible for applying TBAA to see if accesses
237 through PTR1 and PTR2 may conflict at all. */
240 ptr_derefs_may_alias_p (tree ptr1
, tree ptr2
)
242 struct ptr_info_def
*pi1
, *pi2
;
244 /* Conversions are irrelevant for points-to information and
245 data-dependence analysis can feed us those. */
249 /* Disregard pointer offsetting. */
250 if (TREE_CODE (ptr1
) == POINTER_PLUS_EXPR
)
254 ptr1
= TREE_OPERAND (ptr1
, 0);
256 while (TREE_CODE (ptr1
) == POINTER_PLUS_EXPR
);
257 return ptr_derefs_may_alias_p (ptr1
, ptr2
);
259 if (TREE_CODE (ptr2
) == POINTER_PLUS_EXPR
)
263 ptr2
= TREE_OPERAND (ptr2
, 0);
265 while (TREE_CODE (ptr2
) == POINTER_PLUS_EXPR
);
266 return ptr_derefs_may_alias_p (ptr1
, ptr2
);
269 /* ADDR_EXPR pointers either just offset another pointer or directly
270 specify the pointed-to set. */
271 if (TREE_CODE (ptr1
) == ADDR_EXPR
)
273 tree base
= get_base_address (TREE_OPERAND (ptr1
, 0));
275 && (TREE_CODE (base
) == MEM_REF
276 || TREE_CODE (base
) == TARGET_MEM_REF
))
277 return ptr_derefs_may_alias_p (TREE_OPERAND (base
, 0), ptr2
);
280 return ptr_deref_may_alias_decl_p (ptr2
, base
);
284 if (TREE_CODE (ptr2
) == ADDR_EXPR
)
286 tree base
= get_base_address (TREE_OPERAND (ptr2
, 0));
288 && (TREE_CODE (base
) == MEM_REF
289 || TREE_CODE (base
) == TARGET_MEM_REF
))
290 return ptr_derefs_may_alias_p (ptr1
, TREE_OPERAND (base
, 0));
293 return ptr_deref_may_alias_decl_p (ptr1
, base
);
298 /* From here we require SSA name pointers. Anything else aliases. */
299 if (TREE_CODE (ptr1
) != SSA_NAME
300 || TREE_CODE (ptr2
) != SSA_NAME
301 || !POINTER_TYPE_P (TREE_TYPE (ptr1
))
302 || !POINTER_TYPE_P (TREE_TYPE (ptr2
)))
305 /* We may end up with two empty points-to solutions for two same pointers.
306 In this case we still want to say both pointers alias, so shortcut
311 /* If we do not have useful points-to information for either pointer
312 we cannot disambiguate anything else. */
313 pi1
= SSA_NAME_PTR_INFO (ptr1
);
314 pi2
= SSA_NAME_PTR_INFO (ptr2
);
318 /* ??? This does not use TBAA to prune decls from the intersection
319 that not both pointers may access. */
320 return pt_solutions_intersect (&pi1
->pt
, &pi2
->pt
);
323 /* Return true if dereferencing PTR may alias *REF.
324 The caller is responsible for applying TBAA to see if PTR
325 may access *REF at all. */
328 ptr_deref_may_alias_ref_p_1 (tree ptr
, ao_ref
*ref
)
330 tree base
= ao_ref_base (ref
);
332 if (TREE_CODE (base
) == MEM_REF
333 || TREE_CODE (base
) == TARGET_MEM_REF
)
334 return ptr_derefs_may_alias_p (ptr
, TREE_OPERAND (base
, 0));
335 else if (DECL_P (base
))
336 return ptr_deref_may_alias_decl_p (ptr
, base
);
341 /* Returns whether reference REF to BASE may refer to global memory. */
344 ref_may_alias_global_p_1 (tree base
)
347 return is_global_var (base
);
348 else if (TREE_CODE (base
) == MEM_REF
349 || TREE_CODE (base
) == TARGET_MEM_REF
)
350 return ptr_deref_may_alias_global_p (TREE_OPERAND (base
, 0));
355 ref_may_alias_global_p (ao_ref
*ref
)
357 tree base
= ao_ref_base (ref
);
358 return ref_may_alias_global_p_1 (base
);
362 ref_may_alias_global_p (tree ref
)
364 tree base
= get_base_address (ref
);
365 return ref_may_alias_global_p_1 (base
);
368 /* Return true whether STMT may clobber global memory. */
371 stmt_may_clobber_global_p (gimple stmt
)
375 if (!gimple_vdef (stmt
))
378 /* ??? We can ask the oracle whether an artificial pointer
379 dereference with a pointer with points-to information covering
380 all global memory (what about non-address taken memory?) maybe
381 clobbered by this call. As there is at the moment no convenient
382 way of doing that without generating garbage do some manual
384 ??? We could make a NULL ao_ref argument to the various
385 predicates special, meaning any global memory. */
387 switch (gimple_code (stmt
))
390 lhs
= gimple_assign_lhs (stmt
);
391 return (TREE_CODE (lhs
) != SSA_NAME
392 && ref_may_alias_global_p (lhs
));
401 /* Dump alias information on FILE. */
404 dump_alias_info (FILE *file
)
408 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
411 fprintf (file
, "\n\nAlias information for %s\n\n", funcname
);
413 fprintf (file
, "Aliased symbols\n\n");
415 FOR_EACH_LOCAL_DECL (cfun
, i
, var
)
417 if (may_be_aliased (var
))
418 dump_variable (file
, var
);
421 fprintf (file
, "\nCall clobber information\n");
423 fprintf (file
, "\nESCAPED");
424 dump_points_to_solution (file
, &cfun
->gimple_df
->escaped
);
426 fprintf (file
, "\n\nFlow-insensitive points-to information\n\n");
428 for (i
= 1; i
< num_ssa_names
; i
++)
430 tree ptr
= ssa_name (i
);
431 struct ptr_info_def
*pi
;
434 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
435 || SSA_NAME_IN_FREE_LIST (ptr
))
438 pi
= SSA_NAME_PTR_INFO (ptr
);
440 dump_points_to_info_for (file
, ptr
);
443 fprintf (file
, "\n");
447 /* Dump alias information on stderr. */
450 debug_alias_info (void)
452 dump_alias_info (stderr
);
456 /* Dump the points-to set *PT into FILE. */
459 dump_points_to_solution (FILE *file
, struct pt_solution
*pt
)
462 fprintf (file
, ", points-to anything");
465 fprintf (file
, ", points-to non-local");
468 fprintf (file
, ", points-to escaped");
471 fprintf (file
, ", points-to unit escaped");
474 fprintf (file
, ", points-to NULL");
478 fprintf (file
, ", points-to vars: ");
479 dump_decl_set (file
, pt
->vars
);
480 if (pt
->vars_contains_nonlocal
481 && pt
->vars_contains_escaped_heap
)
482 fprintf (file
, " (nonlocal, escaped heap)");
483 else if (pt
->vars_contains_nonlocal
484 && pt
->vars_contains_escaped
)
485 fprintf (file
, " (nonlocal, escaped)");
486 else if (pt
->vars_contains_nonlocal
)
487 fprintf (file
, " (nonlocal)");
488 else if (pt
->vars_contains_escaped_heap
)
489 fprintf (file
, " (escaped heap)");
490 else if (pt
->vars_contains_escaped
)
491 fprintf (file
, " (escaped)");
496 /* Unified dump function for pt_solution. */
499 debug (pt_solution
&ref
)
501 dump_points_to_solution (stderr
, &ref
);
505 debug (pt_solution
*ptr
)
510 fprintf (stderr
, "<nil>\n");
514 /* Dump points-to information for SSA_NAME PTR into FILE. */
517 dump_points_to_info_for (FILE *file
, tree ptr
)
519 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
521 print_generic_expr (file
, ptr
, dump_flags
);
524 dump_points_to_solution (file
, &pi
->pt
);
526 fprintf (file
, ", points-to anything");
528 fprintf (file
, "\n");
532 /* Dump points-to information for VAR into stderr. */
535 debug_points_to_info_for (tree var
)
537 dump_points_to_info_for (stderr
, var
);
541 /* Initializes the alias-oracle reference representation *R from REF. */
544 ao_ref_init (ao_ref
*r
, tree ref
)
551 r
->ref_alias_set
= -1;
552 r
->base_alias_set
= -1;
553 r
->volatile_p
= ref
? TREE_THIS_VOLATILE (ref
) : false;
556 /* Returns the base object of the memory reference *REF. */
559 ao_ref_base (ao_ref
*ref
)
563 ref
->base
= get_ref_base_and_extent (ref
->ref
, &ref
->offset
, &ref
->size
,
568 /* Returns the base object alias set of the memory reference *REF. */
571 ao_ref_base_alias_set (ao_ref
*ref
)
574 if (ref
->base_alias_set
!= -1)
575 return ref
->base_alias_set
;
579 while (handled_component_p (base_ref
))
580 base_ref
= TREE_OPERAND (base_ref
, 0);
581 ref
->base_alias_set
= get_alias_set (base_ref
);
582 return ref
->base_alias_set
;
585 /* Returns the reference alias set of the memory reference *REF. */
588 ao_ref_alias_set (ao_ref
*ref
)
590 if (ref
->ref_alias_set
!= -1)
591 return ref
->ref_alias_set
;
592 ref
->ref_alias_set
= get_alias_set (ref
->ref
);
593 return ref
->ref_alias_set
;
596 /* Init an alias-oracle reference representation from a gimple pointer
597 PTR and a gimple size SIZE in bytes. If SIZE is NULL_TREE then the
598 size is assumed to be unknown. The access is assumed to be only
599 to or after of the pointer target, not before it. */
602 ao_ref_init_from_ptr_and_size (ao_ref
*ref
, tree ptr
, tree size
)
604 HOST_WIDE_INT t
, size_hwi
, extra_offset
= 0;
605 ref
->ref
= NULL_TREE
;
606 if (TREE_CODE (ptr
) == SSA_NAME
)
608 gimple stmt
= SSA_NAME_DEF_STMT (ptr
);
609 if (gimple_assign_single_p (stmt
)
610 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
611 ptr
= gimple_assign_rhs1 (stmt
);
612 else if (is_gimple_assign (stmt
)
613 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
614 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
)
616 ptr
= gimple_assign_rhs1 (stmt
);
617 extra_offset
= BITS_PER_UNIT
618 * int_cst_value (gimple_assign_rhs2 (stmt
));
622 if (TREE_CODE (ptr
) == ADDR_EXPR
)
624 ref
->base
= get_addr_base_and_unit_offset (TREE_OPERAND (ptr
, 0), &t
);
626 ref
->offset
= BITS_PER_UNIT
* t
;
631 ref
->base
= get_base_address (TREE_OPERAND (ptr
, 0));
636 ref
->base
= build2 (MEM_REF
, char_type_node
,
637 ptr
, null_pointer_node
);
640 ref
->offset
+= extra_offset
;
642 && tree_fits_shwi_p (size
)
643 && (size_hwi
= tree_to_shwi (size
)) <= HOST_WIDE_INT_MAX
/ BITS_PER_UNIT
)
644 ref
->max_size
= ref
->size
= size_hwi
* BITS_PER_UNIT
;
646 ref
->max_size
= ref
->size
= -1;
647 ref
->ref_alias_set
= 0;
648 ref
->base_alias_set
= 0;
649 ref
->volatile_p
= false;
652 /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
653 purpose of TBAA. Return 0 if they are distinct and -1 if we cannot
657 same_type_for_tbaa (tree type1
, tree type2
)
659 type1
= TYPE_MAIN_VARIANT (type1
);
660 type2
= TYPE_MAIN_VARIANT (type2
);
662 /* If we would have to do structural comparison bail out. */
663 if (TYPE_STRUCTURAL_EQUALITY_P (type1
)
664 || TYPE_STRUCTURAL_EQUALITY_P (type2
))
667 /* Compare the canonical types. */
668 if (TYPE_CANONICAL (type1
) == TYPE_CANONICAL (type2
))
671 /* ??? Array types are not properly unified in all cases as we have
672 spurious changes in the index types for example. Removing this
673 causes all sorts of problems with the Fortran frontend. */
674 if (TREE_CODE (type1
) == ARRAY_TYPE
675 && TREE_CODE (type2
) == ARRAY_TYPE
)
678 /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
679 object of one of its constrained subtypes, e.g. when a function with an
680 unconstrained parameter passed by reference is called on an object and
681 inlined. But, even in the case of a fixed size, type and subtypes are
682 not equivalent enough as to share the same TYPE_CANONICAL, since this
683 would mean that conversions between them are useless, whereas they are
684 not (e.g. type and subtypes can have different modes). So, in the end,
685 they are only guaranteed to have the same alias set. */
686 if (get_alias_set (type1
) == get_alias_set (type2
))
689 /* The types are known to be not equal. */
693 /* Determine if the two component references REF1 and REF2 which are
694 based on access types TYPE1 and TYPE2 and of which at least one is based
695 on an indirect reference may alias. REF2 is the only one that can
696 be a decl in which case REF2_IS_DECL is true.
697 REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
698 are the respective alias sets. */
701 aliasing_component_refs_p (tree ref1
,
702 alias_set_type ref1_alias_set
,
703 alias_set_type base1_alias_set
,
704 HOST_WIDE_INT offset1
, HOST_WIDE_INT max_size1
,
706 alias_set_type ref2_alias_set
,
707 alias_set_type base2_alias_set
,
708 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
,
711 /* If one reference is a component references through pointers try to find a
712 common base and apply offset based disambiguation. This handles
714 struct A { int i; int j; } *q;
715 struct B { struct A a; int k; } *p;
716 disambiguating q->i and p->a.j. */
722 /* Choose bases and base types to search for. */
724 while (handled_component_p (base1
))
725 base1
= TREE_OPERAND (base1
, 0);
726 type1
= TREE_TYPE (base1
);
728 while (handled_component_p (base2
))
729 base2
= TREE_OPERAND (base2
, 0);
730 type2
= TREE_TYPE (base2
);
732 /* Now search for the type1 in the access path of ref2. This
733 would be a common base for doing offset based disambiguation on. */
735 while (handled_component_p (*refp
)
736 && same_type_for_tbaa (TREE_TYPE (*refp
), type1
) == 0)
737 refp
= &TREE_OPERAND (*refp
, 0);
738 same_p
= same_type_for_tbaa (TREE_TYPE (*refp
), type1
);
739 /* If we couldn't compare types we have to bail out. */
742 else if (same_p
== 1)
744 HOST_WIDE_INT offadj
, sztmp
, msztmp
;
745 get_ref_base_and_extent (*refp
, &offadj
, &sztmp
, &msztmp
);
747 get_ref_base_and_extent (base1
, &offadj
, &sztmp
, &msztmp
);
749 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
751 /* If we didn't find a common base, try the other way around. */
753 while (handled_component_p (*refp
)
754 && same_type_for_tbaa (TREE_TYPE (*refp
), type2
) == 0)
755 refp
= &TREE_OPERAND (*refp
, 0);
756 same_p
= same_type_for_tbaa (TREE_TYPE (*refp
), type2
);
757 /* If we couldn't compare types we have to bail out. */
760 else if (same_p
== 1)
762 HOST_WIDE_INT offadj
, sztmp
, msztmp
;
763 get_ref_base_and_extent (*refp
, &offadj
, &sztmp
, &msztmp
);
765 get_ref_base_and_extent (base2
, &offadj
, &sztmp
, &msztmp
);
767 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
770 /* If we have two type access paths B1.path1 and B2.path2 they may
771 only alias if either B1 is in B2.path2 or B2 is in B1.path1.
772 But we can still have a path that goes B1.path1...B2.path2 with
773 a part that we do not see. So we can only disambiguate now
774 if there is no B2 in the tail of path1 and no B1 on the
776 if (base1_alias_set
== ref2_alias_set
777 || alias_set_subset_of (base1_alias_set
, ref2_alias_set
))
779 /* If this is ptr vs. decl then we know there is no ptr ... decl path. */
781 return (base2_alias_set
== ref1_alias_set
782 || alias_set_subset_of (base2_alias_set
, ref1_alias_set
));
786 /* Return true if we can determine that component references REF1 and REF2,
787 that are within a common DECL, cannot overlap. */
790 nonoverlapping_component_refs_of_decl_p (tree ref1
, tree ref2
)
792 auto_vec
<tree
, 16> component_refs1
;
793 auto_vec
<tree
, 16> component_refs2
;
795 /* Create the stack of handled components for REF1. */
796 while (handled_component_p (ref1
))
798 component_refs1
.safe_push (ref1
);
799 ref1
= TREE_OPERAND (ref1
, 0);
801 if (TREE_CODE (ref1
) == MEM_REF
)
803 if (!integer_zerop (TREE_OPERAND (ref1
, 1)))
805 ref1
= TREE_OPERAND (TREE_OPERAND (ref1
, 0), 0);
808 /* Create the stack of handled components for REF2. */
809 while (handled_component_p (ref2
))
811 component_refs2
.safe_push (ref2
);
812 ref2
= TREE_OPERAND (ref2
, 0);
814 if (TREE_CODE (ref2
) == MEM_REF
)
816 if (!integer_zerop (TREE_OPERAND (ref2
, 1)))
818 ref2
= TREE_OPERAND (TREE_OPERAND (ref2
, 0), 0);
821 /* We must have the same base DECL. */
822 gcc_assert (ref1
== ref2
);
824 /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
825 rank. This is sufficient because we start from the same DECL and you
826 cannot reference several fields at a time with COMPONENT_REFs (unlike
827 with ARRAY_RANGE_REFs for arrays) so you always need the same number
828 of them to access a sub-component, unless you're in a union, in which
829 case the return value will precisely be false. */
834 if (component_refs1
.is_empty ())
836 ref1
= component_refs1
.pop ();
838 while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1
, 0))));
842 if (component_refs2
.is_empty ())
844 ref2
= component_refs2
.pop ();
846 while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2
, 0))));
848 /* Beware of BIT_FIELD_REF. */
849 if (TREE_CODE (ref1
) != COMPONENT_REF
850 || TREE_CODE (ref2
) != COMPONENT_REF
)
853 tree field1
= TREE_OPERAND (ref1
, 1);
854 tree field2
= TREE_OPERAND (ref2
, 1);
856 /* ??? We cannot simply use the type of operand #0 of the refs here
857 as the Fortran compiler smuggles type punning into COMPONENT_REFs
858 for common blocks instead of using unions like everyone else. */
859 tree type1
= DECL_CONTEXT (field1
);
860 tree type2
= DECL_CONTEXT (field2
);
862 /* We cannot disambiguate fields in a union or qualified union. */
863 if (type1
!= type2
|| TREE_CODE (type1
) != RECORD_TYPE
)
866 /* Different fields of the same record type cannot overlap.
867 ??? Bitfields can overlap at RTL level so punt on them. */
868 if (field1
!= field2
)
870 component_refs1
.release ();
871 component_refs2
.release ();
872 return !(DECL_BIT_FIELD (field1
) && DECL_BIT_FIELD (field2
));
877 component_refs1
.release ();
878 component_refs2
.release ();
882 /* qsort compare function to sort FIELD_DECLs after their
883 DECL_FIELD_CONTEXT TYPE_UID. */
886 ncr_compar (const void *field1_
, const void *field2_
)
888 const_tree field1
= *(const_tree
*) const_cast <void *>(field1_
);
889 const_tree field2
= *(const_tree
*) const_cast <void *>(field2_
);
890 unsigned int uid1
= TYPE_UID (DECL_FIELD_CONTEXT (field1
));
891 unsigned int uid2
= TYPE_UID (DECL_FIELD_CONTEXT (field2
));
894 else if (uid1
> uid2
)
899 /* Return true if we can determine that the fields referenced cannot
900 overlap for any pair of objects. */
903 nonoverlapping_component_refs_p (const_tree x
, const_tree y
)
905 if (!flag_strict_aliasing
907 || TREE_CODE (x
) != COMPONENT_REF
908 || TREE_CODE (y
) != COMPONENT_REF
)
911 auto_vec
<const_tree
, 16> fieldsx
;
912 while (TREE_CODE (x
) == COMPONENT_REF
)
914 tree field
= TREE_OPERAND (x
, 1);
915 tree type
= DECL_FIELD_CONTEXT (field
);
916 if (TREE_CODE (type
) == RECORD_TYPE
)
917 fieldsx
.safe_push (field
);
918 x
= TREE_OPERAND (x
, 0);
920 if (fieldsx
.length () == 0)
922 auto_vec
<const_tree
, 16> fieldsy
;
923 while (TREE_CODE (y
) == COMPONENT_REF
)
925 tree field
= TREE_OPERAND (y
, 1);
926 tree type
= DECL_FIELD_CONTEXT (field
);
927 if (TREE_CODE (type
) == RECORD_TYPE
)
928 fieldsy
.safe_push (TREE_OPERAND (y
, 1));
929 y
= TREE_OPERAND (y
, 0);
931 if (fieldsy
.length () == 0)
934 /* Most common case first. */
935 if (fieldsx
.length () == 1
936 && fieldsy
.length () == 1)
937 return ((DECL_FIELD_CONTEXT (fieldsx
[0])
938 == DECL_FIELD_CONTEXT (fieldsy
[0]))
939 && fieldsx
[0] != fieldsy
[0]
940 && !(DECL_BIT_FIELD (fieldsx
[0]) && DECL_BIT_FIELD (fieldsy
[0])));
942 if (fieldsx
.length () == 2)
944 if (ncr_compar (&fieldsx
[0], &fieldsx
[1]) == 1)
946 const_tree tem
= fieldsx
[0];
947 fieldsx
[0] = fieldsx
[1];
952 fieldsx
.qsort (ncr_compar
);
954 if (fieldsy
.length () == 2)
956 if (ncr_compar (&fieldsy
[0], &fieldsy
[1]) == 1)
958 const_tree tem
= fieldsy
[0];
959 fieldsy
[0] = fieldsy
[1];
964 fieldsy
.qsort (ncr_compar
);
966 unsigned i
= 0, j
= 0;
969 const_tree fieldx
= fieldsx
[i
];
970 const_tree fieldy
= fieldsy
[j
];
971 tree typex
= DECL_FIELD_CONTEXT (fieldx
);
972 tree typey
= DECL_FIELD_CONTEXT (fieldy
);
975 /* We're left with accessing different fields of a structure,
976 no possible overlap, unless they are both bitfields. */
977 if (fieldx
!= fieldy
)
978 return !(DECL_BIT_FIELD (fieldx
) && DECL_BIT_FIELD (fieldy
));
980 if (TYPE_UID (typex
) < TYPE_UID (typey
))
983 if (i
== fieldsx
.length ())
989 if (j
== fieldsy
.length ())
999 /* Return true if two memory references based on the variables BASE1
1000 and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
1001 [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. REF1 and REF2
1002 if non-NULL are the complete memory reference trees. */
1005 decl_refs_may_alias_p (tree ref1
, tree base1
,
1006 HOST_WIDE_INT offset1
, HOST_WIDE_INT max_size1
,
1007 tree ref2
, tree base2
,
1008 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
)
1010 gcc_checking_assert (DECL_P (base1
) && DECL_P (base2
));
1012 /* If both references are based on different variables, they cannot alias. */
1016 /* If both references are based on the same variable, they cannot alias if
1017 the accesses do not overlap. */
1018 if (!ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
))
1021 /* For components with variable position, the above test isn't sufficient,
1022 so we disambiguate component references manually. */
1024 && handled_component_p (ref1
) && handled_component_p (ref2
)
1025 && nonoverlapping_component_refs_of_decl_p (ref1
, ref2
))
1031 /* Return true if an indirect reference based on *PTR1 constrained
1032 to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
1033 constrained to [OFFSET2, OFFSET2 + MAX_SIZE2). *PTR1 and BASE2 have
1034 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
1035 in which case they are computed on-demand. REF1 and REF2
1036 if non-NULL are the complete memory reference trees. */
1039 indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED
, tree base1
,
1040 HOST_WIDE_INT offset1
,
1041 HOST_WIDE_INT max_size1 ATTRIBUTE_UNUSED
,
1042 alias_set_type ref1_alias_set
,
1043 alias_set_type base1_alias_set
,
1044 tree ref2 ATTRIBUTE_UNUSED
, tree base2
,
1045 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
,
1046 alias_set_type ref2_alias_set
,
1047 alias_set_type base2_alias_set
, bool tbaa_p
)
1050 tree ptrtype1
, dbase2
;
1051 HOST_WIDE_INT offset1p
= offset1
, offset2p
= offset2
;
1052 HOST_WIDE_INT doffset1
, doffset2
;
1054 gcc_checking_assert ((TREE_CODE (base1
) == MEM_REF
1055 || TREE_CODE (base1
) == TARGET_MEM_REF
)
1058 ptr1
= TREE_OPERAND (base1
, 0);
1060 /* The offset embedded in MEM_REFs can be negative. Bias them
1061 so that the resulting offset adjustment is positive. */
1062 offset_int moff
= mem_ref_offset (base1
);
1063 moff
= wi::lshift (moff
, LOG2_BITS_PER_UNIT
);
1064 if (wi::neg_p (moff
))
1065 offset2p
+= (-moff
).to_short_addr ();
1067 offset1p
+= moff
.to_short_addr ();
1069 /* If only one reference is based on a variable, they cannot alias if
1070 the pointer access is beyond the extent of the variable access.
1071 (the pointer base cannot validly point to an offset less than zero
1073 ??? IVOPTs creates bases that do not honor this restriction,
1074 so do not apply this optimization for TARGET_MEM_REFs. */
1075 if (TREE_CODE (base1
) != TARGET_MEM_REF
1076 && !ranges_overlap_p (MAX (0, offset1p
), -1, offset2p
, max_size2
))
1078 /* They also cannot alias if the pointer may not point to the decl. */
1079 if (!ptr_deref_may_alias_decl_p (ptr1
, base2
))
1082 /* Disambiguations that rely on strict aliasing rules follow. */
1083 if (!flag_strict_aliasing
|| !tbaa_p
)
1086 ptrtype1
= TREE_TYPE (TREE_OPERAND (base1
, 1));
1088 /* If the alias set for a pointer access is zero all bets are off. */
1089 if (base1_alias_set
== -1)
1090 base1_alias_set
= get_deref_alias_set (ptrtype1
);
1091 if (base1_alias_set
== 0)
1093 if (base2_alias_set
== -1)
1094 base2_alias_set
= get_alias_set (base2
);
1096 /* When we are trying to disambiguate an access with a pointer dereference
1097 as base versus one with a decl as base we can use both the size
1098 of the decl and its dynamic type for extra disambiguation.
1099 ??? We do not know anything about the dynamic type of the decl
1100 other than that its alias-set contains base2_alias_set as a subset
1101 which does not help us here. */
1102 /* As we know nothing useful about the dynamic type of the decl just
1103 use the usual conflict check rather than a subset test.
1104 ??? We could introduce -fvery-strict-aliasing when the language
1105 does not allow decls to have a dynamic type that differs from their
1106 static type. Then we can check
1107 !alias_set_subset_of (base1_alias_set, base2_alias_set) instead. */
1108 if (base1_alias_set
!= base2_alias_set
1109 && !alias_sets_conflict_p (base1_alias_set
, base2_alias_set
))
1111 /* If the size of the access relevant for TBAA through the pointer
1112 is bigger than the size of the decl we can't possibly access the
1113 decl via that pointer. */
1114 if (DECL_SIZE (base2
) && COMPLETE_TYPE_P (TREE_TYPE (ptrtype1
))
1115 && TREE_CODE (DECL_SIZE (base2
)) == INTEGER_CST
1116 && TREE_CODE (TYPE_SIZE (TREE_TYPE (ptrtype1
))) == INTEGER_CST
1117 /* ??? This in turn may run afoul when a decl of type T which is
1118 a member of union type U is accessed through a pointer to
1119 type U and sizeof T is smaller than sizeof U. */
1120 && TREE_CODE (TREE_TYPE (ptrtype1
)) != UNION_TYPE
1121 && TREE_CODE (TREE_TYPE (ptrtype1
)) != QUAL_UNION_TYPE
1122 && tree_int_cst_lt (DECL_SIZE (base2
), TYPE_SIZE (TREE_TYPE (ptrtype1
))))
1128 /* If the decl is accessed via a MEM_REF, reconstruct the base
1129 we can use for TBAA and an appropriately adjusted offset. */
1131 while (handled_component_p (dbase2
))
1132 dbase2
= TREE_OPERAND (dbase2
, 0);
1135 if (TREE_CODE (dbase2
) == MEM_REF
1136 || TREE_CODE (dbase2
) == TARGET_MEM_REF
)
1138 offset_int moff
= mem_ref_offset (dbase2
);
1139 moff
= wi::lshift (moff
, LOG2_BITS_PER_UNIT
);
1140 if (wi::neg_p (moff
))
1141 doffset1
-= (-moff
).to_short_addr ();
1143 doffset2
-= moff
.to_short_addr ();
1146 /* If either reference is view-converted, give up now. */
1147 if (same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (ptrtype1
)) != 1
1148 || same_type_for_tbaa (TREE_TYPE (dbase2
), TREE_TYPE (base2
)) != 1)
1151 /* If both references are through the same type, they do not alias
1152 if the accesses do not overlap. This does extra disambiguation
1153 for mixed/pointer accesses but requires strict aliasing.
1154 For MEM_REFs we require that the component-ref offset we computed
1155 is relative to the start of the type which we ensure by
1156 comparing rvalue and access type and disregarding the constant
1158 if ((TREE_CODE (base1
) != TARGET_MEM_REF
1159 || (!TMR_INDEX (base1
) && !TMR_INDEX2 (base1
)))
1160 && same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (dbase2
)) == 1)
1161 return ranges_overlap_p (doffset1
, max_size1
, doffset2
, max_size2
);
1164 && nonoverlapping_component_refs_p (ref1
, ref2
))
1167 /* Do access-path based disambiguation. */
1169 && (handled_component_p (ref1
) || handled_component_p (ref2
)))
1170 return aliasing_component_refs_p (ref1
,
1171 ref1_alias_set
, base1_alias_set
,
1174 ref2_alias_set
, base2_alias_set
,
1175 offset2
, max_size2
, true);
1180 /* Return true if two indirect references based on *PTR1
1181 and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
1182 [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. *PTR1 and *PTR2 have
1183 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
1184 in which case they are computed on-demand. REF1 and REF2
1185 if non-NULL are the complete memory reference trees. */
1188 indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED
, tree base1
,
1189 HOST_WIDE_INT offset1
, HOST_WIDE_INT max_size1
,
1190 alias_set_type ref1_alias_set
,
1191 alias_set_type base1_alias_set
,
1192 tree ref2 ATTRIBUTE_UNUSED
, tree base2
,
1193 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
,
1194 alias_set_type ref2_alias_set
,
1195 alias_set_type base2_alias_set
, bool tbaa_p
)
1199 tree ptrtype1
, ptrtype2
;
1201 gcc_checking_assert ((TREE_CODE (base1
) == MEM_REF
1202 || TREE_CODE (base1
) == TARGET_MEM_REF
)
1203 && (TREE_CODE (base2
) == MEM_REF
1204 || TREE_CODE (base2
) == TARGET_MEM_REF
));
1206 ptr1
= TREE_OPERAND (base1
, 0);
1207 ptr2
= TREE_OPERAND (base2
, 0);
1209 /* If both bases are based on pointers they cannot alias if they may not
1210 point to the same memory object or if they point to the same object
1211 and the accesses do not overlap. */
1212 if ((!cfun
|| gimple_in_ssa_p (cfun
))
1213 && operand_equal_p (ptr1
, ptr2
, 0)
1214 && (((TREE_CODE (base1
) != TARGET_MEM_REF
1215 || (!TMR_INDEX (base1
) && !TMR_INDEX2 (base1
)))
1216 && (TREE_CODE (base2
) != TARGET_MEM_REF
1217 || (!TMR_INDEX (base2
) && !TMR_INDEX2 (base2
))))
1218 || (TREE_CODE (base1
) == TARGET_MEM_REF
1219 && TREE_CODE (base2
) == TARGET_MEM_REF
1220 && (TMR_STEP (base1
) == TMR_STEP (base2
)
1221 || (TMR_STEP (base1
) && TMR_STEP (base2
)
1222 && operand_equal_p (TMR_STEP (base1
),
1223 TMR_STEP (base2
), 0)))
1224 && (TMR_INDEX (base1
) == TMR_INDEX (base2
)
1225 || (TMR_INDEX (base1
) && TMR_INDEX (base2
)
1226 && operand_equal_p (TMR_INDEX (base1
),
1227 TMR_INDEX (base2
), 0)))
1228 && (TMR_INDEX2 (base1
) == TMR_INDEX2 (base2
)
1229 || (TMR_INDEX2 (base1
) && TMR_INDEX2 (base2
)
1230 && operand_equal_p (TMR_INDEX2 (base1
),
1231 TMR_INDEX2 (base2
), 0))))))
1234 /* The offset embedded in MEM_REFs can be negative. Bias them
1235 so that the resulting offset adjustment is positive. */
1236 moff
= mem_ref_offset (base1
);
1237 moff
= wi::lshift (moff
, LOG2_BITS_PER_UNIT
);
1238 if (wi::neg_p (moff
))
1239 offset2
+= (-moff
).to_short_addr ();
1241 offset1
+= moff
.to_shwi ();
1242 moff
= mem_ref_offset (base2
);
1243 moff
= wi::lshift (moff
, LOG2_BITS_PER_UNIT
);
1244 if (wi::neg_p (moff
))
1245 offset1
+= (-moff
).to_short_addr ();
1247 offset2
+= moff
.to_short_addr ();
1248 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1250 if (!ptr_derefs_may_alias_p (ptr1
, ptr2
))
1253 /* Disambiguations that rely on strict aliasing rules follow. */
1254 if (!flag_strict_aliasing
|| !tbaa_p
)
1257 ptrtype1
= TREE_TYPE (TREE_OPERAND (base1
, 1));
1258 ptrtype2
= TREE_TYPE (TREE_OPERAND (base2
, 1));
1260 /* If the alias set for a pointer access is zero all bets are off. */
1261 if (base1_alias_set
== -1)
1262 base1_alias_set
= get_deref_alias_set (ptrtype1
);
1263 if (base1_alias_set
== 0)
1265 if (base2_alias_set
== -1)
1266 base2_alias_set
= get_deref_alias_set (ptrtype2
);
1267 if (base2_alias_set
== 0)
1270 /* If both references are through the same type, they do not alias
1271 if the accesses do not overlap. This does extra disambiguation
1272 for mixed/pointer accesses but requires strict aliasing. */
1273 if ((TREE_CODE (base1
) != TARGET_MEM_REF
1274 || (!TMR_INDEX (base1
) && !TMR_INDEX2 (base1
)))
1275 && (TREE_CODE (base2
) != TARGET_MEM_REF
1276 || (!TMR_INDEX (base2
) && !TMR_INDEX2 (base2
)))
1277 && same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (ptrtype1
)) == 1
1278 && same_type_for_tbaa (TREE_TYPE (base2
), TREE_TYPE (ptrtype2
)) == 1
1279 && same_type_for_tbaa (TREE_TYPE (ptrtype1
),
1280 TREE_TYPE (ptrtype2
)) == 1)
1281 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1283 /* Do type-based disambiguation. */
1284 if (base1_alias_set
!= base2_alias_set
1285 && !alias_sets_conflict_p (base1_alias_set
, base2_alias_set
))
1288 /* If either reference is view-converted, give up now. */
1289 if (same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (ptrtype1
)) != 1
1290 || same_type_for_tbaa (TREE_TYPE (base2
), TREE_TYPE (ptrtype2
)) != 1)
1294 && nonoverlapping_component_refs_p (ref1
, ref2
))
1297 /* Do access-path based disambiguation. */
1299 && (handled_component_p (ref1
) || handled_component_p (ref2
)))
1300 return aliasing_component_refs_p (ref1
,
1301 ref1_alias_set
, base1_alias_set
,
1304 ref2_alias_set
, base2_alias_set
,
1305 offset2
, max_size2
, false);
1310 /* Return true, if the two memory references REF1 and REF2 may alias. */
1313 refs_may_alias_p_1 (ao_ref
*ref1
, ao_ref
*ref2
, bool tbaa_p
)
1316 HOST_WIDE_INT offset1
= 0, offset2
= 0;
1317 HOST_WIDE_INT max_size1
= -1, max_size2
= -1;
1318 bool var1_p
, var2_p
, ind1_p
, ind2_p
;
1320 gcc_checking_assert ((!ref1
->ref
1321 || TREE_CODE (ref1
->ref
) == SSA_NAME
1322 || DECL_P (ref1
->ref
)
1323 || TREE_CODE (ref1
->ref
) == STRING_CST
1324 || handled_component_p (ref1
->ref
)
1325 || TREE_CODE (ref1
->ref
) == MEM_REF
1326 || TREE_CODE (ref1
->ref
) == TARGET_MEM_REF
)
1328 || TREE_CODE (ref2
->ref
) == SSA_NAME
1329 || DECL_P (ref2
->ref
)
1330 || TREE_CODE (ref2
->ref
) == STRING_CST
1331 || handled_component_p (ref2
->ref
)
1332 || TREE_CODE (ref2
->ref
) == MEM_REF
1333 || TREE_CODE (ref2
->ref
) == TARGET_MEM_REF
));
1335 /* Decompose the references into their base objects and the access. */
1336 base1
= ao_ref_base (ref1
);
1337 offset1
= ref1
->offset
;
1338 max_size1
= ref1
->max_size
;
1339 base2
= ao_ref_base (ref2
);
1340 offset2
= ref2
->offset
;
1341 max_size2
= ref2
->max_size
;
1343 /* We can end up with registers or constants as bases for example from
1344 *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
1345 which is seen as a struct copy. */
1346 if (TREE_CODE (base1
) == SSA_NAME
1347 || TREE_CODE (base1
) == CONST_DECL
1348 || TREE_CODE (base1
) == CONSTRUCTOR
1349 || TREE_CODE (base1
) == ADDR_EXPR
1350 || CONSTANT_CLASS_P (base1
)
1351 || TREE_CODE (base2
) == SSA_NAME
1352 || TREE_CODE (base2
) == CONST_DECL
1353 || TREE_CODE (base2
) == CONSTRUCTOR
1354 || TREE_CODE (base2
) == ADDR_EXPR
1355 || CONSTANT_CLASS_P (base2
))
1358 /* We can end up referring to code via function and label decls.
1359 As we likely do not properly track code aliases conservatively
1361 if (TREE_CODE (base1
) == FUNCTION_DECL
1362 || TREE_CODE (base1
) == LABEL_DECL
1363 || TREE_CODE (base2
) == FUNCTION_DECL
1364 || TREE_CODE (base2
) == LABEL_DECL
)
1367 /* Two volatile accesses always conflict. */
1368 if (ref1
->volatile_p
1369 && ref2
->volatile_p
)
1372 /* Defer to simple offset based disambiguation if we have
1373 references based on two decls. Do this before defering to
1374 TBAA to handle must-alias cases in conformance with the
1375 GCC extension of allowing type-punning through unions. */
1376 var1_p
= DECL_P (base1
);
1377 var2_p
= DECL_P (base2
);
1378 if (var1_p
&& var2_p
)
1379 return decl_refs_may_alias_p (ref1
->ref
, base1
, offset1
, max_size1
,
1380 ref2
->ref
, base2
, offset2
, max_size2
);
1382 ind1_p
= (TREE_CODE (base1
) == MEM_REF
1383 || TREE_CODE (base1
) == TARGET_MEM_REF
);
1384 ind2_p
= (TREE_CODE (base2
) == MEM_REF
1385 || TREE_CODE (base2
) == TARGET_MEM_REF
);
1387 /* Canonicalize the pointer-vs-decl case. */
1388 if (ind1_p
&& var2_p
)
1393 tmp1
= offset1
; offset1
= offset2
; offset2
= tmp1
;
1394 tmp1
= max_size1
; max_size1
= max_size2
; max_size2
= tmp1
;
1395 tmp2
= base1
; base1
= base2
; base2
= tmp2
;
1396 tmp3
= ref1
; ref1
= ref2
; ref2
= tmp3
;
1403 /* First defer to TBAA if possible. */
1405 && flag_strict_aliasing
1406 && !alias_sets_conflict_p (ao_ref_alias_set (ref1
),
1407 ao_ref_alias_set (ref2
)))
1410 /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators. */
1411 if (var1_p
&& ind2_p
)
1412 return indirect_ref_may_alias_decl_p (ref2
->ref
, base2
,
1414 ao_ref_alias_set (ref2
), -1,
1417 ao_ref_alias_set (ref1
),
1418 ao_ref_base_alias_set (ref1
),
1420 else if (ind1_p
&& ind2_p
)
1421 return indirect_refs_may_alias_p (ref1
->ref
, base1
,
1423 ao_ref_alias_set (ref1
), -1,
1426 ao_ref_alias_set (ref2
), -1,
1429 /* We really do not want to end up here, but returning true is safe. */
1430 #ifdef ENABLE_CHECKING
1438 refs_may_alias_p (tree ref1
, ao_ref
*ref2
)
1441 ao_ref_init (&r1
, ref1
);
1442 return refs_may_alias_p_1 (&r1
, ref2
, true);
1446 refs_may_alias_p (tree ref1
, tree ref2
)
1450 ao_ref_init (&r1
, ref1
);
1451 ao_ref_init (&r2
, ref2
);
1452 res
= refs_may_alias_p_1 (&r1
, &r2
, true);
1454 ++alias_stats
.refs_may_alias_p_may_alias
;
1456 ++alias_stats
.refs_may_alias_p_no_alias
;
1460 /* Returns true if there is a anti-dependence for the STORE that
1461 executes after the LOAD. */
1464 refs_anti_dependent_p (tree load
, tree store
)
1467 ao_ref_init (&r1
, load
);
1468 ao_ref_init (&r2
, store
);
1469 return refs_may_alias_p_1 (&r1
, &r2
, false);
1472 /* Returns true if there is a output dependence for the stores
1473 STORE1 and STORE2. */
1476 refs_output_dependent_p (tree store1
, tree store2
)
1479 ao_ref_init (&r1
, store1
);
1480 ao_ref_init (&r2
, store2
);
1481 return refs_may_alias_p_1 (&r1
, &r2
, false);
1484 /* If the call CALL may use the memory reference REF return true,
1485 otherwise return false. */
1488 ref_maybe_used_by_call_p_1 (gimple call
, ao_ref
*ref
)
1492 int flags
= gimple_call_flags (call
);
1494 /* Const functions without a static chain do not implicitly use memory. */
1495 if (!gimple_call_chain (call
)
1496 && (flags
& (ECF_CONST
|ECF_NOVOPS
)))
1499 base
= ao_ref_base (ref
);
1503 /* A call that is not without side-effects might involve volatile
1504 accesses and thus conflicts with all other volatile accesses. */
1505 if (ref
->volatile_p
)
1508 /* If the reference is based on a decl that is not aliased the call
1509 cannot possibly use it. */
1511 && !may_be_aliased (base
)
1512 /* But local statics can be used through recursion. */
1513 && !is_global_var (base
))
1516 callee
= gimple_call_fndecl (call
);
1518 /* Handle those builtin functions explicitly that do not act as
1519 escape points. See tree-ssa-structalias.c:find_func_aliases
1520 for the list of builtins we might need to handle here. */
1521 if (callee
!= NULL_TREE
1522 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
1523 switch (DECL_FUNCTION_CODE (callee
))
1525 /* All the following functions read memory pointed to by
1526 their second argument. strcat/strncat additionally
1527 reads memory pointed to by the first argument. */
1528 case BUILT_IN_STRCAT
:
1529 case BUILT_IN_STRNCAT
:
1532 ao_ref_init_from_ptr_and_size (&dref
,
1533 gimple_call_arg (call
, 0),
1535 if (refs_may_alias_p_1 (&dref
, ref
, false))
1539 case BUILT_IN_STRCPY
:
1540 case BUILT_IN_STRNCPY
:
1541 case BUILT_IN_MEMCPY
:
1542 case BUILT_IN_MEMMOVE
:
1543 case BUILT_IN_MEMPCPY
:
1544 case BUILT_IN_STPCPY
:
1545 case BUILT_IN_STPNCPY
:
1546 case BUILT_IN_TM_MEMCPY
:
1547 case BUILT_IN_TM_MEMMOVE
:
1550 tree size
= NULL_TREE
;
1551 if (gimple_call_num_args (call
) == 3)
1552 size
= gimple_call_arg (call
, 2);
1553 ao_ref_init_from_ptr_and_size (&dref
,
1554 gimple_call_arg (call
, 1),
1556 return refs_may_alias_p_1 (&dref
, ref
, false);
1558 case BUILT_IN_STRCAT_CHK
:
1559 case BUILT_IN_STRNCAT_CHK
:
1562 ao_ref_init_from_ptr_and_size (&dref
,
1563 gimple_call_arg (call
, 0),
1565 if (refs_may_alias_p_1 (&dref
, ref
, false))
1569 case BUILT_IN_STRCPY_CHK
:
1570 case BUILT_IN_STRNCPY_CHK
:
1571 case BUILT_IN_MEMCPY_CHK
:
1572 case BUILT_IN_MEMMOVE_CHK
:
1573 case BUILT_IN_MEMPCPY_CHK
:
1574 case BUILT_IN_STPCPY_CHK
:
1575 case BUILT_IN_STPNCPY_CHK
:
1578 tree size
= NULL_TREE
;
1579 if (gimple_call_num_args (call
) == 4)
1580 size
= gimple_call_arg (call
, 2);
1581 ao_ref_init_from_ptr_and_size (&dref
,
1582 gimple_call_arg (call
, 1),
1584 return refs_may_alias_p_1 (&dref
, ref
, false);
1586 case BUILT_IN_BCOPY
:
1589 tree size
= gimple_call_arg (call
, 2);
1590 ao_ref_init_from_ptr_and_size (&dref
,
1591 gimple_call_arg (call
, 0),
1593 return refs_may_alias_p_1 (&dref
, ref
, false);
1596 /* The following functions read memory pointed to by their
1598 CASE_BUILT_IN_TM_LOAD (1):
1599 CASE_BUILT_IN_TM_LOAD (2):
1600 CASE_BUILT_IN_TM_LOAD (4):
1601 CASE_BUILT_IN_TM_LOAD (8):
1602 CASE_BUILT_IN_TM_LOAD (FLOAT
):
1603 CASE_BUILT_IN_TM_LOAD (DOUBLE
):
1604 CASE_BUILT_IN_TM_LOAD (LDOUBLE
):
1605 CASE_BUILT_IN_TM_LOAD (M64
):
1606 CASE_BUILT_IN_TM_LOAD (M128
):
1607 CASE_BUILT_IN_TM_LOAD (M256
):
1608 case BUILT_IN_TM_LOG
:
1609 case BUILT_IN_TM_LOG_1
:
1610 case BUILT_IN_TM_LOG_2
:
1611 case BUILT_IN_TM_LOG_4
:
1612 case BUILT_IN_TM_LOG_8
:
1613 case BUILT_IN_TM_LOG_FLOAT
:
1614 case BUILT_IN_TM_LOG_DOUBLE
:
1615 case BUILT_IN_TM_LOG_LDOUBLE
:
1616 case BUILT_IN_TM_LOG_M64
:
1617 case BUILT_IN_TM_LOG_M128
:
1618 case BUILT_IN_TM_LOG_M256
:
1619 return ptr_deref_may_alias_ref_p_1 (gimple_call_arg (call
, 0), ref
);
1621 /* These read memory pointed to by the first argument. */
1622 case BUILT_IN_STRDUP
:
1623 case BUILT_IN_STRNDUP
:
1624 case BUILT_IN_REALLOC
:
1627 tree size
= NULL_TREE
;
1628 if (gimple_call_num_args (call
) == 2)
1629 size
= gimple_call_arg (call
, 1);
1630 ao_ref_init_from_ptr_and_size (&dref
,
1631 gimple_call_arg (call
, 0),
1633 return refs_may_alias_p_1 (&dref
, ref
, false);
1635 /* These read memory pointed to by the first argument. */
1636 case BUILT_IN_INDEX
:
1637 case BUILT_IN_STRCHR
:
1638 case BUILT_IN_STRRCHR
:
1641 ao_ref_init_from_ptr_and_size (&dref
,
1642 gimple_call_arg (call
, 0),
1644 return refs_may_alias_p_1 (&dref
, ref
, false);
1646 /* These read memory pointed to by the first argument with size
1647 in the third argument. */
1648 case BUILT_IN_MEMCHR
:
1651 ao_ref_init_from_ptr_and_size (&dref
,
1652 gimple_call_arg (call
, 0),
1653 gimple_call_arg (call
, 2));
1654 return refs_may_alias_p_1 (&dref
, ref
, false);
1656 /* These read memory pointed to by the first and second arguments. */
1657 case BUILT_IN_STRSTR
:
1658 case BUILT_IN_STRPBRK
:
1661 ao_ref_init_from_ptr_and_size (&dref
,
1662 gimple_call_arg (call
, 0),
1664 if (refs_may_alias_p_1 (&dref
, ref
, false))
1666 ao_ref_init_from_ptr_and_size (&dref
,
1667 gimple_call_arg (call
, 1),
1669 return refs_may_alias_p_1 (&dref
, ref
, false);
1672 /* The following builtins do not read from memory. */
1674 case BUILT_IN_MALLOC
:
1675 case BUILT_IN_POSIX_MEMALIGN
:
1676 case BUILT_IN_ALIGNED_ALLOC
:
1677 case BUILT_IN_CALLOC
:
1678 case BUILT_IN_ALLOCA
:
1679 case BUILT_IN_ALLOCA_WITH_ALIGN
:
1680 case BUILT_IN_STACK_SAVE
:
1681 case BUILT_IN_STACK_RESTORE
:
1682 case BUILT_IN_MEMSET
:
1683 case BUILT_IN_TM_MEMSET
:
1684 case BUILT_IN_MEMSET_CHK
:
1685 case BUILT_IN_FREXP
:
1686 case BUILT_IN_FREXPF
:
1687 case BUILT_IN_FREXPL
:
1688 case BUILT_IN_GAMMA_R
:
1689 case BUILT_IN_GAMMAF_R
:
1690 case BUILT_IN_GAMMAL_R
:
1691 case BUILT_IN_LGAMMA_R
:
1692 case BUILT_IN_LGAMMAF_R
:
1693 case BUILT_IN_LGAMMAL_R
:
1695 case BUILT_IN_MODFF
:
1696 case BUILT_IN_MODFL
:
1697 case BUILT_IN_REMQUO
:
1698 case BUILT_IN_REMQUOF
:
1699 case BUILT_IN_REMQUOL
:
1700 case BUILT_IN_SINCOS
:
1701 case BUILT_IN_SINCOSF
:
1702 case BUILT_IN_SINCOSL
:
1703 case BUILT_IN_ASSUME_ALIGNED
:
1704 case BUILT_IN_VA_END
:
1706 /* __sync_* builtins and some OpenMP builtins act as threading
1708 #undef DEF_SYNC_BUILTIN
1709 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1710 #include "sync-builtins.def"
1711 #undef DEF_SYNC_BUILTIN
1712 case BUILT_IN_GOMP_ATOMIC_START
:
1713 case BUILT_IN_GOMP_ATOMIC_END
:
1714 case BUILT_IN_GOMP_BARRIER
:
1715 case BUILT_IN_GOMP_BARRIER_CANCEL
:
1716 case BUILT_IN_GOMP_TASKWAIT
:
1717 case BUILT_IN_GOMP_TASKGROUP_END
:
1718 case BUILT_IN_GOMP_CRITICAL_START
:
1719 case BUILT_IN_GOMP_CRITICAL_END
:
1720 case BUILT_IN_GOMP_CRITICAL_NAME_START
:
1721 case BUILT_IN_GOMP_CRITICAL_NAME_END
:
1722 case BUILT_IN_GOMP_LOOP_END
:
1723 case BUILT_IN_GOMP_LOOP_END_CANCEL
:
1724 case BUILT_IN_GOMP_ORDERED_START
:
1725 case BUILT_IN_GOMP_ORDERED_END
:
1726 case BUILT_IN_GOMP_SECTIONS_END
:
1727 case BUILT_IN_GOMP_SECTIONS_END_CANCEL
:
1728 case BUILT_IN_GOMP_SINGLE_COPY_START
:
1729 case BUILT_IN_GOMP_SINGLE_COPY_END
:
1733 /* Fallthru to general call handling. */;
1736 /* Check if base is a global static variable that is not read
1738 if (callee
!= NULL_TREE
1739 && TREE_CODE (base
) == VAR_DECL
1740 && TREE_STATIC (base
))
1742 struct cgraph_node
*node
= cgraph_node::get (callee
);
1745 /* FIXME: Callee can be an OMP builtin that does not have a call graph
1746 node yet. We should enforce that there are nodes for all decls in the
1747 IL and remove this check instead. */
1749 && (not_read
= ipa_reference_get_not_read_global (node
))
1750 && bitmap_bit_p (not_read
, DECL_UID (base
)))
1754 /* Check if the base variable is call-used. */
1757 if (pt_solution_includes (gimple_call_use_set (call
), base
))
1760 else if ((TREE_CODE (base
) == MEM_REF
1761 || TREE_CODE (base
) == TARGET_MEM_REF
)
1762 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
1764 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (TREE_OPERAND (base
, 0));
1768 if (pt_solutions_intersect (gimple_call_use_set (call
), &pi
->pt
))
1774 /* Inspect call arguments for passed-by-value aliases. */
1776 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1778 tree op
= gimple_call_arg (call
, i
);
1779 int flags
= gimple_call_arg_flags (call
, i
);
1781 if (flags
& EAF_UNUSED
)
1784 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
1785 op
= TREE_OPERAND (op
, 0);
1787 if (TREE_CODE (op
) != SSA_NAME
1788 && !is_gimple_min_invariant (op
))
1791 ao_ref_init (&r
, op
);
1792 if (refs_may_alias_p_1 (&r
, ref
, true))
1801 ref_maybe_used_by_call_p (gimple call
, ao_ref
*ref
)
1804 res
= ref_maybe_used_by_call_p_1 (call
, ref
);
1806 ++alias_stats
.ref_maybe_used_by_call_p_may_alias
;
1808 ++alias_stats
.ref_maybe_used_by_call_p_no_alias
;
1813 /* If the statement STMT may use the memory reference REF return
1814 true, otherwise return false. */
1817 ref_maybe_used_by_stmt_p (gimple stmt
, ao_ref
*ref
)
1819 if (is_gimple_assign (stmt
))
1823 /* All memory assign statements are single. */
1824 if (!gimple_assign_single_p (stmt
))
1827 rhs
= gimple_assign_rhs1 (stmt
);
1828 if (is_gimple_reg (rhs
)
1829 || is_gimple_min_invariant (rhs
)
1830 || gimple_assign_rhs_code (stmt
) == CONSTRUCTOR
)
1833 return refs_may_alias_p (rhs
, ref
);
1835 else if (is_gimple_call (stmt
))
1836 return ref_maybe_used_by_call_p (stmt
, ref
);
1837 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
1839 tree retval
= gimple_return_retval (stmt
);
1841 && TREE_CODE (retval
) != SSA_NAME
1842 && !is_gimple_min_invariant (retval
)
1843 && refs_may_alias_p (retval
, ref
))
1845 /* If ref escapes the function then the return acts as a use. */
1846 tree base
= ao_ref_base (ref
);
1849 else if (DECL_P (base
))
1850 return is_global_var (base
);
1851 else if (TREE_CODE (base
) == MEM_REF
1852 || TREE_CODE (base
) == TARGET_MEM_REF
)
1853 return ptr_deref_may_alias_global_p (TREE_OPERAND (base
, 0));
1861 ref_maybe_used_by_stmt_p (gimple stmt
, tree ref
)
1864 ao_ref_init (&r
, ref
);
1865 return ref_maybe_used_by_stmt_p (stmt
, &r
);
1868 /* If the call in statement CALL may clobber the memory reference REF
1869 return true, otherwise return false. */
1872 call_may_clobber_ref_p_1 (gimple call
, ao_ref
*ref
)
1877 /* If the call is pure or const it cannot clobber anything. */
1878 if (gimple_call_flags (call
)
1879 & (ECF_PURE
|ECF_CONST
|ECF_LOOPING_CONST_OR_PURE
|ECF_NOVOPS
))
1882 base
= ao_ref_base (ref
);
1886 if (TREE_CODE (base
) == SSA_NAME
1887 || CONSTANT_CLASS_P (base
))
1890 /* A call that is not without side-effects might involve volatile
1891 accesses and thus conflicts with all other volatile accesses. */
1892 if (ref
->volatile_p
)
1895 /* If the reference is based on a decl that is not aliased the call
1896 cannot possibly clobber it. */
1898 && !may_be_aliased (base
)
1899 /* But local non-readonly statics can be modified through recursion
1900 or the call may implement a threading barrier which we must
1901 treat as may-def. */
1902 && (TREE_READONLY (base
)
1903 || !is_global_var (base
)))
1906 callee
= gimple_call_fndecl (call
);
1908 /* Handle those builtin functions explicitly that do not act as
1909 escape points. See tree-ssa-structalias.c:find_func_aliases
1910 for the list of builtins we might need to handle here. */
1911 if (callee
!= NULL_TREE
1912 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
1913 switch (DECL_FUNCTION_CODE (callee
))
1915 /* All the following functions clobber memory pointed to by
1916 their first argument. */
1917 case BUILT_IN_STRCPY
:
1918 case BUILT_IN_STRNCPY
:
1919 case BUILT_IN_MEMCPY
:
1920 case BUILT_IN_MEMMOVE
:
1921 case BUILT_IN_MEMPCPY
:
1922 case BUILT_IN_STPCPY
:
1923 case BUILT_IN_STPNCPY
:
1924 case BUILT_IN_STRCAT
:
1925 case BUILT_IN_STRNCAT
:
1926 case BUILT_IN_MEMSET
:
1927 case BUILT_IN_TM_MEMSET
:
1928 CASE_BUILT_IN_TM_STORE (1):
1929 CASE_BUILT_IN_TM_STORE (2):
1930 CASE_BUILT_IN_TM_STORE (4):
1931 CASE_BUILT_IN_TM_STORE (8):
1932 CASE_BUILT_IN_TM_STORE (FLOAT
):
1933 CASE_BUILT_IN_TM_STORE (DOUBLE
):
1934 CASE_BUILT_IN_TM_STORE (LDOUBLE
):
1935 CASE_BUILT_IN_TM_STORE (M64
):
1936 CASE_BUILT_IN_TM_STORE (M128
):
1937 CASE_BUILT_IN_TM_STORE (M256
):
1938 case BUILT_IN_TM_MEMCPY
:
1939 case BUILT_IN_TM_MEMMOVE
:
1942 tree size
= NULL_TREE
;
1943 /* Don't pass in size for strncat, as the maximum size
1944 is strlen (dest) + n + 1 instead of n, resp.
1945 n + 1 at dest + strlen (dest), but strlen (dest) isn't
1947 if (gimple_call_num_args (call
) == 3
1948 && DECL_FUNCTION_CODE (callee
) != BUILT_IN_STRNCAT
)
1949 size
= gimple_call_arg (call
, 2);
1950 ao_ref_init_from_ptr_and_size (&dref
,
1951 gimple_call_arg (call
, 0),
1953 return refs_may_alias_p_1 (&dref
, ref
, false);
1955 case BUILT_IN_STRCPY_CHK
:
1956 case BUILT_IN_STRNCPY_CHK
:
1957 case BUILT_IN_MEMCPY_CHK
:
1958 case BUILT_IN_MEMMOVE_CHK
:
1959 case BUILT_IN_MEMPCPY_CHK
:
1960 case BUILT_IN_STPCPY_CHK
:
1961 case BUILT_IN_STPNCPY_CHK
:
1962 case BUILT_IN_STRCAT_CHK
:
1963 case BUILT_IN_STRNCAT_CHK
:
1964 case BUILT_IN_MEMSET_CHK
:
1967 tree size
= NULL_TREE
;
1968 /* Don't pass in size for __strncat_chk, as the maximum size
1969 is strlen (dest) + n + 1 instead of n, resp.
1970 n + 1 at dest + strlen (dest), but strlen (dest) isn't
1972 if (gimple_call_num_args (call
) == 4
1973 && DECL_FUNCTION_CODE (callee
) != BUILT_IN_STRNCAT_CHK
)
1974 size
= gimple_call_arg (call
, 2);
1975 ao_ref_init_from_ptr_and_size (&dref
,
1976 gimple_call_arg (call
, 0),
1978 return refs_may_alias_p_1 (&dref
, ref
, false);
1980 case BUILT_IN_BCOPY
:
1983 tree size
= gimple_call_arg (call
, 2);
1984 ao_ref_init_from_ptr_and_size (&dref
,
1985 gimple_call_arg (call
, 1),
1987 return refs_may_alias_p_1 (&dref
, ref
, false);
1989 /* Allocating memory does not have any side-effects apart from
1990 being the definition point for the pointer. */
1991 case BUILT_IN_MALLOC
:
1992 case BUILT_IN_ALIGNED_ALLOC
:
1993 case BUILT_IN_CALLOC
:
1994 case BUILT_IN_STRDUP
:
1995 case BUILT_IN_STRNDUP
:
1996 /* Unix98 specifies that errno is set on allocation failure. */
1998 && targetm
.ref_may_alias_errno (ref
))
2001 case BUILT_IN_STACK_SAVE
:
2002 case BUILT_IN_ALLOCA
:
2003 case BUILT_IN_ALLOCA_WITH_ALIGN
:
2004 case BUILT_IN_ASSUME_ALIGNED
:
2006 /* But posix_memalign stores a pointer into the memory pointed to
2007 by its first argument. */
2008 case BUILT_IN_POSIX_MEMALIGN
:
2010 tree ptrptr
= gimple_call_arg (call
, 0);
2012 ao_ref_init_from_ptr_and_size (&dref
, ptrptr
,
2013 TYPE_SIZE_UNIT (ptr_type_node
));
2014 return (refs_may_alias_p_1 (&dref
, ref
, false)
2016 && targetm
.ref_may_alias_errno (ref
)));
2018 /* Freeing memory kills the pointed-to memory. More importantly
2019 the call has to serve as a barrier for moving loads and stores
2022 case BUILT_IN_VA_END
:
2024 tree ptr
= gimple_call_arg (call
, 0);
2025 return ptr_deref_may_alias_ref_p_1 (ptr
, ref
);
2027 /* Realloc serves both as allocation point and deallocation point. */
2028 case BUILT_IN_REALLOC
:
2030 tree ptr
= gimple_call_arg (call
, 0);
2031 /* Unix98 specifies that errno is set on allocation failure. */
2032 return ((flag_errno_math
2033 && targetm
.ref_may_alias_errno (ref
))
2034 || ptr_deref_may_alias_ref_p_1 (ptr
, ref
));
2036 case BUILT_IN_GAMMA_R
:
2037 case BUILT_IN_GAMMAF_R
:
2038 case BUILT_IN_GAMMAL_R
:
2039 case BUILT_IN_LGAMMA_R
:
2040 case BUILT_IN_LGAMMAF_R
:
2041 case BUILT_IN_LGAMMAL_R
:
2043 tree out
= gimple_call_arg (call
, 1);
2044 if (ptr_deref_may_alias_ref_p_1 (out
, ref
))
2046 if (flag_errno_math
)
2050 case BUILT_IN_FREXP
:
2051 case BUILT_IN_FREXPF
:
2052 case BUILT_IN_FREXPL
:
2054 case BUILT_IN_MODFF
:
2055 case BUILT_IN_MODFL
:
2057 tree out
= gimple_call_arg (call
, 1);
2058 return ptr_deref_may_alias_ref_p_1 (out
, ref
);
2060 case BUILT_IN_REMQUO
:
2061 case BUILT_IN_REMQUOF
:
2062 case BUILT_IN_REMQUOL
:
2064 tree out
= gimple_call_arg (call
, 2);
2065 if (ptr_deref_may_alias_ref_p_1 (out
, ref
))
2067 if (flag_errno_math
)
2071 case BUILT_IN_SINCOS
:
2072 case BUILT_IN_SINCOSF
:
2073 case BUILT_IN_SINCOSL
:
2075 tree sin
= gimple_call_arg (call
, 1);
2076 tree cos
= gimple_call_arg (call
, 2);
2077 return (ptr_deref_may_alias_ref_p_1 (sin
, ref
)
2078 || ptr_deref_may_alias_ref_p_1 (cos
, ref
));
2080 /* __sync_* builtins and some OpenMP builtins act as threading
2082 #undef DEF_SYNC_BUILTIN
2083 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
2084 #include "sync-builtins.def"
2085 #undef DEF_SYNC_BUILTIN
2086 case BUILT_IN_GOMP_ATOMIC_START
:
2087 case BUILT_IN_GOMP_ATOMIC_END
:
2088 case BUILT_IN_GOMP_BARRIER
:
2089 case BUILT_IN_GOMP_BARRIER_CANCEL
:
2090 case BUILT_IN_GOMP_TASKWAIT
:
2091 case BUILT_IN_GOMP_TASKGROUP_END
:
2092 case BUILT_IN_GOMP_CRITICAL_START
:
2093 case BUILT_IN_GOMP_CRITICAL_END
:
2094 case BUILT_IN_GOMP_CRITICAL_NAME_START
:
2095 case BUILT_IN_GOMP_CRITICAL_NAME_END
:
2096 case BUILT_IN_GOMP_LOOP_END
:
2097 case BUILT_IN_GOMP_LOOP_END_CANCEL
:
2098 case BUILT_IN_GOMP_ORDERED_START
:
2099 case BUILT_IN_GOMP_ORDERED_END
:
2100 case BUILT_IN_GOMP_SECTIONS_END
:
2101 case BUILT_IN_GOMP_SECTIONS_END_CANCEL
:
2102 case BUILT_IN_GOMP_SINGLE_COPY_START
:
2103 case BUILT_IN_GOMP_SINGLE_COPY_END
:
2106 /* Fallthru to general call handling. */;
2109 /* Check if base is a global static variable that is not written
2111 if (callee
!= NULL_TREE
2112 && TREE_CODE (base
) == VAR_DECL
2113 && TREE_STATIC (base
))
2115 struct cgraph_node
*node
= cgraph_node::get (callee
);
2119 && (not_written
= ipa_reference_get_not_written_global (node
))
2120 && bitmap_bit_p (not_written
, DECL_UID (base
)))
2124 /* Check if the base variable is call-clobbered. */
2126 return pt_solution_includes (gimple_call_clobber_set (call
), base
);
2127 else if ((TREE_CODE (base
) == MEM_REF
2128 || TREE_CODE (base
) == TARGET_MEM_REF
)
2129 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
2131 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (TREE_OPERAND (base
, 0));
2135 return pt_solutions_intersect (gimple_call_clobber_set (call
), &pi
->pt
);
2141 /* If the call in statement CALL may clobber the memory reference REF
2142 return true, otherwise return false. */
2145 call_may_clobber_ref_p (gimple call
, tree ref
)
2149 ao_ref_init (&r
, ref
);
2150 res
= call_may_clobber_ref_p_1 (call
, &r
);
2152 ++alias_stats
.call_may_clobber_ref_p_may_alias
;
2154 ++alias_stats
.call_may_clobber_ref_p_no_alias
;
2159 /* If the statement STMT may clobber the memory reference REF return true,
2160 otherwise return false. */
2163 stmt_may_clobber_ref_p_1 (gimple stmt
, ao_ref
*ref
)
2165 if (is_gimple_call (stmt
))
2167 tree lhs
= gimple_call_lhs (stmt
);
2169 && TREE_CODE (lhs
) != SSA_NAME
)
2172 ao_ref_init (&r
, lhs
);
2173 if (refs_may_alias_p_1 (ref
, &r
, true))
2177 return call_may_clobber_ref_p_1 (stmt
, ref
);
2179 else if (gimple_assign_single_p (stmt
))
2181 tree lhs
= gimple_assign_lhs (stmt
);
2182 if (TREE_CODE (lhs
) != SSA_NAME
)
2185 ao_ref_init (&r
, lhs
);
2186 return refs_may_alias_p_1 (ref
, &r
, true);
2189 else if (gimple_code (stmt
) == GIMPLE_ASM
)
2196 stmt_may_clobber_ref_p (gimple stmt
, tree ref
)
2199 ao_ref_init (&r
, ref
);
2200 return stmt_may_clobber_ref_p_1 (stmt
, &r
);
2203 /* If STMT kills the memory reference REF return true, otherwise
2207 stmt_kills_ref_p (gimple stmt
, ao_ref
*ref
)
2209 if (!ao_ref_base (ref
))
2212 if (gimple_has_lhs (stmt
)
2213 && TREE_CODE (gimple_get_lhs (stmt
)) != SSA_NAME
2214 /* The assignment is not necessarily carried out if it can throw
2215 and we can catch it in the current function where we could inspect
2217 ??? We only need to care about the RHS throwing. For aggregate
2218 assignments or similar calls and non-call exceptions the LHS
2219 might throw as well. */
2220 && !stmt_can_throw_internal (stmt
))
2222 tree lhs
= gimple_get_lhs (stmt
);
2223 /* If LHS is literally a base of the access we are done. */
2226 tree base
= ref
->ref
;
2227 if (handled_component_p (base
))
2229 tree saved_lhs0
= NULL_TREE
;
2230 if (handled_component_p (lhs
))
2232 saved_lhs0
= TREE_OPERAND (lhs
, 0);
2233 TREE_OPERAND (lhs
, 0) = integer_zero_node
;
2237 /* Just compare the outermost handled component, if
2238 they are equal we have found a possible common
2240 tree saved_base0
= TREE_OPERAND (base
, 0);
2241 TREE_OPERAND (base
, 0) = integer_zero_node
;
2242 bool res
= operand_equal_p (lhs
, base
, 0);
2243 TREE_OPERAND (base
, 0) = saved_base0
;
2246 /* Otherwise drop handled components of the access. */
2249 while (handled_component_p (base
));
2251 TREE_OPERAND (lhs
, 0) = saved_lhs0
;
2253 /* Finally check if lhs is equal or equal to the base candidate
2255 if (operand_equal_p (lhs
, base
, 0))
2259 /* Now look for non-literal equal bases with the restriction of
2260 handling constant offset and size. */
2261 /* For a must-alias check we need to be able to constrain
2262 the access properly. */
2263 if (ref
->max_size
== -1)
2265 HOST_WIDE_INT size
, offset
, max_size
, ref_offset
= ref
->offset
;
2266 tree base
= get_ref_base_and_extent (lhs
, &offset
, &size
, &max_size
);
2267 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
2268 so base == ref->base does not always hold. */
2269 if (base
!= ref
->base
)
2271 /* If both base and ref->base are MEM_REFs, only compare the
2272 first operand, and if the second operand isn't equal constant,
2273 try to add the offsets into offset and ref_offset. */
2274 if (TREE_CODE (base
) == MEM_REF
&& TREE_CODE (ref
->base
) == MEM_REF
2275 && TREE_OPERAND (base
, 0) == TREE_OPERAND (ref
->base
, 0))
2277 if (!tree_int_cst_equal (TREE_OPERAND (base
, 1),
2278 TREE_OPERAND (ref
->base
, 1)))
2280 offset_int off1
= mem_ref_offset (base
);
2281 off1
= wi::lshift (off1
, LOG2_BITS_PER_UNIT
);
2283 offset_int off2
= mem_ref_offset (ref
->base
);
2284 off2
= wi::lshift (off2
, LOG2_BITS_PER_UNIT
);
2286 if (wi::fits_shwi_p (off1
) && wi::fits_shwi_p (off2
))
2288 offset
= off1
.to_shwi ();
2289 ref_offset
= off2
.to_shwi ();
2298 /* For a must-alias check we need to be able to constrain
2299 the access properly. */
2300 if (size
!= -1 && size
== max_size
)
2302 if (offset
<= ref_offset
2303 && offset
+ size
>= ref_offset
+ ref
->max_size
)
2308 if (is_gimple_call (stmt
))
2310 tree callee
= gimple_call_fndecl (stmt
);
2311 if (callee
!= NULL_TREE
2312 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
2313 switch (DECL_FUNCTION_CODE (callee
))
2317 tree ptr
= gimple_call_arg (stmt
, 0);
2318 tree base
= ao_ref_base (ref
);
2319 if (base
&& TREE_CODE (base
) == MEM_REF
2320 && TREE_OPERAND (base
, 0) == ptr
)
2325 case BUILT_IN_MEMCPY
:
2326 case BUILT_IN_MEMPCPY
:
2327 case BUILT_IN_MEMMOVE
:
2328 case BUILT_IN_MEMSET
:
2329 case BUILT_IN_MEMCPY_CHK
:
2330 case BUILT_IN_MEMPCPY_CHK
:
2331 case BUILT_IN_MEMMOVE_CHK
:
2332 case BUILT_IN_MEMSET_CHK
:
2334 /* For a must-alias check we need to be able to constrain
2335 the access properly. */
2336 if (ref
->max_size
== -1)
2338 tree dest
= gimple_call_arg (stmt
, 0);
2339 tree len
= gimple_call_arg (stmt
, 2);
2340 if (!tree_fits_shwi_p (len
))
2342 tree rbase
= ref
->base
;
2343 offset_int roffset
= ref
->offset
;
2345 ao_ref_init_from_ptr_and_size (&dref
, dest
, len
);
2346 tree base
= ao_ref_base (&dref
);
2347 offset_int offset
= dref
.offset
;
2348 if (!base
|| dref
.size
== -1)
2350 if (TREE_CODE (base
) == MEM_REF
)
2352 if (TREE_CODE (rbase
) != MEM_REF
)
2354 // Compare pointers.
2355 offset
+= wi::lshift (mem_ref_offset (base
),
2356 LOG2_BITS_PER_UNIT
);
2357 roffset
+= wi::lshift (mem_ref_offset (rbase
),
2358 LOG2_BITS_PER_UNIT
);
2359 base
= TREE_OPERAND (base
, 0);
2360 rbase
= TREE_OPERAND (rbase
, 0);
2363 && wi::les_p (offset
, roffset
)
2364 && wi::les_p (roffset
+ ref
->max_size
,
2365 offset
+ wi::lshift (wi::to_offset (len
),
2366 LOG2_BITS_PER_UNIT
)))
2371 case BUILT_IN_VA_END
:
2373 tree ptr
= gimple_call_arg (stmt
, 0);
2374 if (TREE_CODE (ptr
) == ADDR_EXPR
)
2376 tree base
= ao_ref_base (ref
);
2377 if (TREE_OPERAND (ptr
, 0) == base
)
2390 stmt_kills_ref_p (gimple stmt
, tree ref
)
2393 ao_ref_init (&r
, ref
);
2394 return stmt_kills_ref_p (stmt
, &r
);
2398 /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
2399 TARGET or a statement clobbering the memory reference REF in which
2400 case false is returned. The walk starts with VUSE, one argument of PHI. */
2403 maybe_skip_until (gimple phi
, tree target
, ao_ref
*ref
,
2404 tree vuse
, unsigned int *cnt
, bitmap
*visited
,
2405 bool abort_on_visited
,
2406 void *(*translate
)(ao_ref
*, tree
, void *, bool),
2409 basic_block bb
= gimple_bb (phi
);
2412 *visited
= BITMAP_ALLOC (NULL
);
2414 bitmap_set_bit (*visited
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
2416 /* Walk until we hit the target. */
2417 while (vuse
!= target
)
2419 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
2420 /* Recurse for PHI nodes. */
2421 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2423 /* An already visited PHI node ends the walk successfully. */
2424 if (bitmap_bit_p (*visited
, SSA_NAME_VERSION (PHI_RESULT (def_stmt
))))
2425 return !abort_on_visited
;
2426 vuse
= get_continuation_for_phi (def_stmt
, ref
, cnt
,
2427 visited
, abort_on_visited
,
2433 else if (gimple_nop_p (def_stmt
))
2437 /* A clobbering statement or the end of the IL ends it failing. */
2439 if (stmt_may_clobber_ref_p_1 (def_stmt
, ref
))
2442 && (*translate
) (ref
, vuse
, data
, true) == NULL
)
2448 /* If we reach a new basic-block see if we already skipped it
2449 in a previous walk that ended successfully. */
2450 if (gimple_bb (def_stmt
) != bb
)
2452 if (!bitmap_set_bit (*visited
, SSA_NAME_VERSION (vuse
)))
2453 return !abort_on_visited
;
2454 bb
= gimple_bb (def_stmt
);
2456 vuse
= gimple_vuse (def_stmt
);
2461 /* For two PHI arguments ARG0 and ARG1 try to skip non-aliasing code
2462 until we hit the phi argument definition that dominates the other one.
2463 Return that, or NULL_TREE if there is no such definition. */
2466 get_continuation_for_phi_1 (gimple phi
, tree arg0
, tree arg1
,
2467 ao_ref
*ref
, unsigned int *cnt
,
2468 bitmap
*visited
, bool abort_on_visited
,
2469 void *(*translate
)(ao_ref
*, tree
, void *, bool),
2472 gimple def0
= SSA_NAME_DEF_STMT (arg0
);
2473 gimple def1
= SSA_NAME_DEF_STMT (arg1
);
2478 else if (gimple_nop_p (def0
)
2479 || (!gimple_nop_p (def1
)
2480 && dominated_by_p (CDI_DOMINATORS
,
2481 gimple_bb (def1
), gimple_bb (def0
))))
2483 if (maybe_skip_until (phi
, arg0
, ref
, arg1
, cnt
,
2484 visited
, abort_on_visited
, translate
, data
))
2487 else if (gimple_nop_p (def1
)
2488 || dominated_by_p (CDI_DOMINATORS
,
2489 gimple_bb (def0
), gimple_bb (def1
)))
2491 if (maybe_skip_until (phi
, arg1
, ref
, arg0
, cnt
,
2492 visited
, abort_on_visited
, translate
, data
))
2495 /* Special case of a diamond:
2497 goto (cond) ? L1 : L2
2498 L1: store1 = ... #MEM_2 = vuse(MEM_1)
2500 L2: store2 = ... #MEM_3 = vuse(MEM_1)
2501 L3: MEM_4 = PHI<MEM_2, MEM_3>
2502 We were called with the PHI at L3, MEM_2 and MEM_3 don't
2503 dominate each other, but still we can easily skip this PHI node
2504 if we recognize that the vuse MEM operand is the same for both,
2505 and that we can skip both statements (they don't clobber us).
2506 This is still linear. Don't use maybe_skip_until, that might
2507 potentially be slow. */
2508 else if ((common_vuse
= gimple_vuse (def0
))
2509 && common_vuse
== gimple_vuse (def1
))
2512 if ((!stmt_may_clobber_ref_p_1 (def0
, ref
)
2514 && (*translate
) (ref
, arg0
, data
, true) == NULL
))
2515 && (!stmt_may_clobber_ref_p_1 (def1
, ref
)
2517 && (*translate
) (ref
, arg1
, data
, true) == NULL
)))
2525 /* Starting from a PHI node for the virtual operand of the memory reference
2526 REF find a continuation virtual operand that allows to continue walking
2527 statements dominating PHI skipping only statements that cannot possibly
2528 clobber REF. Increments *CNT for each alias disambiguation done.
2529 Returns NULL_TREE if no suitable virtual operand can be found. */
2532 get_continuation_for_phi (gimple phi
, ao_ref
*ref
,
2533 unsigned int *cnt
, bitmap
*visited
,
2534 bool abort_on_visited
,
2535 void *(*translate
)(ao_ref
*, tree
, void *, bool),
2538 unsigned nargs
= gimple_phi_num_args (phi
);
2540 /* Through a single-argument PHI we can simply look through. */
2542 return PHI_ARG_DEF (phi
, 0);
2544 /* For two or more arguments try to pairwise skip non-aliasing code
2545 until we hit the phi argument definition that dominates the other one. */
2546 else if (nargs
>= 2)
2551 /* Find a candidate for the virtual operand which definition
2552 dominates those of all others. */
2553 arg0
= PHI_ARG_DEF (phi
, 0);
2554 if (!SSA_NAME_IS_DEFAULT_DEF (arg0
))
2555 for (i
= 1; i
< nargs
; ++i
)
2557 arg1
= PHI_ARG_DEF (phi
, i
);
2558 if (SSA_NAME_IS_DEFAULT_DEF (arg1
))
2563 if (dominated_by_p (CDI_DOMINATORS
,
2564 gimple_bb (SSA_NAME_DEF_STMT (arg0
)),
2565 gimple_bb (SSA_NAME_DEF_STMT (arg1
))))
2569 /* Then pairwise reduce against the found candidate. */
2570 for (i
= 0; i
< nargs
; ++i
)
2572 arg1
= PHI_ARG_DEF (phi
, i
);
2573 arg0
= get_continuation_for_phi_1 (phi
, arg0
, arg1
, ref
,
2574 cnt
, visited
, abort_on_visited
,
2586 /* Based on the memory reference REF and its virtual use VUSE call
2587 WALKER for each virtual use that is equivalent to VUSE, including VUSE
2588 itself. That is, for each virtual use for which its defining statement
2589 does not clobber REF.
2591 WALKER is called with REF, the current virtual use and DATA. If
2592 WALKER returns non-NULL the walk stops and its result is returned.
2593 At the end of a non-successful walk NULL is returned.
2595 TRANSLATE if non-NULL is called with a pointer to REF, the virtual
2596 use which definition is a statement that may clobber REF and DATA.
2597 If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
2598 If TRANSLATE returns non-NULL the walk stops and its result is returned.
2599 If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
2600 to adjust REF and *DATA to make that valid.
2602 TODO: Cache the vector of equivalent vuses per ref, vuse pair. */
2605 walk_non_aliased_vuses (ao_ref
*ref
, tree vuse
,
2606 void *(*walker
)(ao_ref
*, tree
, unsigned int, void *),
2607 void *(*translate
)(ao_ref
*, tree
, void *, bool),
2610 bitmap visited
= NULL
;
2612 unsigned int cnt
= 0;
2613 bool translated
= false;
2615 timevar_push (TV_ALIAS_STMT_WALK
);
2621 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
2622 res
= (*walker
) (ref
, vuse
, cnt
, data
);
2624 if (res
== (void *)-1)
2629 /* Lookup succeeded. */
2630 else if (res
!= NULL
)
2633 def_stmt
= SSA_NAME_DEF_STMT (vuse
);
2634 if (gimple_nop_p (def_stmt
))
2636 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2637 vuse
= get_continuation_for_phi (def_stmt
, ref
, &cnt
,
2638 &visited
, translated
, translate
, data
);
2642 if (stmt_may_clobber_ref_p_1 (def_stmt
, ref
))
2646 res
= (*translate
) (ref
, vuse
, data
, false);
2647 /* Failed lookup and translation. */
2648 if (res
== (void *)-1)
2653 /* Lookup succeeded. */
2654 else if (res
!= NULL
)
2656 /* Translation succeeded, continue walking. */
2659 vuse
= gimple_vuse (def_stmt
);
2665 BITMAP_FREE (visited
);
2667 timevar_pop (TV_ALIAS_STMT_WALK
);
2673 /* Based on the memory reference REF call WALKER for each vdef which
2674 defining statement may clobber REF, starting with VDEF. If REF
2675 is NULL_TREE, each defining statement is visited.
2677 WALKER is called with REF, the current vdef and DATA. If WALKER
2678 returns true the walk is stopped, otherwise it continues.
2680 If function entry is reached, FUNCTION_ENTRY_REACHED is set to true.
2681 The pointer may be NULL and then we do not track this information.
2683 At PHI nodes walk_aliased_vdefs forks into one walk for reach
2684 PHI argument (but only one walk continues on merge points), the
2685 return value is true if any of the walks was successful.
2687 The function returns the number of statements walked. */
2690 walk_aliased_vdefs_1 (ao_ref
*ref
, tree vdef
,
2691 bool (*walker
)(ao_ref
*, tree
, void *), void *data
,
2692 bitmap
*visited
, unsigned int cnt
,
2693 bool *function_entry_reached
)
2697 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
2700 && !bitmap_set_bit (*visited
, SSA_NAME_VERSION (vdef
)))
2703 if (gimple_nop_p (def_stmt
))
2705 if (function_entry_reached
)
2706 *function_entry_reached
= true;
2709 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2713 *visited
= BITMAP_ALLOC (NULL
);
2714 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); ++i
)
2715 cnt
+= walk_aliased_vdefs_1 (ref
, gimple_phi_arg_def (def_stmt
, i
),
2716 walker
, data
, visited
, 0,
2717 function_entry_reached
);
2721 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
2724 || stmt_may_clobber_ref_p_1 (def_stmt
, ref
))
2725 && (*walker
) (ref
, vdef
, data
))
2728 vdef
= gimple_vuse (def_stmt
);
2734 walk_aliased_vdefs (ao_ref
*ref
, tree vdef
,
2735 bool (*walker
)(ao_ref
*, tree
, void *), void *data
,
2737 bool *function_entry_reached
)
2739 bitmap local_visited
= NULL
;
2742 timevar_push (TV_ALIAS_STMT_WALK
);
2744 if (function_entry_reached
)
2745 *function_entry_reached
= false;
2747 ret
= walk_aliased_vdefs_1 (ref
, vdef
, walker
, data
,
2748 visited
? visited
: &local_visited
, 0,
2749 function_entry_reached
);
2751 BITMAP_FREE (local_visited
);
2753 timevar_pop (TV_ALIAS_STMT_WALK
);