[Bug c/28395] New: Improved division-by-constant code

["vda dot linux at googlemail dot com" <gcc-bugzilla at gcc dot gnu dot org>]

32-bit unsigned division A/B by compile-time constant B can be optimized by
replacing it with multiplication and shift right. For example, division by 10
is done like this: (A*3435973837) >> 35, in i386 asm:
        movl    $-858993459, %ecx
        movl    8(%ebp), %eax
        mull    %ecx
        movl    %edx, %esi
        shrl    $3, %esi
Choosing right constant by which we need to multiply is not trivial: large A
values can give wrong results. I spent a few days researching this. I will
attach the following test programs:

find_fast_div.c: reports fastdiv params for every B in [3..2^32-1]

fast_div_bench.c: measures speed improvement when dividing by B=10.

find_fast_div_random.c: there is fastdiv_params() function which is intended to
go into gcc's optimizer, "constant division" department. It calculates fastdiv
parameters (K,bits) for given B and max_A (max_A is to be supplied by gcc's
value range analyser). main() calls fastdiv_params() with random parameters in
the loop.

I am not familiar with gcc internals. Please tell me what should I do next in
order to integrate it inot gcc.


-- 
           Summary: Improved division-by-constant code
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: vda dot linux at googlemail dot com


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