Deep Learning for Compilers(era.ed.ac.uk)
era.ed.ac.uk
Deep Learning for Compilers
https://era.ed.ac.uk/handle/1842/36866
9 comments
I long thought that compilers are an area where deep learning could make a huge difference, with dynamic compiler construction you could even do a hardware architecture search to find HW and instructions that is efficient after compiler optimisations, but I guess that step is sill a few years down the line. It might turn out that moving complexity to the compiler this way (instead of complex branch perdictors in HW) is the better choice.
A past discussion: https://news.ycombinator.com/item?id=18748193
This is the PhD dissertation of one of the authors of that article.
I'm concerned because (1) when deep learning fails, it tends to fail in very weird ways and (2) current deep learning techniques tend largely to be black boxes.
So you could end up with a compiler that largely works, but occasionally generates incorrect code, and if it does, there is no "underlying reason" for the code generation error, and you may not even be able to extract a small reproducible case, because the error may only appear when compiling the whole original compilation unit.
So you could end up with a compiler that largely works, but occasionally generates incorrect code, and if it does, there is no "underlying reason" for the code generation error, and you may not even be able to extract a small reproducible case, because the error may only appear when compiling the whole original compilation unit.
>when deep learning fails, it tends to fail in very weird ways
I like to describe it as ML/AI leans towards catastrophic failure.
The quintessential example being turning a cat into an ostrich by modifying a few key pixels.
I like to describe it as ML/AI leans towards catastrophic failure.
The quintessential example being turning a cat into an ostrich by modifying a few key pixels.
Modern optimizing compilers are already effective black boxes with massive "surface area complexity" that fail in strange ways and have bugs. That they have heuristics written by humans doesn't necessarily mean they're explicable. None of that is new, honestly. You can find lots of bugs with already existing tools.
The paper in question also uses DL for two things that have nothing to do with optimization, benchmark generation and fuzzing (which actually make existing compilers more robust), and the third technique which does learn optimization heuristics (between domains, even!) but it comes across as trivially deterministic. There is nothing to suggest that, say, deep learning cost models for a compiler will "magically generate invalid code" anymore than a compiler today already will. Furthermore, in this case the model isn't doing semantic translation between the input domain and output domain, it's rather answering queries like "is this better on a GPU or CPU" or "What is the best granularity to do this parallel task" i.e. it is constrained to a problem that is highly dimensional and variable, but in a sense has no impact on the outward semantics. This is how many such approaches work: they do not use models to "generate semantically equivalent results", but instead use them to replace existing oracles that answer questions a compiler already had to ask: "Is representation A cheaper than representation B, in this context?" is a very different problem than "Magically generate programs equivalent to A." The question is then whether your hand-written oracle is better than a machine learned one.
The problem you're imagining, I suspect, is that the system will hit strange "performance cliffs" where one tiny tweak to the source will magically tank your performance, similar to adversarial approaches. But this is already the case today; writing highly performance sensitive code is largely a dance with the devil and you have to be working in tandem with the compiler constantly. On the other hand, "high level optimization" like choosing workload granularity is still understood rather poorly, I think. I don't think it's immediately clear if the current way we do things is better or not. Compilers make many, many individual decisions that are "locally optimal" without necessarily getting global optimums.
Much of this can be said of SQL optimizers, which have very similar problems and followed a similar history (complex, hand-written heuristic-based optimizers vs cost models combined with searching the problem space.) In a similar vein I suspect an approach like this could be very powerful when combined with designs like equality saturation, which would effectively make a modern compiler look like an advanced, global cost optimizer in a SQL database.
I suggest you try actually reading the paper. It's pretty interesting.
The paper in question also uses DL for two things that have nothing to do with optimization, benchmark generation and fuzzing (which actually make existing compilers more robust), and the third technique which does learn optimization heuristics (between domains, even!) but it comes across as trivially deterministic. There is nothing to suggest that, say, deep learning cost models for a compiler will "magically generate invalid code" anymore than a compiler today already will. Furthermore, in this case the model isn't doing semantic translation between the input domain and output domain, it's rather answering queries like "is this better on a GPU or CPU" or "What is the best granularity to do this parallel task" i.e. it is constrained to a problem that is highly dimensional and variable, but in a sense has no impact on the outward semantics. This is how many such approaches work: they do not use models to "generate semantically equivalent results", but instead use them to replace existing oracles that answer questions a compiler already had to ask: "Is representation A cheaper than representation B, in this context?" is a very different problem than "Magically generate programs equivalent to A." The question is then whether your hand-written oracle is better than a machine learned one.
The problem you're imagining, I suspect, is that the system will hit strange "performance cliffs" where one tiny tweak to the source will magically tank your performance, similar to adversarial approaches. But this is already the case today; writing highly performance sensitive code is largely a dance with the devil and you have to be working in tandem with the compiler constantly. On the other hand, "high level optimization" like choosing workload granularity is still understood rather poorly, I think. I don't think it's immediately clear if the current way we do things is better or not. Compilers make many, many individual decisions that are "locally optimal" without necessarily getting global optimums.
Much of this can be said of SQL optimizers, which have very similar problems and followed a similar history (complex, hand-written heuristic-based optimizers vs cost models combined with searching the problem space.) In a similar vein I suspect an approach like this could be very powerful when combined with designs like equality saturation, which would effectively make a modern compiler look like an advanced, global cost optimizer in a SQL database.
I suggest you try actually reading the paper. It's pretty interesting.
> Modern optimizing compilers are already effective black boxes
Not the way DL models are. You can step through a forest of switch / if statements. You can even step through something like a lex / yacc state table, as unpleasant as that prospect is. You cannot meaningfully step through an algorithm that passes your data through a series of multiplications with large floating point matrices.
> The paper in question also uses DL for two things that have nothing to do with optimization, benchmark generation and fuzzing
I agree, those two applications seem unobjectionable.
> "Is representation A cheaper than representation B, in this context?" is a very different problem than "Magically generate programs equivalent to A."
Agreed. I was more concerned about the latter application (and some other commenters in this discussion apparently had the same expectation).
> one tiny tweak to the source will magically tank your performance [...] But this is already the case today
No the same way, I suspect. A DL model could, for instance, tank your performance because of the way a particular variable is named because of some spurious correlation it learned from its training set.
Not the way DL models are. You can step through a forest of switch / if statements. You can even step through something like a lex / yacc state table, as unpleasant as that prospect is. You cannot meaningfully step through an algorithm that passes your data through a series of multiplications with large floating point matrices.
> The paper in question also uses DL for two things that have nothing to do with optimization, benchmark generation and fuzzing
I agree, those two applications seem unobjectionable.
> "Is representation A cheaper than representation B, in this context?" is a very different problem than "Magically generate programs equivalent to A."
Agreed. I was more concerned about the latter application (and some other commenters in this discussion apparently had the same expectation).
> one tiny tweak to the source will magically tank your performance [...] But this is already the case today
No the same way, I suspect. A DL model could, for instance, tank your performance because of the way a particular variable is named because of some spurious correlation it learned from its training set.
A github crawler I cobbled together back in '16 can be trivially modified to scrape compiler code that could be used to train such DL models.
https://github.com/DataMeta/GithubSourceCrawler
https://github.com/DataMeta/GithubSourceCrawler
ML would certainly help compilers. Some problems like register allocation is NP-complete. ML with a large training data set could probably do a good job in optimization.
Already being used at the chip level, e.g. for branch prediction.
deep learning systems are evolving toward similar architectures as compilers (front/back ends, etc) too. Interesting edge to watch
Where is the code?
wouldn't this affect reproducible builds ?
Author here. In the sense that a trained neural net produces the same output from the same input, this is deterministic. But I don’t think that’s what you’re getting at. Where it gets interesting is if we inserted a feedback loop (such as FDO) so that the compiler could fine tune itself on past decisions. In that case, the build would still be deterministic, but the compiler would keep changing, invalidating the build cache.
Why?
Two of the projects (fuzzing, benchmark sets) don't affect the compiler behavior at all. The third project (heuristics) already interfere with reproducible builds if they use things like time budgets but could also be made entirely determistic.
Two of the projects (fuzzing, benchmark sets) don't affect the compiler behavior at all. The third project (heuristics) already interfere with reproducible builds if they use things like time budgets but could also be made entirely determistic.