The following patch addresses PR67170 which shows we fail to disambiguate
INTENT(IN) variables against for example recursive calls. The trick
in solving this is to notice that when a function has a fn spec
attribute that says memory reachable by a parameter is not modified
then that memory behaves as if it were readonly throughout the function
and thus it doesn't have a dependence on any other reference in that
function.
In the PR I prototyped a patch in the alias oracle itself but that's
too expensive (we need to find the index of a PARM_DECL). Thus the
following patch implements that trick in the value-numbering machinery
instead. Going with the alias oracle patch would still be possible
if we decide on caching the fn spec information in a place that is
O(1) accessible from relevant memory references (thus either on the
SSA default def or the PARM_DECL itself).
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
This improves a future important benchmark implementing a
Sudoku puzzle solver considerably (~10% on x86_64 IIRC).
Richard.
2015-09-29 Richard Biener <rguent...@suse.de>
PR tree-optimization/67170
* tree-ssa-alias.h (get_continuation_for_phi): Adjust
the translate function pointer parameter to get the
bool whether to disambiguate only by reference.
(walk_non_aliased_vuses): Likewise.
* tree-ssa-alias.c (maybe_skip_until): Adjust.
(get_continuation_for_phi_1): Likewise.
(get_continuation_for_phi): Likewise.
(walk_non_aliased_vuses): Likewise.
* tree-ssa-sccvn.c (const_parms): New bitmap.
(vn_reference_lookup_3): Adjust for interface change.
Disambiguate parameters pointing to readonly memory.
(free_scc_vn): Free const_parms.
(run_scc_vn): Initialize const_parms from a fn spec attribute.
* gfortran.dg/pr67170.f90: New testcase.
Index: gcc/tree-ssa-alias.c
===================================================================
*** gcc/tree-ssa-alias.c (revision 228230)
--- gcc/tree-ssa-alias.c (working copy)
*************** static bool
*** 2442,2448 ****
maybe_skip_until (gimple *phi, tree target, ao_ref *ref,
tree vuse, unsigned int *cnt, bitmap *visited,
bool abort_on_visited,
! void *(*translate)(ao_ref *, tree, void *, bool),
void *data)
{
basic_block bb = gimple_bb (phi);
--- 2442,2448 ----
maybe_skip_until (gimple *phi, tree target, ao_ref *ref,
tree vuse, unsigned int *cnt, bitmap *visited,
bool abort_on_visited,
! void *(*translate)(ao_ref *, tree, void *, bool *),
void *data)
{
basic_block bb = gimple_bb (phi);
*************** maybe_skip_until (gimple *phi, tree targ
*** 2477,2484 ****
++*cnt;
if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
{
if (translate
! && (*translate) (ref, vuse, data, true) == NULL)
;
else
return false;
--- 2477,2485 ----
++*cnt;
if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
{
+ bool disambiguate_only = true;
if (translate
! && (*translate) (ref, vuse, data, &disambiguate_only) == NULL)
;
else
return false;
*************** static tree
*** 2505,2511 ****
get_continuation_for_phi_1 (gimple *phi, tree arg0, tree arg1,
ao_ref *ref, unsigned int *cnt,
bitmap *visited, bool abort_on_visited,
! void *(*translate)(ao_ref *, tree, void *, bool),
void *data)
{
gimple *def0 = SSA_NAME_DEF_STMT (arg0);
--- 2506,2512 ----
get_continuation_for_phi_1 (gimple *phi, tree arg0, tree arg1,
ao_ref *ref, unsigned int *cnt,
bitmap *visited, bool abort_on_visited,
! void *(*translate)(ao_ref *, tree, void *, bool *),
void *data)
{
gimple *def0 = SSA_NAME_DEF_STMT (arg0);
*************** get_continuation_for_phi_1 (gimple *phi,
*** 2547,2559 ****
else if ((common_vuse = gimple_vuse (def0))
&& common_vuse == gimple_vuse (def1))
{
*cnt += 2;
if ((!stmt_may_clobber_ref_p_1 (def0, ref)
|| (translate
! && (*translate) (ref, arg0, data, true) == NULL))
&& (!stmt_may_clobber_ref_p_1 (def1, ref)
|| (translate
! && (*translate) (ref, arg1, data, true) == NULL)))
return common_vuse;
}
--- 2548,2561 ----
else if ((common_vuse = gimple_vuse (def0))
&& common_vuse == gimple_vuse (def1))
{
+ bool disambiguate_only = true;
*cnt += 2;
if ((!stmt_may_clobber_ref_p_1 (def0, ref)
|| (translate
! && (*translate) (ref, arg0, data, &disambiguate_only) == NULL))
&& (!stmt_may_clobber_ref_p_1 (def1, ref)
|| (translate
! && (*translate) (ref, arg1, data, &disambiguate_only) ==
NULL)))
return common_vuse;
}
*************** tree
*** 2571,2577 ****
get_continuation_for_phi (gimple *phi, ao_ref *ref,
unsigned int *cnt, bitmap *visited,
bool abort_on_visited,
! void *(*translate)(ao_ref *, tree, void *, bool),
void *data)
{
unsigned nargs = gimple_phi_num_args (phi);
--- 2573,2579 ----
get_continuation_for_phi (gimple *phi, ao_ref *ref,
unsigned int *cnt, bitmap *visited,
bool abort_on_visited,
! void *(*translate)(ao_ref *, tree, void *, bool *),
void *data)
{
unsigned nargs = gimple_phi_num_args (phi);
*************** get_continuation_for_phi (gimple *phi, a
*** 2648,2654 ****
void *
walk_non_aliased_vuses (ao_ref *ref, tree vuse,
void *(*walker)(ao_ref *, tree, unsigned int, void *),
! void *(*translate)(ao_ref *, tree, void *, bool),
tree (*valueize)(tree),
void *data)
{
--- 2650,2656 ----
void *
walk_non_aliased_vuses (ao_ref *ref, tree vuse,
void *(*walker)(ao_ref *, tree, unsigned int, void *),
! void *(*translate)(ao_ref *, tree, void *, bool *),
tree (*valueize)(tree),
void *data)
{
*************** walk_non_aliased_vuses (ao_ref *ref, tre
*** 2690,2696 ****
{
if (!translate)
break;
! res = (*translate) (ref, vuse, data, false);
/* Failed lookup and translation. */
if (res == (void *)-1)
{
--- 2692,2699 ----
{
if (!translate)
break;
! bool disambiguate_only = false;
! res = (*translate) (ref, vuse, data, &disambiguate_only);
/* Failed lookup and translation. */
if (res == (void *)-1)
{
*************** walk_non_aliased_vuses (ao_ref *ref, tre
*** 2701,2707 ****
else if (res != NULL)
break;
/* Translation succeeded, continue walking. */
! translated = true;
}
vuse = gimple_vuse (def_stmt);
}
--- 2704,2710 ----
else if (res != NULL)
break;
/* Translation succeeded, continue walking. */
! translated = translated || !disambiguate_only;
}
vuse = gimple_vuse (def_stmt);
}
Index: gcc/tree-ssa-alias.h
===================================================================
*** gcc/tree-ssa-alias.h (revision 228230)
--- gcc/tree-ssa-alias.h (working copy)
*************** extern bool stmt_kills_ref_p (gimple *,
*** 118,129 ****
extern bool stmt_kills_ref_p (gimple *, ao_ref *);
extern tree get_continuation_for_phi (gimple *, ao_ref *,
unsigned int *, bitmap *, bool,
! void *(*)(ao_ref *, tree, void *, bool),
void *);
extern void *walk_non_aliased_vuses (ao_ref *, tree,
void *(*)(ao_ref *, tree,
unsigned int, void *),
! void *(*)(ao_ref *, tree, void *, bool),
tree (*)(tree),
void *);
extern unsigned int walk_aliased_vdefs (ao_ref *, tree,
--- 118,129 ----
extern bool stmt_kills_ref_p (gimple *, ao_ref *);
extern tree get_continuation_for_phi (gimple *, ao_ref *,
unsigned int *, bitmap *, bool,
! void *(*)(ao_ref *, tree, void *, bool *),
void *);
extern void *walk_non_aliased_vuses (ao_ref *, tree,
void *(*)(ao_ref *, tree,
unsigned int, void *),
! void *(*)(ao_ref *, tree, void *, bool *),
tree (*)(tree),
void *);
extern unsigned int walk_aliased_vdefs (ao_ref *, tree,
Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c (revision 228230)
--- gcc/tree-ssa-sccvn.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 120,125 ****
--- 120,126 ----
static tree *last_vuse_ptr;
static vn_lookup_kind vn_walk_kind;
static vn_lookup_kind default_vn_walk_kind;
+ bitmap const_parms;
/* vn_nary_op hashtable helpers. */
*************** vn_reference_lookup_or_insert_for_pieces
*** 1656,1676 ****
/* Callback for walk_non_aliased_vuses. Tries to perform a lookup
from the statement defining VUSE and if not successful tries to
translate *REFP and VR_ through an aggregate copy at the definition
! of VUSE. */
static void *
vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_,
! bool disambiguate_only)
{
vn_reference_t vr = (vn_reference_t)vr_;
gimple *def_stmt = SSA_NAME_DEF_STMT (vuse);
! tree base;
HOST_WIDE_INT offset, maxsize;
static vec<vn_reference_op_s>
lhs_ops = vNULL;
ao_ref lhs_ref;
bool lhs_ref_ok = false;
/* First try to disambiguate after value-replacing in the definitions LHS.
*/
if (is_gimple_assign (def_stmt))
{
--- 1657,1691 ----
/* Callback for walk_non_aliased_vuses. Tries to perform a lookup
from the statement defining VUSE and if not successful tries to
translate *REFP and VR_ through an aggregate copy at the definition
! of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation
! of *REF and *VR. If only disambiguation was performed then
! *DISAMBIGUATE_ONLY is set to true. */
static void *
vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_,
! bool *disambiguate_only)
{
vn_reference_t vr = (vn_reference_t)vr_;
gimple *def_stmt = SSA_NAME_DEF_STMT (vuse);
! tree base = ao_ref_base (ref);
HOST_WIDE_INT offset, maxsize;
static vec<vn_reference_op_s>
lhs_ops = vNULL;
ao_ref lhs_ref;
bool lhs_ref_ok = false;
+ /* If the reference is based on a parameter that was determined as
+ pointing to readonly memory it doesn't change. */
+ if (TREE_CODE (base) == MEM_REF
+ && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
+ && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (base, 0))
+ && bitmap_bit_p (const_parms,
+ SSA_NAME_VERSION (TREE_OPERAND (base, 0))))
+ {
+ *disambiguate_only = true;
+ return NULL;
+ }
+
/* First try to disambiguate after value-replacing in the definitions LHS.
*/
if (is_gimple_assign (def_stmt))
{
*************** vn_reference_lookup_3 (ao_ref *ref, tree
*** 1687,1693 ****
TREE_TYPE (lhs), lhs_ops);
if (lhs_ref_ok
&& !refs_may_alias_p_1 (ref, &lhs_ref, true))
! return NULL;
}
else
{
--- 1702,1711 ----
TREE_TYPE (lhs), lhs_ops);
if (lhs_ref_ok
&& !refs_may_alias_p_1 (ref, &lhs_ref, true))
! {
! *disambiguate_only = true;
! return NULL;
! }
}
else
{
*************** vn_reference_lookup_3 (ao_ref *ref, tree
*** 1723,1736 ****
for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i)
gimple_call_set_arg (def_stmt, i, oldargs[i]);
if (!res)
! return NULL;
}
}
! if (disambiguate_only)
return (void *)-1;
- base = ao_ref_base (ref);
offset = ref->offset;
maxsize = ref->max_size;
--- 1741,1756 ----
for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i)
gimple_call_set_arg (def_stmt, i, oldargs[i]);
if (!res)
! {
! *disambiguate_only = true;
! return NULL;
! }
}
}
! if (*disambiguate_only)
return (void *)-1;
offset = ref->offset;
maxsize = ref->max_size;
*************** free_scc_vn (void)
*** 4342,4347 ****
--- 4362,4369 ----
XDELETE (valid_info);
free_vn_table (optimistic_info);
XDELETE (optimistic_info);
+
+ BITMAP_FREE (const_parms);
}
/* Set *ID according to RESULT. */
*************** run_scc_vn (vn_lookup_kind default_vn_wa
*** 4677,4682 ****
--- 4699,4727 ----
init_scc_vn ();
+ /* Collect pointers we know point to readonly memory. */
+ const_parms = BITMAP_ALLOC (NULL);
+ tree fnspec = lookup_attribute ("fn spec",
+ TYPE_ATTRIBUTES (TREE_TYPE (cfun->decl)));
+ if (fnspec)
+ {
+ fnspec = TREE_VALUE (TREE_VALUE (fnspec));
+ i = 1;
+ for (tree arg = DECL_ARGUMENTS (cfun->decl);
+ arg; arg = DECL_CHAIN (arg), ++i)
+ {
+ if (i >= (unsigned) TREE_STRING_LENGTH (fnspec))
+ break;
+ if (TREE_STRING_POINTER (fnspec)[i] == 'R'
+ || TREE_STRING_POINTER (fnspec)[i] == 'r')
+ {
+ tree name = ssa_default_def (cfun, arg);
+ if (name)
+ bitmap_set_bit (const_parms, SSA_NAME_VERSION (name));
+ }
+ }
+ }
+
/* Mark all edges as possibly executable. */
FOR_ALL_BB_FN (bb, cfun)
{
Index: gcc/testsuite/gfortran.dg/pr67170.f90
===================================================================
*** gcc/testsuite/gfortran.dg/pr67170.f90 (revision 0)
--- gcc/testsuite/gfortran.dg/pr67170.f90 (revision 0)
***************
*** 0 ****
--- 1,31 ----
+ ! { dg-do compile }
+ ! { dg-options "-O -fdump-tree-fre1" }
+
+ module test_module
+ integer, parameter :: r=10
+ integer :: data(r, r), block(r, r, r)
+ contains
+ recursive subroutine foo(arg)
+ integer, intent(in) :: arg
+ integer :: loop, x(r), y(r)
+
+ where(data(arg, :) /= 0)
+ x = data(arg, :)
+ y = l
+ elsewhere
+ x = 1
+ y = r
+ end where
+
+ do loop = x(1), y(1)
+ if(block(arg, 1, loop) <= 0) cycle
+ block(arg, 1:4, loop) = block(arg, 1:4, i1) + 1
+ call foo(arg + 2)
+ block(arg, 1:4, loop) = block(arg, 1:4, i1) + 10
+ end do
+ end subroutine foo
+
+ end module test_module
+ end program
+
+ ! { dg-final { scan-tree-dump-times "= \\*arg_\[0-9\]+\\(D\\);" 1 "fre1" } }
