Re: Bit swizzling

Martin Ward <martin@gkc.org.uk>
Mon, 7 Sep 2020 12:08:23 +0100

          From comp.compilers
Related articles
Bit swizzling rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-05)
Re: Bit swizzling DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2020-09-05)
Re: Bit Swizzling johnl@taugh.com (John Levine) (2020-09-05)
Re: Bit swizzling 793-849-0957@kylheku.com (Kaz Kylheku) (2020-09-05)
Re: Bit swizzling davidlovemore@gmail.com (davidl...@gmail.com) (2020-09-06)
Re: Bit Swizzling xxx.syseng.yyy@gfsys.co.uk (Chris) (2020-09-06)
Re: Bit swizzling martin@gkc.org.uk (Martin Ward) (2020-09-07)
Re: Bit swizzling rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-07)
Re: Bit swizzling DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2020-09-08)
Re: Bit swizzling tomcrick@gmail.com (Tom Crick) (2020-09-08)
Re: Bit swizzling gah4@u.washington.edu (gah4) (2020-09-10)
Re: Bit swizzling rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-10)
| List of all articles for this month |
From: Martin Ward <martin@gkc.org.uk>
Newsgroups: comp.compilers
Date: Mon, 7 Sep 2020 12:08:23 +0100
Organization: Compilers Central
References: 20-09-014
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="25796"; mail-complaints-to="abuse@iecc.com"
Keywords: optimize
Posted-Date: 07 Sep 2020 13:57:44 EDT
In-Reply-To: 20-09-014
Content-Language: en-GB

On 05/09/2020 17:05, Rick C. Hodgin wrote:
> Are there any existing algorithms which examine the operations that
> must be conducted and then create an optimized / minimal sequence of
> mechanical steps to conduct it given a constrained set of features
> (such as those present on a given CPU)?


The process you are describing is called "Superoptimization":
finding the optimal code sequence for one loop-free sequence
of instructions.


https://en.wikipedia.org/wiki/Superoptimization


The term superoptimization was first coined by Alexia Massalin in the
1987 paper "Superoptimizer: A Look at the Smallest Program":


http://www.stanford.edu/class/cs343/resources/superoptimizer.pdf


Back in 1980 there was a discussion in the magazine
"Pratical Electronics" regarding the shortest sequence of
instructions needed to reverse the bits in the accumulator
for a 6800 system (an operation that is needed in some Fast Fourier
Transform algorithms).


One solution (given in June 1980, page 70) consisted of just
two instructions and used no additional data.
The instructions were:


STAA PORTA write to output port
LDAB PORTB read from input port


with the output port being wired directly to the input port with
the bits reversed!


--
Martin


Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.