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

["gcc-bugzilla at gcc dot gnu dot org" <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.