针对LLVM的RISCV后端的的codesize优化 (BLT to BLEZ)

毕设做的部分工作，整理一下。

针对 LLVM 的 RISCV 后端的 codesize 优化 (BLT to BLEZ)。

案例：

int test_func(int aa, int bb,int cc){
  int jk = 7;
  if(aa > 0 && bb > 0 && cc > 0){
    jk = jk+ 20;
  }
  else{
    jk = jk+4396;
  }
  return jk;
}

使用 clang 编译生成的汇编代码：

test_func:
        addi    a3, zero, 1
        blt     a0, a3, .LBB0_4
        blt     a1, a3, .LBB0_4
        addi    a0, zero, 27
        blez    a2, .LBB0_4
        ret
.LBB0_4:
        lui     a0, 1
        addi    a0, a0, 307
        ret

而 GCC 生成的汇编代码：

test_func:
        ble     a0,zero,.L5
        ble     a1,zero,.L5
        ble     a2,zero,.L5
        li      a0,27
        ret
.L5:
        li      a0,4096
        addi    a0,a0,307
        ret

能否对 LLVM 后端进行优化，使其能像 GCC 一样，生成 BLEZ 的指令，减少汇编代码？

LLVM 后端知识

在进行 clang 的 Code Size 优化前，必须了解到 clang 是作为 llvm 的前端使用的，它完成前端语法分析工作以及抽象语法树的生成，然后生成中间代码，由 llvm 后端开始对中间代码进行优化。我们对 Clang 进行优化也在后端进行优化。而 llvm 的后端工作是非常多的，它包括一系列的流程优化、指令选择、指令调度、寄存器分配、以及代码导出等。

从图中我们可以看到 llvm 后端的主要工作就是流程优化以及代码导出，在代码导出前需要进行若干次优化。llvm 后端得到的 LLVM IR 为中间代码，这个中间代码直接由源代码转换而来，与具体的目标架构无关。最初的中间代码经过一些的流程优化之后便进入指令选择阶段，在此阶段会将优化过后的 IR 经过 SelectionDAGBuilder 转换成 SelectionDAG 节点，即将 IR 中的三地址结构转换成有向无环图，基本上转换后 IR 中一个基本块对应一个独立的 DAG 图。而 DAG 中的每个节点则对应一条指令，而 DAG 图中节点间的方向线则表示指令之间的依赖关系。将所有 IR 转换成 DAG 图之后，在指令选择阶段还会进行若干次 Combine 操作以及 Legalize 操作，从而将某些指令合并起来，我们之后将会在案例中对此进行分析。

在指令选择阶段之后，得到的 DAG 图信息保存在 SelectionDAG 类中，llvm 后端从中可以得到应该使用那些目标指令来执行每个 IR 块的计算，但是 DAG 图中没有包含某个图中没有依赖关系的指令间的顺序，所以需要进行指令调度操作。在指令调度阶段，将会尽可能地优化指令级的并行度，以及对指令的执行顺序进行排序，并且将 DAG 节点中的指令转换成 MachineInstr 三地址形式。

在转换成 MachineInstr 三地址形式之后将会进行寄存器分配。在 IR 以及 DAG 图中，所有的指令都存在虚拟的 “无限寄存器” 中，但是实际上任何机器上的寄存器都是有限的，所以需要进行寄存器分配将指令中的寄存器映射到机器实际上的有限寄存器当中。当程序代码特别大所需寄存器超出目标机器寄存器上限时会产生溢出，这时将会引入堆栈。

在寄存器分配阶段之后会进行第二次指令调度，此时目标机器的寄存器信息已知，编译器可以根据具体的资源竞争关系以及不同指令前后执行顺序对源程序进行进一步的代码质量提升。

后端的最后一步就是代码输出阶段。它将会把得到 MachineInstr 指令转换成目标相关的具体的 MCInstr 实例。这种实例将适用于汇编器和链接器，可以根据用户需要输出最终的汇编代码或者二进制的目标代码。

在这后端的每一步都有可能对最终汇编代码的 Code Size 产生影响，但是具体的问题需要具体分析，在进行 Code Size 必须对 llvm 后端足够了解，在产生问题时能够立马分析出是在哪个阶段出现的问题。我们将对前面提到的案例结果进行分析，并尝试进行优化。

案例分析

从双方的汇编代码结果来看，clang 的编译结果比 gcc 多了一行立即数 1 的引用指令，正是因为这条指令的产生，从而影响了接下来的三个判断，所以我们必须分析产生立即数 1 的原因。

我们先从后端的指令选择阶段开始分析。在指令选择阶段，所有的 IR 都将转换成 DAG 图，我们可以使用 llvm 的工具将此阶段的 DAG 图导出，导出 DAG 图的阶段选择在指令选择中的第一次 combine 之前和之后，导出命令：

./llc -march=riscv32 -mattr=+m ./test.ll -view-dag-combine1-dags
dot /tmp/dag.test_func-e3ff26.dot -Tpng -o ./a.png

执行该命令后我们将得到 -view-dag-combine1-dags 操作之前的 SelectionDAG 图，从 combine 操作之前的 DAG 图我们可以看到，在此时判断条件还依然是 setgt（大于），即大于 0 判断，在此阶段并没有问题，与源码一致，但是请注意那个 -1 节点。接着我们继续导出 DAG 图，导出的阶段为类型合法化前。

./llc -march=riscv32 -mattr=+m ./test.ll -view-legalize-types-dags
dot /tmp/dag.test_func-e3ff26.dot -Tpng -o ./a.png

执行该命令之后我们将得到该程序代码在类型合法化之前的 SelectionDAG 图。从合法化之前导出的 DAG 看，setgt（大于） 节点已经换成了 setlt（小于） 节点，并且 - 1 节点已经消失，立即数 0 节点也被换成了立即数 1 节点，即从合并前大于 0 操作在合并之后已经被换成了小于 1 操作。请注意在 combine 之前的 DAG 图中，出现的 -1 节点，它为亦或操作 xor 的依赖， xor 的另一个依赖为 setcc 节点，而该节点的的操作为 setgt（大于），即大于 0 操作，所以将 setcc 节点和 -1 进行 xor 操作之后，setgt（大于） 操作变成了 setlt（小于） 操作，而同时立即数 0 节点消失，立即数 1 节点引入。那么，为什么会引入立即数 1？

从导出的 DAG 图我们可以知道，combine 之前节点并没有变化，而 combine 之后 setcc 的节点发生了变化，所以我们可以判断出，在 combine 阶段发生了目标代码的变化。我们可以使用调试工作在运行阶段通过实时输出 DAG 图的方式得到 DAG 的变化过程。

对于该案例在 combine 之前调试得到的 DAG 节点：

某次节点合并之后 DAG 节点图的变化：

我们可以从两次 DAG 图中的变化中看到此时 setgt（大于） 已经换成了 setle（小于等于）。

然后经过第二次合并操作

已经将 setle（小于等于） 换成了 setlt（小于）, 并引入了立即数 1。

于是，我们找到了问题出现的阶段，在该节点寻找 clang 编译器的源代码，最终在 TargetLowering.cpp 文件中发现了关于此类问题的 “优化算法”：

Clang 的优化算法：TargetLowering.cpp line:3466 SimplifySetCC ()

//line 3905
if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
  // X <= MAX --> true
  if (C1 == MaxVal)
    return DAG.getBoolConstant(true, dl, VT, OpVT);

  // X <= C0 --> X < (C0 + 1)
  if (!VT.isVector()) { // TODO: Support this for vectors.
    APInt C = C1 + 1;
    ISD::CondCode NewCC = (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT;
    if ((DCI.isBeforeLegalizeOps() ||
         isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
        (!N1C->isOpaque() || (C.getBitWidth() <= 64 &&
                              isLegalICmpImmediate(C.getSExtValue())))) {
      return DAG.getSetCC(dl, VT, N0,
                          DAG.getConstant(C, dl, N1.getValueType()),
                          NewCC);
    }
  }
}

通过源码释义我们可以了解到，该代码的作用为对于所有简单判断，即 X<= C0 操作编译器都会将其 “优化” 成 X < (C0+1) 操作。那么，对于此类问题，我们该如何对编译器进行优化呢？

基于目标相关代码的优化

根据这种针对 setcc 节点的简单判断优化，我们可以在目标相关的后端代码中找到 setcc 相关的节点并进行修改：RISCVISelLowering.cpp: PerformDAGCombine ()

// line 2245
case ISD::SETCC: {
    // (setcc X, 1, setne) -> (setcc X, 0, seteq) if we can prove X is 0/1.
    // Comparing with 0 may allow us to fold into bnez/beqz.
    SDValue LHS = N->getOperand(0);
    SDValue RHS = N->getOperand(1);
    if (LHS.getValueType().isScalableVector())
      break;
    auto CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
    APInt Mask = APInt::getBitsSetFrom(LHS.getValueSizeInBits(), 1);
    if (isOneConstant(RHS) && ISD::isIntEqualitySetCC(CC) &&
        DAG.MaskedValueIsZero(LHS, Mask)) {
      SDLoc DL(N);
      SDValue Zero = DAG.getConstant(0, DL, LHS.getValueType());
      CC = ISD::getSetCCInverse(CC, LHS.getValueType());
      return DAG.getSetCC(DL, N->getValueType(0), LHS, Zero, CC);
    }
    // (setcc X, 1, setlt/setgt) -> (setcc X, 0, setle/setge) if we can prove X is 0/1.
    // Comparing with 0 may allow us to fold into blez/bgez.
    if ((ISD::isSignedIntSetCC(CC) || ISD::isUnsignedIntSetCC(CC)) && isOneConstant(RHS)){
      if (CC == ISD::SETGE || CC == ISD::SETUGE || CC == ISD::SETLE || CC == ISD::SETULE)
        break;
      unsigned OperationCC = CC;
      SDLoc DL(N);
      SDValue Zero = DAG.getConstant(0, DL, LHS.getValueType());
      OperationCC ^= 1; 
      CC = ISD::CondCode(OperationCC);
      //CC = ISD::getSetCCInverse(CC, LHS.getValueType());
      return DAG.getSetCC(DL, N->getValueType(0), LHS, Zero, CC);
    }
    break;
}

代码作用是在生成后端相关指令时便对目标相关的 setcc 节点进行优化。当我们遇到 setlt（小于） 或者 setgt（大于） 操作并且该操作的操作数为立即数 1 时，我们对其进行条件判断，当条件满足时我们可以进行优化，使 setlt （小于）或者 setgt（大于） 操作替换成 setle（小于等于） 或者 setge（大于等于） 操作。

基于目标无关代码的优化

目标无关的方式为在进行 DAG 节点 combine 之前，我们阻止其 setge 或者 setle 节点对 setgt (大于) 或者 setlt（小于） 节点的转换，该转换的代码在 DAGCombiner.cpp：combine () 中，我们可以对其添加如下代码：DAGCombiner.cpp : 1744 combine ()

SDValue DAGCombiner::combine(SDNode *N) {
  SDValue RV;
  DisableGenericCombines =false;
  bool targetIsRISCV = false;
  bool optLevelIsDefault = false;
  const char* targetStr = DAG.getSubtarget().getTargetTriple().getTriple().c_str();
  if (strncmp("riscv",targetStr,5)==0)
    targetIsRISCV = true;
  if (OptLevel == CodeGenOpt::Default)
    optLevelIsDefault = true;
  if (targetIsRISCV && optLevelIsDefault){
    if (N->getOpcode() == ISD::SETCC){
      auto CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
      if ((CC == ISD::SETGE || CC == ISD::SETUGE || CC == ISD::SETLE || CC == ISD::SETULE) && isNullFPConstant(N->getOperand(1))){
        DisableGenericCombines = true;
      }
    }
  }
  ...
}

该代码的作用是遇到对常量 0 的大于或者小于判定的 SETCC 节点时，阻止其节点进行 Combine 操作，并判断后端是否为 RISCV。

效果

优化前生成的汇编代码

test_func:
        addi    a3, zero, 1
        blt     a0, a3, .LBB0_4
        blt     a1, a3, .LBB0_4
        addi    a0, zero, 27
        blez    a2, .LBB0_4
        ret
.LBB0_4:
        lui     a0, 1
        addi    a0, a0, 307
        ret

优化后生成的汇编代码

test_func:
        blez    a0, .LBB0_4
        blez    a1, .LBB0_4
        addi    a0, zero, 27
        blez    a2, .LBB0_4
        ret
.LBB0_4:
        lui     a0, 1
        addi    a0, a0, 307
        ret

可以看到优化后已经能够生成 blez 的指令，并且常量 1 的汇编代码也没有再生成。