Comment by BeeOnRope
2 years ago
Modern compilers are not doing much searching in general. It's mostly apply some feed-forward heuristic to determine whether to apply a transformation or not.
I think a slower, search based compiler could have a lot of potential for the hottest parts you're willing to spend exorbitant time on a search.
I have heard search based compiler optimization called "superoptimization"[1]. It seems interesting, but as far as I know has not seen much industrial use.
1. https://blog.regehr.org/archives/2578
It simply doesn’t scale. You can only superoptimize very short runs of code, nowhere anywhere close to even smaller code bases, let alone big ones.
It scales well enough. You can apparently run Souper on SQLite in 24 hours with a beefy machine, according to a talk I recently attended, by one of the developers.
1 reply →
I understand the compiler Microsoft uses to build release versions of Windows, Office etc is like this and can take days to run.
and well worth the cost
> Modern compilers are not doing much searching in general.
This is false. Any compiler that does register allocation and instruction scheduling (all of them) is searching for an optimal (or just good enough) solution to an optimization problem.
Where things get fun is when two optimizations combine to make things worse. They never tell you about that in compiler class!
It's like designing a house. If you want the master closet bigger, the master bath has to shrink. Everything is a tradeoff.
You have this exact issue in VLIW and it's exactly where you can't cheat by using heuristics:
Combinatorial Register Allocation and Instruction Scheduling
https://dl.acm.org/doi/10.1145/3332373
Can you give an example?
In general, searching any significant space is very slow, applying heuristics is much quicker.
I'm not sure there is a clear separation between applying heuristics and searching a space. Often in compilers you search a subset of a space using heuristics, and you can adjust those to control how much of the space you cover.
For example, here is a pass that reorders WebAssembly globals in the Binaryen optimizer:
https://github.com/WebAssembly/binaryen/blob/main/src/passes...
We have a simple criteria for the quality of a solution - how big the binary size is with an order - but the space of possible orders is huge (every permutation that keeps every global after its dependencies). What we do is a targeted search of that space using some heuristics using parameters that work well enough and aren't too slow in practice.
4 replies →
I don't know what you're asking for - this isn't some kind of controversial topic - any iterative algo that isn't polynomial time (or is approximate) is search.
In the context of compilers there are many. Look at this block diagram for Chaitin's register allocator:
https://en.wikipedia.org/wiki/Register_allocation#Principle_...
That's a search because it tries an allocation, possibly incurs a spill, tries again.