From: SourceForge.net <no...@so...> - 2011-08-05 13:48:33
|
Feature Requests item #1307995, was opened at 2005-09-29 15:37 Message generated for change (Comment added) made by spth You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=350599&aid=1307995&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: Open Priority: 5 Private: No Submitted By: Philipp Klaus Krause (spth) Assigned to: Nobody/Anonymous (nobody) Summary: Optimize divisons by powers of two. Initial Comment: Please optimize divisons by powers of two. The following two simple functions now generate calls to the internal division functions, while they could be easily implemented with bit shifts: C code: int divtesti(int a) { return(a / 8); } char divtestc(char a) { return(a / 8); } Resulting Z80 asm: ;test.c:8: int divtesti(int a) ; genLabel ; genFunction ; --------------------------------- ; Function divtesti ; --------------------------------- _divtesti_start:: _divtesti: push ix ld ix,#0 add ix,sp ;test.c:10: return(a / 8); ; genIpush ; _saveRegsForCall: sendSetSize: 0 deInUse: 0 bcInUse: 0 deSending: 0 ld hl,#0x0008 push hl ; genIpush ; AOP_STK for ld l,4(ix) ld h,5(ix) push hl ; genCall call __divsint_rrx_s ld b,h ld c,l pop af pop af ; genRet ; Dump of IC_LEFT: type AOP_REG size 2 ; reg = bc ld l,c ld h,b ; genLabel 00101$: ; genEndFunction pop ix ret _divtesti_end:: _BILD: .dw #0x1800 ;test.c:13: char divtestc(char a) ; genLabel ; genFunction ; --------------------------------- ; Function divtestc ; --------------------------------- _divtestc_start:: _divtestc: push ix ld ix,#0 add ix,sp ;test.c:15: return(a / 8); ; genIpush ; _saveRegsForCall: sendSetSize: 0 deInUse: 0 bcInUse: 0 deSending: 0 ld a,#0x08 push af inc sp ; genIpush ; AOP_STK for ld a,4(ix) push af inc sp ; genCall call __divschar_rrx_s ld c,l pop af ; genRet ; Dump of IC_LEFT: type AOP_REG size 1 ; reg = c ld l,c ; genLabel 00101$: ; genEndFunction pop ix ret _divtestc_end:: ---------------------------------------------------------------------- >Comment By: Philipp Klaus Krause (spth) Date: 2011-08-05 15:48 Message: If we want to make right shift logic by default for some target in the future we can always introduce a new shift operator which is undefined for negative qunatities then. Or, alternatively, introduce an ARIGHT_OP and have the old RIGHT_OP undefined for signed stuff (and then make division use ARIGHT_OP). IMO we can use the existing RIGHT_OP for now, and reconsider making separate operations when the need arises. Philipp ---------------------------------------------------------------------- Comment By: Borut Ražem (borutr) Date: 2011-08-05 15:43 Message: My (now shown as false) assumption about different implementations of >> is based on comments in #2997777 and different regtest results for different target when the patch was applied. I didn't systematically look in the code. But even if it is true that all targets do an arithmetic right shift it is dangerous to relay the division with 2^n on it: rhe implementation of >> may change in the future and the division with 2^n will suddenly fail. OTOH the regression tests will show this immediately.... ---------------------------------------------------------------------- Comment By: Philipp Klaus Krause (spth) Date: 2011-08-05 15:41 Message: I don't think there can be ports that do not use arithmetic right shift for signed types: Regression test2ShiftRight() in the shifts.c regression tests explicitly checks that right shift is arithmetic. Philipp ---------------------------------------------------------------------- Comment By: Philipp Klaus Krause (spth) Date: 2011-08-05 15:29 Message: >The result of a right shift of a signed negative quantity is undefined in the C spec I know. > The implementation differs even for different targets in sdcc I thought that all targets do an arithmetic right shift. Which ones do not? A quick look at the z80 and pic16 shows they do arithmetic right shift. The pic14 port seems to do it that way as well, but it has the confusing comment that was in the z80 code, too. Would there be a cost associated with making all ports always do an arithmetic right shift for signed types? Philipp P.S.: There were contradicting comments in the Z80 backend code regarding this issue. I just removed the incorrect one. ---------------------------------------------------------------------- Comment By: Borut Ražem (borutr) Date: 2011-08-05 15:06 Message: The result of a right shift of a signed negative quantity is undefined in the C spec, as Maaten already mentioned in #2997777. The implementation differs even for different targets in sdcc. In the proposed solution is probably assumed that >> is implemented as arithmetic shift right (please correct me if I'm wrong), so the proper notation would be: t = x; if(t < 0) t += 2 ^ k - 1; y = t ASR_OP k; See my proposal for ASR_OP introduction in #2997777 and all conversation that follows. Borut ---------------------------------------------------------------------- Comment By: Philipp Klaus Krause (spth) Date: 2011-08-05 14:28 Message: IMO the solution presented here is equivalent to the one from #3072154, but written down in a more elegant way. The proposal from #2997777 is just wrong. Thus I'll close the other two items. Philipp ---------------------------------------------------------------------- Comment By: Borut Ražem (borutr) Date: 2011-08-05 14:20 Message: See also http://sourceforge.net/tracker/?func=detail&aid=2997777&group_id=599&atid=300599 and http://sourceforge.net/tracker/?func=detail&aid=3072154&group_id=599&atid=350599 ---------------------------------------------------------------------- Comment By: Philipp Klaus Krause (spth) Date: 2011-08-04 12:35 Message: The correct wayx to implement this would be to transform y = x / 2^k; into t = x; if(t < 0) t += 2 ^ k - 1; y = t >> k; The simpler y = x >> k; is wrong, since it rounds towards minus infinity instead of towards zero. Philipp ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=350599&aid=1307995&group_id=599 |