This is because operand_equal_p is "smarter" than data_ref_compare_tree. We have something like

A: (long)_1 + (_2 + _3)
B: (_2 + _4) + (long)_1
C: (_2 + _3) + (long)_1

with A == C != B according to operand_equal_p (and A < B < C according to data_ref_compare_tree), making comparison steps like this non-transitive:

  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0))
    {
      cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra),
                                   DR_BASE_ADDRESS (drb));


Perhaps additive chains in compared operands should be canonicalized first so that if two items are equal according to operand_equal_p they're also guaranteed to be equal according to data_ref_compare_tree?

(In reply to Alexander Monakov from comment #1)
> This is because operand_equal_p is "smarter" than data_ref_compare_tree. We
> have something like
> 
> A: (long)_1 + (_2 + _3)
> B: (_2 + _4) + (long)_1
> C: (_2 + _3) + (long)_1
> 
> with A == C != B according to operand_equal_p (and A < B < C according to
> data_ref_compare_tree), making comparison steps like this non-transitive:
> 
>   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0))
>     {
>       cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra),
>                                    DR_BASE_ADDRESS (drb));
> 
> 
> Perhaps additive chains in compared operands should be canonicalized first
> so that if two items are equal according to operand_equal_p they're also
> guaranteed to be equal according to data_ref_compare_tree?

Possibly.  operand_equal_p does the following which is exponential.

    case tcc_comparison:
    case tcc_binary:
      if (OP_SAME (0) && OP_SAME (1))
        return 1;

      /* For commutative ops, allow the other order.  */
      return (commutative_tree_code (TREE_CODE (arg0))
              && operand_equal_p (TREE_OPERAND (arg0, 0),
                                  TREE_OPERAND (arg1, 1), flags)
              && operand_equal_p (TREE_OPERAND (arg0, 1),
                                  TREE_OPERAND (arg1, 0), flags));

I think sth better would be

   if (commutative_tree_code (...)
       && tree_swap_operands ())
     std::swap (...);

and just compare once.  tree-swap-operands doesn't handle enough cases so
we'd lose some equalities.  But exponential behavior is bad.

Is it possible to simply invoke data_ref_compare_tree always, without checking operand_equal_p beforehand? It's possible to canonicalize commutative chains in data_ref_compare_tree, or - even better - while generating trees in the first place; I don't understand why the operand_equal_p checks are there, they seem more costly than what data_ref_compare_tree does.

On Wed, 4 Oct 2017, amonakov at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82397
> 
> --- Comment #3 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
> Is it possible to simply invoke data_ref_compare_tree always, without checking
> operand_equal_p beforehand? It's possible to canonicalize commutative chains in
> data_ref_compare_tree, or - even better - while generating trees in the first
> place; I don't understand why the operand_equal_p checks are there, they seem
> more costly than what data_ref_compare_tree does.

I believe we exactly left them there because they catches more 
equalities and data_ref_compare_tree was supposed to only order
non-equal ones.

Mine.

(In reply to Alexander Monakov from comment #1)
> This is because operand_equal_p is "smarter" than data_ref_compare_tree. We
> have something like
> 
> A: (long)_1 + (_2 + _3)
> B: (_2 + _4) + (long)_1
> C: (_2 + _3) + (long)_1
> 
> with A == C != B according to operand_equal_p (and A < B < C according to
> data_ref_compare_tree), making comparison steps like this non-transitive:
> 
>   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0))
>     {
>       cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra),
>                                    DR_BASE_ADDRESS (drb));
> 
> 
> Perhaps additive chains in compared operands should be canonicalized first
> so that if two items are equal according to operand_equal_p they're also
> guaranteed to be equal according to data_ref_compare_tree?

I think the issue is not so much the equalness (which we really like to
see!) but the recursion down to the operands with determining which
one is less depends on the order of the operands:

      /* For expressions with operands, compare their operands recursively.  */
      for (i = TREE_OPERAND_LENGTH (t1) - 1; i >= 0; --i)
        {
          cmp = data_ref_compare_tree (TREE_OPERAND (t1, i),
                                       TREE_OPERAND (t2, i));
          if (cmp != 0)
            return cmp;
        }

for a solution we either may _not_ exploit commutativity when looking for
equalities or we need to make the above loop take into consideration
all operands and compute a result that is independent of individual
operand order (which I guess makes the comparison useless...).

Thus.  Hum.  The only thing we can do is to apply clever canonicalization.

Ok, so I'm going to remove all the operand_equal_p tests as a first step.  As a second we can add cleverness like the following (but we really would like to
do this "flatter" in the end...).  iterative_hash_expr could compute it once
for each node in the tree and we could pass the info down when recursing.
Need to think about some clever way to do that tho...

Index: tree-data-ref.c
===================================================================
--- tree-data-ref.c     (revision 253437)
+++ tree-data-ref.c     (working copy)
@@ -1251,6 +1251,28 @@ data_ref_compare_tree (tree t1, tree t2)
          break;
        }
 
+      if (commutative_tree_code (code))
+       {
+         tree t10 = TREE_OPERAND (t1, 0);
+         tree t11 = TREE_OPERAND (t1, 1);
+         tree t20 = TREE_OPERAND (t2, 0);
+         tree t21 = TREE_OPERAND (t2, 1);
+         /* Apply "clever" canonicalization to detect more equalities.
+            ???  Doing this here rather than in whoever builds the
+            trees makes it exponential in the tree size.  */
+         if (iterative_hash_expr (t10, 0) > iterative_hash_expr (t11, 0))
+           std::swap (t10, t11);
+         if (iterative_hash_expr (t20, 0) > iterative_hash_expr (t21, 0))
+           std::swap (t20, t21);
+         cmp = data_ref_compare_tree (t10, t20);
+         if (cmp != 0)
+           return cmp;
+         cmp = data_ref_compare_tree (t11, t21);
+         if (cmp != 0)
+           return cmp;
+         return 0;
+       }
+
       /* For expressions with operands, compare their operands recursively.  */
       for (i = TREE_OPERAND_LENGTH (t1) - 1; i >= 0; --i)
        {

*** Bug 82441 has been marked as a duplicate of this bug. ***

Author: rguenth
Date: Fri Oct  6 09:27:09 2017
New Revision: 253482

URL: https://gcc.gnu.org/viewcvs?rev=253482&root=gcc&view=rev
Log:
2017-10-06  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/82397
	* tree-vect-data-refs.c (dr_group_sort_cmp): Do not use
	operand_equal_p but rely on data_ref_compare_tree for detecting
	equalities.
	(vect_analyze_data_ref_accesses): Use data_ref_compare_tree
	to match up with dr_group_sort_cmp.

	* gfortran.dg/pr82397.f: New testcase.

Added:
    trunk/gcc/testsuite/gfortran.dg/pr82397.f
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vect-data-refs.c

Fixed.

Author: rguenth
Date: Mon Oct  9 14:13:43 2017
New Revision: 253547

URL: https://gcc.gnu.org/viewcvs?rev=253547&root=gcc&view=rev
Log:
2017-10-09  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/82397
	* tree-data-ref.c (data_ref_compare_tree): Make sure to return
	equality only for semantically equal trees.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-data-ref.c