satgo1546​/​satisfied

32位，小端序。

寄存器

寄存器0～3只能作为源寄存器使用；标志寄存器不能作为源寄存器或目标寄存器直接使用。

指令编码

跳转类指令的偏移量皆是相对于之后一条指令，故十六进制编码为71 00000000的指令相当于什么都没做，而61 FE则为死循环。

指令集

条件码

常见问题

• SETcc R → MOV R, 0; CMOVcc R, 1
• ZXT8 R → AND R, 0xFF
• ZXT16 R → AND R, 0xFFFF
• RCL R → ADC R, R
• NEG R → RSUB R, 0
• NOT R → XOR R, −1
• INC R → ADD R, 1
• DEC R → SUB R, 1

原理

• 静态单赋值数据流。
  • 众人尽知LLVM之功成名就，细看发觉其bitcode版本可谓三日一minor，五日一major，迭代速度恐怖如斯。个人开发者岂有这空闲，可次次投入跟进LLVM毫无保留的更新中？故试取之精也。今有Go因其神而弃其形，自组SSA优化后端，其理类同。
• 结构化控制流。静态单赋值与控制流图并非天生一对。高阶结构无控制流图之纷繁复杂，且仍可偷得些许跳转自由。
  • 条件分支连带其后紧随的合并块，与来路关联的φ函数插入于此。
  • 只有当型循环。循环条件是条件分支。φ函数插入于循环体开头。
  • 鲜见直到型循环；即便如此，大可改写为无限循环和跳出语句。无限循环改写为当型循环，循环体全部塞入条件，配以条件分支跳过预定跳出后不必再执行的语句。
• 操作码贴近常见硬件，直译为佳；不必最简，OpSubtractBranchIfNonzero少有实现。
• 指令集合为单链表，数据结构比双链表更干净，手操也不会吃力。既然没有删除某处use的需要，便无需双向链表。
• 参考资料。
  • Ron Cytron、Jeanne Ferrante、Barry K. Rosen、Mark N. Wegman、F. Kenneth Zadeck等人于1991年提出了高效转换任意流程图到静态单赋值形式的算法，Efficiently computing static single assignment form and the control dependence graph这篇论文也成为了SSA宇宙的中心。不过，这并不是针对开发新式编程语言的最佳建议，因为……
  • Marc M. Brandis和Hanspeter Mössenböck于1994年在ACM Transactions on Programming Languages and Systems上发表的论文Single-pass generation of static single-assignment form for structured languages指出，如果源程序只含有if ~ else、while、repeat ~ until这三种控制结构，而没有goto、break、return的话，要生成静态单赋值形式就是小菜一碟，不必用Cytron等人的那套经典三遍的方法大费周章。该文章中虽也有应对break和return的方法，但比较复杂。
  • Marc M. Brandis于1995年递交的百来页的科技博士学位论文Optimizing compilers for structured programming languages中以PowerPC目标架构和Oberon编程语言为例，概略解说了一例完整的优化编译器的实现原理。在总览比较各种已有中间表示形式后，该编译器选用了卫式单赋值形式，使各种优化得以轻松实施。satisfied所用中间表示很大程度上是受了此文的启发，关于break和return语句的处理也应用了其中的方法。
  • Jeffery von Ronne、Ning Wang、Michael Franz在2004年的报告Interpreting programs in static single assignment form中用很烂很暴力的方法直接运行静态单赋值指令序列。运行φ函数的方法跟常规编译时差不多，不过为了保持φ函数的位置不变，仅在前驱基本块尾部添加一个寄存器赋值指令，以便在φ函数处判断该选哪个参数。satisfied最初的目标代码生成阶段使用了类似的思路。

常见问题

• do { S; } while (C); → while ({ S; }, C);
• break; S; → _break = 1; if (!_break) { S; }

原理

自JSON直接读入树结构，内存表示同样无环，故引用定义不以指针，而是凭借整数标识符和相对层级。为免去JSON不允许尾随逗号之烦，不用行末逗号，而用行首逗号。缩进干扰版本控制系统的判断，故也不缩进。一段简短的程序写作JSON看起来甚至比S-表达式都长太多，其实只是常用算术记号太精简带来的错觉。

编译器的Go实现使用内置的JSON库直接解析到对象。参数列表对应切片（语言中的标准列表类型），最是方便。若要以其他语言实现，也请活用内置JSON库的惯例。

常见问题

• { S1; S2; } → arglast(S1, S2);