LR/SCを用いたAtomicコードの生成
以下のようなコードを考える。
cpp_atomic.cpp
#include <stdint.h> #include <atomic> std::atomic<int32_t> x32; std::atomic<int16_t> x16; std::atomic<int8_t > x8; int32_t test_32() { x32.fetch_add(2); return x32.load(); } int16_t test_16() { x16.fetch_add(2); return x16.load(); } int8_t test_8() { x8.fetch_add(2); return x8.load(); }
3種類用意した。32ビット版、16ビット版、8ビット版でそれぞれアトミック操作を行い加算を行うプログラムだ。アトミックな変数はグローバルな領域に確保しており、それをアトミックに加算して、その結果を返す仕組みだ。
まず1つ目の作戦として、MIPSのコードを真似てLoad Linked / Store Conditionalを使って実装してみる。MIPSではLL/SC命令という命令がありる。Load Linkedでリンク付きのロードを行い、Store Conditionalで、リンクがまだ切れていなければ正常なストア、別のスレッドにより書き換えが生じている場合は失敗として何度もLLから再試行する。
RISC-Vにも同様の命令が定義されている。LR(Load-Reserved)とSC(Store-Conditional)だ。
32ビット整数レジスタ(RV32)に対しては、LR.WとSC.W命令が定義されている。64ビットに対しては、LR.D命令とSC.D命令が定義されている。ここでは、LR.WとSC.W命令を定義する。
llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
class LRBase<bits<7> opcode, bits<3> funct3, bits<7> funct7, string opstring, RegisterClass RC, Operand Mem> :
MYRISCVX_R<opcode, funct3, funct7, (outs RC:$rd), (ins RC:$rs1),
!strconcat(opstring, "\t$rd, (${rs1})"), [], IILoad> {
let mayLoad = 1;
let rs2 = 0;
}
class SCBase<bits<7> opcode, bits<3> funct3, bits<7> funct7, string opstring, RegisterClass RC, Operand Mem> :
MYRISCVX_R<opcode, funct3, funct7, (outs RC:$rd), (ins RC:$rs1, RC:$rs2),
!strconcat(opstring, "\t$rd, $rs2, (${rs1})"), [], IIStore> {
let mayStore = 1;
}
/// Load-linked, Store-conditional
def LR_W : LRBase<0b0101111, 0b010, 0b0001000, "lr.w", GPR, mem>;
def SC_W : SCBase<0b0101111, 0b010, 0b0001100, "sc.w", GPR, mem>;
LRBaseはLoad Reserved用のテンプレートだ。rs2レジスタフィールドは0なので、let rs2 = 0;で固定している。SCBaseはStore Conditional用のテンプレートだ。
この2つを使って、今回はLR_WとSC_Wを定義した。
次に、Atomic操作を定義する。実際の動作はMYRISCVXTargetLoweringクラス内で実装することにする。
MYRISCVXTargetLoweringクラス内のEmitInstrWithCustomInserter()に実装を追加するので、Atomic操作の定義は、useCustomInserter =で囲む。
llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
// Atomic instructions with 2 source operands (ATOMIC_SWAP & ATOMIC_LOAD_*).
class Atomic2Ops<PatFrag Op, RegisterClass DRC> :
MYRISCVXPseudo<(outs DRC:$rd), (ins PtrRC:$ptr, DRC:$incr), "",
[(set DRC:$rd, (Op iPTR:$ptr, DRC:$incr))]>;
// Atomic Compare & Swap.
class AtomicCmpSwap<PatFrag Op, RegisterClass RC> :
MYRISCVXPseudo<(outs RC:$rd), (ins PtrRC:$ptr, RC:$cmp, RC:$swap), "",
[(set RC:$rd, (Op iPTR:$ptr, RC:$cmp, RC:$swap))]>;
let usesCustomInserter = 1 in {
def ATOMIC_LOAD_ADD_I8 : Atomic2Ops<atomic_load_add_8 , GPR>;
def ATOMIC_LOAD_ADD_I16 : Atomic2Ops<atomic_load_add_16 , GPR>;
def ATOMIC_LOAD_ADD_I32 : Atomic2Ops<atomic_load_add_32 , GPR>;
def ATOMIC_LOAD_SUB_I8 : Atomic2Ops<atomic_load_sub_8 , GPR>;
def ATOMIC_LOAD_SUB_I16 : Atomic2Ops<atomic_load_sub_16 , GPR>;
def ATOMIC_LOAD_SUB_I32 : Atomic2Ops<atomic_load_sub_32 , GPR>;
def ATOMIC_LOAD_AND_I8 : Atomic2Ops<atomic_load_and_8 , GPR>;
def ATOMIC_LOAD_AND_I16 : Atomic2Ops<atomic_load_and_16 , GPR>;
def ATOMIC_LOAD_AND_I32 : Atomic2Ops<atomic_load_and_32 , GPR>;
def ATOMIC_LOAD_OR_I8 : Atomic2Ops<atomic_load_or_8 , GPR>;
def ATOMIC_LOAD_OR_I16 : Atomic2Ops<atomic_load_or_16 , GPR>;
def ATOMIC_LOAD_OR_I32 : Atomic2Ops<atomic_load_or_32 , GPR>;
def ATOMIC_LOAD_XOR_I8 : Atomic2Ops<atomic_load_xor_8 , GPR>;
def ATOMIC_LOAD_XOR_I16 : Atomic2Ops<atomic_load_xor_16 , GPR>;
def ATOMIC_LOAD_XOR_I32 : Atomic2Ops<atomic_load_xor_32 , GPR>;
def ATOMIC_LOAD_NAND_I8 : Atomic2Ops<atomic_load_nand_8 , GPR>;
def ATOMIC_LOAD_NAND_I16 : Atomic2Ops<atomic_load_nand_16 , GPR>;
def ATOMIC_LOAD_NAND_I32 : Atomic2Ops<atomic_load_nand_32 , GPR>;
def ATOMIC_SWAP_I8 : Atomic2Ops<atomic_swap_8 , GPR>;
def ATOMIC_SWAP_I16 : Atomic2Ops<atomic_swap_16 , GPR>;
def ATOMIC_SWAP_I32 : Atomic2Ops<atomic_swap_32 , GPR>;
def ATOMIC_CMP_SWAP_I8 : AtomicCmpSwap<atomic_cmp_swap_8 , GPR>;
def ATOMIC_CMP_SWAP_I16 : AtomicCmpSwap<atomic_cmp_swap_16 , GPR>;
def ATOMIC_CMP_SWAP_I32 : AtomicCmpSwap<atomic_cmp_swap_32 , GPR>;
}
実装の方針としては、
Atomic操作を定義する。定義する操作は、
実装する関数は
32ビットのAtomic操作 :
MYRISCVXTargetLowering::emitAtomicBinary(),MYRISCVXTargetLowering::emitAtomicCmpSwap()で実装する。16ビットのAttmic操作 / 8ビットのAtomic操作 :
MYRISCVXTargetLowering::emitAtomicBinaryPartword(),MYRISCVXTargetLowering::emitAtomicCmpSwapPartword()に実装する。基本的な考え方は32ビット版の実装と同じで、データをマスクして16ビット、8ビットに対応させる。
というわけで、MYRISCVXTargetLowering::EmitInstrWithCustomInserter()に条件分岐を追加する。
MachineBasicBlock *
MYRISCVXTargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
MachineBasicBlock *BB) const {
switch (MI.getOpcode()) {
default:
llvm_unreachable("Unexpected instr type to insert");
case MYRISCVX::Select_GPR_Using_CC_GPR:
break;
case MYRISCVX::ATOMIC_LOAD_ADD_I8: return emitAtomicBinaryPartword (MI, BB, 1, MYRISCVX::ADD);
case MYRISCVX::ATOMIC_LOAD_ADD_I16: return emitAtomicBinaryPartword (MI, BB, 2, MYRISCVX::ADD);
case MYRISCVX::ATOMIC_LOAD_ADD_I32: return emitAtomicBinary (MI, BB, 4, MYRISCVX::ADD);
case MYRISCVX::ATOMIC_LOAD_AND_I8: return emitAtomicBinaryPartword (MI, BB, 1, MYRISCVX::AND);
case MYRISCVX::ATOMIC_LOAD_AND_I16: return emitAtomicBinaryPartword (MI, BB, 2, MYRISCVX::AND);
case MYRISCVX::ATOMIC_LOAD_AND_I32: return emitAtomicBinary (MI, BB, 4, MYRISCVX::AND);
case MYRISCVX::ATOMIC_LOAD_OR_I8: return emitAtomicBinaryPartword (MI, BB, 1, MYRISCVX::OR);
case MYRISCVX::ATOMIC_LOAD_OR_I16: return emitAtomicBinaryPartword (MI, BB, 2, MYRISCVX::OR);
case MYRISCVX::ATOMIC_LOAD_OR_I32: return emitAtomicBinary (MI, BB, 4, MYRISCVX::OR);
case MYRISCVX::ATOMIC_LOAD_XOR_I8: return emitAtomicBinaryPartword (MI, BB, 1, MYRISCVX::XOR);
case MYRISCVX::ATOMIC_LOAD_XOR_I16: return emitAtomicBinaryPartword (MI, BB, 2, MYRISCVX::XOR);
case MYRISCVX::ATOMIC_LOAD_XOR_I32: return emitAtomicBinary (MI, BB, 4, MYRISCVX::XOR);
case MYRISCVX::ATOMIC_LOAD_NAND_I8: return emitAtomicBinaryPartword (MI, BB, 1, 0, true);
case MYRISCVX::ATOMIC_LOAD_NAND_I16: return emitAtomicBinaryPartword (MI, BB, 2, 0, true);
case MYRISCVX::ATOMIC_LOAD_NAND_I32: return emitAtomicBinary (MI, BB, 4, 0, true);
case MYRISCVX::ATOMIC_LOAD_SUB_I8: return emitAtomicBinaryPartword (MI, BB, 1, MYRISCVX::SUB);
case MYRISCVX::ATOMIC_LOAD_SUB_I16: return emitAtomicBinaryPartword (MI, BB, 2, MYRISCVX::SUB);
case MYRISCVX::ATOMIC_LOAD_SUB_I32: return emitAtomicBinary (MI, BB, 4, MYRISCVX::SUB);
case MYRISCVX::ATOMIC_SWAP_I8: return emitAtomicBinaryPartword (MI, BB, 1, 0);
case MYRISCVX::ATOMIC_SWAP_I16: return emitAtomicBinaryPartword (MI, BB, 2, 0);
case MYRISCVX::ATOMIC_SWAP_I32: return emitAtomicBinary (MI, BB, 4, 0);
case MYRISCVX::ATOMIC_CMP_SWAP_I8: return emitAtomicCmpSwapPartword (MI, BB, 1);
case MYRISCVX::ATOMIC_CMP_SWAP_I16: return emitAtomicCmpSwapPartword (MI, BB, 2);
case MYRISCVX::ATOMIC_CMP_SWAP_I32: return emitAtomicCmpSwap (MI, BB, 4);
}
大量に条件分岐を追加してしまったが、要するに
- 32ビットのAtomiLoadの場合は
emitAtomicBinary()を呼ぶ。 - 16ビット/8ビットのAtomicLoadの場合は
emitAtomicBinaryPartword()を呼ぶ。 - NANDの場合は条件が若干複雑 (RISC-VにNAND命令が存在しないので)。
- 32ビットの
AtomicCmpSwapはemitAtomicCmpSwap()を呼び、16ビット/8ビットの場合はemitAtomicCmpSwapPartword()を呼ぶ。
emitAtomicBinary()の実装は以下のようになる。まず、LRを発行してSCを発行し、その結果を確認する。
// insert new blocks after the current block const BasicBlock *LLVM_BB = BB->getBasicBlock(); MachineBasicBlock *loopMBB = MF->CreateMachineBasicBlock(LLVM_BB); MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB); MachineFunction::iterator It = ++BB->getIterator(); MF->insert(It, loopMBB); MF->insert(It, exitMBB); // Transfer the remainder of BB and its successor edges to exitMBB. exitMBB->splice(exitMBB->begin(), BB, std::next(MachineBasicBlock::iterator(MI)), BB->end()); exitMBB->transferSuccessorsAndUpdatePHIs(BB); // thisMBB: // ... // fallthrough --> loopMBB BB->addSuccessor(loopMBB); loopMBB->addSuccessor(loopMBB); loopMBB->addSuccessor(exitMBB); // loopMBB: // ll oldval, 0(ptr) // <binop> storeval, oldval, incr // sc success, storeval, 0(ptr) // beq success, $0, loopMBB BB = loopMBB; // Load Reservedを実行 BuildMI(BB, DL, TII->get(LR), OldVal).addReg(Ptr); // 演算を実行 BuildMI(BB, DL, TII->get(BinOpcode), StoreVal).addReg(OldVal).addReg(Incr); // Store Conditionalを実行 BuildMI(BB, DL, TII->get(SC), Success).addReg(Ptr).addReg(StoreVal); // BEQで条件が成立しなければもう一度LRからやり直す。 BuildMI(BB, DL, TII->get(BEQ)).addReg(Success).addReg(ZERO).addMBB(loopMBB);
コードを実行すると、以下のようになる。
_Z7test_32v: .cfi_startproc .frame x8,8,x1 .mask 0x00000004,-4 .set noreorder .set nomacro # %bb.0: # %entry addi x2, x2, -8 .cfi_def_cfa_offset 8 sw x2, 4(x2) # 4-byte Folded Spill .cfi_offset 2, -4 sync 0 lui x10, %hi(x32) ori x10, x10, %lo(x32) addi x11, zero, 2 $BB0_1: # %entry # =>This Inner Loop Header: Depth=1 lr.w x12, (x10) add x12, x12, x11 sc.w x12, x12, (x10) beq x12, zero, $BB0_1 # %bb.2: # %entry sync 0 addi x11, zero, 0 addi x12, x11, 0 j __sync_val_compare_and_swap_4 sync 0 lw x2, 4(x2) # 4-byte Folded Reload addi x2, x2, 8 ret
