[tliltocatl]

> One of them is even Turing complete.

> figuring out where in memory or registers a given high level variable

Isn't the task itself Turing-hard? Or at least complex enough so that coming up with a non-Turing-complete solution would be impractical?

[VorpalWay]

Good question, that I don't fully know the answer to. The rest of the byte code (apart from the primitives that enable looping) already allow expressing a lot. From memory (it has been almost half a year since I last worked on this), you can specify things like "for this 32 bit value, the first two bytes can be found in the middle of RAX, the third byte is found following this chain of pointers, and the final byte is on the stack" without even touching the TC parts.

Basically, my impression was that that the format was flexible enough that I couldn't see why you would need the TC parts in practice. The compilers seemed to agree and not use it in practise (at least gcc and llvm).

This was of interest to me since I was generating BPF code from these (for user space trace points) and BPF is famously and intentionally not TC. I could translate many patterns that do show up in real world code, but not the general case.

[saagarjha]

This is largely because debug info is not great and does not generate the Turing complete counterpart to your code so that variables do not get optimized out. In the general case this is required.