[tadeegan]

Compilers have soooo many heuristics. And a lot of it looks like a chess or Go game: You have a list of 100s of AST optimization passes (possible moves) that preserve the semantics of the program but you have limited compute with which to run iterations of these passes. What order and combination of these should you use?

[titzer]

This is known as the "phase ordering problem". Despite the super-exponential (even unbounded, because phases can be repeated) space, I think this is more tractable for certain subsets. For example, in sea of nodes compilers, like HotSpot, Graal, and TurboFan, forward dataflow analyses that do reductions (i.e. always make the graph smaller and/or cheaper) can be combined into one mega-pass where they positively interact each other. The problem is that some problems are not forward data flow problems and some transformations are not simple reductions. Also, some phases make use of type information which can be destroyed or obscured by lowering.

[quotemstr]

In general, every heuristic in systems programming --- kernels z compilers, databases, whatever --- is an opportunity to substitute an ML system.

[brrrrrm]

today, learned heuristics have a couple of pitfalls that make them hard to add to such systems

1. they are usually hard to run efficiently

2. they are usually hard to explain

The former is definitely changing with low precision formats like fp16 and useful coprocessors that can do matrix multiplications efficiently (M1, Intel). The latter hasn't been developed much and unless you're just training a model to memorize the entire space the heuristic operates in, it can be scary to trust it on unseen data.

[zasdffaa]

Which you should use are often unknowable because it's often about how the code is driven by the data - you need to know the characteristics of the data to know how the code will behave, only then can you meaningfully talk about picking a 'better' heuristic.

Analogy: otherwise you're just optimising the design of a car. But optimising it for what? speed, efficiency, reliability, price, weight, carrying capacity... You first need to know how it's expected to be used.

I guess local inlining might sometimes be an unconditional win, but even then only under specific circumstances.

(disclaimer: I know something but am not an expert)

[xdfgh1112]

Profile guided optimisation is a thing.

[yunohn]

Well, in this case, TFA:

> Better code optimization can significantly reduce the operational cost of large datacenter applications

They’re aiming to spend a bit more time compiling models, to reduce the scaled operational costs moving forward.