1 /* Alias analysis for trees.
2 Copyright (C) 2004-2013 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 */
31 #include "langhooks.h"
34 #include "tree-pretty-print.h"
37 #include "gimple-ssa.h"
38 #include "stringpool.h"
39 #include "tree-ssanames.h"
42 #include "tree-inline.h"
45 #include "pointer-set.h"
46 #include "alloc-pool.h"
47 #include "tree-ssa-alias.h"
48 #include "ipa-reference.h"
50 /* Broad overview of how alias analysis on gimple works:
52 Statements clobbering or using memory are linked through the
53 virtual operand factored use-def chain. The virtual operand
54 is unique per function, its symbol is accessible via gimple_vop (cfun).
55 Virtual operands are used for efficiently walking memory statements
56 in the gimple IL and are useful for things like value-numbering as
57 a generation count for memory references.
59 SSA_NAME pointers may have associated points-to information
60 accessible via the SSA_NAME_PTR_INFO macro. Flow-insensitive
61 points-to information is (re-)computed by the TODO_rebuild_alias
62 pass manager todo. Points-to information is also used for more
63 precise tracking of call-clobbered and call-used variables and
64 related disambiguations.
66 This file contains functions for disambiguating memory references,
67 the so called alias-oracle and tools for walking of the gimple IL.
69 The main alias-oracle entry-points are
71 bool stmt_may_clobber_ref_p (gimple, tree)
73 This function queries if a statement may invalidate (parts of)
74 the memory designated by the reference tree argument.
76 bool ref_maybe_used_by_stmt_p (gimple, tree)
78 This function queries if a statement may need (parts of) the
79 memory designated by the reference tree argument.
81 There are variants of these functions that only handle the call
82 part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
83 Note that these do not disambiguate against a possible call lhs.
85 bool refs_may_alias_p (tree, tree)
87 This function tries to disambiguate two reference trees.
89 bool ptr_deref_may_alias_global_p (tree)
91 This function queries if dereferencing a pointer variable may
94 More low-level disambiguators are available and documented in
95 this file. Low-level disambiguators dealing with points-to
96 information are in tree-ssa-structalias.c. */
99 /* Query statistics for the different low-level disambiguators.
100 A high-level query may trigger multiple of them. */
103 unsigned HOST_WIDE_INT refs_may_alias_p_may_alias
;
104 unsigned HOST_WIDE_INT refs_may_alias_p_no_alias
;
105 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias
;
106 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias
;
107 unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias
;
108 unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias
;
112 dump_alias_stats (FILE *s
)
114 fprintf (s
, "\nAlias oracle query stats:\n");
115 fprintf (s
, " refs_may_alias_p: "
116 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
117 HOST_WIDE_INT_PRINT_DEC
" queries\n",
118 alias_stats
.refs_may_alias_p_no_alias
,
119 alias_stats
.refs_may_alias_p_no_alias
120 + alias_stats
.refs_may_alias_p_may_alias
);
121 fprintf (s
, " ref_maybe_used_by_call_p: "
122 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
123 HOST_WIDE_INT_PRINT_DEC
" queries\n",
124 alias_stats
.ref_maybe_used_by_call_p_no_alias
,
125 alias_stats
.refs_may_alias_p_no_alias
126 + alias_stats
.ref_maybe_used_by_call_p_may_alias
);
127 fprintf (s
, " call_may_clobber_ref_p: "
128 HOST_WIDE_INT_PRINT_DEC
" disambiguations, "
129 HOST_WIDE_INT_PRINT_DEC
" queries\n",
130 alias_stats
.call_may_clobber_ref_p_no_alias
,
131 alias_stats
.call_may_clobber_ref_p_no_alias
132 + alias_stats
.call_may_clobber_ref_p_may_alias
);
136 /* Return true, if dereferencing PTR may alias with a global variable. */
139 ptr_deref_may_alias_global_p (tree ptr
)
141 struct ptr_info_def
*pi
;
143 /* If we end up with a pointer constant here that may point
145 if (TREE_CODE (ptr
) != SSA_NAME
)
148 pi
= SSA_NAME_PTR_INFO (ptr
);
150 /* If we do not have points-to information for this variable,
155 /* ??? This does not use TBAA to prune globals ptr may not access. */
156 return pt_solution_includes_global (&pi
->pt
);
159 /* Return true if dereferencing PTR may alias DECL.
160 The caller is responsible for applying TBAA to see if PTR
161 may access DECL at all. */
164 ptr_deref_may_alias_decl_p (tree ptr
, tree decl
)
166 struct ptr_info_def
*pi
;
168 /* Conversions are irrelevant for points-to information and
169 data-dependence analysis can feed us those. */
172 /* Anything we do not explicilty handle aliases. */
173 if ((TREE_CODE (ptr
) != SSA_NAME
174 && TREE_CODE (ptr
) != ADDR_EXPR
175 && TREE_CODE (ptr
) != POINTER_PLUS_EXPR
)
176 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
177 || (TREE_CODE (decl
) != VAR_DECL
178 && TREE_CODE (decl
) != PARM_DECL
179 && TREE_CODE (decl
) != RESULT_DECL
))
182 /* Disregard pointer offsetting. */
183 if (TREE_CODE (ptr
) == POINTER_PLUS_EXPR
)
187 ptr
= TREE_OPERAND (ptr
, 0);
189 while (TREE_CODE (ptr
) == POINTER_PLUS_EXPR
);
190 return ptr_deref_may_alias_decl_p (ptr
, decl
);
193 /* ADDR_EXPR pointers either just offset another pointer or directly
194 specify the pointed-to set. */
195 if (TREE_CODE (ptr
) == ADDR_EXPR
)
197 tree base
= get_base_address (TREE_OPERAND (ptr
, 0));
199 && (TREE_CODE (base
) == MEM_REF
200 || TREE_CODE (base
) == TARGET_MEM_REF
))
201 ptr
= TREE_OPERAND (base
, 0);
206 && CONSTANT_CLASS_P (base
))
212 /* Non-aliased variables can not be pointed to. */
213 if (!may_be_aliased (decl
))
216 /* If we do not have useful points-to information for this pointer
217 we cannot disambiguate anything else. */
218 pi
= SSA_NAME_PTR_INFO (ptr
);
222 return pt_solution_includes (&pi
->pt
, decl
);
225 /* Return true if dereferenced PTR1 and PTR2 may alias.
226 The caller is responsible for applying TBAA to see if accesses
227 through PTR1 and PTR2 may conflict at all. */
230 ptr_derefs_may_alias_p (tree ptr1
, tree ptr2
)
232 struct ptr_info_def
*pi1
, *pi2
;
234 /* Conversions are irrelevant for points-to information and
235 data-dependence analysis can feed us those. */
239 /* Disregard pointer offsetting. */
240 if (TREE_CODE (ptr1
) == POINTER_PLUS_EXPR
)
244 ptr1
= TREE_OPERAND (ptr1
, 0);
246 while (TREE_CODE (ptr1
) == POINTER_PLUS_EXPR
);
247 return ptr_derefs_may_alias_p (ptr1
, ptr2
);
249 if (TREE_CODE (ptr2
) == POINTER_PLUS_EXPR
)
253 ptr2
= TREE_OPERAND (ptr2
, 0);
255 while (TREE_CODE (ptr2
) == POINTER_PLUS_EXPR
);
256 return ptr_derefs_may_alias_p (ptr1
, ptr2
);
259 /* ADDR_EXPR pointers either just offset another pointer or directly
260 specify the pointed-to set. */
261 if (TREE_CODE (ptr1
) == ADDR_EXPR
)
263 tree base
= get_base_address (TREE_OPERAND (ptr1
, 0));
265 && (TREE_CODE (base
) == MEM_REF
266 || TREE_CODE (base
) == TARGET_MEM_REF
))
267 return ptr_derefs_may_alias_p (TREE_OPERAND (base
, 0), ptr2
);
270 return ptr_deref_may_alias_decl_p (ptr2
, base
);
274 if (TREE_CODE (ptr2
) == ADDR_EXPR
)
276 tree base
= get_base_address (TREE_OPERAND (ptr2
, 0));
278 && (TREE_CODE (base
) == MEM_REF
279 || TREE_CODE (base
) == TARGET_MEM_REF
))
280 return ptr_derefs_may_alias_p (ptr1
, TREE_OPERAND (base
, 0));
283 return ptr_deref_may_alias_decl_p (ptr1
, base
);
288 /* From here we require SSA name pointers. Anything else aliases. */
289 if (TREE_CODE (ptr1
) != SSA_NAME
290 || TREE_CODE (ptr2
) != SSA_NAME
291 || !POINTER_TYPE_P (TREE_TYPE (ptr1
))
292 || !POINTER_TYPE_P (TREE_TYPE (ptr2
)))
295 /* We may end up with two empty points-to solutions for two same pointers.
296 In this case we still want to say both pointers alias, so shortcut
301 /* If we do not have useful points-to information for either pointer
302 we cannot disambiguate anything else. */
303 pi1
= SSA_NAME_PTR_INFO (ptr1
);
304 pi2
= SSA_NAME_PTR_INFO (ptr2
);
308 /* ??? This does not use TBAA to prune decls from the intersection
309 that not both pointers may access. */
310 return pt_solutions_intersect (&pi1
->pt
, &pi2
->pt
);
313 /* Return true if dereferencing PTR may alias *REF.
314 The caller is responsible for applying TBAA to see if PTR
315 may access *REF at all. */
318 ptr_deref_may_alias_ref_p_1 (tree ptr
, ao_ref
*ref
)
320 tree base
= ao_ref_base (ref
);
322 if (TREE_CODE (base
) == MEM_REF
323 || TREE_CODE (base
) == TARGET_MEM_REF
)
324 return ptr_derefs_may_alias_p (ptr
, TREE_OPERAND (base
, 0));
325 else if (DECL_P (base
))
326 return ptr_deref_may_alias_decl_p (ptr
, base
);
331 /* Return true whether REF may refer to global memory. */
334 ref_may_alias_global_p (tree ref
)
336 tree base
= get_base_address (ref
);
338 return is_global_var (base
);
339 else if (TREE_CODE (base
) == MEM_REF
340 || TREE_CODE (base
) == TARGET_MEM_REF
)
341 return ptr_deref_may_alias_global_p (TREE_OPERAND (base
, 0));
345 /* Return true whether STMT may clobber global memory. */
348 stmt_may_clobber_global_p (gimple stmt
)
352 if (!gimple_vdef (stmt
))
355 /* ??? We can ask the oracle whether an artificial pointer
356 dereference with a pointer with points-to information covering
357 all global memory (what about non-address taken memory?) maybe
358 clobbered by this call. As there is at the moment no convenient
359 way of doing that without generating garbage do some manual
361 ??? We could make a NULL ao_ref argument to the various
362 predicates special, meaning any global memory. */
364 switch (gimple_code (stmt
))
367 lhs
= gimple_assign_lhs (stmt
);
368 return (TREE_CODE (lhs
) != SSA_NAME
369 && ref_may_alias_global_p (lhs
));
378 /* Dump alias information on FILE. */
381 dump_alias_info (FILE *file
)
385 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
388 fprintf (file
, "\n\nAlias information for %s\n\n", funcname
);
390 fprintf (file
, "Aliased symbols\n\n");
392 FOR_EACH_LOCAL_DECL (cfun
, i
, var
)
394 if (may_be_aliased (var
))
395 dump_variable (file
, var
);
398 fprintf (file
, "\nCall clobber information\n");
400 fprintf (file
, "\nESCAPED");
401 dump_points_to_solution (file
, &cfun
->gimple_df
->escaped
);
403 fprintf (file
, "\n\nFlow-insensitive points-to information\n\n");
405 for (i
= 1; i
< num_ssa_names
; i
++)
407 tree ptr
= ssa_name (i
);
408 struct ptr_info_def
*pi
;
411 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
412 || SSA_NAME_IN_FREE_LIST (ptr
))
415 pi
= SSA_NAME_PTR_INFO (ptr
);
417 dump_points_to_info_for (file
, ptr
);
420 fprintf (file
, "\n");
424 /* Dump alias information on stderr. */
427 debug_alias_info (void)
429 dump_alias_info (stderr
);
433 /* Dump the points-to set *PT into FILE. */
436 dump_points_to_solution (FILE *file
, struct pt_solution
*pt
)
439 fprintf (file
, ", points-to anything");
442 fprintf (file
, ", points-to non-local");
445 fprintf (file
, ", points-to escaped");
448 fprintf (file
, ", points-to unit escaped");
451 fprintf (file
, ", points-to NULL");
455 fprintf (file
, ", points-to vars: ");
456 dump_decl_set (file
, pt
->vars
);
457 if (pt
->vars_contains_nonlocal
458 && pt
->vars_contains_escaped_heap
)
459 fprintf (file
, " (nonlocal, escaped heap)");
460 else if (pt
->vars_contains_nonlocal
461 && pt
->vars_contains_escaped
)
462 fprintf (file
, " (nonlocal, escaped)");
463 else if (pt
->vars_contains_nonlocal
)
464 fprintf (file
, " (nonlocal)");
465 else if (pt
->vars_contains_escaped_heap
)
466 fprintf (file
, " (escaped heap)");
467 else if (pt
->vars_contains_escaped
)
468 fprintf (file
, " (escaped)");
473 /* Unified dump function for pt_solution. */
476 debug (pt_solution
&ref
)
478 dump_points_to_solution (stderr
, &ref
);
482 debug (pt_solution
*ptr
)
487 fprintf (stderr
, "<nil>\n");
491 /* Dump points-to information for SSA_NAME PTR into FILE. */
494 dump_points_to_info_for (FILE *file
, tree ptr
)
496 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
498 print_generic_expr (file
, ptr
, dump_flags
);
501 dump_points_to_solution (file
, &pi
->pt
);
503 fprintf (file
, ", points-to anything");
505 fprintf (file
, "\n");
509 /* Dump points-to information for VAR into stderr. */
512 debug_points_to_info_for (tree var
)
514 dump_points_to_info_for (stderr
, var
);
518 /* Initializes the alias-oracle reference representation *R from REF. */
521 ao_ref_init (ao_ref
*r
, tree ref
)
528 r
->ref_alias_set
= -1;
529 r
->base_alias_set
= -1;
530 r
->volatile_p
= ref
? TREE_THIS_VOLATILE (ref
) : false;
533 /* Returns the base object of the memory reference *REF. */
536 ao_ref_base (ao_ref
*ref
)
540 ref
->base
= get_ref_base_and_extent (ref
->ref
, &ref
->offset
, &ref
->size
,
545 /* Returns the base object alias set of the memory reference *REF. */
547 static alias_set_type
548 ao_ref_base_alias_set (ao_ref
*ref
)
551 if (ref
->base_alias_set
!= -1)
552 return ref
->base_alias_set
;
556 while (handled_component_p (base_ref
))
557 base_ref
= TREE_OPERAND (base_ref
, 0);
558 ref
->base_alias_set
= get_alias_set (base_ref
);
559 return ref
->base_alias_set
;
562 /* Returns the reference alias set of the memory reference *REF. */
565 ao_ref_alias_set (ao_ref
*ref
)
567 if (ref
->ref_alias_set
!= -1)
568 return ref
->ref_alias_set
;
569 ref
->ref_alias_set
= get_alias_set (ref
->ref
);
570 return ref
->ref_alias_set
;
573 /* Init an alias-oracle reference representation from a gimple pointer
574 PTR and a gimple size SIZE in bytes. If SIZE is NULL_TREE then the
575 size is assumed to be unknown. The access is assumed to be only
576 to or after of the pointer target, not before it. */
579 ao_ref_init_from_ptr_and_size (ao_ref
*ref
, tree ptr
, tree size
)
581 HOST_WIDE_INT t
, size_hwi
, extra_offset
= 0;
582 ref
->ref
= NULL_TREE
;
583 if (TREE_CODE (ptr
) == SSA_NAME
)
585 gimple stmt
= SSA_NAME_DEF_STMT (ptr
);
586 if (gimple_assign_single_p (stmt
)
587 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
588 ptr
= gimple_assign_rhs1 (stmt
);
589 else if (is_gimple_assign (stmt
)
590 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
591 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
)
593 ptr
= gimple_assign_rhs1 (stmt
);
594 extra_offset
= BITS_PER_UNIT
595 * int_cst_value (gimple_assign_rhs2 (stmt
));
599 if (TREE_CODE (ptr
) == ADDR_EXPR
)
601 ref
->base
= get_addr_base_and_unit_offset (TREE_OPERAND (ptr
, 0), &t
);
603 ref
->offset
= BITS_PER_UNIT
* t
;
608 ref
->base
= get_base_address (TREE_OPERAND (ptr
, 0));
613 ref
->base
= build2 (MEM_REF
, char_type_node
,
614 ptr
, null_pointer_node
);
617 ref
->offset
+= extra_offset
;
619 && tree_fits_shwi_p (size
)
620 && (size_hwi
= tree_to_shwi (size
)) <= HOST_WIDE_INT_MAX
/ BITS_PER_UNIT
)
621 ref
->max_size
= ref
->size
= size_hwi
* BITS_PER_UNIT
;
623 ref
->max_size
= ref
->size
= -1;
624 ref
->ref_alias_set
= 0;
625 ref
->base_alias_set
= 0;
626 ref
->volatile_p
= false;
629 /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
630 purpose of TBAA. Return 0 if they are distinct and -1 if we cannot
634 same_type_for_tbaa (tree type1
, tree type2
)
636 type1
= TYPE_MAIN_VARIANT (type1
);
637 type2
= TYPE_MAIN_VARIANT (type2
);
639 /* If we would have to do structural comparison bail out. */
640 if (TYPE_STRUCTURAL_EQUALITY_P (type1
)
641 || TYPE_STRUCTURAL_EQUALITY_P (type2
))
644 /* Compare the canonical types. */
645 if (TYPE_CANONICAL (type1
) == TYPE_CANONICAL (type2
))
648 /* ??? Array types are not properly unified in all cases as we have
649 spurious changes in the index types for example. Removing this
650 causes all sorts of problems with the Fortran frontend. */
651 if (TREE_CODE (type1
) == ARRAY_TYPE
652 && TREE_CODE (type2
) == ARRAY_TYPE
)
655 /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
656 object of one of its constrained subtypes, e.g. when a function with an
657 unconstrained parameter passed by reference is called on an object and
658 inlined. But, even in the case of a fixed size, type and subtypes are
659 not equivalent enough as to share the same TYPE_CANONICAL, since this
660 would mean that conversions between them are useless, whereas they are
661 not (e.g. type and subtypes can have different modes). So, in the end,
662 they are only guaranteed to have the same alias set. */
663 if (get_alias_set (type1
) == get_alias_set (type2
))
666 /* The types are known to be not equal. */
670 /* Determine if the two component references REF1 and REF2 which are
671 based on access types TYPE1 and TYPE2 and of which at least one is based
672 on an indirect reference may alias. REF2 is the only one that can
673 be a decl in which case REF2_IS_DECL is true.
674 REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
675 are the respective alias sets. */
678 aliasing_component_refs_p (tree ref1
,
679 alias_set_type ref1_alias_set
,
680 alias_set_type base1_alias_set
,
681 HOST_WIDE_INT offset1
, HOST_WIDE_INT max_size1
,
683 alias_set_type ref2_alias_set
,
684 alias_set_type base2_alias_set
,
685 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
,
688 /* If one reference is a component references through pointers try to find a
689 common base and apply offset based disambiguation. This handles
691 struct A { int i; int j; } *q;
692 struct B { struct A a; int k; } *p;
693 disambiguating q->i and p->a.j. */
699 /* Choose bases and base types to search for. */
701 while (handled_component_p (base1
))
702 base1
= TREE_OPERAND (base1
, 0);
703 type1
= TREE_TYPE (base1
);
705 while (handled_component_p (base2
))
706 base2
= TREE_OPERAND (base2
, 0);
707 type2
= TREE_TYPE (base2
);
709 /* Now search for the type1 in the access path of ref2. This
710 would be a common base for doing offset based disambiguation on. */
712 while (handled_component_p (*refp
)
713 && same_type_for_tbaa (TREE_TYPE (*refp
), type1
) == 0)
714 refp
= &TREE_OPERAND (*refp
, 0);
715 same_p
= same_type_for_tbaa (TREE_TYPE (*refp
), type1
);
716 /* If we couldn't compare types we have to bail out. */
719 else if (same_p
== 1)
721 HOST_WIDE_INT offadj
, sztmp
, msztmp
;
722 get_ref_base_and_extent (*refp
, &offadj
, &sztmp
, &msztmp
);
724 get_ref_base_and_extent (base1
, &offadj
, &sztmp
, &msztmp
);
726 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
728 /* If we didn't find a common base, try the other way around. */
730 while (handled_component_p (*refp
)
731 && same_type_for_tbaa (TREE_TYPE (*refp
), type2
) == 0)
732 refp
= &TREE_OPERAND (*refp
, 0);
733 same_p
= same_type_for_tbaa (TREE_TYPE (*refp
), type2
);
734 /* If we couldn't compare types we have to bail out. */
737 else if (same_p
== 1)
739 HOST_WIDE_INT offadj
, sztmp
, msztmp
;
740 get_ref_base_and_extent (*refp
, &offadj
, &sztmp
, &msztmp
);
742 get_ref_base_and_extent (base2
, &offadj
, &sztmp
, &msztmp
);
744 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
747 /* If we have two type access paths B1.path1 and B2.path2 they may
748 only alias if either B1 is in B2.path2 or B2 is in B1.path1.
749 But we can still have a path that goes B1.path1...B2.path2 with
750 a part that we do not see. So we can only disambiguate now
751 if there is no B2 in the tail of path1 and no B1 on the
753 if (base1_alias_set
== ref2_alias_set
754 || alias_set_subset_of (base1_alias_set
, ref2_alias_set
))
756 /* If this is ptr vs. decl then we know there is no ptr ... decl path. */
758 return (base2_alias_set
== ref1_alias_set
759 || alias_set_subset_of (base2_alias_set
, ref1_alias_set
));
763 /* Return true if we can determine that component references REF1 and REF2,
764 that are within a common DECL, cannot overlap. */
767 nonoverlapping_component_refs_of_decl_p (tree ref1
, tree ref2
)
769 stack_vec
<tree
, 16> component_refs1
;
770 stack_vec
<tree
, 16> component_refs2
;
772 /* Create the stack of handled components for REF1. */
773 while (handled_component_p (ref1
))
775 component_refs1
.safe_push (ref1
);
776 ref1
= TREE_OPERAND (ref1
, 0);
778 if (TREE_CODE (ref1
) == MEM_REF
)
780 if (!integer_zerop (TREE_OPERAND (ref1
, 1)))
782 ref1
= TREE_OPERAND (TREE_OPERAND (ref1
, 0), 0);
785 /* Create the stack of handled components for REF2. */
786 while (handled_component_p (ref2
))
788 component_refs2
.safe_push (ref2
);
789 ref2
= TREE_OPERAND (ref2
, 0);
791 if (TREE_CODE (ref2
) == MEM_REF
)
793 if (!integer_zerop (TREE_OPERAND (ref2
, 1)))
795 ref2
= TREE_OPERAND (TREE_OPERAND (ref2
, 0), 0);
798 /* We must have the same base DECL. */
799 gcc_assert (ref1
== ref2
);
801 /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
802 rank. This is sufficient because we start from the same DECL and you
803 cannot reference several fields at a time with COMPONENT_REFs (unlike
804 with ARRAY_RANGE_REFs for arrays) so you always need the same number
805 of them to access a sub-component, unless you're in a union, in which
806 case the return value will precisely be false. */
811 if (component_refs1
.is_empty ())
813 ref1
= component_refs1
.pop ();
815 while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1
, 0))));
819 if (component_refs2
.is_empty ())
821 ref2
= component_refs2
.pop ();
823 while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2
, 0))));
825 /* Beware of BIT_FIELD_REF. */
826 if (TREE_CODE (ref1
) != COMPONENT_REF
827 || TREE_CODE (ref2
) != COMPONENT_REF
)
830 tree field1
= TREE_OPERAND (ref1
, 1);
831 tree field2
= TREE_OPERAND (ref2
, 1);
833 /* ??? We cannot simply use the type of operand #0 of the refs here
834 as the Fortran compiler smuggles type punning into COMPONENT_REFs
835 for common blocks instead of using unions like everyone else. */
836 tree type1
= TYPE_MAIN_VARIANT (DECL_CONTEXT (field1
));
837 tree type2
= TYPE_MAIN_VARIANT (DECL_CONTEXT (field2
));
839 /* We cannot disambiguate fields in a union or qualified union. */
840 if (type1
!= type2
|| TREE_CODE (type1
) != RECORD_TYPE
)
843 /* Different fields of the same record type cannot overlap.
844 ??? Bitfields can overlap at RTL level so punt on them. */
845 if (field1
!= field2
)
847 component_refs1
.release ();
848 component_refs2
.release ();
849 return !(DECL_BIT_FIELD (field1
) && DECL_BIT_FIELD (field2
));
854 component_refs1
.release ();
855 component_refs2
.release ();
859 /* Return true if two memory references based on the variables BASE1
860 and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
861 [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. REF1 and REF2
862 if non-NULL are the complete memory reference trees. */
865 decl_refs_may_alias_p (tree ref1
, tree base1
,
866 HOST_WIDE_INT offset1
, HOST_WIDE_INT max_size1
,
867 tree ref2
, tree base2
,
868 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
)
870 gcc_checking_assert (DECL_P (base1
) && DECL_P (base2
));
872 /* If both references are based on different variables, they cannot alias. */
876 /* If both references are based on the same variable, they cannot alias if
877 the accesses do not overlap. */
878 if (!ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
))
881 /* For components with variable position, the above test isn't sufficient,
882 so we disambiguate component references manually. */
884 && handled_component_p (ref1
) && handled_component_p (ref2
)
885 && nonoverlapping_component_refs_of_decl_p (ref1
, ref2
))
891 /* Return true if an indirect reference based on *PTR1 constrained
892 to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
893 constrained to [OFFSET2, OFFSET2 + MAX_SIZE2). *PTR1 and BASE2 have
894 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
895 in which case they are computed on-demand. REF1 and REF2
896 if non-NULL are the complete memory reference trees. */
899 indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED
, tree base1
,
900 HOST_WIDE_INT offset1
,
901 HOST_WIDE_INT max_size1 ATTRIBUTE_UNUSED
,
902 alias_set_type ref1_alias_set
,
903 alias_set_type base1_alias_set
,
904 tree ref2 ATTRIBUTE_UNUSED
, tree base2
,
905 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
,
906 alias_set_type ref2_alias_set
,
907 alias_set_type base2_alias_set
, bool tbaa_p
)
910 tree ptrtype1
, dbase2
;
911 HOST_WIDE_INT offset1p
= offset1
, offset2p
= offset2
;
912 HOST_WIDE_INT doffset1
, doffset2
;
914 gcc_checking_assert ((TREE_CODE (base1
) == MEM_REF
915 || TREE_CODE (base1
) == TARGET_MEM_REF
)
918 ptr1
= TREE_OPERAND (base1
, 0);
920 /* The offset embedded in MEM_REFs can be negative. Bias them
921 so that the resulting offset adjustment is positive. */
922 offset_int moff
= mem_ref_offset (base1
);
923 moff
= wi::lshift (moff
, (BITS_PER_UNIT
== 8
924 ? 3 : exact_log2 (BITS_PER_UNIT
)));
925 if (wi::neg_p (moff
))
926 offset2p
+= (-moff
).to_short_addr ();
928 offset1p
+= moff
.to_short_addr ();
930 /* If only one reference is based on a variable, they cannot alias if
931 the pointer access is beyond the extent of the variable access.
932 (the pointer base cannot validly point to an offset less than zero
934 ??? IVOPTs creates bases that do not honor this restriction,
935 so do not apply this optimization for TARGET_MEM_REFs. */
936 if (TREE_CODE (base1
) != TARGET_MEM_REF
937 && !ranges_overlap_p (MAX (0, offset1p
), -1, offset2p
, max_size2
))
939 /* They also cannot alias if the pointer may not point to the decl. */
940 if (!ptr_deref_may_alias_decl_p (ptr1
, base2
))
943 /* Disambiguations that rely on strict aliasing rules follow. */
944 if (!flag_strict_aliasing
|| !tbaa_p
)
947 ptrtype1
= TREE_TYPE (TREE_OPERAND (base1
, 1));
949 /* If the alias set for a pointer access is zero all bets are off. */
950 if (base1_alias_set
== -1)
951 base1_alias_set
= get_deref_alias_set (ptrtype1
);
952 if (base1_alias_set
== 0)
954 if (base2_alias_set
== -1)
955 base2_alias_set
= get_alias_set (base2
);
957 /* When we are trying to disambiguate an access with a pointer dereference
958 as base versus one with a decl as base we can use both the size
959 of the decl and its dynamic type for extra disambiguation.
960 ??? We do not know anything about the dynamic type of the decl
961 other than that its alias-set contains base2_alias_set as a subset
962 which does not help us here. */
963 /* As we know nothing useful about the dynamic type of the decl just
964 use the usual conflict check rather than a subset test.
965 ??? We could introduce -fvery-strict-aliasing when the language
966 does not allow decls to have a dynamic type that differs from their
967 static type. Then we can check
968 !alias_set_subset_of (base1_alias_set, base2_alias_set) instead. */
969 if (base1_alias_set
!= base2_alias_set
970 && !alias_sets_conflict_p (base1_alias_set
, base2_alias_set
))
972 /* If the size of the access relevant for TBAA through the pointer
973 is bigger than the size of the decl we can't possibly access the
974 decl via that pointer. */
975 if (DECL_SIZE (base2
) && COMPLETE_TYPE_P (TREE_TYPE (ptrtype1
))
976 && TREE_CODE (DECL_SIZE (base2
)) == INTEGER_CST
977 && TREE_CODE (TYPE_SIZE (TREE_TYPE (ptrtype1
))) == INTEGER_CST
978 /* ??? This in turn may run afoul when a decl of type T which is
979 a member of union type U is accessed through a pointer to
980 type U and sizeof T is smaller than sizeof U. */
981 && TREE_CODE (TREE_TYPE (ptrtype1
)) != UNION_TYPE
982 && TREE_CODE (TREE_TYPE (ptrtype1
)) != QUAL_UNION_TYPE
983 && tree_int_cst_lt (DECL_SIZE (base2
), TYPE_SIZE (TREE_TYPE (ptrtype1
))))
989 /* If the decl is accessed via a MEM_REF, reconstruct the base
990 we can use for TBAA and an appropriately adjusted offset. */
992 while (handled_component_p (dbase2
))
993 dbase2
= TREE_OPERAND (dbase2
, 0);
996 if (TREE_CODE (dbase2
) == MEM_REF
997 || TREE_CODE (dbase2
) == TARGET_MEM_REF
)
999 offset_int moff
= mem_ref_offset (dbase2
);
1000 moff
= wi::lshift (moff
, (BITS_PER_UNIT
== 8
1001 ? 3 : exact_log2 (BITS_PER_UNIT
)));
1002 if (wi::neg_p (moff
))
1003 doffset1
-= (-moff
).to_short_addr ();
1005 doffset2
-= moff
.to_short_addr ();
1008 /* If either reference is view-converted, give up now. */
1009 if (same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (ptrtype1
)) != 1
1010 || same_type_for_tbaa (TREE_TYPE (dbase2
), TREE_TYPE (base2
)) != 1)
1013 /* If both references are through the same type, they do not alias
1014 if the accesses do not overlap. This does extra disambiguation
1015 for mixed/pointer accesses but requires strict aliasing.
1016 For MEM_REFs we require that the component-ref offset we computed
1017 is relative to the start of the type which we ensure by
1018 comparing rvalue and access type and disregarding the constant
1020 if ((TREE_CODE (base1
) != TARGET_MEM_REF
1021 || (!TMR_INDEX (base1
) && !TMR_INDEX2 (base1
)))
1022 && same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (dbase2
)) == 1)
1023 return ranges_overlap_p (doffset1
, max_size1
, doffset2
, max_size2
);
1025 /* Do access-path based disambiguation. */
1027 && (handled_component_p (ref1
) || handled_component_p (ref2
)))
1028 return aliasing_component_refs_p (ref1
,
1029 ref1_alias_set
, base1_alias_set
,
1032 ref2_alias_set
, base2_alias_set
,
1033 offset2
, max_size2
, true);
1038 /* Return true if two indirect references based on *PTR1
1039 and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
1040 [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. *PTR1 and *PTR2 have
1041 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
1042 in which case they are computed on-demand. REF1 and REF2
1043 if non-NULL are the complete memory reference trees. */
1046 indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED
, tree base1
,
1047 HOST_WIDE_INT offset1
, HOST_WIDE_INT max_size1
,
1048 alias_set_type ref1_alias_set
,
1049 alias_set_type base1_alias_set
,
1050 tree ref2 ATTRIBUTE_UNUSED
, tree base2
,
1051 HOST_WIDE_INT offset2
, HOST_WIDE_INT max_size2
,
1052 alias_set_type ref2_alias_set
,
1053 alias_set_type base2_alias_set
, bool tbaa_p
)
1057 tree ptrtype1
, ptrtype2
;
1059 gcc_checking_assert ((TREE_CODE (base1
) == MEM_REF
1060 || TREE_CODE (base1
) == TARGET_MEM_REF
)
1061 && (TREE_CODE (base2
) == MEM_REF
1062 || TREE_CODE (base2
) == TARGET_MEM_REF
));
1064 ptr1
= TREE_OPERAND (base1
, 0);
1065 ptr2
= TREE_OPERAND (base2
, 0);
1067 /* If both bases are based on pointers they cannot alias if they may not
1068 point to the same memory object or if they point to the same object
1069 and the accesses do not overlap. */
1070 if ((!cfun
|| gimple_in_ssa_p (cfun
))
1071 && operand_equal_p (ptr1
, ptr2
, 0)
1072 && (((TREE_CODE (base1
) != TARGET_MEM_REF
1073 || (!TMR_INDEX (base1
) && !TMR_INDEX2 (base1
)))
1074 && (TREE_CODE (base2
) != TARGET_MEM_REF
1075 || (!TMR_INDEX (base2
) && !TMR_INDEX2 (base2
))))
1076 || (TREE_CODE (base1
) == TARGET_MEM_REF
1077 && TREE_CODE (base2
) == TARGET_MEM_REF
1078 && (TMR_STEP (base1
) == TMR_STEP (base2
)
1079 || (TMR_STEP (base1
) && TMR_STEP (base2
)
1080 && operand_equal_p (TMR_STEP (base1
),
1081 TMR_STEP (base2
), 0)))
1082 && (TMR_INDEX (base1
) == TMR_INDEX (base2
)
1083 || (TMR_INDEX (base1
) && TMR_INDEX (base2
)
1084 && operand_equal_p (TMR_INDEX (base1
),
1085 TMR_INDEX (base2
), 0)))
1086 && (TMR_INDEX2 (base1
) == TMR_INDEX2 (base2
)
1087 || (TMR_INDEX2 (base1
) && TMR_INDEX2 (base2
)
1088 && operand_equal_p (TMR_INDEX2 (base1
),
1089 TMR_INDEX2 (base2
), 0))))))
1092 /* The offset embedded in MEM_REFs can be negative. Bias them
1093 so that the resulting offset adjustment is positive. */
1094 moff
= mem_ref_offset (base1
);
1095 moff
= wi::lshift (moff
, (BITS_PER_UNIT
== 8
1096 ? 3 : exact_log2 (BITS_PER_UNIT
)));
1097 if (wi::neg_p (moff
))
1098 offset2
+= (-moff
).to_short_addr ();
1100 offset1
+= moff
.to_shwi ();
1101 moff
= mem_ref_offset (base2
);
1102 moff
= wi::lshift (moff
, (BITS_PER_UNIT
== 8
1103 ? 3 : exact_log2 (BITS_PER_UNIT
)));
1104 if (wi::neg_p (moff
))
1105 offset1
+= (-moff
).to_short_addr ();
1107 offset2
+= moff
.to_short_addr ();
1108 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1110 if (!ptr_derefs_may_alias_p (ptr1
, ptr2
))
1113 /* Disambiguations that rely on strict aliasing rules follow. */
1114 if (!flag_strict_aliasing
|| !tbaa_p
)
1117 ptrtype1
= TREE_TYPE (TREE_OPERAND (base1
, 1));
1118 ptrtype2
= TREE_TYPE (TREE_OPERAND (base2
, 1));
1120 /* If the alias set for a pointer access is zero all bets are off. */
1121 if (base1_alias_set
== -1)
1122 base1_alias_set
= get_deref_alias_set (ptrtype1
);
1123 if (base1_alias_set
== 0)
1125 if (base2_alias_set
== -1)
1126 base2_alias_set
= get_deref_alias_set (ptrtype2
);
1127 if (base2_alias_set
== 0)
1130 /* If both references are through the same type, they do not alias
1131 if the accesses do not overlap. This does extra disambiguation
1132 for mixed/pointer accesses but requires strict aliasing. */
1133 if ((TREE_CODE (base1
) != TARGET_MEM_REF
1134 || (!TMR_INDEX (base1
) && !TMR_INDEX2 (base1
)))
1135 && (TREE_CODE (base2
) != TARGET_MEM_REF
1136 || (!TMR_INDEX (base2
) && !TMR_INDEX2 (base2
)))
1137 && same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (ptrtype1
)) == 1
1138 && same_type_for_tbaa (TREE_TYPE (base2
), TREE_TYPE (ptrtype2
)) == 1
1139 && same_type_for_tbaa (TREE_TYPE (ptrtype1
),
1140 TREE_TYPE (ptrtype2
)) == 1)
1141 return ranges_overlap_p (offset1
, max_size1
, offset2
, max_size2
);
1143 /* Do type-based disambiguation. */
1144 if (base1_alias_set
!= base2_alias_set
1145 && !alias_sets_conflict_p (base1_alias_set
, base2_alias_set
))
1148 /* Do access-path based disambiguation. */
1150 && (handled_component_p (ref1
) || handled_component_p (ref2
))
1151 && same_type_for_tbaa (TREE_TYPE (base1
), TREE_TYPE (ptrtype1
)) == 1
1152 && same_type_for_tbaa (TREE_TYPE (base2
), TREE_TYPE (ptrtype2
)) == 1)
1153 return aliasing_component_refs_p (ref1
,
1154 ref1_alias_set
, base1_alias_set
,
1157 ref2_alias_set
, base2_alias_set
,
1158 offset2
, max_size2
, false);
1163 /* Return true, if the two memory references REF1 and REF2 may alias. */
1166 refs_may_alias_p_1 (ao_ref
*ref1
, ao_ref
*ref2
, bool tbaa_p
)
1169 HOST_WIDE_INT offset1
= 0, offset2
= 0;
1170 HOST_WIDE_INT max_size1
= -1, max_size2
= -1;
1171 bool var1_p
, var2_p
, ind1_p
, ind2_p
;
1173 gcc_checking_assert ((!ref1
->ref
1174 || TREE_CODE (ref1
->ref
) == SSA_NAME
1175 || DECL_P (ref1
->ref
)
1176 || TREE_CODE (ref1
->ref
) == STRING_CST
1177 || handled_component_p (ref1
->ref
)
1178 || TREE_CODE (ref1
->ref
) == MEM_REF
1179 || TREE_CODE (ref1
->ref
) == TARGET_MEM_REF
)
1181 || TREE_CODE (ref2
->ref
) == SSA_NAME
1182 || DECL_P (ref2
->ref
)
1183 || TREE_CODE (ref2
->ref
) == STRING_CST
1184 || handled_component_p (ref2
->ref
)
1185 || TREE_CODE (ref2
->ref
) == MEM_REF
1186 || TREE_CODE (ref2
->ref
) == TARGET_MEM_REF
));
1188 /* Decompose the references into their base objects and the access. */
1189 base1
= ao_ref_base (ref1
);
1190 offset1
= ref1
->offset
;
1191 max_size1
= ref1
->max_size
;
1192 base2
= ao_ref_base (ref2
);
1193 offset2
= ref2
->offset
;
1194 max_size2
= ref2
->max_size
;
1196 /* We can end up with registers or constants as bases for example from
1197 *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
1198 which is seen as a struct copy. */
1199 if (TREE_CODE (base1
) == SSA_NAME
1200 || TREE_CODE (base1
) == CONST_DECL
1201 || TREE_CODE (base1
) == CONSTRUCTOR
1202 || TREE_CODE (base1
) == ADDR_EXPR
1203 || CONSTANT_CLASS_P (base1
)
1204 || TREE_CODE (base2
) == SSA_NAME
1205 || TREE_CODE (base2
) == CONST_DECL
1206 || TREE_CODE (base2
) == CONSTRUCTOR
1207 || TREE_CODE (base2
) == ADDR_EXPR
1208 || CONSTANT_CLASS_P (base2
))
1211 /* We can end up referring to code via function and label decls.
1212 As we likely do not properly track code aliases conservatively
1214 if (TREE_CODE (base1
) == FUNCTION_DECL
1215 || TREE_CODE (base1
) == LABEL_DECL
1216 || TREE_CODE (base2
) == FUNCTION_DECL
1217 || TREE_CODE (base2
) == LABEL_DECL
)
1220 /* Two volatile accesses always conflict. */
1221 if (ref1
->volatile_p
1222 && ref2
->volatile_p
)
1225 /* Defer to simple offset based disambiguation if we have
1226 references based on two decls. Do this before defering to
1227 TBAA to handle must-alias cases in conformance with the
1228 GCC extension of allowing type-punning through unions. */
1229 var1_p
= DECL_P (base1
);
1230 var2_p
= DECL_P (base2
);
1231 if (var1_p
&& var2_p
)
1232 return decl_refs_may_alias_p (ref1
->ref
, base1
, offset1
, max_size1
,
1233 ref2
->ref
, base2
, offset2
, max_size2
);
1235 ind1_p
= (TREE_CODE (base1
) == MEM_REF
1236 || TREE_CODE (base1
) == TARGET_MEM_REF
);
1237 ind2_p
= (TREE_CODE (base2
) == MEM_REF
1238 || TREE_CODE (base2
) == TARGET_MEM_REF
);
1240 /* Canonicalize the pointer-vs-decl case. */
1241 if (ind1_p
&& var2_p
)
1246 tmp1
= offset1
; offset1
= offset2
; offset2
= tmp1
;
1247 tmp1
= max_size1
; max_size1
= max_size2
; max_size2
= tmp1
;
1248 tmp2
= base1
; base1
= base2
; base2
= tmp2
;
1249 tmp3
= ref1
; ref1
= ref2
; ref2
= tmp3
;
1256 /* First defer to TBAA if possible. */
1258 && flag_strict_aliasing
1259 && !alias_sets_conflict_p (ao_ref_alias_set (ref1
),
1260 ao_ref_alias_set (ref2
)))
1263 /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators. */
1264 if (var1_p
&& ind2_p
)
1265 return indirect_ref_may_alias_decl_p (ref2
->ref
, base2
,
1267 ao_ref_alias_set (ref2
), -1,
1270 ao_ref_alias_set (ref1
),
1271 ao_ref_base_alias_set (ref1
),
1273 else if (ind1_p
&& ind2_p
)
1274 return indirect_refs_may_alias_p (ref1
->ref
, base1
,
1276 ao_ref_alias_set (ref1
), -1,
1279 ao_ref_alias_set (ref2
), -1,
1282 /* We really do not want to end up here, but returning true is safe. */
1283 #ifdef ENABLE_CHECKING
1291 refs_may_alias_p (tree ref1
, tree ref2
)
1295 ao_ref_init (&r1
, ref1
);
1296 ao_ref_init (&r2
, ref2
);
1297 res
= refs_may_alias_p_1 (&r1
, &r2
, true);
1299 ++alias_stats
.refs_may_alias_p_may_alias
;
1301 ++alias_stats
.refs_may_alias_p_no_alias
;
1305 /* Returns true if there is a anti-dependence for the STORE that
1306 executes after the LOAD. */
1309 refs_anti_dependent_p (tree load
, tree store
)
1312 ao_ref_init (&r1
, load
);
1313 ao_ref_init (&r2
, store
);
1314 return refs_may_alias_p_1 (&r1
, &r2
, false);
1317 /* Returns true if there is a output dependence for the stores
1318 STORE1 and STORE2. */
1321 refs_output_dependent_p (tree store1
, tree store2
)
1324 ao_ref_init (&r1
, store1
);
1325 ao_ref_init (&r2
, store2
);
1326 return refs_may_alias_p_1 (&r1
, &r2
, false);
1329 /* If the call CALL may use the memory reference REF return true,
1330 otherwise return false. */
1333 ref_maybe_used_by_call_p_1 (gimple call
, ao_ref
*ref
)
1337 int flags
= gimple_call_flags (call
);
1339 /* Const functions without a static chain do not implicitly use memory. */
1340 if (!gimple_call_chain (call
)
1341 && (flags
& (ECF_CONST
|ECF_NOVOPS
)))
1344 base
= ao_ref_base (ref
);
1348 /* A call that is not without side-effects might involve volatile
1349 accesses and thus conflicts with all other volatile accesses. */
1350 if (ref
->volatile_p
)
1353 /* If the reference is based on a decl that is not aliased the call
1354 cannot possibly use it. */
1356 && !may_be_aliased (base
)
1357 /* But local statics can be used through recursion. */
1358 && !is_global_var (base
))
1361 callee
= gimple_call_fndecl (call
);
1363 /* Handle those builtin functions explicitly that do not act as
1364 escape points. See tree-ssa-structalias.c:find_func_aliases
1365 for the list of builtins we might need to handle here. */
1366 if (callee
!= NULL_TREE
1367 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
1368 switch (DECL_FUNCTION_CODE (callee
))
1370 /* All the following functions read memory pointed to by
1371 their second argument. strcat/strncat additionally
1372 reads memory pointed to by the first argument. */
1373 case BUILT_IN_STRCAT
:
1374 case BUILT_IN_STRNCAT
:
1377 ao_ref_init_from_ptr_and_size (&dref
,
1378 gimple_call_arg (call
, 0),
1380 if (refs_may_alias_p_1 (&dref
, ref
, false))
1384 case BUILT_IN_STRCPY
:
1385 case BUILT_IN_STRNCPY
:
1386 case BUILT_IN_MEMCPY
:
1387 case BUILT_IN_MEMMOVE
:
1388 case BUILT_IN_MEMPCPY
:
1389 case BUILT_IN_STPCPY
:
1390 case BUILT_IN_STPNCPY
:
1391 case BUILT_IN_TM_MEMCPY
:
1392 case BUILT_IN_TM_MEMMOVE
:
1395 tree size
= NULL_TREE
;
1396 if (gimple_call_num_args (call
) == 3)
1397 size
= gimple_call_arg (call
, 2);
1398 ao_ref_init_from_ptr_and_size (&dref
,
1399 gimple_call_arg (call
, 1),
1401 return refs_may_alias_p_1 (&dref
, ref
, false);
1403 case BUILT_IN_STRCAT_CHK
:
1404 case BUILT_IN_STRNCAT_CHK
:
1407 ao_ref_init_from_ptr_and_size (&dref
,
1408 gimple_call_arg (call
, 0),
1410 if (refs_may_alias_p_1 (&dref
, ref
, false))
1414 case BUILT_IN_STRCPY_CHK
:
1415 case BUILT_IN_STRNCPY_CHK
:
1416 case BUILT_IN_MEMCPY_CHK
:
1417 case BUILT_IN_MEMMOVE_CHK
:
1418 case BUILT_IN_MEMPCPY_CHK
:
1419 case BUILT_IN_STPCPY_CHK
:
1420 case BUILT_IN_STPNCPY_CHK
:
1423 tree size
= NULL_TREE
;
1424 if (gimple_call_num_args (call
) == 4)
1425 size
= gimple_call_arg (call
, 2);
1426 ao_ref_init_from_ptr_and_size (&dref
,
1427 gimple_call_arg (call
, 1),
1429 return refs_may_alias_p_1 (&dref
, ref
, false);
1431 case BUILT_IN_BCOPY
:
1434 tree size
= gimple_call_arg (call
, 2);
1435 ao_ref_init_from_ptr_and_size (&dref
,
1436 gimple_call_arg (call
, 0),
1438 return refs_may_alias_p_1 (&dref
, ref
, false);
1441 /* The following functions read memory pointed to by their
1443 CASE_BUILT_IN_TM_LOAD (1):
1444 CASE_BUILT_IN_TM_LOAD (2):
1445 CASE_BUILT_IN_TM_LOAD (4):
1446 CASE_BUILT_IN_TM_LOAD (8):
1447 CASE_BUILT_IN_TM_LOAD (FLOAT
):
1448 CASE_BUILT_IN_TM_LOAD (DOUBLE
):
1449 CASE_BUILT_IN_TM_LOAD (LDOUBLE
):
1450 CASE_BUILT_IN_TM_LOAD (M64
):
1451 CASE_BUILT_IN_TM_LOAD (M128
):
1452 CASE_BUILT_IN_TM_LOAD (M256
):
1453 case BUILT_IN_TM_LOG
:
1454 case BUILT_IN_TM_LOG_1
:
1455 case BUILT_IN_TM_LOG_2
:
1456 case BUILT_IN_TM_LOG_4
:
1457 case BUILT_IN_TM_LOG_8
:
1458 case BUILT_IN_TM_LOG_FLOAT
:
1459 case BUILT_IN_TM_LOG_DOUBLE
:
1460 case BUILT_IN_TM_LOG_LDOUBLE
:
1461 case BUILT_IN_TM_LOG_M64
:
1462 case BUILT_IN_TM_LOG_M128
:
1463 case BUILT_IN_TM_LOG_M256
:
1464 return ptr_deref_may_alias_ref_p_1 (gimple_call_arg (call
, 0), ref
);
1466 /* These read memory pointed to by the first argument. */
1467 case BUILT_IN_STRDUP
:
1468 case BUILT_IN_STRNDUP
:
1471 tree size
= NULL_TREE
;
1472 if (gimple_call_num_args (call
) == 2)
1473 size
= gimple_call_arg (call
, 1);
1474 ao_ref_init_from_ptr_and_size (&dref
,
1475 gimple_call_arg (call
, 0),
1477 return refs_may_alias_p_1 (&dref
, ref
, false);
1479 /* These read memory pointed to by the first argument. */
1480 case BUILT_IN_INDEX
:
1481 case BUILT_IN_STRCHR
:
1482 case BUILT_IN_STRRCHR
:
1485 ao_ref_init_from_ptr_and_size (&dref
,
1486 gimple_call_arg (call
, 0),
1488 return refs_may_alias_p_1 (&dref
, ref
, false);
1490 /* These read memory pointed to by the first argument with size
1491 in the third argument. */
1492 case BUILT_IN_MEMCHR
:
1495 ao_ref_init_from_ptr_and_size (&dref
,
1496 gimple_call_arg (call
, 0),
1497 gimple_call_arg (call
, 2));
1498 return refs_may_alias_p_1 (&dref
, ref
, false);
1500 /* These read memory pointed to by the first and second arguments. */
1501 case BUILT_IN_STRSTR
:
1502 case BUILT_IN_STRPBRK
:
1505 ao_ref_init_from_ptr_and_size (&dref
,
1506 gimple_call_arg (call
, 0),
1508 if (refs_may_alias_p_1 (&dref
, ref
, false))
1510 ao_ref_init_from_ptr_and_size (&dref
,
1511 gimple_call_arg (call
, 1),
1513 return refs_may_alias_p_1 (&dref
, ref
, false);
1516 /* The following builtins do not read from memory. */
1518 case BUILT_IN_MALLOC
:
1519 case BUILT_IN_CALLOC
:
1520 case BUILT_IN_ALLOCA
:
1521 case BUILT_IN_ALLOCA_WITH_ALIGN
:
1522 case BUILT_IN_STACK_SAVE
:
1523 case BUILT_IN_STACK_RESTORE
:
1524 case BUILT_IN_MEMSET
:
1525 case BUILT_IN_TM_MEMSET
:
1526 case BUILT_IN_MEMSET_CHK
:
1527 case BUILT_IN_FREXP
:
1528 case BUILT_IN_FREXPF
:
1529 case BUILT_IN_FREXPL
:
1530 case BUILT_IN_GAMMA_R
:
1531 case BUILT_IN_GAMMAF_R
:
1532 case BUILT_IN_GAMMAL_R
:
1533 case BUILT_IN_LGAMMA_R
:
1534 case BUILT_IN_LGAMMAF_R
:
1535 case BUILT_IN_LGAMMAL_R
:
1537 case BUILT_IN_MODFF
:
1538 case BUILT_IN_MODFL
:
1539 case BUILT_IN_REMQUO
:
1540 case BUILT_IN_REMQUOF
:
1541 case BUILT_IN_REMQUOL
:
1542 case BUILT_IN_SINCOS
:
1543 case BUILT_IN_SINCOSF
:
1544 case BUILT_IN_SINCOSL
:
1545 case BUILT_IN_ASSUME_ALIGNED
:
1546 case BUILT_IN_VA_END
:
1548 /* __sync_* builtins and some OpenMP builtins act as threading
1550 #undef DEF_SYNC_BUILTIN
1551 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1552 #include "sync-builtins.def"
1553 #undef DEF_SYNC_BUILTIN
1554 case BUILT_IN_GOMP_ATOMIC_START
:
1555 case BUILT_IN_GOMP_ATOMIC_END
:
1556 case BUILT_IN_GOMP_BARRIER
:
1557 case BUILT_IN_GOMP_BARRIER_CANCEL
:
1558 case BUILT_IN_GOMP_TASKWAIT
:
1559 case BUILT_IN_GOMP_TASKGROUP_END
:
1560 case BUILT_IN_GOMP_CRITICAL_START
:
1561 case BUILT_IN_GOMP_CRITICAL_END
:
1562 case BUILT_IN_GOMP_CRITICAL_NAME_START
:
1563 case BUILT_IN_GOMP_CRITICAL_NAME_END
:
1564 case BUILT_IN_GOMP_LOOP_END
:
1565 case BUILT_IN_GOMP_LOOP_END_CANCEL
:
1566 case BUILT_IN_GOMP_ORDERED_START
:
1567 case BUILT_IN_GOMP_ORDERED_END
:
1568 case BUILT_IN_GOMP_SECTIONS_END
:
1569 case BUILT_IN_GOMP_SECTIONS_END_CANCEL
:
1570 case BUILT_IN_GOMP_SINGLE_COPY_START
:
1571 case BUILT_IN_GOMP_SINGLE_COPY_END
:
1575 /* Fallthru to general call handling. */;
1578 /* Check if base is a global static variable that is not read
1580 if (callee
!= NULL_TREE
1581 && TREE_CODE (base
) == VAR_DECL
1582 && TREE_STATIC (base
))
1584 struct cgraph_node
*node
= cgraph_get_node (callee
);
1587 /* FIXME: Callee can be an OMP builtin that does not have a call graph
1588 node yet. We should enforce that there are nodes for all decls in the
1589 IL and remove this check instead. */
1591 && (not_read
= ipa_reference_get_not_read_global (node
))
1592 && bitmap_bit_p (not_read
, DECL_UID (base
)))
1596 /* Check if the base variable is call-used. */
1599 if (pt_solution_includes (gimple_call_use_set (call
), base
))
1602 else if ((TREE_CODE (base
) == MEM_REF
1603 || TREE_CODE (base
) == TARGET_MEM_REF
)
1604 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
1606 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (TREE_OPERAND (base
, 0));
1610 if (pt_solutions_intersect (gimple_call_use_set (call
), &pi
->pt
))
1616 /* Inspect call arguments for passed-by-value aliases. */
1618 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1620 tree op
= gimple_call_arg (call
, i
);
1621 int flags
= gimple_call_arg_flags (call
, i
);
1623 if (flags
& EAF_UNUSED
)
1626 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
1627 op
= TREE_OPERAND (op
, 0);
1629 if (TREE_CODE (op
) != SSA_NAME
1630 && !is_gimple_min_invariant (op
))
1633 ao_ref_init (&r
, op
);
1634 if (refs_may_alias_p_1 (&r
, ref
, true))
1643 ref_maybe_used_by_call_p (gimple call
, tree ref
)
1647 ao_ref_init (&r
, ref
);
1648 res
= ref_maybe_used_by_call_p_1 (call
, &r
);
1650 ++alias_stats
.ref_maybe_used_by_call_p_may_alias
;
1652 ++alias_stats
.ref_maybe_used_by_call_p_no_alias
;
1657 /* If the statement STMT may use the memory reference REF return
1658 true, otherwise return false. */
1661 ref_maybe_used_by_stmt_p (gimple stmt
, tree ref
)
1663 if (is_gimple_assign (stmt
))
1667 /* All memory assign statements are single. */
1668 if (!gimple_assign_single_p (stmt
))
1671 rhs
= gimple_assign_rhs1 (stmt
);
1672 if (is_gimple_reg (rhs
)
1673 || is_gimple_min_invariant (rhs
)
1674 || gimple_assign_rhs_code (stmt
) == CONSTRUCTOR
)
1677 return refs_may_alias_p (rhs
, ref
);
1679 else if (is_gimple_call (stmt
))
1680 return ref_maybe_used_by_call_p (stmt
, ref
);
1681 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
1683 tree retval
= gimple_return_retval (stmt
);
1686 && TREE_CODE (retval
) != SSA_NAME
1687 && !is_gimple_min_invariant (retval
)
1688 && refs_may_alias_p (retval
, ref
))
1690 /* If ref escapes the function then the return acts as a use. */
1691 base
= get_base_address (ref
);
1694 else if (DECL_P (base
))
1695 return is_global_var (base
);
1696 else if (TREE_CODE (base
) == MEM_REF
1697 || TREE_CODE (base
) == TARGET_MEM_REF
)
1698 return ptr_deref_may_alias_global_p (TREE_OPERAND (base
, 0));
1705 /* If the call in statement CALL may clobber the memory reference REF
1706 return true, otherwise return false. */
1709 call_may_clobber_ref_p_1 (gimple call
, ao_ref
*ref
)
1714 /* If the call is pure or const it cannot clobber anything. */
1715 if (gimple_call_flags (call
)
1716 & (ECF_PURE
|ECF_CONST
|ECF_LOOPING_CONST_OR_PURE
|ECF_NOVOPS
))
1719 base
= ao_ref_base (ref
);
1723 if (TREE_CODE (base
) == SSA_NAME
1724 || CONSTANT_CLASS_P (base
))
1727 /* A call that is not without side-effects might involve volatile
1728 accesses and thus conflicts with all other volatile accesses. */
1729 if (ref
->volatile_p
)
1732 /* If the reference is based on a decl that is not aliased the call
1733 cannot possibly clobber it. */
1735 && !may_be_aliased (base
)
1736 /* But local non-readonly statics can be modified through recursion
1737 or the call may implement a threading barrier which we must
1738 treat as may-def. */
1739 && (TREE_READONLY (base
)
1740 || !is_global_var (base
)))
1743 callee
= gimple_call_fndecl (call
);
1745 /* Handle those builtin functions explicitly that do not act as
1746 escape points. See tree-ssa-structalias.c:find_func_aliases
1747 for the list of builtins we might need to handle here. */
1748 if (callee
!= NULL_TREE
1749 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
1750 switch (DECL_FUNCTION_CODE (callee
))
1752 /* All the following functions clobber memory pointed to by
1753 their first argument. */
1754 case BUILT_IN_STRCPY
:
1755 case BUILT_IN_STRNCPY
:
1756 case BUILT_IN_MEMCPY
:
1757 case BUILT_IN_MEMMOVE
:
1758 case BUILT_IN_MEMPCPY
:
1759 case BUILT_IN_STPCPY
:
1760 case BUILT_IN_STPNCPY
:
1761 case BUILT_IN_STRCAT
:
1762 case BUILT_IN_STRNCAT
:
1763 case BUILT_IN_MEMSET
:
1764 case BUILT_IN_TM_MEMSET
:
1765 CASE_BUILT_IN_TM_STORE (1):
1766 CASE_BUILT_IN_TM_STORE (2):
1767 CASE_BUILT_IN_TM_STORE (4):
1768 CASE_BUILT_IN_TM_STORE (8):
1769 CASE_BUILT_IN_TM_STORE (FLOAT
):
1770 CASE_BUILT_IN_TM_STORE (DOUBLE
):
1771 CASE_BUILT_IN_TM_STORE (LDOUBLE
):
1772 CASE_BUILT_IN_TM_STORE (M64
):
1773 CASE_BUILT_IN_TM_STORE (M128
):
1774 CASE_BUILT_IN_TM_STORE (M256
):
1775 case BUILT_IN_TM_MEMCPY
:
1776 case BUILT_IN_TM_MEMMOVE
:
1779 tree size
= NULL_TREE
;
1780 /* Don't pass in size for strncat, as the maximum size
1781 is strlen (dest) + n + 1 instead of n, resp.
1782 n + 1 at dest + strlen (dest), but strlen (dest) isn't
1784 if (gimple_call_num_args (call
) == 3
1785 && DECL_FUNCTION_CODE (callee
) != BUILT_IN_STRNCAT
)
1786 size
= gimple_call_arg (call
, 2);
1787 ao_ref_init_from_ptr_and_size (&dref
,
1788 gimple_call_arg (call
, 0),
1790 return refs_may_alias_p_1 (&dref
, ref
, false);
1792 case BUILT_IN_STRCPY_CHK
:
1793 case BUILT_IN_STRNCPY_CHK
:
1794 case BUILT_IN_MEMCPY_CHK
:
1795 case BUILT_IN_MEMMOVE_CHK
:
1796 case BUILT_IN_MEMPCPY_CHK
:
1797 case BUILT_IN_STPCPY_CHK
:
1798 case BUILT_IN_STPNCPY_CHK
:
1799 case BUILT_IN_STRCAT_CHK
:
1800 case BUILT_IN_STRNCAT_CHK
:
1801 case BUILT_IN_MEMSET_CHK
:
1804 tree size
= NULL_TREE
;
1805 /* Don't pass in size for __strncat_chk, as the maximum size
1806 is strlen (dest) + n + 1 instead of n, resp.
1807 n + 1 at dest + strlen (dest), but strlen (dest) isn't
1809 if (gimple_call_num_args (call
) == 4
1810 && DECL_FUNCTION_CODE (callee
) != BUILT_IN_STRNCAT_CHK
)
1811 size
= gimple_call_arg (call
, 2);
1812 ao_ref_init_from_ptr_and_size (&dref
,
1813 gimple_call_arg (call
, 0),
1815 return refs_may_alias_p_1 (&dref
, ref
, false);
1817 case BUILT_IN_BCOPY
:
1820 tree size
= gimple_call_arg (call
, 2);
1821 ao_ref_init_from_ptr_and_size (&dref
,
1822 gimple_call_arg (call
, 1),
1824 return refs_may_alias_p_1 (&dref
, ref
, false);
1826 /* Allocating memory does not have any side-effects apart from
1827 being the definition point for the pointer. */
1828 case BUILT_IN_MALLOC
:
1829 case BUILT_IN_CALLOC
:
1830 case BUILT_IN_STRDUP
:
1831 case BUILT_IN_STRNDUP
:
1832 /* Unix98 specifies that errno is set on allocation failure. */
1834 && targetm
.ref_may_alias_errno (ref
))
1837 case BUILT_IN_STACK_SAVE
:
1838 case BUILT_IN_ALLOCA
:
1839 case BUILT_IN_ALLOCA_WITH_ALIGN
:
1840 case BUILT_IN_ASSUME_ALIGNED
:
1842 /* Freeing memory kills the pointed-to memory. More importantly
1843 the call has to serve as a barrier for moving loads and stores
1846 case BUILT_IN_VA_END
:
1848 tree ptr
= gimple_call_arg (call
, 0);
1849 return ptr_deref_may_alias_ref_p_1 (ptr
, ref
);
1851 case BUILT_IN_GAMMA_R
:
1852 case BUILT_IN_GAMMAF_R
:
1853 case BUILT_IN_GAMMAL_R
:
1854 case BUILT_IN_LGAMMA_R
:
1855 case BUILT_IN_LGAMMAF_R
:
1856 case BUILT_IN_LGAMMAL_R
:
1858 tree out
= gimple_call_arg (call
, 1);
1859 if (ptr_deref_may_alias_ref_p_1 (out
, ref
))
1861 if (flag_errno_math
)
1865 case BUILT_IN_FREXP
:
1866 case BUILT_IN_FREXPF
:
1867 case BUILT_IN_FREXPL
:
1869 case BUILT_IN_MODFF
:
1870 case BUILT_IN_MODFL
:
1872 tree out
= gimple_call_arg (call
, 1);
1873 return ptr_deref_may_alias_ref_p_1 (out
, ref
);
1875 case BUILT_IN_REMQUO
:
1876 case BUILT_IN_REMQUOF
:
1877 case BUILT_IN_REMQUOL
:
1879 tree out
= gimple_call_arg (call
, 2);
1880 if (ptr_deref_may_alias_ref_p_1 (out
, ref
))
1882 if (flag_errno_math
)
1886 case BUILT_IN_SINCOS
:
1887 case BUILT_IN_SINCOSF
:
1888 case BUILT_IN_SINCOSL
:
1890 tree sin
= gimple_call_arg (call
, 1);
1891 tree cos
= gimple_call_arg (call
, 2);
1892 return (ptr_deref_may_alias_ref_p_1 (sin
, ref
)
1893 || ptr_deref_may_alias_ref_p_1 (cos
, ref
));
1895 /* __sync_* builtins and some OpenMP builtins act as threading
1897 #undef DEF_SYNC_BUILTIN
1898 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1899 #include "sync-builtins.def"
1900 #undef DEF_SYNC_BUILTIN
1901 case BUILT_IN_GOMP_ATOMIC_START
:
1902 case BUILT_IN_GOMP_ATOMIC_END
:
1903 case BUILT_IN_GOMP_BARRIER
:
1904 case BUILT_IN_GOMP_BARRIER_CANCEL
:
1905 case BUILT_IN_GOMP_TASKWAIT
:
1906 case BUILT_IN_GOMP_TASKGROUP_END
:
1907 case BUILT_IN_GOMP_CRITICAL_START
:
1908 case BUILT_IN_GOMP_CRITICAL_END
:
1909 case BUILT_IN_GOMP_CRITICAL_NAME_START
:
1910 case BUILT_IN_GOMP_CRITICAL_NAME_END
:
1911 case BUILT_IN_GOMP_LOOP_END
:
1912 case BUILT_IN_GOMP_LOOP_END_CANCEL
:
1913 case BUILT_IN_GOMP_ORDERED_START
:
1914 case BUILT_IN_GOMP_ORDERED_END
:
1915 case BUILT_IN_GOMP_SECTIONS_END
:
1916 case BUILT_IN_GOMP_SECTIONS_END_CANCEL
:
1917 case BUILT_IN_GOMP_SINGLE_COPY_START
:
1918 case BUILT_IN_GOMP_SINGLE_COPY_END
:
1921 /* Fallthru to general call handling. */;
1924 /* Check if base is a global static variable that is not written
1926 if (callee
!= NULL_TREE
1927 && TREE_CODE (base
) == VAR_DECL
1928 && TREE_STATIC (base
))
1930 struct cgraph_node
*node
= cgraph_get_node (callee
);
1934 && (not_written
= ipa_reference_get_not_written_global (node
))
1935 && bitmap_bit_p (not_written
, DECL_UID (base
)))
1939 /* Check if the base variable is call-clobbered. */
1941 return pt_solution_includes (gimple_call_clobber_set (call
), base
);
1942 else if ((TREE_CODE (base
) == MEM_REF
1943 || TREE_CODE (base
) == TARGET_MEM_REF
)
1944 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
1946 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (TREE_OPERAND (base
, 0));
1950 return pt_solutions_intersect (gimple_call_clobber_set (call
), &pi
->pt
);
1956 /* If the call in statement CALL may clobber the memory reference REF
1957 return true, otherwise return false. */
1960 call_may_clobber_ref_p (gimple call
, tree ref
)
1964 ao_ref_init (&r
, ref
);
1965 res
= call_may_clobber_ref_p_1 (call
, &r
);
1967 ++alias_stats
.call_may_clobber_ref_p_may_alias
;
1969 ++alias_stats
.call_may_clobber_ref_p_no_alias
;
1974 /* If the statement STMT may clobber the memory reference REF return true,
1975 otherwise return false. */
1978 stmt_may_clobber_ref_p_1 (gimple stmt
, ao_ref
*ref
)
1980 if (is_gimple_call (stmt
))
1982 tree lhs
= gimple_call_lhs (stmt
);
1984 && TREE_CODE (lhs
) != SSA_NAME
)
1987 ao_ref_init (&r
, lhs
);
1988 if (refs_may_alias_p_1 (ref
, &r
, true))
1992 return call_may_clobber_ref_p_1 (stmt
, ref
);
1994 else if (gimple_assign_single_p (stmt
))
1996 tree lhs
= gimple_assign_lhs (stmt
);
1997 if (TREE_CODE (lhs
) != SSA_NAME
)
2000 ao_ref_init (&r
, lhs
);
2001 return refs_may_alias_p_1 (ref
, &r
, true);
2004 else if (gimple_code (stmt
) == GIMPLE_ASM
)
2011 stmt_may_clobber_ref_p (gimple stmt
, tree ref
)
2014 ao_ref_init (&r
, ref
);
2015 return stmt_may_clobber_ref_p_1 (stmt
, &r
);
2018 /* If STMT kills the memory reference REF return true, otherwise
2022 stmt_kills_ref_p_1 (gimple stmt
, ao_ref
*ref
)
2024 /* For a must-alias check we need to be able to constrain
2025 the access properly.
2026 FIXME: except for BUILTIN_FREE. */
2027 if (!ao_ref_base (ref
)
2028 || ref
->max_size
== -1)
2031 if (gimple_has_lhs (stmt
)
2032 && TREE_CODE (gimple_get_lhs (stmt
)) != SSA_NAME
2033 /* The assignment is not necessarily carried out if it can throw
2034 and we can catch it in the current function where we could inspect
2036 ??? We only need to care about the RHS throwing. For aggregate
2037 assignments or similar calls and non-call exceptions the LHS
2038 might throw as well. */
2039 && !stmt_can_throw_internal (stmt
))
2041 tree base
, lhs
= gimple_get_lhs (stmt
);
2042 HOST_WIDE_INT size
, offset
, max_size
, ref_offset
= ref
->offset
;
2043 base
= get_ref_base_and_extent (lhs
, &offset
, &size
, &max_size
);
2044 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
2045 so base == ref->base does not always hold. */
2046 if (base
!= ref
->base
)
2048 /* If both base and ref->base are MEM_REFs, only compare the
2049 first operand, and if the second operand isn't equal constant,
2050 try to add the offsets into offset and ref_offset. */
2051 if (TREE_CODE (base
) == MEM_REF
&& TREE_CODE (ref
->base
) == MEM_REF
2052 && TREE_OPERAND (base
, 0) == TREE_OPERAND (ref
->base
, 0))
2054 if (!tree_int_cst_equal (TREE_OPERAND (base
, 1),
2055 TREE_OPERAND (ref
->base
, 1)))
2057 offset_int off1
= mem_ref_offset (base
);
2058 off1
= wi::lshift (off1
, (BITS_PER_UNIT
== 8
2059 ? 3 : exact_log2 (BITS_PER_UNIT
)));
2061 offset_int off2
= mem_ref_offset (ref
->base
);
2062 off2
= wi::lshift (off2
, (BITS_PER_UNIT
== 8
2063 ? 3 : exact_log2 (BITS_PER_UNIT
)));
2065 if (wi::fits_shwi_p (off1
) && wi::fits_shwi_p (off2
))
2067 offset
= off1
.to_shwi ();
2068 ref_offset
= off2
.to_shwi ();
2077 /* For a must-alias check we need to be able to constrain
2078 the access properly. */
2079 if (size
!= -1 && size
== max_size
)
2081 if (offset
<= ref_offset
2082 && offset
+ size
>= ref_offset
+ ref
->max_size
)
2087 if (is_gimple_call (stmt
))
2089 tree callee
= gimple_call_fndecl (stmt
);
2090 if (callee
!= NULL_TREE
2091 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
2092 switch (DECL_FUNCTION_CODE (callee
))
2096 tree ptr
= gimple_call_arg (stmt
, 0);
2097 tree base
= ao_ref_base (ref
);
2098 if (base
&& TREE_CODE (base
) == MEM_REF
2099 && TREE_OPERAND (base
, 0) == ptr
)
2104 case BUILT_IN_MEMCPY
:
2105 case BUILT_IN_MEMPCPY
:
2106 case BUILT_IN_MEMMOVE
:
2107 case BUILT_IN_MEMSET
:
2108 case BUILT_IN_MEMCPY_CHK
:
2109 case BUILT_IN_MEMPCPY_CHK
:
2110 case BUILT_IN_MEMMOVE_CHK
:
2111 case BUILT_IN_MEMSET_CHK
:
2113 tree dest
= gimple_call_arg (stmt
, 0);
2114 tree len
= gimple_call_arg (stmt
, 2);
2115 if (!tree_fits_shwi_p (len
))
2117 tree rbase
= ref
->base
;
2118 offset_int roffset
= ref
->offset
;
2120 ao_ref_init_from_ptr_and_size (&dref
, dest
, len
);
2121 tree base
= ao_ref_base (&dref
);
2122 offset_int offset
= dref
.offset
;
2123 if (!base
|| dref
.size
== -1)
2125 if (TREE_CODE (base
) == MEM_REF
)
2127 if (TREE_CODE (rbase
) != MEM_REF
)
2129 // Compare pointers.
2130 offset
+= mem_ref_offset (base
) * BITS_PER_UNIT
;
2131 roffset
+= mem_ref_offset (rbase
) * BITS_PER_UNIT
;
2132 base
= TREE_OPERAND (base
, 0);
2133 rbase
= TREE_OPERAND (rbase
, 0);
2137 offset_int size
= wi::to_offset (len
) * BITS_PER_UNIT
;
2138 if (wi::les_p (offset
, roffset
)
2139 && wi::les_p (roffset
+ ref
->max_size
, offset
+ size
))
2145 case BUILT_IN_VA_END
:
2147 tree ptr
= gimple_call_arg (stmt
, 0);
2148 if (TREE_CODE (ptr
) == ADDR_EXPR
)
2150 tree base
= ao_ref_base (ref
);
2151 if (TREE_OPERAND (ptr
, 0) == base
)
2164 stmt_kills_ref_p (gimple stmt
, tree ref
)
2167 ao_ref_init (&r
, ref
);
2168 return stmt_kills_ref_p_1 (stmt
, &r
);
2172 /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
2173 TARGET or a statement clobbering the memory reference REF in which
2174 case false is returned. The walk starts with VUSE, one argument of PHI. */
2177 maybe_skip_until (gimple phi
, tree target
, ao_ref
*ref
,
2178 tree vuse
, unsigned int *cnt
, bitmap
*visited
,
2179 bool abort_on_visited
)
2181 basic_block bb
= gimple_bb (phi
);
2184 *visited
= BITMAP_ALLOC (NULL
);
2186 bitmap_set_bit (*visited
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
2188 /* Walk until we hit the target. */
2189 while (vuse
!= target
)
2191 gimple def_stmt
= SSA_NAME_DEF_STMT (vuse
);
2192 /* Recurse for PHI nodes. */
2193 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2195 /* An already visited PHI node ends the walk successfully. */
2196 if (bitmap_bit_p (*visited
, SSA_NAME_VERSION (PHI_RESULT (def_stmt
))))
2197 return !abort_on_visited
;
2198 vuse
= get_continuation_for_phi (def_stmt
, ref
, cnt
,
2199 visited
, abort_on_visited
);
2204 else if (gimple_nop_p (def_stmt
))
2208 /* A clobbering statement or the end of the IL ends it failing. */
2210 if (stmt_may_clobber_ref_p_1 (def_stmt
, ref
))
2213 /* If we reach a new basic-block see if we already skipped it
2214 in a previous walk that ended successfully. */
2215 if (gimple_bb (def_stmt
) != bb
)
2217 if (!bitmap_set_bit (*visited
, SSA_NAME_VERSION (vuse
)))
2218 return !abort_on_visited
;
2219 bb
= gimple_bb (def_stmt
);
2221 vuse
= gimple_vuse (def_stmt
);
2226 /* For two PHI arguments ARG0 and ARG1 try to skip non-aliasing code
2227 until we hit the phi argument definition that dominates the other one.
2228 Return that, or NULL_TREE if there is no such definition. */
2231 get_continuation_for_phi_1 (gimple phi
, tree arg0
, tree arg1
,
2232 ao_ref
*ref
, unsigned int *cnt
,
2233 bitmap
*visited
, bool abort_on_visited
)
2235 gimple def0
= SSA_NAME_DEF_STMT (arg0
);
2236 gimple def1
= SSA_NAME_DEF_STMT (arg1
);
2241 else if (gimple_nop_p (def0
)
2242 || (!gimple_nop_p (def1
)
2243 && dominated_by_p (CDI_DOMINATORS
,
2244 gimple_bb (def1
), gimple_bb (def0
))))
2246 if (maybe_skip_until (phi
, arg0
, ref
, arg1
, cnt
,
2247 visited
, abort_on_visited
))
2250 else if (gimple_nop_p (def1
)
2251 || dominated_by_p (CDI_DOMINATORS
,
2252 gimple_bb (def0
), gimple_bb (def1
)))
2254 if (maybe_skip_until (phi
, arg1
, ref
, arg0
, cnt
,
2255 visited
, abort_on_visited
))
2258 /* Special case of a diamond:
2260 goto (cond) ? L1 : L2
2261 L1: store1 = ... #MEM_2 = vuse(MEM_1)
2263 L2: store2 = ... #MEM_3 = vuse(MEM_1)
2264 L3: MEM_4 = PHI<MEM_2, MEM_3>
2265 We were called with the PHI at L3, MEM_2 and MEM_3 don't
2266 dominate each other, but still we can easily skip this PHI node
2267 if we recognize that the vuse MEM operand is the same for both,
2268 and that we can skip both statements (they don't clobber us).
2269 This is still linear. Don't use maybe_skip_until, that might
2270 potentially be slow. */
2271 else if ((common_vuse
= gimple_vuse (def0
))
2272 && common_vuse
== gimple_vuse (def1
))
2275 if (!stmt_may_clobber_ref_p_1 (def0
, ref
)
2276 && !stmt_may_clobber_ref_p_1 (def1
, ref
))
2284 /* Starting from a PHI node for the virtual operand of the memory reference
2285 REF find a continuation virtual operand that allows to continue walking
2286 statements dominating PHI skipping only statements that cannot possibly
2287 clobber REF. Increments *CNT for each alias disambiguation done.
2288 Returns NULL_TREE if no suitable virtual operand can be found. */
2291 get_continuation_for_phi (gimple phi
, ao_ref
*ref
,
2292 unsigned int *cnt
, bitmap
*visited
,
2293 bool abort_on_visited
)
2295 unsigned nargs
= gimple_phi_num_args (phi
);
2297 /* Through a single-argument PHI we can simply look through. */
2299 return PHI_ARG_DEF (phi
, 0);
2301 /* For two or more arguments try to pairwise skip non-aliasing code
2302 until we hit the phi argument definition that dominates the other one. */
2303 else if (nargs
>= 2)
2308 /* Find a candidate for the virtual operand which definition
2309 dominates those of all others. */
2310 arg0
= PHI_ARG_DEF (phi
, 0);
2311 if (!SSA_NAME_IS_DEFAULT_DEF (arg0
))
2312 for (i
= 1; i
< nargs
; ++i
)
2314 arg1
= PHI_ARG_DEF (phi
, i
);
2315 if (SSA_NAME_IS_DEFAULT_DEF (arg1
))
2320 if (dominated_by_p (CDI_DOMINATORS
,
2321 gimple_bb (SSA_NAME_DEF_STMT (arg0
)),
2322 gimple_bb (SSA_NAME_DEF_STMT (arg1
))))
2326 /* Then pairwise reduce against the found candidate. */
2327 for (i
= 0; i
< nargs
; ++i
)
2329 arg1
= PHI_ARG_DEF (phi
, i
);
2330 arg0
= get_continuation_for_phi_1 (phi
, arg0
, arg1
, ref
,
2331 cnt
, visited
, abort_on_visited
);
2342 /* Based on the memory reference REF and its virtual use VUSE call
2343 WALKER for each virtual use that is equivalent to VUSE, including VUSE
2344 itself. That is, for each virtual use for which its defining statement
2345 does not clobber REF.
2347 WALKER is called with REF, the current virtual use and DATA. If
2348 WALKER returns non-NULL the walk stops and its result is returned.
2349 At the end of a non-successful walk NULL is returned.
2351 TRANSLATE if non-NULL is called with a pointer to REF, the virtual
2352 use which definition is a statement that may clobber REF and DATA.
2353 If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
2354 If TRANSLATE returns non-NULL the walk stops and its result is returned.
2355 If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
2356 to adjust REF and *DATA to make that valid.
2358 TODO: Cache the vector of equivalent vuses per ref, vuse pair. */
2361 walk_non_aliased_vuses (ao_ref
*ref
, tree vuse
,
2362 void *(*walker
)(ao_ref
*, tree
, unsigned int, void *),
2363 void *(*translate
)(ao_ref
*, tree
, void *), void *data
)
2365 bitmap visited
= NULL
;
2367 unsigned int cnt
= 0;
2368 bool translated
= false;
2370 timevar_push (TV_ALIAS_STMT_WALK
);
2376 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
2377 res
= (*walker
) (ref
, vuse
, cnt
, data
);
2379 if (res
== (void *)-1)
2384 /* Lookup succeeded. */
2385 else if (res
!= NULL
)
2388 def_stmt
= SSA_NAME_DEF_STMT (vuse
);
2389 if (gimple_nop_p (def_stmt
))
2391 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2392 vuse
= get_continuation_for_phi (def_stmt
, ref
, &cnt
,
2393 &visited
, translated
);
2397 if (stmt_may_clobber_ref_p_1 (def_stmt
, ref
))
2401 res
= (*translate
) (ref
, vuse
, data
);
2402 /* Failed lookup and translation. */
2403 if (res
== (void *)-1)
2408 /* Lookup succeeded. */
2409 else if (res
!= NULL
)
2411 /* Translation succeeded, continue walking. */
2414 vuse
= gimple_vuse (def_stmt
);
2420 BITMAP_FREE (visited
);
2422 timevar_pop (TV_ALIAS_STMT_WALK
);
2428 /* Based on the memory reference REF call WALKER for each vdef which
2429 defining statement may clobber REF, starting with VDEF. If REF
2430 is NULL_TREE, each defining statement is visited.
2432 WALKER is called with REF, the current vdef and DATA. If WALKER
2433 returns true the walk is stopped, otherwise it continues.
2435 At PHI nodes walk_aliased_vdefs forks into one walk for reach
2436 PHI argument (but only one walk continues on merge points), the
2437 return value is true if any of the walks was successful.
2439 The function returns the number of statements walked. */
2442 walk_aliased_vdefs_1 (ao_ref
*ref
, tree vdef
,
2443 bool (*walker
)(ao_ref
*, tree
, void *), void *data
,
2444 bitmap
*visited
, unsigned int cnt
)
2448 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
2451 && !bitmap_set_bit (*visited
, SSA_NAME_VERSION (vdef
)))
2454 if (gimple_nop_p (def_stmt
))
2456 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2460 *visited
= BITMAP_ALLOC (NULL
);
2461 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); ++i
)
2462 cnt
+= walk_aliased_vdefs_1 (ref
, gimple_phi_arg_def (def_stmt
, i
),
2463 walker
, data
, visited
, 0);
2467 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
2470 || stmt_may_clobber_ref_p_1 (def_stmt
, ref
))
2471 && (*walker
) (ref
, vdef
, data
))
2474 vdef
= gimple_vuse (def_stmt
);
2480 walk_aliased_vdefs (ao_ref
*ref
, tree vdef
,
2481 bool (*walker
)(ao_ref
*, tree
, void *), void *data
,
2484 bitmap local_visited
= NULL
;
2487 timevar_push (TV_ALIAS_STMT_WALK
);
2489 ret
= walk_aliased_vdefs_1 (ref
, vdef
, walker
, data
,
2490 visited
? visited
: &local_visited
, 0);
2492 BITMAP_FREE (local_visited
);
2494 timevar_pop (TV_ALIAS_STMT_WALK
);