[Bug optimization/12849] New: testing divisibility by constant

[Bug optimization/12849] New: testing divisibility by constant

[gcc-bugzilla at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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

           Summary: testing divisibility by constant
           Product: gcc
           Version: 3.3.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: user42 at zip dot com dot au
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i486-pc-linux-gnu
  GCC host triplet: i486-pc-linux-gnu
GCC target triplet: i486-pc-linux-gnu

I believe tests of divisibility by a constant (ie. n % d == 0, where d
is a compile-time constant) can be improved by the technique described
in section 9 of "Division by Invariant Integers using Multiplication"
by Granlund and Montgomery.

	ftp://ftp.cwi.nl/pub/pmontgom/divcnst.psa4.gz

(This section of this paper is what's currently used in gcc for exact
division by a constant arising from pointer subtraction, but the
divisibility tests managed to escape implementation. :-)

Environment:
System: Linux blah 2.2.15 #1 Tue Apr 25 17:13:48 EST 2000 i586 unknown unknown GNU/Linux
Architecture: i586
	<machine, os, target, libraries (multiple lines)>
host: i486-pc-linux-gnu
build: i486-pc-linux-gnu
target: i486-pc-linux-gnu
configured with: ../src/configure -v --enable-languages=c,c++,java,f77,pascal,objc,ada,treelang --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-gxx-include-dir=/usr/include/c++/3.3 --enable-shared --with-system-zlib --enable-nls --without-included-gettext --enable-__cxa_atexit --enable-clocale=gnu --enable-debug --enable-java-gc=boehm --enable-java-awt=xlib --enable-objc-gc i486-linux

How-To-Repeat:
A little function like,

	void
	bar (unsigned n)
	{
	  if (n % 3 == 0)
	    true ();
	  else
	    false ();
	}

compiled with

	gcc -march=athlon -mcpu=athlon -O3 -fomit-frame-pointer -S dive.c

currently comes out with

        movl    4(%esp), %ecx
        movl    $1639179445, %edx
        movl    %ecx, %eax
        mull    %edx
        shrl    $16, %edx
        imull   $171717, %edx, %edx
        cmpl    %edx, %ecx
	...

I believe instead this could be something like

        movl    4(%esp), %ecx
	imull	$0x4B45300D, %ecx
	cmpl	$0x61B3, %ecx
	...

Notice there's only one low-half multiply, as opposed to a high-half
plus a low-half above.

An even divisor will require an extra rotl (or a separate test of some
low bits), but still ought to be smaller and faster in all cases.


If the actual value of the remainder is wanted then this technique
wouldn't help, it's only for a test for == 0 (or particular values).

When the input does prove to be divisible, then the mul shown gives
the quotient.  Maybe that could be noted on the corresponding side of
the branch, in case it allowed for some CSE.

[Bug optimization/12849] testing divisibility by constant

[falk at debian dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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


falk at debian dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


------- Additional Comments From falk at debian dot org  2003-10-30 22:42 -------
If anybody wants to look into this, the material at http://www.hackersdelight.org/
might be useful.

[Bug optimization/12849] testing divisibility by constant

[pinskia at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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


pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Keywords|                            |pessimizes-code
   Last reconfirmed|0000-00-00 00:00:00         |2003-10-31 01:03:19
               date|                            |


------- Additional Comments From pinskia at gcc dot gnu dot org  2003-10-31 01:03 -------
Nice optimizations.

[Bug optimization/12849] testing divisibility by constant

[user42 at zip dot com dot au]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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



------- Additional Comments From user42 at zip dot com dot au  2003-10-31 22:00 -------
Subject: Re:  testing divisibility by constant

I wrote:
>
> 	  if (n % 3 == 0)

Actually, the asm code I included was for a divisor of 171717.  Small
values get strength reduction on the multiplies, obscuring what gets
done.