Throw in some more of context tracking (e.g. "did the left-hand side turn out to be a constant" or "are we in the (X+Y)+Z situation?" etc.) and you can start doing optimization such as constant folding and expression-tree rebalancing.
Then you can start emitting chunks of assembly instead of bytecode ("iconst X" turns into "push X", "add" turns into "pop eax; pop ecx; add eax, ecx; push eax" etc). Again, with enough context tracking (for example, what's in what registers), you can emit much less stupid assembly.
Isn't Apple M1 much wider than x86?
If there's a serious problem w/ the x86 architecture it's that the instructions are variable length from 1 to 14 bytes so if you wanted to build a decoder that fetches, say, 5 instructions at a time it would have to read 70 bytes. It has to run very quickly, ideally it doesn't consume a lot of power, so it is going to take up a lot of die area and if you want to make it wider still it is a challenge.
Intel and AMD do really well despite this and the long instructions mean you can build all sorts of acceleration into the CPU which can make up for this (some of why the double-pumped AVX512 is effective on AMD's latest is that even when it s getting work down at AVX256 speeds at the core, it is wasting fewer resources dealing with instructions.)
No you don't. Look at a block diagram of (say) Skylake: https://en.wikichip.org/wiki/intel/microarchitectures/skylak...
What you do is extract up to N instructions from a block of memory (in this case, 16 bytes). If there are fewer than N instructions, well, you can only issue as many as you have; if there are more than N instructions, well, you can only issue N instructions that cycle. Note that most instructions are only a few bytes length; I don't have hard data on the average instruction length of an x86-64 instruction in practice, but my guess is it's around 3-4 bytes.
The hard part about a variable-length ISA, as I understand it (hardware is not my expertise), is that you have to build essentially a mux that can steer from 16 source places to 5 outputs.
It's not just the mux, it's the control signals for the mux. If your first instruction in your 16-byte window is three bytes long, you can't realistically mux bytes 3-15 to the second decoder input, because you don't know that it needs to start decoding at byte 3 until /after/ the first instruction has decoded; so your gate delays would be the sum of the five decoders, plus muxing etc, and we're trying to do this at a single cycle.
The alternative is to have 16 decoders, each decoding what an instruction /would/ be if it started at a given byte. These all complete in parallel, but many of them might produce garbage. So we need to find the first five of these that have non-garbage outputs, and /then/ mux those sixteen possible outputs down to five channels. This is doable (and done), but it's a lot more hardware in both decoders and muxing than you might think at first.
Basically: To decode five instructions per cycle from a fixed-instruction-width stream takes five decoders. To decode up to five instructions per cycle from a variable-instruction-width stream takes number-of-possible-starts decoders and a mess of muxing. There really is a cost here.
The Thumb ISA is left as an exercise for the reader.
And of course every part of it has to be balanced. It makes no sense to decode instructions faster than the system downstream can handle it, particularly if you are wasting resources to do so.
The reason why Intel has so many different implementations of x86 is to meet the needs of different market segments.
Trade-offs are everywhere. But certainly fixed width instructions, or variable-width-but-trivial-to-determine-length (Thumb before Thumb2, RISC-V compressed) have real advantages.
I believe reading somewhere that that's pretty much how more or less recent Intel processors do that.
Well that just sounds hideously complex.
I don't think the x86 decoder is actually a particularly complex state machine (I haven't attempted to actually build it), so it's probably overall far less complex than most people assume it is.
And then add to that the complexity of speculative and out of order execution: you will want to very early decide, i.e. (pre)decode, where branch instructions are, in order to make sure your branch prediction unit has the right inputs in time, to decide where to fetch the next instructions from.
And after all that, on a branch mispredict earlier on (or pipeline flush for another reason), you might need to throw almost all of that expensively decoded instructions away and start fetching from elsewhere...
CPUs are fun :)
Section 2.2.1, Intel® 64 and IA-32 Architectures Software Developer’s Manual
Also, long instructions are infrequent, 96%+ are 7 bytes or less. That's static and dynamic is higher.
PyPI is the Python Package Index. https://en.wikipedia.org/wiki/Python_Package_Index
PyPy is the Python implementation with JIT. https://en.wikipedia.org/wiki/PyPy
(Yes, it is extremely confusing that there are two Python projects with homophonous, nearly-identical names.)
There's more than one way to name it! No, that's Raku.
Interpreters operate sequentially in time.
They take the compiler output, combine it with parameters from the world outside the cpu, and sequentially produce results that affect the physical world in some way, even if it’s just writing a result to memory.
The interpreter may use the compiled text many times.
At some point, it’s interpreters all the way down, at first in object code, then microcode. The ALU itself is a sequential hardware interpreter.
There's a historical line from a CS great (I am not sure who) that goes something like:
When you first start writing software, you will not understand the difference between an interpreter and a compiler. After you've been writing software for a certain amount of time, you will never confuse an interpreter and a compiler. But after you've been writing software for a bit longer than that, you will again not understand what the difference between them really is.
I always thought of an interpreter as a translator, while a compiler was a translator and optimizer.
So my question - can LLMs do this? They are really good at contextualizing and generating code - so why not build a compiler that is basically an LLM?
For instance there is the kind of simple interpreter that I know how to write off the top of my head which evaluates the nodes of an expression tree which is horribly inefficient.
Then there is something like Python which "compiles" code to bytecode which is then interpreted by a "virtual machine". That kind of system admits very complex optimizations about as far you as can imagine, including compiling some of the bytecode all the way to machine code the way PyPi or the JVM does it.
Note most interpretations of the Intel architectures break complex instructions up into RISC-like "micro-ops", which is a bit like bytecode interpretation.
One of the biggest concerns in a modern CPU is that memory accesses are very slow relative to a CPU cycle so you want to be executing a large number of instructions at a time to hide the latency of memory access. Intel's failed Itanium had the compiler try to explicitly schedule this but it didn't work because the compiler can't know ahead of time (for general purpose code) what is in what level of the cache and what isn't -- and in a worse case scenario this can hang up not only one instruction but many other instructions that depend on the result of that instruction, ether because they really depend on the result or because the CPU gets hung up. The CPU, on the other hand, does know, and can be opportunistic about taking advantage of available parallelism.