RISC-Vにおける32ビットよりも大きな定数の生成方法

ふと気になって、RISC-Vの32ビットよりも大きな定数の作り方を調べることにした。これはRISC-VのISAの話というよりもコンパイラの話だ。

例えば以下のようなプログラムをGCCでコンパイルするとどのように定数を生成するのかチェックしてみる。

• long_value.c

int long_value()
{
  long long_const = 0x0123456789abcdefULL;
  return 0;
}

riscv64-unknown-elf-gcc -c long_value.c -S -o -

long_value:
        lui     a5,%hi(.LC0)
        ld      a5,%lo(.LC0)(a5)
        addi    sp,sp,-16
        li      a0,0
        sd      a5,8(sp)
        addi    sp,sp,16
        jr      ra
        .size   long_value, .-long_value
        .section        .srodata.cst8,"aM",@progbits,8
        .align  3
.LC0:
        .dword  81985529216486895

ラベルとして定数を宣言してそこに配置してきた。ぬ、その手があったか。

これではつまらないのでもう少し見ていきたい。LLVMだとどうか。

./bin/clang -O3 long_value.c -c -target riscv64-unknown-elf -S -o -

long_value:                             # @long_value
# %bb.0:                                # %entry
        addi    sp, sp, -16
        lui     a0, 146
        addiw   a0, a0, -1493
        slli    a0, a0, 12
        addi    a0, a0, 965
        slli    a0, a0, 13
        addi    a0, a0, -1347
        slli    a0, a0, 12
        addi    a0, a0, -529
        sd      a0, 8(sp)
        mv      a0, zero
        addi    sp, sp, 16
        ret

なんだか摩訶不思議な命令が生成された。これを読み解いていくカギは、LLVMのRISC-V実装における定数生成アルゴリズムにある。

0x0123456789abcdefという64ビット数をレジスタに格納するために必要なことを考える。

1. 下位の12ビットと上位の50ビットを分割して考える。上位の50ビットを生成できれば、下位の12ビットはADDI命令を使って結合することで生成64ビット数を生成できる。
2. 上位の50ビットも下位の12ビットと上位の38ビットに分割して考える。上位の38ビットを生成できれば、12ビットシフトした後にADDI命令で下位の12ビットと結合して50ビットの値を生成できる。
3. これを繰り返す。つまり再帰的に上位から順に値を作ってはシフトして加算する。

この方式はRISC-V向けのRISCVISelDAGToDAGクラスを参考にした。

もしRV64向けに64ビットの定数を生成する場合はselectImm()にジャンプし、定数を手動で生成する。

• llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

void RISCVDAGToDAGISel::Select(SDNode *Node) {
  // If we have a custom node, we have already selected.
  if (Node->isMachineOpcode()) {
    LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << "\n");
    Node->setNodeId(-1);
    return;
  }
...
  switch (Opcode) {
  case ISD::Constant: {
    auto ConstNode = cast<ConstantSDNode>(Node);
    if (VT == XLenVT && ConstNode->isNullValue()) {
      SDValue New = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), SDLoc(Node),
                                           RISCV::X0, XLenVT);
      ReplaceNode(Node, New.getNode());
      return;
    }
    int64_t Imm = ConstNode->getSExtValue();
    if (XLenVT == MVT::i64) {
      ReplaceNode(Node, selectImm(CurDAG, SDLoc(Node), Imm, XLenVT));
      return;
    }
    break;
  }

selectImm()の実装は以下となる。

• llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

static SDNode *selectImm(SelectionDAG *CurDAG, const SDLoc &DL, int64_t Imm,
                         MVT XLenVT) {
  RISCVMatInt::InstSeq Seq;
  RISCVMatInt::generateInstSeq(Imm, XLenVT == MVT::i64, Seq);

  SDNode *Result = nullptr;
  SDValue SrcReg = CurDAG->getRegister(RISCV::X0, XLenVT);
  for (RISCVMatInt::Inst &Inst : Seq) {
    SDValue SDImm = CurDAG->getTargetConstant(Inst.Imm, DL, XLenVT);
    if (Inst.Opc == RISCV::LUI)
      Result = CurDAG->getMachineNode(RISCV::LUI, DL, XLenVT, SDImm);
    else
      Result = CurDAG->getMachineNode(Inst.Opc, DL, XLenVT, SrcReg, SDImm);

    // Only the first instruction has X0 as its source.
    SrcReg = SDValue(Result, 0);
  }

  return Result;
}

RISCVMatInt::generationIntSeqに64ビットの定数を生成するためのアセンブリ命令の出力アルゴリズムが含まれている。

1つずつ読み解いていく。まず32ビットに収まる値の範囲内であれば何も考えずに値を生成する。

• llvm/lib/Target/RISCV/Utils/RISCVMatInt.cpp

void generateInstSeq(int64_t Val, bool IsRV64, InstSeq &Res) {
  if (isInt<32>(Val)) {
    // Depending on the active bits in the immediate Value v, the following
    // instruction sequences are emitted:
    //
    // v == 0                        : ADDI
    // v[0,12) != 0 && v[12,32) == 0 : ADDI
    // v[0,12) == 0 && v[12,32) != 0 : LUI
    // v[0,32) != 0                  : LUI+ADDI(W)
    int64_t Hi20 = ((Val + 0x800) >> 12) & 0xFFFFF;
    int64_t Lo12 = SignExtend64<12>(Val);

    if (Hi20)
      Res.push_back(Inst(RISCV::LUI, Hi20));

    if (Lo12 || Hi20 == 0) {
      unsigned AddiOpc = (IsRV64 && Hi20) ? RISCV::ADDIW : RISCV::ADDI;
      Res.push_back(Inst(AddiOpc, Lo12));
    }
    return;
  }

32ビットよりも大きな値を作りたいときは下位12ビットと上位12ビットを切り離す。

  int64_t Lo12 = SignExtend64<12>(Val);
  int64_t Hi52 = ((uint64_t)Val + 0x800ull) >> 12;
  int ShiftAmount = 12 + findFirstSet((uint64_t)Hi52);
  Hi52 = SignExtend64(Hi52 >> (ShiftAmount - 12), 64 - ShiftAmount);

上位ビットの定数生成を行うために、上位ビットの値を引数としてgenerateInstSeq()再帰的に呼び出すことで命令を生成する。

  Hi52 = SignExtend64(Hi52 >> (ShiftAmount - 12), 64 - ShiftAmount);

  generateInstSeq(Hi52, IsRV64, Res);

生成した上位ビットは、シフト命令SLLIを使って上位にシフトする。さらにADDI命令を生成して下位12ビットを結合する。

この実装ではもう少し賢い方法を取っている。上位ビットHi52の下位ビットに0が並んでいる場合、これを省略してより高いビット位置から上位定数の生成を開始している。これにより再帰的呼び出しの回数を減らし、定数生成のステップを減らそうといる。

生成された命令に対して、コメントを付加してみると以下のようになる。

long_value:                             # @long_value

# %bb.0:                                # %entry
        addi    x2, x2, -8
        lui     x10, 146                # 0x0000_0000_0009_2000
        addi    x10, x10, -1493         # 0x0000_0000_0009_1a2b
        slli    x10, x10, 12            # 0x0000_0000_91a2_b000
        addi    x10, x10, 965           # 0x0000_0000_91a2_b3c5
        slli    x10, x10, 13            # 0x0000_1234_5678_a000
        addi    x10, x10, -1347         # 0x0000_1234_5678_9abd
        slli    x10, x10, 12            # 0x0123_4567_89ab_d000
        addi    x10, x10, -529          # 0x0123_4567_89ab_cdef
        sd      x10, 0(x2)
        addi    x10, zero, 0
        addi    x2, x2, 8
        ret