Comment by almostgotcaught
2 years ago
> 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.
> I'm not sure there is a clear separation between applying heuristics
There is and it's quite simple: if your heuristic reduces the size of your search space faster than it takes to perform the search (ie try solutions) then you have a real algo on your hands. Otherwise you're just searching. This is basically the border between P and NP and it's just that in compilers most of the problems are NP hard so none of the heuristics are really that good.
3 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.