From e4c8c807bb609daa9be3fb9977703355b119fe8c Mon Sep 17 00:00:00 2001 From: Alexei Starovoitov Date: Sat, 24 Jan 2015 17:51:26 +0000 Subject: BPF backend Summary: V8->V9: - cleanup tests V7->V8: - addressed feedback from David: - switched to range-based 'for' loops - fixed formatting of tests V6->V7: - rebased and adjusted AsmPrinter args - CamelCased .td, fixed formatting, cleaned up names, removed unused patterns - diffstat: 3 files changed, 203 insertions(+), 227 deletions(-) V5->V6: - addressed feedback from Chandler: - reinstated full verbose standard banner in all files - fixed variables that were not in CamelCase - fixed names of #ifdef in header files - removed redundant braces in if/else chains with single statements - fixed comments - removed trailing empty line - dropped debug annotations from tests - diffstat of these changes: 46 files changed, 456 insertions(+), 469 deletions(-) V4->V5: - fix setLoadExtAction() interface - clang-formated all where it made sense V3->V4: - added CODE_OWNERS entry for BPF backend V2->V3: - fix metadata in tests V1->V2: - addressed feedback from Tom and Matt - removed top level change to configure (now everything via 'experimental-backend') - reworked error reporting via DiagnosticInfo (similar to R600) - added few more tests - added cmake build - added Triple::bpf - tested on linux and darwin V1 cover letter: --------------------- recently linux gained "universal in-kernel virtual machine" which is called eBPF or extended BPF. The name comes from "Berkeley Packet Filter", since new instruction set is based on it. This patch adds a new backend that emits extended BPF instruction set. The concept and development are covered by the following articles: http://lwn.net/Articles/599755/ http://lwn.net/Articles/575531/ http://lwn.net/Articles/603983/ http://lwn.net/Articles/606089/ http://lwn.net/Articles/612878/ One of use cases: dtrace/systemtap alternative. bpf syscall manpage: https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=b4fc1a460f3017e958e6a8ea560ea0afd91bf6fe instruction set description and differences vs classic BPF: http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/Documentation/networking/filter.txt Short summary of instruction set: - 64-bit registers R0 - return value from in-kernel function, and exit value for BPF program R1 - R5 - arguments from BPF program to in-kernel function R6 - R9 - callee saved registers that in-kernel function will preserve R10 - read-only frame pointer to access stack - two-operand instructions like +, -, *, mov, load/store - implicit prologue/epilogue (invisible stack pointer) - no floating point, no simd Short history of extended BPF in kernel: interpreter in 3.15, x64 JIT in 3.16, arm64 JIT, verifier, bpf syscall in 3.18, more to come in the future. It's a very small and simple backend. There is no support for global variables, arbitrary function calls, floating point, varargs, exceptions, indirect jumps, arbitrary pointer arithmetic, alloca, etc. From C front-end point of view it's very restricted. It's done on purpose, since kernel rejects all programs that it cannot prove safe. It rejects programs with loops and with memory accesses via arbitrary pointers. When kernel accepts the program it is guaranteed that program will terminate and will not crash the kernel. This patch implements all 'must have' bits. There are several things on TODO list, so this is not the end of development. Most of the code is a boiler plate code, copy-pasted from other backends. Only odd things are lack or < and <= instructions, specialized load_byte intrinsics and 'compare and goto' as single instruction. Current instruction set is fixed, but more instructions can be added in the future. Signed-off-by: Alexei Starovoitov Subscribers: majnemer, chandlerc, echristo, joerg, pete, rengolin, kristof.beyls, arsenm, t.p.northover, tstellarAMD, aemerson, llvm-commits Differential Revision: http://reviews.llvm.org/D6494 llvm-svn: 227008 --- llvm/test/CodeGen/BPF/alu8.ll | 46 +++++ llvm/test/CodeGen/BPF/atomics.ll | 20 +++ llvm/test/CodeGen/BPF/basictest.ll | 28 +++ llvm/test/CodeGen/BPF/byval.ll | 27 +++ llvm/test/CodeGen/BPF/cc_args.ll | 96 +++++++++++ llvm/test/CodeGen/BPF/cc_ret.ll | 48 ++++++ llvm/test/CodeGen/BPF/cmp.ll | 119 +++++++++++++ llvm/test/CodeGen/BPF/ex1.ll | 46 +++++ llvm/test/CodeGen/BPF/intrinsics.ll | 50 ++++++ llvm/test/CodeGen/BPF/load.ll | 43 +++++ llvm/test/CodeGen/BPF/loops.ll | 111 ++++++++++++ llvm/test/CodeGen/BPF/many_args1.ll | 12 ++ llvm/test/CodeGen/BPF/many_args2.ll | 15 ++ llvm/test/CodeGen/BPF/sanity.ll | 117 +++++++++++++ llvm/test/CodeGen/BPF/setcc.ll | 99 +++++++++++ llvm/test/CodeGen/BPF/shifts.ll | 101 +++++++++++ llvm/test/CodeGen/BPF/sockex2.ll | 326 +++++++++++++++++++++++++++++++++++ llvm/test/CodeGen/BPF/struct_ret1.ll | 17 ++ llvm/test/CodeGen/BPF/struct_ret2.ll | 12 ++ llvm/test/CodeGen/BPF/vararg1.ll | 9 + 20 files changed, 1342 insertions(+) create mode 100644 llvm/test/CodeGen/BPF/alu8.ll create mode 100644 llvm/test/CodeGen/BPF/atomics.ll create mode 100644 llvm/test/CodeGen/BPF/basictest.ll create mode 100644 llvm/test/CodeGen/BPF/byval.ll create mode 100644 llvm/test/CodeGen/BPF/cc_args.ll create mode 100644 llvm/test/CodeGen/BPF/cc_ret.ll create mode 100644 llvm/test/CodeGen/BPF/cmp.ll create mode 100644 llvm/test/CodeGen/BPF/ex1.ll create mode 100644 llvm/test/CodeGen/BPF/intrinsics.ll create mode 100644 llvm/test/CodeGen/BPF/load.ll create mode 100644 llvm/test/CodeGen/BPF/loops.ll create mode 100644 llvm/test/CodeGen/BPF/many_args1.ll create mode 100644 llvm/test/CodeGen/BPF/many_args2.ll create mode 100644 llvm/test/CodeGen/BPF/sanity.ll create mode 100644 llvm/test/CodeGen/BPF/setcc.ll create mode 100644 llvm/test/CodeGen/BPF/shifts.ll create mode 100644 llvm/test/CodeGen/BPF/sockex2.ll create mode 100644 llvm/test/CodeGen/BPF/struct_ret1.ll create mode 100644 llvm/test/CodeGen/BPF/struct_ret2.ll create mode 100644 llvm/test/CodeGen/BPF/vararg1.ll (limited to 'llvm/test/CodeGen') diff --git a/llvm/test/CodeGen/BPF/alu8.ll b/llvm/test/CodeGen/BPF/alu8.ll new file mode 100644 index 00000000000..0233225f81b --- /dev/null +++ b/llvm/test/CodeGen/BPF/alu8.ll @@ -0,0 +1,46 @@ +; RUN: llc -march=bpf -show-mc-encoding < %s | FileCheck %s +; test little endian only for now + +define i8 @mov(i8 %a, i8 %b) nounwind { +; CHECK-LABEL: mov: +; CHECK: mov r0, r2 # encoding: [0xbf,0x20,0x00,0x00,0x00,0x00,0x00,0x00] +; CHECK: ret # encoding: [0x95,0x00,0x00,0x00,0x00,0x00,0x00,0x00] + ret i8 %b +} + +define i8 @add(i8 %a, i8 %b) nounwind { +; CHECK-LABEL: add: +; CHECK: add r1, r2 # encoding: [0x0f,0x21,0x00,0x00,0x00,0x00,0x00,0x00] +; CHECK: mov r0, r1 # encoding: [0xbf,0x10,0x00,0x00,0x00,0x00,0x00,0x00] + %1 = add i8 %a, %b + ret i8 %1 +} + +define i8 @and(i8 %a, i8 %b) nounwind { +; CHECK-LABEL: and: +; CHECK: and r1, r2 # encoding: [0x5f,0x21,0x00,0x00,0x00,0x00,0x00,0x00] + %1 = and i8 %a, %b + ret i8 %1 +} + +define i8 @bis(i8 %a, i8 %b) nounwind { +; CHECK-LABEL: bis: +; CHECK: or r1, r2 # encoding: [0x4f,0x21,0x00,0x00,0x00,0x00,0x00,0x00] + %1 = or i8 %a, %b + ret i8 %1 +} + +define i8 @xorand(i8 %a, i8 %b) nounwind { +; CHECK-LABEL: xorand: +; CHECK: xori r2, -1 # encoding: [0xa7,0x02,0x00,0x00,0xff,0xff,0xff,0xff] + %1 = xor i8 %b, -1 + %2 = and i8 %a, %1 + ret i8 %2 +} + +define i8 @xor(i8 %a, i8 %b) nounwind { +; CHECK-LABEL: xor: +; CHECK: xor r1, r2 # encoding: [0xaf,0x21,0x00,0x00,0x00,0x00,0x00,0x00] + %1 = xor i8 %a, %b + ret i8 %1 +} diff --git a/llvm/test/CodeGen/BPF/atomics.ll b/llvm/test/CodeGen/BPF/atomics.ll new file mode 100644 index 00000000000..2f9730dddde --- /dev/null +++ b/llvm/test/CodeGen/BPF/atomics.ll @@ -0,0 +1,20 @@ +; RUN: llc < %s -march=bpf -verify-machineinstrs -show-mc-encoding | FileCheck %s +; test little endian only for now + +; CHECK-LABEL: test_load_add_32 +; CHECK: xadd32 +; CHECK: encoding: [0xc3 +define void @test_load_add_32(i32* %p, i32 zeroext %v) { +entry: + atomicrmw add i32* %p, i32 %v seq_cst + ret void +} + +; CHECK-LABEL: test_load_add_64 +; CHECK: xadd64 +; CHECK: encoding: [0xdb +define void @test_load_add_64(i64* %p, i64 zeroext %v) { +entry: + atomicrmw add i64* %p, i64 %v seq_cst + ret void +} diff --git a/llvm/test/CodeGen/BPF/basictest.ll b/llvm/test/CodeGen/BPF/basictest.ll new file mode 100644 index 00000000000..0cbfff83442 --- /dev/null +++ b/llvm/test/CodeGen/BPF/basictest.ll @@ -0,0 +1,28 @@ +; RUN: llc < %s -march=bpf | FileCheck %s + +define i32 @test0(i32 %X) { + %tmp.1 = add i32 %X, 1 + ret i32 %tmp.1 +; CHECK-LABEL: test0: +; CHECK: addi r1, 1 +} + +; CHECK-LABEL: store_imm: +; CHECK: stw 0(r1), r0 +; CHECK: stw 4(r2), r0 +define i32 @store_imm(i32* %a, i32* %b) { +entry: + store i32 0, i32* %a, align 4 + %0 = getelementptr inbounds i32* %b, i32 1 + store i32 0, i32* %0, align 4 + ret i32 0 +} + +@G = external global i8 +define zeroext i8 @loadG() { + %tmp = load i8* @G + ret i8 %tmp +; CHECK-LABEL: loadG: +; CHECK: ld_64 r1 +; CHECK: ldb r0, 0(r1) +} diff --git a/llvm/test/CodeGen/BPF/byval.ll b/llvm/test/CodeGen/BPF/byval.ll new file mode 100644 index 00000000000..065604b29e9 --- /dev/null +++ b/llvm/test/CodeGen/BPF/byval.ll @@ -0,0 +1,27 @@ +; RUN: not llc -march=bpf < %s 2> %t1 +; RUN: FileCheck %s < %t1 +; CHECK: by value not supported + +%struct.S = type { [10 x i32] } + +; Function Attrs: nounwind uwtable +define void @bar(i32 %a) #0 { +entry: + %.compoundliteral = alloca %struct.S, align 8 + %arrayinit.begin = getelementptr inbounds %struct.S* %.compoundliteral, i64 0, i32 0, i64 0 + store i32 1, i32* %arrayinit.begin, align 8 + %arrayinit.element = getelementptr inbounds %struct.S* %.compoundliteral, i64 0, i32 0, i64 1 + store i32 2, i32* %arrayinit.element, align 4 + %arrayinit.element2 = getelementptr inbounds %struct.S* %.compoundliteral, i64 0, i32 0, i64 2 + store i32 3, i32* %arrayinit.element2, align 8 + %arrayinit.start = getelementptr inbounds %struct.S* %.compoundliteral, i64 0, i32 0, i64 3 + %scevgep4 = bitcast i32* %arrayinit.start to i8* + call void @llvm.memset.p0i8.i64(i8* %scevgep4, i8 0, i64 28, i32 4, i1 false) + call void @foo(i32 %a, %struct.S* byval align 8 %.compoundliteral) #3 + ret void +} + +declare void @foo(i32, %struct.S* byval align 8) #1 + +; Function Attrs: nounwind +declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) #3 diff --git a/llvm/test/CodeGen/BPF/cc_args.ll b/llvm/test/CodeGen/BPF/cc_args.ll new file mode 100644 index 00000000000..5085fe5684e --- /dev/null +++ b/llvm/test/CodeGen/BPF/cc_args.ll @@ -0,0 +1,96 @@ +; RUN: llc < %s -march=bpf -show-mc-encoding | FileCheck %s +; test little endian only for now + +define void @test() #0 { +entry: +; CHECK: test: + +; CHECK: mov r1, 123 # encoding: [0xb7,0x01,0x00,0x00,0x7b,0x00,0x00,0x00] +; CHECK: call f_i16 + call void @f_i16(i16 123) + +; CHECK: mov r1, 12345678 # encoding: [0xb7,0x01,0x00,0x00,0x4e,0x61,0xbc,0x00] +; CHECK: call f_i32 + call void @f_i32(i32 12345678) + +; CHECK: ld_64 r1, 72623859790382856 # encoding: [0x18,0x01,0x00,0x00,0x08,0x07,0x06,0x05,0x00,0x00,0x00,0x00,0x04,0x03,0x02,0x01] +; CHECK: call f_i64 + call void @f_i64(i64 72623859790382856) + +; CHECK: mov r1, 1234 +; CHECK: mov r2, 5678 +; CHECK: call f_i32_i32 + call void @f_i32_i32(i32 1234, i32 5678) + +; CHECK: mov r1, 2 +; CHECK: mov r2, 3 +; CHECK: mov r3, 4 +; CHECK: call f_i16_i32_i16 + call void @f_i16_i32_i16(i16 2, i32 3, i16 4) + +; CHECK: mov r1, 5 +; CHECK: ld_64 r2, 7262385979038285 +; CHECK: mov r3, 6 +; CHECK: call f_i16_i64_i16 + call void @f_i16_i64_i16(i16 5, i64 7262385979038285, i16 6) + + ret void +} + +@g_i16 = common global i16 0, align 2 +@g_i32 = common global i32 0, align 2 +@g_i64 = common global i64 0, align 4 + +define void @f_i16(i16 %a) #0 { +; CHECK: f_i16: +; CHECK: sth 0(r2), r1 # encoding: [0x6b,0x12,0x00,0x00,0x00,0x00,0x00,0x00] + store volatile i16 %a, i16* @g_i16, align 2 + ret void +} + +define void @f_i32(i32 %a) #0 { +; CHECK: f_i32: +; CHECK: sth 0(r2), r1 # encoding: [0x6b,0x12,0x00,0x00,0x00,0x00,0x00,0x00] +; CHECK: sth 2(r2), r1 # encoding: [0x6b,0x12,0x02,0x00,0x00,0x00,0x00,0x00] + store volatile i32 %a, i32* @g_i32, align 2 + ret void +} + +define void @f_i64(i64 %a) #0 { +; CHECK: f_i64: +; CHECK: stw 0(r2), r1 +; CHECK: stw 4(r2), r1 # encoding: [0x63,0x12,0x04,0x00,0x00,0x00,0x00,0x00] + store volatile i64 %a, i64* @g_i64, align 2 + ret void +} + +define void @f_i32_i32(i32 %a, i32 %b) #0 { +; CHECK: f_i32_i32: +; CHECK: stw 0(r3), r1 + store volatile i32 %a, i32* @g_i32, align 4 +; CHECK: stw 0(r3), r2 + store volatile i32 %b, i32* @g_i32, align 4 + ret void +} + +define void @f_i16_i32_i16(i16 %a, i32 %b, i16 %c) #0 { +; CHECK: f_i16_i32_i16: +; CHECK: sth 0(r4), r1 + store volatile i16 %a, i16* @g_i16, align 2 +; CHECK: stw 0(r1), r2 + store volatile i32 %b, i32* @g_i32, align 4 +; CHECK: sth 0(r4), r3 + store volatile i16 %c, i16* @g_i16, align 2 + ret void +} + +define void @f_i16_i64_i16(i16 %a, i64 %b, i16 %c) #0 { +; CHECK: f_i16_i64_i16: +; CHECK: sth 0(r4), r1 + store volatile i16 %a, i16* @g_i16, align 2 +; CHECK: std 0(r1), r2 # encoding: [0x7b,0x21,0x00,0x00,0x00,0x00,0x00,0x00] + store volatile i64 %b, i64* @g_i64, align 8 +; CHECK: sth 0(r4), r3 + store volatile i16 %c, i16* @g_i16, align 2 + ret void +} diff --git a/llvm/test/CodeGen/BPF/cc_ret.ll b/llvm/test/CodeGen/BPF/cc_ret.ll new file mode 100644 index 00000000000..e32b17bcc61 --- /dev/null +++ b/llvm/test/CodeGen/BPF/cc_ret.ll @@ -0,0 +1,48 @@ +; RUN: llc < %s -march=bpf | FileCheck %s + +define void @test() #0 { +entry: +; CHECK: test: + +; CHECK: call f_i16 +; CHECK: sth 0(r1), r0 + %0 = call i16 @f_i16() + store volatile i16 %0, i16* @g_i16 + +; CHECK: call f_i32 +; CHECK: stw 0(r1), r0 + %1 = call i32 @f_i32() + store volatile i32 %1, i32* @g_i32 + +; CHECK: call f_i64 +; CHECK: std 0(r1), r0 + %2 = call i64 @f_i64() + store volatile i64 %2, i64* @g_i64 + + ret void +} + +@g_i16 = common global i16 0, align 2 +@g_i32 = common global i32 0, align 2 +@g_i64 = common global i64 0, align 2 + +define i16 @f_i16() #0 { +; CHECK: f_i16: +; CHECK: mov r0, 1 +; CHECK: ret + ret i16 1 +} + +define i32 @f_i32() #0 { +; CHECK: f_i32: +; CHECK: mov r0, 16909060 +; CHECK: ret + ret i32 16909060 +} + +define i64 @f_i64() #0 { +; CHECK: f_i64: +; CHECK: ld_64 r0, 72623859790382856 +; CHECK: ret + ret i64 72623859790382856 +} diff --git a/llvm/test/CodeGen/BPF/cmp.ll b/llvm/test/CodeGen/BPF/cmp.ll new file mode 100644 index 00000000000..b353f90ab56 --- /dev/null +++ b/llvm/test/CodeGen/BPF/cmp.ll @@ -0,0 +1,119 @@ +; RUN: llc < %s -march=bpf | FileCheck %s + +; Function Attrs: nounwind readnone uwtable +define signext i8 @foo_cmp1(i8 signext %a, i8 signext %b) #0 { + %1 = icmp sgt i8 %a, %b + br i1 %1, label %2, label %4 + +;