[Bug c/28417] suboptimal 'division by constant' optimization

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

------- Comment #2 from vda dot linux at googlemail dot com  2006-07-18 12:06 -------
Pseudo-code to help in reading above code:

void fastdiv_params(unsigned B, unsigned max_A)
{
        L = (max_unsigned_long_long/max_unsigned - 1) * B;
        L = largest_pow2_smaller_or_eq_to(L);
        bits = log2(L);
        while ((K = L/B + 1) > max_unsigned)
                bits--, L >>= 1;
        // There is not much point in multiplying by even 'K'
        // and then shifting right (dividing by 2*n). Reduce K & L to avoid it:
        while (!(K & 1) && bits > 32)
                bits--, L >>= 1, K = L/B + 1;

        d_LB = ((L/B) * B + B - L);
        bad_A = L / d_LB;
        bad_A = (bad_A / B) * B + B-1;
        if (bad_A <= max_A)
                bail_out_no_params_exist;

        // 'K' and 'bits' params are already determined, can return them...
        /* return_params(K,bits); */

        // ...but if max_A is smaller then max_unsigned, we can
        // optionally use smaller 'K' and 'bits'. Find smallest which
        // still work:
        max_bits = bits;
        max_bad_A = bad_A;
        while(1) {
                uint64_t last_L = L;
                unsigned last_K = K;
                bits--;
                L >>= 1;
                K = L/B + 1;
                d_LB = ((L/B) * B + B - L);
                bad_A = L / d_LB;
                bad_A = (bad_A / B) * B + B-1;
                if (bad_A <= max_A || bits < 32)
                        // new params are bad, report last ones and bail out
                        return_params(last_K,bits+1);
        }
}


-- 

vda dot linux at googlemail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|middle-end                  |c


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