Live data from Hacker News

Nanopass Framework: Clean Compiler Creation Language

nanopass.org

31–40 of 40 posts

Re: Nanopass Framework: Clean Compiler Creation Language

#31

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…

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

#32
post #9

Wouldn'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.

> 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

#33
As a compiler developer I see no reason to use a lot of passes. My language compiler is designed in such a way, that it does its frontend work (except tokenization and syntax analysis) in one big pass, which does all the stuff necessary. Splitting this work in multiple passes is impossible due to language specifics - interleaving many compilation stages is necessary for many language features to function properly.

Also 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

#34
I built a nanopass-like compiler using Clojure (plus a pattern-matching library[1] that I created) to compile a subset of Python all the way down to bytecode for Untether AI's inference accelerator, a RISC ISA extended with an at-memory compute array. The python subset allowed full control of the array via type-inference instead of intrinsic ops.

I 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

#35

Earlier 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.

Egraphs fundamentally require a first-order language, i.e. no lambda functions, because they do not handle scoping well. There are workarounds that work in some circumstances, but no general solution (that I'm aware of).

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

#36

Earlier 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.

But why? The goal of egraphs is to optimally order passes, but these passes have a single order.

Re: Nanopass Framework: Clean Compiler Creation Language

#37
post #7

Earlier 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.

Do you remember articles or books about this ? I'd be curious to read more

Re: Nanopass Framework: Clean Compiler Creation Language

#38
post #37

Earlier 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

Hmm, there was this recent article - not exactly right but overlaps and has interesting ideas

https://sequoiacap.com/article/from-hierarchy-to-intelligenc...

Re: Nanopass Framework: Clean Compiler Creation Language

#39
post #37

Earlier quoted context omitted.

Do you remember articles or books about this ? I'd be curious to read more

Hmm, there was this recent article - not exactly right but overlaps and has interesting ideas https://sequoiacap.com/article/from-hierarchy-to-intelligenc...

Thanks a ton :)

Re: Nanopass Framework: Clean Compiler Creation Language

#40
post #4

I'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…

Vaguely resembles microkernel vs monolithic debate.
Post reply on HN