Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Nanopass Framework: Clean Compiler Creation Language

nanopass.org

Post reply on HN
Print view View original

21–30 of 40 posts

Re: Nanopass Framework: Clean Compiler Creation Language

#21

Post by spankalee »

munificent wrote: post #16
verdagon wrote: 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…

I work on Dart. I don't work directly on the compilers much, but I've gathered from talking to my teammates who do that, yeah, generally fewer passes is better. From a maintenance perspective, it's really appealing to have a lot of small clearly defined passes so that you can have good separation of concerns. But over time, they often end up needing to interact in complex ways anyway. For example, you might think you…

Hey - I used to be on your team long ago :)

> For example, you might think you can do lexical identifier resolution and type checking in separate passes. But then the language gets extension methods and now it's possible for a bare identifier inside a class declaration to refer to an extension method that can only be resolved once you have some static type information available.

Some of this is language design though. If you make it a requirement that scope analysis can be done in isolation (so that it's parallelizable), then you design things like imports and classes so that you never have identifiers depend on types or other libraries.

I've been working on a language lately and thinking about passes - mostly where they run and what previous state they depend on - has been a big help in designing language so the compiler can be parallel, cache, and incremental friendly.

Re: Nanopass Framework: Clean Compiler Creation Language

#22

Post by bjoli »

vmsp wrote: 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.

Optimization level 2 in chez scheme does about 100 KLOC/s in my pretty modest machine, while also producing code that is pretty darn fast.

Re: Nanopass Framework: Clean Compiler Creation Language

#23

Post by pfdietz »

soegaard wrote: post #12
pfdietz wrote: post #10

Earlier quoted context omitted.

Yes, and a similar question is the organization of the thing being acted on by the passes. If I understand correctly, this is in scheme and the things being acted on are trees with pointers. A performance optimized compiler, on the other hand, will probably use some sort of array-based implementation of trees. There's also a question of data about the trees (like, a flow graph) being recomputed for each nanopass. Als…

Nanopass uses structures internally to represent the programs. The Nanopass dsl just gives the user a nicer syntax to specify the transformations.

So, a conventional linked representation of a tree (but not a tree of cons cells).

Re: Nanopass Framework: Clean Compiler Creation Language

#24

Post by mncharity »

LegNeato wrote: post #15
verdagon wrote: 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…

Why do passes anymore when we have invented egraphs?

Recent related discussion/blog[1].

[1] The acyclic e-graph: Cranelift's mid-end optimizer https://news.ycombinator.com/item?id=47717192

Re: Nanopass Framework: Clean Compiler Creation Language

#25

Post by armchairhacker »

LegNeato wrote: post #15
verdagon wrote: 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…

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/accepted/... is that cranelift’s egraph optimizations are pure expression reordering/duplication/deduplication and rewrite rules.

Re: Nanopass Framework: Clean Compiler Creation Language

#26

Post by eholk »

verdagon wrote: 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…

I used the Nano pass framework for my language when I was in grad school and loved it. I forget the exact count but I think we had 40 or 50 passes. Generally each pass either did some analysis that would be consumed by a later pass or it rewrote some higher level concept or feature in terms of more primitive operations.

Nanopass had a DSL for describing what forms you delete from each intermediate language and which forms you add. Each pass was generally pretty small then, usually just replacing one form with some set of other forms.

Be cause each pass was really small it was pretty easy to reorder them. Sometimes we figured out if we moved one optimization sooner then later passes worked better. Or we realized some analysis was useful somewhere else so we rearranged the passes again. The pass ordering made it really clear which analysis results are valid at each point in the compilation process.

Re: Nanopass Framework: Clean Compiler Creation Language

#27

Post by norir »

marssaxman wrote: post #20
vmsp wrote: 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.

This highly depends on the language and your skill as a compiler writer. You can write a single pass assembler that generates great code but you have to of course write the low level code yourself (including manual register assignment). To do decent automatic register assignment, I agree you need at least two passes, but not 10 or more.

Re: Nanopass Framework: Clean Compiler Creation Language

#28

Post by soegaard »

pfdietz wrote: post #23
soegaard wrote: post #12

Earlier quoted context omitted.

Nanopass uses structures internally to represent the programs. The Nanopass dsl just gives the user a nicer syntax to specify the transformations.

So, a conventional linked representation of a tree (but not a tree of cons cells).

Yes.

Re: Nanopass Framework: Clean Compiler Creation Language

#29

Post by munificent »

spankalee wrote: post #21
munificent wrote: post #16

Earlier quoted context omitted.

I work on Dart. I don't work directly on the compilers much, but I've gathered from talking to my teammates who do that, yeah, generally fewer passes is better. From a maintenance perspective, it's really appealing to have a lot of small clearly defined passes so that you can have good separation of concerns. But over time, they often end up needing to interact in complex ways anyway. For example, you might think you…

Hey - I used to be on your team long ago :) > For example, you might think you can do lexical identifier resolution and type checking in separate passes. But then the language gets extension methods and now it's possible for a bare identifier inside a class declaration to refer to an extension method that can only be resolved once you have some static type information available. Some of this is language design though…

> I used to be on your team long ago :)

I miss getting to talk to you about music!

> Some of this is language design though.

Totally, but it's no fun to be stuck between users wanting some eminently useful feature and not being able to ship it because of your compiler architecture.

Post reply on HN