This post and the Hydra paper reminds me a lot of Ruler and Enumo.
* Nandi, Chandrakana, et al. "Rewrite rule inference using equality saturation." Proceedings of the ACM on Programming Languages 5.OOPSLA (2021): 1-28.
* Pal, Anjali, et al. "Equality Saturation Theory Exploration à la Carte." Proceedings of the ACM on Programming Languages 7.OOPSLA2 (2023): 1034-1062.
I will need to read more about both of these techniques along with Synthesizing Abstract Transformers.
> Out in the literature we can find a huge number of dataflow analyses, some of which are useful to optimize some kinds of code — but it’s hard to know which ones to actually implement. […] First, implementing the analysis itself, which requires creating an abstract version of each instruction in the compiler’s IR: these are called dataflow transfer functions. For example, to implement the addition operation for integer ranges, we can use [lo1, hi1] + [lo2, hi2] = [lo1 + lo2, hi1 + hi2] as the transfer function.
What papers would you recommend for learning implementing dataflow analysis? For example, foundational or tutorial papers.
Every good book on compilers. I learned this from [1]. The (hard to read) original papers include [2, 3]. Interesting tidbit: Gary Kildall, one of the pioneers of abstracting dataflow analyses, later played a role in the (in)famous deal between Microsoft and IBM that became the starting point for the dominance of the former. The foundational theory behind this is abstract interpretation for which you have many introductions, including [5, 6], with the (hard to read) original being [7].
[5] F. Nielson, H. Riis Nielson, C. Hankin, Principles of Program Analysis.
[6] X. Rival, K. Yi, Introduction to Static Analysis: An Abstract Interpretation Perspective.
[7] P. Cousot, R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints.
The order goes from simpler to more complex data flow analysis frameworks. These frameworks allow you to encode dataflow problems and solve them.
* Kam, John B., and Jeffrey D. Ullman. "Monotone data flow analysis frameworks." Acta informatica 7.3 (1977): 305-317.
* Reps, Thomas, Susan Horwitz, and Mooly Sagiv. "Precise interprocedural dataflow analysis via graph reachability." Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 1995.
* Sagiv, Mooly, Thomas Reps, and Susan Horwitz. "Precise interprocedural dataflow analysis with applications to constant propagation." TAPSOFT'95: Theory and Practice of Software Development: 6th International Joint Conference CAAP/FASE Aarhus, Denmark, May 22–26, 1995 Proceedings 20. Springer Berlin Heidelberg, 1995.
* Reps, Thomas, et al. "Weighted pushdown systems and their application to interprocedural dataflow analysis." Science of Computer Programming 58.1-2 (2005): 206-263.
* Späth, Johannes, Karim Ali, and Eric Bodden. "Context-, flow-, and field-sensitive data-flow analysis using synchronized pushdown systems." Proceedings of the ACM on Programming Languages 3.POPL (2019): 1-29.
I am not sure why you mention LLM, the post mentions LLVM. Second, you can have different optimization options with different tradeoffs in compile-time and run-time. Third, even if the default and only options distributed with clang are too compile-time intensive, the good news is that this is open source and you could argue against it, or fork and maintain your own compile-time run-time tradeoff compiler along with other people who also want that behaviour. I don't see any benefit of arguing against research. Having new techniques to improve compilers is not a zero sum game.
Readit News
Thanks for sharing! Really exciting stuff!
What papers would you recommend for learning implementing dataflow analysis? For example, foundational or tutorial papers.
[1] https://cs.au.dk/~amoeller/spa/
[2] G. A. Kildall, Global expression optimization during compilation.
[3] G. A. Kildall, A Unified Approach to Global Program Optimization.
[4] https://en.wikipedia.org/wiki/Gary_Kildall
[5] F. Nielson, H. Riis Nielson, C. Hankin, Principles of Program Analysis.
[6] X. Rival, K. Yi, Introduction to Static Analysis: An Abstract Interpretation Perspective.
[7] P. Cousot, R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints.
would a x1000 compute cluster provide a meaningful performance boost ( of the generated binaries)?
For example, clang compilation times have slowed down something like 5-6x faster than the code they generate.
As a developer I can come up with better structure in my code much faster if I can try more things out in a day.
Now we want to add LLMs of all things in there? I'm not looking forward to code taking one or two orders of magnitude longer to compile