[llvm-dev] Tablegen backend for emulator core?

[John Byrd via llvm-dev]

On Tue, Mar 23, 2021 at 4:41 AM Simon Cook <simon.cook at embecosm.com> wrote:

> > The first thing is what kind of simulation do we want to have LLVM
model, if its a simple instruction set simulator then in some regards I
don't imagine this being too hard, but if we want to be able to stretch as
far as modelling full pipelines (unlikely to be automatically), it would be
good to generate the components, even if we have to build the pipeline by
hand (I think scheduling info in TableGen is probably insufficient for
this).

Because processors can be arbitrarily simple or complex, and the needs for
quality of emulation vary as well (do we need to simulate cache effects or
no?  do we want RSP protocol support or no?) then I'd suggest creating a
set of base classes that can be extended per processor, to whatever levels
of modelling are needed for that architecture.  I think this is more in
line with LLVM's philosophy of creating a bunch of base classes, that you
can extend into particular tool implementations.

I can think of three basic strategies for emulating an existing
architecture, within LLVM.

First, an instruction level emulator.  Basically, a large switch statement,
conditioned on the opcode.  Each emulation step uses the existing
MCDisassembler architecture to decode the operands out of each instruction,
and then emulate the instruction on those operands.  Slow, but well
understood and easy to implement.

Second, a cross compiler from the emulated machine's binary code, to C++.
Instead of emitting a large switch statement, we emit a very large function
with C-style labels on every emulated instruction.  Branch instructions are
modelled as conditional goto's in the emitted code.  We could even
reconstruct BasicBlocks of code, by using tablegen's knowledge of whether a
particular instruction is a terminator or not.  Since we're letting LLVM
use all its optimizers on each emulated BasicBlock, performance should be
much more reasonable.  Drawbacks include not being able to support
self-modifying code.  This shouldn't be a big problem, because LLVM
currently doesn't emit self-modifying code, AFAIK.

Third, a qemu-style dynamic recompiler, Conveniently, we happen to have a
JIT compiler already built into LLVM!  In fact, we could modify the second
approach, such that when we trap on attempting to write the read-only code
areas, instead we cross compile that basic block with the changes that were
just made to that memory area.  So this third style would be fast, and it
could even handle self-modifying code.

The key insight for all three of these strategies, is that the code that
parses operands, and applies the opcode instruction to those operands, can
be the same for all three styles of emulation.  And there's where tablegen
could save the day, by spitting out all that code per emulator.

Internally, tablegen is dumber than a lot of people give it credit for.
It's all just records, and classes of records, and methods for determining
whether one class inherits from another.  The smarts are in each of
tablegen's backends, which determine how those records should be
interpolated into code.  What tablegen IS good at, is concatenating
arbitrary strings and/or code snippets.  So, each instruction in tablegen
could map a list of emulator IDs, onto a list of strings (code) that
implements these instructions for that emulator.  This approach would allow
any backend to experiment with multiple simultaneous emulation approaches.
So you could bring a more sophisticated emulator online, while a simpler
one is already in production.

This approach also has the advantage that the code that runs the emulation
can be compositional -- tablegen can concatenate the code that parses an
operand, with code that checks for cache effects, with code that implements
the opcode, with code that retires instructions from cache, etc.  Tablegen
remains DRY, but by having tablegen restricted to concatenating code
snippets to emulate instructions or basic blocks, you can still make the
emulation as simple or as complex as you want it to be.

I thought about pulling that existing emulator from lldb, but it seemed to
me like it would introduce a novel dependency into llvm, to cause llvm to
depend upon lldb.  RSP server support is a good idea however, and it
clearly would be the same code regardless of what style of emulation you
were doing.  If you build your base classes right, you could even support
fancy things like reverse execution, out of box.

I'm envisioning an llvm-emu command line tool that lets you choose an -mcpu
and a -triple and an -arch to emulate.  And there'd also be flags for
printing either emulated instructions, or the emulated program's stdout, so
that you can verify an emulated program run with lit.

Anyway, the whole purpose of such an emulator, and the immediate reason why
multiple projects need it, is that it permits you to quickly test new
codegen ideas, as part of the normal check-llvm or check-clang build.
Codegen testing inside llvm, is currently restricted to "do you emit this
exact sequence of instructions or not."  Having an on-board set of
emulators, allows you to write tests of the form "does the generated code
do this or not," and get rapid feedback.  Of course, a well-structured set
of base classes would allow you to build a lot of other emulate-ish things
as well.

---

John Byrd
Gigantic Software
2321 E 4th Street
Suite C #429
Santa Ana, CA  92705-3862
http://www.giganticsoftware.com
T: (949) 892-3526 F: (206) 309-0850
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210328/3b689c30/attachment.html>