See the previous post for context and explanation of SSI . After reading Chris Fallin’s aegraph post , new ZJIT contributor dak2 landed a block-local version of the canonicalize function in #16828 . The pseudocode of the block-local canonicalize function looks like this: for block in function . reverse_post_order (): rewrite_map = {} for insn in block . insns : insn . operands . map_in_place (…
NB: This isn’t about crypto. I don’t care about crypto. Chris messaged me the other week asking if I wanted to implement zero-knowledge proofs. I initially was not interested, but then he said: What if I told you there’s a version of them that has nothing to do with cryptocurrencies? What if I told you it involves graph theory? What if I told you there’s a 30 line implementation? Now that was…
Originally published on Rails At Scale . We recently enabled a really cool feature in ZJIT that makes it feel like a Real Compiler™: the inliner! We’ll write more about it soon. In this post, we’ll talk about one excellent concrete benefit we are already seeing and how it optimizes blocks in pretty much every Ruby program. I’ll start off with a refresher on how blocks work in the Ruby interpreter,…
I had another excellent PLDI this past June. It was my fourth 1 . I continued to meet new people and learn new things! Overall: I got to meet a lot of new people, which was exciting. I had some good chats about research. I asked a question at a talk! I got to show Aaron and Jacob PLDI and see them enjoy it. I missed hanging out with CF Bolz-Tereick and Chris Fallin, the usual suspects at…
Compilers, especially method just-in-time compilers, operate on one function at a time. It is a natural code unit size, especially for a dynamic language JIT: at a given point in time, what more information can you gather about other parts of a running, changing system? I don’t have any data to back this up—maybe I should go gather some—but on average, methods are small. Especially in languages…
Short post today. New ZJIT contributor dak2 submitted a PR to fix an overflow bug in fixnum division in ZJIT. We did the division fine, but lied about the type of the result in the case of dividing FIXNUM_MIN by -1 . You can see how this is special-cased in CRuby: static inline void rb_fix_divmod_fix ( VALUE a , VALUE b , VALUE * divp , VALUE * modp ) { // ... if ( x == FIXNUM_MIN && y == - 1 ) {…
I just got back from a three and a half week trip to Japan. It was the longest trip I have ever been on (aside from studying abroad in Germany, which felt different). I made the following wild circuit with only a backpack and a duffel: Tokyo Toyama Kanazawa Nara ish Ito Hakodate Nikko Mashiko Karuizawa Tokyo This trip was split into three parts: time with my immediate family, going to a…
In compilers, static single information form (SSI) is a common extension to static single assignment form (SSA). It was introduced by C. Scott Ananian in 1999 in his MS thesis (PDF) 1 . SSI extends your existing SSA intermediate representation by discovering facts from your existing program and reifying them as path-dependent/flow-sensitive IR nodes. That might sound complicated, but at least the…
Welcome back to compiler land. Today we’re going to talk about value numbering , which is like SSA, but more. Static single assignment (SSA) gives names to values: every expression has a name, and each name corresponds to exactly one expression. It transforms programs like this: x = 0 x = x + 1 x = x + 1 where the variable x is assigned more than once in the program text, into programs like this:…
Originally published on Rails At Scale . Look! A trace of slow events in a benchmark! Hover over the image to see it get bigger. A sneak preview of what the trace looks like. Now read on to see what the slow events are and how we got this pretty picture. The rules The first rule of just-in-time compilers is: you stay in JIT code. The second rule of JIT is: you STAY in JIT code! When control leaves…
I noticed that the URLs were all a little off (had two slashes instead of one) and went in and fixed it. I did not think everyone's RSS software was going to freak out the way it did. PS: this is a special RSS-only post that is not visible on the site. Enjoy.