Path: csiph.com!goblin3!goblin.stu.neva.ru!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Martin Ward Newsgroups: comp.compilers Subject: Re: Bit swizzling Date: Mon, 7 Sep 2020 12:08:23 +0100 Organization: Compilers Central Lines: 38 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <20-09-020@comp.compilers> References: <20-09-014@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit 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 X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com In-Reply-To: <20-09-014@comp.compilers> Content-Language: en-GB Xref: csiph.com comp.compilers:2591 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