|Scitoshi Nakayobro 79470e1e3d Improve optimizations||2 weeks ago|
|.idea||1 month ago|
|src||2 weeks ago|
|test||1 month ago|
|.gitignore||1 month ago|
|LICENSE||1 month ago|
|README.md||1 month ago|
|bfc.iml||1 month ago|
|compile||1 month ago|
|run||1 month ago|
bfc is an optimizing Brainfuck to C compiler.
The compiler uses the a linear IR consisting of instructions of the following types:
Adjust :: + or - Select :: > or < Read :: , Write :: . Open :: [ Close :: ] Set :: generated by optimizations MAdd :: generated by optimizations ScanLeft :: [<] ScanRight :: [>]
The compiler parses Brainfuck code into the following instructions:
Adjust Select Read Write Open Close
The rest are generated from the input IR by various optimizations.
This optimization essentially performs “run-length encoding” on ‘Adjust’ instructions (
-). For example:
This optimization turns loops of the following form:
into a single instruction:
This optimization acts on two specific instances of loops:
[<]. The optimization generates code that uses
memrchr respectively. On Windows,
memrchr is not supported so
[<] just turns into a regular scan loop.
This optimization acts on balanced loops (loops in which the data pointer ends where it began) that only contain adjust and select (
<) instructions. It extracts ‘multiply and add’ (MADD) operations from the loop and generates individual instructions for them.
[ - > +++ > ++ << ]
madd  3 madd  2 set 0
Notice that this optimization only occurs if the loop decrements its condition cell by one.
This optimization simply removes adjust operations which occur directly before set operations as they are entirely redundant. For example:
adjust 5 set 0
This optimization turns multiple adjacent set instructions into a single set instruction, namely, the last one; the preceeding ones are redundant. For example:
set 0 set 5
This optimization detects adjust instructions that occur directly after set instructions and combine them into a single set instruction. For example:
set 0 adjust 5
This optimization removes adjust and select instructions whose value is zero. For example:
adjust 0 select 0
Would turn into nothing.
This optimization removes set or adjust instructions that occur directly before a read instruction as the read will overwrite them. For example:
adjust 5 read
This optimization calculates data pointer offsets for certain instructions by counting the preceeding select instructions and adds those offsets to the instructions, allowing the select instructions to be eliminated. This is best explained visually:
adjust 3 select 5 adjust -2 select 2 set 0 select -1 read open ... close
adjust  3 adjust  -2 set  0 read  select 6 open ... close