From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 15136 invoked by alias); 16 Jul 2006 15:44:52 -0000 Received: (qmail 14681 invoked by uid 48); 16 Jul 2006 15:44:44 -0000 Date: Sun, 16 Jul 2006 15:44:00 -0000 Subject: [Bug c/28395] New: Improved division-by-constant code X-Bugzilla-Reason: CC Message-ID: Reply-To: gcc-bugzilla@gcc.gnu.org To: gcc-bugs@gcc.gnu.org From: "vda dot linux at googlemail dot com" Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org X-SW-Source: 2006-07/txt/msg01175.txt.bz2 List-Id: 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