Re: Bit swizzling

From	Martin Ward <martin@gkc.org.uk>
Newsgroups	comp.compilers
Subject	Re: Bit swizzling
Date	2020-09-07 12:08 +0100
Organization	Compilers Central
Message-ID	<20-09-020@comp.compilers> (permalink)
References	<20-09-014@comp.compilers>

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Bit swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-05 12:05 -0400
  Re: Bit swizzling Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-09-05 19:38 +0200
  Re: Bit Swizzling "John Levine" <johnl@taugh.com> - 2020-09-05 18:50 +0000
    Re: Bit Swizzling Chris <xxx.syseng.yyy@gfsys.co.uk> - 2020-09-06 17:48 +0100
  Re: Bit swizzling Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-05 20:15 +0000
  Re: Bit swizzling "davidl...@gmail.com" <davidlovemore@gmail.com> - 2020-09-06 00:31 -0700
  Re: Bit swizzling Martin Ward <martin@gkc.org.uk> - 2020-09-07 12:08 +0100
    Re: Bit swizzling Tom Crick <tomcrick@gmail.com> - 2020-09-08 09:35 +0100
  Re: Bit swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-07 10:55 -0400
    Re: Bit swizzling Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-09-08 01:45 +0200
  Re: Bit swizzling gah4 <gah4@u.washington.edu> - 2020-09-10 10:34 -0700
    Re: Bit swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-10 17:13 -0400

csiph-web