RednaxelaFX对《ふつうのコンパイラをつくろう》的笔记(4)

这本书的主题是描述是整个编译和执行的流程，所以并没有实现多少复杂的优化，而只实现了两个非常简单的局部优化：表达式简化（algebraic simplification）和强度降低（strength reduction）。 本来作者还打算实现常量折叠（constant folding），但受篇幅所限只好割舍了。其实常量折叠实现起来也超简单啦，可能只是书的篇幅不够写了而已⋯但感觉2页就够说完了？

cbc IR不愧是继承自虎书的思路。 这个IR里只有两种节点可以有副作用，一个是Assign（对应虎书的MOVE），另一个是Call。 应对副作用的思路是：cbc会保持语句的顺序，所以副作用只要依附在语句上，顺序就能得到维持；而cbc不保证维持表达式的顺序，所以要杜绝在表达式里有副作用。 Assign是Stmt的子类，其在语句中的顺序自然得到cbc维持。 図11.2 提到，Call虽然是Expr的子类，但因为它有副作用，为了方便后续IR变换而对Call能合法出现的位置做了限制。只有以下两种可能合法： 1. ExprStmt(Call(...)): Call直接位于ExprStmt（对应虎书IR的EXP）的子节点位置；这是抛弃Call返回值的情况。 2. Assign(Addr Call(...)): Call位于Assign的子节点位置；这是保留Call返回值并赋值给一个（临时）变量的情况。 通过把Call直接挂在特定Stmt子类节点，Call能在IR里出现的顺序也就被固定下来，因而后续对IR的处理都不必再担心表达式求值顺序的问题——因为不会通过副作用反映出来。 这就直接跟虎书（ML版）第8章所述的Canonical Tree的形式一样：

这里cbc强调的是虎书Canonical Tree的第2点；至于第1点，cbc一开始就是用ArrayList<Stmt>来收集所有语句，绕开了先生成串起语句与表达式的ESEQ和串起表达式的SEQ。 但是cbc没把事情做到底。虎书第8章做了3件事情： 1. linearize：把第7章的IR转换为Canonical Trees 2. basicBlocks：把Canonical Trees按基本块分割，每个基本块除头尾之外不能有label或跳转； 3. traceSchedule：把CJUMP的false label对应的基本块调度到紧接在该CJUMP后面，以便在生成代码时用fallthrough方式减少冗余跳转。 而cbc只做了第一件，没有构造出基本块和控制流图。但话说回来，cbc一趟生成中间代码的顺序其实已经达到了虎书在traceSchedule之后的顺序，就差没把CJump的条件/目标反转利用fallthrough而已。所以硬要说的话应该是虎书写得太麻烦，本书更直观——我觉得两者的取舍在于：本书的做法利用了副作用（ArrayList.add()），直接把生成的IR收集到一个ArrayList<Stmt>里；而虎书则是分了多趟，先生成了纯粹的树，再按照一定规则把树扁平化收集到Tree.stm list里，不利用任何副作用。 关联到本书263页对控制流生成中间代码的地方：http://book.douban.com/annotation/34768487/ 以及433页对CJump生成最终代码的地方：http://book.douban.com/annotation/34768597/ 还有虎书（ML版）第8章第173页：http://book.douban.com/annotation/34768294/

这一节讲解了if、while、break的中间代码生成，但是却漏掉了对conditional expression的代码生成，感觉是个遗憾。 虎书（ML版）第7章里奇怪的exp类型很大程度上是迁就两种需求：表达式语句（忽略表达式的值，和条件表达式（名为表达式，但里面却嵌入了控制流语句）。

datatype exp = Ex of Tree.exp
             | Nx of Tree.stm
             | Cx of Temp.label * Temp.label -> Tree.stm

cbc对conditional expression的中间代码生成的实现在： https://github.com/aamine/cbc/blob/b9ad38ef165a1daeb0f0743a16def5e50e916a27/net/loveruby/cflat/compiler/IRGenerator.java#L424 可以看到，虽然它在上层语法中名为“表达式”，但实际在生成中间代码时却用了一系列语句节点。思路如下：

  if (condExpr) goto thenLabel else elseLabel
thenLabel:
  tmp = thenExpr
  goto endLabel
elseLabel:
  tmp = elseExpr
  goto endLabel // not using fallthough here, should improve
endLabel:
  ...

（当然要留意这里condExpr、thenExpr、elseExpr里也都可能有“条件表达式”，因而里面也可能嵌有控制流） 对比cbc对if-then-else的中间代码生成： https://github.com/aamine/cbc/blob/b9ad38ef165a1daeb0f0743a16def5e50e916a27/net/loveruby/cflat/compiler/IRGenerator.java#L196

  if (condExpr) goto thenLabel else elseLabel
thenLabel:
  thenBody
  goto endLabel
elseLabel:
  elseBody
  // using fallthough here
endLabel:
  ...

Hmm⋯ 不使用fallthrough的好处很明显：如果有控制流方面的处理/优化，那没有falltrough而用显式jump来结束基本块的话就可以很方便的重新调度基本块；而用了fallthrough的话，基本块挪动起来就有点麻烦。 结论是还在高层IR准备做优化的时候应该构造显式CFG，不用fallthrough；而在低层IR准备生成最终代码时应该尽量使用fallthrough。 cbc的IR身兼高层和低层IR之任，既然接下来没啥优化直接生成机器码，应该还是用fallthrough好。 但话说回来，如果想给cbc添加优化的话，条件表达式只能翻译为CJump而不让Bin能处理and/or逻辑运算表达式，感觉很不好⋯IR的抽象层次太低了。 或许应该给Bin添加and/or operator的支持，然后让它们在codegen之前lower成CJump，在lower之前做些优化尝试把条件合并啥的。

这里关注一下从中间代码CJump生成最终代码的地方： https://github.com/aamine/cbc/blob/b9ad38ef165a1daeb0f0743a16def5e50e916a27/net/loveruby/cflat/sysdep/x86/CodeGenerator.java#L700

    public Void visit(CJump node) {
        compile(node.cond());
        testCond(node.cond().type(), ax());
        as.jnz(node.thenLabel());
        as.jmp(node.elseLabel());
        return null;
    }

也就是说，CJump语句节点会生成出下述模式的代码：

  condExpr // result in ax
  test ax, ax // in corresponding type
  jnz thenLabel
  jmp elseLabel
thenLabel:
  ...
  jmp endLabel
elseLabel:
  ...
  // jmp endLabel // optimized away by peephole
endLabel:
  // ...

留意到else分支的最后、endLabel之前，我在注释里写了一句jmp endLabel并表明它被优化掉了。优化掉它的逻辑在cbc里的： https://github.com/aamine/cbc/blob/b9ad38ef165a1daeb0f0743a16def5e50e916a27/net/loveruby/cflat/sysdep/x86/PeepholeOptimizer.java#L271

        /**
         * Returns true if jmpDest is found in asms before any instruction
         * or directives.  For example, this method returns true if contents
         * of asms are:
         *
         *    if_end3:
         *          # comment
         *    jmpDest:
         *          mov
         *          mov
         *          add
         */
        private boolean doesLabelFollows(Cursor<Assembly> asms, Symbol jmpDest) {
            while (asms.hasNext()) {
                Assembly asm = asms.next();
                if (asm.isLabel()) {
                    Label label = (Label)asm;
                    if (label.symbol().equals(jmpDest)) {
                        return true;
                    }
                    else {
                        continue;
                    }
                }
                else if (asm.isComment()) {
                    continue;
                }
                else {
                    // instructions or directives
                    return false;
                }
            }
            return false;
        }

但是这个优化却无法处理thenLabel之前的jnz thenLabel与jmp elseLabel，因为jnz thenLabel与thenLabel之间隔着一条指令。这里更好的代码生成方式是把判断条件反转并使用fallthrough：

  condExpr // result in ax
  test ax, ax // in corresponding type
  je elseLabel // inversed condition
  // else fallthrough
thenLabel:
  ...
  jmp endLabel
elseLabel:
  ...
  // jmp endLabel // optimized away by peephole
endLabel:
  // ...