brainoxide 0.1.2

An optimizing Brainfuck compiler/interpreter
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

# BrainOxide

[ [On crates.io](https://crates.io/crates/brainoxide) ]

An optimizing [Brainfuck] interpreter/compiler-to-C in Rust.

Made as a project to learn Rust. Code is for sure not idiomatic and quite messy
in places.

Features:

* [Optimisation](#optimisations)
* Fuzz tested
* Regression test suite
* Two backend modes: interpret or generate C code

## Why?

Does the world need yet another BF implementation? Not really. Did I have fun
making it, and did I learn things? Yes.

## Optimisations

BrainOxide performs the following optimisations:

* Instruction merging
* Loop lowering: while → if, while → equations / set
* Constant folding
* IO operation merging: Merges constant outputs into a single byte array output.
* Dead store elimination
* Peephole optimisation: `[>]`, `[>>]`, ... → various seeks

BrainOxide internally differentiates between balanced and unbalanced code
sections. This refers to the amount of `>` vs `<`. In a balanced code sections
we know all offsets, and are thus able to optimise better. In unbalanced
sections we have very limited abilities to optimise.

For balanced code sections BrainOxide builds a directed acyclic graph (DAG) and
performs the optimisation on the DAG.

### Optimisation wish list

* Partial evaluation until first input instruction:

  This could potentially constant fold large programs into a single `fputs()` call.
  It would have to be opt-in. Additionally, it only makes sense for code gen mode.

* Better equation handling:

  Right now the lowering of loops into equations is fairly
  limited and simplistic. The code cannot lower loops already containing equations for
  example, and only a loop index stride of `-1` is supported.

* Loop/If unrolling:

  Unroll loops when we know the iteration count statically, if it makes sense.
  A heuristic would be needed.

## Code stability

This code base does not have a stable API. It is not meant to be used
as a library. The command line flags are not stable either, as there
are some changes I'd like to make to allow more flexible logging options.

This software has only been tested on an up-to-date install of Arch Linux x86-64.
If it happens to work on non-Linux, that is a happy accident.

## Minimum supported rust version (MSRV)

YMMV. It works on rustc 1.67.0 as of writing. It should continue working on
the latest stable Rust (except fuzz testing that needs nightly). I will not
test on older versions than whatever happens to be the latest stable when I
make a change.

So in summary: There is no MSRV policy.

## License

BrainOxide is released under GPL 3.0 (only, not "or later").

[Brainfuck]: https://en.wikipedia.org/wiki/Brainfuck