#3855 32 to 16 bit optimization

[Chingson Chen]

long g(long t)
{
    if(t>=2000 && t<4250)
        t=t-(24*t-38580)/1000;
    return t;
}
int main()
{
    if(g(4000)!=3943) fail();
    pass();
}

current sdcc will optimize the 24*t to 16 bit because of previous "if",
and the result is not as expected.

sdcc -v
SDCC : mcs51/z80/z180/r2k/r2ka/r3ka/sm83/tlcs90/ez80_z80/z80n/r800/ds390/pic16/pic14/TININative/ds400/hc08/s08/stm8/pdk13/pdk14/pdk15/mos6502/mos65c02/f8 TD- 4.5.2 #15411 (Linux)
published under GNU General Public License (GPL)

Any comments will be helpful.

P.S.: Edited by @spth, so the multiplication symbols are shown properly instead of being used as markup.

[Janko Stamenović]

A little simpler version with assembly output:

long g(long t) {
    if(t>=2000 && t<4250)
        t=(24*t-38580)/1000;
    return t;
}
int main() {
    long r = g(4000);
    // ASSERT( r == 57 ); // 24*4000-38580=57420
    return r != 57;
}

gives for g:

; Function g
; ---------------------------------
_g::
;abug.c:2: if(t>=2000 && t<4250)
    ld  a, e
    sub a, #0xd0
    ld  a, d
    sbc a, #0x07
    ld  a, l
    sbc a, #0x00
    ld  a, h
    rla
    ccf
    rra
    sbc a, #0x80
    ret C
    ld  a, e
    sub a, #0x9a
    ld  a, d
    sbc a, #0x10
    ld  a, l
    sbc a, #0x00
    ld  a, h
    sbc a, #0x00
    ret NC
;abug.c:3: t=(24*t-38580)/1000;
    ld  l, e
    ld  h, d
    add hl, hl
    add hl, de
    add hl, hl
    add hl, hl
    add hl, hl
    ld  a, l
    add a, #0x4c
    ld  l, a
    ld  a, h
    adc a, #0x69
    ld  de, #0x03e8
    ld  h, a
    call    __divsint
    ld  hl, #0x0000
;abug.c:4: return t;
;abug.c:5: }
    ret

here the if is with the correct 32-bit constants, but afterwards it's indeed everything on 16-bit: the multiplication is done on 16 bits. The subtraction is implemented as adding 0x694c (and note 65536-0x694c=38580) and finally 0x03e8 with which that 16-bit division is performed is the original 1000 decimal.
Without t>=2000 check in the if the expression would use longs:

; Function g
; ---------------------------------
_g::
;abug.c:2: if(t<4250)
    ld  a, e
    sub a, #0x9a
    ld  a, d
    sbc a, #0x10
    ld  a, l
    sbc a, #0x00
    ld  a, h
    rla
    ccf
    rra
    sbc a, #0x80
    ret NC
;abug.c:3: t=(24*t-38580)/1000;
    push    hl
    push    de
    ld  de, #0x0018
    ld  hl, #0x0000
    call    __mullong
    pop af
    pop af
    ld  a, e
    add a, #0x4c
    ld  e, a
    ld  a, d
    adc a, #0x69
    ld  d, a
    ld  a, l
    adc a, #0xff
    ld  l, a
    ld  a, h
    adc a, #0xff
    ld  bc, #0x0000
    push    bc
    ld  bc, #0x03e8
    push    bc
    ld  h, a
    call    __divslong
    pop af
    pop af
;abug.c:4: return t;
;abug.c:5: }
    ret

The condition checks that the t>=2000 and t <4250. Now with these limits can (24*t-38580)/1000 fit in 16 bit arithmetic? As 24*4250==102000for unsigned arithmetic avoiding using one bit could be enough: (12*t-19290)/500 <--that's not done by SDCC now

If the original program would be rewritten e.g. as

long g(long t)
{
    if(t>=2000 && t<4250)
       t=t-(12*t-19290)/500;
    return t;
}
int main()
{
    if(g(4000)!=3943) fail();
    pass();
}

The results would be as expected (I get pass in this example).

[Janko Stamenović]

My experiments show that the current logic in compiler calculates for which range it could use 16-bit arithmetic for the above expression up to the upper limit of:

    if(t>=2000 && t<4339)
        t=t-(24*t-38580)/1000;

because

24*4338-38580 = 65532

for one above it would use longs.
But the above limits are reasonable if the unchanged expression 24*t-38580 uses __divuint, i.e. t=t-(24*(unsigned)t-(unsigned)38580)/1000; would give correct answers for that input range t>=2000 && t<4339.

So if the compiler is not doing the "adjustment of the constants to use less bits" like in my first idea(12*t-19290)/500; but by design always keeps the constants as it finds them in the source, then the current bug is in not using __divuint in that expression in that range in which it estimated under these assumptions that all calculations should fit 16 bits.

[Philipp Klaus Krause]

I've used your simplified version for a regression test ([r15441], disabled for now, until the bug is fixed). Definitely looks like an issue with generalized constant propagation. --nogenconstprop is a workaround.

[Philipp Klaus Krause]

A closer look revealed that generalized constant propagation itself is fine, it just happens to trigger a bug in the handling of unsigned BitInt divisions here.

[Philipp Klaus Krause]

Fixed in [r15555].

[Philipp Klaus Krause]

I have to reopen this ticket: the fix caused a regression for ports that use support functions for shifts. I should have a fix by tonight.

[Philipp Klaus Krause]

Fixed the shift issue in [r15559].