ping
> -----Original Message-----
> From: Tamar Christina
> Sent: Tuesday, September 10, 2024 8:57 PM
> To: Tamar Christina <tamar.christ...@arm.com>; gcc-patches@gcc.gnu.org
> Cc: nd <n...@arm.com>; rguent...@suse.de; j...@ventanamicro.com
> Subject: RE: [PATCH 2/2]middle-end: use two's complement equality when
> comparing IVs during candidate selection [PR114932]
>
> ping
>
> > -----Original Message-----
> > From: Tamar Christina <tamar.christ...@arm.com>
> > Sent: Tuesday, August 20, 2024 2:06 PM
> > To: gcc-patches@gcc.gnu.org
> > Cc: nd <n...@arm.com>; rguent...@suse.de; j...@ventanamicro.com
> > Subject: [PATCH 2/2]middle-end: use two's complement equality when
> comparing
> > IVs during candidate selection [PR114932]
> >
> > Hi All,
> >
> > IVOPTS normally uses affine trees to perform comparisons between different
> > IVs,
> > but these seem to have been missing in two key spots and instead normal tree
> > equivalencies used.
> >
> > In some cases where we have a two-complements equivalence but not a strict
> > signedness equivalencies we end up generating both a signed and unsigned IV
> > for
> > the same candidate.
> >
> > 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.
> >
> > This happens quite a lot with fortran but can also happen in C because this
> > came
> > code is unable to figure out when one expression is a multiple of another.
> >
> > As an example in the attached testcase we get:
> >
> > Initial set of candidates:
> > cost: 24 (complexity 3)
> > reg_cost: 9
> > cand_cost: 15
> > cand_group_cost: 0 (complexity 3)
> > candidates: 1, 6, 8
> > group:0 --> iv_cand:6, cost=(0,1)
> > group:1 --> iv_cand:1, cost=(0,0)
> > group:2 --> iv_cand:8, cost=(0,1)
> > group:3 --> iv_cand:8, cost=(0,1)
> > invariant variables: 6
> > invariant expressions: 1, 2
> >
> > <Invariant Expressions>:
> > inv_expr 1: stride.3_27 * 4
> > inv_expr 2: (unsigned long) stride.3_27 * 4
> >
> > These end up being used in the same group:
> >
> > Group 1:
> > cand cost compl. inv.expr. inv.vars
> > 1 0 0 NIL; 6
> > 2 0 0 NIL; 6
> > 3 0 0 NIL; 6
> >
> > which ends up with IV opts picking the signed and unsigned IVs:
> >
> > Improved to:
> > cost: 24 (complexity 3)
> > reg_cost: 9
> > cand_cost: 15
> > cand_group_cost: 0 (complexity 3)
> > candidates: 1, 6, 8
> > group:0 --> iv_cand:6, cost=(0,1)
> > group:1 --> iv_cand:1, cost=(0,0)
> > group:2 --> iv_cand:8, cost=(0,1)
> > group:3 --> iv_cand:8, cost=(0,1)
> > invariant variables: 6
> > invariant expressions: 1, 2
> >
> > and so generates the same IV as both signed and unsigned:
> >
> > ;; basic block 21, loop depth 3, count 214748368 (estimated locally, freq
> > 58.2545), maybe hot
> > ;; prev block 28, next block 31, flags: (NEW, REACHABLE, VISITED)
> > ;; pred: 28 [always] count:23622320 (estimated locally, freq
> > 6.4080)
> > (FALLTHRU,EXECUTABLE)
> > ;; 25 [always] count:191126046 (estimated locally, freq
> > 51.8465)
> > (FALLTHRU,DFS_BACK,EXECUTABLE)
> > # .MEM_66 = PHI <.MEM_34(28), .MEM_22(25)>
> > # ivtmp.22_41 = PHI <0(28), ivtmp.22_82(25)>
> > # ivtmp.26_51 = PHI <ivtmp.26_55(28), ivtmp.26_72(25)>
> > # ivtmp.28_90 = PHI <ivtmp.28_99(28), ivtmp.28_98(25)>
> >
> > ...
> >
> > ;; basic block 24, loop depth 3, count 214748366 (estimated locally, freq
> > 58.2545), maybe hot
> > ;; prev block 22, next block 25, flags: (NEW, REACHABLE, VISITED)'
> > ;; pred: 22 [always] count:95443719 (estimated locally, freq
> > 25.8909)
> > (FALLTHRU)
> > ;; 21 [33.3% (guessed)] count:71582790 (estimated locally,
> > freq
> 19.4182)
> > (TRUE_VALUE,EXECUTABLE)
> > ;; 31 [33.3% (guessed)] count:47721860 (estimated locally,
> > freq
> 12.9455)
> > (TRUE_VALUE,EXECUTABLE)
> > # .MEM_22 = PHI <.MEM_44(22), .MEM_31(21), .MEM_79(31)>
> > ivtmp.22_82 = ivtmp.22_41 + 1;
> > ivtmp.26_72 = ivtmp.26_51 + _80;
> > ivtmp.28_98 = ivtmp.28_90 + _39;
> >
> > These two IVs are always used as unsigned, so IV ops generates:
> >
> > _73 = stride.3_27 * 4;
> > _80 = (unsigned long) _73;
> > _54 = (unsigned long) stride.3_27;
> > _39 = _54 * 4;
> >
> > Which means that in e.g. exchange2 we generate a lot of duplicate code.
> >
> > This is because candidate 6 and 8 are equivalent under two's complement but
> have
> > different signs.
> >
> > This patch changes it so that if you have two IVs that are affine
> > equivalent to
> > just pick one over the other. IV already has code for this, so the patch
> > just
> > uses affine trees instead of tree for the check.
> >
> > With it we get:
> >
> > <Invariant Expressions>:
> > inv_expr 1: stride.3_27 * 4
> >
> > <Group-candidate Costs>:
> > Group 0:
> > cand cost compl. inv.expr. inv.vars
> > 5 0 2 NIL; NIL;
> > 6 0 3 NIL; NIL;
> >
> > Group 1:
> > cand cost compl. inv.expr. inv.vars
> > 1 0 0 NIL; 6
> > 2 0 0 NIL; 6
> > 3 0 0 NIL; 6
> > 4 0 0 NIL; 6
> >
> > Initial set of candidates:
> > cost: 16 (complexity 3)
> > reg_cost: 6
> > cand_cost: 10
> > cand_group_cost: 0 (complexity 3)
> > candidates: 1, 6
> > group:0 --> iv_cand:6, cost=(0,3)
> > group:1 --> iv_cand:1, cost=(0,0)
> > invariant variables: 6
> > invariant expressions: 1
> >
> > The two patches together results in a 10% performance increase in exchange2
> > in
> > SPECCPU 2017 and a 4% reduction in binary size and a 5% improvement in
> > compile
> > time. There's also a 5% performance improvement in fotonik3d and similar
> > reduction in binary size.
> >
> > 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_STRUCTURAL_EQ.
> > * 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.
> >
> > ---
> > diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc
> > index
> >
> 71e82b1d76d4106c7c23c54af8b35905a1af9f1c..52a4465de0355220befa6d6b
> > 3301e21e038e3e41 100644
> > --- a/gcc/fold-const.cc
> > +++ b/gcc/fold-const.cc
> > @@ -3208,7 +3208,19 @@ operand_compare::operand_equal_p (tree type0,
> > const_tree arg0,
> > return tree_int_cst_equal (arg0, arg1);
> > }
> >
> > - 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;
> > + break;
> > + }
> > +
> > /* Define macros to test an operand from arg0 and arg1 for equality and a
> > variant that allows null and views null as being different from any
> > non-null value. In the latter case, if either is null, the both
> > @@ -4218,7 +4246,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_STRUCTURAL_EQ)))
> > {
> > inchash::hash hstate0 (0), hstate1 (0);
> > hash_operand (arg0, hstate0, flags | OEP_HASH_CHECK);
> > @@ -17357,6 +17385,95 @@ 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_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));
> > +
> > + /* (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_STRUCTURAL_EQ));
> > + 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_STRUCTURAL_EQ));
> > + ASSERT_FALSE (operand_equal_p (lhs4, rhs4, 0));
> > +
> > + /* (unsigned x) / 4 == x / 4. */
> > + tree lhs5 = fold_build2 (TRUNC_DIV_EXPR, stype, x, four);;
> > + tree rhs5 = fold_build2 (TRUNC_DIV_EXPR, utype,
> > + fold_convert (utype, x),
> > + fold_convert (utype, four));
> > + ASSERT_FALSE (operand_equal_p (lhs5, rhs5, OEP_STRUCTURAL_EQ));
> > + ASSERT_FALSE (operand_equal_p (lhs5, rhs5, 0));
> > +
> > + /* (unsigned x) + 4 == x + 4. */
> > + tree lhs6 = fold_build2 (PLUS_EXPR, stype, x, four);
> > + tree rhs6 = fold_build2 (PLUS_EXPR, utype,
> > + fold_convert (utype, x),
> > + fold_convert (utype, four));
> > + ASSERT_TRUE (operand_equal_p (lhs6, rhs6, OEP_STRUCTURAL_EQ));
> > + ASSERT_FALSE (operand_equal_p (lhs6, rhs6, 0));
> > +
> > + /* (unsigned x) + 4 == 4 + x. */
> > + tree lhs7 = fold_build2 (PLUS_EXPR, stype, four, x);
> > + tree rhs7 = fold_build2 (PLUS_EXPR, utype,
> > + fold_convert (utype, x),
> > + fold_convert (utype, four));
> > + ASSERT_TRUE (operand_equal_p (lhs7, rhs7, OEP_STRUCTURAL_EQ));
> > + ASSERT_FALSE (operand_equal_p (lhs7, rhs7, 0));
> > +
> > + /* ((unsigned x) + 4) * (unsigned y)) + z == ((4 + x) * y) + z. */
> > + tree lhs8 = fold_build2 (PLUS_EXPR, stype,
> > + fold_build2 (MULT_EXPR, stype,
> > + fold_build2 (PLUS_EXPR, stype, four, x),
> > + y),
> > + z);
> > + tree rhs8 = fold_build2 (MULT_EXPR, utype,
> > + fold_build2 (PLUS_EXPR, utype,
> > + fold_convert (utype, x),
> > + fold_convert (utype, four)),
> > + fold_convert (utype, y));
> > + rhs8 = fold_build2 (PLUS_EXPR, stype, fold_convert (stype, rhs8), z);
> > + ASSERT_TRUE (operand_equal_p (lhs8, rhs8, OEP_STRUCTURAL_EQ));
> > + ASSERT_FALSE (operand_equal_p (lhs8, rhs8, 0));
> > +}
> > +}
> > +
> > namespace test_fold_vec_perm_cst {
> >
> > /* Build a VECTOR_CST corresponding to VMODE, and has
> > @@ -18150,6 +18267,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..8eee4be3dc4d69fecfacd4c
> > 2e24a4973c8539fae
> > --- /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
> >
> 27c569c77022227643151fa4a909a95f3d45bf55..fe398d99bcaa9e8fcec45e5e0
> > 7d133bc393aa4a7 100644
> > --- a/gcc/tree-core.h
> > +++ b/gcc/tree-core.h
> > @@ -962,7 +962,9 @@ 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 for structural equivalence and ignore NOP_CONVERT casts. */
> > + OEP_STRUCTURAL_EQ = 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
> >
> c3218a3e8eedbb8d0a7f14c01eeb069cb6024c29..b05e4ac1e63b5c110707a8a3
> > ed5e614b7ccc702f 100644
> > --- a/gcc/tree-ssa-loop-ivopts.cc
> > +++ b/gcc/tree-ssa-loop-ivopts.cc
> > @@ -1623,8 +1623,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_STRUCTURAL_EQ)
> > + && operand_equal_p (addr_base, use->addr_base,
> > OEP_STRUCTURAL_EQ))
> > break;
> > }
> > if (i == data->vgroups.length ())
> >
> >
> >
> >
> > --
