Re: Bit swizzling

Martin Ward <>
Mon, 7 Sep 2020 12:08:23 +0100

          From comp.compilers

Related articles
Bit swizzling (Rick C. Hodgin) (2020-09-05)
Re: Bit swizzling (Hans-Peter Diettrich) (2020-09-05)
Re: Bit Swizzling (John Levine) (2020-09-05)
Re: Bit swizzling (Kaz Kylheku) (2020-09-05)
Re: Bit swizzling ( (2020-09-06)
Re: Bit Swizzling (Chris) (2020-09-06)
Re: Bit swizzling (Martin Ward) (2020-09-07)
Re: Bit swizzling (Rick C. Hodgin) (2020-09-07)
Re: Bit swizzling (Hans-Peter Diettrich) (2020-09-08)
Re: Bit swizzling (Tom Crick) (2020-09-08)
Re: Bit swizzling (gah4) (2020-09-10)
Re: Bit swizzling (Rick C. Hodgin) (2020-09-10)
| List of all articles for this month |

From: Martin Ward <>
Newsgroups: comp.compilers
Date: Mon, 7 Sep 2020 12:08:23 +0100
Organization: Compilers Central
References: 20-09-014
Injection-Info:; posting-host=""; logging-data="25796"; mail-complaints-to=""
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.

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

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!


Dr Martin Ward | Email: |
G.K.Chesterton site: | Erdos number: 4

Post a followup to this message

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