if a is unsigned, but doesn't perform this valid transformation when a is signed (in which case the sign bit is correctly propagated by the right shift). The attached patch fixes the problem.
It doesn't work for negative values, since the arithmetic shift should be used instead of logical shift produced by RIGHT_OP.
I see 3 possible solutions:
- introduce a new "arithmetic shift right" iCode operator (ASR_OP)
- "manually" adjust the sign bit after shifting. This one probably doesn't make sense...
- move the optimization from iCode level to target code generation level
Borut
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Not quite. It might work for negative values as the behaviour is undefined in the C spec. I don't know what the current behaviour is but we could choose to make it an arithmetic shift.
In general an arithmetic shift might be more expensive than a logical shift though if the mcu does support it natively.
Maarten
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
It might work, but it doesn't: the RIGHT_OP is implemented as logical shift on all platforms (you can see regression tests failures if you apply the patch, as I did ;-).
So Marten, you are right, there is a fourth possibility:
- implement RIGHT_OP as arithmetic right shift instead of logical shift for all targets
but this would break the backward compatibility in case somebody relay on this behavior and bloat the generated code for C shift (x >> n) on targets that doesn't natively support arithmetic shift right (do we have such one?)
Borut
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
At least the Z80 and the HC08 have both logical and arithmetic shift right instructions. The mcs51 and ds390 have neither, they can only rotate. I know nothing about PICs.
So we have regression tests to test undefined behaviour. You learn something new every day ;-)
I agree to keep things as they are and not introduce a new operator for this optimization.
Btw. I moved this item to PATCHES as it is no BUG and contained a patch.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Maybe we should open a RFE to optimize division by power of 2 so that it will remain open and maybe someone will implement it someday.This one is already closed and will be lost in the time and space...
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
1) Some ports, e.g. the Z80 already do an arithmetic shift for RIGHT_OP on signed operands.
2) It's not as simple as everyone in the comments seems to assume. Arithmetic right shift is not a valid substitute for signed division by powers of two: The C standard requires the division results to be rounded towards zero. The arithmetic right shift rounds towards minus infinity.
Philipp
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I ran regtsts with the applied patch, and here are the failing tests:
gen/ds390/bug-524685/bug-524685.out:3:--- FAIL: "Assertion failed" on left/4 == (-18/4) at gen/ds390/bug-524685/bug-524685.c:11
gen/ds390/muldiv/muldiv_storage_none_type_char_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_char_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_none_type_char_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_char_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_none_type_int_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_int_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_none_type_int_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_int_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_none_type_long_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_long_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_none_type_long_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_long_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_none_type_short_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_short_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_none_type_short_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_short_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_static_type_char_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_char_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_static_type_char_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_char_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_static_type_int_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_int_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_static_type_int_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_int_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_static_type_long_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_long_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_static_type_long_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_long_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_static_type_shortds390_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_short_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_static_type_short_attr_volatile.out:6:--- FAILhc08: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_short_attr_volatile.c:89
The tests fails in the same way for targets: ds390, hc08, mcs51-huge, mcs51-large, mcs51-medium, mcs51-small, mcs51-stack-auto, mcs51-xstack-auto.
The ucz80 test result is slightly different (muldiv test fails only 13 times, while on other tests if fails 16 times):
gen/ucz80/bug-524685/bug-524685.out:9:--- FAIL: "Assertion failed" on left/4 == (-18/4) at gen/ucz80/bug-524685/bug-524685.c:11
gen/ucz80/muldiv/muldiv_storage_none_type_char_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_char_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_char_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_char_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_int_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_int_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_int_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_int_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_long_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_long_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_short_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_short_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_short_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_short_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_char_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_char_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_char_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_char_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_int_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_int_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_int_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_int_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_short_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_short_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_short_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_short_attr_volatile.c:89
I haven't made deeper analyses, but the the results show that the patch fails also on mcs51 target.
It fails on z80 target to, but not so many times.
I haven't tested the pic and pic16 targets.
Borut
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
In RFE #1307995 a correct (unlike this one) solution is proposed. I'll thus close this item. However, it could be that the simpler solution rpesented here would be correct for ANSI C and ISO C89. It is definitely wrong for ISO C99; the solution from RFE #1307995 is correct for all of them.
Philipp
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Stating that the solution is wrong is too strong. C99 does not require the right shift operator (>>) to round towards minus infinity. It does not even require to keep the sign. It says the result of right shifting a negative signed value is "implementation defined". However since SDCC currently implements it as an arithmetic right shift that does keep the sign and rounds towards minus infinity (just as GCC does) I agree to close and discard this item.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
> Stating that the solution is wrong is too strong.
Yes. However that would be a quite weird implementation of >> that would make using >> for / work.
Neither arithmetic shift nor logical shift would allow just replacing / by >>.
Philipp
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Patch to fix optimization of signed division.
It doesn't work for negative values, since the arithmetic shift should be used instead of logical shift produced by RIGHT_OP.
I see 3 possible solutions:
- introduce a new "arithmetic shift right" iCode operator (ASR_OP)
- "manually" adjust the sign bit after shifting. This one probably doesn't make sense...
- move the optimization from iCode level to target code generation level
Borut
Not quite. It might work for negative values as the behaviour is undefined in the C spec. I don't know what the current behaviour is but we could choose to make it an arithmetic shift.
In general an arithmetic shift might be more expensive than a logical shift though if the mcu does support it natively.
Maarten
It might work, but it doesn't: the RIGHT_OP is implemented as logical shift on all platforms (you can see regression tests failures if you apply the patch, as I did ;-).
So Marten, you are right, there is a fourth possibility:
- implement RIGHT_OP as arithmetic right shift instead of logical shift for all targets
but this would break the backward compatibility in case somebody relay on this behavior and bloat the generated code for C shift (x >> n) on targets that doesn't natively support arithmetic shift right (do we have such one?)
Borut
At least the Z80 and the HC08 have both logical and arithmetic shift right instructions. The mcs51 and ds390 have neither, they can only rotate. I know nothing about PICs.
So we have regression tests to test undefined behaviour. You learn something new every day ;-)
I agree to keep things as they are and not introduce a new operator for this optimization.
Btw. I moved this item to PATCHES as it is no BUG and contained a patch.
Oh wait, I think you meant we have a test for division by two on signed integers.
Exactly. And they showed the the patch is not correct since RIGHT_OP is implemented with logical shifts.
Maybe we should open a RFE to optimize division by power of 2 so that it will remain open and maybe someone will implement it someday.This one is already closed and will be lost in the time and space...
borutr: you must not have tested on the mcs51 target: it implements RIGHT_OP as an arithmetic shift. (My patch works correctly for me!)
Test case:
#include <stdint.h>
extern void foo(int8_t x);
void bar(int8_t x) {
foo(x >> 2);
}
Command:
sdcc --version
SDCC : mcs51/gbz80/z80/avr/ds390/pic16/pic14/TININative/xa51/ds400/hc08 2.9.0 #5416 (May 6 2010) (UNIX)
sdcc -c test.c
Output:
107 ; test.c:4: foo(x >> 2);
0000 E5 82 108 mov a,dpl
0002 A2 E7 109 mov c,acc.7
0004 13 110 rrc a
0005 A2 E7 111 mov c,acc.7
0007 13 112 rrc a
0008 F5 82 113 mov dpl,a
000A 02s00r00 114 ljmp _foo
1) Some ports, e.g. the Z80 already do an arithmetic shift for RIGHT_OP on signed operands.
2) It's not as simple as everyone in the comments seems to assume. Arithmetic right shift is not a valid substitute for signed division by powers of two: The C standard requires the division results to be rounded towards zero. The arithmetic right shift rounds towards minus infinity.
Philipp
I ran regtsts with the applied patch, and here are the failing tests:
gen/ds390/bug-524685/bug-524685.out:3:--- FAIL: "Assertion failed" on left/4 == (-18/4) at gen/ds390/bug-524685/bug-524685.c:11
gen/ds390/muldiv/muldiv_storage_none_type_char_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_char_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_none_type_char_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_char_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_none_type_int_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_int_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_none_type_int_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_int_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_none_type_long_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_long_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_none_type_long_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_long_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_none_type_short_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_short_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_none_type_short_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_none_type_short_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_static_type_char_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_char_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_static_type_char_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_char_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_static_type_int_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_int_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_static_type_int_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_int_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_static_type_long_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_long_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_static_type_long_attr_volatile.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_long_attr_volatile.c:89
gen/ds390/muldiv/muldiv_storage_static_type_shortds390_attr_none.out:6:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_short_attr_none.c:89
gen/ds390/muldiv/muldiv_storage_static_type_short_attr_volatile.out:6:--- FAILhc08: "Assertion failed" on i/4 == -12 at gen/ds390/muldiv/muldiv_storage_static_type_short_attr_volatile.c:89
The tests fails in the same way for targets: ds390, hc08, mcs51-huge, mcs51-large, mcs51-medium, mcs51-small, mcs51-stack-auto, mcs51-xstack-auto.
The ucz80 test result is slightly different (muldiv test fails only 13 times, while on other tests if fails 16 times):
gen/ucz80/bug-524685/bug-524685.out:9:--- FAIL: "Assertion failed" on left/4 == (-18/4) at gen/ucz80/bug-524685/bug-524685.c:11
gen/ucz80/muldiv/muldiv_storage_none_type_char_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_char_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_char_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_char_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_int_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_int_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_int_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_int_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_long_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_long_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_short_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_short_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_none_type_short_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_none_type_short_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_char_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_char_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_char_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_char_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_int_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_int_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_int_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_int_attr_volatile.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_short_attr_none.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_short_attr_none.c:89
gen/ucz80/muldiv/muldiv_storage_static_type_short_attr_volatile.out:12:--- FAIL: "Assertion failed" on i/4 == -12 at gen/ucz80/muldiv/muldiv_storage_static_type_short_attr_volatile.c:89
I haven't made deeper analyses, but the the results show that the patch fails also on mcs51 target.
It fails on z80 target to, but not so many times.
I haven't tested the pic and pic16 targets.
Borut
In RFE #1307995 a correct (unlike this one) solution is proposed. I'll thus close this item. However, it could be that the simpler solution rpesented here would be correct for ANSI C and ISO C89. It is definitely wrong for ISO C99; the solution from RFE #1307995 is correct for all of them.
Philipp
Stating that the solution is wrong is too strong. C99 does not require the right shift operator (>>) to round towards minus infinity. It does not even require to keep the sign. It says the result of right shifting a negative signed value is "implementation defined". However since SDCC currently implements it as an arithmetic right shift that does keep the sign and rounds towards minus infinity (just as GCC does) I agree to close and discard this item.
> Stating that the solution is wrong is too strong.
Yes. However that would be a quite weird implementation of >> that would make using >> for / work.
Neither arithmetic shift nor logical shift would allow just replacing / by >>.
Philipp