Optimize brainfuck output

[sunjay]

We want to generate the smallest brainfuck files possible while still using as few brainfuck cells as possible. Less instructions is a greater priority than memory efficiency since brainfuck doesn't use that much memory to begin with. That being said, memory is still important and must be taken into account.

• [ ] Make optimization a pure operation Instructions -> Instructions and write tests
• [ ] Make optimization level a command line argument
• [x] Cancel out opposite operations with no other instruction between them (cancel out opposing >< or <> and opposing +- or -+)
• [ ] Remove any instructions on cells that never get written out or get overwritten by reads (especially at the end of the instructions)
  • At the end, you can safely remove any ><+- instructions since these have no consequences at the end of the program
  • Dead code removal
  • Example: ++++++++++++++, is completely useless since , overwrites all the +
• [ ] Modify the order in which cells are modified in order to avoid unnecessary movement instructions (e.g. when copying)
• [ ] Use allocated cells as temporary cells when copying string
  • Example: Let's say you want to copy "hello". The memory might look like [h][e][l][l][o][ ][ ][ ][ ][ ][ ] where you have the original cells for "hello", enough cells for the copy and a temporary space to use during the copy to keep the original letter. Instead of using a temporary cell at the very end, you can use the adjacent spot to the letter you are copying. So if you were copying "h" into its destination cell, instead of using the temporary cell allocated at the very end, you could use the space for "o". That cell would automatically be cleared at the end of the copy so this is a safe operation. This saves a lot of instructions going back and forth over completely empty cells and will produce even higher savings when the cells to copy aren't right next to each other on the tape. Note: You still need an empty temporary cell at the end for the last character.
• [ ] Interlacing: Instead of ,>,>,>,<<<.>.>.>., we can probably do ,.>,.>,.>,. (needs thought on the consequences of this since it might not be 100% safe)
• [ ] Replace long strings of repeated instructions with loops
• [ ] Loop fusion
• [ ] Expanded output mode of compilation - add a mode to the compiler that explicitly outputs large amounts of repeated instructions instead of rolling those into loops using temporary cells. This saved on memory while potentially making the binary huge. The real reason for introducing this however is because long strings of the same instruction are easier to optimize and more decidable than loops which can only be unrolled in the simplest of cases.

Resources:

• http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html

[sunjay]

The basic scaffolding for optimizations has been implemented. More optimizations will be added as time goes on and more features are added to the language. This issues tracks the progress of that work and other future optimizations as well.