This is an archive of the discontinued LLVM Phabricator instance.

BPF backend
ClosedPublic

Authored by ast on Dec 2 2014, 7:08 PM.

Details

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 <alexei.starovoitov@gmail.com>

Diff Detail

Repository
rL LLVM

Event Timeline

ast updated this revision to Diff 16846.Dec 2 2014, 7:08 PM
ast retitled this revision from to [RFC PATCH] BPF backend.
ast updated this object.
ast edited the test plan for this revision. (Show Details)
ast added a subscriber: Unknown Object (MLST).
tstellarAMD added inline comments.Dec 3 2014, 1:53 PM
configure
5309–5315 ↗(On Diff #16846)

You need to add this target to the CMake build system too.

lib/Target/BPF/BPFISelLowering.cpp
434–435 ↗(On Diff #16846)

Coding style: Bracket should be on same line as function.

436–456 ↗(On Diff #16846)

You may be able to simplify this using ISD::getSetCCSwappedOperands().

lib/Target/BPF/BPFInstrInfo.td
96–99 ↗(On Diff #16846)

You don't need to specify register classes any more, so you can rewrite this pattern as:

(BPFbrcc i64:$rA, i64:$rX, Cond, bb:$dst)]

Some comment for most other patterns in this file.

501–504 ↗(On Diff #16846)

I did not realize this was possible. Does the instruction selector add R0 as an implicit def?

lib/Target/BPF/BPFRegisterInfo.td
7–8 ↗(On Diff #16846)

I'm not sure what you are using Num here for, but Register has a HWEncoding field which is accessible from the CodeEmitter if you need it.

lib/Target/BPF/MCTargetDesc/BPFBaseInfo.h
14–30 ↗(On Diff #16846)

See my previous comment about the HWEncoding field for registers, you can have TableGen generate this for you.

lib/Target/BPF/MCTargetDesc/BPFMCCodeEmitter.cpp
127–147 ↗(On Diff #16846)

Why can't you just emit the value returned by getBinaryCodeForInstr() directly without re-ordering the bytes?

Please let me know your feedback and steps to get it merged.

Could I ask who's going to maintain this backend? Targets without an
active LLVM sub-community behind them tend to slowly bit-rot until
everyone else gets fed up enough with fixing it when they refactor
things; they then get removed.

Cheers.

Tim.

arsenm added a subscriber: arsenm.Dec 3 2014, 5:25 PM
arsenm added inline comments.
lib/Target/BPF/BPFISelLowering.cpp
109 ↗(On Diff #16846)

You aren't using setBooleanContents. I'm guessing you probably want ZeroOrOneBooleanContent rather than the default UndefinedBooleanContent. Also since there isn' a select, you might want to look into SelectIsExpensive

473–474 ↗(On Diff #16846)

I think you can get away without custom lowering select_cc, and just select from the generic select_cc node, since you just select to a pseudo anyway and have to custom inserter.

484 ↗(On Diff #16846)

This should be a getTargetConstant

487–492 ↗(On Diff #16846)

You can use a statically sized array for this

565–568 ↗(On Diff #16846)

The usual style is to have each .add* on a separate line

lib/Target/BPF/BPFInstrInfo.cpp
140 ↗(On Diff #16846)

Dead code

lib/Target/BPF/BPFInstrInfo.td
77 ↗(On Diff #16846)

It's probably better to just not set this

lib/Target/BPF/BPFRegisterInfo.cpp
33–34 ↗(On Diff #16846)

A comment about why these are reserved might be helpful

lib/Target/BPF/BPFSubtarget.h
24 ↗(On Diff #16846)

I don't think you need this include here

lib/Target/BPF/InstPrinter/BPFInstPrinter.cpp
7 ↗(On Diff #16846)

DEBUG_TYPE should now go below all includes

62 ↗(On Diff #16846)

You might want to use formatImm/formatDec/formatHex instead of directly writing the immediate this way.

70 ↗(On Diff #16846)

Single quotes around '(' ')'

lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp
58–62 ↗(On Diff #16846)

Dead code

arsenm added inline comments.Dec 3 2014, 5:25 PM
lib/Target/BPF/BPFAsmPrinter.cpp
66–67 ↗(On Diff #16846)

Should remove this dead code

lib/Target/BPF/BPFFrameLowering.h
26 ↗(On Diff #16846)

This comment should be removed

lib/Target/BPF/BPFISelDAGToDAG.cpp
103 ↗(On Diff #16846)

DEBUG() printing should print to dbgs(), not errs(). This should also use single quotes around '\n'

112–113 ↗(On Diff #16846)

I think you should delete this error. Just printing the undef node isn't really useful, and it's better to just let this fall to the generic cannot select error

152–157 ↗(On Diff #16846)

You can put all of these under a single DEBUG()

lib/Target/BPF/BPFISelLowering.cpp
46–49 ↗(On Diff #16846)

You could try using the backend error reporting that's now available. R600 uses this for calls and some other things. I've been thinking it might be good to add an Unsupported legalize action to emit these sort of errors generically

160–166 ↗(On Diff #16846)

This should probably just be llvm_unreachable with a message

189–191 ↗(On Diff #16846)

You can usually print to a stream with *FunctionType rather than separately calling dump

495 ↗(On Diff #16846)

This is probably a pretty noisy debug statement, and I don't think any other targets have printing like this in their Lower*. Also dump without a DAG tends to crash frequently

lib/Target/BPF/BPFInstrInfo.h
23–26 ↗(On Diff #16846)

This and everywhere else should use override

lib/Target/BPF/MCTargetDesc/BPFBaseInfo.h
14 ↗(On Diff #16846)

You don't need this function. See MCRegisterInfo::getEncodingValue

lib/Target/BPF/MCTargetDesc/BPFELFObjectWriter.cpp
39–44 ↗(On Diff #16846)

You can just return the value from here, no need for Type

I believe you should be able to do what you want using llvm-objdump.
It's used quite often in the tests; just grep for "llvm-objdump"
in the test sub-directory.
One example is test/MC/ARM/align_thumb_2_arm.s

Thanks,

Kristof

ast updated this revision to Diff 17069.Dec 8 2014, 8:57 PM
ast retitled this revision from [RFC PATCH] BPF backend to [RFC v2] BPF backend.
ast added subscribers: rengolin, pete, joerg and 2 others.

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

cc-ing everyone from previous thread.
Thanks!

ast updated this revision to Diff 17377.Dec 16 2014, 8:44 PM
ast retitled this revision from [RFC v2] BPF backend to [RFC v3] BPF backend.

V2->V3:

  • patch bit-rotted a bit... rebased and fixed 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
ast updated this revision to Diff 17480.Dec 18 2014, 7:25 PM
ast retitled this revision from [RFC v3] BPF backend to [RFC v4] BPF backend.
ast updated this object.

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
ast updated this revision to Diff 18042.Jan 12 2015, 1:06 PM
ast retitled this revision from [RFC v4] BPF backend to [v5] BPF backend.
ast updated this object.

V4->V5:

  • rebased and fixed setLoadExtAction() interface
  • clang-formated all where it made sense

I'm still not sure who suppose to approve it.

A bunch of miscellaneous code hygiene comments here. While these are fairly trivial, when a backend is coming into the project is the best time to do this kind of audit and get these things cleaned up. I've generally only commented once on issues even if they repeated. Please check for other instances of the coding standards stuff.

The thing which is most important is the banner. The banner at the top of files should always be preserved.

Note that I may have some suggestions here that are just out of the norm for backends as I'm not a backend expert. I've tried to check myself against them, and the backends I reference the most are the AArch64 backend and the X86 backend, but I may still just have some stuff wrong. Mostly, I'm focusing on general LLVM coding suggestions, and fairly high-level stuff. I generally trust that the logic and functionality is in good shape.

Two high level things that I noticed going through this which you might want to address in follow-up patches (but that are too invasive IMO to try to do prior to it going in, and much lower risk of not getting cleaned up):

  1. There seems to be inconsistency with whether single-statement if's or 'else's are braced or un-braced. My mild preference is to not use braces when all branches on the if/else chain are single statements, but I don't really care which as long as it is reasonably consistent within the backend.
  2. There seem to be functions that would benefit from being split apart into static helper functions if just to comment the different sections and separate the logic better. This is mostly in the ISelLowering code.

I've not been able to spot check the .td files very much as I'm not an expert there.

I'd also love to get on MC expert to sign off on the assembler, disassembler, and general MC-layer sanity of the backend. In particular to make sure that all the important features, functionality, etc. are provided here so that this doesn't add yet another backend we have to update / migrate to newer tech.

I'll take another pass over the C++ code after you've done some of this cleanup.

include/llvm/IR/IntrinsicsBPF.td
1–6 ↗(On Diff #18042)

Missing the bottom of the banner on this file. Please make it look exactly like the other intrinsics files.

17 ↗(On Diff #18042)

I would trim trailing blank lines.

lib/Target/BPF/BPF.h
1–3 ↗(On Diff #18042)

Please don't alter the banner at the top of each file. All of the files should have the standard banner.

5–6 ↗(On Diff #18042)

Please follow the macro naming convention of the rest of LLVM, so for example LLVM_LIB_TARGET_AARCH64_AARCH64_H.

14–15 ↗(On Diff #18042)
18 ↗(On Diff #18042)

I prefer the X86 backend's pattern of declaring the extern targets explicitly in the few files they are needed rather than a header. I would declare them as locally as is reasonable.

lib/Target/BPF/BPF.td
8 ↗(On Diff #18042)

These aren't subtarget features...

lib/Target/BPF/BPFISelLowering.cpp
83–84 ↗(On Diff #18042)

s/tm/TM/

183 ↗(On Diff #18042)

Without the horizontal rule, the centered comment text really doesn't work.

I don't care whether you use the horizontal rule style of commenting or not within the code itself (I don't care for horizontal rules, but I don't feel strongly about it), if you don't use it, don't center the text and do something else to set off the comment. Not sure that's even necessary here though given the include.

198–199 ↗(On Diff #18042)

doxygen comment in the middle of the function?

264–266 ↗(On Diff #18042)

Variable naming in LLVM is still 'ProudCamelCase', so these should be IsFooBar.

280–281 ↗(On Diff #18042)

Another doxygen comment in the function body...

540 ↗(On Diff #18042)

s/dl/DL/

ast added a comment.Jan 14 2015, 12:12 AM

There seems to be inconsistency with whether single-statement if's or 'else's are braced or un-braced

in general I've tried not to waste extra line on a last brace for single line statements, but looks like
I've missed few cases.. will double check.

The thing which is most important is the banner. The banner at the top of files should always be preserved.

the banner felt way too verbose. I kept copyright and general text, but removed ----- lines.
Sure. Will restore verbosity :)

Thank you for the review!

include/llvm/IR/IntrinsicsBPF.td
1–6 ↗(On Diff #18042)

you mean something like:
===----------------------------------------------------------------------===

This file defines all of the X86-specific intrinsics.

===----------------------------------------------------------------------===//

I felt that all these unnecessary verbose lines don't provide any
information into the logic of the file. Only increase line count...
Sure... will restore verbosity here and everywhere.

17 ↗(On Diff #18042)

ok

lib/Target/BPF/BPF.h
1–3 ↗(On Diff #18042)

sure. just tried to reduce verbosity...

5–6 ↗(On Diff #18042)

ok

14–15 ↗(On Diff #18042)

was a copy-paste from MSP430... Sure. will fix in other places. here just going to remove it to match style of other backends.

18 ↗(On Diff #18042)

that was the style of R600 and NVPTX, Yes, makes sense to reduce the scope.

lib/Target/BPF/BPF.td
8 ↗(On Diff #18042)

copy paste left over. good catch. thanks

lib/Target/BPF/BPFISelLowering.cpp
83–84 ↗(On Diff #18042)

hexagon and systemz are using lower case... sure. will upper case it, since that's a preferred way.

183 ↗(On Diff #18042)

I wish I knew why arm, aarch64 and others are doing this way...
the only thing I did is dropped:
===----------------------------------------------------------------------===
around it that looks way too verbose to me.
Agree. It looks out of place with the rest. Will simplify.

198–199 ↗(On Diff #18042)

in the earlier versions it was a helper function with single caller. I manually inlined it and kept the comment.
I guess that's what you were hinting about splitting them up into helpers. Will uninline.

264–266 ↗(On Diff #18042)

Actually that part of coding style is the most confusing:
$ git grep isVarArg|wc -l
476
$ git grep IsVarArg|wc -l
126

I see the same in x86, sparc and other backends....
so I think I picked the right one...

280–281 ↗(On Diff #18042)

will uninline into helper

540 ↗(On Diff #18042)

I don't think there is a consistency:
$ git grep 'SDLoc dl('|wc -l
499
$ git grep 'SDLoc DL('|wc -l
326

I think I picked the right one...

ast updated this revision to Diff 18208.Jan 14 2015, 6:59 PM
ast retitled this revision from [v5] BPF backend to [v6] BPF backend.
ast updated this object.
ast added a reviewer: chandlerc.

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
  • decided not to introduce helpers for LowerCall*() since there is no common bits and logic pretty contained. All of them are much shorter than corresponding functions from other backends diffstat of these changes: 46 files changed, 456 insertions(+), 469 deletions(-)

Chandler, please take another look.
Thanks

ast updated this revision to Diff 18408.Jan 19 2015, 6:03 PM
ast retitled this revision from [v6] BPF backend to [v7] BPF backend.
ast updated this object.

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(-)
majnemer added inline comments.
lib/Target/BPF/BPFISelLowering.cpp
261–263 ↗(On Diff #18408)

Any reason these SmallVectors can't be SmallVectorImpl ?

296 ↗(On Diff #18408)

Would a range-based for loop be more concise?

345 ↗(On Diff #18408)

Would a range-based for loop be more concise?

362 ↗(On Diff #18408)

Consider reserving RegsToPass.size() + 3 elements to reduce the number of allocations.

368–370 ↗(On Diff #18408)

Would a range-based for loop be more concise?

417 ↗(On Diff #18408)

Would a range-based for loop be more concise?

458 ↗(On Diff #18408)

Would a range-based for loop be more concise?

lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp
71 ↗(On Diff #18408)

Is this code independent of endianness?

test/CodeGen/BPF/alu8.ll
36–38 ↗(On Diff #18408)

Can the leading whitespace of these instructions match the style of the surrounding test case?

ast added a comment.Jan 19 2015, 10:19 PM

Thanks for the review!
Will wait for more feedback and repost then.

lib/Target/BPF/BPFISelLowering.cpp
210 ↗(On Diff #18408)

concisified this one as well

261–263 ↗(On Diff #18408)

doable, but probably better to use auto then...

296 ↗(On Diff #18408)

yep. done

345 ↗(On Diff #18408)

done

362 ↗(On Diff #18408)

that's an overkill. bpf calling convention is set to max of 5 arguments, so 8 here will never trigger a resize.

368–370 ↗(On Diff #18408)

done

417 ↗(On Diff #18408)

not here, since OutVals is spoiling clean loop.

458 ↗(On Diff #18408)

done

lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp
71 ↗(On Diff #18408)

It is in cpu endianness. This 2 bytes is a relative offset in jump instructions. Thanks for checking ;)

test/CodeGen/BPF/alu8.ll
36–38 ↗(On Diff #18408)

good catch! fixed.

ast updated this revision to Diff 18468.Jan 20 2015, 5:28 PM
ast retitled this revision from [v7] BPF backend to [v8] BPF backend.
ast updated this object.

V7->V8:

  • addressed feedback from David:
  • switched to range-based 'for' loops
  • fixed formatting of tests
  • diffstat: 8 files changed, 117 insertions(+), 120 deletions(-)
ast updated this revision to Diff 18722.Jan 24 2015, 9:37 AM
ast retitled this revision from [v8] BPF backend to BPF backend.
ast updated this object.
ast removed a reviewer: chandlerc.
ast set the repository for this revision to rL LLVM.

V8->V9:

  • final cleanup of tests and commit log
Closed by commit rL227008: BPF backend (authored by ast). · Explain WhyJan 24 2015, 9:53 AM
This revision was automatically updated to reflect the committed changes.
ealfie added a subscriber: ealfie.Mar 28 2016, 2:38 AM