FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages

オリジナルLLVM Backendを追加しよう (19. 大きな値の生成)

LLVMにはすでにRISC-Vのバックエンドサポートが追加されている。しかし、勉強のために独自のRISC-V実装をLLVMに追加している。

f:id:msyksphinz:20190117013715p:plain

Cpu0チュートリアルの、ch3_largeframe.bcをうまくアセンブリ生成することができない。 大きな値を作成するために、MYRISCVXAnalyzeImmediate.cppの実装がうまく行っていないようで、これを解析している。

int test_largegframe() {
  int a[469753856];

  return 0;
}

このときにスタックをずらすため、大きな値を生成するルーチンが必要になる。このために、MYRISCVXAnalyzeImmediate.cppというルーチンを追加している。これは、MIPSのものを参考にした。

実装は進んでいるのだが、なぜか命令を生成するときにハングしてしまう。 試しに、MYRISCVXAnalyzeImmediate::Analyzeの命令生成過程をダンプしてみた。

-march=mipsだと以下のようになった。

Analyze : Imm = 1879015432, Size = 32
GetInstSeqLsADDI : Imm = 1879015432, RemSize = 32
GetInstSeqLsORI : Imm = 1879015432, RemSize = 32
Analyze : Imm = 1879015432, Size = 32
GetInstSeqLsADDI : Imm = 1879015432, RemSize = 32
GetInstSeqLsORI : Imm = 1879015432, RemSize = 32
Analyze : Imm = 1879015428, Size = 32
GetInstSeqLsADDI : Imm = 1879015428, RemSize = 32
Analyze : Imm = 1879015428, Size = 32
GetInstSeqLsADDI : Imm = 1879015428, RemSize = 32

一方でMYRISCVXだと以下のようになる。符号が完全に逆だ。

Analyze : Imm = 18446744071830536192, Size = 32
GetInstSeqLsADDI : Imm = 18446744071830536192, RemSize = 32
GetInstSeqLsORI : Imm = 18446744071830536192, RemSize = 32
Invalid opcode! 43668112, 136

Mipsの実装を参考に、スタックが伸びる方向がマイナスの場合はSUB命令を使うように変更した。

diff --git a/lib/Target/MYRISCVX/MYRISCVXSEInstrInfo.cpp b/lib/Target/MYRISCVX/MYRISCVXSEInstrInfo.cpp
index fbfc76e5810..8b0cb9f57eb 100644
--- a/lib/Target/MYRISCVX/MYRISCVXSEInstrInfo.cpp
+++ b/lib/Target/MYRISCVX/MYRISCVXSEInstrInfo.cpp
@@ -65,16 +65,21 @@ void MYRISCVXSEInstrInfo::adjustStackPtr(unsigned SP, int64_t Amount,
                                          MachineBasicBlock &MBB,
                                          MachineBasicBlock::iterator I) const {
   DebugLoc DL = I != MBB.end() ? I->getDebugLoc() : DebugLoc();
-  unsigned ADD  = MYRISCVX::ADD;
-  unsigned ADDI = MYRISCVX::ADDI;

-  if (isInt<16>(Amount)) {
+  if (isInt<12>(Amount)) {
     // addiu sp, sp, amount
-    BuildMI(MBB, I, DL, get(ADDI), SP).addReg(SP).addImm(Amount);
+    BuildMI(MBB, I, DL, get(MYRISCVX::ADDI), SP).addReg(SP).addImm(Amount);
   }
   else { // Expand immediate that doesn't fit in 16-bit.
+    // For numbers which are not 16bit integers we synthesize Amount inline
+    // then add or subtract it from sp.
+    unsigned Opc = MYRISCVX::ADD;
+    if (Amount < 0) {
+      Opc = MYRISCVX::SUB;
+      Amount = -Amount;
+    }
     unsigned Reg = loadImmediate(Amount, MBB, I, DL, nullptr);
-    BuildMI(MBB, I, DL, get(ADD), SP).addReg(SP).addReg(Reg, RegState::Kill);
+    BuildMI(MBB, I, DL, get(Opc), SP).addReg(SP).addReg(Reg, RegState::Kill);
   }
 }

と思ったらベースになるメンバ変数にOpcodeをアサインしていなかった。しょうもないミスをしてしまった。 っていうか直接MYRISCVX::命令名を書くのじゃダメなのか...?

diff --git a/lib/Target/MYRISCVX/MYRISCVXAnalyzeImmediate.h b/lib/Target/MYRISCVX/MYRISCVXAnalyzeImmediate.h
index 2548555cc0b..f81c3f792e4 100644
--- a/lib/Target/MYRISCVX/MYRISCVXAnalyzeImmediate.h
+++ b/lib/Target/MYRISCVX/MYRISCVXAnalyzeImmediate.h
@@ -54,7 +54,6 @@ namespace llvm {
     /// return it in Insts.
     void GetShortestSeq(InstSeqLs &SeqLs, InstSeq &Insts);
     unsigned Size;
-    unsigned ADDI, ORI, SHL, LUi;
     InstSeq Insts;
   };
 }
diff --git a/lib/Target/MYRISCVX/MYRISCVXAnalyzeImmediate.cpp b/lib/Target/MYRISCVX/MYRISCVXAnalyzeImmediate.cpp
index 19a0b629207..834e2c75d19 100644
--- a/lib/Target/MYRISCVX/MYRISCVXAnalyzeImmediate.cpp
+++ b/lib/Target/MYRISCVX/MYRISCVXAnalyzeImmediate.cpp
@@ -29,14 +29,14 @@ void MYRISCVXAnalyzeImmediate::ADDInstr(InstSeqLs &SeqLs, const Inst &I) {
 void MYRISCVXAnalyzeImmediate::GetInstSeqLsADDI(uint64_t Imm, unsigned RemSize,
                                                 InstSeqLs &SeqLs) {
   GetInstSeqLs((Imm + 0x8000ULL) & 0xffffffffffff0000ULL, RemSize, SeqLs);
-  ADDInstr(SeqLs, Inst(ADDI, Imm & 0xffffULL));
+  ADDInstr(SeqLs, Inst(MYRISCVX::ADDI, Imm & 0xffffULL));
 }

これでllcを生成する。再度ch3_largeframe.bcを食わせてみると、今度はRegのレジスタアドレスがおかしいと言われた。

        .globl  _Z16test_largegframev   # -- Begin function _Z16test_largegframev
        .p2align        2
        .type   _Z16test_largegframev,@function
        .ent    _Z16test_largegframev   # @_Z16test_largegframev
_Z16test_largegframev:
        .frame  $x8,1879015424,$x1
        .mask   0x00000000,0
        .set    noreorder
        .set    nomacro
# %bb.0:                                # %entry
        lui     llc: /home/masayuki/others/riscv/llvm/build-myriscvx/lib/Target/MYRISCVX/MYRISCVXGenAsmWriter.inc:238: static const char *llvm::MYRISCVXInstPrinter::getRegisterName(unsigned int): Assertion `RegNo && RegNo < 33 && "Invali
d register number!"' failed.
Stack dump:

うーん、このレジスタCreateVirtualRegister関数を使って生成しているレジスタだ。つまり、CreateVirtualRegisterで作ったレジスタを正しく割り当てできていないことになる。これは実装の途中ではまだ未対応なのか?よく分からない。

仕方がないので、とりあえずS0レジスタに決め打ちでレジスタを割り付けた。これなら最後まで生成できる。

diff --git a/lib/Target/MYRISCVX/MYRISCVXSEInstrInfo.cpp b/lib/Target/MYRISCVX/MYRISCVXSEInstrInfo.cpp
index a6cbc2bd79d..b358cdb3c01 100644
--- a/lib/Target/MYRISCVX/MYRISCVXSEInstrInfo.cpp
+++ b/lib/Target/MYRISCVX/MYRISCVXSEInstrInfo.cpp
@@ -98,11 +98,15 @@ MYRISCVXSEInstrInfo::loadImmediate(int64_t Imm, MachineBasicBlock &MBB,
   bool LastInstrIsADDiu = NewImm;

   MachineRegisterInfo &RegInfo = MBB.getParent()->getRegInfo();
+
   // The first instruction can be a LUi, which is different from other
   // instructions (ADDiu, ORI and SLL) in that it does not have a register
   // operand.
   const TargetRegisterClass *RC = &MYRISCVX::GPRRegClass;
-  unsigned Reg = RegInfo.createVirtualRegister(RC);
+
+  // MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
+  // xxx: It's very temporal implementation
+  unsigned Reg = MYRISCVX::S0;

   const MYRISCVXAnalyzeImmediate::InstSeq &Seq =
       AnalyzeImm.Analyze(Imm, Size, LastInstrIsADDiu);

これは最終的には修正してCreateVirtualRegister()に対応させなければならない。とりあえずこのまま進んで大丈夫かな。。。

大きな整数を生成するルーチン

例えば、469753856 x 4 =1879015424 (= 0x6FFF8000) のような値を生成する場合、AnalyzeImmediate関数は以下のような処理を行う。

&MYRISCVXAnalyzeImmediate::Analyze(uint64_t Imm, unsigned Size,
                                   bool LastInstrIsADDI) {
  // Get the list of instruction sequences.
  if (LastInstrIsADDI | !Imm)
    GetInstSeqLsADDI(Imm, Size, SeqLs);
  else
    GetInstSeqLs(Imm, Size, SeqLs);
  GetShortestSeq(SeqLs, Insts);
  return Insts;
}

Immに0x6FFF8000が入っている。GetInstSeqLs(Imm, Size, SeqLs)が呼ばれる。

void MYRISCVXAnalyzeImmediate::GetInstSeqLs(uint64_t Imm, unsigned RemSize,
                                            InstSeqLs &SeqLs) {
  uint64_t MaskedImm = Imm & (0xffffffffffffffffULL >> (64 - Size));
  // Do nothing if Imm is 0.
  if (!MaskedImm)
    return;
  // A single ADDI will do if RemSize <= 16.
  if (RemSize <= 16) {
    ADDInstr(SeqLs, Inst(MYRISCVX::ADDI, MaskedImm));
    return;
  }
  // Shift if the lower 16-bit is cleared.
  if (!(Imm & 0xffff)) {
    GetInstSeqLsSHL(Imm, RemSize, SeqLs);
    return;

  }

この部分は条件に入らないので除去される。下位16ビットが0の場合はGetInstSeqLsSHL(Imm, RemSize, SeqLs)が呼ばれ、単純な16ビットシフトによる命令生成が行われる。 そうでない場合、

  GetInstSeqLsADDI(Imm, RemSize, SeqLs);

ADDIを使った整数命令処理が行われる。これは、まず上位の16ビットを作って、それからADDI命令を使って足し算をして、大きな整数を作るという処理になる。

void MYRISCVXAnalyzeImmediate::GetInstSeqLsADDI(uint64_t Imm, unsigned RemSize,
                                                InstSeqLs &SeqLs) {
  GetInstSeqLs((Imm + 0x8000ULL) & 0xffffffffffff0000ULL, RemSize, SeqLs);
  ADDInstr(SeqLs, Inst(MYRISCVX::ADDI, Imm & 0xffffULL));
}

というわけでもう一度GetInstSeqLs((Imm + 0x8000ULL) & 0xffffffffffff0000ULL, RemSize, SeqLs)が呼ばれる。この時、下位の16ビットは全部0になっているので、先ほどのルーチンでGetInstSeqLsSHL()が呼ばれる。

void MYRISCVXAnalyzeImmediate::GetInstSeqLsSHL(uint64_t Imm, unsigned RemSize,
                                               InstSeqLs &SeqLs) {
  unsigned Shamt = countTrailingZeros(Imm);
  GetInstSeqLs(Imm >> Shamt, RemSize - Shamt, SeqLs);
  ADDInstr(SeqLs, Inst(MYRISCVX::SRL, Shamt));
}

上記のルーチンは、下位の0になっている部分をシフトして除去し、まずその値をGetInstSeqLs(Imm >> Shamt, RemSize - Shamt, SeqLs)で生成する。 次にMYRISCVX::SRLで、必要な分だけシフトして値を生成する。

これらの処理を繰り返して、まずは

  • ADDIによる上位16ビットの値を下位ビットに生成する。
  • SRLによる論理シフトで上位ビット生成
  • ADDIで下位の値を作る。

という一連の命令が生成される。

これを最適化する。具体的にはGetShortestSeq()関数、さらにReplaceADDISHLWithLUi()で処理される。

つまり、ADDI、SHLの処理がLUI命令に置き換えることができるならば置き換える。

void MYRISCVXAnalyzeImmediate::ReplaceADDISHLWithLUi(InstSeq &Seq) {
  // Check if the first two instructions are ADDI and SHL and the shift amount
  // is at least 16.
  if ((Seq.size() < 2) || (Seq[0].Opc != MYRISCVX::ADDI) ||
      (Seq[1].Opc != MYRISCVX::SRL) || (Seq[1].ImmOpnd < 16))
    return;
  // Sign-extend and shift operand of ADDI and see if it still fits in 16-bit.
  int64_t Imm = SignExtend64<16>(Seq[0].ImmOpnd);
  int64_t ShiftedImm = (uint64_t)Imm << (Seq[1].ImmOpnd - 16);
  if (!isInt<16>(ShiftedImm))
    return;
  // Replace the first instruction and erase the second.
  Seq[0].Opc = MYRISCVX::LUI;
  Seq[0].ImmOpnd = (unsigned)(ShiftedImm & 0xffff);
  Seq.erase(Seq.begin() + 1);

というところまでは理解できた。ただし、これはRISC-V のADDI、つまり即値が12ビットの時に対応できていないので、今度はそれを考える。