3 ms·

This is necessary because there is a branch (if) in our code and traces are not allowed to have internal branches. I (mostly) understand the performance of the

• obl 11y ago
  The big advantage in optimizing a trace at a time is that you don't have inbound control flow. In fact, the first transform that a tracing JIT does to the code (trace extraction) can be seen as removing every inbound CF edge except the loop head (leaving them in the deoptimized version of the trace). One reason for that is that it makes optimization of the trace a lot easier since every forward dataflow problem (e.g. constant propagation or type inference) becomes more precise : if a is a string && b is a string x = concat(a,b) else if a is a int && b is a int x = add_int(a,b) else ... if you have knowledge (thanks to runtime instrumentation) that most of the time the second branch is taken, you can transform it to : bail if a is a string && b is a string bail if !(a is a int && b is a int) x = add_int(a,b) ... (where bail goes to the full code at the right place) This version is a lot easier to analyze because you don't have to worry about what might be true in alternate branches : for example, since we can assume we didn't bail out, at the end of this snippet x is always an integer. There is no reason to my knowledge why they couldn't support unbiased branches by including them in a trace, but it would complicate the implementation of various (forward) optimizing passes which don't have to worry about control flow in a single-trace model.
• rayiner 11y ago
  A branch-free section of straight-line code is pretty much the definition of a trace. You can use something other than traces in a "tracing JIT" of course,[1] but your complexity goes up. One nice property of straight-line traces is that it makes optimization extremely simple. Any instruction dominates all instructions that occur later in the trace. In the example with the "if" statement inside the loop, that is not true. Operations that happen in either branch do not dominate anything that comes after control flow merges back together after the if statement. So you have to do more sophisticated analysis to merge data flows at that point. It's doable--the point of SSA representation is to make that easier--but it's a lot slower and more complex than what you can do with straight line code. [1] E.g. trees of traces: https://github.com/oleganza/iovm2/blob/master/doc/papers/Incremental%20Dynamic%20Code%20Generation%20with%20Trace%20Trees.pdf https://github.com/oleganza/iovm2/blob/master/doc/papers/Inc.... Trace trees avoid the above problem by basically doing aggressive tail duplication.
  • nkurz 11y ago
    Thanks for the answer and the link. I think my confusion is/was that an "if" statement in the interpreted language might even be implemented as a conditional move in assembly. Thus it seems like it would be useful to distinguish "if (condition) a = a + 1" from "if (condition) frobnicate(a)" when defining a trace, even if both are written with an "if" in the interpreted language.
• mikemike 11y ago
  By definition, a trace doesn't have internal branches. The solution is to use Hyperblock Scheduling. This is an extra pass that merges multiple traces, e.g. the described root trace and its side trace. The result is a single trace with a predicated IR. This is amenable to most linear optimizations, with only minor limitations. A predicated IR is the ideal representation to apply branch-free optimizations, using bit operations or SIMD tricks. If there are any predicates left in the IR, the compiler backend will either turn it into predicated machine code (on CPUs which support that to some extent, e.g. ARM32) or generate machine code with internal branches.