A CPU is a compiler(outerproduct.net)
outerproduct.net
A CPU is a compiler
https://outerproduct.net/boring/2023-03-22_cpu-compiler-gc-ohmy.html
97 comments
> An advanced interpreter has many features of a compiler.
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.
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.
The same about the difference between software and hardware
Surprisingly, there is not that much distance between tree-walking evaluator and (stack-oriented-)bytecode emitter: you just have slightly different accumulator (integer vs. list of bytecodes) with slightly different operations on it (arithmetics vs. appending line "add/sub/etc." to the end of list).
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.
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.
Just a tiny nitpick for clarity, I think you mean PyPy rather than "PyPi". :)
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.)
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.)
To help me keep the spellings straight, I pronounce them as "pie pea eye" and "pie pie" respectively. That's also the PyPI project's preferred pronunciation.
https://pypi.org/help/#pronunciation
https://pypi.org/help/#pronunciation
Thanks for the correction, I fixed it.
Two pretty large, important projects, too. :-D
There's more than one way to name it! No, that's Raku.
There's more than one way to name it! No, that's Raku.
Compilers translate a text to (typically) a lower level, optimized, which is stored for later execution. The length of time the output is stored is arbitrary.
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.
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.
This is a question that has been at the back of my mind for some time. I may be very wrong.
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?
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?
That simple interpreter is inefficient, sort-of. It's 10X slower than compiling to code. It's 10X faster than ordinary interpreters. A compromise solution in some instances.
> The CPU, on the other hand, does know, and can be opportunistic about taking advantage of available parallelism.
Isn't Apple M1 much wider than x86?
Isn't Apple M1 much wider than x86?
Like ARM, there are many implementations of the x86. Intel has all the various "creeks" and "lakes", AMD has various implementations and there have been others like Cyrix.
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.)
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.)
> if you wanted to build a decoder that fetches, say, 5 instructions at a time it would have to read 70 bytes
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.
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.
> 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.
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.
Very nice explanation! It gets very complex very quickly... And then there's of course also the fact you never know if your last bytes in the Ifetch you get from the cache is a full instruction or not. You'll need to keep that around until the next line arrives which will have the rest of that instruction.
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 :)
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 :)
It all depends how much you want to get that last bit of performance and what you are willing to pay for it in terms of power, die area, all that.
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.
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.
Yep. And it's worth saying that, contrary to my previous over-simplification, the trade-offs change once you give up on single-cycle instruction decoding. With a longer pipeline, you can do a split into 16 simple, small pre-decoders, that basically just extract the length of the instruction, /then/ mux on the inputs to just five full decoders. It adds a pipeline stage, but it can be lower area for the same sustained performance.
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.
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.
> 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.
Well that just sounds hideously complex.
Well that just sounds hideously complex.
Length decoding is a finite state machine, and the transition function of finite state machines is associative, which means you can actually compile them into a reduction tree to do it in parallel.
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.
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.
> 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.
I believe reading somewhere that that's pretty much how more or less recent Intel processors do that.
I believe reading somewhere that that's pretty much how more or less recent Intel processors do that.
15 not 14. The instruction-size limit of 15 bytes still applies to instructions with a REX prefix.
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.
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.
Domain was previously elrond.net (redirects to outerproduct.net). Previous submission to HN is a jewel:
"Why no one should use AT&T syntax ever, for any reason, under any circumstances"
https://news.ycombinator.com/item?id=26122532
"Why no one should use AT&T syntax ever, for any reason, under any circumstances"
https://news.ycombinator.com/item?id=26122532
When down that route once, about 20 years ago, never again.
A jewel? Um... I'd call it a rant, myself. Not even a very well-grounded rant.
same...I feel weird because I learned AT&T syntax since day 1. And even with that, I think Intel syntax is just another way of writing, period. No hard feeling at all. Don't quite understand why the author is so...pissed.
Chip designers have noticed this similarity in the past have and attempted to push some of the work done by the CPU back into the compiler. Itanium and the Mill CPU both work(ed) like this I believe.
Mill CPU never existed in silicon, so there are questions to that. But IIRC Ivan said that they didn't do anything that compilers didn't do already for DPSs. He specifically mentioned that they don't want to be like Itanic.
This will never work due to incentive structure, unless the compiler devs are working for the same company that makes the CPU. Otherwise, compiler devs will target a lowest common denominator and call it a day. And even if the compiler devs perfectly support new CPU instructions, compiler users usually want a single binary that can run on as many CPUs as possible, and so will use the lowest common denominator once again. Currently, your CPU will 99% of the time run basic AMD64 instructions, regardless of its capabilities. So Intel and AMD try to make their CPUs really good at running AMD64 code.
> unless the compiler devs are working for the same company that makes the CPU
Every CPU manufacturing company have a compile team.
> This will never work
VLIW processors do work, and for a while now. This type of architecture performs better for data-intensive workloads, so you don't see them in the general-purpose world.
But if you are talking about Mill, yes it will never work.
Every CPU manufacturing company have a compile team.
> This will never work
VLIW processors do work, and for a while now. This type of architecture performs better for data-intensive workloads, so you don't see them in the general-purpose world.
But if you are talking about Mill, yes it will never work.
> But if you are talking about Mill, yes it will never work.
Maybe Mill Computing won't pull it off, but why do you think the approach is bad? It seems sufficiently different from Itanium to not have the exact same problems.
Maybe Mill Computing won't pull it off, but why do you think the approach is bad? It seems sufficiently different from Itanium to not have the exact same problems.
They don't have a "deliver at all costs" philosophy and they are creating a new and different CPU architecture from scratch, a task where even teams oriented at delivering at all costs tend to almost always fail.
The architecture itself looks very good. If it was built in a way similar to RISC-V, it would probably become very influential. (But then, I'm not sure you can create something that innovative by the same procedures RISC-V was created.)
The architecture itself looks very good. If it was built in a way similar to RISC-V, it would probably become very influential. (But then, I'm not sure you can create something that innovative by the same procedures RISC-V was created.)
The architecture looks like a dead end compared to other novel architecture like the Reduceron which reached 33% of the performance of a single core 2 duo processor core while running on an FPGA with only 90MHz without using pipelining or out of order execution. The catch is that the execution model of the Reduceron is graph reduction which basically means lambda calculus/lazy functional programming languages.
The Reduceron's raw arithmetic performance isn't better, but it doesn't matter because lazy evaluation is memory intensive, the more memory intensive the algorithm, the better the Reduceron performs, which is very unlike classical C machines like x86 or ARM or RISC-V where memory intensitivity must be avoided at all costs for good performance. Where the Reduceron does a single graph reduction per clock cycle, a C machine has to do it with several sequential instructions so a massive clock rate advantage isn't worth much.
Well, first of all, because it shows no results after +10 years. There is definitely no indication that it will work someday.
And above all because there are too many choices that are too specific, outdated and too exotic. (e.g. the split-stream encoding is way too exotic)
I work in a small company that makes processors, and I know from experience that developing a processor is a very complicated subject, you have to go step by step (Mill does not). When you come up with a new design/idea, you try to simulate it, test it and implement it. You don't pile up new ideas without getting feedback on them.
And above all because there are too many choices that are too specific, outdated and too exotic. (e.g. the split-stream encoding is way too exotic)
I work in a small company that makes processors, and I know from experience that developing a processor is a very complicated subject, you have to go step by step (Mill does not). When you come up with a new design/idea, you try to simulate it, test it and implement it. You don't pile up new ideas without getting feedback on them.
VLIW works _really_ well if you have deterministic memory timings, e.g. DSP/risc style architectures, and you're up for writing a complicated compiler.
And at least the Intel compiler was/is pretty good at producing a single binary that uses whatever features your CPU has available by switching to different code paths depending on the cpuid flags. At least if your CPU is an Intel CPU, it's more conservative with that on AMD CPUs.
> Every CPU manufacturing company have a compile team
Sure, but that doesn't help when all the binaries are compiled for AMD64 anyway.
Sure, but that doesn't help when all the binaries are compiled for AMD64 anyway.
You can compile your own binaries if max performance is the goal.
Assuming you have access to the source code of course.
Assuming you have access to the source code of course.
Intel and AMD are so good at running AMD64 code that it's often slower to use additional instructions.
It's quite complicated. Sometimes hardware instructions are awkward or redundant enough that compilers ignore them. Or they're broken in hardware and the compiler tries to patch around them. Sometimes there are invariants that are easy for compilers and really annoying for assembly programmers. A given sequence of instructions may execute correctly on multiple (sub)architectures with widely divergent performance behaviour.
The one binary that does minimal to no self modification on boot is popular with users but intrinsically slower. Arm's variable length vector instructions are catering to that.
One binary that is specialised to hardware and expected arguments is the fastest you can do without optimising while the program is starting/running.
However hardware usually changes slower than software. Specifically if a program starts running on a specific x64 chip it's likely to stay on that chip until it finishes running. Linux used to patch itself on boot to pick a faster memcpy (may still do).
It seems obvious that fastest for sufficiently long running processes is to ship a compiler IR, specialise first to the hardware and second to patterns in the data. OpenCL/spir-v have a finaliser premise where you lower to a given GPU just before running on it. Specialising on program data is branded JIT compilation. I don't know of anything doing both yet.
The one binary that does minimal to no self modification on boot is popular with users but intrinsically slower. Arm's variable length vector instructions are catering to that.
One binary that is specialised to hardware and expected arguments is the fastest you can do without optimising while the program is starting/running.
However hardware usually changes slower than software. Specifically if a program starts running on a specific x64 chip it's likely to stay on that chip until it finishes running. Linux used to patch itself on boot to pick a faster memcpy (may still do).
It seems obvious that fastest for sufficiently long running processes is to ship a compiler IR, specialise first to the hardware and second to patterns in the data. OpenCL/spir-v have a finaliser premise where you lower to a given GPU just before running on it. Specialising on program data is branded JIT compilation. I don't know of anything doing both yet.
> Otherwise, compiler devs will target a lowest common denominator and call it a day.
Mill's idea for that is that compiler outputs a multi-target binary, which is specialized to the current CPU at install/first-run time, by fixing the size of the belt and other such hardware details.
> "genAsm is a dataflow language, essentially a programmable representation of a single-assignment compiler IR."
https://millcomputing.com/docs/compiler/
Mill's idea for that is that compiler outputs a multi-target binary, which is specialized to the current CPU at install/first-run time, by fixing the size of the belt and other such hardware details.
> "genAsm is a dataflow language, essentially a programmable representation of a single-assignment compiler IR."
https://millcomputing.com/docs/compiler/
You can argue that it's the RISC approach, to some extent.
All of them. And the compiler engineers try to push work into the CPU.
I used to enjoy the Mill CPU videos. Is there some good post-mortem explaining what happened to that project?
It is reportedly still alive according to their website, but it's not very convincing.
The merging of both compiler (cpu and software) is the main reason of the success of Nvidia.
Make the chip simpler and more parallel (way more cores) Make the compiler smarter to better use the capabilities of the hardware.
Watching Jim Keller interview made me realise how much transistors are wasted because the cpu is trying to predict what the code is going to do.
There is an insane amount of complexity in chips trying to make single threaded code fast when what need the most cpu time in our code is usually parallels problem.
Maybe Triton will break that paradigm and will allow diverse parallels hardware to emerge and be used effectively.
Make the chip simpler and more parallel (way more cores) Make the compiler smarter to better use the capabilities of the hardware.
Watching Jim Keller interview made me realise how much transistors are wasted because the cpu is trying to predict what the code is going to do.
There is an insane amount of complexity in chips trying to make single threaded code fast when what need the most cpu time in our code is usually parallels problem.
Maybe Triton will break that paradigm and will allow diverse parallels hardware to emerge and be used effectively.
But don't underestimate how much 'middleware' there is in Cuda/CuDNN, NCCL etc. A lot of it is not in the compiler, but much more in hand crafted, carefully optimised libraries.
As an example: there are so many low level ways to run a conv2D kernel on a SIMT machine, but CuDNN will pick the best option for you based on the card you have, and the tensor sizes you are using.
As an example: there are so many low level ways to run a conv2D kernel on a SIMT machine, but CuDNN will pick the best option for you based on the card you have, and the tensor sizes you are using.
The failure of the Itanium highlights the danger of tilting too much complexity into the software / compiler space. It was very difficult to make a compiler which could generate parallelizable machine code and that lead to very disappointing performance for most software.
It only failed, because of AMD being allowed to come up with AMD64.
If x86 was Intel only, Itanium would have been eventually pushed everywhere no matter what.
If x86 was Intel only, Itanium would have been eventually pushed everywhere no matter what.
> Branch probability analysis | Branch prediction
> Peephole optimisations, idioms | Idioms
From the software side, what is it exactly that makes it so difficult to write a higher-level language that must be optimized, instead of a language that already exposes the optimizations in a friendly way?
("higher-level language" meaning c, not python or something)
> Peephole optimisations, idioms | Idioms
From the software side, what is it exactly that makes it so difficult to write a higher-level language that must be optimized, instead of a language that already exposes the optimizations in a friendly way?
("higher-level language" meaning c, not python or something)
The literal answer is that compilers are really easy to write when the source and destination language are the same and you don't want any optimisation. E.g. write the x64 machine code out as raw bytes and cat is good enough to turn it into x64 machine code.
Difficulty increases as the source and target languages become less similar, as more ambitious performance optimisations are attempted, as more comprehensive type/lint/warning style systems are implemented and as performance constraints on the compiler itself tighten.
So a compiler that takes imprecise scribblings, spots errors in them, and emits asymptotically perfect machine code for heterogenous distributed systems in real time is quite dramatically more complicated than cat.
Difficulty increases as the source and target languages become less similar, as more ambitious performance optimisations are attempted, as more comprehensive type/lint/warning style systems are implemented and as performance constraints on the compiler itself tighten.
So a compiler that takes imprecise scribblings, spots errors in them, and emits asymptotically perfect machine code for heterogenous distributed systems in real time is quite dramatically more complicated than cat.
Well the low-level implementations differ from cpu-to-cpu. Even between Itanium releases the width changes. They don't want to get bound to a single implementation as techniques improve and new approaches are found. Otherwise, each time they discover something new they'd have to release a new ISA and backwards compatibility was the most commercially influential aspect of a chip. Now, it used to be that super-computer were made with custom chips, with custom ISAs, but the advantage of mass consumer parts is too high. So in general the decoupling of implementation and programming language allows for enough wiggle room to allow independent evolution without being rigidly coupled.
Not sure what is exactly your thought, since the optimizations you quote don't really takes advantage of any exposed optimization feature of the language.
Are your asking why we could not expose optimization feature (e.g. branch hint to replace branch-prediction) in the programming language ?
Are you asking if it's difficult for a compiler to optimize some type of high-level languages ?
Since "higher-level" language is C in your question, what the "language that already exposes the optimizations in a friendly way" ? Are you thinking the CPU µop as a language ?
Are your asking why we could not expose optimization feature (e.g. branch hint to replace branch-prediction) in the programming language ?
Are you asking if it's difficult for a compiler to optimize some type of high-level languages ?
Since "higher-level" language is C in your question, what the "language that already exposes the optimizations in a friendly way" ? Are you thinking the CPU µop as a language ?
I can't recall the quote or source, but it went something like: A CPU is a compiler that transforms a serial instruction stream to a wide (acyclic) graph of data dependencies. This refers to concepts like out-of-order execution, superscalar processing, functional unit scheduling, and register renaming.
This is kind of gibberish IMO.
A nice introduction to some similarities but the details and constraints are quite different.
Transmeta however...
A nice introduction to some similarities but the details and constraints are quite different.
Transmeta however...
If we are okay to admit that CPU is a compiler (or an interpreter), can I say that self-printing machine code like https://susam.net/blog/self-printing-machine-code.html is a CPU quine?
Interesting point. CPU designers and compiler experts have worked almost the same way to optimize the execution performance.
Nice comparison. I think register renaming is more like doing SSA renaming on a trace than register allocation, though.
Intel made a processor with a GC in hardware once
Linn (the hifi people, not the drum machine people) made a CPU called "Rekursiv" (because they like odd spelling like that) which had objects and GC implemented in hardware, on a couple of very large custom chips on VMEBus boards. These were horrendously expensive and were to be plugged into a Sun 3 box, making it all quite breathtakingly spendy.
When Sun brought out their SPARC hardware the language they run was ported to that, and ran about four times faster clock-for-clock.
You can gain some measure of the Rekursiv's success from the fact that the only complete machine known to still exist can be found on the bottom of the Forth and Clyde Canal, somewhere around the Possil Road Aqueduct.
When Sun brought out their SPARC hardware the language they run was ported to that, and ran about four times faster clock-for-clock.
You can gain some measure of the Rekursiv's success from the fact that the only complete machine known to still exist can be found on the bottom of the Forth and Clyde Canal, somewhere around the Possil Road Aqueduct.
I can't imagine the thought process by which a niche Hi-Fi company decides the best way to automate their production system is to custom develop a totally new class of CPU... which is why I am glad there are at least a few people in the world that make the attempt.
(This whole thing also reminds me of the Intel 432... had some similar properties)
(This whole thing also reminds me of the Intel 432... had some similar properties)
Goodness! Did you have a hand in placing that machine there?
Not me, no, but I know some of the dramatis personae from way back then.
What does it mean to have "objects" implemented in hardware?
> because they like odd spelling like that
The founders parents fled from Austria during Nazi times. In Austria we speak German. The English word "recursive" is "rekursiv" in German.
The founders parents fled from Austria during Nazi times. In Austria we speak German. The English word "recursive" is "rekursiv" in German.
Ja, genau. Actually, his parents were Polish but moved to Austria.
Fascinating guy.
Fascinating guy.
so did sun - https://web.archive.org/web/20061230133753im_/http://researc...
and david bacon (et al) - https://files.catbox.moe/bipg79.pdf
and david bacon (et al) - https://files.catbox.moe/bipg79.pdf
If you remember the Transmeta chips from the early 2000s they literally were compilers. Took in x86 binaries but JITed them to an internal RISC instruction set.
The x86-to-vliw transformation was implemented in software. See https://en.wikipedia.org/wiki/Transmeta under "code morphing software". Similar to Rosetta.
I think that's how pretty much all of the high-performance desktop & server CPUs operate now.
I'm not sure where in that article the re-write-microcode feature lies? That is, modern CPUs can write microcode for instruction sequences, not just single opcodes. Which is almost exactly what a compiler is, if you substitute 'op code sequence' for 'source code sequence'.
Any recommendations of books on compiler optimizations?
The tiger books have a couple of them, pick your flavour,
https://www.cs.princeton.edu/~appel/modern/
https://www.cs.princeton.edu/~appel/modern/
Engineering a compiler is quite a good read.
Writing compiler in normal, high levels langs is non trivial,
I do wonder how this CPU code looks like
I do wonder how this CPU code looks like
Depends on what you pick.
ML, Lisp, and Logic derived languages are all relatively easy.
Hence why on my degree their were forbidden for compiler assignments, even though we had a strong ML and Prolog set of lectures in programming languages I and II, LP II.
We were supposed to earn the compiler design assignment, from the professor´s point of view.
Although the year I took it, it was about the time Java was being introduced, so doing it with Java, SableCC while not as easy wasn't that harder, specially following alongside the Tiger book.
ML, Lisp, and Logic derived languages are all relatively easy.
Hence why on my degree their were forbidden for compiler assignments, even though we had a strong ML and Prolog set of lectures in programming languages I and II, LP II.
We were supposed to earn the compiler design assignment, from the professor´s point of view.
Although the year I took it, it was about the time Java was being introduced, so doing it with Java, SableCC while not as easy wasn't that harder, specially following alongside the Tiger book.
Wow, that is awful. For compiler writing, you should use a good language for that purpose, so that the hard parts of the program are the actual compilation algorithms, not debugging segfaults in a graph structure or whatever, or wasting time on electricity-and-running-water infrastructural code whose existence should be taken for granted.
There is plenty of "cred" to be earned without that; you can still be pulling your hair out debugging a compiler written in Lisp, find years-old bugs in it and so on.
I don't know anything else about your ex-prof other than what you have in the comment, but based on that, my Ouija board's planchette is edging toward "insufferable asshole".
Mental note: be sure not to be that guy if you ever turn professor.
There is plenty of "cred" to be earned without that; you can still be pulling your hair out debugging a compiler written in Lisp, find years-old bugs in it and so on.
I don't know anything else about your ex-prof other than what you have in the comment, but based on that, my Ouija board's planchette is edging toward "insufferable asshole".
Mental note: be sure not to be that guy if you ever turn professor.
Unfortunately universities are full of such folks.
Our Physics III was even worse, it was one of those that was proud of hard it was to go through his final semester exam.
Thankfully they tend to be a minority, I also met several that became an a good example of how teaching should be like.
Our Physics III was even worse, it was one of those that was proud of hard it was to go through his final semester exam.
Thankfully they tend to be a minority, I also met several that became an a good example of how teaching should be like.
It's all just specific instances of the post correspondence problem!!
They both practically translate and optimize, so yeah, that makes sense.
On the surface a "modern" x86 is an interpreter/compiler. Why can't we jit/compile directly to quecto code?
and an interpreter
Compilers all the way down!
Every software is a compiler. It takes mouse clicks and keyboard presses and converts them into machine code.
No, most software is existing machine code, your clicks only “navigate” inside its control flow. They never create any new code.
This is not terribly hard, though,—Forth implementations have long explored[1] the road from emiting a list of VM instructions (“token threading”) to emitting a list of VM instruction implementation entry points (“direct threading”, although “indirect threading” arguably fits this as well) to emitting a stream of call instructions targeting said entry points (“subroutine threading”) to copying the implementation bodies into the stream (“inline threading”).
With sufficient dedication, you can even cut out the bodies from the binary the compiler of your high-level implementation language produced, to piggyback on its target support. Gforth[2] among others does this in the land of Forth, but the more well-known implementation is perhaps the dyngen code generator[3] used in Qemu before the switch to TCG in version 0.10.
Generating machine code isn’t difficult, and neither is modifying a (low-level) bytecode generator to do it[4]. Generaring good machine code is difficult.
[1] http://www.bradrodriguez.com/papers/moving1.htm
[2] https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Dyn...
[3] https://gitlab.com/qemu-project/qemu/-/blob/v0.9.1/qemu-tech..., rendered as https://web.archive.org/web/20081120011949if_/http://bellard...
[4] https://github.com/EarlGray/c4/blob/master/JIT.md
With sufficient dedication, you can even cut out the bodies from the binary the compiler of your high-level implementation language produced, to piggyback on its target support. Gforth[2] among others does this in the land of Forth, but the more well-known implementation is perhaps the dyngen code generator[3] used in Qemu before the switch to TCG in version 0.10.
Generating machine code isn’t difficult, and neither is modifying a (low-level) bytecode generator to do it[4]. Generaring good machine code is difficult.
[1] http://www.bradrodriguez.com/papers/moving1.htm
[2] https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Dyn...
[3] https://gitlab.com/qemu-project/qemu/-/blob/v0.9.1/qemu-tech..., rendered as https://web.archive.org/web/20081120011949if_/http://bellard...
[4] https://github.com/EarlGray/c4/blob/master/JIT.md
... unfortunately.
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 PyPy 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.