[sdcc-devel] [ sdcc-Feature Requests-3072154 ] Optimize division by powers of two.

[SourceForge.net <no...@so...>]

Feature Requests item #3072154, was opened at 2010-09-20 23:07
Message generated for change (Comment added) made by frief
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=350599&aid=3072154&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: 3
Private: No
Submitted By: Philipp Klaus Krause (spth)
Assigned to: Nobody/Anonymous (nobody)
Summary: Optimize division by powers of two.

Initial Comment:
x / 2^n for a int16_t x

could be implemented like this:

int16_t divbytwo(int16_t x, uint8_t n)
{
bool s = (x < 0);
uint16_t v = x;
do
  v >>= 1;
while(--n);
return(s ? -v : v);
}

This would be significantly faster than the currently used generic division.

Philipp


----------------------------------------------------------------------

>Comment By: Frieder Ferlemann (frief)
Date: 2010-11-11 22:52

Message:
Hi b-s-a,

code for optimizing multiply with 7 and 5 was there for PIC once.

case 5:
 	emitpcode(POC_MOVFW, popGet(AOP(left),0));
 	emitpcode(POC_ADDFW, popGet(AOP(left),0)); // W = 2*F
 	emitpcode(POC_ADDWF, popGet(AOP(left),0)); // F = 3*F
 	emitpcode(POC_ADDWF, popGet(AOP(left),0)); // F = 5*F
 	return; 

case 7:

but unfortunately was removed.

With recent renaming/moving of the pic tree to the pic14 tree
the history of all the files is lost. Not good.

But the really out of date cvs repository still has the function
genUMult8XLit_16(). See
http://sdcc.cvs.sourceforge.net/viewvc/sdcc/sdcc/src/pic/genarith.c?revision=1.36&view=markup
line 1710

There is another reminiscent of these formerly implemented pic14 
optimizations in the pic regression test in sdcc/src/regression/mult1.c 
which includes checks for multiplies with
2; 3; 4; 5; 6; 7; 8; 9;
10;11;12;13;14;15;16;17;18;19;20;21;22;23;24;31;32;64;128;

----------------------------------------------------------------------

Comment By: b-s-a (b-s-a)
Date: 2010-11-11 12:09

Message:
Moreover it is possible to optimize (for speed) any multiplication with
constant using shifts, additions and subtractions.
Examples:
x * 7 == {t = x; x <<= 3; x -= t; }
x * 5 == {t = x; x <<= 2; x += t; }

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=350599&aid=3072154&group_id=599