They can extract some ILP, but most of that is because it has no limitations but the semantics of the instruction set. It also cheats and can speculate just about everything legally, because it can always undo it.

A large amount of the ILP is, AFAIK, from being able to prefetch accurately (IE guess what memory will be accessed) and guess branch directions correctly.

This is not possible to do as well statically. You actually can do it well dynamically (IE i could make a branch guessing thread and a prefetching thread), but you can't do it fast enough.

In a lot of workloads, most time is spent stalling for memory.

Also note that in VLIW, you have to extract ILP or you are just wasting time (IE are executing NOPs). You end up with a half or 3/4 empty pipeline. So unless you can predict you are going to stall for memory well, you are wasting the pipeline. On the other hand, modern OOO cores can just extract more ILP when possible. IE when stalling for memory, they can figure out what they could be doing otherwise.

It sounds like you just proved the point.

I always wondered how CPUs could do all of this so fast. Doesn't all the branch prediction etc. have to be done by a kind of program that is "parsing" instructions on the fly and storing state about its execution? How is that implemented, and how is it faster than doing the equivalent in software?

Branch prediction under latency constraints is a difficult task! I believe perceptrons are the SOTA right now (have recently beat out TAGE predictors to take the crown once again) but are very energy intensive, the alternative is (which is currently used I think) are two level look up tables.

Maybe it's like JITs vs static compilers - we're better off with JIT even if your language is static, because you can adapt to real runtime conditions.

But we aren't better off with JIT in software. x64 processors work because they are doing things dynamically in separate hardware. It is part of how they use ever increasing transistor budgets to speed up serial processing.

Really, at this point the transistor budget is mostly going to bigger caches and more cores.

It's really little short of a miracle that Intel still managed to extract double digit percent improvements in serial code for all of Sandy Bridge, Haswell and Skylake.

It's less of a miracle and more like "larger OoO window, K done"

No, that's not so easy.

You cannot fill that out-of-order window if you mispredict branches. So the branch prediction has gotten better and better, to an absurd level of accuracy.

You also need more execution units, to accommodate more kinds of serial code without stalling the pipeline. In Skylake they also improved the retirement unit, apparently to improve hyperthreading performance.

There are also better prefetchers and decoders, while the decoders also become more complicated because this is good old x86's variable-length encoding, with further complications for x86-64, AVX, and so on.

TLBs also get more complex (there have been two-level TLBs for a while now), though I guess that is part of the "bigger caches" part.

I agree, I was being a little blunt, but it's not necessarily as complicated as people make it out to be. The best branch predictor is once again the perceptron, and it beats current Intel chips on benchmarks. (I would hazard a, guess that Intel uses something like the tage predictor)

JITs do not and cannot have a complete program view.

Whole program compiler can insert JIT-calling code (specializing for common pattern), JIT compiler cannot view whole program.

One of the things JITs can't do is to add and/or remove parallelism from the program (i.e., add/remove OpenMP pragmas).

> JITs can't do is to add and/or remove parallelism from the program

Of course they can. A trivial practical example is the JVM JIT using vector instructions to add parallelism to a program that didn't have any before. But a JIT compiler could also profile code and add thread-level parallelism if it wanted.

For thread-level parallelism to be added you need to perform something akin to Fourier-Motzkin resolution algorithm or Omega test to find out what dependencies program has and has not.

FM is NP-hard. Omega test is imprecise.

And in general you need more complicated checks like aliasing checks. Which are equal to stopping problem, most of the time.

Usually you can't spend that amount of time on EACH INVOCATION of a program.

The techniques you are talking about are for proving that there is parallelism. The beauty of a JIT is that you can speculate that there is parallelism, go ahead, and then sort out the mess later and recompile to sequential if there wasn't.

https://en.wikipedia.org/wiki/Speculative_multithreading

You can use hardware functionality such as TSX to support this.

You can't speculate about parallelism when dealing with shared resource.

It is unbelievable you even suggested it.

TSX won't save you.

> You can't speculate about parallelism when dealing with shared resource

Why do you think that? What do you think the optimistic software transactional memory algorithms are doing if not speculating on parallel access to shared memory?

Because you have O(n) for size of transaction and this O will quickly rise to overflow any buffers you have in hardware, for one.

Because Microsoft tried to add STM to the .Net and get 4x slower code after extensive effort: http://www.mail-archive.com/[email protected]/msg7973...

Should I continue from these two arguments?

You've just said that you 'can't speculate about parallelism when dealing with shared resource', and then gave me an example of a system that did exactly that. Clearly, it is possible to do speculative parallelism of shared resources. We may not yet know how to make it efficient, but it is possible.

From what I gather, STM in .Net heavily relies on the static program analysis.

You may see it as a proof of your point, but I see it as a counterexample - a team of smart people was not able make speculative parallelism efficient even with static analysis. JIT will be even less efficient as it has to keep and account for tracing information and for speculation logs. These two interact in interesting way, I guess.

One reason is that the idea behind 'just need a smart compiler' was doomed from the start. If you build something that won't shine unless everyone that builds a compiler for it makes sure to extract plenty of instruction level parallelism, it is doomed to fail. Maybe these days with LLVM it could have been a little more practical, but Intel has dominated largely by making sure poorly written programs run as fast as possible. To put all that aside and hope that compilers and programmers become much more sophisticated was never going to happen, especially because so much software is already set and won't change.

LLVM is the godsend that any new architecture (especially a VLIW) to compete with Intel needed. I'm the founder of a startup that has made a new VLIW processor with our toolchain built on top of LLVM... We get the front end and all of the languages it supports virtually for free (we've only had to make small tweaks to clang), and get to focus our effort on just the parts important to us, our actual target backend and the unique optimization steps. Right now we can take any code that compiles through LLVM and run it on a single one of our cores while finding a good chunk of ILP (we are quad issue, averaging close to 2.5 IPC, sometimes higher), and be beating out the performance of some ARM and DSP cores that are 10x the size. Multi core parallelism requires including our hand tuned libraries, but our true MIMD style of task and data level parallelism is a lot more flexible than SIMD/SIMT/SMP that you are stuck with on existing chips.

I'm not sure why GCC would have been anything different.

No, porting GCC to a new architecture is not a big deal. The really complex part is the ABI, and what I have heard from former GCC developers is that it's as much of a mess in LLVM, because it's simply a messy domain.

LLVM is much more compartimentalized, so we can make changes to the backend without touching/breaking other parts. The GCC loader was miles ahead of the LLVM loader up until the past few releases, and we were originally using a modified version of the GCC loader before switching.

LLVM also has a bunch of awesome projects like Poly for polyhedral compilation that we are able to use that don't exist at all for GCC, or are very difficult to integrate. LLVMs lego block like architecture (it was originally designed as a tool to help build toolchains) plus things like Tablegen enabled our single "real" software engineer/CTO to do initial bring up of a backend in under a month.

Is it the case that you can implement just a new backend and produce good machine code for your processor, or really do you need to modify the frontend to get it to generate code IR from which you can generate good machine code, because otherwise useful information has been lost by time you get the IR from the frontend?

We have played around with having "hints" in the original source code that will be preserved through the IR, but the vast majority of the optimizations and scheduling decisions we need to do are happening once it has been converted into machine code by the backend. I may be slightly off (I'm the dumb CEO/hardware architect), but I'm fairly sure 85%-90% of our compiler work has been done on the backend... I just remember being told some tweaks were made to clang due to some weird issue.

It's really three stages, not frontend and backend.

The first stage is the LLVM front end, Clang and other language parsers. They generate IR.

The middle stage is the LLVM optimizer, opt, which takes IR and runs a variety of optimization passes. Opt takes and gives IR.

http://llvm.org/docs/Passes.html

The third is the backend code generator. It lowers IR to the target ISA. There's a tablegen description, there's are MI scheduler models which abstract architectural information as well.

http://llvm.org/docs/WritingAnLLVMBackend.html

I think you really meant can you write an optimizing pass specifically for your target? Yes. But I don't think that modifying the real front end Clang is going to get you much of anything. Intrinsics are different; that's the programmer inserting ISA specific instructions rather than Clang extracting ISA specific information. Really, modifying Clang isn't going to get you anything.

Thomas, what were the 'small' Clang specific tweaks?

Was this not true of GCC as well?