1 /* Alias analysis for trees.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
34 #include "langhooks.h"
37 #include "diagnostic.h"
38 #include "tree-dump.h"
40 #include "tree-flow.h"
41 #include "tree-inline.h"
42 #include "tree-pass.h"
45 #include "ipa-type-escape.h"
49 #include "pointer-set.h"
50 #include "alloc-pool.h"
51 #include "tree-ssa-alias.h"
53 /* Broad overview of how alias analysis on gimple works:
55 Statements clobbering or using memory are linked through the
56 virtual operand factored use-def chain. The virtual operand
57 is unique per function, its symbol is accessible via gimple_vop (cfun).
58 Virtual operands are used for efficiently walking memory statements
59 in the gimple IL and are useful for things like value-numbering as
60 a generation count for memory references.
62 SSA_NAME pointers may have associated points-to information
63 accessible via the SSA_NAME_PTR_INFO macro. Flow-insensitive
64 points-to information is (re-)computed by the TODO_rebuild_alias
65 pass manager todo. Points-to information is also used for more
66 precise tracking of call-clobbered and call-used variables and
67 related disambiguations.
69 This file contains functions for disambiguating memory references,
70 the so called alias-oracle and tools for walking of the gimple IL.
72 The main alias-oracle entry-points are
74 bool stmt_may_clobber_ref_p (gimple, tree)
76 This function queries if a statement may invalidate (parts of)
77 the memory designated by the reference tree argument.
79 bool ref_maybe_used_by_stmt_p (gimple, tree)
81 This function queries if a statement may need (parts of) the
82 memory designated by the reference tree argument.
84 There are variants of these functions that only handle the call
85 part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
86 Note that these do not disambiguate against a possible call lhs.
88 bool refs_may_alias_p (tree, tree)
90 This function tries to disambiguate two reference trees.
92 bool ptr_deref_may_alias_global_p (tree)
94 This function queries if dereferencing a pointer variable may
97 More low-level disambiguators are available and documented in
98 this file. Low-level disambiguators dealing with points-to
99 information are in tree-ssa-structalias.c. */
102 /* Query statistics for the different low-level disambiguators.
103 A high-level query may trigger multiple of them. */
106 unsigned HOST_WIDE_INT refs_may_alias_p_may_alias;
107 unsigned HOST_WIDE_INT refs_may_alias_p_no_alias;
108 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias;
109 unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias;
110 unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias;
111 unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias;
115 dump_alias_stats (FILE *s)
117 fprintf (s, "\nAlias oracle query stats:\n");
118 fprintf (s, " refs_may_alias_p: "
119 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
120 HOST_WIDE_INT_PRINT_DEC" queries\n",
121 alias_stats.refs_may_alias_p_no_alias,
122 alias_stats.refs_may_alias_p_no_alias
123 + alias_stats.refs_may_alias_p_may_alias);
124 fprintf (s, " ref_maybe_used_by_call_p: "
125 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
126 HOST_WIDE_INT_PRINT_DEC" queries\n",
127 alias_stats.ref_maybe_used_by_call_p_no_alias,
128 alias_stats.refs_may_alias_p_no_alias
129 + alias_stats.ref_maybe_used_by_call_p_may_alias);
130 fprintf (s, " call_may_clobber_ref_p: "
131 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
132 HOST_WIDE_INT_PRINT_DEC" queries\n",
133 alias_stats.call_may_clobber_ref_p_no_alias,
134 alias_stats.call_may_clobber_ref_p_no_alias
135 + alias_stats.call_may_clobber_ref_p_may_alias);
139 /* Return true, if dereferencing PTR may alias with a global variable. */
142 ptr_deref_may_alias_global_p (tree ptr)
144 struct ptr_info_def *pi;
146 /* If we end up with a pointer constant here that may point
148 if (TREE_CODE (ptr) != SSA_NAME)
151 pi = SSA_NAME_PTR_INFO (ptr);
153 /* If we do not have points-to information for this variable,
158 /* ??? This does not use TBAA to prune globals ptr may not access. */
159 return pt_solution_includes_global (&pi->pt);
162 /* Return true if dereferencing PTR may alias DECL.
163 The caller is responsible for applying TBAA to see if PTR
164 may access DECL at all. */
167 ptr_deref_may_alias_decl_p (tree ptr, tree decl)
169 struct ptr_info_def *pi;
171 /* ??? During SCCVN/PRE we can end up with *&x during valueizing
172 operands. Likewise we can end up with dereferencing constant
173 pointers. Just bail out in these cases for now. */
174 if (TREE_CODE (ptr) == ADDR_EXPR
175 || TREE_CODE (ptr) == INTEGER_CST)
178 gcc_assert (TREE_CODE (ptr) == SSA_NAME
179 && (TREE_CODE (decl) == VAR_DECL
180 || TREE_CODE (decl) == PARM_DECL
181 || TREE_CODE (decl) == RESULT_DECL));
183 /* Non-aliased variables can not be pointed to. */
184 if (!may_be_aliased (decl))
187 /* If we do not have useful points-to information for this pointer
188 we cannot disambiguate anything else. */
189 pi = SSA_NAME_PTR_INFO (ptr);
193 return pt_solution_includes (&pi->pt, decl);
196 /* Return true if dereferenced PTR1 and PTR2 may alias.
197 The caller is responsible for applying TBAA to see if accesses
198 through PTR1 and PTR2 may conflict at all. */
201 ptr_derefs_may_alias_p (tree ptr1, tree ptr2)
203 struct ptr_info_def *pi1, *pi2;
205 /* ??? During SCCVN/PRE we can end up with *&x during valueizing
206 operands. Likewise we can end up with dereferencing constant
207 pointers. Just bail out in these cases for now. */
208 if (TREE_CODE (ptr1) == ADDR_EXPR
209 || TREE_CODE (ptr1) == INTEGER_CST
210 || TREE_CODE (ptr2) == ADDR_EXPR
211 || TREE_CODE (ptr2) == INTEGER_CST)
214 gcc_assert (TREE_CODE (ptr1) == SSA_NAME
215 && TREE_CODE (ptr2) == SSA_NAME);
217 /* We may end up with two empty points-to solutions for two same pointers.
218 In this case we still want to say both pointers alias, so shortcut
223 /* If we do not have useful points-to information for either pointer
224 we cannot disambiguate anything else. */
225 pi1 = SSA_NAME_PTR_INFO (ptr1);
226 pi2 = SSA_NAME_PTR_INFO (ptr2);
230 /* ??? This does not use TBAA to prune decls from the intersection
231 that not both pointers may access. */
232 return pt_solutions_intersect (&pi1->pt, &pi2->pt);
236 /* Dump alias information on FILE. */
239 dump_alias_info (FILE *file)
243 = lang_hooks.decl_printable_name (current_function_decl, 2);
244 referenced_var_iterator rvi;
247 fprintf (file, "\n\nAlias information for %s\n\n", funcname);
249 fprintf (file, "Aliased symbols\n\n");
251 FOR_EACH_REFERENCED_VAR (var, rvi)
253 if (may_be_aliased (var))
254 dump_variable (file, var);
257 fprintf (file, "\nCall clobber information\n");
259 fprintf (file, "\nESCAPED");
260 dump_points_to_solution (file, &cfun->gimple_df->escaped);
261 fprintf (file, "\nCALLUSED");
262 dump_points_to_solution (file, &cfun->gimple_df->callused);
264 fprintf (file, "\n\nFlow-insensitive points-to information\n\n");
266 for (i = 1; i < num_ssa_names; i++)
268 tree ptr = ssa_name (i);
269 struct ptr_info_def *pi;
272 || SSA_NAME_IN_FREE_LIST (ptr))
275 pi = SSA_NAME_PTR_INFO (ptr);
277 dump_points_to_info_for (file, ptr);
280 fprintf (file, "\n");
284 /* Dump alias information on stderr. */
287 debug_alias_info (void)
289 dump_alias_info (stderr);
293 /* Return the alias information associated with pointer T. It creates a
294 new instance if none existed. */
296 struct ptr_info_def *
297 get_ptr_info (tree t)
299 struct ptr_info_def *pi;
301 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
303 pi = SSA_NAME_PTR_INFO (t);
306 pi = GGC_CNEW (struct ptr_info_def);
307 pt_solution_reset (&pi->pt);
308 SSA_NAME_PTR_INFO (t) = pi;
314 /* Dump the points-to set *PT into FILE. */
317 dump_points_to_solution (FILE *file, struct pt_solution *pt)
320 fprintf (file, ", points-to anything");
323 fprintf (file, ", points-to non-local");
326 fprintf (file, ", points-to escaped");
329 fprintf (file, ", points-to NULL");
333 fprintf (file, ", points-to vars: ");
334 dump_decl_set (file, pt->vars);
335 if (pt->vars_contains_global)
336 fprintf (file, " (includes global vars)");
340 /* Dump points-to information for SSA_NAME PTR into FILE. */
343 dump_points_to_info_for (FILE *file, tree ptr)
345 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
347 print_generic_expr (file, ptr, dump_flags);
350 dump_points_to_solution (file, &pi->pt);
352 fprintf (file, ", points-to anything");
354 fprintf (file, "\n");
358 /* Dump points-to information for VAR into stderr. */
361 debug_points_to_info_for (tree var)
363 dump_points_to_info_for (stderr, var);
367 /* Initializes the alias-oracle reference representation *R from REF. */
370 ao_ref_init (ao_ref *r, tree ref)
377 r->ref_alias_set = -1;
378 r->base_alias_set = -1;
381 /* Returns the base object of the memory reference *REF. */
384 ao_ref_base (ao_ref *ref)
388 ref->base = get_ref_base_and_extent (ref->ref, &ref->offset, &ref->size,
393 /* Returns the base object alias set of the memory reference *REF. */
395 static alias_set_type ATTRIBUTE_UNUSED
396 ao_ref_base_alias_set (ao_ref *ref)
398 if (ref->base_alias_set != -1)
399 return ref->base_alias_set;
400 ref->base_alias_set = get_alias_set (ao_ref_base (ref));
401 return ref->base_alias_set;
404 /* Returns the reference alias set of the memory reference *REF. */
407 ao_ref_alias_set (ao_ref *ref)
409 if (ref->ref_alias_set != -1)
410 return ref->ref_alias_set;
411 ref->ref_alias_set = get_alias_set (ref->ref);
412 return ref->ref_alias_set;
415 /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
416 purpose of TBAA. Return 0 if they are distinct and -1 if we cannot
420 same_type_for_tbaa (tree type1, tree type2)
422 type1 = TYPE_MAIN_VARIANT (type1);
423 type2 = TYPE_MAIN_VARIANT (type2);
425 /* If we would have to do structural comparison bail out. */
426 if (TYPE_STRUCTURAL_EQUALITY_P (type1)
427 || TYPE_STRUCTURAL_EQUALITY_P (type2))
430 /* Compare the canonical types. */
431 if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
434 /* ??? Array types are not properly unified in all cases as we have
435 spurious changes in the index types for example. Removing this
436 causes all sorts of problems with the Fortran frontend. */
437 if (TREE_CODE (type1) == ARRAY_TYPE
438 && TREE_CODE (type2) == ARRAY_TYPE)
441 /* The types are known to be not equal. */
445 /* Determine if the two component references REF1 and REF2 which are
446 based on access types TYPE1 and TYPE2 and of which at least one is based
447 on an indirect reference may alias. */
450 nonaliasing_component_refs_p (tree ref1, tree type1,
451 HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
452 tree ref2, tree type2,
453 HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2)
455 /* If one reference is a component references through pointers try to find a
456 common base and apply offset based disambiguation. This handles
458 struct A { int i; int j; } *q;
459 struct B { struct A a; int k; } *p;
460 disambiguating q->i and p->a.j. */
464 /* Now search for the type1 in the access path of ref2. This
465 would be a common base for doing offset based disambiguation on. */
467 while (handled_component_p (*refp)
468 && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0)
469 refp = &TREE_OPERAND (*refp, 0);
470 same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1);
471 /* If we couldn't compare types we have to bail out. */
474 else if (same_p == 1)
476 HOST_WIDE_INT offadj, sztmp, msztmp;
477 get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
479 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
481 /* If we didn't find a common base, try the other way around. */
483 while (handled_component_p (*refp)
484 && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0)
485 refp = &TREE_OPERAND (*refp, 0);
486 same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2);
487 /* If we couldn't compare types we have to bail out. */
490 else if (same_p == 1)
492 HOST_WIDE_INT offadj, sztmp, msztmp;
493 get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
495 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
497 /* If we have two type access paths B1.path1 and B2.path2 they may
498 only alias if either B1 is in B2.path2 or B2 is in B1.path1. */
502 /* Return true if two memory references based on the variables BASE1
503 and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1[ and
504 [OFFSET2, OFFSET2 + MAX_SIZE2[ may alias. */
507 decl_refs_may_alias_p (tree base1,
508 HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
510 HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2)
512 gcc_assert (SSA_VAR_P (base1) && SSA_VAR_P (base2));
514 /* If both references are based on different variables, they cannot alias. */
515 if (!operand_equal_p (base1, base2, 0))
518 /* If both references are based on the same variable, they cannot alias if
519 the accesses do not overlap. */
520 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
523 /* Return true if an indirect reference based on *PTR1 constrained
524 to [OFFSET1, OFFSET1 + MAX_SIZE1[ may alias a variable based on BASE2
525 constrained to [OFFSET2, OFFSET2 + MAX_SIZE2[. *PTR1 and BASE2 have
526 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
527 in which case they are computed on-demand. REF1 and REF2
528 if non-NULL are the complete memory reference trees. */
531 indirect_ref_may_alias_decl_p (tree ref1, tree ptr1,
532 HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
533 alias_set_type base1_alias_set,
534 tree ref2, tree base2,
535 HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
536 alias_set_type base2_alias_set)
538 /* If only one reference is based on a variable, they cannot alias if
539 the pointer access is beyond the extent of the variable access.
540 (the pointer base cannot validly point to an offset less than zero
542 They also cannot alias if the pointer may not point to the decl. */
544 && !ranges_overlap_p (offset1, max_size1, 0, offset2 + max_size2))
546 if (!ptr_deref_may_alias_decl_p (ptr1, base2))
549 /* Disambiguations that rely on strict aliasing rules follow. */
550 if (!flag_strict_aliasing)
553 /* If the alias set for a pointer access is zero all bets are off. */
554 if (base1_alias_set == -1)
555 base1_alias_set = get_deref_alias_set (ptr1);
556 if (base1_alias_set == 0)
558 if (base2_alias_set == -1)
559 base2_alias_set = get_alias_set (base2);
561 /* If both references are through the same type, they do not alias
562 if the accesses do not overlap. This does extra disambiguation
563 for mixed/pointer accesses but requires strict aliasing. */
564 if (same_type_for_tbaa (TREE_TYPE (TREE_TYPE (ptr1)),
565 TREE_TYPE (base2)) == 1)
566 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
568 /* The only way to access a variable is through a pointer dereference
569 of the same alias set or a subset of it. */
570 if (base1_alias_set != base2_alias_set
571 && !alias_set_subset_of (base1_alias_set, base2_alias_set))
574 /* Do access-path based disambiguation. */
576 && handled_component_p (ref1)
577 && handled_component_p (ref2))
578 return nonaliasing_component_refs_p (ref1, TREE_TYPE (TREE_TYPE (ptr1)),
580 ref2, TREE_TYPE (base2),
586 /* Return true if two indirect references based on *PTR1
587 and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1[ and
588 [OFFSET2, OFFSET2 + MAX_SIZE2[ may alias. *PTR1 and *PTR2 have
589 the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
590 in which case they are computed on-demand. REF1 and REF2
591 if non-NULL are the complete memory reference trees. */
594 indirect_refs_may_alias_p (tree ref1, tree ptr1,
595 HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
596 alias_set_type base1_alias_set,
597 tree ref2, tree ptr2,
598 HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
599 alias_set_type base2_alias_set)
601 /* If both bases are based on pointers they cannot alias if they may not
602 point to the same memory object or if they point to the same object
603 and the accesses do not overlap. */
604 if (operand_equal_p (ptr1, ptr2, 0))
605 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
606 if (!ptr_derefs_may_alias_p (ptr1, ptr2))
609 /* Disambiguations that rely on strict aliasing rules follow. */
610 if (!flag_strict_aliasing)
613 /* If the alias set for a pointer access is zero all bets are off. */
614 if (base1_alias_set == -1)
615 base1_alias_set = get_deref_alias_set (ptr1);
616 if (base1_alias_set == 0)
618 if (base2_alias_set == -1)
619 base2_alias_set = get_deref_alias_set (ptr2);
620 if (base2_alias_set == 0)
623 /* If both references are through the same type, they do not alias
624 if the accesses do not overlap. This does extra disambiguation
625 for mixed/pointer accesses but requires strict aliasing. */
626 if (same_type_for_tbaa (TREE_TYPE (TREE_TYPE (ptr1)),
627 TREE_TYPE (TREE_TYPE (ptr2))) == 1)
628 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
630 /* Do type-based disambiguation. */
631 if (base1_alias_set != base2_alias_set
632 && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
635 /* Do access-path based disambiguation. */
637 && handled_component_p (ref1)
638 && handled_component_p (ref2))
639 return nonaliasing_component_refs_p (ref1, TREE_TYPE (TREE_TYPE (ptr1)),
641 ref2, TREE_TYPE (TREE_TYPE (ptr2)),
647 /* Return true, if the two memory references REF1 and REF2 may alias. */
650 refs_may_alias_p_1 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
653 HOST_WIDE_INT offset1 = 0, offset2 = 0;
654 HOST_WIDE_INT size1 = -1, size2 = -1;
655 HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
656 bool var1_p, var2_p, ind1_p, ind2_p;
659 gcc_assert ((!ref1->ref
660 || SSA_VAR_P (ref1->ref)
661 || handled_component_p (ref1->ref)
662 || INDIRECT_REF_P (ref1->ref)
663 || TREE_CODE (ref1->ref) == TARGET_MEM_REF)
665 || SSA_VAR_P (ref2->ref)
666 || handled_component_p (ref2->ref)
667 || INDIRECT_REF_P (ref2->ref)
668 || TREE_CODE (ref2->ref) == TARGET_MEM_REF));
670 /* Decompose the references into their base objects and the access. */
671 base1 = ao_ref_base (ref1);
672 offset1 = ref1->offset;
674 max_size1 = ref1->max_size;
675 base2 = ao_ref_base (ref2);
676 offset2 = ref2->offset;
678 max_size2 = ref2->max_size;
680 /* We can end up with registers or constants as bases for example from
681 *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
682 which is seen as a struct copy. */
683 if (TREE_CODE (base1) == SSA_NAME
684 || TREE_CODE (base2) == SSA_NAME
685 || is_gimple_min_invariant (base1)
686 || is_gimple_min_invariant (base2))
689 /* Defer to simple offset based disambiguation if we have
690 references based on two decls. Do this before defering to
691 TBAA to handle must-alias cases in conformance with the
692 GCC extension of allowing type-punning through unions. */
693 var1_p = SSA_VAR_P (base1);
694 var2_p = SSA_VAR_P (base2);
695 if (var1_p && var2_p)
696 return decl_refs_may_alias_p (base1, offset1, max_size1,
697 base2, offset2, max_size2);
699 /* First defer to TBAA if possible. */
701 && flag_strict_aliasing
702 && !alias_sets_conflict_p (ao_ref_alias_set (ref1),
703 ao_ref_alias_set (ref2)))
706 /* If one reference is a TARGET_MEM_REF weird things are allowed. Still
707 TBAA disambiguation based on the access type is possible, so bail
708 out only after that check. */
709 if ((ref1->ref && TREE_CODE (ref1->ref) == TARGET_MEM_REF)
710 || (ref2->ref && TREE_CODE (ref2->ref) == TARGET_MEM_REF))
713 /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators. */
714 ind1_p = INDIRECT_REF_P (base1);
715 ind2_p = INDIRECT_REF_P (base2);
716 set = tbaa_p ? -1 : 0;
717 if (var1_p && ind2_p)
718 return indirect_ref_may_alias_decl_p (ref2->ref, TREE_OPERAND (base2, 0),
719 offset2, max_size2, set,
721 offset1, max_size1, set);
722 else if (ind1_p && var2_p)
723 return indirect_ref_may_alias_decl_p (ref1->ref, TREE_OPERAND (base1, 0),
724 offset1, max_size1, set,
726 offset2, max_size2, set);
727 else if (ind1_p && ind2_p)
728 return indirect_refs_may_alias_p (ref1->ref, TREE_OPERAND (base1, 0),
729 offset1, max_size1, set,
730 ref2->ref, TREE_OPERAND (base2, 0),
731 offset2, max_size2, set);
737 refs_may_alias_p (tree ref1, tree ref2)
741 ao_ref_init (&r1, ref1);
742 ao_ref_init (&r2, ref2);
743 res = refs_may_alias_p_1 (&r1, &r2, true);
745 ++alias_stats.refs_may_alias_p_may_alias;
747 ++alias_stats.refs_may_alias_p_no_alias;
751 /* Returns true if there is a anti-dependence for the STORE that
752 executes after the LOAD. */
755 refs_anti_dependent_p (tree load, tree store)
758 ao_ref_init (&r1, load);
759 ao_ref_init (&r2, store);
760 return refs_may_alias_p_1 (&r1, &r2, false);
763 /* Returns true if there is a output dependence for the stores
764 STORE1 and STORE2. */
767 refs_output_dependent_p (tree store1, tree store2)
770 ao_ref_init (&r1, store1);
771 ao_ref_init (&r2, store2);
772 return refs_may_alias_p_1 (&r1, &r2, false);
775 /* If the call CALL may use the memory reference REF return true,
776 otherwise return false. */
779 ref_maybe_used_by_call_p_1 (gimple call, tree ref)
783 int flags = gimple_call_flags (call);
785 /* Const functions without a static chain do not implicitly use memory. */
786 if (!gimple_call_chain (call)
787 && (flags & (ECF_CONST|ECF_NOVOPS)))
790 /* If the reference is not based on a decl give up.
791 ??? Handle indirect references by intersecting the call-used
792 solution with that of the pointer. */
793 base = get_base_address (ref);
798 /* If the reference is based on a decl that is not aliased the call
799 cannot possibly use it. */
801 && !may_be_aliased (base)
802 /* But local statics can be used through recursion. */
803 && !is_global_var (base))
806 /* Check if base is a global static variable that is not read
808 if (TREE_CODE (base) == VAR_DECL
809 && TREE_STATIC (base)
810 && !TREE_PUBLIC (base))
812 tree callee = gimple_call_fndecl (call);
815 if (callee != NULL_TREE
817 = ipa_reference_get_not_read_global (cgraph_node (callee)))
818 && bitmap_bit_p (not_read, DECL_UID (base)))
822 /* If the base variable is call-used or call-clobbered then
824 if (flags & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
826 if (is_call_used (base))
831 if (is_call_clobbered (base))
835 /* Inspect call arguments for passed-by-value aliases. */
837 for (i = 0; i < gimple_call_num_args (call); ++i)
839 tree op = gimple_call_arg (call, i);
841 if (TREE_CODE (op) == EXC_PTR_EXPR
842 || TREE_CODE (op) == FILTER_EXPR)
845 if (TREE_CODE (op) == WITH_SIZE_EXPR)
846 op = TREE_OPERAND (op, 0);
848 if (TREE_CODE (op) != SSA_NAME
849 && !is_gimple_min_invariant (op)
850 && refs_may_alias_p (op, ref))
858 ref_maybe_used_by_call_p (gimple call, tree ref)
860 bool res = ref_maybe_used_by_call_p_1 (call, ref);
862 ++alias_stats.ref_maybe_used_by_call_p_may_alias;
864 ++alias_stats.ref_maybe_used_by_call_p_no_alias;
869 /* If the statement STMT may use the memory reference REF return
870 true, otherwise return false. */
873 ref_maybe_used_by_stmt_p (gimple stmt, tree ref)
875 if (is_gimple_assign (stmt))
879 /* All memory assign statements are single. */
880 if (!gimple_assign_single_p (stmt))
883 rhs = gimple_assign_rhs1 (stmt);
884 if (is_gimple_reg (rhs)
885 || is_gimple_min_invariant (rhs)
886 || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
889 return refs_may_alias_p (rhs, ref);
891 else if (is_gimple_call (stmt))
892 return ref_maybe_used_by_call_p (stmt, ref);
897 /* If the call in statement CALL may clobber the memory reference REF
898 return true, otherwise return false. */
901 call_may_clobber_ref_p_1 (gimple call, ao_ref *ref)
905 /* If the call is pure or const it cannot clobber anything. */
906 if (gimple_call_flags (call)
907 & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
910 base = ao_ref_base (ref);
914 if (TREE_CODE (base) == SSA_NAME
915 || CONSTANT_CLASS_P (base))
918 /* If the reference is based on a decl that is not aliased the call
919 cannot possibly clobber it. */
921 && !may_be_aliased (base)
922 /* But local non-readonly statics can be modified through recursion
923 or the call may implement a threading barrier which we must
925 && (TREE_READONLY (base)
926 || !is_global_var (base)))
929 /* Check if base is a global static variable that is not written
931 if (TREE_CODE (base) == VAR_DECL
932 && TREE_STATIC (base)
933 && !TREE_PUBLIC (base))
935 tree callee = gimple_call_fndecl (call);
938 if (callee != NULL_TREE
940 = ipa_reference_get_not_written_global (cgraph_node (callee)))
941 && bitmap_bit_p (not_written, DECL_UID (base)))
946 return is_call_clobbered (base);
951 static bool ATTRIBUTE_UNUSED
952 call_may_clobber_ref_p (gimple call, tree ref)
956 ao_ref_init (&r, ref);
957 res = call_may_clobber_ref_p_1 (call, &r);
959 ++alias_stats.call_may_clobber_ref_p_may_alias;
961 ++alias_stats.call_may_clobber_ref_p_no_alias;
966 /* If the statement STMT may clobber the memory reference REF return true,
967 otherwise return false. */
970 stmt_may_clobber_ref_p_1 (gimple stmt, ao_ref *ref)
972 if (is_gimple_call (stmt))
974 tree lhs = gimple_call_lhs (stmt);
976 && !is_gimple_reg (lhs))
979 ao_ref_init (&r, lhs);
980 if (refs_may_alias_p_1 (ref, &r, true))
984 return call_may_clobber_ref_p_1 (stmt, ref);
986 else if (is_gimple_assign (stmt))
989 ao_ref_init (&r, gimple_assign_lhs (stmt));
990 return refs_may_alias_p_1 (ref, &r, true);
992 else if (gimple_code (stmt) == GIMPLE_ASM)
999 stmt_may_clobber_ref_p (gimple stmt, tree ref)
1002 ao_ref_init (&r, ref);
1003 return stmt_may_clobber_ref_p_1 (stmt, &r);
1007 static tree get_continuation_for_phi (gimple, ao_ref *, bitmap *);
1009 /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
1010 TARGET or a statement clobbering the memory reference REF in which
1011 case false is returned. The walk starts with VUSE, one argument of PHI. */
1014 maybe_skip_until (gimple phi, tree target, ao_ref *ref,
1015 tree vuse, bitmap *visited)
1018 *visited = BITMAP_ALLOC (NULL);
1020 bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
1022 /* Walk until we hit the target. */
1023 while (vuse != target)
1025 gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1026 /* Recurse for PHI nodes. */
1027 if (gimple_code (def_stmt) == GIMPLE_PHI)
1029 /* An already visited PHI node ends the walk successfully. */
1030 if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (def_stmt))))
1032 vuse = get_continuation_for_phi (def_stmt, ref, visited);
1037 /* A clobbering statement or the end of the IL ends it failing. */
1038 else if (gimple_nop_p (def_stmt)
1039 || stmt_may_clobber_ref_p_1 (def_stmt, ref))
1041 vuse = gimple_vuse (def_stmt);
1046 /* Starting from a PHI node for the virtual operand of the memory reference
1047 REF find a continuation virtual operand that allows to continue walking
1048 statements dominating PHI skipping only statements that cannot possibly
1049 clobber REF. Returns NULL_TREE if no suitable virtual operand can
1053 get_continuation_for_phi (gimple phi, ao_ref *ref, bitmap *visited)
1055 unsigned nargs = gimple_phi_num_args (phi);
1057 /* Through a single-argument PHI we can simply look through. */
1059 return PHI_ARG_DEF (phi, 0);
1061 /* For two arguments try to skip non-aliasing code until we hit
1062 the phi argument definition that dominates the other one. */
1065 tree arg0 = PHI_ARG_DEF (phi, 0);
1066 tree arg1 = PHI_ARG_DEF (phi, 1);
1067 gimple def0 = SSA_NAME_DEF_STMT (arg0);
1068 gimple def1 = SSA_NAME_DEF_STMT (arg1);
1072 else if (gimple_nop_p (def0)
1073 || (!gimple_nop_p (def1)
1074 && dominated_by_p (CDI_DOMINATORS,
1075 gimple_bb (def1), gimple_bb (def0))))
1077 if (maybe_skip_until (phi, arg0, ref, arg1, visited))
1080 else if (gimple_nop_p (def1)
1081 || dominated_by_p (CDI_DOMINATORS,
1082 gimple_bb (def0), gimple_bb (def1)))
1084 if (maybe_skip_until (phi, arg1, ref, arg0, visited))
1092 /* Based on the memory reference REF and its virtual use VUSE call
1093 WALKER for each virtual use that is equivalent to VUSE, including VUSE
1094 itself. That is, for each virtual use for which its defining statement
1095 does not clobber REF.
1097 WALKER is called with REF, the current virtual use and DATA. If
1098 WALKER returns non-NULL the walk stops and its result is returned.
1099 At the end of a non-successful walk NULL is returned.
1101 TRANSLATE if non-NULL is called with a pointer to REF, the virtual
1102 use which definition is a statement that may clobber REF and DATA.
1103 If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
1104 If TRANSLATE returns non-NULL the walk stops and its result is returned.
1105 If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
1106 to adjust REF and *DATA to make that valid.
1108 TODO: Cache the vector of equivalent vuses per ref, vuse pair. */
1111 walk_non_aliased_vuses (ao_ref *ref, tree vuse,
1112 void *(*walker)(ao_ref *, tree, void *),
1113 void *(*translate)(ao_ref *, tree, void *), void *data)
1115 bitmap visited = NULL;
1118 timevar_push (TV_ALIAS_STMT_WALK);
1124 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
1125 res = (*walker) (ref, vuse, data);
1129 def_stmt = SSA_NAME_DEF_STMT (vuse);
1130 if (gimple_nop_p (def_stmt))
1132 else if (gimple_code (def_stmt) == GIMPLE_PHI)
1133 vuse = get_continuation_for_phi (def_stmt, ref, &visited);
1136 if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
1140 res = (*translate) (ref, vuse, data);
1141 /* Failed lookup and translation. */
1142 if (res == (void *)-1)
1147 /* Lookup succeeded. */
1148 else if (res != NULL)
1150 /* Translation succeeded, continue walking. */
1152 vuse = gimple_vuse (def_stmt);
1158 BITMAP_FREE (visited);
1160 timevar_pop (TV_ALIAS_STMT_WALK);
1166 /* Based on the memory reference REF call WALKER for each vdef which
1167 defining statement may clobber REF, starting with VDEF. If REF
1168 is NULL_TREE, each defining statement is visited.
1170 WALKER is called with REF, the current vdef and DATA. If WALKER
1171 returns true the walk is stopped, otherwise it continues.
1173 At PHI nodes walk_aliased_vdefs forks into one walk for reach
1174 PHI argument (but only one walk continues on merge points), the
1175 return value is true if any of the walks was successful.
1177 The function returns the number of statements walked. */
1180 walk_aliased_vdefs_1 (tree ref, tree vdef,
1181 bool (*walker)(tree, tree, void *), void *data,
1182 bitmap *visited, unsigned int cnt)
1186 gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
1189 && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
1192 if (gimple_nop_p (def_stmt))
1194 else if (gimple_code (def_stmt) == GIMPLE_PHI)
1198 *visited = BITMAP_ALLOC (NULL);
1199 for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
1200 cnt += walk_aliased_vdefs_1 (ref, gimple_phi_arg_def (def_stmt, i),
1201 walker, data, visited, 0);
1205 /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
1208 || stmt_may_clobber_ref_p (def_stmt, ref))
1209 && (*walker) (ref, vdef, data))
1212 vdef = gimple_vuse (def_stmt);
1218 walk_aliased_vdefs (tree ref, tree vdef,
1219 bool (*walker)(tree, tree, void *), void *data,
1222 bitmap local_visited = NULL;
1225 timevar_push (TV_ALIAS_STMT_WALK);
1227 ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
1228 visited ? visited : &local_visited, 0);
1230 BITMAP_FREE (local_visited);
1232 timevar_pop (TV_ALIAS_STMT_WALK);