[Bug tree-optimization/57600] New: Turn 2 comparisons into 1 with the min

[Bug tree-optimization/57600] New: Turn 2 comparisons into 1 with the min

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57600

            Bug ID: 57600
           Summary: Turn 2 comparisons into 1 with the min
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org

Hello,

in this code:

double SumProduct(const double* v1, const double* v2, int n1, int n2)
{
  double sum=0;
  for(int i=0; i<n1 && i<n2; ++i)
    sum += v1[i]*v2[i];
  return sum;
}

it seems clear that i<n1 && i<n2 should be replaced with i<min(n1,n2) with the
min computation taken out of the loop. Not only do we have 2 comparisons
instead of one in the loop, this also prevents vectorization.

The closest PRs I have found (PR 10520 and PR 21855) are actually very
different.

[Bug tree-optimization/57600] Turn 2 comparisons into 1 with the min

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57600

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-06-13
             Blocks|                            |53947
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  We have tree-ssa-if-combine.c that has various ways to combine
&&ed and ||ed comparisons.  This transform would be a useful addition.

[Bug tree-optimization/57600] Turn 2 comparisons into 1 with the min

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57600

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
The main difficulty is deciding when this transformation is a good idea. A
priori a<b&&a<c can be faster than a<min(b,c). Good cases:
- if there is a min insn (like minsd for double on x86_64, but that might
require finite-math-only);
- if we are in a loop and b and c are invariants (not sure ifcombine is the
right place for that).

Or do we want to do the transformation always, and maybe have something later
(in RTL?) to undo it if it didn't help?

Note that in some experiments with more meat in the loop, having i<min(n1,n2)
made the compiler not see a dominating i<n1 anymore and it lost some
optimizations.

[Bug tree-optimization/57600] Turn 2 comparisons into 1 with the min

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57600

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Perhaps we want to perform it just during ifcvt once it is rolled into
vectorizer and works on an on-the-side bb?  Then it wouldn't affect
non-vectorized code.

[Bug tree-optimization/57600] Turn 2 comparisons into 1 with the min

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57600

--- Comment #4 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #3)
> Perhaps we want to perform it just during ifcvt once it is rolled into
> vectorizer and works on an on-the-side bb?  Then it wouldn't affect
> non-vectorized code.

We would miss some useful cases (in the original testcase, the transformation
is worth it even without vectorizing), but at least it would make regressions
unlikely...

[Bug tree-optimization/57600] Turn 2 comparisons into 1 with the min

[alalaw01 at gcc dot gnu.org]

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

alalaw01 at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |alalaw01 at gcc dot gnu.org

--- Comment #5 from alalaw01 at gcc dot gnu.org ---
(In reply to Marc Glisse from comment #2)
>
> Or do we want to do the transformation always, and maybe have something
> later (in RTL?) to undo it if it didn't help?
> 
> Note that in some experiments with more meat in the loop, having
> i<min(n1,n2) made the compiler not see a dominating i<n1 anymore and it lost
> some optimizations.

Can you give an example where it not only doesn't help, but actually hurts? Are
they all just because of not seeing analysis properties, i.e. we could get
there by realizing a<=min(a,...) and looking far enough to see a<X<=Y means a<Y
? In terms of code generation,

t = min (a,b)
if (x<t) goto ...

can always be implemented as

t = a
if (a<b) goto lab
t=b
lab: if (x<t) goto ...

vs

if (x<a) goto ...
if (x<b) goto ...

i.e. the same number of compares and branches, so is it the extra two moves we
are concerned about?

(Jump-threading on RTL to remove even those, perhaps?!)

[Bug tree-optimization/57600] Turn 2 comparisons into 1 with the min

[glisse at gcc dot gnu.org]

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

--- Comment #6 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to alalaw01 from comment #5)
> Can you give an example where it not only doesn't help, but actually hurts?

I don't remember at all what I was talking about. I can imagine that if we are
in a branch predicated by i < n1, the compiler has an easy time turning
i<n1&&i<n2 into just i<n2, but it has a harder time turning i<min(n1,n2) into
i<n2, for instance, and that can block a whole line of further optimizations.

> Are they all just because of not seeing analysis properties, i.e. we could
> get there by realizing a<=min(a,...) and looking far enough to see a<X<=Y
> means a<Y ?

I guess it is always possible to add enough knowledge of this special case in
various places in gcc to avoid most regressions. I don't have enough data to
judge how hard it would be to make the transformation a win on average. It
might be that it is already more often beneficial than detrimental, for all I
know...

> In terms of code generation,

I am more worried about the high-level optimizations we may miss, but note that
the number of comparisons is not necessarily the right metric, the comparison
a<b may be completely unpredictable while t<a and t<b are always true.