autoperm

autoperm 是一个生成应用 栈效应图 的程序的工具。生成结果具有最少的 MOV* 指令数。该算法基于 Tarjan 强连通分量算法。

该库与后端无关。提供了一个 brainfuck 后端。将crate作为二进制安装后，可以通过 autoperm 命令访问该 brainfuck 后端。

* MOV 清除特定内存地址中的数据并将其写入其他单元的列表

最终我会创建一份正式的说明，但现在这里是我的快速 说明。

安装

cargo install autoperm

用法

$ autoperm a b -- b a
[->+<]<[->+<]>>[-<<+>>]<

$ autoperm
a b c -- c a b
[->+<]<[->+<]<[->+<]>>>[-<<<+>>>]<

a -- a a a a
[->>>>+<<<<]>>>>[-<+<+<+<+>>>>]<

a b c d -- d c a b
[->+<]<<[->>+<<]>[-<+>]<<[->>+<<]>>>>[-<<<<+>>>>]<

a b c -- c
<<[-]>[-]>[-<<+>>]<<

a b c d e f -- c d d f e e b
<<<<<[-]>[->>>>>+<<<<<]>[-<<+>>]>[-<+<+>>]>>[-<<+>>]<[->>>+<<<]>>>[-<<+<+>>>]<

该程序假定内存指针指向栈顶。任何新的单元应该为空，并且必须在栈顶有1个空闲单元用于临时存储。

例如

(a b c -- c)
start must be:
  a  b *c  0 // a and b are cleared
<<[-]>[-]>[-<<+>>]<<
end:
 *c  0  0  0

(a -- a a a a)
start must be:
  a  0  0  0  0 // note: no 0s are initialized before usage
[->>>>+<<<<]>>>>[-<+<+<+<+>>>>]<
end:
  a  a  a *a  0

(a b -- a b a b) 的遍历

a b -- a b a b
<[->>>>+<<<<]>>>>[-<<+<<+>>>>]<<<[->>>+<<<]>>>[-<+<<+>>>]<

# the tape
 0 *1  2  3  T 
 a  b  0  0  0

<[->>>>+<<<<]      0 → {T}
*0  1  2  3  T 
 0  b  0  0  a

>>>>[-<<+<<+>>>>]  T → {2 0}
 0  1  2  3 *T 
 a  b  a  0  0

<<<[->>>+<<<]      1 → {T}
 0 *1  2  3  T 
 a  0  a  0  b

>>>[-<+<<+>>>]     T → {1 3}
 0  1  2  3 *T 
 a  b  a  b  0

< 
 0  1  2 *3  T 
 a  b  a  b  0