[Bug tree-optimization/82397] [8 Regression] qsort comparator non-negative on sorted output: 1 in vect_analyze_data_ref_accesses

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82397

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ice-checking
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2017-10-04
            Version|unknown                     |8.0
   Target Milestone|---                         |8.0
            Summary|qsort comparator            |[8 Regression] qsort
                   |non-negative on sorted      |comparator non-negative on
                   |output: 1 in                |sorted output: 1 in
                   |vect_analyze_data_ref_acces |vect_analyze_data_ref_acces
                   |ses                         |ses
     Ever confirmed|0                           |1

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
(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.