IAF: Where can a trace end? Why?

[lukego]

Here is an Infrequently Answered Question:

Where can a trace end? Why?

Can a trace end on any bytecode at all? Or are there restrictions about e.g. what is the final bytecode, what is the point of control flow, etc?

This seems relevant to understanding how much flexibility the JIT has in selecting traces. For example, if we encounter an uncompilable bytecode like an NYI or a blacklisted function, do we have the option to successfully end the current trace and then transition to the interpreter? Or do we have to abort because this is not a valid end point for a trace for some reason?

cc @javierguerragiraldez

[igelhaus]

I faced the same question some time ago, and here is what I learned after a very quick investigation:

1. If you are recording a root looping trace, you finish recording as soon as you complete the iteration of that loop and hit again the same byte-code that triggered recoding.
2. If you are recording a root scalar trace (aka a trace without a loop), you finish recording as soon as you return from the function that triggered recording.
3. If you are recording a side trace, you finish recording either when you return to the beginning of your root trace or when the execution flow carries you to some other already compiled root.

There are some corner cases, though:

1. During recording you can hit an already compiled loop. Looks like in this case you link to this loop.
2. During recording you can hit an already compiled function. In this case you "inline" a call to that function if the corresponding trace returns to the interpreter on exit and go ahead with recording. Otherwise you either link to that trace form a recursion.

So answering your first question: No, looks like there is no option to finish recording on an arbitrary byte code.

Just in case: To figure things out, I was simply trying to understand the code around rec_stop in lj_record.c

[lukego]

Thanks for the notes @igelhaus!

Do you think it is important to the design that traces only end on these particular points? I noticed an assertion in trace_stop() that will abort if a trace would end on a bytecode other than FORL/LOOP/ITERL/FUNCF/RET/RET0/RET1/JMP/CALLM/CALL/ITERC and I am wondering how important this is i.e. are the other cases truly invalid or simply unexpected.

Seems to me like a trace should be able to end at any point. The JIT can exit to a side-trace at any point and the end of the trace is just another exit, right? Seems to me like this would be desirable too e.g. if your trace has 100 instructions and you hit an NYI/ILOOP/IFUNC then it is probably best to accept the trace and bail out to the interpreter as late as possible. That would about the situation of "blacklisting contagion" where one NYI can propagate through the whole program.

[igelhaus]

Technically a "true" trace exit and a side trace exit are handled with more or less the same code (I mean, side exits do hot-counting etc., but I do not remember any crucial differences here), so I see no design limitations. I can only guess, but probably recording stops at some fixed points to minimise unexpected negative performance impact. Assume you are trying to compile a loop and you have assembled a trace from N byte code instructions with (N+1)-th being both a NYI and a last one in the loop body. An arbitrary exit to the interpreter adds a switch between the interpreter and the compiled code on each iteration, which is not as lightweight, which, in turn, can eat up all performance gain achieved with JITting N instructions (especially when N is considerably small). But back to your example, it is still tempting to be able to JIT 100 instructions of some scalar code before, say, a NYI that appears unconditionally in the control flow. Looks like the trace stitching feature (briefly mentioned on http://wiki.luajit.org/NYI) addresses this issue to some point. 2017-09-10 13:16 GMT+03:00 Luke Gorrie <notifications@github.com>:

…

Thanks for the notes @igelhaus <https://github.com/igelhaus>! Do you think it is important to the design that traces only end on these particular points? I noticed an assertion in trace_stop() <https://github.com/raptorjit/raptorjit/blob/master/src/lj_trace.c#L438> that will abort if a trace would end on a bytecode other than FORL/LOOP/ITERL/FUNCF/RET/RET0/RET1/JMP/CALLM/CALL/ITERC and I am wondering how important this is i.e. are the other cases truly invalid or simply unexpected. Seems to me like a trace should be able to end at any point. The JIT can exit to a side-trace at any point and the end of the trace is just another exit, right? Seems to me like this would be desirable too e.g. if your trace has 100 instructions and you hit an NYI/ILOOP/IFUNC then it is probably best to accept the trace and bail out to the interpreter as late as possible. That would about the situation of "blacklisting contagion" where one NYI can propagate through the whole program. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#103 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGWzvvVJ6CwESb58DBj33fs7z6aRC_KDks5sg7bygaJpZM4PR8on> .

-- Med vennlig hilsen, Anton Soldatov