> > This patch implements a new OEP flag called OEP_STRUCTURAL_EQ. This flag > > will > > check if the operands would produce the same bit values after the > > computations > > even if the final sign is different. > > I think the name is badly chosen - we already have OEP_LEXICOGRAPHIC and > OEP_BITWISE. I would suggest to use OEP_ASSUME_TWOS_COMPLEMENT > or OEP_ASSUME_WRAPV. >
I went with OEP_ASSUME_WRAPV.. saves chars on the 80 char line limit :)
> > - if (!(flags & OEP_ADDRESS_OF))
> > + if ((flags & OEP_STRUCTURAL_EQ)
> > + && (CONVERT_EXPR_P (arg0) || CONVERT_EXPR_P (arg1)))
> > + {
> > + const_tree t_arg0 = arg0;
> > + const_tree t_arg1 = arg1;
> > + STRIP_NOPS (arg0);
> > + STRIP_NOPS (arg1);
> > + /* Only recurse if the conversion was one that was valid to strip.
> > */
> > + if (t_arg0 != arg0 || t_arg1 != arg1)
> > + return operand_equal_p (type0, arg0, type1, arg1, flags);
>
> (*)
>
> > + }
> > +
> > + if (!(flags & (OEP_ADDRESS_OF | OEP_STRUCTURAL_EQ)))
> > {
> > /* If both types don't have the same signedness, then we can't
> > consider
> > them equal. We must check this before the STRIP_NOPS calls
> > @@ -3439,6 +3451,22 @@ operand_compare::operand_equal_p (tree type0,
> const_tree arg0,
> > if (flags & (OEP_ONLY_CONST | OEP_BITWISE))
> > return false;
> >
> > + /* Check if we are checking an operation where the two's compliment
> > bitwise
> > + representation of the result is not the same between signed and
> > + unsigned arithmetic. */
> > + switch (TREE_CODE (arg0))
> > + {
> > + case PLUS_EXPR:
> > + case MINUS_EXPR:
> > + case MULT_EXPR:
> > + break;
> > +
> > + default:
> > + /* Clear the structural comparison bit. */
> > + flags &= ~OEP_STRUCTURAL_EQ;
>
> So this handling means that a / (int)((unsigned)b - (unsigned)c)) and
> a / (b - c) are not equal with respect to OEP_STRUCTURAL_EQ because
> we drop that flag when processing the division and thus the recursion on
> the minus operands doesn't have it any more.
Yeah I did do this intentionally, since I don’t expect division in IV
computations
anyway. But given that this is supposed to be a more generic helper I've
extended
it properly now.
>
> So shouldn't this and (*) be integrated with the TYPE_UNSIGNED compare in
> the !OEP_ADDRESS_OF case? Aka not require same signedness for
> PLUS/MINUS/MULT/CONVERT?
>
Yup, fair enough, I had a similar thought after I sent out the patch, in that
the precision
check is still good to have. I've done this in the patch, it turns the
conditions for ignoring
the signs into an opt-in check rather than an opt-out check. Hopefully I kept
the logic simple
to follow.
> I think we have to document what the TYPE, ARG combination means
> semantically. As far as I understand TYPE doesn't specify the signedness
> of the operation ARG but instead represents a possibly stripped conversion
> of the result?
>
I added some more documentation to the function arguments and the enum
definition.
> > + /* (int)((unsigned x) + (unsigned y)) == x + y. */
> > + ASSERT_TRUE (operand_equal_p (lhs1, rhs1, OEP_STRUCTURAL_EQ));
> > + ASSERT_FALSE (operand_equal_p (lhs1, rhs1, 0));
> > +
> > + /* (int)(unsigned) x == x. */
> > + tree lhs2 = build1 (NOP_EXPR, stype,
> > + build1 (NOP_EXPR, utype, x));
> > + tree rhs2 = x;
> > + ASSERT_TRUE (operand_equal_p (lhs2, rhs2, OEP_STRUCTURAL_EQ));
> > + ASSERT_TRUE (operand_equal_p (lhs2, rhs2, 0));
>
> That's not too useful - we'd never see this due to folding.
>
Yeah, it's why I avoided fold here explicitly. I added this as when I had
messed up
something it was a cheap and early test that failed. So in that sense it's
usefulness
is purely for debugging.
--
Bootstrapped Regtested on aarch64-none-linux-gnu,
arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
-m32, -m64 and no issues.
Ok for master?
Thanks,
Tamar
gcc/ChangeLog:
PR tree-optimization/114932
* fold-const.cc (operand_compare::operand_equal_p): Use it.
(operand_compare::verify_hash_value): Likewise.
(test_operand_equality::test): New.
(fold_const_cc_tests): Use it.
* tree-core.h (enum operand_equal_flag): Add OEP_ASSUME_WRAPV.
* tree-ssa-loop-ivopts.cc (record_group_use): Check for structural eq.
gcc/testsuite/ChangeLog:
PR tree-optimization/114932
* gfortran.dg/addressing-modes_2.f90: New test.
-- inline copy of patch --
diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc
index
158591165ccdea3c7a7c47fb575d59484368e147..cfbd367c708475ba7fefb3433d0c3ca9f98f949d
100644
--- a/gcc/fold-const.cc
+++ b/gcc/fold-const.cc
@@ -3172,8 +3172,10 @@ operand_compare::operand_equal_p (const_tree arg0,
const_tree arg1,
return operand_equal_p (TREE_TYPE (arg0), arg0, TREE_TYPE (arg1), arg1,
flags);
}
-/* The same as operand_equal_p however the type of ARG0 and ARG1 are assumed
to be
- the TYPE0 and TYPE1 respectively. */
+/* The same as operand_equal_p however the type of ARG0 and ARG1 are assumed to
+ be the TYPE0 and TYPE1 respectively. TYPE0 and TYPE1 represent the type the
+ expression is being compared under for equality. This means that they can
+ differ from the actual TREE_TYPE (..) value of ARG0 and ARG1. */
bool
operand_compare::operand_equal_p (tree type0, const_tree arg0,
@@ -3220,15 +3222,52 @@ operand_compare::operand_equal_p (tree type0,
const_tree arg0,
return tree_int_cst_equal (arg0, arg1);
}
+ if ((flags & OEP_ASSUME_WRAPV)
+ && (CONVERT_EXPR_P (arg0) || CONVERT_EXPR_P (arg1)))
+ {
+ const_tree t_arg0 = arg0;
+ const_tree t_arg1 = arg1;
+ STRIP_NOPS (arg0);
+ STRIP_NOPS (arg1);
+ /* Only recurse if the conversion was one that was valid to strip. */
+ if (t_arg0 != arg0 || t_arg1 != arg1)
+ return operand_equal_p (type0, arg0, type1, arg1, flags);
+ }
+
if (!(flags & OEP_ADDRESS_OF))
{
+ /* Check if we are checking an operation where the two's compliment
+ bitwise representation of the result is not the same between signed and
+ unsigned arithmetic. */
+ bool enforce_signedness = true;
+ if (flags & OEP_ASSUME_WRAPV)
+ {
+ switch (TREE_CODE (arg0))
+ {
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ case MULT_EXPR:
+ case SSA_NAME:
+ case INTEGER_CST:
+ case VAR_DECL:
+ case PARM_DECL:
+ CASE_CONVERT:
+ enforce_signedness = false;
+ break;
+
+ default:
+ break;
+ }
+ }
+
/* If both types don't have the same signedness, then we can't consider
them equal. We must check this before the STRIP_NOPS calls
because they may change the signedness of the arguments. As pointers
strictly don't have a signedness, require either two pointers or
two non-pointers as well. */
- if (TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
- || POINTER_TYPE_P (type0) != POINTER_TYPE_P (type1))
+ if (POINTER_TYPE_P (type0) != POINTER_TYPE_P (type1)
+ || (TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
+ && enforce_signedness))
return false;
/* If both types don't have the same precision, then it is not safe
@@ -4236,7 +4275,7 @@ operand_compare::verify_hash_value (const_tree arg0,
const_tree arg1,
{
if (operand_equal_p (arg0, arg1, flags | OEP_NO_HASH_CHECK))
{
- if (arg0 != arg1 && !(flags & OEP_DECL_NAME))
+ if (arg0 != arg1 && !(flags & (OEP_DECL_NAME | OEP_ASSUME_WRAPV)))
{
inchash::hash hstate0 (0), hstate1 (0);
hash_operand (arg0, hstate0, flags | OEP_HASH_CHECK);
@@ -17476,6 +17515,111 @@ test_arithmetic_folding ()
x);
}
+namespace test_operand_equality {
+
+/* Verify structural equality. */
+
+/* Execute fold_vec_perm_cst unit tests. */
+
+static void
+test ()
+{
+ tree stype = integer_type_node;
+ tree utype = unsigned_type_node;
+ tree x = create_tmp_var_raw (stype, "x");
+ tree y = create_tmp_var_raw (stype, "y");
+ tree z = create_tmp_var_raw (stype, "z");
+ tree four = build_int_cst (stype, 4);
+ tree lhs1 = fold_build2 (PLUS_EXPR, stype, x, y);
+ tree rhs1 = fold_convert (stype,
+ fold_build2 (PLUS_EXPR, utype,
+ fold_convert (utype, x),
+ fold_convert (utype, y)));
+
+ /* (int)((unsigned x) + (unsigned y)) == x + y. */
+ ASSERT_TRUE (operand_equal_p (lhs1, rhs1, OEP_ASSUME_WRAPV));
+ ASSERT_FALSE (operand_equal_p (lhs1, rhs1, 0));
+
+ /* (int)(unsigned) x == x. */
+ tree lhs2 = build1 (NOP_EXPR, stype,
+ build1 (NOP_EXPR, utype, x));
+ tree rhs2 = x;
+ ASSERT_TRUE (operand_equal_p (lhs2, rhs2, OEP_ASSUME_WRAPV));
+ ASSERT_TRUE (operand_equal_p (lhs2, rhs2, 0));
+
+ /* (unsigned x) + (unsigned y) == x + y. */
+ tree lhs3 = lhs1;
+ tree rhs3 = fold_build2 (PLUS_EXPR, utype,
+ fold_convert (utype, x),
+ fold_convert (utype, y));
+ ASSERT_TRUE (operand_equal_p (lhs3, rhs3, OEP_ASSUME_WRAPV));
+ ASSERT_FALSE (operand_equal_p (lhs3, rhs3, 0));
+
+ /* (unsigned x) / (unsigned y) == x / y. */
+ tree lhs4 = fold_build2 (TRUNC_DIV_EXPR, stype, x, y);;
+ tree rhs4 = fold_build2 (TRUNC_DIV_EXPR, utype,
+ fold_convert (utype, x),
+ fold_convert (utype, y));
+ ASSERT_FALSE (operand_equal_p (lhs4, rhs4, OEP_ASSUME_WRAPV));
+ ASSERT_FALSE (operand_equal_p (lhs4, rhs4, 0));
+
+ /* (long x) / 4 == (long)(x / 4). */
+ tree lstype = long_long_integer_type_node;
+ tree lfour = build_int_cst (lstype, 4);
+ tree lhs5 = fold_build2 (TRUNC_DIV_EXPR, lstype,
+ fold_build1 (VIEW_CONVERT_EXPR, lstype, x), lfour);
+ tree rhs5 = fold_build1 (VIEW_CONVERT_EXPR, lstype,
+ fold_build2 (TRUNC_DIV_EXPR, stype, x, four));
+ ASSERT_FALSE (operand_equal_p (lhs5, rhs5, OEP_ASSUME_WRAPV));
+ ASSERT_FALSE (operand_equal_p (lhs5, rhs5, 0));
+
+ /* (unsigned x) / 4 == x / 4. */
+ tree lhs6 = fold_build2 (TRUNC_DIV_EXPR, stype, x, four);;
+ tree rhs6 = fold_build2 (TRUNC_DIV_EXPR, utype,
+ fold_convert (utype, x),
+ fold_convert (utype, four));
+ ASSERT_FALSE (operand_equal_p (lhs6, rhs6, OEP_ASSUME_WRAPV));
+ ASSERT_FALSE (operand_equal_p (lhs6, rhs6, 0));
+
+ /* a / (int)((unsigned)b - (unsigned)c)) == a / (b - c). */
+ tree lhs7 = fold_build2 (TRUNC_DIV_EXPR, stype, x, lhs1);
+ tree rhs7 = fold_build2 (TRUNC_DIV_EXPR, stype, x, rhs1);
+ ASSERT_TRUE (operand_equal_p (lhs7, rhs7, OEP_ASSUME_WRAPV));
+ ASSERT_FALSE (operand_equal_p (lhs7, rhs7, 0));
+
+ /* (unsigned x) + 4 == x + 4. */
+ tree lhs8 = fold_build2 (PLUS_EXPR, stype, x, four);
+ tree rhs8 = fold_build2 (PLUS_EXPR, utype,
+ fold_convert (utype, x),
+ fold_convert (utype, four));
+ ASSERT_TRUE (operand_equal_p (lhs8, rhs8, OEP_ASSUME_WRAPV));
+ ASSERT_FALSE (operand_equal_p (lhs8, rhs8, 0));
+
+ /* (unsigned x) + 4 == 4 + x. */
+ tree lhs9 = fold_build2 (PLUS_EXPR, stype, four, x);
+ tree rhs9 = fold_build2 (PLUS_EXPR, utype,
+ fold_convert (utype, x),
+ fold_convert (utype, four));
+ ASSERT_TRUE (operand_equal_p (lhs9, rhs9, OEP_ASSUME_WRAPV));
+ ASSERT_FALSE (operand_equal_p (lhs9, rhs9, 0));
+
+ /* ((unsigned x) + 4) * (unsigned y)) + z == ((4 + x) * y) + z. */
+ tree lhs10 = fold_build2 (PLUS_EXPR, stype,
+ fold_build2 (MULT_EXPR, stype,
+ fold_build2 (PLUS_EXPR, stype, four, x),
+ y),
+ z);
+ tree rhs10 = fold_build2 (MULT_EXPR, utype,
+ fold_build2 (PLUS_EXPR, utype,
+ fold_convert (utype, x),
+ fold_convert (utype, four)),
+ fold_convert (utype, y));
+ rhs10 = fold_build2 (PLUS_EXPR, stype, fold_convert (stype, rhs10), z);
+ ASSERT_TRUE (operand_equal_p (lhs10, rhs10, OEP_ASSUME_WRAPV));
+ ASSERT_FALSE (operand_equal_p (lhs10, rhs10, 0));
+}
+}
+
namespace test_fold_vec_perm_cst {
/* Build a VECTOR_CST corresponding to VMODE, and has
@@ -18269,6 +18413,7 @@ fold_const_cc_tests ()
test_vector_folding ();
test_vec_duplicate_folding ();
test_fold_vec_perm_cst::test ();
+ test_operand_equality::test ();
}
} // namespace selftest
diff --git a/gcc/testsuite/gfortran.dg/addressing-modes_2.f90
b/gcc/testsuite/gfortran.dg/addressing-modes_2.f90
new file mode 100644
index
0000000000000000000000000000000000000000..8eee4be3dc4d69fecfacd4c2e24a4973c8539fae
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/addressing-modes_2.f90
@@ -0,0 +1,20 @@
+! { dg-do compile { target aarch64-*-* } }
+! { dg-additional-options "-w -Ofast -fdump-tree-ivopts-all" }
+
+module a
+integer, parameter :: b=3, c=b
+contains
+subroutine d(block)
+integer f, col , block(:, :, :), e
+do f = 1, c
+ do col = 1, c
+ block(:f, :, e()) = do
+ end do
+ end do
+ end
+ end
+
+! { dg-final { scan-tree-dump-not {Selected IV set for loop .+ niters, 3 IVs:}
ivopts } }
+! { dg-final { scan-tree-dump-times {Selected IV set for loop .+ niters, 2
IVs:} 1 ivopts } }
+! { dg-final { scan-tree-dump-times {Selected IV set for loop .+ niters, 1
IVs:} 1 ivopts } }
+
diff --git a/gcc/tree-core.h b/gcc/tree-core.h
index
1776c154d94e12e6efaf846d1b60c3170d469605..30bada4776d8363f7fa355caa9bd6c2608d3074a
100644
--- a/gcc/tree-core.h
+++ b/gcc/tree-core.h
@@ -1007,7 +1007,14 @@ enum operand_equal_flag {
/* In conjunction with OEP_LEXICOGRAPHIC considers names of declarations
of the same kind. Used to compare VLA bounds involving parameters
across redeclarations of the same function. */
- OEP_DECL_NAME = 512
+ OEP_DECL_NAME = 512,
+ /* Check if two expressions result in the same bit values while possibly
+ ignoring the sign of the expressions and any differences in undefined
+ behaviour. The compared expressions must however perform the same
+ operations. Because this comparison ignores any possible UB it cannot
+ be used blindly without ensuring that the context you are using it in
+ itself doesn't guarantee that there will be no UB. */
+ OEP_ASSUME_WRAPV = 1024
};
/* Enum and arrays used for tree allocation stats.
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index
b38bc6971a8ebfa16c30329bc69d8e3add77f8d0..0f5dd089a0e6335410acc8bd0a466b9c525551c6
100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -1624,8 +1624,8 @@ record_group_use (struct ivopts_data *data, tree *use_p,
/* Check if it has the same stripped base and step. */
if (operand_equal_p (iv->base_object, use->iv->base_object, 0)
- && operand_equal_p (iv->step, use->iv->step, 0)
- && operand_equal_p (addr_base, use->addr_base, 0))
+ && operand_equal_p (iv->step, use->iv->step, OEP_ASSUME_WRAPV)
+ && operand_equal_p (addr_base, use->addr_base, OEP_ASSUME_WRAPV))
break;
}
if (i == data->vgroups.length ())
rb18723.patch
Description: rb18723.patch
