Earlier quoted context omitted.
Why do passes anymore when we have invented egraphs?
Egraphs are for optimization passes, which operate on the same IR, and (without egraphs) may undo and/or prevent each other and are repeated for more optimization. Nanopass is compiler passes, which each have their own IR, and run once in a fixed sequence. Egraphs also require the IR to be defined a specific way, which prevents some optimizations. My understanding of https://github.com/bytecodealliance/rfcs/blob/main…
Nanopass Framework: Clean Compiler Creation Language
31–40 of 40 posts
Re: Nanopass Framework: Clean Compiler Creation Language
#32Wouldn't this kind of architecture yield a slower compiler, regardless of output quality? Conceptually, trying to implement the least-amount of passes with each doing as much work as possible would make more sense to me.
There is nothing stopping you from building an old-fashioned single-pass compiler, if compile time is your only concern. The code it generates just wouldn't be very good.
Define "very good".
The very simplest optimizations get you almost all the benefit. Proebsting's Law applies: Compiler Advances Double Computing Power Every 18 Years
Re: Nanopass Framework: Clean Compiler Creation Language
#33Also I doubt that a common framework can be used by many languages at all. Usually a mature language compiler is self-hosted, which makes near to impossible to incorporate in it some thirdparty library/framework written in some other language.
Re: Nanopass Framework: Clean Compiler Creation Language
#34I learned how to build a compiler using the nanopass approach and I still think it was a good way to learn, but I would not build another real compiler that way.
Building a lot of passes was great for initial development of the compilation pipeline, but was terrible for maintenance and relatively limited for creating optimizations. Bugfixes in an early pass would frequently require changes across several subsequent ones, especially if any change in representation were required.
About 8 months in, I adopted the a Sea of Nodes[2] approach for the optimizer, type inference, and scheduling but kept my nanopass ingestion, allocation and codegen passes. At the 12 month mark, the v1 compiler was functional but had limitations.
For the next leg of the project I decided to switch fully to Sea of Nodes. The final compiler was much better; orders of magnitude faster, more flexible, much easier to debug and test, more features, and about the same amount of code.
Sea of Nodes takes the core idea of isolating passes to its logical conclusion by narrowing the scope of each change down to a single transformation on a single graph node. Operations are worklist based and can happen in any order, eliminating the pass ordering problem. The IR is a graph that follows simple and consistent semantics from parsing through all phases down to code generation. Going from 20+ IR dialects/sub-dialects to a single graph representation was a huge plus.
[1] https://github.com/pangloss/pattern [2] https://github.com/SeaOfNodes/Simple
Re: Nanopass Framework: Clean Compiler Creation Language
#35Earlier quoted context omitted.
Egraphs are for optimization passes, which operate on the same IR, and (without egraphs) may undo and/or prevent each other and are repeated for more optimization. Nanopass is compiler passes, which each have their own IR, and run once in a fixed sequence. Egraphs also require the IR to be defined a specific way, which prevents some optimizations. My understanding of https://github.com/bytecodealliance/rfcs/blob/main…
There is no reason why compiler passes cannot be in an egraph, they are more general than optimizations. When you think about it, traditional compiler concerns like instructions selection are sort of a optimization problem if you squint.
Additionally, egraphs express rewrites on a single language. Compilers are fundamentally translators between different languages; how do you write typechecking as an egraph rewrite rule? Or conversion to assembly?
Re: Nanopass Framework: Clean Compiler Creation Language
#36Earlier quoted context omitted.
Egraphs are for optimization passes, which operate on the same IR, and (without egraphs) may undo and/or prevent each other and are repeated for more optimization. Nanopass is compiler passes, which each have their own IR, and run once in a fixed sequence. Egraphs also require the IR to be defined a specific way, which prevents some optimizations. My understanding of https://github.com/bytecodealliance/rfcs/blob/main…
There is no reason why compiler passes cannot be in an egraph, they are more general than optimizations. When you think about it, traditional compiler concerns like instructions selection are sort of a optimization problem if you squint.
Re: Nanopass Framework: Clean Compiler Creation Language
#37Earlier quoted context omitted.
I wonder if there's some implicit wisdom that layering/modularizing incurs some communication cost that can cancel all the benefits.
This is a question folks are asking about in terms of organization building too. Bottlenecks are changing and it's pretty interesting.
Re: Nanopass Framework: Clean Compiler Creation Language
#38Earlier quoted context omitted.
This is a question folks are asking about in terms of organization building too. Bottlenecks are changing and it's pretty interesting.
Do you remember articles or books about this ? I'd be curious to read more
https://sequoiacap.com/article/from-hierarchy-to-intelligenc...
Re: Nanopass Framework: Clean Compiler Creation Language
#39Re: Nanopass Framework: Clean Compiler Creation Language
#40I'm often skeptical of the desire to create a lot of passes. In the early Vale compiler, and in the Mojo compiler, we were paying a lot of interest on tech debt because features were put in the wrong pass. We often incurred more complexity trying to make a concept work across passes than we would have had in fewer, larger passes. I imagine this also has analogies to microservices in some way. Maybe other compiler peo…