gir/optimizations.md

Gir has five optimization passes.

joinAdjacentOps

• consumes: commands without offsets
• produces: commands without offsets
• unknown commands: passed through unmodified
• acts on: moveHead, add
• other known commands: loop (recurses)

joinAdjacentOps joins adjacent moveHeads and adds together. Normally parse joins runs of <> or +- into one command, but if the runs are interrupted by another character two commands get generated. moveHeads are joined first, before the pass goes over the generated commands again and joins adds.

transformClearLoops

• consumes: commands without offsets
• produces: commands without offsets
• unknown commands: passed through unmodified
• acts on: loop with one command, which is add 1 or add -1
• other known commands: loop (recurses)

transformClearLoops changes loops of the form [-] or [+] into a single clear command.

addOffsetProperties

• consumes: commands without offsets
• produces: commands with offsets
• unknown commands: raise UnknownIRError
• acts on: moveHead, add, clear, writeByte, readByte, loop

addOffsetProperties adds an offset property to add, clear, writeByte, and readByte. The offset tells the offset at which from the current tape head location the operations are performed. It also adds an isBalanced property to loops. This property tells if execution of loop body ends at the same cell where it began, which is useful for performing further optimizations.

transformMultiplyLoops

• consumed: commands with offsets
• unknown commands: passed through unmodified
• acts on: balanced loops that only have adds and where adds at offset 0 are together 1 or -1
• other known commands: loop (recurses)

transformMultiplyLoops changes loops of the form [>+>++<<-] into a single multiply command.

flattenLoops

• consumes: commands with offsets
• produces: flattened array commands with offsets
• unknown commands: passed through unmodified
• acts on: loop

flattenLoops changes the nested structure where loop commands have a content property with the loop body inside to a flat structure with jumpIfZero and jumpIfNonZero.