Esotope-BFC Comparison

This page is a draft of “Comparison” page that will be later posted in the project wiki. Also note that this survey is slightly outdated: for example, LLVM was able to generate a comparative code without the knowledge of Brainfuck at all.

The following list is the comparison of various Brainfuck compilers and optimizers. The implementation listed later provides more advanced optimization compared to the former. I also made some section to describe certain class of optimization.

No optimization at all

This class of optimizer doesn’t do any attempt to optimization.

C code generation:

Other code generation:

Binary generation:

Compression of consecutive commands

This class of optimizer is so far very popular, given the fact that Brainfuck program contains lots of duplicated commands. It should convert +++++[->+++++++<] to something like 5+[->7+<]. It might not be capable to convert >>><<< into no-op, though.

Interpreter:

Binary generation:

Multi-target compiler:

Special casing for cell copy or clear

Another effective optimization is to recognize common idiom: [-] (or [+] if wrapping is allowed) sets the current cell to zero, [>+<-] (or [<<<+>>>-] etc.) copies the current cell to other cell with destructing (i.e. setting to zero) the current cell.

C code generation:

Simple loop detection

Simple loop is defined as a loop with the following constraints:

  1. It only has a memory operations: +, -, < and >. Sometimes other simple loop can be recognized inside it.
  2. After the loop body is executed, the memory pointer remains same.
  3. The loop body alters the target (normally the “current”) cell by 1 or -1.

Simple loop is very common, as it is used to implement constant multiplication. [-] is also a simple loop, so the optimizer doesn’t have to need to special-case it.

Interpreter:

Pointer propagation

This class of optimizer flattens out the pointer operation < and > as much as possible. For example, >++++>>>>>--<<<<++>->>+++ may be represented as 1:+4, 2:+2, 3:-1, 5:+3, 6:-2 with final pointer adjustment by 5. This optimization is quite necessary to enable other optimizations.

Multi-target compiler:

Advanced loop optimization

This class of optimizer recognizes broader range of loops, outlined below:

  1. If loop, which sets the target cell to zero inside it, thus only get executed at most one time.
  2. Repeat loop, whose repeat count is fixed but cannot be flattened. Some complex multiplication loop uses nested loop and cannot be classified as simple.
  3. Almost-simple loop, which is simple except that the target cell is altered by constant but not -1 nor 1. Some almost-simple loop results in the infinite loop (e.g. +[--]), and optimizer should insert some check for it.
  4. Seek loop, whose body moves the pointer by fixed amount. Most common one is [>] or [<], and they can be replaced by memchr library function in C, for example.

It doesn’t need to support all of them, but this list is roughtly sorted by importance so it should optimize at least if loop. Note that optimizing almost-simple loop involves some mathematical (number-theoretic) calculations. :p

C code generation:

State-of-the-art optimization

Here I included the most advanced optimizer I have ever seen. Note that I’m using state-of-the-art in the sense of Brainfuck optimization: in my opinion, almost every Brainfuck compiler even doesn’t attempt the basic principle of compiler construction. So this measure is quite relative.

C code generation:

메아리 뇌

ikiwiki를 씁니다.
마지막 수정
저작권자 © 1999–2011 강 성훈. 저작권을 약간 가집니다.