[Idea] Rewriting in LLVM DSL

[indutny]

I know it sounds crazy, but bear with me 😉

What would you think about rewriting whole project using some JavaScript tool to compile a DSL to a LLVM IR?

I've several reasons for this:

• Getting rid of huge switch statement that isn't optimized well, and putting separate states into separate procedures with optimized jumps between the states
• Having architecture-specific vector comparisons that are easy to use

It doesn't sound to complicated, and may finally make our codebase shine.

cc @bnoordhuis @mscdex

[indutny]

Here is an example of what it might look like: https://github.com/indutny/llparse/blob/master/test/fixtures/example.js

[bnoordhuis]

If you're thinking of writing some lexer generator, I could definitely get behind that - I've had the same thought more than once - but why LLVM IR specifically and wouldn't we be reinventing ragel?

[indutny]

@bnoordhuis there're probably better solutions out there, but I always wanted to write something that compiles to LLVM IR. Is it a valid excuse?

On a more serious note, I'd like every state implementation to live in a separate procedure that tail-calls other procedures in the most of the cases. This might turn out to be faster than having a single grand dispatch.

[indutny]

Also on the feature list is having a low-level trie implementation that works seamlessly.

[indutny]

It could probably work in a way similar to Ragel, however it'd have to rely on LLVM to inline the C code into compiled nodes of the state machine graph.

[bnoordhuis]

You can't replace http-parser with something that spits out LLVM IR, that leaves too many users out in the cold. Something that compiles to C or has different back-ends could work though (but then you're half-way on the road to reimplementing ragel or re2c.)

a low-level trie implementation

What for?

[indutny]

We obviously need a trie-like state machine to replace hand-written state code for the methods.

[bnoordhuis]

Not sure I follow. For lexers, you compute the DFA or NFA and then emit state tables or goto-based code. I guess you could implement it as a trie but I don't know why you would.

[indutny]

I didn't mean in-memory trie, as a data-structure. Rather a compiled code consisting of branches and states linked in a trie-like structure.

[bnoordhuis]

Ah, okay. You get that for free with a DFA but I guess a trie is pretty much a DFA encoded as a tree.

[indutny]

I think I'm on the edge of giving up. Just figured out that musttail may not work on arm.

[indutny]

Nvm, it works! 👍

[indutny]

Took few iterations, but I think I've reached some intermediate milestone here: https://github.com/indutny/llparse/blob/master/test/api-test.js

What do you think, @bnoordhuis ?