[Bug fortran/57071] New: Optimize (-1)**k to 1 - 2 * mod(K, 2)

[Bug fortran/57071] New: Optimize (-1)**k to 1 - 2 * mod(K, 2)

[burnus at gcc dot gnu.org]

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

             Bug #: 57071
           Summary: Optimize  (-1)**k  to 1 - 2 * mod(K, 2)
    Classification: Unclassified
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: fortran
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: burnus@gcc.gnu.org
                CC: tkoenig@gcc.gnu.org


Motivated by
https://groups.google.com/forum/?fromgroups=#!topic/comp.lang.fortran/60jYF5XEY3c

The code (k is an integer):
  (-1)**k
and
  (-1.0)**k
can be rather common in numeric code. The former is converted into
  _gfortran_pow_i4_i4 (-1, *k);
the latter is
  __builtin_powif (-1.0e+0, *k);

However, for (-1)**k, the result is simply 1 is k is even and -1 if it is odd,
or in other words:

  1 - 2 * mod(K, 2)


integer function f(k)
  f = (-1)**k  ! Or: (-1.0)**k
end

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[burnus at gcc dot gnu.org]

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

Tobias Burnus <burnus at gcc dot gnu.org> changed:

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

--- Comment #1 from Tobias Burnus <burnus at gcc dot gnu.org> 2013-04-25 18:06:08 UTC ---
See also PR 57073 for the related middle-end bug report.

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[Joost.VandeVondele at mat dot ethz.ch]

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

Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Joost.VandeVondele at mat
                   |                            |dot ethz.ch

--- Comment #2 from Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> 2013-04-26 06:52:13 UTC ---
indeed, very common to write this.. however, this is even more common in a loop

DO i=0,N
   y=y+(-1)**i * x**i
ENDDO

so there you really would like to have this converted to some form that uses
...
DO i=..
    tmp_s=-tmp_s  
    tmp_x=tmp_x*x
    y=y+tmp_s*tmp_x
ENDDO

I'm not sure how the different forms behave in this respect.

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[burnus at gcc dot gnu.org]

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

--- Comment #3 from Tobias Burnus <burnus at gcc dot gnu.org> 2013-04-26 07:07:22 UTC ---
As James Van Buskirk pointed out, the algorithm will fail if k < 0. Thus, he
suggests, which gives the expected result:

  1 - ISHFT(IAND(K,1),1)

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[Joost.VandeVondele at mat dot ethz.ch]

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

--- Comment #4 from Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> 2013-04-26 07:12:04 UTC ---
(In reply to comment #3)
> As James Van Buskirk pointed out, the algorithm will fail if k < 0. 

note that in the case of k being a loop index, there will be pretty good range
infomation (e.g. k>=0)

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[burnus at gcc dot gnu.org]

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

--- Comment #5 from Tobias Burnus <burnus at gcc dot gnu.org> 2013-04-26 07:26:31 UTC ---
(In reply to comment #3)
>   1 - ISHFT(IAND(K,1),1)

For the real version Jakub suspects that  (k & 1) ? -1.0 : 1.0  is faster than
the mod/convert to float/subtraction or the and/shift/convert to
float/substraction, cf. PR 57073.

(In reply to comment #4)
h> note that in the case of k being a loop index, there will be pretty good
range
> infomation (e.g. k>=0)

But that requires a complicated flow analysis - you have to track where the
exponent gets set etc. And you only gain little compared to the k&1?-1.:1. or
1.0-((k&1)<<1) algorithm - they might even be faster and are more general.

It is also not really clear to me whether the proposal of comment 4 has a
benefit. I think the biggest advantage is to replace a function call by inline
code; that allows more middle-end optimizations as it is inline - and as the
inlined code is small, it should always be a win in code size (and, of course,
performance).

(For completeness: The original algorithm works if one replaces "mod" by
"modulo".)

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> 2013-04-26 09:16:41 UTC ---
Note that for the (-1.0)**k case __builtin_powif (-1.0e+0, k) should be
perfectly fine for the middle-end.  _gfortran_pow_i4_i4 (-1, k) is of
course unfortunate and should be optimized by the frontend.

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[tkoenig at gcc dot gnu.org]

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

--- Comment #8 from Thomas Koenig <tkoenig at gcc dot gnu.org> 2013-04-27 23:19:13 UTC ---
While special-casing power, it might also make sense
to translate 2**n to ishft(1,n).

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[tkoenig at gcc dot gnu.org]

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

--- Comment #9 from Thomas Koenig <tkoenig at gcc dot gnu.org> 2013-04-28 13:34:08 UTC ---
Author: tkoenig
Date: Sun Apr 28 13:32:59 2013
New Revision: 198369

URL: http://gcc.gnu.org/viewcvs?rev=198369&root=gcc&view=rev
Log:
2013-04-28  Thomas Koenig  <tkoenig@gcc.gnu.org>

    PR fortran/57071
    * frontend-passes (optimize_power):  New function.
    (optimize_op):  Use it.

2013-04-28  Thomas Koenig  <tkoenig@gcc.gnu.org>

    PR fortran/57071
    * gfortran.dg/power_3.f90:  New test.
    * gfortran.dg/power_4.f90:  New test.


Added:
    trunk/gcc/testsuite/gfortran.dg/power_3.f90
    trunk/gcc/testsuite/gfortran.dg/power_4.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/frontend-passes.c
    trunk/gcc/testsuite/ChangeLog

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[tkoenig at gcc dot gnu.org]

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

--- Comment #10 from Thomas Koenig <tkoenig at gcc dot gnu.org> 2013-04-30 21:46:11 UTC ---


Author: tkoenig
Date: Tue Apr 30 21:45:13 2013
New Revision: 198476

URL: http://gcc.gnu.org/viewcvs?rev=198476&root=gcc&view=rev
Log:
2013-04-30  Thomas Koenig  <tkoenig@gcc.gnu.org>

    PR fortran/57071
    * frontend-passes.c (optimize_power):  Simplify
    1**k to 1.

2013-04-30  Thomas Koenig  <tkoenig@gcc.gnu.org>

    PR fortran/57071
    * gfortran.dg/power_5.f90:  New test.


Added:
    trunk/gcc/testsuite/gfortran.dg/power_5.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/frontend-passes.c
    trunk/gcc/testsuite/ChangeLog

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[tkoenig at gcc dot gnu.org]

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

Thomas Koenig <tkoenig at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #11 from Thomas Koenig <tkoenig at gcc dot gnu.org> 2013-04-30 21:49:14 UTC ---
Fixed, closing; this time the right PR.

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[tkoenig at gcc dot gnu.org]

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

--- Comment #12 from Thomas Koenig <tkoenig at gcc dot gnu.org> ---
Created attachment 30141
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30141&action=edit
Another patch that doesn't work...

I tried to follow the advice in comment#9, but I hit a wall
(again).

With the attached patch, I hit

foo.f90:1:0: error: SSA_NAME_DEF_STMT is wrong
 program main
 ^
Expected definition statement:
_16 = 1.0e+0;

Actual definition statement:
_16 = _24;

so I suspect I need PHI nodes here.

Is this the right approach in general?  Am I missing something
simple here?

[Bug fortran/57071] Optimize (-1)**k to 1 - 2 * mod(K, 2)

[tkoenig at gcc dot gnu.org]

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

--- Comment #13 from Thomas Koenig <tkoenig at gcc dot gnu.org> ---
Sorry, wrong PR for the comment.