Menu
▾
▴
[sdcc-devel] [ sdcc-Patches-2997777 ] Doesn't strength reduce signed division by powers of two.
|
From: SourceForge.net <no...@so...> - 2011-08-06 09:55:53
|
Patches item #2997777, was opened at 2010-05-06 19:52 Message generated for change (Comment added) made by maartenbrock You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=300599&aid=2997777&group_id=599 Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None Status: Closed Resolution: Rejected Priority: 5 Private: No Submitted By: C. Scott Ananian (cananian) Assigned to: Philipp Klaus Krause (spth) Summary: Doesn't strength reduce signed division by powers of two. Initial Comment: SDCC correctly transforms: a /= 2 to a >>= 1 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. ---------------------------------------------------------------------- >Comment By: Maarten Brock (maartenbrock) Date: 2011-08-06 11:55 Message: 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. ---------------------------------------------------------------------- Comment By: Philipp Klaus Krause (spth) Date: 2011-08-05 14:30 Message: 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 ---------------------------------------------------------------------- Comment By: Borut Ražem (borutr) Date: 2010-05-08 11:22 Message: 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 ---------------------------------------------------------------------- Comment By: Philipp Klaus Krause (spth) Date: 2010-05-08 09:17 Message: 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 ---------------------------------------------------------------------- Comment By: C. Scott Ananian (cananian) Date: 2010-05-07 23:50 Message: 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 ---------------------------------------------------------------------- Comment By: Borut Ražem (borutr) Date: 2010-05-07 19:15 Message: 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... ---------------------------------------------------------------------- Comment By: Borut Ražem (borutr) Date: 2010-05-07 19:08 Message: Exactly. And they showed the the patch is not correct since RIGHT_OP is implemented with logical shifts. ---------------------------------------------------------------------- Comment By: Maarten Brock (maartenbrock) Date: 2010-05-07 17:38 Message: Oh wait, I think you meant we have a test for division by two on signed integers. ---------------------------------------------------------------------- Comment By: Maarten Brock (maartenbrock) Date: 2010-05-07 17:36 Message: 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. ---------------------------------------------------------------------- Comment By: Borut Ražem (borutr) Date: 2010-05-07 16:28 Message: 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 ---------------------------------------------------------------------- Comment By: Maarten Brock (maartenbrock) Date: 2010-05-07 11:12 Message: 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 ---------------------------------------------------------------------- Comment By: Borut Ražem (borutr) Date: 2010-05-07 00:03 Message: 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 ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=300599&aid=2997777&group_id=599 |