[下書き] LLVMバックエンド for RV16Kv2 開発文書

$ bin/llvm-lit test -s  # 全てのテストを実行する
$ bin/llvm-lit -s --filter 'RV16K' test # RV16Kを含むテストを実行する
$ bin/llvm-lit -as --filter 'RV16K' test # テスト結果を詳細に表示する
$ bin/llvm-lit -as --filter 'RV16K' --debug test # デバッグ情報を表示する

LLVM IR code

|
|
v

SelectionDAG (SDNode); RV16Kで扱えない型・操作を含む (not legal)。

|
|  <-- RV16KTargetLowering::RV16KTargetLowering
|  <-- RV16KTargetLowering::Lower*
v

SelectionDAG (SDNode); RV16Kで扱える型・操作のみを含む (legal)。

|
|  <-- RV16KDAGToDAGISel, RV16KInstrInfo
v

SelectionDAG (MachineSDNode); ノードの命令は全てRV16Kのもの。

|
|  <-- RV16KInstrInfo; 命令スケジューリング
v

LLVM MIR (MachineInstr); スケジューリングされた命令列

|  (以下の流れは TargetPassConfig::addMachinePasses に記述されている)
|
|  <-- RV16KTargetLowering::EmitInstrWithCustomInserter;
|          usesCustomInserter フラグが立っている ある MachineInstr の代わりに
|          複数の MachineInstr を挿入したり MachineBasicBlock を追加したりする。
|
|  <-- SSA上での最適化
|
|  <-- レジスタ割り付け
v

LLVM MIR (MachineInstr); 物理レジスタのみを含む命令列（仮想レジスタを含まない）

|
|  <-- RV16KInstrInfo::expandPostRAPseudo
|
|  <-- RV16KFrameLowering::processFunctionBeforeFrameFinalized
|
|  <-- スタックサイズの確定
|
|  <-- RV16KFrameLowering::emitPrologue; 関数プロローグの挿入
|  <-- RV16KFrameLowering::emitEpilogue; 関数エピローグの挿入
|  <-- RV16KRegisterInfo::eliminateFrameIndex; frame indexの消去
|
|  <-- llvm::scavengeFrameVirtualRegs;
|          frame lowering中に必要になった仮想レジスタをscavengeする
v

LLVM MIR (MachineInstr); frame index が削除された命令列

|
|  <-- RV16KPassConfig::addPreEmitPass
|  <-- RV16KPassConfig::addPreEmitPass2
|
|
|  <-- RV16KAsmPrinter
|  <-- PseudoInstExpansion により指定された擬似命令展開の実行
v

MC (MCInst); アセンブリと等価な中間表現

$ git clone https://github.com/llvm/llvm-project.git
$ cd llvm-project
$ git checkout llvmorg-8.0.0
$ git checkout -b rv16k

LLVM_DEBUG(dbgs() << formatv("HOGEHOGE {0} {1} {2} {3}\n", bit15, bit14,
                             bit12, isNIAI));

$ bin/llvm-mc -filetype=obj -triple=rv16k < foo.s | bin/llvm-objdump -debug -d -

$ cat foo.ll
define i16 @lw(i16 *%a) nounwind {
  %1 = getelementptr i16, i16* %a, i16 3
  %2 = load i16, i16* %1
  %3 = load volatile i16, i16* %a
  ret i16 %2
}

$ bin/llc -mtriple=rv16k -verify-machineinstrs -debug-only=isel < foo.ll
	.text
	.file	"<stdin>"



=== lw
Initial selection DAG: %bb.0 'lw:'
SelectionDAG has 12 nodes:
  t0: ch = EntryToken
  t2: i16,ch = CopyFromReg t0, Register:i16 %0
  t5: i16 = Constant(0)
    t4: i16 = add t2, Constant:i16(6)
  t7: i16,ch = load<(load 2 from %ir.1)> t0, t4, undef:i16
    t8: i16,ch = load<(volatile load 2 from %ir.a)> t7:1, t2, undef:i16
  t10: ch,glue = CopyToReg t8:1, Register:i16 $x8, t7
  t11: ch = RV16KISD::RET_FLAG t10, Register:i16 $x8, t10:1


Optimized lowered selection DAG: %bb.0 'lw:'
SelectionDAG has 12 nodes:
  t0: ch = EntryToken
  t2: i16,ch = CopyFromReg t0, Register:i16 %0
    t4: i16 = add t2, Constant:i16(6)
  t7: i16,ch = load<(load 2 from %ir.1)> t0, t4, undef:i16
      t12: i16,ch = load<(volatile load 2 from %ir.a)> t0, t2, undef:i16
    t13: ch = TokenFactor t7:1, t12:1
  t10: ch,glue = CopyToReg t13, Register:i16 $x8, t7
  t11: ch = RV16KISD::RET_FLAG t10, Register:i16 $x8, t10:1


Type-legalized selection DAG: %bb.0 'lw:'
SelectionDAG has 12 nodes:
  t0: ch = EntryToken
  t2: i16,ch = CopyFromReg t0, Register:i16 %0
    t4: i16 = add t2, Constant:i16(6)
  t7: i16,ch = load<(load 2 from %ir.1)> t0, t4, undef:i16
      t12: i16,ch = load<(volatile load 2 from %ir.a)> t0, t2, undef:i16
    t13: ch = TokenFactor t7:1, t12:1
  t10: ch,glue = CopyToReg t13, Register:i16 $x8, t7
  t11: ch = RV16KISD::RET_FLAG t10, Register:i16 $x8, t10:1


Legalized selection DAG: %bb.0 'lw:'
SelectionDAG has 12 nodes:
  t0: ch = EntryToken
  t2: i16,ch = CopyFromReg t0, Register:i16 %0
    t4: i16 = add t2, Constant:i16(6)
  t7: i16,ch = load<(load 2 from %ir.1)> t0, t4, undef:i16
      t12: i16,ch = load<(volatile load 2 from %ir.a)> t0, t2, undef:i16
    t13: ch = TokenFactor t7:1, t12:1
  t10: ch,glue = CopyToReg t13, Register:i16 $x8, t7
  t11: ch = RV16KISD::RET_FLAG t10, Register:i16 $x8, t10:1


Optimized legalized selection DAG: %bb.0 'lw:'
SelectionDAG has 12 nodes:
  t0: ch = EntryToken
  t2: i16,ch = CopyFromReg t0, Register:i16 %0
    t4: i16 = add t2, Constant:i16(6)
  t7: i16,ch = load<(load 2 from %ir.1)> t0, t4, undef:i16
      t12: i16,ch = load<(volatile load 2 from %ir.a)> t0, t2, undef:i16
    t13: ch = TokenFactor t7:1, t12:1
  t10: ch,glue = CopyToReg t13, Register:i16 $x8, t7
  t11: ch = RV16KISD::RET_FLAG t10, Register:i16 $x8, t10:1


===== Instruction selection begins: %bb.0 ''

ISEL: Starting selection on root node: t11: ch = RV16KISD::RET_FLAG t10, Register:i16 $x8, t10:1
ISEL: Starting pattern match
  Morphed node: t11: ch = PseudoRET Register:i16 $x8, t10, t10:1
ISEL: Match complete!

ISEL: Starting selection on root node: t10: ch,glue = CopyToReg t13, Register:i16 $x8, t7

ISEL: Starting selection on root node: t13: ch = TokenFactor t7:1, t12:1

ISEL: Starting selection on root node: t7: i16,ch = load<(load 2 from %ir.1)> t0, t4, undef:i16
ISEL: Starting pattern match
  Initial Opcode index to 5
  Morphed node: t7: i16,i16,ch = LW<Mem:(load 2 from %ir.1)> t2, TargetConstant:i16<6>, t0
ISEL: Match complete!

ISEL: Starting selection on root node: t12: i16,ch = load<(volatile load 2 from %ir.a)> t0, t2, undef:i16
ISEL: Starting pattern match
  Initial Opcode index to 5
  Match failed at index 10
  Continuing at 95
  Morphed node: t12: i16,i16,ch = LW<Mem:(volatile load 2 from %ir.a)> t2, TargetConstant:i16<0>, t0
ISEL: Match complete!

ISEL: Starting selection on root node: t2: i16,ch = CopyFromReg t0, Register:i16 %0

ISEL: Starting selection on root node: t9: i16 = Register $x8

ISEL: Starting selection on root node: t1: i16 = Register %0

ISEL: Starting selection on root node: t0: ch = EntryToken

===== Instruction selection ends:
Selected selection DAG: %bb.0 'lw:'
SelectionDAG has 11 nodes:
  t0: ch = EntryToken
  t2: i16,ch = CopyFromReg t0, Register:i16 %0
  t7: i16,i16,ch = LW<Mem:(load 2 from %ir.1)> t2, TargetConstant:i16<6>, t0
      t12: i16,i16,ch = LW<Mem:(volatile load 2 from %ir.a)> t2, TargetConstant:i16<0>, t0
    t13: ch = TokenFactor t7:2, t12:2
  t10: ch,glue = CopyToReg t13, Register:i16 $x8, t7
  t11: ch = PseudoRET Register:i16 $x8, t10, t10:1


Total amount of phi nodes to update: 0
*** MachineFunction at end of ISel ***
# Machine code for function lw: IsSSA, TracksLiveness
Function Live Ins: $x8 in %0

bb.0 (%ir-block.0):
  liveins: $x8
  %0:gpr = COPY $x8
  %1:gpr = LW %0:gpr, 0, implicit-def dead $flags :: (volatile load 2 from %ir.a)
  %2:gpr = LW %0:gpr, 6, implicit-def dead $flags :: (load 2 from %ir.1)
  $x8 = COPY %2:gpr
  PseudoRET implicit $x8

# End machine code for function lw.

	.globl	lw                      # -- Begin function lw
	.p2align	1
	.type	lw,@function
lw:                                     # @lw
# %bb.0:
	lw	a1, 0(a0)
	lw	a0, 6(a0)
	jr	ra
.Lfunc_end0:
	.size	lw, .Lfunc_end0-lw
                                        # -- End function

	.section	".note.GNU-stack","",@progbits

for (auto N : {ISD::EXTLOAD, ISD::SEXTLOAD, ISD::ZEXTLOAD})
    setLoadExtAction(N, MVT::i16, MVT::i1, Promote);

setOperationAction(ISD::GlobalAddress, MVT::i16, Custom);

@G = global i16 0

define i16 @lw_sw_global(i16 %a) nounwind {
  %1 = load volatile i16, i16* @G
  store i16 %a, i16* @G
  %2 = getelementptr i16, i16* @G, i16 9
  %3 = load volatile i16, i16* %2
  store i16 %a, i16* %2
  ret i16 0
}

$ bin/llc -mtriple=rv16k -verify-machineinstrs < foo.ll
	.text
	.file	"<stdin>"

# After Post-RA pseudo instruction expansion pass
# Machine code for function lw_sw_global: NoPHIs, NoVRegs
Function Live Ins: $x8

bb.0 (%ir-block.0):
  $x10 = LI @G, implicit-def dead $flags
  $x9 = LW $x10, 0, implicit-def dead $flags :: (volatile dereferenceable load 2 from @G)
  SW $x8, killed $x10, 0, implicit-def dead $flags :: (store 2 into @G)
  $x10 = LI @G + 18, implicit-def dead $flags
  dead $x11 = LW $x10, 0, implicit-def dead $flags :: (volatile load 2 from %ir.2)
  SW killed $x8, killed $x10, 0, implicit-def dead $flags :: (store 2 into %ir.2)
  $x8 = MOV killed $x9(tied-def 0), implicit-def $flags
  PseudoRET implicit $x8

# End machine code for function lw_sw_global.

*** Bad machine code: Tied physical registers must match. ***
- function:    lw_sw_global
- basic block: %bb.0  (0xf02c98)
- instruction: $x8 = MOV killed $x9(tied-def 0), implicit-def $flags
- operand 0:   $x8

*** Bad machine code: Two-address instruction operands must be identical ***
- function:    lw_sw_global
- basic block: %bb.0  (0xf02c98)
- instruction: $x8 = MOV killed $x9(tied-def 0), implicit-def $flags
- operand 1:   killed $x9(tied-def 0)

*** Bad machine code: Explicit operand marked as def ***
- function:    lw_sw_global
- basic block: %bb.0  (0xf02c98)
- instruction: $x8 = MOV killed $x9(tied-def 0), implicit-def $flags
- operand 2:   implicit-def $flags

*** Bad machine code: Explicit operand marked as implicit ***
- function:    lw_sw_global
- basic block: %bb.0  (0xf02c98)
- instruction: $x8 = MOV killed $x9(tied-def 0), implicit-def $flags
- operand 2:   implicit-def $flags

*** Bad machine code: Illegal physical register for instruction ***
- function:    lw_sw_global
- basic block: %bb.0  (0xf02c98)
- instruction: $x8 = MOV killed $x9(tied-def 0), implicit-def $flags
- operand 2:   implicit-def $flags
$flags is not a GPR register.
LLVM ERROR: Found 5 machine code errors.

let hasSideEffects = 0, mayLoad = 0, mayStore = 0, Defs = [FLAGS] in
def MOV : RV16KInstRR16<0b11000000, (outs GPR:$rd), (ins GPR:$rs),
                       "mov", "$rd, $rs">;

def SDTX86BrCond  : SDTypeProfile<0, 3,
                                  [SDTCisVT<0, OtherVT>,
                                   SDTCisVT<1, i8>, SDTCisVT<2, i32>]>;
def X86brcond  : SDNode<"X86ISD::BRCOND",   SDTX86BrCond,
                        [SDNPHasChain]>;

SDNode *LEGDAGToDAGISel::SelectConditionalBranch(SDNode *N) {
  SDValue Chain = N->getOperand(0);
  SDValue Cond = N->getOperand(1);
  SDValue LHS = N->getOperand(2);
  SDValue RHS = N->getOperand(3);
  SDValue Target = N->getOperand(4);

  // Generate a comparison instruction.
  EVT CompareTys[] = { MVT::Other, MVT::Glue };
  SDVTList CompareVT = CurDAG->getVTList(CompareTys);
  SDValue CompareOps[] = {LHS, RHS, Chain};
  SDNode *Compare = CurDAG->getMachineNode(LEG::CMP, N, CompareVT, CompareOps);

  // Generate a predicated branch instruction.
  CondCodeSDNode *CC = cast<CondCodeSDNode>(Cond.getNode());
  SDValue CCVal = CurDAG->getTargetConstant(CC->get(), N, MVT::i32);
  SDValue BranchOps[] = {CCVal, Target, SDValue(Compare, 0),
                         SDValue(Compare, 1)};
  return CurDAG->getMachineNode(LEG::Bcc, N, MVT::Other, BranchOps);
}

    SDValue Sub = DAG.getNode(X86ISD::SUB, dl, VTs, Op0, Op1);
    return SDValue(Sub.getNode(), 1);

def : Pat<(brcond (i16 (seteq GPR:$rs1, GPR:$rs2)), bb:$imm),
          (JE simm8_lsb0:$imm, (CMP GPR:$rs1, GPR:$rs2))>;

anonymous_978: 	(JE simm8_lsb0:{ *:[i16] }:$imm, (CMP:{}:{} GPR:{}:$rs1, GPR:{}:$rs2))
Included from /home/anqou/ano/secure_vm/llvm-project/llvm/lib/Target/RV16K/RV16K.td:23:
/home/anqou/ano/secure_vm/llvm-project/llvm/lib/Target/RV16K/RV16KInstrInfo.td:215:1: error: In anonymous_978: Instruction 'JE' was provided 2 operands but expected only 1!
def : Pat<(brcond (i16 (seteq GPR:$rs1, GPR:$rs2)), bb:$imm),

setOperationAction(ISD::BRCOND, MVT::Other, Expand);
setOperationAction(ISD::BR_CC, MVT::i16, Custom);

test11:
  %val11 = load volatile i16, i16* %b
  br i1 %c, label %end, label %test12

def SDT_RV16KCmp      : SDTypeProfile<0,  2, [SDTCisSameAs<0, 1>]>;
def SDT_RV16KBrCC     : SDTypeProfile<0,  2, [SDTCisVT<0, OtherVT>,
                                                  SDTCisVT<1, i16>]>;

def RV16KCmp : SDNode<"RV16KISD::CMP", SDT_RV16KCmp, [SDNPOutGlue]>;
def RV16BrCC : SDNode<"RV16KISD::BR_CC", SDT_RV16KBrCC, [SDNPHasChain, SDNPInGlue]>;

def : Pat<(RV16KCmp GPR:$rs1, GPR:$rs2), (CMP GPR:$rs1, GPR:$rs2)>;
def : Pat<(RV16KBrCC bb:$imm7, RV16K_COND_E), (JE simm8_lsb0:$imm7)>;

/// CALLSEQ_START/CALLSEQ_END - These operators mark the beginning and end
/// of a call sequence, and carry arbitrary information that target might
/// want to know.  The first operand is a chain, the rest are specified by
/// the target and not touched by the DAG optimizers.
/// Targets that may use stack to pass call arguments define additional
/// operands:
/// - size of the call frame part that must be set up within the
///   CALLSEQ_START..CALLSEQ_END pair,
/// - part of the call frame prepared prior to CALLSEQ_START.
/// Both these parameters must be constants, their sum is the total call
/// frame size.
/// CALLSEQ_START..CALLSEQ_END pairs may not be nested.
CALLSEQ_START,  // Beginning of a call sequence
CALLSEQ_END,    // End of a call sequence

define i16 @defined_function(i16 %a) nounwind {
  %1 = add i16 %a, 1
  ret i16 %1
}

define i16 @test_call_defined(i16 %a) nounwind {
  %1 = call i16 @defined_function(i16 %a) nounwind
  %2 = add i16 %a, %1
  ret i16 %2
}

	.text
	.file	"<stdin>"
	.globl	defined_function        # -- Begin function defined_function
	.p2align	1
	.type	defined_function,@function
defined_function:                       # @defined_function
# %bb.0:
	addi	a0, 1
	jr	ra
.Lfunc_end0:
	.size	defined_function, .Lfunc_end0-defined_function
                                        # -- End function
	.globl	test_call_defined       # -- Begin function test_call_defined
	.p2align	1
	.type	test_call_defined,@function
test_call_defined:                      # @test_call_defined
# %bb.0:
	sw	ra, 2(fp)
	sw	s0, 0(fp)
	mov	s0, a0
	li	a1, defined_function
	jalr	a1
	add	s0, a0
	mov	a0, s0
	lw	s0, 0(fp)
	lw	ra, 2(fp)
	jr	ra
.Lfunc_end1:
	.size	test_call_defined, .Lfunc_end1-test_call_defined
                                        # -- End function

	.section	".note.GNU-stack","",@progbits

  int Offset = MFI.getObjectOffset(FI) - getOffsetOfLocalArea() +
               MFI.getOffsetAdjustment();

  explicit RV16KFrameLowering(const RV16KSubtarget &STI)
      : TargetFrameLowering(StackGrowsDown,
                            /*StackAlignment=*/2,
                            /*LocalAreaOffset=*/0) {}

  /// The amount that a frame offset needs to be adjusted to
  /// have the actual offset from the stack/frame pointer.  The exact usage of
  /// this is target-dependent, but it is typically used to adjust between
  /// SP-relative and FP-relative offsets.  E.G., if objects are accessed via
  /// SP then OffsetAdjustment is zero; if FP is used, OffsetAdjustment is set
  /// to the distance between the initial SP and the value in FP.  For many
  /// targets, this value is only used when generating debug info (via
  /// TargetRegisterInfo::getFrameIndexReference); when generating code, the
  /// corresponding adjustments are performed directly.

// Determines the size of the frame and maximum call frame size.
void RISCVFrameLowering::determineFrameLayout(MachineFunction &MF) const {
  MachineFrameInfo &MFI = MF.getFrameInfo();
  const RISCVRegisterInfo *RI = STI.getRegisterInfo();

  // Get the number of bytes to allocate from the FrameInfo.
  uint64_t FrameSize = MFI.getStackSize();

  // Get the alignment.
  uint64_t StackAlign = RI->needsStackRealignment(MF) ? MFI.getMaxAlignment()
                                                      : getStackAlignment();

  // Make sure the frame is aligned.
  FrameSize = alignTo(FrameSize, StackAlign);

  // Update frame info.
  MFI.setStackSize(FrameSize);
}

define i16 @defined_function(i16 %a) nounwind {
  %1 = add i16 %a, 1
  ret i16 %1
}

define i16 @test_call_defined(i16 %a) nounwind {
  %1 = call i16 @defined_function(i16 %a) nounwind
  %2 = add i16 %a, %1
  ret i16 %2
}

    .text
    .file    "<stdin>"
    .globl    defined_function        # -- Begin function defined_function
    .p2align    1
    .type    defined_function,@function
defined_function:                       # @defined_function
# %bb.0:
    addi    sp, -2
    sw    fp, 0(sp)
    mov    fp, sp
    addi    fp, 2
    addi    a0, 1
    lw    fp, 0(sp)
    addi    sp, 2
    jr    ra
.Lfunc_end0:
    .size    defined_function, .Lfunc_end0-defined_function
                                        # -- End function
    .globl    test_call_defined       # -- Begin function test_call_defined
    .p2align    1
    .type    test_call_defined,@function
test_call_defined:                      # @test_call_defined
# %bb.0:
    addi    sp, -6
    sw    ra, 4(sp)
    sw    fp, 2(sp)
    sw    s0, 0(sp)
    mov    fp, sp
    addi    fp, 6
    mov    s0, a0
    li    a1, defined_function
    jalr    a1
    add    s0, a0
    mov    a0, s0
    lw    s0, 0(sp)
    lw    fp, 2(sp)
    lw    ra, 4(sp)
    addi    sp, 6
    jr    ra
.Lfunc_end1:
    .size    test_call_defined, .Lfunc_end1-test_call_defined
                                        # -- End function

    .section    ".note.GNU-stack","",@progbits

/// Select(COND, TRUEVAL, FALSEVAL).  If the type of the boolean COND is not
/// i1 then the high bits must conform to getBooleanContents.
SELECT,

/// Select with condition operator - This selects between a true value and
/// a false value (ops #2 and #3) based on the boolean result of comparing
/// the lhs and rhs (ops #0 and #1) of a conditional expression with the
/// condition code in op #4, a CondCodeSDNode.
SELECT_CC,

/// Indicate that the specified operation does not work with the specified
/// type and indicate what to do about it. Note that VT may refer to either
/// the type of a result or that of an operand of Op.
void setOperationAction(unsigned Op, MVT VT,
                      LegalizeAction Action) {
  assert(Op < array_lengthof(OpActions[0]) && "Table isn't big enough!");
  OpActions[(unsigned)VT.SimpleTy][Op] = Action;
}

def : Pat<(Call GPR:$rs), (JALR GPR:$rs)>;
def : Pat<(Call tglobaladdr:$dst), (JAL tglobaladdr:$dst)>;
def : Pat<(Call texternalsym:$dst), (JAL texternalsym:$dst)>;

$ cat foo.ll
define void @test() {
entry:
  %retval = alloca i16, align 2
  store i16 0, i16* %retval, align 2
  ret void
}

$ bin/llc -mtriple=rv16k -verify-machineinstrs < foo.ll
	.text
	.file	"<stdin>"
LLVM ERROR: Cannot select: t2: i16 = FrameIndex\<0\>
In function: test

def frameindex  : SDNode<"ISD::FrameIndex",           SDTPtrLeaf, [],
                         "FrameIndexSDNode">;

//===----------------------------------------------------------------------===//
// Complex pattern definitions.
//

// Complex patterns, e.g. X86 addressing mode, requires pattern matching code
// in C++. NumOperands is the number of operands returned by the select function;
// SelectFunc is the name of the function used to pattern match the max. pattern;
// RootNodes are the list of possible root nodes of the sub-dags to match.
// e.g. X86 addressing mode - def addr : ComplexPattern<4, "SelectAddr", [add]>;
//
class ComplexPattern<ValueType ty, int numops, string fn,
                     list<SDNode> roots = [], list<SDNodeProperty> props = [],
                     int complexity = -1> {
  ValueType Ty = ty;
  int NumOperands = numops;
  string SelectFunc = fn;
  list<SDNode> RootNodes = roots;
  list<SDNodeProperty> Properties = props;
  int Complexity = complexity;
}

def lea32addr : ComplexPattern<i32, 5, "selectLEAAddr",
                               [add, sub, mul, X86mul_imm, shl, or, frameindex],
                               []>;

/// TokenFactor - This node takes multiple tokens as input and produces a
/// single token result. This is used to represent the fact that the operand
/// operators are independent of each other.
TokenFactor,

  // Copy all of the result registers out of their specified physreg.
  for (auto &VA : RVLocs) {
    // Copy the value out, gluing the copy to the end of the call sequence.
    SDValue RetValue =
        DAG.getCopyFromReg(Chain, DL, VA.getLocReg(), VA.getLocVT(), Glue);
    Chain = RetValue.getValue(1);
    Glue = RetValue.getValue(2);

    InVals.push_back(Chain.getValue(0));
  }

/// Unlike LLVM values, Selection DAG nodes may return multiple
/// values as the result of a computation.  Many nodes return multiple values,
/// from loads (which define a token and a return value) to ADDC (which returns
/// a result and a carry value), to calls (which may return an arbitrary number
/// of values).
///
/// As such, each use of a SelectionDAG computation must indicate the node that
/// computes it as well as which return value to use from that node.  This pair
/// of information is represented with the SDValue value type.
///
class SDValue {
  friend struct DenseMapInfo<SDValue>;

  SDNode *Node = nullptr; // The node defining the value we are using.
  unsigned ResNo = 0;     // Which return value of the node we are using.

  SDValue getValue(unsigned R) const {
    return SDValue(Node, R);
  }

SDValue RetValue =
    DAG.getCopyFromReg(Chain, DL, VA.getLocReg(), VA.getLocVT(), Glue);
Chain = RetValue.getValue(1);
Glue = RetValue.getValue(2);

InVals.push_back(Chain.getValue(0));

  // Use lwsp whenever possible.
  if (MI.getOpcode() == RV16K::LW && FrameReg == RV16K::X1 &&
      isShiftedUInt<8, 1>(Offset)) {
    const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
    MI.setDesc(TII.get(RV16K::LWSP));
  }

  // Use swsp whenever possible.
  if (MI.getOpcode() == RV16K::SW && FrameReg == RV16K::X1 &&
      isShiftedUInt<8, 1>(Offset)) {
    const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
    MI.setDesc(TII.get(RV16K::SWSP));
  }

def : Pat<(store GPR:$rs2, SP:$rs1), (SWSP GPR:$rs2, SP:$rs1, 0)>;
def : Pat<(store GPR:$rs2, (add SP:$rs1, uimm9_lsb0:$imm)),
          (SWSP GPR:$rs2, SP:$rs1, uimm9_lsb0:$imm)>;

  /// Methods with trivial inline returns are convenient points in the common
  /// codegen pass pipeline where targets may insert passes. Methods with
  /// out-of-line standard implementations are major CodeGen stages called by
  /// addMachinePasses. Some targets may override major stages when inserting
  /// passes is insufficient, but maintaining overriden stages is more work.
  ///

  /// addPreISelPasses - This method should add any "last minute" LLVM->LLVM
  /// passes (which are run just before instruction selector).
  virtual bool addPreISel() {
    return true;
  }

  /// addMachineSSAOptimization - Add standard passes that optimize machine
  /// instructions in SSA form.
  virtual void addMachineSSAOptimization();

  /// Add passes that optimize instruction level parallelism for out-of-order
  /// targets. These passes are run while the machine code is still in SSA
  /// form, so they can use MachineTraceMetrics to control their heuristics.
  ///
  /// All passes added here should preserve the MachineDominatorTree,
  /// MachineLoopInfo, and MachineTraceMetrics analyses.
  virtual bool addILPOpts() {
    return false;
  }

  /// This method may be implemented by targets that want to run passes
  /// immediately before register allocation.
  virtual void addPreRegAlloc() { }

  /// createTargetRegisterAllocator - Create the register allocator pass for
  /// this target at the current optimization level.
  virtual FunctionPass *createTargetRegisterAllocator(bool Optimized);

  /// addFastRegAlloc - Add the minimum set of target-independent passes that
  /// are required for fast register allocation.
  virtual void addFastRegAlloc(FunctionPass *RegAllocPass);

  /// addOptimizedRegAlloc - Add passes related to register allocation.
  /// LLVMTargetMachine provides standard regalloc passes for most targets.
  virtual void addOptimizedRegAlloc(FunctionPass *RegAllocPass);

  /// addPreRewrite - Add passes to the optimized register allocation pipeline
  /// after register allocation is complete, but before virtual registers are
  /// rewritten to physical registers.
  ///
  /// These passes must preserve VirtRegMap and LiveIntervals, and when running
  /// after RABasic or RAGreedy, they should take advantage of LiveRegMatrix.
  /// When these passes run, VirtRegMap contains legal physreg assignments for
  /// all virtual registers.
  virtual bool addPreRewrite() {
    return false;
  }

  /// This method may be implemented by targets that want to run passes after
  /// register allocation pass pipeline but before prolog-epilog insertion.
  virtual void addPostRegAlloc() { }

  /// Add passes that optimize machine instructions after register allocation.
  virtual void addMachineLateOptimization();

  /// This method may be implemented by targets that want to run passes after
  /// prolog-epilog insertion and before the second instruction scheduling pass.
  virtual void addPreSched2() { }

  /// addGCPasses - Add late codegen passes that analyze code for garbage
  /// collection. This should return true if GC info should be printed after
  /// these passes.
  virtual bool addGCPasses();

  /// Add standard basic block placement passes.
  virtual void addBlockPlacement();

  /// This pass may be implemented by targets that want to run passes
  /// immediately before machine code is emitted.
  virtual void addPreEmitPass() { }

  /// Targets may add passes immediately before machine code is emitted in this
  /// callback. This is called even later than `addPreEmitPass`.
  // FIXME: Rename `addPreEmitPass` to something more sensible given its actual
  // position and remove the `2` suffix here as this callback is what
  // `addPreEmitPass` *should* be but in reality isn't.
  virtual void addPreEmitPass2() {}

declare i16 @bar(i16*)

define i16 @foo() {
  %1 = alloca i16
  %2 = call i16 @bar(i16* %1)
  ret i16 %2
}

  if (Node->getOpcode() == ISD::FrameIndex) {
    SDLoc DL(Node);
    SDValue Imm = CurDAG->getTargetConstant(0, DL, MVT::i16);
    int FI = dyn_cast<FrameIndexSDNode>(Node)->getIndex();
    EVT VT = Node->getValueType(0);
    SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
    ReplaceNode(Node,
                CurDAG->getMachineNode(RV16K::ADDI, DL, VT, TFI, Imm));
    return;
  }

$ ~/workspace/llvm-project-build/bin/llc -mtriple=rv16k -verify-machineinstrs < 0003.ll
	.text
	.file	"<stdin>"

# After Instruction Selection
# Machine code for function foo: IsSSA, TracksLiveness
Frame Objects:
  fi#0: size=2, align=2, at location [SP]

bb.0 (%ir-block.0):
  ADJCALLSTACKDOWN 0, 0, implicit-def dead $x1, implicit $x1
  %0:gpr = ADDI %stack.0, 0, implicit-def dead $flags
  $x8 = COPY %0:gpr
  JAL @bar, <regmask $x0 $x2 $x3 $x4 $x5 $x6 $x7>, implicit-def dead $x0, implicit $x8, implicit-def $x1, implicit-def $x8
  ADJCALLSTACKUP 0, 0, implicit-def dead $x1, implicit $x1
  %1:gpr = COPY $x8
  $x8 = COPY %1:gpr
  PseudoRET implicit $x8

# End machine code for function foo.

*** Bad machine code: Tied use must be a register ***
- function:    foo
- basic block: %bb.0  (0x5647e963da08)
- instruction: %0:gpr = ADDI %stack.0, 0, implicit-def dead $flags
- operand 1:   %stack.0
LLVM ERROR: Found 1 machine code errors.

let hasSideEffects = 0, mayLoad = 0, mayStore = 0, Defs = [FLAGS] in
def FRMIDX : Pseudo<(outs GPR:$rd), (ins GPR:$rs, simm16:$imm), []>;

  if (Node->getOpcode() == ISD::FrameIndex) {
    // Convert the frameindex into a temp instruction that will hold the
    // effective address of the final stack slot.
    int FI = cast<FrameIndexSDNode>(Node)->getIndex();
    SDValue TFI = CurDAG->getTargetFrameIndex(FI, MVT::i16);

    CurDAG->SelectNodeTo(Node, RV16K::FRMIDX, MVT::i16, TFI,
                         CurDAG->getTargetConstant(0, SDLoc(Node), MVT::i16));
    return;
  }

  /// TiedTo - Non-zero when this register operand is tied to another register
  /// operand. The encoding of this field is described in the block comment
  /// before MachineInstr::tieOperands().
  unsigned TiedTo : 4;

  /// IsDef - True if this is a def, false if this is a use of the register.
  /// This is only valid on register operands.
  ///
  unsigned IsDef : 1;

  /// IsImp - True if this is an implicit def or use, false if it is explicit.
  /// This is only valid on register opderands.
  ///
  unsigned IsImp : 1;

  /// IsDeadOrKill
  /// For uses: IsKill - True if this instruction is the last use of the
  /// register on this path through the function.
  /// For defs: IsDead - True if this register is never used by a subsequent
  /// instruction.
  /// This is only valid on register operands.
  unsigned IsDeadOrKill : 1;

  /// See isRenamable().
  unsigned IsRenamable : 1;

  /// IsUndef - True if this register operand reads an "undef" value, i.e. the
  /// read value doesn't matter.  This flag can be set on both use and def
  /// operands.  On a sub-register def operand, it refers to the part of the
  /// register that isn't written.  On a full-register def operand, it is a
  /// noop.  See readsReg().
  ///
  /// This is only valid on registers.
  ///
  /// Note that an instruction may have multiple <undef> operands referring to
  /// the same register.  In that case, the instruction may depend on those
  /// operands reading the same dont-care value.  For example:
  ///
  ///   %1 = XOR undef %2, undef %2
  ///
  /// Any register can be used for %2, and its value doesn't matter, but
  /// the two operands must be the same register.
  ///
  unsigned IsUndef : 1;

  /// IsInternalRead - True if this operand reads a value that was defined
  /// inside the same instruction or bundle.  This flag can be set on both use
  /// and def operands.  On a sub-register def operand, it refers to the part
  /// of the register that isn't written.  On a full-register def operand, it
  /// is a noop.
  ///
  /// When this flag is set, the instruction bundle must contain at least one
  /// other def of the register.  If multiple instructions in the bundle define
  /// the register, the meaning is target-defined.
  unsigned IsInternalRead : 1;

  /// IsEarlyClobber - True if this MO_Register 'def' operand is written to
  /// by the MachineInstr before all input registers are read.  This is used to
  /// model the GCC inline asm '&' constraint modifier.
  unsigned IsEarlyClobber : 1;

  /// IsDebug - True if this MO_Register 'use' operand is in a debug pseudo,
  /// not a real instruction.  Such uses should be ignored during codegen.
  unsigned IsDebug : 1;

$ cat 0003.ll
declare i16 @bar(i16*)

define i16 @foo() {
  %1 = alloca i16
  %2 = call i16 @bar(i16* %1)
  ret i16 %2
}

$ ~/workspace/llvm-project-build/bin/llc -mtriple=rv16k -verify-machineinstrs -print-after=prologepilog < 0003.ll > /dev/null
# *** IR Dump After Prologue/Epilogue Insertion & Frame Finalization ***:
# Machine code for function foo: NoPHIs, TracksLiveness, NoVRegs
Frame Objects:
  fi#0: size=2, align=2, at location [SP-4]
  fi#1: size=2, align=2, at location [SP-2]

bb.0 (%ir-block.0):
  $x1 = frame-setup ADDI $x1(tied-def 0), -4, implicit-def $flags
  SW killed $x0, $x1, 2, implicit-def $flags
  $x8 = LI 0, implicit-def dead $flags
  $x8 = ADD killed $x8(tied-def 0), $x1, implicit-def dead $flags
  JAL @bar, <regmask $x0 $x2 $x3 $x4 $x5 $x6 $x7>, implicit-def dead $x0, implicit $x8, implicit-def $x1, implicit-def $x8
  $x0 = LW $x1, 2, implicit-def $flags
  $x1 = frame-destroy ADDI $x1(tied-def 0), 4, implicit-def $flags
  PseudoRET implicit $x8

# End machine code for function foo.

def : Pat<(seteq GPR:$lhs, GPR:$rhs),
          (SelectCCrr GPR:$lhs, GPR:$rhs, SETEQ, (LI 0), (LI 1))>;

def : Pat<(SelectCC GPR:$lhs, GPR:$rhs, (i16 imm:$imm), GPR:$src, GPR:$src2),
          (SelectCCrr GPR:$lhs, GPR:$rhs, i16imm:$imm, GPR:$src, GPR:$src2)>;

  /// Analyze the branching code at the end of MBB, returning
  /// true if it cannot be understood (e.g. it's a switch dispatch or isn't
  /// implemented for a target).  Upon success, this returns false and returns
  /// with the following information in various cases:
  ///
  /// 1. If this block ends with no branches (it just falls through to its succ)
  ///    just return false, leaving TBB/FBB null.
  /// 2. If this block ends with only an unconditional branch, it sets TBB to be
  ///    the destination block.
  /// 3. If this block ends with a conditional branch and it falls through to a
  ///    successor block, it sets TBB to be the branch destination block and a
  ///    list of operands that evaluate the condition. These operands can be
  ///    passed to other TargetInstrInfo methods to create new branches.
  /// 4. If this block ends with a conditional branch followed by an
  ///    unconditional branch, it returns the 'true' destination in TBB, the
  ///    'false' destination in FBB, and a list of operands that evaluate the
  ///    condition.  These operands can be passed to other TargetInstrInfo
  ///    methods to create new branches.
  ///
  /// Note that removeBranch and insertBranch must be implemented to support
  /// cases where this method returns success.
  ///
  /// If AllowModify is true, then this routine is allowed to modify the basic
  /// block (e.g. delete instructions after the unconditional branch).
  ///
  /// The CFG information in MBB.Predecessors and MBB.Successors must be valid
  /// before calling this function.
  virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                             MachineBasicBlock *&FBB,
                             SmallVectorImpl<MachineOperand> &Cond,
                             bool AllowModify = false) const {
    return true;
  }

  /// Return true if this is a branch which always
  /// transfers control flow to some other block.  The
  /// TargetInstrInfo::AnalyzeBranch method can be used to get more information
  /// about this branch.
  bool isUnconditionalBranch(QueryType Type = AnyInBundle) const {
    return isBranch(Type) & isBarrier(Type) & !isIndirectBranch(Type);
  }

  /// Remove the branching code at the end of the specific MBB.
  /// This is only invoked in cases where AnalyzeBranch returns success. It
  /// returns the number of instructions that were removed.
  /// If \p BytesRemoved is non-null, report the change in code size from the
  /// removed instructions.
  virtual unsigned removeBranch(MachineBasicBlock &MBB,
                                int *BytesRemoved = nullptr) const {
    llvm_unreachable("Target didn't implement TargetInstrInfo::removeBranch!");
  }

  /// Insert branch code into the end of the specified MachineBasicBlock. The
  /// operands to this method are the same as those returned by AnalyzeBranch.
  /// This is only invoked in cases where AnalyzeBranch returns success. It
  /// returns the number of instructions inserted. If \p BytesAdded is non-null,
  /// report the change in code size from the added instructions.
  ///
  /// It is also invoked by tail merging to add unconditional branches in
  /// cases where AnalyzeBranch doesn't apply because there was no original
  /// branch to analyze.  At least this much must be implemented, else tail
  /// merging needs to be disabled.
  ///
  /// The CFG information in MBB.Predecessors and MBB.Successors must be valid
  /// before calling this function.
  virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
                                MachineBasicBlock *FBB,
                                ArrayRef<MachineOperand> Cond,
                                const DebugLoc &DL,
                                int *BytesAdded = nullptr) const {
    llvm_unreachable("Target didn't implement TargetInstrInfo::insertBranch!");
  }

void RV16KPassConfig::addPreEmitPass2() {
  addPass(createRV16KExpandPseudoPass(), false, true);
}

int test(int a, int b)
{
    if (a < 0) {
        a += b;
        a += b;
        // ... 以下 a += b が続く
        a += b;
    }
    return a;
}

Branch relaxation is needed to support branch displacements that overflow the
instruction's immediate field.

// This method inserts a *direct* branch (JMP), despite its name.
// LLVM calls this method to fixup unconditional branches; it never calls
// insertBranch or some hypothetical "insertDirectBranch".
// See lib/CodeGen/RegisterRelaxation.cpp for details.
// We end up here when a jump is too long for a RJMP instruction.

// Old
let hasSideEffects = 0, mayStore = 0, mayLoad = 0,
    isBarrier = 1, isBranch = 1, isTerminator = 1 in
def PseudoBR : Pseudo<(outs), (ins simm16_lsb0_j:$imm15), [(br bb:$imm15)]>,
               PseudoInstExpansion<(J simm16_lsb0_j:$imm15)>;

// New
def : Pat<(br bb:$imm), (J simm16_lsb0_j:$imm)>;

def : InstAlias<"jr $rs",      (JALR X0, GPR:$rs, 0)>;

let isCall = 1, Defs=[X1] in
let isBarrier = 1, isBranch = 1, isIndirectBranch = 1, isTerminator = 1 in
def PseudoBRIND : Pseudo<(outs), (ins GPR:$rs1, simm12:$imm12), []>,
                  PseudoInstExpansion<(JALR X0, GPR:$rs1, simm12:$imm12)>;

def : Pat<(brind GPR:$rs1), (PseudoBRIND GPR:$rs1, 0)>;
def : Pat<(brind (add GPR:$rs1, simm12:$imm12)),
          (PseudoBRIND GPR:$rs1, simm12:$imm12)>;

def : Pat<(brind GPR:$rs), (JR GPR:$rs)>;
def : Pat<(Call GPR:$rs), (JALR GPR:$rs)>;

void jumpFront(const char *str, int *index)
{
    if (str[*index] != '[') return;
    for (int count = 0; str[*index] != '\0'; (*index)++) {
        if (str[*index] == '[')
            count++;
        else if (str[*index] == ']')
            count--;
        if (count == 0) break;
    }
}

void jumpBack(const char *str, int *index)
{
    if (str[*index] != ']') return;
    for (int count = 0; *index >= 0; (*index)--) {
        if (str[*index] == '[')
            count--;
        else if (str[*index] == ']')
            count++;
        if (count == 0) break;
    }
}

int brainfuck(const char *str)
{
    static int data[100];

    int pointer = sizeof(data) / sizeof(int) / 2;
    for (int index = 0; str[index] != '\0'; index++) {
        switch (str[index]) {
        case '+':
            data[pointer]++;
            break;
        case '-':
            data[pointer]--;
            break;
        case '>':
            pointer++;
            break;
        case '<':
            pointer--;
            break;
        case '.':
            break;
        case ',':
            break;
        case '[':
            if (data[pointer] == 0) jumpFront(str, &index);
            break;
        case ']':
            if (data[pointer] != 0) jumpBack(str, &index);
            break;
        }
    }
    return data[pointer];
}

int main()
{
    return brainfuck("+++++[>++++++++++<-]>++");
}

struct hoge {
    int ary[10];
};

int foo(struct hoge h)
{
    return h.ary[3];
}

int bar(void)
{
    struct hoge h;
    h.ary[3] = 10;
    return foo(h);
}

struct hoge piyo(int i)
{
    struct hoge h;
    h.ary[3] = i;
    return h;
}

struct hoge {
    int ary[10];
};

int foo(struct hoge);

struct hoge bar(int i)
{
    struct hoge h;
    h.ary[3] = i;
    h.ary[3] = foo(h);
    return h;
}

struct RT {
  char A;
  int B[10][20];
  char C;
};
struct ST {
  int X;
  double Y;
  struct RT Z;
};

int *foo(struct ST *s) {
  return &s[1].Z.B[5][13];
}

%struct.RT = type { i8, [10 x [20 x i32]], i8 }
%struct.ST = type { i32, double, %struct.RT }

define i32* @foo(%struct.ST* %s) nounwind uwtable readnone optsize ssp {
entry:
  %arrayidx = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1, i32 2, i32 1, i64 5, i64 13
  ret i32* %arrayidx
}

error: invalid operand in inline asm: 'add $1, $2'
error: invalid operand in inline asm: 'add $1, $2'

Although the register scavenger can often find a spare register, an emergency
spill slot is needed to guarantee success.

def : Pat<(br bb:$imm), (J simm16_lsb0_j:$imm)>;

ISEL: Starting selection on root node: t19: ch = br t21, BasicBlock:ch<test2 0x5577d143f220>
ISEL: Starting pattern match
  Match failed at index 0
LLVM ERROR: Cannot select: t19: ch = br t21, BasicBlock:ch<test2 0x5577d143f220>
In function: foo

/////////// INSERTED FOR DEBUG FROM HERE //////////
std::cerr << "PATTERN: ";
Pattern.dump();
std::cerr << "RESULT:  ";
Result.dump();
/////////// INSERTED FOR DEBUG   TO HERE //////////

ParseOnePattern(CurPattern, Pattern, Result, InstImpResults);

/////////// INSERTED FOR DEBUG FROM HERE //////////
std::cerr << "PATTERN: ";
Pattern.dump();
std::cerr << "RESULT:  ";
Result.dump();
std::cerr << ">>>>>>>>>>>>>>>\t" << std::boolalpha << Temp.getOnlyTree()->hasPossibleType() << std::endl;
/////////// INSERTED FOR DEBUG   TO HERE //////////

// A pattern may end up with an "impossible" type, i.e. a situation
// where all types have been eliminated for some node in this pattern.
// This could occur for intrinsics that only make sense for a specific
// value type, and use a specific register class. If, for some mode,
// that register class does not accept that type, the type inference
// will lead to a contradiction, which is not an error however, but
// a sign that this pattern will simply never match.
if (Temp.getOnlyTree()->hasPossibleType())
  for (auto T : Pattern.getTrees())
    if (T->hasPossibleType())
      AddPatternToMatch(&Pattern,
                        PatternToMatch(TheDef, makePredList(Preds),
                                       T, Temp.getOnlyTree(),
                                       InstImpResults, Complexity,
                                       TheDef->getID()));

PATTERN: anonymous_997: 	(br (bb:{ *:[Other] }):$imm)
RESULT:  anonymous_997: 	(J (imm:{ *:[] })<<P:Predicate_simm16_lsb0_j>>:$imm)
>>>>>>>>>>>>>>>	false

PATTERN: J:     (br (bb:{ *:[Other] }):$imm)
RESULT:  J:     (J (bb:{ *:[Other] }):$imm)
>>>>>>>>>>>>>>> true

def : Pat<(br bb:$imm), (J bb:$imm)>;

PATTERN: anonymous_997: 	(br (imm:{ *:[] })<<P:Predicate_simm16_lsb0_j>>:$imm)
RESULT:  anonymous_997: 	(J (imm:{ *:[] })<<P:Predicate_simm16_lsb0_j>>:$imm)
>>>>>>>>>>>>>>>	false

PATTERN: anonymous_1003:        (RV16KBrCC GPR:{ *:[i16] }:$lhs, GPR:{ *:[i16] }:$rhs, (bb:{ *:[Other] }):$dst, SETLE:{ *:[Other] })
RESULT:  anonymous_1003:        (Bcc:{ *:[i16] } GPR:{ *:[i16] }:$lhs, GPR:{ *:[i16] }:$rhs, simm8_lsb0:{ *:[Other] }:$dst, 1:{ *:[i16] })
>>>>>>>>>>>>>>> true

def simm16_lsb0_j : Operand<OtherVT> {

$ bin/clang -target rv16k -Oz bf.c -o bf.exe --sysroot=/path/to/rv16k-rt

ar rcs libc.a __mulhi3.o __divhi3.o ...

if (!isOptimizingForSize(Level))
  FPM.addPass(LibCallsShrinkWrapPass());

// For PGO use pipeline, try to optimize memory intrinsics such as memcpy
// using the size value profile. Don't perform this when optimizing for size.
if (PGOOpt && PGOOpt->Action == PGOOptions::IRUse &&
    !isOptimizingForSize(Level))
  FPM.addPass(PGOMemOPSizeOpt());

// Generally running simplification passes and the inliner with an high
// threshold results in smaller executables, but there may be cases where
// the size grows, so let's be conservative here and skip this simplification
// at -Os/Oz. We will not do this  inline for context sensistive PGO (when
// IsCS is true).
if (!isOptimizingForSize(Level) && !IsCS) {
  InlineParams IP;

  // In the old pass manager, this is a cl::opt. Should still this be one?
  IP.DefaultThreshold = 75;

  // FIXME: The hint threshold has the same value used by the regular inliner.
  // This should probably be lowered after performance testing.
  // FIXME: this comment is cargo culted from the old pass manager, revisit).
  IP.HintThreshold = 325;

  CGSCCPassManager CGPipeline(DebugLogging);

  CGPipeline.addPass(InlinerPass(IP));

  FunctionPassManager FPM;
  FPM.addPass(SROA());
  FPM.addPass(EarlyCSEPass());    // Catch trivial redundancies.
  FPM.addPass(SimplifyCFGPass()); // Merge & remove basic blocks.
  FPM.addPass(InstCombinePass()); // Combine silly sequences.
  invokePeepholeEPCallbacks(FPM, Level);

  CGPipeline.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM)));

  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPipeline)));
}

bool HasNativeLLVMSupport() const override { return true; }

case Triple::rv16k:
  return EM_RV16K;

$ cat foo.c
int factorial(int x)
{
    if (x > 0)
        return x * factorial(x - 1);
    else
        return 1;
}

int test_tailcall(int a)
{
    return factorial(a);
}

$ ./rv16k-clang -c -S -O1 foo.c -o foo.ll -emit-llvm

$ cat foo.s

...

; Function Attrs: nounwind readnone
define dso_local i16 @factorial(i16 %x) local_unnamed_addr #0 {
entry:
  %cmp3 = icmp sgt i16 %x, 0
  br i1 %cmp3, label %if.then, label %return

if.then:                                          ; preds = %entry, %if.then
  %x.tr5 = phi i16 [ %sub, %if.then ], [ %x, %entry ]
  %accumulator.tr4 = phi i16 [ %mul, %if.then ], [ 1, %entry ]
  %sub = add nsw i16 %x.tr5, -1
  %mul = mul nsw i16 %x.tr5, %accumulator.tr4
  %cmp = icmp sgt i16 %sub, 0
  br i1 %cmp, label %if.then, label %return

return:                                           ; preds = %if.then, %entry
  %accumulator.tr.lcssa = phi i16 [ 1, %entry ], [ %mul, %if.then ]
  ret i16 %accumulator.tr.lcssa
}

; Function Attrs: nounwind readnone
define dso_local i16 @test_tailcall(i16 %a) local_unnamed_addr #0 {
entry:
  %call = tail call i16 @factorial(i16 %a)
  ret i16 %call
}

...

def PseudoTAIL : Pseudo<(outs), (ins simm16_lsb0_j:$imm), []>,
                   PseudoInstExpansion<(J simm16_lsb0_j:$imm)>;

...

def : Pat<(Tail (iPTR tglobaladdr:$dst)),
          (PseudoTAIL texternalsym:$dst)>;

struct hoge {
    int x, y;
};

struct hoge piyo(struct hoge h)
{
    if (h.x < 0) return h;

    h.x -= 1;
    h.y -= 1;
    struct hoge ret = piyo(h);
    return ret;
}

int main()
{
    struct hoge h = {1, 2};
    return piyo(h).y;
}

Creating new node: t17: ch,glue = callseq_start t15, TargetConstant:i16<0>, TargetConstant:i16(0)
Creating new node: t19: ch,glue = CopyToReg t17, Register:i16 $x8, FrameIndex:i16(0)
Creating new node: t21: ch,glue = CopyToReg t19, Register:i16 $x9, FrameIndex:i16<1>, t19:1
Creating new node: t24: ch,glue = RV16KISD::CALL t21, TargetGlobalAddress:i16<void (%struct.hoge*, %struct.hoge*)* @piyo> 0, Register:i16 $x8, Register:i16 $x9, RegisterMask:Untyped, t21:1
Creating new node: t25: ch,glue = callseq_end t24, TargetConstant:i16<0>, TargetConstant:i16<0>, t24:1
Creating new node: t26: i16 = add nuw FrameIndex:i16<0>, Constant:i16(2)
Creating new node: t27: i16,ch = load<(dereferenceable load 2 from %ir.y, !tbaa !7)> t25, t26, undef:i16

...

Combining: t26: i16 = add nuw FrameIndex:i16<0>, Constant:i16(2)
Creating new node: t30: i16 = or FrameIndex:i16<0>, Constant:i16(2)
 ... into: t30: i16 = or FrameIndex:i16<0>, Constant:i16(2)

// fold (a+b) -> (a|b) iff a and b share no bits.
if ((!LegalOperations || TLI.isOperationLegal(ISD::OR, VT)) &&
    DAG.haveNoCommonBitsSet(N0, N1))
  return DAG.getNode(ISD::OR, DL, VT, N0, N1);

def : Pat<(load (IsOrAdd AddrFI:$rs1, simm16_lsb0:$imm16)),
          (LW AddrFI:$rs1, simm16_lsb0:$imm16)>;

def IsOrAdd: PatFrag<(ops node:$A, node:$B), (or node:$A, node:$B), [{
  return isOrEquivalentToAdd(N);
}]>;

ls ~/ano/secure_vm/rv16k-test/build_and_test/test/00*.c | \
while read line; do \
    echo $(basename $line); \
    echo "\tRV16K          $(bin/clang -target rv16k -Oz -c -o - $line | \
                     bin/llvm-readelf -S | \
                     grep " .text" | \
                     sed -E 's/ +/ /g' | \
                     cut -d' ' -f8)"; \
    echo "\tRV32EC (GCC)   $(~/workspace/riscv-gnu-toolchain/build/bin/riscv32-unknown-elf-gcc -march=rv32ec -mabi=ilp32e -Os -c -o _tetete.o $line && \
                      bin/llvm-readelf -S _tetete.o | \
                      sed -E 's/ +/ /g' | \
                      grep " .text" | \
                      cut -d' ' -f8 | \
                      awk '{s+=strtonum("0x"$1)} END {printf "%06x",s}' )"; rm -f _tetete.o; \
    echo "\tRV32IC (LLVM)  $(bin/clang -target riscv32 -march=rv32ic -Oz -c -o - $line | \
                      bin/llvm-readelf -S | \
                      grep " .text" | \
                      sed -E 's/ +/ /g' | \
                      cut -d' ' -f8)"; \
    echo "\tRV32IC (GCC)   $(~/workspace/riscv-gnu-toolchain/build/bin/riscv32-unknown-elf-gcc -march=rv32ic -mabi=ilp32e -Os -c -o _tetete.o $line && \
                      bin/llvm-readelf -S _tetete.o | \
                      sed -E 's/ +/ /g' | \
                      grep " .text" | \
                      cut -d' ' -f8 | \
                      awk '{s+=strtonum("0x"$1)} END {printf "%06x",s}' )"; rm -f _tetete.o; \
done

0001.c
    RV16K          000006
    RV32IC (LLVM)  000006
    RV32EC (GCC)   000006
0002-fib.c
    RV16K          00003e
    RV32IC (LLVM)  000044
    RV32EC (GCC)   00003c
0003-bf.c
    RV16K          000162
    RV32IC (LLVM)  0000f2
    RV32EC (GCC)   0001aa
0004-lisp.c
    RV16K          000176
    RV32IC (LLVM)  00016e
    RV32EC (GCC)   00017e
0005-prime.c
    RV16K          00009c
    RV32IC (LLVM)  000082
    RV32EC (GCC)   000082
0006-editdis.c
    RV16K          0000d6
    RV32IC (LLVM)  00009e
    RV32EC (GCC)   0000de
0007-perceptron.c
    RV16K          000148
    RV32IC (LLVM)  000132
    RV32EC (GCC)   000134
0008-rpn.c
    RV16K          000110
    RV32IC (LLVM)  0000e4
    RV32EC (GCC)   0000e2
0009-gameoflife.c
    RV16K          0001c4
    RV32IC (LLVM)  000166
    RV32EC (GCC)   000130
0010-struct.c
    RV16K          000100
    RV32IC (LLVM)  000090
    RV32EC (GCC)   0000a0

$ bin/llvm-objdump -d -riscv-no-aliases rpn-rv32ec.o | cut -f3 | egrep -v "^$|:" | sort | uniq -c | sort -nr

$ git rebase --onto llvmorg-9.0.0 llvmorg-8.0.0 rv16k-toward-v3

$ cmake -G Ninja \
    -DLLVM_ENABLE_PROJECTS="clang;lld" \
    -DCMAKE_BUILD_TYPE="Debug" \
    -DBUILD_SHARED_LIBS=True \
    -DLLVM_USE_SPLIT_DWARF=True \
    -DLLVM_OPTIMIZED_TABLEGEN=True \
    -DLLVM_BUILD_TESTS=True \
    -DCMAKE_C_COMPILER=clang \
    -DCMAKE_CXX_COMPILER=clang++ \
    -DLLVM_USE_LINKER=lld \
    -DLLVM_TARGETS_TO_BUILD="X86;RISCV" \
    -DLLVM_EXPERIMENTAL_TARGETS_TO_BUILD="RV16K" \
    ~/ano/secure_vm/llvm-project/llvm
    ../llvm
$ cmake --build .

0001.c
    RV16K          000006
    RV32EC (GCC)   000006
    RV32IC (LLVM)  000008
    RV32IC (GCC)   000006
0002-fib.c
    RV16K          00003a
    RV32EC (GCC)   00003c
    RV32IC (LLVM)  000046
    RV32IC (GCC)   00003c
0003-bf.c
    RV16K          00013a
    RV32EC (GCC)   0001aa
    RV32IC (LLVM)  0000e6
    RV32IC (GCC)   0000ec
0004-lisp.c
    RV16K          00013c
    RV32EC (GCC)   00017e
    RV32IC (LLVM)  00017a
    RV32IC (GCC)   00017e
0005-prime.c
    RV16K          00007a
    RV32EC (GCC)   000082
    RV32IC (LLVM)  000082
    RV32IC (GCC)   000082
0006-editdis.c
    RV16K          0000c2
    RV32EC (GCC)   0000de
    RV32IC (LLVM)  0000b0
    RV32IC (GCC)   0000ca
0007-perceptron.c
    RV16K          00013c
    RV32EC (GCC)   000134
    RV32IC (LLVM)  000158
    RV32IC (GCC)   000134
0008-rpn.c
    RV16K          0000fc
    RV32EC (GCC)   0000e2
    RV32IC (LLVM)  0000d8
    RV32IC (GCC)   0000e2
0009-gameoflife.c
    RV16K          0001c6
    RV32EC (GCC)   000130
    RV32IC (LLVM)  000176
    RV32IC (GCC)   000130
0010-struct.c
    RV16K          0000d0
    RV32EC (GCC)   0000a0
    RV32IC (LLVM)  000092
    RV32IC (GCC)   0000a4

    entry
      |
      V
-->for.body
|     |\
|     | \
|     |  \
|     | if.then3
|     |  /
|     | /
|     |/
---for.inc
      |
      V
for.cond.cleanup

entry
for.body
if.then3
for.inc
for.cond.cleanup

   ...
-> for.body
-> （ジャンプ） for.inc
-> （ジャンプ） for.body
   ...

entry
for.inc
for.body
if.then3
for.cond.cleanup

   ...
-> for.body
-> （ジャンプ） for.inc
-> for.body
   ...