{"id":242,"date":"2010-02-01T11:09:35","date_gmt":"2010-02-01T00:09:35","guid":{"rendered":"http:\/\/blog.mozilla.org\/nnethercote\/?p=242"},"modified":"2010-02-01T11:59:11","modified_gmt":"2010-02-01T00:59:11","slug":"a-win-for-code-hygiene","status":"publish","type":"post","link":"https:\/\/blog.mozilla.org\/nnethercote\/2010\/02\/01\/a-win-for-code-hygiene\/","title":{"rendered":"A win for code hygiene"},"content":{"rendered":"

I’ve written<\/a> recently<\/a> about clean-ups I’ve been making in Nanojit — simplifying code, refactoring, adding more internal sanity checking.\u00a0 I’m a firm believer that these kinds of changes are worth doing, that “if it ain’t broke, don’t fix it” is not always true.\u00a0 But there’s always a voice in the back of my head wondering “am I just polishing this code for little gain?\u00a0 Should I be working on something else instead?”\u00a0 Yesterday I received confirmation that this work has been worthwhile.\u00a0 But before I can explain why, I need to give some background.<\/p>\n

Nanojit serves as the back-end of TraceMonkey.\u00a0 It converts LIR (a low-level intermediate representation) generated by TraceMonkey’s front-end into native code.\u00a0 So Nanojit is a critical part of TraceMonkey.\u00a0 And TraceMonkey is a critical part of Firefox.<\/p>\n

However, code generators (and register allocators) are tricky beasts — easy to get wrong and hard to debug.\u00a0 (A long time ago I heard someone, I can’t remember who, say “code generators and garbage collectors should crash as early and noisily as possible”.)\u00a0 So with a piece of code this important and inherently difficult, it’s a good idea to arm yourself with some weapons that give you confidence that it is correct.<\/p>\n

Weapon 1: clean IR semantics<\/h3>\n

One way to do this is to give your IR clean semantics.\u00a0 LIR’s semantics are mostly clean, but there are a few nasty cases.\u00a0 One of the worst is the ‘ov’ instruction.\u00a0 It performs an overflow check on an arithmetic (add, mul, sub, neg) operation.<\/p>\n

JavaScript numbers are doubles by default, but TraceMonkey sometimes demotes them to integers for speed.\u00a0 TraceMonkey has to check for integer overflow in these cases;\u00a0 if an integer does overflow TraceMonkey has to step back and use doubles for the computation.<\/p>\n

Here’s some example LIR that uses ‘ov’:<\/p>\n

 ld6 = ld sp[-8]\r\n\u00a0add1 = add ld6, 1\r\n ov1 = ov add1\r\n xt4: xt ov1 -> pc=0x883ed8 imacpc=0x0 sp+0 rp+0 (GuardID=218)<\/pre>\n
The first instructions loads a value from the stack.\u00a0 The second instruction adds 1 to that value.\u00a0 The third instruction performs an overflow check and puts the result in ‘ov1’.\u00a0 The fourth instruction is a guard;\u00a0 if ‘ov1’ is true it exits the code block.<\/p>\n
So why is ‘ov’ semantically nasty?\u00a0 First consider ‘add’, which is a semantically cleaner instruction.\u00a0 Its result (in this case ‘add1’) is a function of its inputs (‘ld6’ and 1).\u00a0 In comparison, ‘ov’ does not have this property.\u00a0 The ‘ov’ doesn’t really take ‘add1’ as an input —\u00a0 you can’t tell by looking at ‘add1’ whether the addition overflowed.\u00a0 In fact you can’t really understand what is happening here at the LIR level;\u00a0 you have to know what happens in the native code that is generated from this LIR.\u00a0 It turns out that the native code for the ‘add’ also sets some condition codes, and the native code generated for the ‘ov’\/’xt’ pair inspects those condition codes.\u00a0 For this to work, the ‘add’ has to immediately precede the ‘ov’;\u00a0 if it does not, whatever intermediate native code that is generated could overwrite the condition codes, in which case the behaviour of the guard becomes completely unpredictable.\u00a0 This is obviously bad.<\/p>\n
The real problem is that the addition has two outputs:\u00a0 the result, and the overflow status indicator (which maps to condition codes in the hardware).\u00a0 But LIR has no explicit way to represent that second output.\u00a0 So the second output is implicit, and an extra constraint must be imposed on the LIR instead, i.e. ‘ov’ must immediately follow an arithmetic operation.\u00a0 Because this constraint is so arbitrary it’s easy to forget and easy to break.<\/p>\n
In May 2009 Julian Seward opened a bug<\/a> to improve LIR’s semantics, giving five suggestions.\u00a0 It generated a lot of discussion and Julian drafted a patch to replace ‘ov’ with some cleaner opcodes, but there was enough disagreement that it never went anywhere.\u00a0 But I didn’t forget about it, and ‘ov’ has annoyed me enough times recently that I decided to resurrect Julian’s idea, this time in a new bug<\/a> to escape the baggage of the old one.\u00a0 The idea is simple: if ‘ov’ always has to follow an arithmetic operation, then why not create new opcodes that fuse the two parts together?\u00a0 These new opcodes are ‘addxov’, ‘subxov’ and ‘mulxov’.\u00a0 With my patch the code from above now looks like this:<\/p>\n
 ld6 = ld sp[-8]\r\n\u00a0add1 = addxov ld6, 1 -> pc=0x883ed8 imacpc=0x0 sp+0 rp+0 (GuardID=218)<\/pre>\n
The ‘addxov’ adds ‘ld6’ and 1, puts the result in ‘add1’, and exits if there was an overflow.\u00a0 The generated native code is unchanged, but the implicit output of the addition is now hidden within a single LIR instruction, and it’s impossible for overflow checks in the native code to become separated from the potentially-overflowing arithmetic operation.<\/p>\n
Weapon 2: strong IR sanity checking<\/h3>\n
Compilers are usually built in a pipeline fashion, where you have multiple passes over the code representation, and each pass does a task such as optimisation, register allocation or code generation.\u00a0 It’s also a really good idea to have a pass that does a thorough sanity check of the code representation.<\/p>\n
In November 2008 Jim Blandy filed a bug<\/a> suggesting such a pass for Nanojit, one that performs type-checking of the LIR.\u00a0 The bug sat untouched for over six months until some extra discussion occurred and then (once again) Julian wrote a patch.\u00a0 It found at least one case where TraceMonkey was generating bad LIR code, but again the bug stalled, this time because we spent three months merging Mozilla’s and Adobe’s copies of Nanojit.\u00a0 I resurrected the bug again recently and added some “structure checking” for things like the ‘ov’ constraint, and it landed in the TraceMonkey repository on January 21st.\u00a0 Happily, my version of the checker was simpler than Julian’s;\u00a0 this was possible because LIR had had some other semantic clean-ups (e.g. properly distinguishing 64-bit integers from 64-bit floats)<\/a>.\u00a0 My patch replaced a very basic type-checker (called “SanityFilter”) that had been in TraceMonkey, and immediately found two<\/a> bugs<\/a>, one of which involved ‘ov’.<\/p>\n
Synergy<\/h3>\n
It’s not often that a bug report involving your code makes you smile.\u00a0 Yesterday Gary Kwong hit an assertion failure<\/a> in Nanojit when fuzz-testing:<\/p>\n
    LIR structure error (end of writer pipeline):\r\n    in instruction with opcode: ov\r\n    argument 1 has opcode: add\r\n    it should be: located immediately prior, but isn't\r\n  One way to debug this:  change the failing NanoAssertMsgf(0, ...) call to a\r\n  printf(...) call and rerun with verbose output.  If you're lucky, this error\r\n  message will appear before the block containing the erroneous instruction.<\/pre>\n
In other words, there’s an ‘ov’ following an ‘add’, but there are one or more other LIR instructions between them.\u00a0 This means that the code generated will be bogus, as I explained above.\u00a0 This bug may have been in TraceMonkey for a long time, but it wasn’t detected until strong internal sanity checking was added.\u00a0 The good news is that the ‘ov’-removal patch (which hasn’t landed as it’s still awaiting review) will fix this patch.<\/p>\n
Lessons learned<\/h3>\n
This story tied together a number of related ideas for me.\u00a0 In particular:<\/p>\n
    \n
  • Clean IR semantics are worth the effort.\u00a0 Hacks may save time initially but they will come back to bite you.<\/li>\n
  • Strong IR sanity checking is worth the effort.\u00a0 (And cleaner semantic allows for stronger checking.)<\/li>\n
  • Listen to Julian, especially when he talks about correctness.\u00a0 (And read his code!\u00a0 VEX\/pub\/libvex_ir.h in the Valgrind source code describes Valgrind’s IR, which is a wonderfully clean IR, particularly in the way it separates statements (which have side-effects) from expressions (which don’t).)<\/li>\n
  • Don’t put too many ideas into one bug report.\u00a0 Too much discussion can kill a bug, or at least put it in a coma.<\/li>\n
  • Follow-through is important.\u00a0 A patch can’t do much good unless it lands.<\/li>\n
  • Fuzz testing is awesome (but we already knew that).<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
    I’ve written recently about clean-ups I’ve been making in Nanojit — simplifying code, refactoring, adding more internal sanity checking.\u00a0 I’m a firm believer that these kinds of changes are worth doing, that “if it ain’t broke, don’t fix it” is not always true.\u00a0 But there’s always a voice in the back of my head wondering […]<\/p>\n","protected":false},"author":139,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[528,617,467],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/posts\/242"}],"collection":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/users\/139"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/comments?post=242"}],"version-history":[{"count":0,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/posts\/242\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/media?parent=242"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/categories?post=242"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/tags?post=242"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}