怪文書 #25233.md

用語定義

• セル: + 及び - で値を操作することができるもの。
• 番地: < 及び > で前後させることができるもの。
• 再帰的に適用可能: 最適化Aを適用したとしてもなお、最適化条件A' を満たすならば最適化A が適用できること。
• 時間次数を下げる: 線形時間を定数時間に短縮すること。より一般には、次数の高い時間を次数の低い時間に短縮すること。

最適化手法

一般適用

• +- | <> | -+ | ><: NOP
  • 組み合わせると互いに効果を打ち消し合う命令をなかったコトにする。
  • この規則は再帰的に適用可能である。
• [] : ERROR | INFILOOP | NOP
  • コンパイラがセルの値が常に0であることを証明できる場合、NOP命令に置き換わる。
  • できない場合はコンパイルエラー、もしくは実行時に無限ループ。
• +-<>[].,以外の文字: NOP
  • 意味がない。
• プログラムの先頭にある[から対応する]まで: NOP
  • 実行時にすべてのセルは0で初期化されるので無意味。
  • この規則は再帰的に適用可能である。

イディオム

• [-]: LOADCONST 0
  • 時間次数を定数時間に下げられるので積極的に採用するべき。
• [-]++++: LOADCONST $pluscount
  • 線形時間から定数時間になるので積極的に採用するべき。
• [>+<-]: MOVE $offset
  • ここでコンパイラがセルの値が常に$minusの倍数であることを証明できる場合、MOVE命令に置き換わる。
    • 特に、$minusが1である場合は常に最適化できる。
• [>+++<-]: TIMES $offset, $rhs
  • ここでコンパイラがセルの値が常に$minusの倍数であることを証明できる場合、MOVE命令に置き換わる。
    • 特に、$minusが1である場合は常に最適化できる。
• [>]: RFINDZERO
  • コンパイラが確実にゼロであるセルを証明できる場合、そこへのIDX命令にできる。
  • そうでない場合は線形時間のループで探すしかない。
• [<]: LFINDZERO
  • コンパイラが確実にゼロであり、かつ非負の番地を持つセルがあることを証明できる場合、そこへのIDX命令にできる。
  • そうでない場合は線形時間のループで探すしかない。
• [>>]: RFINDZERO $modulo
  • コンパイラが確実にゼロであり、かつ番地が$moduloの倍数であり、かつ現在の番地よりも番地が大きいセルが証明できる場合、そこへのIDX命令にできる。
  • そうでない場合は線形時間のループで探すしかない。
• [<<]: LFINDZERO $modulo
  • コンパイラが確実にゼロであり、かつ番地が$moduloの倍数であり、かつ非負の番地、かつ現在の番地よりも番地が小さいセルが証明できる場合、そこへのIDX命令となる。
  • そうでない場合は線形時間のループで探すしかない。